KNN讲解资料.ppt

《KNN讲解资料.ppt》由会员分享，可在线阅读，更多相关《KNN讲解资料.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2022-8-142主要内容主要内容1 1 引言引言2 KNN2 KNN的基本思想的基本思想3 3 KN KNN N算法的实现算法的实现4 4 KNN KNN的优缺点的优缺点5 5 KNN KNN的一些改进策略的一些改进策略6 6 KNN KNN在实际问题中的应用在实际问题中的应用2022-8-1431 1 引言引言分类（分类（ClassificationClassification）是数据挖掘领域是数据挖掘领域中的一种重要的技术，它是从一组已知的训中的一种重要的技术，它是从一组已知的训练样本中发现分类模型，并且使用这个分类练样本中发现分类模型，并且使用这个分类模型来预测待分类样本。建立一个有

2、效的分模型来预测待分类样本。建立一个有效的分类算法模型最终将待分类的样本进行处理是类算法模型最终将待分类的样本进行处理是非常有必要的。非常有必要的。2022-8-144目前常用的分类算法主要有：朴素贝叶目前常用的分类算法主要有：朴素贝叶斯分类算法（斯分类算法（NaNave Bayesve Bayes）、支持向量机分）、支持向量机分类算法（类算法（Support Vector MachinesSupport Vector Machines）、）、 KNNKNN最近邻算法最近邻算法(k-Nearest Neighbo(k-Nearest Neighbors)rs)、神、神经网络算法（经网络算法（N

3、NetNNet）以及决策树（）以及决策树（Decision Decision TreeTree）等等。）等等。2022-8-1458/14/20225KNNKNN算法是一个理论上比较成熟的方法，算法是一个理论上比较成熟的方法，最初由最初由CoverCover和和HartHart于于19681968年提出，其思路年提出，其思路非常简单直观，易于快速实现。非常简单直观，易于快速实现。因此，因此，KNNKNN算法以其实现的简单性及较算法以其实现的简单性及较高的分类准确性在中文文本自动分类等领域高的分类准确性在中文文本自动分类等领域得到了广泛应用。得到了广泛应用。2022-8-1462 KNN2 KN

4、N的基本思想的基本思想根据根据距离函数距离函数计算待分类样本计算待分类样本X X和每个训和每个训练样本的距离（作为练样本的距离（作为相似度相似度），选择与待分类），选择与待分类样本距离最小的样本距离最小的K K个样本作为个样本作为X X的的K K个最邻近，个最邻近，最后以最后以X X的的K K个最邻近中的大多数所属的类别作个最邻近中的大多数所属的类别作为为X X的类别。的类别。KNNKNN可以说是一种最直接的用来分类未知可以说是一种最直接的用来分类未知数据的方法。数据的方法。2022-8-147 简单来说，简单来说，KNNKNN可以看成：有那么一堆你可以看成：有那么一堆你已经知道分类的数据，然

5、后当一个新数据进入已经知道分类的数据，然后当一个新数据进入的时候，就开始跟训练数据里的每个点求距离的时候，就开始跟训练数据里的每个点求距离，然后挑出离这个数据最近的，然后挑出离这个数据最近的K K个点，看看这个点，看看这K K个点属于什么类型，然后用少数服从多数的原个点属于什么类型，然后用少数服从多数的原则，给新数据归类。则，给新数据归类。2022-8-1482022-8-1493 3 KN KNN N算法的实现算法的实现(1)(1)问题描述问题描述 数据集：数据集：iris.datairis.data标准数据集标准数据集- -鸢尾花。鸢尾花。 采用采用KNNKNN算法对算法对iris.dat

6、airis.data分类。为了操作分类。为了操作方便，对各组数据添加方便，对各组数据添加rowNorowNo属性属性, ,第一组第一组rowNo=1rowNo=1，共有，共有150150组数据组数据, ,选择选择rowNorowNo模模3 3不等不等于于0 0的的100100组作为训练数据集，剩下的组作为训练数据集，剩下的5050组做测组做测试数据集。试数据集。2022-8-1410初始化距离为最大值；初始化距离为最大值；计算未知样本和每个训练样本的距离计算未知样本和每个训练样本的距离distdist；得到目前得到目前K K个最临近样本中的最大距离个最临近样本中的最大距离maxdistmaxd

7、ist；(2)(2)实现步骤：实现步骤：2022-8-1411如果如果distdist小于小于maxdistmaxdist，则将该训练样本作为，则将该训练样本作为K-K-最近邻样本；最近邻样本；重复步骤重复步骤2 2、3 3、4 4，直到所有未知样本和所有训，直到所有未知样本和所有训练样本的距离都算完；练样本的距离都算完；统计统计K-K-最近邻样本中每个类标号出现的次数；最近邻样本中每个类标号出现的次数；选择出现频率最大的类标号作为未知样本的类选择出现频率最大的类标号作为未知样本的类标号。标号。2022-8-14124 KNN4 KNN的优缺点的优缺点u优点优点(1)(1)算法思路较为简单，易

