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

    由于互聯(lián)網(wǎng)上可用的文本信息的迅速增長(zhǎng),，在信息搜集中，常會(huì)有急需查找和組織相關(guān)的信息來(lái)獲得所需要的文本知識(shí),，因此文本自動(dòng)分類技術(shù)就變得越來(lái)越重要,，同時(shí)，提高文本自動(dòng)分類的整體效果也成了一種新的挑戰(zhàn),。目前常用的文本分類算法有樸素貝葉斯（Native Bayes）[1],、K近鄰算法KNN(K Nearest Neighbor)[2]、支持向量機(jī)SVM(Support Vector Machine)[3]等,。其中K近鄰分類算法是一種基于統(tǒng)計(jì)的分類方法,，具有思路簡(jiǎn)單、易實(shí)現(xiàn),、無(wú)需訓(xùn)練過(guò)程等優(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í)的開(kāi)銷,。類中心向量的求法通常有三種,，本文采用如下的計(jì)算方法：
    將某一類別中所有的文本向量求和得到類中心向量，表示成公式為：
  
1.2 傳統(tǒng)的K近鄰算法
    K近鄰[2]分類方法是一種懶惰的,、有監(jiān)督的,、基于實(shí)例的機(jī)器學(xué)習(xí)方法。該算法的基本思路是,，先將訓(xùn)練文本集中的所有文本表示成向量的形式,，再將這些文本向量組成文本向量集并儲(chǔ)存起來(lái)。當(dāng)待分類文本到達(dá)時(shí),，計(jì)算這篇文本與訓(xùn)練文本集中每一個(gè)文本的相似度,，并且將計(jì)算得到的值按降序排列，找出排在最前面的K篇文本,，然后根據(jù)這K篇文本所屬的類別來(lái)判斷待分類文本的類別,。計(jì)算文本相似度的方法通常有歐氏距離、向量?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ù)選取中文語(yǔ)料庫(kù)中的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à)測(cè)試結(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)的有效性和可行性。下一步的工作就是通過(guò)進(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] 劉懷亮,，張治國(guó)，馬志輝,，等．基于SVM與KNN的中文文本分類比較實(shí)證研究[J]．信息系統(tǒng)，2008,，31(6)：941-944．(收稿日期：2011-05-27)