基于改進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.