王愛(ài)平，徐曉艷，國(guó)瑋瑋，李仿華

（安徽大學(xué) 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230039）

由于互聯(lián)網(wǎng)上可用的文本信息的迅速增長(zhǎng)，在信息搜集中，常會(huì)有急需查找和組織相關(guān)的信息來(lái)獲得所需要的文本知識(shí)，因此文本自動(dòng)分類(lèi)技術(shù)就變得越來(lái)越重要，同時(shí)，提高文本自動(dòng)分類(lèi)的整體效果也成了一種新的挑戰(zhàn)。目前常用的文本分類(lèi)算法有樸素貝葉斯（Native Bayes）[1]、K 近 鄰 算 法 KNN(K Nearest Neighbor)[2]、支持向量機(jī)SVM(Support Vector Machine)[3]等。其中K近鄰分類(lèi)算法是一種基于統(tǒng)計(jì)的分類(lèi)方法，具有思路簡(jiǎn)單、易實(shí)現(xiàn)、無(wú)需訓(xùn)練過(guò)程等優(yōu)點(diǎn)，因此得到了廣泛應(yīng)用。相關(guān)研究證明，K近鄰算法是向量空間模型下最好的分類(lèi)算法之一。

盡管如此，K近鄰算法仍然存在很多不足，本文針對(duì)其中的不足之處提出了改進(jìn)的方法。

1 基于近鄰的分類(lèi)方法

1.1 中心向量法

中心向量法[4]的基本思想是，根據(jù)屬于某一類(lèi)別的所有訓(xùn)練文本向量，計(jì)算該類(lèi)別的中心向量，在進(jìn)行分類(lèi)時(shí)，計(jì)算待分類(lèi)文本向量與每個(gè)類(lèi)別中心向量的相似度，然后將其歸入與之相似度最大的那個(gè)類(lèi)別。該方法也可以看成是K近鄰分類(lèi)方法的一種特殊情況，其有效地降低了分類(lèi)時(shí)的開(kāi)銷(xiāo)。類(lèi)中心向量的求法通常有三種，本文采用如下的計(jì)算方法：

將某一類(lèi)別中所有的文本向量求和得到類(lèi)中心向量，表示成公式為：

其中，n表示類(lèi)i中的文本個(gè)數(shù)，dik表示類(lèi)i中的第k篇文本。

1.2 傳統(tǒng)的K近鄰算法

K近鄰[2]分類(lèi)方法是一種懶惰的、有監(jiān)督的、基于實(shí)例的機(jī)器學(xué)習(xí)方法。該算法的基本思路是，先將訓(xùn)練文本集中的所有文本表示成向量的形式，再將這些文本向量組成文本向量集并儲(chǔ)存起來(lái)。當(dāng)待分類(lèi)文本到達(dá)時(shí)，計(jì)算這篇文本與訓(xùn)練文本集中每一個(gè)文本的相似度，并且將計(jì)算得到的值按降序排列，找出排在最前面的K篇文本，然后根據(jù)這K篇文本所屬的類(lèi)別來(lái)判斷待分類(lèi)文本的類(lèi)別。計(jì)算文本相似度的方法通常有歐氏距離、向量?jī)?nèi)積和夾角余弦三種。本文采用夾角余弦計(jì)算文本之間的相似度，公式如下：

其中，W1i和 W2i分別表示文本 d1和 d2的文本向量中第 i個(gè)特征項(xiàng)的權(quán)重。求出的余弦值越大說(shuō)明兩個(gè)文本的相似度越大，兩個(gè)向量所代表的文本就越可能屬于同一個(gè)類(lèi)別，反之，兩個(gè)向量所代表的文本屬于同一個(gè)類(lèi)別的可能性就越小。依據(jù)這K篇文本將待分類(lèi)文本進(jìn)行歸類(lèi)的方法是，對(duì)這K篇文本與待分類(lèi)文本的相似度按公式(3)求和，將屬于同一個(gè)類(lèi)的文本的相似度求和，然后對(duì)每個(gè)類(lèi)所求的和進(jìn)行排序，將待分類(lèi)文本分到相似度和比較大的那個(gè)類(lèi)中。

其中，k表示選取的文本數(shù)，Tj(di)表示文本 di是否屬于Cj類(lèi)，如果屬于，則值為 1，否則值為 0；Sim(d,di)即為式(2)所求。

2 改進(jìn)的K近鄰算法

