一種快速KNN文本分類算法

摘要:KNN(K-Nearest Neighbor)是向量空間模型中最好的文本分類算法之一。但是，當樣本集較大以及文本向量維數較多時，KNN算法分類的效率就會大大降低。該文提出了一種提高KNN分類效率的改進算法。算法在訓練過程中計算出各類文本的分布范圍，在分類過程中，根據待分類文本向量在樣本空間中的分布位置，縮小其K最近鄰搜索范圍。實驗表明改進的算法可以在保持KNN分類性能基本不變的情況下，顯著提高分類效率。

關鍵詞:文本分類;K-最近鄰;算法

中圖分類號:TP391文獻標識碼:A文章編號:1009-3044(2010)01-174-02

An Improved KNN Algorithm for Text Classification

SUN Rong-zong

(Department of Computer Science and Technology， Tongji University， Shanghai 201804， China)

Abstract: KNN(K-Nearest Neighbor) is one of the best text classification algorithms by Vector Support Model. However， its efficiency rate is very low for text classification task with high dimension and huge samples. In this paper， a new algorithm is introduced to improve the efficiency rate. The distribution of training samples of each class is computed in the training process. According to the position of the documents in the sample space， this algorithm can reduce the searching range of their K nearest neighbors in the classing process. The results of experiments show that this algorithm can save largely the classification time and has almost the same classification performance as that of the traditional KNN classification algorithm.

Key words: text classification; KNN; algorithm

自動文本分類是指利用計算機將待分類文本歸于預先給定的某一類或某幾類的過程，屬于有監督學習，簡稱為文本分類。隨著文本信息量的快速增長，文本分類已成為信息檢索、知識挖掘和管理等領域的關鍵技術[1]。現有的文本分類方法主要有K近鄰(KNN)、支持向量機(SVM)、決策樹、線性最小二乘法估計(LLSF)、貝葉斯分類算法(Bayes) 以及神經網絡等。其中，KNN方法在現有文本分類方法中應用得比較廣泛，它屬于基于實例的學習方法[2]，是一種非參數的分類技術，在基于統計的模式識別中非常有效，對于未知和非正態分布可以取得較高的分類準確率，具有魯棒性、概念清晰等諸多優點。

但是KNN算法是一種典型的消極學習方法(lazy learning)[3]，在訓練階段僅僅存儲所有的訓練實例，所有的計算都延遲到分類階段進行，對于高維文本向量或樣本集規模較大的情況，龐大的計算量將嚴重影響分類速度。其實，效率問題一直是阻礙KNN及其變體推廣應用的一個重要的實踐問題，針對這個問題，目前的改進辦法主要分為三類:1)對文本樣本特征空間降維。但是這種方法所能減少的計算量有限，并且有可能會影響分類的準確率。2)用提取代表樣本等方法縮小樣本庫[4]。這類方法對于小樣本庫來說，效果明顯，但對于大樣本庫，其工作量相當巨大。3)提高高維向量空間的KNN檢索效率[5]。這類方法都有一定的局限性，要么往往不可避免地遭遇“維數災難”困擾[6]，不能很好地應用于高維(超過幾十維)數據空間檢索[7];要么只是適用于近似檢索要求，不能保證較高的KNN檢索精度。

然而，以前的算法都忽略了文本向量在空間里具體的分布情況。文本向量的分布表現出某種聚集性，即同類的文本向量大部分都分布在同一區域里，而不同類的文本向量大部分會分布在不同的區域里。據此，本文提出了一種基于分布域的快速KNN分類方法。改進算法能找到并計算出每個類的分布域，參照待分類文本向量的空間位置，相對于傳統KNN，只需要少量的計算就能判斷其歸屬。實驗表明，改進算法能在基本不影響原有算法準確率的情況下，大大提高文本的分類速度，并可應用于高維文本向量或樣本集規模較大的情況。

1 基本概念

1.1 向量空間模型

向量空間模型(VSM)是近年來應用最多且效果較好的文檔表示法之一。在該模型中，文檔空間被看作是由一組正交詞條向量所組成的向量空間，每個文檔d表示為其中的一個范化特征向量V(d)=(t1，W1(d))，…ti，Wi(d)，…tn，Wn(d))，其中ti為詞條項，Wi(d)為ti在d中的權值。Wi(d)一般被定義為ti在d中出現頻率tfi(d)的函數，即Wi(d)= δ(tfi(d))。常用的δ有平方根函數，對數函數，布爾函數和TFIDF(詞頻-逆向文本頻率)函數等。TFIDF是目前最常用的一種權重函數，δ=tfi(d)log(N/ni)，其中N為所有文檔數目，ni為含有詞條ti的文檔數目，它不僅考慮了詞在單個文檔中的局部權值，還考慮到詞在整個文檔庫的全局權值，因而更合理、更準確。

2.2 基于KNN的文本分類方法

KNN最初由Cover和Hart于1968年提出，是一種理論上比較成熟的方法。該算法的基本思想是:根據傳統的向量空間模型，文本內容被形式化為特征空間中的加權特征向量。對于一各待分類文本，計算出它與樣本集中每個文本的相似度，找出K個最相似的文本，根據加權距離之和來判斷待分類文本的所屬類別。算法的具體步驟如下:

1)根據特征向量，把一個待分類文本表示成向量d。

2)計算d與樣本集S中每個文本向量的相似度(通常為歐式距離或者是余弦距離)，選擇與d相似度最大的k個樣本向量作為d的k個最近鄰。

3)計算出d屬于每個類的權重W，d屬于類Cj的權重計算公式為:

