錢 強(qiáng)， 龐林斌， 高 尚

(江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003)

隨著Internet及其相關(guān)技術(shù)的飛速發(fā)展,互聯(lián)網(wǎng)上出現(xiàn)了海量而龐雜的Web信息資源.如何從這些海量的非結(jié)構(gòu)數(shù)據(jù)中提取和產(chǎn)生知識(shí),找到人們感興趣的內(nèi)容,已經(jīng)成為當(dāng)前迫切需要解決的重要問(wèn)題.中文文本分類技術(shù)作為解決這一問(wèn)題的關(guān)鍵技術(shù)之一,日益成為研究的熱點(diǎn).其在搜索引擎、信息推送、信息過(guò)濾和自動(dòng)問(wèn)答等領(lǐng)域得到了越來(lái)越廣泛應(yīng)用[1].目前主流的文本分類算法有向量距離分類算法、樸素貝葉斯分類算法(NB)、K近鄰分類算法(KNN)和支持向量機(jī)分類算法(SVM)等.其中KNN算法因?yàn)榫哂袑?shí)現(xiàn)簡(jiǎn)單、無(wú)訓(xùn)練過(guò)程及較高的精度性能等優(yōu)點(diǎn),得到了廣泛應(yīng)用.但是KNN算法在實(shí)際應(yīng)用過(guò)程中依然有一些不足之處,文中針對(duì)KNN算法的一些缺點(diǎn)提出相應(yīng)的改進(jìn)措施.

1 傳統(tǒng)KNN算法

在模式識(shí)別領(lǐng)域中,KNN算法(最K近鄰算法)是將特征空間中最接近的訓(xùn)練樣本進(jìn)行分類的方法.其中1NN算法(即最近鄰算法)是最小距離分類算法的一種極端的情況,以全部訓(xùn)練樣本作為代表點(diǎn),計(jì)算測(cè)試樣本與所有樣本的距離,并以最近鄰者的類別作為決策.

最初的近鄰法是由Cover和Hart于1968年提出的[2],隨后得到理論上的深入分析與研究,是非參數(shù)法中最重要的方法之一.KNN算法本質(zhì)上是一種基于監(jiān)督的實(shí)例學(xué)習(xí)的機(jī)器學(xué)習(xí)方法.在目前的主流分類算法中,KNN算法是比較適合在文本分類這一領(lǐng)域應(yīng)用的.

KNN算法在所有的機(jī)器學(xué)習(xí)算法中比較簡(jiǎn)單被分配的對(duì)象被列為其鄰域?qū)ο箢悇e較多的分類的K近鄰算法是最常見的(K是一個(gè)正整數(shù),通常很小).如果K=1,那么對(duì)象被簡(jiǎn)單分配給其近鄰的類.

KNN算法描述如下:

目標(biāo):分類未知類別案例.

輸入:待分類的未知類別文本d.已知類別的文本集合D,其中包含M個(gè)已知的文本類別.

輸出:文本d可能的類別.

步驟:

1)依式(1)計(jì)算新文本d與訓(xùn)練集中的所有文本d1,d2,…,dn之間的相似度.得到SIM(d,d1),SIM(d,d2),…,SIM(d,dn).

2)將SIM(d,d1),SIM(d,d2),…,SIM (d,dn)進(jìn)行排序,若是超過(guò)相似度閾值t，則放入近鄰文本集合NN.

3)自近鄰文本集合NN中取出前K名,按照類別多數(shù)判決,從而決定新文本d的所屬類別.

KNN算法中文本樣本之間的相似度計(jì)算方法一般如式(1)所示:

SIM(di,dj)=cos(di,dj)=

(1)

式中：di表示文本i所對(duì)應(yīng)的特征向量;dj表示文本j所對(duì)應(yīng)的特征向量;wki表示文本i的特征向量的第k維特征的特征值(權(quán)重);wkj表示文本j的特征向量的第k維特征的特征值(權(quán)重)[3].

