认证主体：宁夏凯米世纪网络科技有限公司
IP属地：宁夏
统一社会信用代码/组织机构代码
91640100MA774ECW4K
2、；k近邻算法；机器学习；文本分类abstract:knnalgorithm,afamousstatisticalmethodofpatternrecognition,whichisoneofthebestalgorithmsfordealingwithtextcategorization,isplayinganimportantroleinmachinelearningclassificationalgorithm,anditisoneofthesimplestalgorithmsinmachinelearni
3、ng.thispapermainlysummariestheknnalgorithmanditsrelatedliterature,anddetailedintroducesitsmainidea,principle,implementationstepsandspecificimplementationcode,aswellasanalyzestheadvantagesanddisadvantagesofthealgorithmanditsvariousimprovementschemes.thispaper
4、alsointroducesthedevelopmentcourseofknnalgorithm,itsimportantpublishedpaper.inthefinal,thispaperintroducestheapplicationfieldofknnalgorithm,andespeciallyintextcategorization.keywords:knnalgorithm,kneighboralgorithm,machinelearning,textclassification1引言分类是数据挖掘中的
5、核心和基础技术，在经营、决策、管理、科学研究等多个领域都有着广泛的应用。目前主要的分类技术包括决策树、贝叶斯分类、knn分类、人工神经网络等。在这些方法中，knn分类是一种简单、有效、非参数的方法，现已经广泛应用于文本分类、模式识别、图像及空间分类等领域。本文从各个角度对knn算法进行较为全面的总结。本文的结构如下：在第二部分，主要介绍knn算法的基本原理、思想、实现步骤、java实现代码以及发展历程和经典论文。第三部分是对knn算法的诸多不足之处进行的讨论，并给出一些改进的方案。第四部分介绍的是knn算法如何处理多标签数据。第五部分介绍了knn算法目前的主要应用领域，并着重说明了其在文本分类
6、中的出色表现。2knn算法简介2.1算法引入knn算法是机器学习里面比较简单的一个分类算法，整体思想比较简单：计算一个点a与其他所有点之间的距离，取出与该点最近的k个点，然后统计这k个点里面所属分类比例最大的，则点a属于该分类。下面用一个例子来说明一下：电影名称打斗次数接吻次数电影类型californiaman3104romancehesnotreallyintodudes2100romancebeautifulwoman181romancekevinlongblade10110actionroboslayer3000995actionampedii982action简
7、单说一下这个数据的意思：这里用打斗次数和接吻次数来界定电影类型，如上，接吻多的是romance类型的，而打斗多的是动作电影。还有一部名字未知（这里名字未知是为了防止能从名字中猜出电影类型），打斗次数为18次，接吻次数为90次的电影，它到底属于哪种类型的电影呢？knn算法要做的，就是先用打斗次数和接吻次数作为电影的坐标，然后计算其他六部电影与未知电影之间的距离，取得前k个距离最近的电影，然后统计这k个距离最近的电影里，属于哪种类型的电影最多，比如action最多，则说明未知的这部电影属于动作片类型。在实际使用中，有几个问题是值得注意的：k值的选取，选多大合适呢？计算两者间距离，用哪种距离会更好呢
8、？计算量太大怎么办？假设样本中，类型分布非常不均，比如action的电影有200部，但是romance的电影只有20部，这样计算起来，即使不是action的电影，也会因为action的样本太多，导致k个最近邻居里有不少action的电影，这样该怎么办呢？没有万能的算法，只有在一定使用环境中最优的算法。2.2算法指导思想knn算法的指导思想是“近朱者赤，近墨者黑”，由你的邻居来推断出你的类别。先计算待分类样本与已知类别的训练样本之间的距离，找到距离与待分类样本数据最近的k个邻居；再根据这些邻居所属的类别来判断待分类样本数据的类别。2.3算法计算步骤1.算距离：给定测试对象，计算它与训练集中
9、的每个对象的距离；2.找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻；3.做分类：根据这k个近邻归属的主要类别，来对测试对象分类。2.4相似性度量用空间内两个点的距离来度量。距离越大，表示两个点越不相似。距离的选择有很多13，通常用比较简单的欧式距离。欧式距离：deucx,y=j=1d(xj-yj)212=x-y(x-y)t12马氏距离：马氏距离能够缓解由于属性的线性组合带来的距离失真，是数据的协方差矩阵。dmahx,y=x-y-1(x-y)t曼哈顿距离：dmanx,y=j=1dxj-yj切比雪夫距离：dchex,y=maxj(|xj-yj|)闵氏距离：r取值为2时：曼哈顿距离；
10、r取值为1时：欧式距离。dminx,y=j=1d(xj-yj)r1r,r1平均距离：davex,y=1dj=1d(xj-yj)212弦距离：|2表示2-范数，即|x|2=j=1dxj2dchordx,y=2-2j=1dxjyj|x|2|y|212测地距离：dgeox,y=arccos1-dchordx,y2meancharacterdifference：dmcdx,y=1dj=1d|xj-yj|indexofassociation：12j=1dxjl=1dxl-yjl=1dylcanberrametric：j=1d|xj-yj|(xj+yj)czekanowskicoefficie
11、nt：1-2j=1dminxj,yjj=1d(xj+yj)coefficientofdivergence：1dj=1dxj-yjxj+yj2122.5类别的判定投票决定：少数服从多数，近邻中哪个类别的点最多就分为该类。加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数）2.6优缺点2.6.1优点1.简单，易于理解，易于实现，无需估计参数，无需训练；2.适合对稀有事件进行分类；3.特别适合于多分类问题(multi-modal,对象具有多个类别标签)，knn比svm的表现要好。2.6.2缺点1.懒惰算法，对测试样本分类时的计算量大，内存
12、开销大，评分慢；2.当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的k个邻居中大容量类的样本占多数；3.可解释性较差，无法给出决策树那样的规则。2.7常见问题2.7.1k值的设定k值选择过小，得到的近邻数过少，会降低分类精度，同时也会放大噪声数据的干扰；而如果k值选择过大，并且待分类样本属于训练集中包含数据数较少的类，那么在选择k个近邻的时候，实际上并不相似的数据亦被包含进来，造成噪声增加而导致分类效果的降低。如何选取恰当的k值也成为knn的研究热点。k值通常是采用交叉检验来确定（以k=1为基准）。经验规则：k一般低于训练样本数的平
13、方根。2.7.2类别的判定方式投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。2.7.3距离度量方式的选择高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。2.7.4训练样本的参考原则学者们对于训练样本的选择进行研究，以达到减少计算的目的，这些算法大致可分为两类。第一类,减少训练集的大小。knn算法存储的样本数据,这些样本数据包含了大量冗余数据,这些冗余的数据增了存储的开销和计算代价。缩小训练样本的方法有:在原有的样本中删掉
15、一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列5.遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离l与优先级队列中的最大距离lmax6.进行比较。若l=lmax，则舍弃该元组，遍历下一个元组。若llmax，删除优先级队列中最大距离的元7.组，将当前训练元组存入优先级队列。8.遍历完毕，计算优先级队列中k个元组的多数类，并将其作为测试元组的类别。9.测试元组集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最
16、小的k值。2.9knn算法的java实现代码publicclassknn/**设置优先级队列的比较函数，距离越大，优先级越高*/privatecomparatorcomparator=newcomparator()publicintcompare(knnnodeo1,knnnodeo2)if(o1.getdistance()=o2.getdistance()return-1;elsereturn1;/**获取k个不同的随机数*paramk随机数的个数*parammax随机数最大的范围*return生成的随机数数组*/pu
17、bliclistgetrandknum(intk,intmax)listrand=newarraylist(k);for(inti=0;ik;i+)inttemp=(int)(math.random()*max);if(!rand.contains(temp)rand.add(temp);elsei-;returnrand;/**计算测试元组与训练元组之前的距离*paramd1测试元组*paramd2训练元组*return距离值*/publicdoublecaldistance(listd1,listd2
18、)doubledistance=0.00;for(inti=0;id1.size();i+)distance+=(d1.get(i)-d2.get(i)*(d1.get(i)-d2.get(i);returndistance;/**执行knn算法，获取测试元组的类别*paramdatas训练数据集*paramtestdata测试元组*paramk设定的k值*return测试元组的类别*/publicstringknn(listlistdatas,listtestdata,intk)priorityqueue
19、pq=newpriorityqueue(k,comparator);listrandnum=getrandknum(k,datas.size();for(inti=0;ik;i+)intindex=randnum.get(i);listcurrdata=datas.get(index);stringc=currdata.get(currdata.size()-1).tostring();knnnodenode=newknnnode(index,caldistance(testdata,currdata),c);pq.add(n
20、ode);for(inti=0;idatas.size();i+)listt=datas.get(i);doubledistance=caldistance(testdata,t);knnnodetop=pq.peek();if(top.getdistance()distance)pq.remove();pq.add(newknnnode(i,distance,t.get(t.size()-1).tostring();returngetmostclass(pq);/**获取所得到的k个最近邻元组的多数类*parampq存储k个
21、最近近邻元组的优先级队列*return多数类的名称*/privatestringgetmostclass(priorityqueuepq)mapclasscount=newhashmap();intpqsize=pq.size();for(inti=0;ipqsize;i+)knnnodenode=pq.remove();stringc=node.getc();if(classcount.containskey(c)classcount.put(c,classcount.get(c)+1);elseclasscount.put(c,
25、oc.hawaiiintlconf.systemssciences，1968c.j.stoneconsistentnonparametricregression,ann.stat.,vol.3,no.4,pp.595-645,1977.wclevelandrobustlocally-weightedregressionandsmoothingscatterplots,j.am.statisticalsoc.,vol.74,pp.829-836,1979.t.a.brown&j.koplowitz,theweighted
26、nearestneighborruleforclassdependentsamplesizes,ieeetrans.inform.theory,vol.it-25,pp.617-619,sept.1979.r.short&k.fukanaga,anewnearestneighbordistancemeasure,proc.fifthieeeintlconf.patternrecognition,pp.81-86,1980.theoptimaldistancemeasurefornearestneighbor
27、classification,”ieeetrans.informationtheory1981j.p.mylesandd.j.hand,themulti-classmetricprobleminnearestneighbordiscriminationrules,patternrecognition,1990n.s.altmananintroductiontokernelandnearest-neighbornonparametricregression,1992min-lingzhang&zhi-huazhouml-knn:a
29、nn算法的诸多不足之处也逐渐显露，因此许多knn算法的改进算法也应运而生。针对以上算法的不足，算法的改进方向主要分成了分类效率和分类效果两方面。分类效率：事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。分类效果：采用权值的方法（和该样本距离小的邻居权值大）来改进，han等人于2002年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法waknn(weightedadjustedknearestneighbor)，以促进分类效果；而li等人于20
31、样本；或在原来的训练样本集中选取一些代表样本作为新的训练样本；或通过聚类，将聚类所产生的中心点作为新的训练样本。主要方法的文献25-26。这些方法筛选合适的新训练样本，对于大训练样本集，这个工作量是非常巨大的。第二类，采用快速算法，快速搜索到k个最近邻。knn算法要找到k个最近邻的点，则要计算测试点到所有训练样本的距离，然后找出其中k个距离最小有数据点，当训练样本非常大时，knn算法就不切实际了，为了加快knn搜索过程，主要的方法，其中一个方法是部分距离计算，文献27中提出一种基于小波域部分距离计算的knn搜索算法，文献28提出快速算法(kwenns)。另外一种方法是，引入高效的索引方法，高效
32、的索引方法可以大大降低k个最近邻的计算开销，特别是在高维空间中体现更为明显，文献29提出了一种新的索引结存模型，有的算法虽然能够有效降低k个最近邻的计算开销，提高了knn的分类速度，但它们无法保证进行全局的最优搜索。3.1.2优化相似度度量方法基本的knn算法基于欧基里德距离来计算相似度，这种计算距离的度量标准造成了knn算法对噪声特征非常敏感。为了改变传统knn算法中特征作用相同的缺陷，可在度量相似度的距离公式中给特征赋予不同权重，特征的权重一般根据各个特征在分类中的作用设定。可根据特征在整个训练样本库中的分类作用得到权重，也可根据其在训练样本的局部样本（靠近待测试样本的样本集合）中的分类
33、作用得到权重。人们研究了各种学习调整权值的方法，从而提高了knn分类器的性能。3.1.3优化判决策略传统knn的决策规则一个明显的缺点是，当样本分布密度不均匀时，只按照前k个近邻顺序而不考虑它们的距离会造成误判，影响分类的性能。而且在实际设计分类器时，由于一些类别比另一些类别的训练样本更容易获得，往往会造成训练样本各类别之间目数不均衡，即是训练样本在各个类中的数目基本接近，由于其所占区域大小的不同，也会造成训练样本的分布不均匀。目前改进的方法有均匀化样本分布密度；文献30等对knn的决策规则进行了改进，很好地解决了当各类数据分布不均匀时knn分类器分类性能下降的问题，文献31利用大量近邻集来
34、代替knn中的单一集合，并通过累加近邻的数据集对不同类别的支持度，获得相对可信的支持值，从而改善了近邻判决规则。3.1.4选取恰当的k值由于knn算法中几乎所有的计算都发生在分类阶段，而且分类效果很大程度上依赖于k值的选取，k值的选择很重要。k值选择过小，得到的近邻数过少，会降低分类精度，同时也会放大噪声数据的干扰；而如果k值选择过大，并且待分类样本属于训练集中包含数据数较少的类，那么在选择k个近邻的时候，实际上并不相似的数据亦被包含进来，造成噪声增加而导致分类效果的降低。如何选取恰当的k值也成为knn的研究热点。3.1.5多种算法集成除了上述的各种方法外，也有研究者将knn分类方法和其他
40、)不存在检索trmq，收集参数集tj,trjr=1,2,n，由公式(1计算corr(tj)，并存储etj值；存储新矩阵trmq，其中x=x1,x2,xmt，y=difft1,difft2,difftqt(2)使用公式(2)计算待分样本与训练集各样本的距离。for(inti=1；ithresholdandjlujlcntmax&0，其他(5)rj=dcntjconst+skconst+s2(6)其中threshold和const为常数，s为拉普拉斯平滑因子。具体4.3算法的时问复杂度分析在上述fkmc中，仅利用du的k个最近邻的局部信息进行du的排序分类，省去了非常耗时的全局训练过程，这
42、类算法之一，必然有其十分广泛的应用。在这里仅仅列举一些常见的应用，并重点介绍以下knn算法在文本分类中的应用。5.1knn算法的主要应用领域1)模式识别，特别是光学字符识别；2)统计分类；3)计算机视觉；4)数据库，如基于内容的图像检索；5)编码理论（最大似然编码）；6)数据压缩（mpeg-2标准）；7)向导系统；8)网络营销；9)dna测序；10)拼写检查，建议正确拼写；11)剽窃侦查；12)相似比分算法，用来推断运动员的职业表现。5.2knn算法处理文本分类问题5.2.1文本分类介绍文本自动分类最初是应信息检索（ir）系统的要求而出现的。随着全球互联网络的普及
45、页面，下载调度时会做不同的调度策略；在做页面信息抽取时，会根据页面分类的结果做不同的抽取策略；在做检索意图识别的时候，会根据用户所点击的url所属的类别来推断检索串的类别。5.2.2文本分类过程以internet中的文本为例，待分类文本以html格式存储的半格式化的web页面、文档为主，也是当前internet信息的主要组织形式。文本知识挖掘就是要发现其中隐含的规则，以便于实现internet数据挖掘的智能化，离开了文本知识挖掘，智能化是不能实现的。最常用的文本知识挖掘方法是基于文档特征向量空间模型（characteristicvectorspacemodel，cvsm）的。1