基于类别平均距离的加权KNN分类算法-严晓明

计算机系统应用 2014年第23卷第2期基于类别平均距离的加权KNN分类算法?严晓明`(福建师范大学数学与计算机科学学院,福州350117)摘要:本文提出了一种改进的KNN分类算法,利用样本集合中同类别样本点间距离都十分接近的特点辅助KNN算法分类.将待分类样本点的K个最近邻样本点分别求出样本点所属类别的类别平均距离和样本点与待分类样本点距离的差值比,如果大于一个阈值,就将该样本点从K个最近邻的样本点中删除,再用此差值比对不同类别的样本点个数进行加权后执行多数投票,来决定待分类样本点所属的类别.改进后的_算法提高了分类的精度,并且时间复杂度与传统KNN算法相当.关键词:类别平均距离;KNN;加权算法WeightedKNNClassificationAlgorithmBasedonMeanDistanceofCategoryYANXiao-Ming(SchoolofMathematicsandComputerScience,FujianNormalUniversity,Fuzhou350108,China)Abstract:Inthispaper,animprovedKNNclassificationalgorithmisproposedbyusingcharacteristicsthatthepointsdistributedinthesamecategoryofsanqjlecollectionareinclosedistanceasanassistanttoclassifyKNNalgorithm.Thewaytodealwiththek-nearestneighboringsamplepointsiscalculatingtheaveragedistancebetweencategoriesthatthesamplepointsbelongtoandthedifferencesofunspecifiedsamplepointsrespectively.Ifthedatacalculatedisgreaterthanacertainthreshold,deletethissan^)lepointfromk-nearestneighboringsamples,thendeterminethecategoriesofunspecifiedsamplepointsthroughmajorityvoting.TheimprovedKNNalgorithmenhancestheprecisionofclassificationandmaintainsthesametimecomplexityasthetraditionalKNNalgorithm.Keywords:meandistanceofcategory;KNN;weightedalgorithmKNN[1]算法通过待分类样本与其近邻样本点距离 算距离的时间开销,一些学者从减小样本集里样本点的多数投票结果进行分类,以其简单,有效的特点而总数的角度来改进KNN算法,其中很多改进的方法都被广泛地应用于数据挖掘领域.但是传统的_算法 是对原始样本集以一定的方式裁剪掉某些样本点后再是一种懒惰的学习方法,没有预先建立模型后再进行 进行KNN分类,如:Hart的Condensing算法[2]、分类,其具有以下的缺点:1)每个样本点都必须存储,Devijver的MultiEdit算法[3]等,复旦大学的李荣陆14]存储量大;2)每次对新样本点分类时,都要计算所有的 提出基于密度的KNN分类算法,考虑了不同类别的样样本点与待分类样本的距离,计算量大;3)参数K值只 本点间密度的差异对分类结果的影响,并通过对高密能由经验进行设置,并且对某一数据集分类效果较好 度类别的样本点进行裁剪以及在低密度类别的区域填的取值方法对于其他数据集并没有很大的参考意义. 充样本点的方法提高了分类的精度;也有一些学者提为了克服传统_算法的缺点,许多学者从不同 出了通过对样本点进行线性变换以达到提高KNN分角度提出了改进的方法.由于在对待分类样本点确定 类算法精度的目的[5'6];崔正斌[7]等人提出用群智能方类别时,需要将样本集里的每个样本分别计算与待分 法对样本特征维数进行约简的方法来提高_算法类样本点的距离,因此,减小样本点总数就能减小计 性能,在没有改变样本点总数的同时,由于考虑了样①基金项目:福建省教育厅B类基金(JB11036)收稿时间:201307-07;收到修改稿时间:201308-19128软件技术.算法SoftwareTechnique.Algorithm2014年第23卷第2期 计算机系统应用本不同特征的重要性也提高KNN算法的精度. 均距离是有明显差别的.分类是利用数据集中已有标签样本的信息去给出 BBB待分类样本点的类别,若能最大程度地保留已知标签 8样本的信息参与分类操作,可以提高分类的性能.传 a=a1^°j^B统的KNN算法和以裁剪样本点方式改进的KNN算法,没有充分利用到全体已有标签的样本点的信息,只用 B&&到了待分类样本的K个最近邻,而其他带标签的样本 图1样本点类别平均距离示意图也隐藏了对分类十分有用的信息并没有进行利用;以样本特征约简方式改进的KNN算法,通过对样本特征 (1)情况1:当不同类别的样本分布在不同区域,的取舍提高了分类精度,但是样本特征的重要性对不 而待分类样本在这些类别区域的边缘时,由于KNN算同的待分类样本一般也是不相同的,若对不同的待分 法取其K个最近邻,这些最近邻样本点的多数可能并类别样本点都对样本集中所有样本点各个维的重要性 非待分类样本的类别,因此在进行多数投票时,容易进行重新计算,时间消耗是一个很大的问题.本文提 出现错分.如图1所示,待分类样本C属于类别B,而出了一种将样本集中同类别的样本点之间距离的平均 此时不论K值取值多少,样本点C的近邻中,类别A值对KNN分类算法进行加权的方法,使得分类结果更 的样本点总数都是占多数,传统的_分类算法就会加可靠,精度也得到进一步的提高. 将样本点C的类别判断为A.在传统_分类时,如果以K近邻样本点所属类别的类别平均距离为辅助,1样本点类别平均距离对分类结果的影响 就可以避免出现错分的情况.从图1中可以看出,B类在样本集合中,某一类别的所有样本点,它们的 的类别平均距离均值要大于类A,由于待分类样本点分布都呈现出了一定的规律,即相邻样本点之间的距 C与其K个最近邻样本中属于B类的3个样本点间的离一般是接近的,这样的信息隐藏在该类别的所有样 平均距离和B类的类别平均距离接近,而样本点C与本点中,在传统_分类时,没有得到有效的利用. 属于A类的5个样本点平均距离和A类的类别平均距传统的_算法进行分类时,只利用到了待分类样本 离相差较大,因此,把待分类样本点C的类别判断为最近邻的K个带标签样本的信息.而这些带标签的样 类别B.本信息是十分宝贵的,应用到的信息越多,对分类结 (2)情况2:当不同类别样本的分布区域有交叉,果的正面影响就越强.前面介绍的KNN改进算法都对 而待分类样本在交叉区域内时,传统KNN算法所取的已知签标的样本进行了处理,在一定程度上削弱了这 K个最近邻样本中,密度大的类取出的样本点占多数,些样本所包含的信息量. 则进行多数投票时,也容易产生错分的情况.如图2以下用类别样本点平均距离表示某一类别样本点 所示,待分类样本点C的近邻样本点中(图中圆形所与其最近邻的同类别样本点之间距离的平均值.如图 示),类B的样本点有6个,类A的样本点有4个,B1所示,带边框的样本点的类别为B类,与其最近邻的 类的类别平均距离较小,传统的KNN算法将待分类样5个同类别B类样本点(以下划线标注)的距离平均值 本点C判断为B类.如果以这些近邻样本点所属类别即为单个样本点与其同类最近邻样本点的平均距离; 的类别平均距离为辅助,则把待分类样本点C分到A把B类所有样本点的与其同类别的最近邻样本点的平 类'这是因为样本点C与其近邻的4个A类样本点的均距离进行求平均值的结果,即为类B的类别平均距 平均距离和A类的类别平均距离接近,而样本点C与离.同一类别只有一个类别平均距离;类别平均距离 其近邻的6个B类样本点的平均距离和B类的类别平反映了同一类别相邻样本点之间距离大致接近的特点.均距离相差较大.在图1中,类A的样本点与其相邻的A类样本点的距 (3)情况3:当一个类别的样本点分布在另一个类离是接近的,而类B的样本点与其相邻的B类样本点 别内,而待分类样本点C在这两个类别中时,如图3的距离也是接近的;同时不同类的类别平均距离一般 所示.若按传统的KNN算法,会将待分类样本点C判来说有着明显的区别,如图1中,A类、B类的类别平 断为A类,而用类别平均距离进行辅助判断,则把待SoftwareTechnique?Algorithm软件技术?算法129计算机系统应用 2014年第23卷第2期分类样本点C判断为B类,这是由于待分类样本点C 用来保存计算具体类别中每个样本点的近邻样本点,的K个近邻中,与类B样本点的平均距离和B类的类 每次计算后就置空;另一个数组用来保别平均距离更接近. 存数组中的样本与其最近邻样本点的平均距A 离.由于各类的样本总数未知,因此数组的大小设置为\AAB?BB 样本集里的样本点总数《.将两个数组分别置空,并且AAB/^k?ABbB 另外设置一个计数器9,清0.A八Aa(B/bTI ③取样本集中第1个类别的第一个样本点将A 该样本点每一维的特征《/都与该类别中其它所有的样AA 本点第_/维的值进行比较,找出在第/维特征上与样图2不同类别样本点分布区域交叉的情况 本巧的第y维特征差值最小的样本,其中如果这个样本不在数组如叩[1..?]中,就将其保存到BBBB 中.BBABB ④对数组中的每个样本,分别求与第1B个类别的第一个样本点《,的距离,并将差别最大的值BABBAB 去掉,再求距离均值,将其存入数组41..?]中,图3—个类别的样本点分布在另一个类中间的情况 并将计数器g加1.⑤取出样本集中第1个类别的下一个样本,重复从上面的分析可以看出,待分类样本点的K个最 步骤3到步骤4,一直到该类别的所有样本点都取完为近邻样本点所属类别的类别平均距离相差越大,则越 止.并计算数组前9个元素的均值,保存好判断出待分类样本点的类别. 到的第一个元素的位置,同时将类别名称X、存储到数组元素《胃[1]中.2基于类别平均距离的加权KNN分类器 ⑥对样本集里其他类别,重复步骤2到5,直到KNN算法没有事先建立和存储分类模型,只在分 样本集中所有类别的类别平均距离都求出为止.类时才去计算待分类样本点与样本数据集中所有样本 在求某个具体类别义中的一个样本点《与其周围的距离.在样本数据集中某一类别的样本点没有发生 最近邻的同类样本点的平均距离时,一般的做法是求变化时,该类别的类别平均距离保持不变,为了避免 出样本点《和类别尤中其它的样本点的距离,再找出在每次分类操作时都要去计算每一个已知类别的类别 最小的若干个求均值,但是这样做法的缺点是无法确平均距离,可设置数组对该数据进行保存.因此在算 定要找出多少个与样本点《近邻的类别X中的样本点?法中共要设置两个数组,一个保存类别名称,另一个 因此,这里采用了一个方法,基于和样本点《最接近保存该类的类别平均距离,数组的长度为样本集的总 的同类样本点,必定有若千维的特征与样本点《的差类别数.当待分类样本点的类别标签确定后,要更新 值最小的考虑,步骤3和步骤4先找到与样本点n的这个相应数组中的类别平均距离. 每维特征的差值最小的样本点构成集合,再求集合中计算样本集中各类别平均距离的步骤: 的样本点和样本点《距离的平均值.当新加入一个已输入:一个样本集共有m个类别,类别标签分别 知类别标签的样本点后,把该类别的所有样本点执行为岑,每个类别分别有个样