通過(guò)對(duì)KNN算法的分析,可以知道該分類算法的優(yōu)點(diǎn)主要有:首先，思路簡(jiǎn)單,實(shí)現(xiàn)容易;其次，當(dāng)向訓(xùn)練樣本集中加入新的文本時(shí),不需要重新訓(xùn)練.但在KNN算法擁有上述優(yōu)點(diǎn)的同時(shí),也存在著一些不足的情況[4],比如:待分類文本類別是根據(jù)選出的K篇文本來(lái)確定的,所以對(duì)K值的選取將會(huì)影響分類的效果,但是目前只能通過(guò)不斷的實(shí)驗(yàn)來(lái)調(diào)整K的取值,無(wú)法獲取一個(gè)通用的K值參數(shù);另外KNN算法的一個(gè)顯著缺點(diǎn)是其計(jì)算復(fù)雜度高,對(duì)待分類文本進(jìn)行分類時(shí)需要計(jì)算訓(xùn)練集中的所有樣本到該文本的距離,從中排序選取前K個(gè)文本來(lái)決定文本類別.這樣的話,無(wú)論是計(jì)算文本間距離所用的時(shí)間,還是訓(xùn)練集中樣本存儲(chǔ)的空間,都會(huì)隨著訓(xùn)練集規(guī)模的變大和文本特征維數(shù)的增加而線性增加,其時(shí)間復(fù)雜度可以用O(m*n)來(lái)表示.其中,m是選出的特征項(xiàng)的個(gè)數(shù),n是訓(xùn)練集中文本的個(gè)數(shù).當(dāng)分類模型的訓(xùn)練集規(guī)模比較大時(shí),KNN算法的時(shí)間消耗也非常大.這大大限制了該算法的實(shí)際應(yīng)用效果.

2 改進(jìn)型的KNN算法

針對(duì)KNN算法在分類階段計(jì)算復(fù)雜度大,耗時(shí)長(zhǎng)的缺點(diǎn),文中提出一種改進(jìn)型的KNN算法,主要的思想是通過(guò)改進(jìn)待分類文本的近鄰點(diǎn)的查找策略,從而提高KNN算法的運(yùn)行效率,降低其算法復(fù)雜度.

該算法的主要思想如下：首先計(jì)算出訓(xùn)練集中兩兩向量之間的距離；然后對(duì)這些距離進(jìn)行比較排序,針對(duì)每一個(gè)訓(xùn)練向量,設(shè)計(jì)一種獨(dú)特的數(shù)據(jù)結(jié)構(gòu)形式,在其中存儲(chǔ)了到該向量距離最短的前K個(gè)向量的集合和其他一些信息.以上為本算法的訓(xùn)練階段.在分類階段中,對(duì)于新到的待分類的測(cè)試向量,在訓(xùn)練集中隨機(jī)性的找出一個(gè)訓(xùn)練向量,計(jì)算出該向量以及在其數(shù)據(jù)結(jié)構(gòu)中離該向量距離最短的K個(gè)向量(共計(jì)K+1個(gè)向量)到待分類向量的距離.比較排序后找出到待分類向量距離最短的向量.再以此向量為基點(diǎn),計(jì)算出該向量以及在其數(shù)據(jù)結(jié)構(gòu)中離該向量距離最短的K個(gè)向量(共計(jì)K+1個(gè)向量)到測(cè)試向量的距離.如果是已經(jīng)計(jì)算過(guò)距離的向量,則不做第2次計(jì)算.迭代此過(guò)程,一直找到距離測(cè)試向量的距離最短的前K個(gè)向量.再按照傳統(tǒng)的KNN算法,計(jì)算出待分類的測(cè)試向量的所屬類別.圖1中顯示了上述思想.

圖1 通過(guò)搜索選擇最近鄰點(diǎn)Fig. 1 Select the nearest neighbor points through searching

在圖1中,對(duì)于新到的待分類的測(cè)試向量,隨機(jī)性的找出某訓(xùn)練向量,記為p1.按照前面討論的方法,可以依次遞歸的找出p2,p3,…,pn向量.如果以K=3記,可以在pn向量的附近找出距測(cè)試向量最近鄰的3個(gè)點(diǎn).然后按照傳統(tǒng)KNN算法的流程計(jì)算出待分類向量所屬的類別.

