k近邻 文本分类

ＳＯＦｒＷＡＲＥ　ＤＥＶＥＬ０ＰＭＥＮＴ　ＡＮＤ　ＤＥＳＩＧＮ　软件开发与设计　

基于平均距离的Ｋ一近邻分类改进算法　许燕青　（闽南理工学院，石狮３６２７００）　摘要：提出了一种基于平均距离的Ｋ一近邻分类改进算法，克服了Ｋ一近邻分类算法准确率不高的两个问题：一是　各个类别的近邻个数相同时则无法判断测试样本的类别；二是即使某一类别的近邻个数较多，但由于此类别的近邻　样本与测试样本的相似度都比较小，则有可能把测试样本错误地判断为此类别。　关键词：分类；平均距离；Ｋ一近邻分类算法；属性值　

Ｆｏｒｗａｒｄ　ａ　Ｍｅｔｈｏｄ　Ｂａｓｅｄ　ｏｎ　ｔｈｅ　Ａｖｅｒａｇｅ　Ｄｉｓｔａｎｃｅ　Ｋ—ｎｅｉｇｈｂｏｒ　Ａｌｇｏｒｉｔｈｍ．　Ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ＸＵ　Ｙａｎｑｉｎｇ　（Ｍｎｕｓｔ　Ｐｏｌｙｔｅｃｈｎｉｃ　Ｉｎｓｔｉｔｕｔｅ，Ｓｈｉｓｈｉ　３６２７００）　Ａｂｓｔｒａｃｔ：ｔｈｉｓ　ｐａｐｅｒ　ｐｕｔｓ　ｆｏｒｗａｒｄ　ａ　ｍｅｔｈｏｄ　ｂａｓ　ｅｄ　ｏｎ　ａｖｅｒａｇｅ　ｄｉｓｔａｎｃｅ　Ｋ—ｎｅｉｇｈｂｏｒ　ａｌｇｏｒｉｔｈｍ　ｕｓｅｄ　ｔｏ　ｏｖｅｒｃｏｍｅ　ｔｈｅ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ，Ｋ　ｎｅｉｇｈｂｏｒ—ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｔｗｏ　ｒｅａｓｏｎｓ　ｎｏｔ　ｈｉｇｈ　ａｃｃｕｒａｃｙ　ｏｆ　ｅａｃｈ　ｃａｔｅｇｏｒｙ：ｏｎｅ　ｉｓ　ｔｈｅ　ｓａｍｅ　ｎｕｍｂｅｒ　ｏｆ　ｎｅｉｇｈｂｏｒｓ　ｃａｎｎｅｔ　ｊｕｄｇｅ　ｔｈｅ　ｔｅｓｔ　ｓｐｅｃｉｍｅｎ　ｃａｔｅｇｏｒｙ，２　ｅｖｅｎ　ｏｎｅ　ｋｉｎｄ　ｏｆ　ｏｔｈｅｒ　ｎｅｉｇｈｂｏｒｓ，ｂｕｔ　ｂｅｃａｕｓｅ　ｔｈｅ　ｎｕｍｂｅｒ　ｍｏｒｅ　ｓｕｃｈ　ｏｔｈｅｒ　ｎｅｉｇｈｂｏｒｓ　ｓａｍｐｌｅｓ　ａｎｄ　ｔｅｓｔｉｎｇ　ｓａｍｐｌｅｓ　ａｒｅ　ｒｅｌａｔｉｖｅｌｙ　ｓｍａｌｌ，ｓｉｍｉｌａｒｉｔｙ　ｉｓ　ｌｉｋｅｌｙ　ｔｏ　ｔｅｓｔ　ｓａｍｐｌｅ　ｊｕｄｇｅ　ｔｈｉｓ　ｃａｔｅｇｏｒｙ　ｍｉｓｔａｋｅ．　Ｋｅｙ　ｗｏｒｄｓ：ｃｌａｓｓｉｆｉｃａｔｉｏｎ；Ａｖｅｒａｇｅ　ｄｉｓｔａｎｃｅ；Ｋ－ｎｅｉｇｈｂｏｒ　ａｌｇｏｒｉｔｈｍ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ；Ａｔｔｒｉｂｕｔｅ　ｖａｌｕｅｓ　

