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

劉忠 劉洋 建曉

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

0 引言

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

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

1 KNN算法的改進(jìn)

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

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

2 基本概念

2.1 二叉查找樹

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

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

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

2.2 KD-Tree

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

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

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

3.1 算法思想

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

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

3.2 算法步驟

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)來源

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

4.2 評(píng)價(jià)手段

本文使用正確率、召回率和F1測(cè)度值來評(píng)價(jià)算法的分類效果。

4.3 結(jié)果及分析

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

表1 算法分類精度比較

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

表3 算法分類時(shí)間比較

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

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

5 結(jié)論

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

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

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

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

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

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

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

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