在上面的算法中,可以看出由于改進(jìn)了查找最近鄰點(diǎn)的搜索策略,算法的計(jì)算復(fù)雜度將會(huì)大大降低,有很多明顯對(duì)最終分類不起作用的向量將不會(huì)參與計(jì)算.但是也可能會(huì)出現(xiàn)一些問(wèn)題,這主要是由最初隨機(jī)查找初始向量的位置所帶來(lái)的.如圖2,如果一開始的隨機(jī)向量被定為p1,那么最終迭代出離測(cè)試點(diǎn)距離最近的向量為p3.如果按照這樣的方式計(jì)算,那么原本屬于類別2的待分類向量則將會(huì)被錯(cuò)誤的劃分到類別1.另外該算法還可能出現(xiàn)的問(wèn)題是,在本算法的查找過(guò)程中,由于搜索路徑具有明顯的方向性.這樣,某些向量可能離最終的待分類向量更近,但是因?yàn)槠洳辉谒阉髀窂缴?而沒(méi)有參與最終的計(jì)算,從而造成了測(cè)試向量的分類錯(cuò)誤.

圖2 錯(cuò)誤的分類結(jié)果Fig. 2 Error classification results

對(duì)開始的初始化向量的定位方式做出改進(jìn),主要是利用了基于距離向量的算法思想.改進(jìn)的方法如下:首先在樣本的訓(xùn)練階段，找出各個(gè)類別的中心向量，并對(duì)該中心向量也找出離其距離最近的K個(gè)訓(xùn)練樣本(即將該中心向量也作為訓(xùn)練集的樣本之一).這樣,對(duì)于新到的待分類測(cè)試向量,首先以M個(gè)各類別的中心向量為初始化向量,然后以這些向量為起點(diǎn)分別作迭代.在迭代的計(jì)算過(guò)程中,對(duì)已經(jīng)計(jì)算過(guò)的訓(xùn)練樣本向量做出標(biāo)記,以減少重復(fù)計(jì)算,或者直接在該向量的數(shù)據(jù)結(jié)構(gòu)中記錄其距測(cè)試向量的距離,直至最終找出距離待分類向量最近的K個(gè)向量,再按照傳統(tǒng)的KNN算法來(lái)計(jì)算測(cè)試向量的所屬類別.

基于這一改進(jìn)思想,為了算法實(shí)現(xiàn)方便,對(duì)于訓(xùn)練集中的每個(gè)文本向量的表示設(shè)計(jì)了一種特殊的數(shù)據(jù)結(jié)構(gòu),其形式如表1.基于如表1中的數(shù)據(jù)結(jié)構(gòu),對(duì)該改進(jìn)的KNN算法的算法步驟整理描述如下:

表1 訓(xùn)練集中的文本表示Table 1 Text representation for the training set

算法:改進(jìn)的KNN算法

輸入:訓(xùn)練文本集D={d1,d2,…,d|D|},屬于類別集C={c1,c2,…,cM},K值,閾值T,待分類的測(cè)試文本d.

輸出:d所屬類別Cd.

步驟:

1)對(duì)訓(xùn)練集中的各個(gè)類，計(jì)算出其類別中心dc1,dc2,…,dcM;并進(jìn)行訓(xùn)練集文本的初始化工作;

2)對(duì)訓(xùn)練集D中的每個(gè)文本di(包括類別中心dc1,dc2,…,dcM,計(jì)算其文本表示的數(shù)據(jù)結(jié)構(gòu).在訓(xùn)練集D中,計(jì)算出每一個(gè)文本到di的距離值,如果該值大于閾值T,則直接丟棄,如果該值小于T則予以保留;對(duì)計(jì)算出的所有距離進(jìn)行排序,找出最小的K個(gè)距離所對(duì)應(yīng)的文本,將這些文本寫入di對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)的NearestNeighbors屬性中.此為本算法的訓(xùn)練階段;

3)對(duì)于新到的待分類的測(cè)試文本d,首先以c1類的類別中心文本dc1為基點(diǎn),從dc1的NearestNeighbors屬性中找出距離其最近的K個(gè)文本集合.計(jì)算出這些文本與待分類文本d的距離，并填入這些文本結(jié)構(gòu)各自的Distance屬性中.然后根據(jù)該屬性,在這K+1個(gè)文本(dc1和距離它最近的K個(gè)文本)中找出距離待分類文本最近的新基點(diǎn)dn;

4)如果新基點(diǎn)dn就是c1類的類別中心文本dc1，則直接轉(zhuǎn)入步驟7);

