劉忠 劉洋 建曉

桂林理工大學(xué)信息科學(xué)與工程學(xué)院 廣西 541004

0 引言

文本分類是在預(yù)定義的分類體系下，根據(jù)文本的特征(內(nèi)容或?qū)傩?，將給定文本與一個或多個類別相關(guān)聯(lián)的過程。常見的分類算法包括：樸素貝葉斯分類法、支持向量機分類法，k-最近鄰法，神經(jīng)網(wǎng)絡(luò)法，決策樹分類法等。

KNN分類法因其思想簡單，效果較好得到了廣泛的應(yīng)用。但是KNN是一種惰性學(xué)習(xí)法，模型僅對訓(xùn)練樣本進行簡單的存儲或稍加處理，一直等到給定一個檢驗樣本時才進行泛化。通過給定的檢驗樣本與和它相似的訓(xùn)練樣本進行比較來預(yù)測類別。然而，在文本分類中，由于訓(xùn)練樣本集很大和文本特征向量的維數(shù)很高，計算訓(xùn)練樣本的最近鄰樣本需要花費很多時間。

1 KNN算法的改進

針對KNN算法在文本分類上效率低下的問題，目前已經(jīng)提出了很多的改進算法。歸納起來有兩種途徑：①降低文本向量的維度，采用的主要方法有：聚合文本向量中相關(guān)聯(lián)的特征詞的方法，基于隱含語義的kNN文本分類方法；②裁剪訓(xùn)練集，使用小樣本代替大樣本，采用的主要方法有：基于中心向量的分類法，基于質(zhì)心的文本分類算法，基于簇的K最近鄰分類算法，基于粗糙集的快速KNN文本分類算法。

本文提出的基于KD-Tree的KNN文本分類算法就是在保持原有KNN算法訓(xùn)練時間為零的前提下，通過對訓(xùn)練文本向量集建立KD-Tree，測試時，只需要對KD-Tree進行搜索，而不是對整個無序的訓(xùn)練集進行搜索，這樣，測試時間為，遠小于原始算法的，使得總的分類時間大大減小。

2 基本概念

2.1 二叉查找樹

二叉查找樹是一種特殊的二叉樹。二叉查找樹的存儲規(guī)則是：在一棵二叉查找樹中，節(jié)點的元素可以使用一個全序語義比較，每個節(jié)點n都要遵循下面這兩個規(guī)則：

(1) n的左子樹的每個節(jié)點的元素小于等于節(jié)點n的元素。

(2) n的右子樹的每個節(jié)點的元素大于等于節(jié)點n的元素。

2.2 KD-Tree

KD-Tree指k維的二叉查找樹，在其上可實現(xiàn)對給定k維數(shù)據(jù)的快速最近鄰查找。與二叉查找樹不同的，KD-Tree的每個節(jié)點代表k維空間的一個點，并且樹的每一層都根據(jù)這一層的分辨器做出分枝決策。第i層的分辨器定義為：i mod k。

存儲規(guī)則為：對第 i層的任意一個節(jié)點 n，若它的左子樹非空，則其左子樹上所有節(jié)點的第i mod k維值均小于節(jié)點n的第i mod k維值；若它的右子樹非空，則其右子樹上所有節(jié)點的第i mod k維值均大于節(jié)點n的第i mod k維值；并且它的左右子樹也分別為KD-Tree。

3 基于KD-Tree的KNN文本分類算法

3.1 算法思想

傳統(tǒng)的knn算法認為訓(xùn)練文本集是一個無序的集合，所以在測試時需要一個一個地比較訓(xùn)練文本和測試文本的相似度。其實訓(xùn)練文本集是一個同類文本相互聚集，不同類文本距離較大的集合。KD-Tree可以近似的描述文本集的這種關(guān)系，在KD-Tree中，某個節(jié)點的分辨器(即i mod k)都大于左子樹中所有節(jié)點的第i mod k維值，都小于右子樹中所有節(jié)點的第i mod k維值?？梢訩D-Tree利用這個特性，把訓(xùn)練文本向量集插入一棵KD-Tree后，在KD-Tree中搜索待測文本向量時，搜索路徑所經(jīng)過的節(jié)點和待測文本的相似度越來越大，而那些和待測文本相似度較小的節(jié)點則在搜索中被忽略了。這樣就能通過步得到個相似文本，再計算這個相似文本中哪個與待測文本最為相似。