信息技术　：　兰　：Ｅ　Ｃｈｉｎａ　Ｎｅｗ　Ｔｅｃｈｎｏｌｏｇｉｅｓ　ａｎｄ　Ｐｒｏｄｕｃｔｓ　搜索引擎中的文本分类方法研究　彭玉容沈红岩程芳　（河北农业大学信息科学与技术学院，河北保定０７１０００）　摘要：文本分类技术在搜索引擎中有很重要的用途，本文简要分析了文本分类的评估方法，应用于搜索引擎的分类过程，重点介绍了现行的文　本自动分类方法，包括经典算法和新算法以及未来的发展趋势。　关键词：文本分类；分类器；准确率　互联网的出现，使得人类全部的信息资源以前　所未有的方式和程度在全球内互联互通，现在网上　的信息纷繁芜杂，还没有—个统一的组织标准。在　信　量如此丰富的网上查找自己感兴趣的信息是　当务之急，搜索引擎就应运而生。即便如此搜索引　擎搜索到的信息也是杂乱无章的，如果我们对网页　进行分类就会为我们提供很多方便。如果人工进行　分类几乎是不可能的，如果能够实施网页的自动　分类，就可以实现网页标引和检索的分类主题一体　化，搜索引擎就能够兼有分类浏览、检索和关键词　检索的优点　Ｂ够深入到网页层次，帮助用户迅速的　判断返回的结果是否符合自己的检索要求。　１评估方法　因为文本分类从根本上说是一个映射过程，所　以评估文本分类系统的标志是映射的准确程度和　映射的速度。映射的速度取决于映射规则的复杂程　度，而评估映射准确程度的参照物是通过专家思考　判断后对文本的分类结果　里假设人工分类完全　正确并且排除个人思维差异的因素），与人工分类　结果越相近，分类的准确程度就越高，这里隐含了　评估文本分类系统的两个指标：准确率和查全率，准　确率是所有判断的文本中与人工分类结果吻合的　文本所占的比率。其数学公式表示如下：　绯编　分类的ｉＥ确立＝本数　…　实际分黉翰文本数　查全率是人工分类结果应有的文本中分类系　统吻合的文本所占的比率，其数学公式表示如下：　分类的正确文本数　——　ｊｉ　准确率和查全率反映了分类质量的两个不同　方面，两者必须综合考虑，不可偏废，因此，存在一　种新的评估指标，ｎ测试值，其数学公式如下：　Ｆ　湖Ｉ试值＝　；　２文本分类过程　圈一圈一回　ｉ嚣二　ｌ囤一困一巨　ｌ　张蟪琏籀　ｌ　静耩矬精　从图１可以看出，构建一个分类器的关键因素　包括：预处理、训练集、特征选取算法、分类算法和　截尾算法等。　３常用分类算法　到目前为止产生了许多的文本自动分类方法，　如中心向量法、朴素贝叶斯方法等等。在讨论各种　分类方法之前，我们首先说明本章用到的一些常用　符号。　Ｄ＝｛＜ｗ　．．Ｗ　＞｝表示将要被分类的文本的特　征向量；　ＣＩ￣，－Ｃ　表示这些文本可能的类别；　．ｒ．【ｄ．，．．．ｄｊ表示包含Ｎ个文本的训练集；　ｖ　…ｙ　，表示这Ｎ个训练文本的类别；　Ｎ．表示训练集中类的样本个数；　ｍ表示训练集特征个数；　３．１中心向量法　中心向量算法比较简单，它利用向量空间模　型，对各个训练类别分别计算平均向量，进行标准　化处理，再计算相似度。设Ｔ＝｛ｄ１，…ｄＪ＝｛＜ｗ　．－Ｗ　。＞，．．．，＜ｗ　．＿Ｗ　）＜ｗ　－Ｗ　，表示文档ｄｊ的向量，ｗ　表示特征ｉ在文档　中的权重，对于类别ｃ。其中心　向量ＶＣｉ＝｛ＶＷ　－Ｖｗ　其中：　１　。　……，ｍ　然后，用Ｃｏｓ（Ｄ，ｖｃｉ）来计算它们之间的相似　度。　３．２朴素贝叶斯方法（Ｎａ¨ｖｅ　Ｂａｙｅｓ）　Ｎａ¨ｖｅ　Ｂａｙｅｓ（简称ＮＢ）理论的基本观点是：假　设在给定的文本类语境下，文本＿『蓠．性是相互独立　的。　贝叶斯分类方法以贝叶斯定理为理论基础，是　一种在已知先验概率与条件概率的情况下的模式　识别方法。贝叶斯分类方法分两种：一种将问题　简化．ｆ段设—个屙ｌ生对给定类的影响独立于其他属　性，即特征独立性假设。当假设成立时，与其他分类　算法相比，朴素贝叶斯分类器是最精确的。但是实　际问题中文本属性之间的依赖关系是可能存在　的。这就要求考虑屙Ｉ生之间的依赖程度，显然其　计算复杂度比前一种高得多，当然也更能反映真实　文本的情况。但是实现十分复杂，目前还停留在理　论的研究阶段。大量的理论和实验表明贝叶斯算法　繁杂，且效果不显著。但是我们可以借鉴其项无　关ｌ生的基本棚念。　３－３　ｋ一近邻算法（Ｋ－ＮＮ）　ＫＮＮ方法是一种基于实例的文本分类方法．首　先，对于一个测试文本，计算它与训练样本集中每　个文本的文本相似度，依文本相似度找出ｋ个最相　似的训练文本。然后在此基础上给每一个文本类打　分，分值是ｋ个训练文档中属于该类的文本与测试　文本之间的文档相似度之和。对这ｋ个文本所属类　的分值统计完毕之后，即按分值进行排序。为了分　类合理，应当选定一个阈值，可以认为测试文本属　于越过阈值的所有类。　ｋｎｎｄｏｃ是指在训练集中依文本相似度找出与　文本ｄｘ，最相似的ｋ个训练文本所组成的训练文本　子集；当训练文本ｄ　属于ｃ＇类时　ｃ　取１，否则取　ｎ一般可以通过另　３．４支持向量机（ＳＶＭ）　支持向量机（ＳＶＭ）建立在计算学习理论的结　构风险最小化原则之上，其主要思想是针对两类分　类问题在高维空间中寻找一个超平面作为两类的　分割。以保证最小的分类错误率。用（ＳＶＭ）实现分　类，首先要从原始空间中抽取特征，将原始空问中　的样本映射为高维特征空间中的一个向量。包含这　个向量的文本称为正例，所有不包含这个向量的文　本称为反例。空白被定义为在线形关系里，距正例　和反例最近的超平面中的实例。一个支持向量机是　从最大空白中分离反例的正例集合构成的超平面。　３．５基于投票的方法（、　ｉｎｇ　Ｍｅｔｈｏｄ）　基于投票方法比较典型的有Ｂａｇｇｉｎｇ法和　Ｂｏｏｓｔｉｎｇ法。ａ．Ｂａｇｇｉｎｇ法。训练Ｒ个分类器ｆｉ，分类　器之间其他相同就是参数不同。其中ｆ　ｉ是通过从　训练集合中（Ｎ篇文档）随机取陬后放回）Ｎ次文档　构成的训练集合训练得到的。对于新文档ｄ，用这　Ｒ个分类器去分类，得到的最多的那个类别作为ｄ　的最终类别。ｂ．Ｂｏｏｓｔｉｎｇ法。类似Ｂａｇｇｉｎｇ方法＇彳旦是　训练是串行进行的第ｋ个分类器训练时关注对前　ｋ一１分类器中错分的文档，即不是随机晚而是加大　取这些文档的概率。　３．６遗传算法（Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍｓ，ＧＡ）　遗传算法是一种基于生物进化过程的组合优　化方法。其基本思想是：随着时间的更替，只有最适　合的物种才得以进化。将这种思想用于文本挖掘就　是根据遗传算法获得最适合的模型，并据此对模型　进行优化。遗传算法能够解决其他技术难以解决的　问题然而它也是一种最难理解和最开放的方法。遗　传算法常与神经网络结合起来使用，以在较高的层　次上提高模型的可理解性。它有三个基本算子：遗　传、交叉、变异萁基本步骤为ａ随机产生初始种群；　ｂ．构造评价函数　．选择高适应值的个体进入下一　代｜ｄ．通过遗传、变异算子产生新的个体．ｅ．重复ｂ￣ｄ　过程，直到产生最优化个体问题解决。　３－７神经网络　神经网络的基本特　：大量简单节点的复杂连　接；高度并行处理；分布式存储，信息存在整个网中，　用权值体现出来有联想能力，可以从—个不完整的　信息恢复出完整信息泊组织、自学习。图２是—个　多层的神经网络结构图。　图２多层神经网络结构图　神经网络的最大优点是他能精确地对复杂问　题进行预测。　以上列出了七种分类方法但是这些分类方法　也还远没有达到满足用户的需求。伴随着计算机　技术的不断进步，人们也在不断的研究新的分类方　法。　４小结：此文章对于深入研究文本信息加工、　信息服务有重要的指导意义。虽然文本分类技术取　得了长足发展，不断涌现新的算法，但是对于一般　用户的感觉还是不能够随心所欲的快捷方便的找　到自己所需要的信息，所以在文本自动分类领域还　有很大的发展空间。　参考文献　［１降国和．基于聚类的大样本支持向量机研究．计算　机科学２ｏｏ６（４）．　［２］王义麟．一种基于决策树的分类算法Ｊ．软件学　报２００４。１５（１１：１—４．　１和亚丽’陈立潮．Ｗｅｂ文本挖掘中的特征选取方　法研究Ｊ．计算机工程２００５圆．　中国新技术新产品　