研究表明，在用相似度計(jì)算方法計(jì)算兩個(gè)文本向量之間的相似度時(shí)，并沒(méi)有考慮待分類(lèi)文本與訓(xùn)練文本所屬的類(lèi)別之間是否存在相似性，因此將所求的結(jié)果運(yùn)用到分類(lèi)中時(shí)可能會(huì)導(dǎo)致分類(lèi)結(jié)果的不準(zhǔn)確。針對(duì)這一不足，本文將中心向量分類(lèi)方法的思想引入到了相似度計(jì)算公式中,對(duì)夾角余弦相似度計(jì)算公式進(jìn)行了改進(jìn)。

2.1 改進(jìn)的相似度計(jì)算公式

首先引入權(quán)向量 Vi，Vi表示類(lèi)別 i的權(quán)向量，Vij表示權(quán)向量Vi的第j個(gè)特征值，初始化Vij為1。改進(jìn)的夾角余弦相似度計(jì)算公式和相似度求和公式如下：

2.2 針對(duì)文本在每個(gè)類(lèi)別中分布不均勻情況的處理

假如只有A、B兩種類(lèi)別，若標(biāo)記為A類(lèi)別的文本d0被歸到 B類(lèi)別中，即 TA(d0,VA)小于 TB(d0,VB)，則增大類(lèi)別A的權(quán)向量VA，減小類(lèi)別B的權(quán)向量VB,直到TA(d0,VA)小于TB(d0,VB)，經(jīng)過(guò)幾輪增減操作后，待分類(lèi)文本d0就會(huì)被正確歸類(lèi)。

上述方法克服了每個(gè)類(lèi)別中文本篇數(shù)不平均的問(wèn)題。如果類(lèi)別A是一個(gè)包括較多篇數(shù)文本的類(lèi)別，類(lèi)別B是一個(gè)包括較少篇數(shù)文本的類(lèi)別，根據(jù)傳統(tǒng)的K近鄰分類(lèi)算法，類(lèi)別B中的樣本有可能被歸到類(lèi)別A中，則對(duì)類(lèi)別B的權(quán)向量進(jìn)行的增加操作的次數(shù)就會(huì)比類(lèi)別A的權(quán)向量的多。經(jīng)過(guò)幾輪增減操作后，含有較少篇數(shù)文本的類(lèi)別B就可能有較大的權(quán)向量VB。因此，引入權(quán)向量可以克服文本在每個(gè)類(lèi)別中分布不均勻的問(wèn)題。

2.3 相似度計(jì)算方法的改進(jìn)策略

首先，引入兩個(gè)向量，類(lèi)別i不可變的中心向量Ciu和可變的中心向量Cia，Ciu的計(jì)算公式如式 (1)，初始化Cia為Ciu， 即Cija,0=Ciju， 其中Ciju表示向量Ciu的第j個(gè)特征值，Cija,0表示向量Cia的第j個(gè)特征值，上標(biāo)中的0表示此次正在進(jìn)行的增減操作，由此可得Vij0=1。在每次增減操作后，都必須對(duì)訓(xùn)練文本集中的所有文本進(jìn)行分類(lèi)，如果標(biāo)記為類(lèi)別A的文本d0被歸到B類(lèi)別，就用如下公式來(lái)調(diào)整 CAa,0、CBa,0、VA0和 VB0：

其中，式(6)和式(7)是進(jìn)行增加操作的公式，式(8)和式(9)是進(jìn)行減少操作的公式，increase_weight和reduce_weight是每次進(jìn)行增減操作的權(quán)值。

3 性能評(píng)價(jià)方法

分類(lèi)的準(zhǔn)確度和速度是評(píng)價(jià)一種文本分類(lèi)算法的標(biāo)準(zhǔn)。其中，分類(lèi)速度取決于分類(lèi)規(guī)則的復(fù)雜程度，而分類(lèi)的準(zhǔn)確度主要是參照通過(guò)專(zhuān)家思考判斷后對(duì)文本的分類(lèi)結(jié)果與人工分類(lèi)結(jié)果的相近程度，越相近其分類(lèi)的準(zhǔn)確程度就越高，這里包含了評(píng)價(jià)文本分類(lèi)算法的兩個(gè)指標(biāo)：準(zhǔn)確率(Precision)和召回率(Recall)[5]。由于準(zhǔn)確率和召回率分別表示分類(lèi)效果的兩個(gè)不同方面，因此通常使用F1測(cè)試值統(tǒng)籌評(píng)估分類(lèi)結(jié)果[6]。另外有微平均和宏平均兩種計(jì)算準(zhǔn)確率、召回率和 F1值的方法[7]。在計(jì)算分類(lèi)的各個(gè)評(píng)價(jià)指標(biāo)時(shí)，先建立如表1所示的二值分類(lèi)列聯(lián)表。

