3.KNN不足与改进的内容

北京理工大学软件学院商务智能KNN算法不足与改进学号：班级：姓名：专业：指导教师：摘要：KNN算法的核心思想是，通过计算每个训练样本到待分类数据的距离，取和待分类数据距离最近的K个训练样本，K个样本中哪个类别的训练样本占多数，则待分类数据就属于哪个类别。本文首先说明了KNN算法的应用及优点，继而基于KNN算法的不足以及改进方法进行详细论述，最后结束语总结全文。一前言KNN算法是对NN（nearestneighbor）算法即近邻算法的改进，最初的近邻算法是由T.M.Cover,在其文章”RatesofConvergenceforNearestNeighborProcedures,”中提出的，是以全部训练样本作为带标点，计算测试样本与所有样本的距离并以最近邻者的类别作为决策，后学者们对近邻算法进行了各方面的改进。1.1KNN应用场景文本分类：文本分类主要应用于信息检索，机器翻译，自动文摘，信息过滤，邮件分类等任务。文本分类在搜索引擎中也有着大量的使用，网页分类/分层技术是检索系统的一项关键技术，搜索引擎需要研究如何对网页进行分类、分层，对不同类别的网页采用差异化的存储和处理，以保证在有限的硬件资源下，提供给用户一个高效的检索系统，同时提供给用户相关、丰富的检索结果。回归：通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。可以使用knn算法做到比较通用的现有用户产品推荐，基于用户的最近邻(长得最像的用户)买了什么产品来推荐是种介于电子商务网站和sns网站之间的精确营销。1.2KNN有如下优点本就聚为若干个类了。每个簇的类别由簇中多数文本类别而定。然后结合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算法分类速度的主要改进办法之一就是通过使用小样本库代替原来的大样本库进行分类。这类方法一般是在原来的训练样本库中选取一些代表样本作为新的训练样本,或删除原来的训练样本库中的某些样本,将剩下的样本作为新的训练样本库,从而达到减小训练样本库的目的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距离，然后依据测试文本与训练文本的距离远近来确定类别。显然，它没有非常显别地考虑特征属性关联及其现等因素对文本相似度的影响，可以认为恰当的考虑关联与共现等因素，KNN的效果应当更好。3.3.2改进的KNN方法根据语言学知识，一定层次上的语义是由一定范围的词汇共同表达的，共同表达的词汇构成语义链。语义链中不仅有规范的词汇，而且有规范的次序。语义链的重现，就可以为彼此表达同一语义，而且能进一步认为，语义链重合量越多，那么语义同一性越大。向量空间中，每一个元素对应一个经过提取之后的文本特征，可以认为它就是语义链的一个组成部分。一个文本中的所有特征，构成了文本的整个语义，特征之间的相