一種基于改進型KNN算法的文本分類方法

錢 強， 龐林斌， 高 尚

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

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

1 傳統(tǒng)KNN算法

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

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

KNN算法在所有的機器學習算法中比較簡單被分配的對象被列為其鄰域對象類別較多的分類的K近鄰算法是最常見的(K是一個正整數,通常很小).如果K=1,那么對象被簡單分配給其近鄰的類.

KNN算法描述如下:

目標:分類未知類別案例.

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

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

步驟:

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

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

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

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

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

(1)

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

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

2 改進型的KNN算法

針對KNN算法在分類階段計算復雜度大,耗時長的缺點,文中提出一種改進型的KNN算法,主要的思想是通過改進待分類文本的近鄰點的查找策略,從而提高KNN算法的運行效率,降低其算法復雜度.

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

圖1 通過搜索選擇最近鄰點Fig. 1 Select the nearest neighbor points through searching

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

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

圖2 錯誤的分類結果Fig. 2 Error classification results

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

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

表1 訓練集中的文本表示Table 1 Text representation for the training set

算法:改進的KNN算法

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

輸出:d所屬類別Cd.

步驟:

1)對訓練集中的各個類，計算出其類別中心dc1,dc2,…,dcM;并進行訓練集文本的初始化工作;

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

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

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

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

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

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

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

3 實驗結果

一般在信息檢索領域,準確率和召回率被認為是一對相互制約的指標,考慮到準確率和召回率并不具有相互獨立性且一般呈互逆相關關系,所以更多時候將這兩個指標綜合考慮.一個融合了準確率和召回率的指標是F值,它是準確率和召回率的調和平均值[5].在文中的分類評價標準中,也采用這3個指標來衡量.

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

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

在實驗中分別采用傳統(tǒng)的KNN算法和改進型的KNN算法對數據源做了以下對比實驗.首先針對不同K值,對分類效果做了對比,其實驗目的是為了找出最優(yōu)的參數K值,實驗結果如表2;其次,取K值為9,對傳統(tǒng)的KNN算法以及文本提出的改進的KNN算法做了對比實驗,實驗結果如表3;最后,在K的不同取值,對兩種算法在時間消耗做了對比實驗,實驗結果如表4.

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

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

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

通過該組對比實驗可以發(fā)現(xiàn),在分類F1值性能上,文中提出的改進型KNN算法要比傳統(tǒng)的KNN算法略差,這主要是因為文中提出的算法,在查找距測試向量最近的K個向量時,可能會有遺漏某些向量.但是可以看出兩種算法在此性能上的差別很小,這是因為在分類策略上,兩者完全一致.在實際應用中,精度性能上的細微差別可以忽略.

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

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

4 結論

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

[1] 蘇金樹,張博鋒,徐昕.基于機器學習的文本分類技術研究進展[J].軟件學報,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的中文文本自動分類研究[J].情報科學,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] 王愛平,徐曉燕,國瑋瑋,等.基于改進KNN算法的中文文本分類方法[J].微型機與應用,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. 信息檢索導論[M]. 王斌，譯.北京:人民郵電出版社,2010:187-188.

[6] 劉應東,牛惠民.基于k-最近鄰圖的小樣本KNN分類算法[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].計算機工程與應用.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)