文本表示通常采用向量空間模型，一個文檔看成是n維空間中的一個向量。文本向量維數(shù)一般成千上萬，因此傳統(tǒng)KNN算法計算開銷非常大。而改進算法通過搜索 KD-Tree大大減少了需要計算相似度的文本數(shù)量，所以雖然文本維數(shù)很高，但是改進算法效率依然很高。

3.2 算法步驟

(1) 建立一個空 KD-Tree，將訓(xùn)練集文本向量依次插入KD-Tree中。

(2) 在測試集中取出一個待測文本向量，在KD-Tree中搜索這個文本向量，得到祖先節(jié)點集。

(3) 依次計算待測文本向量與祖先節(jié)點的相似度，相似度最大的文本類型就是待測文本的文本類型。

(4) 測試集文本是否計算完畢，是則結(jié)束，不是則轉(zhuǎn)到第(2)步。

4 實驗結(jié)果與分析

4.1 實驗數(shù)據(jù)來源

本文選取了復(fù)旦大學(xué)李榮陸博士的文本分類語料庫，共分為20個類別，分別是：Art，Literature，Education，Philosophy，History，Space，Energy，Electronics，Communication，Computer，Mine，Transport，Environment，Agriculture，Economy，Law，Medical，Military，Politics，Sports。原始訓(xùn)練集有 9804個文本，測試集有9833個文本。去除無效文本和重復(fù)文本后，訓(xùn)練集剩余8333個有效文本，測試集剩余8345個有效文本。復(fù)旦語料庫不是一個均衡的語料庫，比如：訓(xùn)練集中computer，Economy，Politics，Sports類別的文本量都超過1000個，而 Energy，Electronics，Communication類別的文本量則不超過30個。

4.2 評價手段

本文使用正確率、召回率和F1測度值來評價算法的分類效果。

4.3 結(jié)果及分析

實驗分詞使用的是開源分詞程序IKAnalyzer3.2.8，然后去除停用詞，用信息增益法選取前 1000個貢獻最大的詞為特征詞集。使用TF-IDF作為計算文本向量特征的權(quán)重函數(shù)。結(jié)果如表1、表2、表3。

表1 算法分類精度比較

表2 算法平均準(zhǔn)確率比較

表3 算法分類時間比較

從準(zhǔn)確率和召回率來看，對于語料庫中文本數(shù)量相對較多的類別，傳統(tǒng)KNN和改進KNN都具有較好的分類效果，文本數(shù)量相對較少的類別，分類效果則較差。但因為語料庫分布不均衡，貧樣本類別的文本總量占語料庫文本總數(shù)比例過少，所以平均準(zhǔn)確率還是很高的。

從分類時間上來看，改進的KNN的效率是極高的，提高了近 60倍。這是由于 KD-Tree的時間復(fù)雜度僅有的緣故。

5 結(jié)論

針對傳統(tǒng)KNN文本分類算法的缺點，本文提出一種基于KD-Tree的KNN文本分類算法。實驗表明，改進的KNN算法的效率是非常高效的，并且隨著文本數(shù)目的增加，效率也不會顯著變慢。比如，假設(shè)訓(xùn)練集有一百萬個文本，log106≈20，即比較20個文本即可計算出待測樣本的類別，所以該算法有一定的Web海量文本分類和挖掘的潛力。并且該算法只需額外建立一個 KD-Tree，所以非常容易集成到已有的分類系統(tǒng)中，另外結(jié)合其他算法的話，比如基于語義等方法，效率和準(zhǔn)確度會更高。

今后的工作是在改進算法的基礎(chǔ)上，繼續(xù)尋找提升準(zhǔn)確度的更好的方法，并且進一步提升算法的效率和精度。

[1]李瑩,張曉輝,王華勇.一種應(yīng)用向量聚合技術(shù)的 KNN 中文文本分類方法[J].小型微型計算機系統(tǒng).2004.

[2]李永平,程莉,葉衛(wèi)國.基于隱含語義的 kNN 文本分類研究.計算機工程與應(yīng)用.2004.

[3]魯婷,王浩,姚宏亮.一種基于中心文檔的 KNN 中文文本分類算法.計算機工程與應(yīng)用.2011.

[4]柴玉梅.基于質(zhì)心的文本分類算法.計算機工程.2009.

[5]潘麗芳,楊炳儒.基于簇的K最近鄰(KNN)分類算法研究.計算機工程與設(shè)計.2009.

[6]孫榮宗.基于粗糙集的快速KNN文本分類算法.計算機工程.