其中sim(di，d)是d的k個最近鄰中樣本di之間的相似度，而φ(di，Cj)的取值為1或者0，如果di∈Cj，則函數值為1，反之則為0。

4)比較權重，將待分類樣本d歸屬于權重最大的那個類別。

2 基于分布域的KNN文本分類方法

2.1 基本概念

為了刻畫文本向量在空間中的分布，我們引入分布域的概念:

定義1(分布域):在文本向量空間中，若存在子空間，使得類C中的文本向量全部分布于其中，那么稱滿足條件的最小子空間為C的分布域。

2.2 改進的KNN算法

改進算法的步驟:1)計算出每個類的分布域;2)計算出待分類文本向量u在樣本空間中的位置;3)看u位于哪些類的分布域之外，在計算u的K個最近鄰向量時，排除與這些類中所有向量之間的距離計算，計算完畢后，根據公式(1)判定u的歸屬，算法結束。

改進算法分析:u的K近鄰搜索范圍會由于它落在一些類的分布域之外而被縮小，從而使分類的效率與傳統KNN相比得到提高。同時根據定義1，在計算u的K最近鄰向量時排除的都是其不可能屬于的類，所以不會影響準確率。

2.3 分布域的計算方法

我們可以跟據訓練樣本來計算各類的分布域，但是訓練樣本總是有限的，再有其中難免會存在的噪音數據，這樣使得在實踐中只能找到各類分布域的近似值，從而影響到改進算法的分類準確率，但總體來說這并不妨礙改進算法的實用性，下面介紹本文使用的計算方法。

設T為樣本集中全體文本向量集合，分布在m維的樣本空間V中，其中共有n個類，分別用C1，C2，…Ci…Cn表示;類Ci的中心向量表示為O(Ci)。用S(O(Ci)，r)表示樣本空間中以O(Ci)為中心、r為半徑的超球空間，分布于其中的文本向量集用E(S(O(Ci)，r))表示。

我們根據大量的實驗數據得知T中文本向量的空間分布有如下的規律:Ci中的大部分向量聚集在O(Ci)的周圍，總體來說比其他類中的向量與O(Ci)的距離近。隨著r的減小， E(S(O(Ci)，r))中的屬于類Ci的文本向量比率會變高，反之則會變低。

根據這種規律，我們用如下方式計算各類的分布域的近似值:設定閾值t(0

計算r的算法:

Begin

Forνi∈D，D={ν1， ν2， …νi…νn}

If νi∈C，

If (Num(i)+1)/N>t，

r=dist(νi，O(C))(計算結束)，

End.

其中，D里存放的是按照與O(C)之間距離升序排列的訓練樣本集T內各向量，N是C中的向量個數，Num(i)代表D中前i個向量里屬于C的個數，dist(νi，O(C)代表νi與O(C)之間的距離。

3 實驗結果

我們實現了本文的算法并設計了實驗，分別考察了t的取值對算法效率和準確率的影響，并在總體上分析了算法的有效性。實驗采用了搜狐新聞語料庫，包含IT，財經，體育等共9個類，16049篇文檔。生成文本向量時，特征加權算法為TFIDF，維數為1000。改進算法的效率、準確率均和傳統KNN做比較，K值取50，權重判定公式(1)中相似度函數sim(di，d)取兩個向量之間的余弦。

由圖1和圖2可以看出，隨著t的增大，效率會逐漸提高，但是隨著計算出的各類分布域的縮小，使得準確率直線下降，這是因為很多文本向量被排除在了本類分布域之外，計算K最近鄰的結果偏離原始取值的程度不斷加大所致。t的不同取值會使得改進算法有不同的效率和準確率，只有合理的選取t值，才能使改進算法具有實用性，通過實驗發現t=0.04時，改進算法的效果最好，準確率不至于下降太多，同時效率能有相當大的提高。可以看到，相對于傳統KNN，改進的算法可以做到在準確率損失不到2%的情況下，提高70%以上的效率。總之，在閾值選取合理的情況下，改進的算法可以在基本不影響的準確率的同時提高KNN的效率，但如果超過這個范圍，雖然可以提高效率，但是準確率會急劇下降，使算法變得不實用。

4 結束語

本文提出了一種基于粗糙集的KNN快速分類算法。根據文本向量在空間的分布特點，計算出各類的分布域，在尋找待分類文本向量的K最近鄰時，可以少做對樣本集的搜索，從而大大提高了KNN的效率。

參考文獻:

[1] Yang Y. Expert network: Effective and efficient learning from human decisions in text categorizations in text categorization and retrieval[C]//The 17th International ACM SIGIR Conference on Research and development in Information Retrieval，1994:13-22.

[2] Aha D W， Kibler D， Albert M K. Instance-based learning algorithms[J]. Machine Learning，1991(6):37-66.

[3] Aha D W. Lazy learning[M]. Dordrecht: Kluwer Academic，1997.

[4] 王曉燁，王正歐.K-最近鄰分類技術的改進算法[J].電子信息學報，2005，27(3):487-491.

[5] Hjaltason G R， Hanan S. Index-driven similarity search in metric spaces[J]. ACM Trans. on Database Systems，2003，28(4):517-580.

[6] Hinneburg A， Aggarwal C C， Keim D A. What is the nearest neighbor in high dimensional spaces[C]//The 26th International Conference on Very Large Data Bases， Cairo， Egypt，2000:506-515.

[7] Weber R， Schek H， Blott S. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces[C]//The 24th International Conference on Very Large Data Bases， Morgan Kaufman，1998:194-205.