摘   要： 介紹了中心向量算法和KNN算法兩種分類方法。針對(duì)KNN分類方法在計(jì)算文本相似度時(shí)存在的不足，提出了改進(jìn)方案。新方案引入了中心向量分類法的思想。通過實(shí)驗(yàn),對(duì)改進(jìn)的KNN算法、中心向量算法和傳統(tǒng)的KNN算法應(yīng)用于文本分類效果進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的KNN算法較中心向量法和傳統(tǒng)的KNN算法在處理中文文本分類問題上有較好的分類效果，驗(yàn)證了對(duì)KNN算法改進(jìn)的有效性和可行性。
關(guān)鍵詞： 文本分類；中心向量法；KNN；相似度

    由于互聯(lián)網(wǎng)上可用的文本信息的迅速增長，在信息搜集中，常會(huì)有急需查找和組織相關(guān)的信息來獲得所需要的文本知識(shí)，因此文本自動(dòng)分類技術(shù)就變得越來越重要，同時(shí)，提高文本自動(dòng)分類的整體效果也成了一種新的挑戰(zhàn)。目前常用的文本分類算法有樸素貝葉斯（Native Bayes）[1]、K近鄰算法KNN(K Nearest Neighbor)[2]、支持向量機(jī)SVM(Support Vector Machine)[3]等。其中K近鄰分類算法是一種基于統(tǒng)計(jì)的分類方法，具有思路簡單、易實(shí)現(xiàn)、無需訓(xùn)練過程等優(yōu)點(diǎn)，因此得到了廣泛應(yīng)用。相關(guān)研究證明，K近鄰算法是向量空間模型下最好的分類算法之一。
    盡管如此，K近鄰算法仍然存在很多不足，本文針對(duì)其中的不足之處提出了改進(jìn)的方法。
1 基于近鄰的分類方法
1.1 中心向量法
    中心向量法[4]的基本思想是，根據(jù)屬于某一類別的所有訓(xùn)練文本向量，計(jì)算該類別的中心向量，在進(jìn)行分類時(shí)，計(jì)算待分類文本向量與每個(gè)類別中心向量的相似度，然后將其歸入與之相似度最大的那個(gè)類別。該方法也可以看成是K近鄰分類方法的一種特殊情況，其有效地降低了分類時(shí)的開銷。類中心向量的求法通常有三種，本文采用如下的計(jì)算方法：
    將某一類別中所有的文本向量求和得到類中心向量，表示成公式為：
  
1.2 傳統(tǒng)的K近鄰算法
    K近鄰[2]分類方法是一種懶惰的、有監(jiān)督的、基于實(shí)例的機(jī)器學(xué)習(xí)方法。該算法的基本思路是，先將訓(xùn)練文本集中的所有文本表示成向量的形式，再將這些文本向量組成文本向量集并儲(chǔ)存起來。當(dāng)待分類文本到達(dá)時(shí)，計(jì)算這篇文本與訓(xùn)練文本集中每一個(gè)文本的相似度，并且將計(jì)算得到的值按降序排列，找出排在最前面的K篇文本，然后根據(jù)這K篇文本所屬的類別來判斷待分類文本的類別。計(jì)算文本相似度的方法通常有歐氏距離、向量內(nèi)積和夾角余弦三種。本文采用夾角余弦計(jì)算文本之間的相似度，公式如下：
  

鄰算法的分類方法達(dá)到比較穩(wěn)定的性能改進(jìn)。進(jìn)行增減操作的最大次數(shù)也是一個(gè)比較難確定的值，但是實(shí)驗(yàn)表明，當(dāng)把增減操作最大次數(shù)設(shè)為5時(shí)，可以獲得較好的分類效果。
    實(shí)驗(yàn)數(shù)據(jù)選取中文語料庫中的4個(gè)類別作為訓(xùn)練文本集，每類文本的篇數(shù)不等。改進(jìn)的K近鄰算法的分類結(jié)果如表2、表3和圖1所示。

    從2表可以看出，對(duì)于各個(gè)類別，使用改進(jìn)的K近鄰分類算法后其準(zhǔn)確率、召回率和F1值都比使用中心向量法和傳統(tǒng)的K近鄰算法有明顯的提高。從圖1可以看出，如果從整體上評(píng)價(jià)測試結(jié)果，使用傳統(tǒng)的K近鄰算法的分類效果在微F1值和宏F1值都比使用中心向量算法提高近1個(gè)百分點(diǎn)，使用改進(jìn)的K近鄰算法的分類效果在微F1值和宏F1值又都比傳統(tǒng)的K近鄰算法提高近3個(gè)百分點(diǎn)。所以，改進(jìn)的K近鄰算法比中心向量算法和傳統(tǒng)的K近鄰算法有較好的分類效果。
    本文提出的改進(jìn)的K近鄰算法，與傳統(tǒng)的K近鄰算法相比，引入了中心向量分類算法的思想，在相似度計(jì)算方面進(jìn)行了改進(jìn)。從實(shí)驗(yàn)結(jié)果可以得到，改進(jìn)的K近鄰分類算法的分類效果比傳統(tǒng)的K近鄰算法高出3個(gè)百分點(diǎn)，同時(shí)也驗(yàn)證了對(duì)算法改進(jìn)的有效性和可行性。下一步的工作就是通過進(jìn)一步學(xué)習(xí)其他的分類算法，嘗試將其他的分類算法引入到K近鄰分類算法中，以達(dá)到更高的分類效果。
參考文獻(xiàn)
[1] 宮秀軍，孫建平，史忠植．主動(dòng)貝葉斯網(wǎng)絡(luò)分類器[J]. 計(jì)算機(jī)研究與發(fā)展，2002，39(5)：74-79．
[2] 張 寧，賈自艷，史忠植．使用KNN算法的文本分類[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 of  ECML-98, 10th European Conference on Machine Learning, Berlin：Springer-Ver-lag, 1998：137-142．
[4] 王新麗．中文文本分類系統(tǒng)的研究與實(shí)現(xiàn)[D]．天津大學(xué)碩士研究生論文，2007．
[5] 曹勇,吳順祥．KNN文本分類算法中的特征選取方法研究[J]．科技信息(科技·教研)，2006(12)：26-28．
[6] 柴春梅，李翔，林祥．基于改進(jìn)KNN算法實(shí)現(xiàn)網(wǎng)絡(luò)媒體信息智能分類[J]．計(jì)算機(jī)技術(shù)與發(fā)展，2009，19(1)：1-4．
[7] 劉懷亮，張治國，馬志輝，等．基于SVM與KNN的中文文本分類比較實(shí)證研究[J]．信息系統(tǒng)，2008，31(6)：941-944．(收稿日期：2011-05-27)