5)從dn的NearestNeighbors屬性中找出距離其最近的K個(gè)文本集合.查看集合中每個(gè)文本的Distance屬性,如果某個(gè)文本的該屬性值為0,則計(jì)算出此文本至d的距離.從這K+1個(gè)文本中找出距離待分類文本距離最近的新基點(diǎn)dn+1;

6)如果dn+1不等于dn,則令dn為dn+1,并轉(zhuǎn)入步驟5);

7)記錄dn+1及距離其最近的K個(gè)向量,記為組G1;

8)對(duì)于其余的分類c2,c3,…,cM，重復(fù)步驟3)～7).對(duì)于組G1,G2,…,GM中的文本，按照傳統(tǒng)的KNN算法進(jìn)行分類,以計(jì)算出待分類文本d的所屬類別Cd.

3 實(shí)驗(yàn)結(jié)果

一般在信息檢索領(lǐng)域,準(zhǔn)確率和召回率被認(rèn)為是一對(duì)相互制約的指標(biāo),考慮到準(zhǔn)確率和召回率并不具有相互獨(dú)立性且一般呈互逆相關(guān)關(guān)系,所以更多時(shí)候?qū)⑦@兩個(gè)指標(biāo)綜合考慮.一個(gè)融合了準(zhǔn)確率和召回率的指標(biāo)是F值,它是準(zhǔn)確率和召回率的調(diào)和平均值[5].在文中的分類評(píng)價(jià)標(biāo)準(zhǔn)中,也采用這3個(gè)指標(biāo)來(lái)衡量.

文中實(shí)驗(yàn)所采用的操作系統(tǒng)是Windows XP.CPU是Pentium(R) Dual-Core T440 @2.2 GHz.內(nèi)存大小為2 GB.實(shí)驗(yàn)采用的開發(fā)工具是Microsoft Visual Studio 2008.開發(fā)語(yǔ)言是C++.實(shí)驗(yàn)中用到的其他開發(fā)工具包括中科院計(jì)算技術(shù)研究所的中文分詞系統(tǒng)ICTCLAS以及開源庫(kù)Boost C++.

文本實(shí)驗(yàn)所采用的語(yǔ)料庫(kù)主要來(lái)自于搜狗語(yǔ)料庫(kù),其下載地址為http://www.sogou.com/labs/dl/t.html.在實(shí)驗(yàn)過(guò)程中將文本分為歷史、教育、文化、軍事、社會(huì)法律、娛樂(lè)和IT 7類,采用了語(yǔ)料庫(kù)中的350篇文本作為訓(xùn)練集(每個(gè)類別采用了50篇文本).剩下的文本作為測(cè)試集.

在實(shí)驗(yàn)中分別采用傳統(tǒng)的KNN算法和改進(jìn)型的KNN算法對(duì)數(shù)據(jù)源做了以下對(duì)比實(shí)驗(yàn).首先針對(duì)不同K值,對(duì)分類效果做了對(duì)比,其實(shí)驗(yàn)?zāi)康氖菫榱苏页鲎顑?yōu)的參數(shù)K值,實(shí)驗(yàn)結(jié)果如表2;其次,取K值為9,對(duì)傳統(tǒng)的KNN算法以及文本提出的改進(jìn)的KNN算法做了對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如表3;最后,在K的不同取值,對(duì)兩種算法在時(shí)間消耗做了對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如表4.

表2 不同K值的分類效果對(duì)比Table 2 Contrast results of different K value

通過(guò)該組對(duì)比實(shí)驗(yàn)可以看出,不同K值對(duì)于分類的各項(xiàng)性能的影響明顯不同.表2中,當(dāng)K值為9時(shí),無(wú)論是在準(zhǔn)確率還是召回率上,兩種算法的實(shí)驗(yàn)性能都可以到達(dá)一個(gè)頂點(diǎn).這里值得注意的一點(diǎn)是,同樣是針對(duì)中文文本及網(wǎng)頁(yè)分類,不同的研究者在不同的數(shù)據(jù)源上實(shí)驗(yàn)得出的最優(yōu)K值均有差異[6-7].體現(xiàn)出了KNN算法很難給出一個(gè)通用的最優(yōu)K值,需要根據(jù)實(shí)驗(yàn)不斷地調(diào)整.這在一定程度上限制了KNN算法的應(yīng)用.

表3 傳統(tǒng)KNN算法和改進(jìn)型KNN算法的性能比較Table 3 Performance comparison of traditional KNN algorithm and improved KNN algorithm

