KNN讲解资料.pptx

2024/9/6 周五1K K最近邻最近邻(K-NEAREST(K-NEAREST NEIGHBOR)NEIGHBOR)KNNKNN分类算法分类算法2024/9/6 周五2主要内容主要内容1 1 引引言言2 2 K K N N N N的的 基基 本本 思思 想想3 3 K K N NN N 算算 法法 的的 实实 现现4 4 K K N N N N的的优优缺缺点点5 5 K KN NN N的的 一一 些些 改改 进进 策策 略略6 6 K KN NN N在在实实际际问问题题中中的的应应用用2024/9/6 周五31 1 引言引言分分类类（ClassificationClassification）是是数数据据挖挖掘掘领领域域中中的的一一种种重重要要的的技技术术，它它是是从从一一组组已已知知的的训训练练样样本本中中发发现现分分类类模模型型，并并且且使使用用这这个个分分类类模模型型来来预预测测待待分分类类样样本本。建建立立一一个个有有效效的的分分类类算算法法模模型型最最终终将将待待分分类类的的样样本本进进行行处处理理是是非常有必要的。非常有必要的。2024/9/6 周五4目目前前常常用用的的分分类类算算法法主主要要有有：朴朴素素贝贝叶叶斯斯分分类类算算法法（NaNave ve BayesBayes）、支支持持向向量量机机分分类类算算法法（Support Support Vector Vector MachinesMachines）、KNNKNN最最近近邻邻算算法法(k-Nearest(k-Nearest NeighboNeighbors)rs)、神神经经网网络络算算法法（NNetNNet）以以及及决决策策树树（Decision Decision TreeTree）等等。）等等。2024/9/6 周五59/6/20245KNNKNN算算法法是是一一个个理理论论上上比比较较成成熟熟的的方方法法，最最初初由由CoverCover和和HartHart于于19681968年年提提出出，其其思思路路非常简单直观，易于快速实现。非常简单直观，易于快速实现。因因此此，KNNKNN算算法法以以其其实实现现的的简简单单性性及及较较高高的的分分类类准准确确性性在在中中文文文文本本自自动动分分类类等等领领域域得到了广泛应用。得到了广泛应用。2024/9/6 周五62 KNN2 KNN的基本思想的基本思想根根据据距距离离函函数数计计算算待待分分类类样样本本X X和和每每个个训训练练样样本本的的距距离离（作作为为相相似似度度），选选择择与与待待分分类类样样本本距距离离最最小小的的K K个个样样本本作作为为X X的的K K个个最最邻邻近近，最最后后以以X X的的K K个个最最邻邻近近中中的的大大多多数数所所属属的的类类别别作作为为X X的类别。的类别。KNNKNN可可以以说说是是一一种种最最直直接接的的用用来来分分类类未未知知数数据的方法。据的方法。2024/9/6 周五7 简简单单来来说说，KNNKNN可可以以看看成成：有有那那么么一一堆堆你你已已经经知知道道分分类类的的数数据据，然然后后当当一一个个新新数数据据进进入入的的时时候候，就就开开始始跟跟训训练练数数据据里里的的每每个个点点求求距距离离，然然后后挑挑出出离离这这个个数数据据最最近近的的K K个个点点，看看看看这这K K个个点点属属于于什什么么类类型型，然然后后用用少少数数服服从从多多数数的的原原则则，给新数据归类。给新数据归类。2024/9/6 周五82024/9/6 周五93 3 KN KNN N算法的实现算法的实现(1)(1)问题描述问题描述 数据集：数据集：iris.datairis.data标准数据集标准数据集-鸢尾花。鸢尾花。采采用用KNNKNN算算法法对对iris.datairis.data分分类类。为为了了操操作作方方便便，对对各各组组数数据据添添加加rowNorowNo属属性性,第第一一组组rowNo=1rowNo=1，共共有有150150组组数数据据,选选择择rowNorowNo模模3 3不不等等于于0 0的的100100组作为训练数据集，剩下的组作为训练数据集，剩下的5050组做测试数据集。组做测试数据集。2024/9/6 周五10初始化距离为最大值；初始化距离为最大值；计计算算未未知知样样本本和和每每个个训训练练样样本本的的距距离离distdist；得得到到目目前前K K个个最最临临近近样样本本中中的的最最大大距距离离maxdistmaxdist；(2)(2)实现步骤：实现步骤：2024/9/6 周五11如如果果distdist小小于于maxdistmaxdist，则则将将该该训训练练样样本本作作为为K-K-最近邻样本；最近邻样本；重重复复步步骤骤2 2、3 3、4 4，直直到到所所有有未未知知样样本本和和所所有有训训练样本的距离都算完；练样本的距离都算完；统计统计K-K-最近邻样本中每个类标号出现的次数；最近邻样本中每个类标号出现的次数；选选择择出出现现频频率率最最大大的的类类标标号号作作为为未未知知样样本本的的类类标号。标号。2024/9/6 周五124 KNN4 KNN的优缺点的优缺点u优点优点(1)(1)算法思路较为简单，易于实现；算法思路较为简单，易于实现；(2)(2)当当有有新新样样本本要要加加入入训训练练集集中中时时，无无需需重重新训练（即重新训练的代价低）；新训练（即重新训练的代价低）；(3)(3)计计算算时时间间和和空空间间线线性性于于训训练练集集的的规规模模（在一些场合不算太大）。（在一些场合不算太大）。2024/9/6 周五13u不足不足(1)(1)分类速度慢分类速度慢；KNNKNN算算法法的的时时间间复复杂杂度度和和存存储储空空间间会会随随着着训训练练集集规规模模和和特特征征维维数数的的增增大大而而快快速速增增加加。因因为为每每次次新新的的待待分分样样本本都都必必须须与与所所有有训训练练集集一一同同计计算算比比较较相相似似度度，以以便便取取出出靠靠前前的的K K个个已已分分类类样样本本。整整个个算算法法的的时时间间复复杂杂度度可可以以用用O(m*n)O(m*n)表表示示，其其中中m m是是选选出出的的特特征征项项(属属性性)的的个个数数，而而n n是训练集样本的个数。是训练集样本的个数。2024/9/6 周五14(2)(2)各属性的各属性的权重相同权重相同，影响了准确率；，影响了准确率；当当样样本本不不平平衡衡时时，如如一一个个类类的的样样本本容容量量很很大大，而而其其他他类类样样本本容容量量很很小小时时，有有可可能能导导致致当当输输入入一一个个新新样样本本时时，该该样样本本的的K K个个邻邻居居中中大大容容量量类类的的样样本本占占多多数数。该该算算法法只只计计算算“最最近近的的”邻邻居居样样本本，如如果果某某一一类类的的样样本本数数量量很很大大，那那么么可可能能目目标标样样本本并并不不接接近近这这类类样样本本，却却会会将将目目标标样样本本分分到到该该类类下下，影响分类准确率。影响分类准确率。2024/9/6 周五15(3)(3)样本库容量依赖性较强；样本库容量依赖性较强；(4)(4)K K值不好确定值不好确定；k k值值选选择择过过小小，得得到到的的近近邻邻数数过过少少，会会降降低低分分类类精精度度，同同时时也也会会放放大大噪噪声声数数据据的的干干扰扰；而而k k值值选选择择过过大大，如如果果待待分分类类样样本本属属于于训训练练集集中中包包含含数数据据较较少少的的类类，那那么么在在选选择择k k个个近近邻邻的的时时候候，实实际际上上并并不不相相似似的的数数据据也也被被包包含含进进来来，造成噪声增加而导致分类效果的降低。造成噪声增加而导致分类效果的降低。2024/9/6 周五162024/9/6 周五175 KNN5 KNN的一些改进策略的一些改进策略(1)(1)从从降低计算复杂度降低计算复杂度的角度的角度 当样本容量较大以及特征属性较多时，当样本容量较大以及特征属性较多时，KNNKNN算算法分类的效率就将大大降低。可以采用以下方法进法分类的效率就将大大降低。可以采用以下方法进行改进。行改进。如如果果在在使使用用KNNKNN算算法法之之前前对对样样本本的的属属性性进进行行约约简简，删删除除那那些些对对分分类类结结果果影影响响较较小小（不不重重要要）的的属属性性，则则可可以以用用KNNKNN算算法法快快速速地地得得出出待待分分类类样样本本的的类类别别，从而可以得到更好的效果。从而可以得到更好的效果。2024/9/6 周五18 粗粗糙糙集集理理论论在在用用于于决决策策表表的的属属性性约约简简时时，可可在在保保持持决决策策表表中中决决策策能能力力不不变变的的前前提提下下，删除其中不相关的冗余属性。删除其中不相关的冗余属性。详详细细参参考考：计计算算机机科科学学2008VOL35NO32008VOL35NO3一一个个高效的高效的KNNKNN分类算法分类算法张著英等张著英等 2024/9/6 周五19缩缩小小训训练练样样本本的的方方法法：在在原原有有的的样样本本中中删删掉掉一一部部分分与与分分类类相相关关不不大大的的样样本本，将将剩剩下下的的样样本本作作为为新新的的训训练练样样本本或或者者在在原原来来的的训训练练样样本本集集中中选选取取一一些些代代表表样样本本作作为新的训练样本；为新的训练样本；通通过过聚聚类类（clusteringclustering），将将聚聚类类所所产产生的中心点作为新的训练样本。生的中心点作为新的训练样本。2024/9/6 周五20(2)(2)从从优化相似度度量方法优化相似度度量方法的角度的角度 基基本本的的KNNKNN算算法法基基于于欧欧几几里里得得距距离离来来计计算算样样本的相似度，这种方法对噪声特征非常敏感。本的相似度，这种方法对噪声特征非常敏感。为为了了改改变变传传统统KNNKNN算算法法中中特特征征作作用用相相同同的的缺缺陷陷，可可在在度度量量相相似似度度的的距距离离公公式式中中给给特特征征赋赋予予不不同同权权重重，特特征征的的权权重重一一般般根根据据各各个个特特征征在在分分类中的作用设定。类中的作用设定。2024/9/6 周五21(3)(3)从从优化判决策略优化判决策略的角度的角度 传传统统的的KNNKNN算算法法的的决决策策规规则则的的缺缺点点是是，当当样样本本分分布布不不均均匀匀（训训练练样样本本各各类类别别之之间间数数目目不不均均衡衡，或或者者即即使使基基本本数数目目接接近近，由由于于其其所所占占区区域域大大小小的的不不同同）时时，只只按按照照前前K K个个邻邻近近顺顺序序而而不不考考虑它们的距离，会造成误判，影响分类的性能。虑它们的距离，会造成误判，影响分类的性能。可以采用可以采用均匀化样本分布密度均匀化样本分布密度的方法进行改进。的方法进行改进。2024/9/6 周五22(4)(4)从从选取恰当选取恰当k k值值的角度的角度 由由于于KNNKNN算算法法中中几几乎乎所所有有的的计计算算都都发发生生在在分分类类阶阶段段，而而且且分分类类效效果果很很大大程程度度上上依依赖赖于于k k值值的的选选取取。而而目目前前为为止止，比比较较好好的的选选k k值值的的方方法只能是通过反复试验调整。法只能是通过反复试验调整。2024/9/6 周五236 KNN6 KNN在实际问题中的应用在实际问题中的应用来自于文献来自于文献KNNKNN算法在就业预测模型中的应用算法在就业预测模型中的应用特征向量提取特征向量提取 本例将从课程平均成绩、实践成绩、英语本例将从课程平均成绩、实践成绩、英语成绩和毕业设计成绩成绩和毕业设计成绩4 4个维度（属性）作为探个维度（属性）作为探讨学生就业状态的主要影响因素。讨学生就业状态的主要影响因素。2024/9/6 周五242024/9/6 周五252024/9/6 周五26计算相似度计算相似度设两个特征向量分别为设两个特征向量分别为X=X=（x x1 1,x,x2 2,.,x,.,xn n）和）和Y=(yY=(y1 1,y,y2 2,.y,.yn n)2024/9/6 周五27 将将需需要要预预测测的的学学生生的的特特征征向向量量与与训训练练集集中中的的所所有有特特征征向向量量，用用上上述述公公式式计计算算出出距距离离，将将各各个个距距离离值值排排序序，将将最最距距离离小小的的排排在在前前面面，最最后后取取前前k k个个样样本本，得得出出在在这这k k个个样样本本中中，国国企企、外外企企、私私企企所所占占比比例例，比比例例最最大大的的就就是是该预测样本所属于的类别。该预测样本所属于的类别。2024/9/6 周五28传统传统KNNKNN算法实验结果算法实验结果2024/9/6 周五292024/9/6 周五302024/9/6 周五31改进改进1 1、样本特征、样本特征加权加权处理处理 传统的方法认为样本各个特征（属性）的作传统的方法认为样本各个特征（属性）的作用是相同的，即权重相同，无法体现各特征与分用是相同的，即权重相同，无法体现各特征与分类间的关系。如果有些特征与分类相关度很高，类间的关系。如果有些特征与分类相关度很高，有些很低，则其分类误差就会较大。有些很低，则其分类误差就会较大。可以给每一个属性特征赋予相应的权重，代可以给每一个属性特征赋予相应的权重，代表其重要程度。表其重要程度。2024/9/6 周五32 本本例例中中针针对对k k值值得得确确定定问问题题，基基于于样样本本间间距距的的思思想想采采用用一一种种避避开开k k值值得得选选择择。其其基基本本思思想想为为：将将训训练练样样本本集集合合分分为为m m类类，分分别别用用C Ci i（i=1,2i=1,2，.,m.,m）表表示示。然然后后求求未未知知样样本本X X与与类类别别C Ci i中中k k个个样样本本的的距距离离d dj j（j=1,2j=1,2，.,k.,k），最最后后统统计计样样本本X X与与类类别别C Ci i的的平平均均距距离离，如如下式所示：下式所示：2 2、k k值值的选择的选择2024/9/6 周五33改进的改进的KNNKNN算法实验结果算法实验结果2024/9/6 周五34小结：小结：KNNKNN算法简单，易于实现，但当样本规模算法简单，易于实现，但当样本规模很大时，其复杂度会很大，所谓很大时，其复杂度会很大，所谓“适合的适合的就是最好的就是最好的”，在选择分类算法时我们应，在选择分类算法时我们应该根据具体应用的需求，选择适当的分类该根据具体应用的需求，选择适当的分类算法。算法。