8、于实现；算法思路较为简单，易于实现；(2)(2)当有新样本要加入训练集中时，无需重当有新样本要加入训练集中时，无需重新训练（即重新训练的代价低）；新训练（即重新训练的代价低）；(3)(3)计算时间和空间线性于训练集的规模计算时间和空间线性于训练集的规模（在一些场合不算太大）。（在一些场合不算太大）。2022-8-1413u不足不足(1)(1)分类速度慢分类速度慢； KNNKNN算法的时间复杂度和存储空间会随着算法的时间复杂度和存储空间会随着训练集规模和特征维数的增大而快速增加。训练集规模和特征维数的增大而快速增加。因为每次新的待分样本都必须与所有训练集因为每次新的待分样本都必须与所有训练集一同

9、计算比较相似度，以便取出靠前的一同计算比较相似度，以便取出靠前的K K个已个已分类样本。整个算法的时间复杂度可以用分类样本。整个算法的时间复杂度可以用O(mO(m* *n)n)表示，其中表示，其中m m是选出的特征项是选出的特征项( (属性属性) )的的个数，而个数，而n n是训练集样本的个数。是训练集样本的个数。2022-8-1414(2)(2)各属性的各属性的权重相同权重相同，影响了准确率；，影响了准确率； 当样本不平衡时，如一个类的样本容量很大当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的一

10、个新样本时，该样本的K K个邻居中大容量类的样个邻居中大容量类的样本占多数。该算法只计算本占多数。该算法只计算“最近的最近的”邻居样本，邻居样本，如果某一类的样本数量很大，那么可能目标样本如果某一类的样本数量很大，那么可能目标样本并不接近这类样本，却会将目标样本分到该类下并不接近这类样本，却会将目标样本分到该类下，影响分类准确率。，影响分类准确率。2022-8-1415(3)(3)样本库容量依赖性较强；样本库容量依赖性较强；(4)(4)K K值不好确定值不好确定； k k值选择过小，得到的近邻数过少，会降值选择过小，得到的近邻数过少，会降低分类精度，同时也会放大噪声数据的干扰；低分类精度，同时

11、也会放大噪声数据的干扰；而而k k值选择过大，如果待分类样本属于训练集值选择过大，如果待分类样本属于训练集中包含数据较少的类，那么在选择中包含数据较少的类，那么在选择k k个近邻的个近邻的时候，实际上并不相似的数据也被包含进来，时候，实际上并不相似的数据也被包含进来，造成噪声增加而导致分类效果的降低。造成噪声增加而导致分类效果的降低。2022-8-14162022-8-14175 KNN5 KNN的一些改进策略的一些改进策略(1)(1)从从降低计算复杂度降低计算复杂度的角度的角度 当样本容量较大以及特征属性较多时，当样本容量较大以及特征属性较多时，KNNKNN算算法分类的效率就将大大降低。可以

12、采用以下方法法分类的效率就将大大降低。可以采用以下方法进行改进。进行改进。如果在使用如果在使用KNNKNN算法之前对样本的算法之前对样本的属性属性进行进行约简约简，删除那些删除那些对分类结果影响较小（不重要）对分类结果影响较小（不重要）的属性，的属性，则可以用则可以用KNNKNN算法快速地得出待分类样本的类别，算法快速地得出待分类样本的类别，从而可以得到更好的效果。从而可以得到更好的效果。2022-8-1418 粗糙集理论粗糙集理论在用于决策表的属性约简时，在用于决策表的属性约简时，可在保持决策表中决策能力不变的前提下，可在保持决策表中决策能力不变的前提下，删除其中不相关的冗余属性。删除其中不

13、相关的冗余属性。 详细参考：计算机科学详细参考：计算机科学2008VOL35NO32008VOL35NO3一个一个高效的高效的KNNKNN分类算法分类算法张著英等张著英等 2022-8-1419 缩小训练样本缩小训练样本的方法：在原有的样本中的方法：在原有的样本中删掉一部分与分类相关不大的样本，将删掉一部分与分类相关不大的样本，将剩下的样本作为新的训练样本或者在原剩下的样本作为新的训练样本或者在原来的训练样本集中选取一些代表样本作来的训练样本集中选取一些代表样本作为新的训练样本；为新的训练样本； 通过通过聚类（聚类（clusteringclustering），将聚类所产，将聚类所产生的中心点作

14、为新的训练样本。生的中心点作为新的训练样本。2022-8-1420(2)(2)从从优化相似度度量方法优化相似度度量方法的角度的角度 基本的基本的KNNKNN算法基于算法基于欧几里得距离欧几里得距离来计算样来计算样本的相似度，这种方法对噪声特征非常敏感。本的相似度，这种方法对噪声特征非常敏感。 为了改变传统为了改变传统KNNKNN算法中特征作用相同的缺算法中特征作用相同的缺陷，可在度量相似度的距离公式中给特征陷，可在度量相似度的距离公式中给特征赋予赋予不同权重不同权重，特征的权重一般根据各个特征在分，特征的权重一般根据各个特征在分类中的作用设定。类中的作用设定。2022-8-1421(3)(3)