通過(guò)該組對(duì)比實(shí)驗(yàn)可以發(fā)現(xiàn),在分類F1值性能上,文中提出的改進(jìn)型KNN算法要比傳統(tǒng)的KNN算法略差,這主要是因?yàn)槲闹刑岢龅乃惴?在查找距測(cè)試向量最近的K個(gè)向量時(shí),可能會(huì)有遺漏某些向量.但是可以看出兩種算法在此性能上的差別很小,這是因?yàn)樵诜诸惒呗陨?兩者完全一致.在實(shí)際應(yīng)用中,精度性能上的細(xì)微差別可以忽略.

表4 傳統(tǒng)KNN算法和改進(jìn)型KNN算法的時(shí)間消耗比較Table 4 Time consuming comparison of traditional KNN algorithm and improved KNN algorithm

通過(guò)該組對(duì)比試驗(yàn),可以發(fā)現(xiàn),在K的各種取值下,文中所提出的改進(jìn)型KNN算法在時(shí)間開銷上都具有明顯的優(yōu)勢(shì).這也說(shuō)明了該算法是行之有效的，可以較好地解決傳統(tǒng)KNN算法在計(jì)算時(shí),時(shí)間消耗大的問(wèn)題.當(dāng)然,取得這一優(yōu)點(diǎn)的代價(jià)是改進(jìn)型的KNN算法需要在訓(xùn)練階段消耗時(shí)間,這一時(shí)間消耗是明顯要高于傳統(tǒng)KNN算法的.

4 結(jié)論

文中提出的改進(jìn)型的KNN算法在計(jì)算復(fù)雜度上由于改進(jìn)了對(duì)近鄰點(diǎn)的搜索策略,能明顯地優(yōu)于傳統(tǒng)的KNN算法，具有一定的理論意義和實(shí)際應(yīng)用價(jià)值.同時(shí)在對(duì)于初始點(diǎn)的選取上是選取了各個(gè)類別的中心,相比于傳統(tǒng)的KNN算法,更適合采用并行計(jì)算結(jié)構(gòu).這也是下一步需要考慮的研究工作.

[1] 蘇金樹,張博鋒,徐昕.基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J].軟件學(xué)報(bào),2006,17(9):1848-1859.

Su Jinshu,Zhang Bofeng,Xu Xin.Advances in machine learning based text categorization[J].JournalofSoftware,2006,17(9):1848-1859.(in Chinese)

[2] Cover T M, Hart P E. Nearest neighbor pattern classification[J].IEEETransactionsonInformationTheory,1967, 13(1): 21-27.

[3] 張野,楊建林.基于KNN和SVM的中文文本自動(dòng)分類研究[J].情報(bào)科學(xué),2011,29(9):1313-1317.

Zhang Ye,Yang Jianlin.Research on automatic classification for Chinese text based on KNN and SVM[J].InformationScience, 2011,29(9):1313-1317.(in Chinese)

[4] 王愛平,徐曉燕,國(guó)瑋瑋,等.基于改進(jìn)KNN算法的中文文本分類方法[J].微型機(jī)與應(yīng)用,2011,30(18):8-10.

Wang Aiping, Xu Xiaoyan, Guo Weiwei,et al.Text categorization method based on improved KNN algorithm[J].Microcomputer&ItsApplications,2011,30(18):8-10. (in Chinese)

[5] Manning C D. 信息檢索導(dǎo)論[M]. 王斌，譯.北京:人民郵電出版社,2010:187-188.

[6] 劉應(yīng)東,?；菝?基于k-最近鄰圖的小樣本KNN分類算法[J].計(jì)算機(jī)工程.2011,37(9):199-200.

Liu Yingdong,Niu Huimin.KNN classification algorithm based on k-nearest neighbor graph for small sample[J].ComputerEngineering,2011,37(9):199-200. (in Chinese)

[7] 魯婷,王浩,姚宏亮.一種基于中心文檔的KNN中文文本分類算法[J].計(jì)算機(jī)工程與應(yīng)用.2011,47(2):127-130.

Lu Ting,Wang Hao,Yao Hongliang.K-nearest neighbor Chinese text categorization algorithm based on center documents[J].ComputerEngineeringandApplication,2011,47(2):127-130. (in Chinese)