KNN算法总结

1 KNN分类算法

1.1KNN简述

K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别[1]。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

KNN最邻近规则，主要应用领域是对未知事物的识别，即判断未知事物属于哪一类，判断思想是，基于欧几里得定理，判断未知事物的特征和哪一类已知事物的的特征最接近。

1.2 KNN原理

最近邻方法(k-nearest neighbor,简称kNN)是一种简洁而有效的非参数分类方法，是最简单的机器学习算法之一，该算法最初由Cover和Hart提出的，用于解决文本的分类问题。

K近邻算法是最近邻算法的一个推广。该规则将是一个测试数据点x分类为与它最接近的K个近邻中出现最多的那个类别。K近邻算法从测试样本点x开始生长，不断的扩大区域，直到包含进K个训练样本点为止，并且把测试样本点x归为这最近的K个训练样本点中出现频率最大的类别。其中测试样本与训练样本的相似度一般使用欧式距离测量。

如果K值固定，并且允许训练样本个数趋向于无穷大，那么，所有的这K个近邻都将收敛于x。如同最近邻规则一样，K个近邻的标记都是随机变量，概率P（wi|x），i=1,2,…,K都是相互独立的。假设P（wm|x）是较大的那个后验概率，那么根据贝叶斯分类规则，则选取类别wm。而最近邻规则以概率P（wm|x）选取类别。而根据K近邻规则，只有当K个最近邻中的大多数的标记记为wm，才判定为类别wm。做出这样断定的概率为

