摘 要： 介绍了中心向量算法和KNN算法两种分类方法。针对KNN分类方法在计算文本相似度时存在的不足，提出了改进方案。新方案引入了中心向量分类法的思想。通过实验,对改进的KNN算法、中心向量算法和传统的KNN算法应用于文本分类效果进行了比较。实验结果表明，改进的KNN算法较中心向量法和传统的KNN算法在处理中文文本分类问题上有较好的分类效果，验证了对KNN算法改进的有效性和可行性。
关键词： 文本分类；中心向量法；KNN；相似度
由于互联网上可用的文本信息的迅速增长，在信息搜集中，常会有急需查找和组织相关的信息来获得所需要的文本知识，因此文本自动分类技术就变得越来越重要，同时，提高文本自动分类的整体效果也成了一种新的挑战。目前常用的文本分类算法有朴素贝叶斯（Native Bayes）[1]、K近邻算法KNN(K Nearest Neighbor)[2]、支持向量机SVM(Support Vector Machine)[3]等。其中K近邻分类算法是一种基于统计的分类方法，具有思路简单、易实现、无需训练过程等优点，因此得到了广泛应用。相关研究证明，K近邻算法是向量空间模型下最好的分类算法之一。
尽管如此，K近邻算法仍然存在很多不足，本文针对其中的不足之处提出了改进的方法。
1 基于近邻的分类方法
1.1 中心向量法
中心向量法[4]的基本思想是，根据属于某一类别的所有训练文本向量，计算该类别的中心向量，在进行分类时，计算待分类文本向量与每个类别中心向量的相似度，然后将其归入与之相似度最大的那个类别。该方法也可以看成是K近邻分类方法的一种特殊情况，其有效地降低了分类时的开销。类中心向量的求法通常有三种，本文采用如下的计算方法：
将某一类别中所有的文本向量求和得到类中心向量，表示成公式为：
1.2 传统的K近邻算法
K近邻[2]分类方法是一种懒惰的、有监督的、基于实例的机器学习方法。该算法的基本思路是，先将训练文本集中的所有文本表示成向量的形式，再将这些文本向量组成文本向量集并储存起来。当待分类文本到达时，计算这篇文本与训练文本集中每一个文本的相似度，并且将计算得到的值按降序排列，找出排在最前面的K篇文本，然后根据这K篇文本所属的类别来判断待分类文本的类别。计算文本相似度的方法通常有欧氏距离、向量内积和夹角余弦三种。本文采用夹角余弦计算文本之间的相似度，公式如下：
邻算法的分类方法达到比较稳定的性能改进。进行增减操作的最大次数也是一个比较难确定的值，但是实验表明，当把增减操作最大次数设为5时，可以获得较好的分类效果。
实验数据选取中文语料库中的4个类别作为训练文本集，每类文本的篇数不等。改进的K近邻算法的分类结果如表2、表3和图1所示。
从2表可以看出，对于各个类别，使用改进的K近邻分类算法后其准确率、召回率和F1值都比使用中心向量法和传统的K近邻算法有明显的提高。从图1可以看出，如果从整体上评价测试结果，使用传统的K近邻算法的分类效果在微F1值和宏F1值都比使用中心向量算法提高近1个百分点，使用改进的K近邻算法的分类效果在微F1值和宏F1值又都比传统的K近邻算法提高近3个百分点。所以，改进的K近邻算法比中心向量算法和传统的K近邻算法有较好的分类效果。
本文提出的改进的K近邻算法，与传统的K近邻算法相比，引入了中心向量分类算法的思想，在相似度计算方面进行了改进。从实验结果可以得到，改进的K近邻分类算法的分类效果比传统的K近邻算法高出3个百分点，同时也验证了对算法改进的有效性和可行性。下一步的工作就是通过进一步学习其他的分类算法，尝试将其他的分类算法引入到K近邻分类算法中，以达到更高的分类效果。
参考文献
[1] 宫秀军，孙建平，史忠植．主动贝叶斯网络分类器[J]. 计算机研究与发展，2002，39(5)：74-79．
[2] 张 宁，贾自艳，史忠植．使用KNN算法的文本分类[J]．计算机工程，2005，31(8)：171-173．
[3] JOACHIMS T. Text categorization with support vector machines: learning with many relevant features[C]．In Proceeding of ECML-98, 10th European Conference on Machine Learning, Berlin：Springer-Ver-lag, 1998：137-142．
[4] 王新丽．中文文本分类系统的研究与实现[D]．天津大学硕士研究生论文，2007．
[5] 曹勇,吴顺祥．KNN文本分类算法中的特征选取方法研究[J]．科技信息(科技·教研)，2006(12)：26-28．
[6] 柴春梅，李翔，林祥．基于改进KNN算法实现网络媒体信息智能分类[J]．计算机技术与发展，2009，19(1)：1-4．
[7] 刘怀亮，张治国，马志辉，等．基于SVM与KNN的中文文本分类比较实证研究[J]．信息系统，2008，31(6)：941-944．(收稿日期：2011-05-27)