基于改进KNN算法的中文文本分类方法

王爱平，徐晓艳，国玮玮，李仿华

（安徽大学 计算智能与信号处理教育部重点实验室，安徽 合肥 230039）

由于互联网上可用的文本信息的迅速增长，在信息搜集中，常会有急需查找和组织相关的信息来获得所需要的文本知识，因此文本自动分类技术就变得越来越重要，同时，提高文本自动分类的整体效果也成了一种新的挑战。目前常用的文本分类算法有朴素贝叶斯（Native Bayes）[1]、K 近 邻 算 法 KNN(K Nearest Neighbor)[2]、支持向量机SVM(Support Vector Machine)[3]等。其中K近邻分类算法是一种基于统计的分类方法，具有思路简单、易实现、无需训练过程等优点，因此得到了广泛应用。相关研究证明，K近邻算法是向量空间模型下最好的分类算法之一。

尽管如此，K近邻算法仍然存在很多不足，本文针对其中的不足之处提出了改进的方法。

1 基于近邻的分类方法

1.1 中心向量法

中心向量法[4]的基本思想是，根据属于某一类别的所有训练文本向量，计算该类别的中心向量，在进行分类时，计算待分类文本向量与每个类别中心向量的相似度，然后将其归入与之相似度最大的那个类别。该方法也可以看成是K近邻分类方法的一种特殊情况，其有效地降低了分类时的开销。类中心向量的求法通常有三种，本文采用如下的计算方法：

将某一类别中所有的文本向量求和得到类中心向量，表示成公式为：

其中，n表示类i中的文本个数，dik表示类i中的第k篇文本。

1.2 传统的K近邻算法

K近邻[2]分类方法是一种懒惰的、有监督的、基于实例的机器学习方法。该算法的基本思路是，先将训练文本集中的所有文本表示成向量的形式，再将这些文本向量组成文本向量集并储存起来。当待分类文本到达时，计算这篇文本与训练文本集中每一个文本的相似度，并且将计算得到的值按降序排列，找出排在最前面的K篇文本，然后根据这K篇文本所属的类别来判断待分类文本的类别。计算文本相似度的方法通常有欧氏距离、向量内积和夹角余弦三种。本文采用夹角余弦计算文本之间的相似度，公式如下：

其中，W1i和 W2i分别表示文本 d1和 d2的文本向量中第 i个特征项的权重。求出的余弦值越大说明两个文本的相似度越大，两个向量所代表的文本就越可能属于同一个类别，反之，两个向量所代表的文本属于同一个类别的可能性就越小。依据这K篇文本将待分类文本进行归类的方法是，对这K篇文本与待分类文本的相似度按公式(3)求和，将属于同一个类的文本的相似度求和，然后对每个类所求的和进行排序，将待分类文本分到相似度和比较大的那个类中。

其中，k表示选取的文本数，Tj(di)表示文本 di是否属于Cj类，如果属于，则值为 1，否则值为 0；Sim(d,di)即为式(2)所求。

2 改进的K近邻算法

研究表明，在用相似度计算方法计算两个文本向量之间的相似度时，并没有考虑待分类文本与训练文本所属的类别之间是否存在相似性，因此将所求的结果运用到分类中时可能会导致分类结果的不准确。针对这一不足，本文将中心向量分类方法的思想引入到了相似度计算公式中,对夹角余弦相似度计算公式进行了改进。

2.1 改进的相似度计算公式

首先引入权向量 Vi，Vi表示类别 i的权向量，Vij表示权向量Vi的第j个特征值，初始化Vij为1。改进的夹角余弦相似度计算公式和相似度求和公式如下：

2.2 针对文本在每个类别中分布不均匀情况的处理

假如只有A、B两种类别，若标记为A类别的文本d0被归到 B类别中，即 TA(d0,VA)小于 TB(d0,VB)，则增大类别A的权向量VA，减小类别B的权向量VB,直到TA(d0,VA)小于TB(d0,VB)，经过几轮增减操作后，待分类文本d0就会被正确归类。

上述方法克服了每个类别中文本篇数不平均的问题。如果类别A是一个包括较多篇数文本的类别，类别B是一个包括较少篇数文本的类别，根据传统的K近邻分类算法，类别B中的样本有可能被归到类别A中，则对类别B的权向量进行的增加操作的次数就会比类别A的权向量的多。经过几轮增减操作后，含有较少篇数文本的类别B就可能有较大的权向量VB。因此，引入权向量可以克服文本在每个类别中分布不均匀的问题。

2.3 相似度计算方法的改进策略

首先，引入两个向量，类别i不可变的中心向量Ciu和可变的中心向量Cia，Ciu的计算公式如式 (1)，初始化Cia为Ciu， 即Cija,0=Ciju， 其中Ciju表示向量Ciu的第j个特征值，Cija,0表示向量Cia的第j个特征值，上标中的0表示此次正在进行的增减操作，由此可得Vij0=1。在每次增减操作后，都必须对训练文本集中的所有文本进行分类，如果标记为类别A的文本d0被归到B类别，就用如下公式来调整 CAa,0、CBa,0、VA0和 VB0：

其中，式(6)和式(7)是进行增加操作的公式，式(8)和式(9)是进行减少操作的公式，increase_weight和reduce_weight是每次进行增减操作的权值。

3 性能评价方法

分类的准确度和速度是评价一种文本分类算法的标准。其中，分类速度取决于分类规则的复杂程度，而分类的准确度主要是参照通过专家思考判断后对文本的分类结果与人工分类结果的相近程度，越相近其分类的准确程度就越高，这里包含了评价文本分类算法的两个指标：准确率(Precision)和召回率(Recall)[5]。由于准确率和召回率分别表示分类效果的两个不同方面，因此通常使用F1测试值统筹评估分类结果[6]。另外有微平均和宏平均两种计算准确率、召回率和 F1值的方法[7]。在计算分类的各个评价指标时，先建立如表1所示的二值分类列联表。

可用如下的公式计算准确率(Precision)、召回率(Recall)、F1值、宏 F1值(MacroF1)和微 F1值(MicroF1)：

表1 二值分类列联表

在式(10)中，如果 A+B=0，则 Precision=1，在式（11）中，如果 A+C=0，则 Recall=1。

4 实验与结果分析

在实验中，增减操作的权值用来控制每次增减操作的步长，它会影响实验的结果，当把增减操作的权值都设为1.0时，进行增减操作可以使基于K近邻算法的分类方法达到比较稳定的性能改进。进行增减操作的最大次数也是一个比较难确定的值，但是实验表明，当把增减操作最大次数设为5时，可以获得较好的分类效果。

实验数据选取中文语料库中的4个类别作为训练文本集，每类文本的篇数不等。改进的K近邻算法的分类结果如表2、表3和图1所示。

从2表可以看出，对于各个类别，使用改进的K近邻分类算法后其准确率、召回率和F1值都比使用中心向量法和传统的K近邻算法有明显的提高。从图1可以看出，如果从整体上评价测试结果，使用传统的K近邻算法的分类效果在微F1值和宏F1值都比使用中心向量算法提高近1个百分点，使用改进的K近邻算法的分类效果在微F1值和宏F1值又都比传统的K近邻算法提高近3个百分点。所以，改进的K近邻算法比中心向量算法和传统的K近邻算法有较好的分类效果。

表2 改进的K近邻算法在各个类上的分类结果

表3 该技能的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 ofECML-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.