KNN讲解

2020/4/191K最近邻(K-NEARESTNEIGHBOR)KNN分类算法2020/4/192主要内容1引言2KNN的基本思想3KNN算法的实现4KNN的优缺点5KNN的一些改进策略6KNN在实际问题中的应用2020/4/1931引言分类（Classification）是数据挖掘领域中的一种重要的技术，它是从一组已知的训练样本中发现分类模型，并且使用这个分类模型来预测待分类样本。建立一个有效的分类算法模型最终将待分类的样本进行处理是非常有必要的。2020/4/194目前常用的分类算法主要有：朴素贝叶斯分类算法（NaïveBayes）、支持向量机分类算法（SupportVectorMachines）、KNN最近邻算法(k-NearestNeighbors)、神经网络算法（NNet）以及决策树（DecisionTree）等等。2020/4/1954/19/20205KNN算法是一个理论上比较成熟的方法，最初由Cover和Hart于1968年提出，其思路非常简单直观，易于快速实现。因此，KNN算法以其实现的简单性及较高的分类准确性在中文文本自动分类等领域得到了广泛应用。2020/4/1962KNN的基本思想根据距离函数计算待分类样本X和每个训练样本的距离（作为相似度），选择与待分类样本距离最小的K个样本作为X的K个最邻近，最后以X的K个最邻近中的大多数所属的类别作为X的类别。KNN可以说是一种最直接的用来分类未知数据的方法。2020/4/197简单来说，KNN可以看成：有那么一堆你已经知道分类的数据，然后当一个新数据进入的时候，就开始跟训练数据里的每个点求距离，然后挑出离这个数据最近的K个点，看看这K个点属于什么类型，然后用少数服从多数的原则，给新数据归类。2020/4/1982020/4/1993KNN算法的实现(1)问题描述数据集：iris.data标准数据集-鸢尾花。采用KNN算法对iris.data分类。为了操作方便，对各组数据添加rowNo属性,第一组rowNo=1，共有150组数据,选择rowNo模3不等于0的100组作为训练数据集，剩下的50组做测试数据集。2020/4/1910初始化距离为最大值；计算未知样本和每个训练样本的距离dist；得到目前K个最临近样本中的最大距离maxdist；(2)实现步骤：2020/4/1911如果dist小于maxdist，则将该训练样本作为K-最近邻样本；重复步骤2、3、4，直到所有未知样本和所有训练样本的距离都算完；统计K-最近邻样本中每个类标号出现的次数；选择出现频率最大的类标号作为未知样本的类标号。2020/4/19124KNN的优缺点优点(1)算法思路较为简单，易于实现；(2)当有新样本要加入训练集中时，无需重新训练（即重新训练的代价低）；(3)计算时间和空间线性于训练集的规模（在一些场合不算太大）。2020/4/1913不足(1)分类速度慢；KNN算法的时间复杂度和存储空间会随着训练集规模和特征维数的增大而快速增加。因为每次新的待分样本都必须与所有训练集一同计算比较相似度，以便取出靠前的K个已分类样本。整个算法的时间复杂度可以用O(m*n)表示，其中m是选出的特征项(属性)的个数，而n是训练集样本的个数。2020/4/1914(2)各属性的权重相同，影响了准确率；当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，如果某一类的样本数量很大，那么可能目标样本并不接近这类样本，却会将目标样本分到该类下，影响分类准确率。2020/4/1915(3)样本库容量依赖性较强；(4)K值不好确定；k值选择过小，得到的近邻数过少，会降低分类精度，同时也会放大噪声数据的干扰；而k值选择过大，如果待分类样本属于训练集中包含数据较少的类，那么在选择k个近邻的时候，实际上并不相似的数据也被包含进来，造成噪声增加而导致分类效果的降低。2020/4/19162020/4/19175KNN的一些改进策略(1)从降低计算复杂度的角度当样本容量较大以及特征属性较多时，KNN算法分类的效率就将大大降低。可以采用以下方法进行改进。如果在使用KNN算法之前对样本的属性进行约简，删除那些对分类结果影响较小（不重要）的属性，则可以用KNN算法快速地得出待分类样本的类别，从而可以得到更好的效果。2020/4/1918粗糙集理论在用于决策表的属性约简时，可在保持决策表中决策能力不变的前提下，删除其中不相关的冗余属性。详细参考：计算机科学2008VOL35NO3《一个高效的KNN分类算法》张著英等2020/4/1919缩小训练样本的方法：在原有的样本中删掉一部分与分类相关不大的样本，将剩下的样本作为新的训练样本或者在原来的训练样本集中选取一些代表样本作为新的训练样本；通过聚类（clustering），将聚类所产生的中心点作为新的训练样本。2020/4/1920(2)从优化相似度度量方法的角度基本的KNN算法基于欧几里得距离来计算样本的相似度，这种方法对噪声特征非常敏感。为了改变传统KNN算法中特征作用相同的缺陷，可在度量相似度的距离公式中给特征赋予不同权重，特征的权重一般根据各个特征在分类中的作用设定。2020/4/1921(3)从优化判决策略的角度传统的KNN算法的决策规则的缺点是，当样本分布不均匀（训练样本各类别之间数目不均衡，或者即使基本数目接近，由于其所占区域大小的不同）时，只按照前K个邻近顺序而不考虑它们的距离，会造成误判，影响分类的性能。可以采用均匀化样本分布密度的方法进行改进。2020/4/1922(4)从选取恰当k值的角度由于KNN算法中几乎所有的计算都发生在分类阶段，而且分类效果很大程度上依赖于k值的选取。而目前为止，比较好的选k值的方法只能是通过反复试验调整。2020/4/19236KNN在实际问题中的应用来自于文献《KNN算法在就业预测模型中的应用》①特征向量提取本例将从课程平均成绩、实践成绩、英语成绩和毕业设计成绩4个维度（属性）作为探讨学生就业状态的主要影响因素。2020/4/19242020/4/19252020/4/1926计算相似度设两个特征向量分别为X=（x1,x2,...,xn）和Y=(y1,y2,...yn)2020/4/1927将需要预测的学生的特征向量与训练集中的所有特征向量，用上述公式计算出距离，将各个距离值排序，将最距离小的排在前面，最后取前k个样本，得出在这k个样本中，国企、外企、私企所占比例，比例最大的就是该预测样本所属于的类别。2020/4/1928传统KNN算法实验结果2020/4/19292020/4/19302020/4/1931改进1、样本特征加权处理传统的方法认为样本各个特征（属性）的作用是相同的，即权重相同，无法体现各特征与分类间的关系。如果有些特征与分类相关度很高，有些很低，则其分类误差就会较大。可以给每一个属性特征赋予相应的权重，代表其重要程度。2020/4/1932本例中针对k值得确定问题，基于样本间距的思想采用一种避开k值得选择。其基本思想为：将训练样本集合分为m类，分别用Ci（i=1,2，...,m）表示。然后求未知样本X与类别Ci中k个样本的距离dj（j=1,2，...,k），最后统计样本X与类别Ci的平均距离，如下式所示：2、k值的选择2020/4/1933改进的KNN算法实验结果2020/4/1934小结：KNN算法简单，易于实现，但当样本规模很大时，其复杂度会很大，所谓“适合的就是最好的”，在选择分类算法时我们应该根据具体应用的需求，选择适当的分类算法。