kNN算法综述

1kNN算法综述kNN算法综述王宇航13120476(北京交通大学计算机与信息技术学院，北京，100044)摘要：kNN算法是著名的模式识别统计学方法，是最好的文本分类算法之一，在机器学习分类算法中占有相当大的地位，是最简单的机器学习算法之一。本文对kNN算法及相关文献做一份总结，详细介绍kNN算法的思想、原理、实现步骤以及具体实现代码，并分析了算法的优缺点及其各种改进方案。本文还介绍了kNN算法的发展历程、重要的发表的论文。本文在最后介绍了kNN算法的应用领域，并重点说明其在文本分类中的实现。关键字：kNN算法；k近邻算法；机器学习；文本分类Abstract:KNNalgorithm,afamousstatisticalmethodofpatternrecognition,whichisoneofthebestalgorithmsfordealingwithtextcategorization,isplayinganimportantroleinmachinelearningclassificationalgorithm,anditisoneofthesimplestalgorithmsinmachinelearning.ThispapermainlysummariesthekNNalgorithmanditsrelatedliterature,anddetailedintroducesitsmainidea,principle,implementationstepsandspecificimplementationcode,aswellasanalyzestheadvantagesanddisadvantagesofthealgorithmanditsvariousimprovementschemes.ThispaperalsointroducesthedevelopmentcourseofkNNalgorithm,itsimportantpublishedpaper.Inthefinal,thispaperintroducestheapplicationfieldofkNNalgorithm,andespeciallyintextcategorization.Keywords:KNNalgorithm,Kneighboralgorithm,Machinelearning,Textclassification1引言分类是数据挖掘中的核心和基础技术，在经营、决策、管理、科学研究等多个领域都有着广泛的应用。目前主要的分类技术包括决策树、贝叶斯分类、kNN分类、人工神经网络等。在这些方法中，kNN分类是一种简单、有效、非参数的方法，现已经广泛应用于文本分类、模式识别、图像及空间分类等领域。本文从各个角度对kNN算法进行较为全面的总结。本文的结构如下：在第二部分，主要介绍kNN算法的基本原理、思想、实现步骤、Java实现代码以及发展历程和经典论文。第三部分是对kNN算法的诸多不足之处进行的讨论，并给出一些改进的方案。2kNN算法综述第四部分介绍的是kNN算法如何处理多标签数据。第五部分介绍了kNN算法目前的主要应用领域，并着重说明了其在文本分类中的出色表现。2kNN算法简介2.1算法引入KNN算法是机器学习里面比较简单的一个分类算法，整体思想比较简单：计算一个点A与其他所有点之间的距离，取出与该点最近的k个点，然后统计这k个点里面所属分类比例最大的，则点A属于该分类。下面用一个例子来说明一下：电影名称打斗次数接吻次数电影类型CaliforniaMan3104RomanceHe’sNotReallyintoDudes2100RomanceBeautifulWoman181RomanceKevinLongblade10110ActionRoboSlayer3000995ActionAmpedII982Action简单说一下这个数据的意思：这里用打斗次数和接吻次数来界定电影类型，如上，接吻多的是Romance类型的，而打斗多的是动作电影。还有一部名字未知（这里名字未知是为了防止能从名字中猜出电影类型），打斗次数为18次，接吻次数为90次的电影，它到底属于哪种类型的电影呢？KNN算法要做的，就是先用打斗次数和接吻次数作为电影的坐标，然后计算其他六部电影与未知电影之间的距离，取得前K个距离最近的电影，然后统计这k个距离最近的电影里，属于哪种类型的电影最多，比如Action最多，则说明未知的这部电影属于动作片类型。在实际使用中，有几个问题是值得注意的：K值的选取，选多大合适呢？计算两者间距离，用哪种距离会更好呢？计算量太大怎么办？假设样本中，类型分布非常不均，比如Action的电影有200部，但是Romance的电影只有20部，这样计算起来，即使不是Action的电影，也会因为Action的样本太多，导致k个最近邻居里有不少Action的电影，这样该怎么办呢？没有万能的算法，只有在一定使用环境中最优的算法。2.2算法指导思想kNN算法的指导思想是“近朱者赤，近墨者黑”，由你的邻居来推断出你的类别。先计算待分类样本与已知类别的训练样本之间的距离，找到距离与待分类样本数据最近的k个邻居；再根据这些邻居所属的类别来判断待分类样本数据的类别。3kNN算法综述2.3算法计算步骤1.算距离：给定测试对象，计算它与训练集中的每个对象的距离；2.找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻；3.做分类：根据这k个近邻归属的主要类别，来对测试对象分类。2.4相似性度量用空间内两个点的距离来度量。距离越大，表示两个点越不相似。距离的选择有很多[13]，通常用比较简单的欧式距离。欧式距离：deuc(𝑥,𝑦)=[∑(𝑥𝑗−𝑦𝑗)2𝑑𝑗=1]12=[(𝑥−𝑦)(𝑥−𝑦)𝑇]12马氏距离：马氏距离能够缓解由于属性的线性组合带来的距离失真，Σ是数据的协方差矩阵。dmah(𝑥,𝑦)=√(𝑥−𝑦)𝛴−1(𝑥−𝑦)𝑇曼哈顿距离：dman(𝑥,𝑦)=∑|𝑥𝑗−𝑦𝑗|𝑑𝑗=1切比雪夫距离：dche(𝑥,𝑦)=max𝑗(|𝑥𝑗−𝑦𝑗|)闵氏距离：r取值为2时：曼哈顿距离；r取值为1时：欧式距离。dmin(𝑥,𝑦)=(∑(𝑥𝑗−𝑦𝑗)𝑟𝑑𝑗=1)1𝑟,𝑟≥1平均距离：dave(𝑥,𝑦)=[1𝑑∑(𝑥𝑗−𝑦𝑗)2𝑑𝑗=1]12弦距离：||∙||2表示2-范数，即||𝑥||2=√∑𝑥𝑗2𝑑𝑗=1dchord(𝑥,𝑦)=(2−2∑𝑥𝑗𝑦𝑗𝑑𝑗=1||𝑥||2||𝑦||2)12测地距离：dgeo(𝑥,𝑦)=arccos(1−𝑑𝑐ℎ𝑜𝑟𝑑(𝑥,𝑦)2)Meancharacterdifference：4kNN算法综述dmcd(𝑥,𝑦)=1𝑑∑|𝑥𝑗−𝑦𝑗|𝑑𝑗=1Indexofassociation：12∑|𝑥𝑗∑𝑥𝑙𝑑𝑙=1−𝑦𝑗∑𝑦𝑙𝑑𝑙=1|𝑑𝑗=1Canberrametric：∑|𝑥𝑗−𝑦𝑗|(𝑥𝑗+𝑦𝑗)𝑑𝑗=1Czekanowskicoefficient：1−2∑min⁡{𝑥𝑗,𝑦𝑗}𝑑𝑗=1∑(𝑥𝑗+𝑦𝑗)𝑑𝑗=1Coefficientofdivergence：(1𝑑∑(𝑥𝑗−𝑦𝑗𝑥𝑗+𝑦𝑗)2𝑑𝑗=1)122.5类别的判定投票决定：少数服从多数，近邻中哪个类别的点最多就分为该类。加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数）2.6优缺点2.6.1优点1.简单，易于理解，易于实现，无需估计参数，无需训练；2.适合对稀有事件进行分类；3.特别适合于多分类问题(multi-modal,对象具有多个类别标签)，kNN比SVM的表现要好。2.6.2缺点1.懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢；2.当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数；3.可解释性较差，无法给出决策树那样的规则。5kNN算法综述2.7常见问题2.7.1k值的设定k值选择过小，得到的近邻数过少，会降低分类精度，同时也会放大噪声数据的干扰；而如果k值选择过大，并且待分类样本属于训练集中包含数据数较少的类，那么在选择k个近邻的时候，实际上并不相似的数据亦被包含进来，造成噪声增加而导致分类效果的降低。如何选取恰当的K值也成为KNN的研究热点。k值通常是采用交叉检验来确定（以k=1为基准）。经验规则：k一般低于训练样本数的平方根。2.7.2类别的判定方式投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。2.7.3距离度量方式的选择高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。2.7.4训练样本的参考原则学者们对于训练样本的选择进行研究，以达到减少计算的目的，这些算法大致可分为两类。第一类,减少训练集的大小。KNN算法存储的样本数据,这些样本数据包含了大量冗余数据,这些冗余的数据增了存储的开销和计算代价。缩小训练样本的方法有:在原有的样本中删掉一部分与分类相关不大的样本样本,将剩下的样本作为新的训练样本;或在原来的训练样本集中选取一些代表样本作为新的训练样本；或通过聚类,将聚类所产生的中心点作为新的训练样本。在训练集中，有些样本可能是更值得依赖的。可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。2.7.5性能问题kNN是一种懒惰算法，而懒惰的后果：构造模型很简单，但在对测试样本分类地的系统开销大，因为要扫描全部训练样本并计算距离。已经有一些方法提高计算的效率，例如压缩训练样本量等。2.8算法流程1.准备数据，对数据进行预处理2.选用合适的数据结构存储训练数据和测试元组3.设定参数，如k4.维护一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这6kNN算法综述k个元组的距离，将训练元组标号和距离存入优先级队列5.遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L与优先级队列中的最大距离Lmax6.进行比较。若L=Lmax，则舍弃该元组，遍历下一个元组。若LLmax，删除优先级队列中最大距离的元7.组，将当前训练元组存入优先级队列。8.遍历完毕，计算优先级队列中k个元组的多数类，并将其作为测试元组的类别。9.测试元组集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最小的k值。2.9kNN算法的Java实现代码publicclassKNN{/***设置优先级队列的比较函数，距离越大，优先级越高*/privateComparatorKNNNodecomparator=newComparatorKNNNode(){publicintcompare(KNNNodeo1,KNNNodeo2){if(o1.getDistance()=o2.getDistance())return-1;elsereturn1;}};/***获取K个不同的随机数*@paramk随机数的个数*@parammax随机数最大的范围*@return生成的随机数数组*/publicListIntegergetRandKNum(intk,intmax){ListIntegerrand=newArrayListInteger(k);for(inti=0;ik;i++){inttemp=(int)(Math.random()*max);if(!rand.contains(temp))rand.add