搜索
北京理工大学软件学院商务智能1KNN算法不足与改进学号：班级：姓名：专业：指导教师：北京理工大学软件学院商务智能2摘要：KNN算法的核心思想是，通过计算每个训练样本到待分类数据的距离，取和待分类数据距离最近的K个训练样本，K个样本中哪个类别的训练样本占多数，则待分类数据就属于哪个类别。本文首先说明了KNN算法的应用及优点，继而基于KNN算法的不足以及改进方法进行详细论述，最后结束语总结全文。一前言KNN算法是对NN（nearestneighbor）算法即近邻算法的改进，最初的近邻算法是由T.M.Cover,在其文章”RatesofConvergenceforNearestNeighborProcedures,”中提出的，是以全部训练样本作为带标点，计算测试样本与所有样本的距离并以最近邻者的类别作为决策，后学者们对近邻算法进行了各方面的改进。1.1KNN应用场景文本分类：文本分类主要应用于信息检索，机器翻译，自动文摘，信息过滤，邮件分类等任务。文本分类在搜索引擎中也有着大量的使用，网页分类/分层技术是检索系统的一项关键技术，搜索引擎需要研究如何对网页进行分类、分层，对不同类别的网页采用差异化的存储和处理，以保证在有限的硬件资源下，提供给用户一个高效的检索系统，同时提供给用户相关、丰富的检索结果。回归：通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。可以使用knn算法做到比较通用的现有用户产品推荐，基于用户的最近邻(长得最像的用户)买了什么产品来推荐是种介于电子商务网站和sns网站之间的精确营销。1.2KNN有如下优点北京理工大学软件学院商务智能3-算法易于理解且易于实现-几乎没有训练过程(只是需要确定K值和必要的预处理)-可以在线更新-非线性分类器，鲁棒性强二KNN算法不足该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。【KNN的主要不足】-计算量大，分类速度慢·浓缩训练样本集·加快K个最近邻的搜索速度·KNN在对属性较多的训练样本进行分类时，由于计算量大而使其效率大大降低效果不是很理想。·懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢。-K值难以确定·目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整K值。·可解释性较差，无法给出决策树那样的规则。-对于不平衡样本集比较敏感·采用权值的方法（增大距离小的邻居样本的权值）当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。北京理工大学软件学院商务智能4三KNN算法改进3.1基于聚类的KNN算法改进3.1.1传统的kNN算法对于测试集中每一个测试文本,都需要计算它与训练集中每个文本的距离,然后把距离排序找到离该测试文本最近的k个文本,根据测试文本与训练文本的距离来给该测试文档的候选类别按公式（1）评分。如果有属于同一个类别的,就将该类别中的文本的打分求和作为该类别的得分。最后,将得分排序，测试文本将被分配给得分最高的那个类别。SCORE(c|x)=Σsim(x,d)I(d,c)x是一个测试集文本，c是训练集的类别，d是距离x最近的k个文本之一；sim(x,d)是文本x与文本d的相似度，这里指的是距离；I(d,c)是表示d是否属于类c，如果属于类c则为1，否则为0。3.1.2改进的IKNN算法首先对训练集文本进行聚类，采用DBSCAN算法。算法过程如下：第一步：如果文本对象P未被归入某个簇或标记为噪声，就检查它的指定半径邻域r，如果指定半径邻域内包含的对象数目大于等于给定的值m，就建立新簇C，将p的指定半径领域r中所有点加入该簇C；第二步：对C中所有尚未被处理(归入某个簇或标记为噪声)的对象q，检查它的指定半径邻域，如果该邻域内包含对象数目大于等于给定的值m，将该邻域中没有归入任何一个簇的对象加入C；第三步：重复第二步，继续检查C中未被处理对象，直到没有新的对象加入当前簇C：第四步：重复以上步骤，直到所有对象都被处理。其中关键参数为作为密度计算的距离表示的半径，密集点所必需的在指定半径内拥有的最少的其他点的数目。通过这两个参数我们就可以计算在任何点周围的密度值。这样，训练集中文北京理工大学软件学院商务智能5本就聚为若干个类了。每个簇的类别由簇中多数文本类别而定。然后结合KNN算法，计算测试集文本与训练集文本簇之间的距离，这样可以减少计算量和个别孤立点对测试集文本的影响。具体算法：第一步：对于任一个给定的测试集文本，计算与训练集中各个簇的距离，采用（2）式为测试集文本评分SCORE(c|x)=Σsim(x,t)I(t,c)其中x是一个测试集文本，c是训练集的类别，t是距离x最近的k个文本簇之一。sim(x,t)是文本x与文本t簇的相似度，这里指的是距离;I(t,c)是表示t簇是否属于类c，如果属于类c则为1，否则为0;第二步：根据评分结果进行排序，选取前k个簇。第三步：从这些簇中选取n个与测试集文本最近的文本，按照（1）式评分，判定该测试集文本类别，回归到传统的KNN算法。改进算法中有领域半径r，指定邻域内最小文本数m，选取簇类个数k，从k簇中选取距离最小的n个文本这几个参数。根据试验表明，这几个参数需要经过多次试验，得出较优取值范围。3.2用于文本分类的改进KNN算法在文本分类中,KNN方法通常是建立在VSM模型上的,其判断样本相似度的样本距离测度通常使用欧氏距离在传统的欧氏距离中,各特征的权重相同,也就是认定各个特征对于分类的贡献是相同的,显然这是不符合实际情况的同等的权重使得特征向量之间相似度计算不够准确,进而影响分类精度。本文采用加权欧氏距离公式,特征权重通过灵敏度方法获得传统KNN方法样本相似度计算量较大和对样本库容量依赖性较强。在KNN分类算法中,确定待分类样本类别需要计算其与训练样本库中所有样本的相似度,才能求得与其距离最近的I个样本众所周知,文本的特征向量空间具有很高的维数,这样对于一个有成千上万的训练样本的文本分类系统而言,庞大的计算量将严重阻碍分类速度,难以达到用户的实际需求,甚至导致KNN算法在文本分类中失去实用性本文通过样本库的裁减来减少样本相似度的计算量,提高KNN的分类速度,以提高KNN在文本分类中的实用价值降低样本相似度计算量,加快KNN算法分类速度的主要改进办法之一就是通过使用小样本库代替原来的大样本库进行分类。北京理工大学软件学院商务智能6这类方法一般是在原来的训练样本库中选取一些代表样本作为新的训练样本,或删除原来的训练样本库中的某些样本,将剩下的样本作为新的训练样本库,从而达到减小训练样本库的目的O这种途径最主要的方法是Hart的Condensing算法。WilSon的Editing算法和Devijver的MultiEdit算法,Kuncheva使用遗传算法在这方面也进行了一些研究O在训练样本库中每增加或删除一个样本时,都要对样本进行一次测试,反复迭代直到样本库不再变化,这对于有成百上千的训练样本来说,其工作量是非常巨大的O在本文的裁减训练样本库的方法中,首先利用CURE聚类算法获得样本数据库S的代表样本库S1,然后再用基于Tabu算法的方法对新的训练样本库S1进行一步维护(增加或删除训练样本),以得到一个分类性能较优。样本量较小的训练样本库O本文算法不仅极大缩减样本库裁减的工作量,且在裁减样本库的基础上使KNN算法的分类速度和分类精度都得到了提高O实验结果表明了这种方法的有效性和实用性。3.3改进的KNN方法及其在文本分类中的应用3.3.1文本分类的KNN方法在向量空间模型中，文本的内容被形式化为多维空间中的一个点，通过向量的形式给出。正是因为把文档以向量的形式定义到实数域中，才使得模式识别和其它领域中各种成熟的计算方法得以采用，极大地提高了自然语言文档的可计算性和可操作性。文档向量中的各个维对应于用于表征文档的各个特征属性。一般采用经典的TFIDF进行文档的特征权值的表示。KNN方法是一种基于实例的方本分类方法。首先，对于一个测试文本，计算它与训练样本集中每个文本的文本相似度，依文本相似度找出k个最相似的训练文本。然后在此基础上给每一个文本类打分，分值是k个训练文档中属于该类的文本与测试文本之间的文档相似度之和。对这k个文本所属类的分值统计完毕之后，即按分值进行排序。为了分类合理，应当选定一个阈值，可以认为测试文本属于越过阈值的所有类。通过上面的分析可知道，KNN法的实质就是以特征属性权值作为特征空间的坐标系测度，先计算测试文本与训练文本之间在该坐标系中的Cosine距离，然后依据测试文本与训练文本的距离远近来确定类别。显然，它没有非常显别地考虑特征属性关联及其现等因素对文本相似度的影响，可以认为北京理工大学软件学院商务智能7恰当的考虑关联与共现等因素，KNN的效果应当更好。3.3.2改进的KNN方法根据语言学知识，一定层次上的语义是由一定范围的词汇共同表达的，共同表达的词汇构成语义链。语义链中不仅有规范的词汇，而且有规范的次序。语义链的重现，就可以为彼此表达同一语义，而且能进一步认为，语义链重合量越多，那么语义同一性越大。向量空间中，每一个元素对应一个经过提取之后的文本特征，可以认为它就是语义链的一个组成部分。一个文本中的所有特征，构成了文本的整个语义，特征之间的相互关联和共现，对于文本相似度来说是很有意义的。然而，传统向量空间模型中相似度的计算没有很好地考虑到特征词之间的相互关联与共现，使分类结果不甚理想。四参考文献【1】王煜、张明、王正欧用于文本分类的改进KNN算法2007【2】樊东辉基于聚类的KNN算法改进【3】孙丽华一种改进的KNN方法及其在文本分类中的应用