可用如下的公式計(jì)算準(zhǔn)確率(Precision)、召回率(Recall)、F1值、宏 F1值(MacroF1)和微 F1值(MicroF1)：

表1 二值分類(lèi)列聯(lián)表

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

4 實(shí)驗(yàn)與結(jié)果分析

在實(shí)驗(yàn)中，增減操作的權(quán)值用來(lái)控制每次增減操作的步長(zhǎng)，它會(huì)影響實(shí)驗(yàn)的結(jié)果，當(dāng)把增減操作的權(quán)值都設(shè)為1.0時(shí)，進(jìn)行增減操作可以使基于K近鄰算法的分類(lèi)方法達(dá)到比較穩(wěn)定的性能改進(jìn)。進(jìn)行增減操作的最大次數(shù)也是一個(gè)比較難確定的值，但是實(shí)驗(yàn)表明，當(dāng)把增減操作最大次數(shù)設(shè)為5時(shí)，可以獲得較好的分類(lèi)效果。

實(shí)驗(yàn)數(shù)據(jù)選取中文語(yǔ)料庫(kù)中的4個(gè)類(lèi)別作為訓(xùn)練文本集，每類(lèi)文本的篇數(shù)不等。改進(jìn)的K近鄰算法的分類(lèi)結(jié)果如表2、表3和圖1所示。

從2表可以看出，對(duì)于各個(gè)類(lèi)別，使用改進(jìn)的K近鄰分類(lèi)算法后其準(zhǔn)確率、召回率和F1值都比使用中心向量法和傳統(tǒng)的K近鄰算法有明顯的提高。從圖1可以看出，如果從整體上評(píng)價(jià)測(cè)試結(jié)果，使用傳統(tǒng)的K近鄰算法的分類(lèi)效果在微F1值和宏F1值都比使用中心向量算法提高近1個(gè)百分點(diǎn)，使用改進(jìn)的K近鄰算法的分類(lèi)效果在微F1值和宏F1值又都比傳統(tǒng)的K近鄰算法提高近3個(gè)百分點(diǎn)。所以，改進(jìn)的K近鄰算法比中心向量算法和傳統(tǒng)的K近鄰算法有較好的分類(lèi)效果。

表2 改進(jìn)的K近鄰算法在各個(gè)類(lèi)上的分類(lèi)結(jié)果

表3 該技能的K近鄰算法在整體上的測(cè)試結(jié)果

本文提出的改進(jìn)的K近鄰算法，與傳統(tǒng)的K近鄰算法相比，引入了中心向量分類(lèi)算法的思想，在相似度計(jì)算方面進(jìn)行了改進(jìn)。從實(shí)驗(yàn)結(jié)果可以得到，改進(jìn)的K近鄰分類(lèi)算法的分類(lèi)效果比傳統(tǒng)的K近鄰算法高出3個(gè)百分點(diǎn)，同時(shí)也驗(yàn)證了對(duì)算法改進(jìn)的有效性和可行性。下一步的工作就是通過(guò)進(jìn)一步學(xué)習(xí)其他的分類(lèi)算法，嘗試將其他的分類(lèi)算法引入到K近鄰分類(lèi)算法中，以達(dá)到更高的分類(lèi)效果。

[1]宮秀軍，孫建平，史忠植.主動(dòng)貝葉斯網(wǎng)絡(luò)分類(lèi)器[J].計(jì)算機(jī)研究與發(fā)展，2002，39(5)：74-79.

[2]張 寧，賈自艷，史忠植.使用KNN算法的文本分類(lèi)[J].計(jì)算機(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]王新麗.中文文本分類(lèi)系統(tǒng)的研究與實(shí)現(xiàn)[D].天津大學(xué)碩士研究生論文，2007.

[5]曹勇,吳順祥.KNN文本分類(lèi)算法中的特征選取方法研究[J].科技信息(科技·教研)，2006(12)：26-28.

[6]柴春梅，李翔，林祥.基于改進(jìn)KNN算法實(shí)現(xiàn)網(wǎng)絡(luò)媒體信息智能分類(lèi)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19(1)：1-4.

[7]劉懷亮，張治國(guó)，馬志輝，等.基于SVM與KNN的中文文本分類(lèi)比較實(shí)證研究[J].信息系統(tǒng)，2008，31(6)：941-944.