摘 要： 介紹了中心向量算法和KNN算法兩種分類方法。針對KNN分類方法在計算文本相似度時存在的不足，提出了改進方案。新方案引入了中心向量分類法的思想。通過實驗,對改進的KNN算法、中心向量算法和傳統的KNN算法應用于文本分類效果進行了比較。實驗結果表明，改進的KNN算法較中心向量法和傳統的KNN算法在處理中文文本分類問題上有較好的分類效果，驗證了對KNN算法改進的有效性和可行性。
關鍵詞： 文本分類；中心向量法；KNN；相似度
由于互聯網上可用的文本信息的迅速增長，在信息搜集中，常會有急需查找和組織相關的信息來獲得所需要的文本知識，因此文本自動分類技術就變得越來越重要，同時，提高文本自動分類的整體效果也成了一種新的挑戰。目前常用的文本分類算法有樸素貝葉斯（Native Bayes）[1]、K近鄰算法KNN(K Nearest Neighbor)[2]、支持向量機SVM(Support Vector Machine)[3]等。其中K近鄰分類算法是一種基于統計的分類方法，具有思路簡單、易實現、無需訓練過程等優點，因此得到了廣泛應用。相關研究證明，K近鄰算法是向量空間模型下最好的分類算法之一。
盡管如此，K近鄰算法仍然存在很多不足，本文針對其中的不足之處提出了改進的方法。
1 基于近鄰的分類方法
1.1 中心向量法
中心向量法[4]的基本思想是，根據屬于某一類別的所有訓練文本向量，計算該類別的中心向量，在進行分類時，計算待分類文本向量與每個類別中心向量的相似度，然后將其歸入與之相似度最大的那個類別。該方法也可以看成是K近鄰分類方法的一種特殊情況，其有效地降低了分類時的開銷。類中心向量的求法通常有三種，本文采用如下的計算方法：
將某一類別中所有的文本向量求和得到類中心向量，表示成公式為：
1.2 傳統的K近鄰算法
K近鄰[2]分類方法是一種懶惰的、有監督的、基于實例的機器學習方法。該算法的基本思路是，先將訓練文本集中的所有文本表示成向量的形式，再將這些文本向量組成文本向量集并儲存起來。當待分類文本到達時，計算這篇文本與訓練文本集中每一個文本的相似度，并且將計算得到的值按降序排列，找出排在最前面的K篇文本，然后根據這K篇文本所屬的類別來判斷待分類文本的類別。計算文本相似度的方法通常有歐氏距離、向量內積和夾角余弦三種。本文采用夾角余弦計算文本之間的相似度，公式如下：
鄰算法的分類方法達到比較穩定的性能改進。進行增減操作的最大次數也是一個比較難確定的值，但是實驗表明，當把增減操作最大次數設為5時，可以獲得較好的分類效果。
實驗數據選取中文語料庫中的4個類別作為訓練文本集，每類文本的篇數不等。改進的K近鄰算法的分類結果如表2、表3和圖1所示。
從2表可以看出，對于各個類別，使用改進的K近鄰分類算法后其準確率、召回率和F1值都比使用中心向量法和傳統的K近鄰算法有明顯的提高。從圖1可以看出，如果從整體上評價測試結果，使用傳統的K近鄰算法的分類效果在微F1值和宏F1值都比使用中心向量算法提高近1個百分點，使用改進的K近鄰算法的分類效果在微F1值和宏F1值又都比傳統的K近鄰算法提高近3個百分點。所以，改進的K近鄰算法比中心向量算法和傳統的K近鄰算法有較好的分類效果。
本文提出的改進的K近鄰算法，與傳統的K近鄰算法相比，引入了中心向量分類算法的思想，在相似度計算方面進行了改進。從實驗結果可以得到，改進的K近鄰分類算法的分類效果比傳統的K近鄰算法高出3個百分點，同時也驗證了對算法改進的有效性和可行性。下一步的工作就是通過進一步學習其他的分類算法，嘗試將其他的分類算法引入到K近鄰分類算法中，以達到更高的分類效果。
參考文獻
[1] 宮秀軍，孫建平，史忠植．主動貝葉斯網絡分類器[J]. 計算機研究與發展，2002，39(5)：74-79．
[2] 張 寧，賈自艷，史忠植．使用KNN算法的文本分類[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] 王新麗．中文文本分類系統的研究與實現[D]．天津大學碩士研究生論文，2007．
[5] 曹勇,吳順祥．KNN文本分類算法中的特征選取方法研究[J]．科技信息(科技·教研)，2006(12)：26-28．
[6] 柴春梅，李翔，林祥．基于改進KNN算法實現網絡媒體信息智能分類[J]．計算機技術與發展，2009，19(1)：1-4．
[7] 劉懷亮，張治國，馬志輝，等．基于SVM與KNN的中文文本分類比較實證研究[J]．信息系統，2008，31(6)：941-944．(收稿日期：2011-05-27)