龙源期刊网

一种基于KNN的文本分类算法

作者：余悦蒙 黄小斌

来源：《电脑知识与技术》2012年第07期

摘要：KNN(K-Nearest Neighbor)是向量空间模型中最好的文本分类算法之一。但是，当样本集较大以及文本向量维数较多时，KNN算法分类的效率和准确率就会大大降低。该文提出了一种提高KNN分类效率的改进算法,并且改进了相似度的计算方法，能更准确的判断维数高且样本集大的文本向量。算法在训练过程中计算出各类文本在向量空间中的分布范围，在分类过程中，根据待分类文本向量在样本空间中的分布位置，缩小其K最近邻搜索范围。实验证实改进的算法可以在保持KNN分类性能基本不变的情况下，显著提高分类效率。

关键词：文本分类；K-最近邻；算法

中图分类号：TP301文献标识码：A文章编号：1009-3044(2012)07-1564-03

An Algorithm for Text Classification Based on KNN

YU Yue-meng, HUANG Xiao-bin

(School of Information Science and Engineering, Xiamen University, Xiamen 361005, China)

Abstract: KNN (K-Nearest Neighbor) is one of the best text classification algorithms by Vector

Support Model. However, its efficiency and accuracy rate are very low for text classification task with

high dimension and huge samples. In this paper, a new algorithm is introduced to improve the