15、从从优化判决策略优化判决策略的角度的角度 传统的传统的KNNKNN算法的决策规则的缺点是，当样算法的决策规则的缺点是，当样本分布不均匀（训练样本各类别之间数目不均本分布不均匀（训练样本各类别之间数目不均衡，或者即使基本数目接近，由于其所占区域衡，或者即使基本数目接近，由于其所占区域大小的不同）时，只按照前大小的不同）时，只按照前K K个邻近顺序而不考个邻近顺序而不考虑它们的距离，会造成误判，影响分类的性能。虑它们的距离，会造成误判，影响分类的性能。可以采用可以采用均匀化样本分布密度均匀化样本分布密度的方法进行改进。的方法进行改进。2022-8-1422(4)(4)从从选取恰当选取恰当k k值值

16、的角度的角度 由于由于KNNKNN算法中几乎所有的计算都发生在算法中几乎所有的计算都发生在分类阶段，而且分类效果很大程度上依赖于分类阶段，而且分类效果很大程度上依赖于k k值的选取。值的选取。而目前为止，比较好的选而目前为止，比较好的选k k值的方值的方法只能是通过反复试验调整。法只能是通过反复试验调整。2022-8-14236 KNN6 KNN在实际问题中的应用在实际问题中的应用来自于文献来自于文献KNNKNN算法在就业预测模型中的应用算法在就业预测模型中的应用特征向量提取特征向量提取 本例将从课程平均成绩、实践成绩、英语本例将从课程平均成绩、实践成绩、英语成绩和毕业设计成绩成绩和毕业设计成

17、绩4 4个维度（属性）作为探个维度（属性）作为探讨学生就业状态的主要影响因素。讨学生就业状态的主要影响因素。2022-8-14242022-8-14252022-8-1426计算相似度计算相似度设两个特征向量分别为设两个特征向量分别为X=X=（x x1 1,x,x2 2,.,x,.,xn n）和）和Y=(yY=(y1 1,y,y2 2,.y,.yn n) )2022-8-1427 将需要预测的学生的特征向量与训练集将需要预测的学生的特征向量与训练集中的所有特征向量，用上述公式计算出距离，中的所有特征向量，用上述公式计算出距离，将各个距离值排序，将最距离小的排在前面，将各个距离值排序，将最距离小

18、的排在前面，最后取最后取前前k k个样本个样本，得出在这，得出在这k k个样本中，国个样本中，国企、外企、私企所占比例，比例最大的就是企、外企、私企所占比例，比例最大的就是该预测样本所属于的类别。该预测样本所属于的类别。2022-8-1428传统传统KNNKNN算法实验结果算法实验结果2022-8-14292022-8-14302022-8-1431改进改进1 1、样本特征、样本特征加权加权处理处理 传统的方法认为样本各个特征（属性）的作传统的方法认为样本各个特征（属性）的作用是相同的，即权重相同，无法体现各特征与分用是相同的，即权重相同，无法体现各特征与分类间的关系。如果有些特征与分类相关度

19、很高，类间的关系。如果有些特征与分类相关度很高，有些很低，则其分类误差就会较大。有些很低，则其分类误差就会较大。 可以给每一个属性特征赋予相应的权重，代可以给每一个属性特征赋予相应的权重，代表其重要程度。表其重要程度。2022-8-1432 本例中针对本例中针对k k值得确定问题，基于样本间距的思值得确定问题，基于样本间距的思想采用一种避开想采用一种避开k k值得选择。其基本思想为：将训练值得选择。其基本思想为：将训练样本集合分为样本集合分为m m类，分别用类，分别用C Ci i（i=1,2i=1,2，.,m.,m）表示。）表示。然后求未知样本然后求未知样本X X与类别与类别C Ci i中中k

20、 k个样本的距离个样本的距离d dj j（j=1,2j=1,2，.,k.,k），最后统计样本），最后统计样本X X与类别与类别C Ci i的平均的平均距离，如下式所示：距离，如下式所示： 2 2、k k值值的选择的选择2022-8-1433改进的改进的KNNKNN算法实验结果算法实验结果2022-8-1434小结：小结： KNNKNN算法简单，易于实现，但当样本规算法简单，易于实现，但当样本规模很大时，其复杂度会很大，所谓模很大时，其复杂度会很大，所谓“适合适合的就是最好的的就是最好的”，在选择分类算法时我们，在选择分类算法时我们应该根据具体应用的需求，选择适当的分应该根据具体应用的需求，选择适当的分类算法。类算法。结束结束