本文關(guān)鍵詞：基于決策樹和K最近鄰算法的文本分類研究，由筆耕文化傳播整理發(fā)布。

優(yōu)化算法

42622009,30(18)計算機(jī)工程與設(shè)計ComputerEngineeringandDesign

Ifdi(i=1)，看作第一簇，分配簇ID=0，簇的中心向量

就是文本向量，將簇ID放入中心向量詞條的簇鏈表中

else基于已經(jīng)生成的(還沒有完全生成，只生成了一部

分)詞條到簇的倒排索引結(jié)構(gòu)，找到和di的詞條有交集的簇(Clus)，所有這樣的簇組成簇集合(CS)

j=1

while(j≤|CS|)(|CS|表示CS的長度)

Ifdi與CSj的中心向量(ccvj)的相似度Sim(di，ccvj)>=

中心向量相似閾值(預(yù)先給定)

Ifdi和CSj中每個文本的相似度都>=文本相似閾

值(預(yù)先給定)，分別記下簇ID、最大相似度，并設(shè)置標(biāo)志表明文本能夠歸入已有的簇，j++，計算下一簇

Elsej++，計算下一簇Elsej++，計算下一簇

If能夠歸入已有簇，選擇相似度最大的一簇加入，簇中成員發(fā)生變化，更新中心向量，如果中心向量中加入了新的詞條，將簇ID放入新詞條的簇鏈表中

Else自成一簇，簇ID為已有最大簇ID加一，，簇的中心向量就是文本向量，將簇ID放入中心向量詞條的簇鏈表中

i++

3.3基于簇的KNN分類算法

把待分類文本d表示成文檔向量V(w1，w2，…，wn)基于詞條到簇的倒排索引結(jié)構(gòu)，找到向量V中每個詞條

ti(1≤i≤n)(n表示文檔向量的長度)的簇鏈表li(1≤i≤n)

合并li，去掉重復(fù)的簇ID，得到簇集合(CS)

For(1≤j≤|CS|)(|CS|表示CS的長度)

依次計算d與CSj的中心向量(ccvj)的相似度Sim(d，ccvj)按照相似度排序，得到最近的m個簇Clusi(1≤i≤m)For(1≤i≤m)

計算d與Clusi中每個文本的相似度

按照相似度排序，得到最近的k個文本，根據(jù)這k個文本的類別得到待分類文本的類別。

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

我們從阿里巴巴網(wǎng)站上下載了30多萬描述產(chǎn)品的網(wǎng)頁，

其中30萬的網(wǎng)頁做訓(xùn)練集，其余的網(wǎng)頁做測試集。下載的網(wǎng)頁含有類標(biāo)簽，總共有2602個產(chǎn)品類，這些產(chǎn)品類有電子類、服裝類等。

這些網(wǎng)頁經(jīng)過初步處理，寫成了文本。文本由3部分組成，產(chǎn)品所屬的類、產(chǎn)品的名字、產(chǎn)品的描述。訓(xùn)練文本分詞、特征提取后，使用了公式(2)設(shè)置特征項的權(quán)重。生成簇的實(shí)驗(yàn)結(jié)果如表1所示。

表1

生成簇的實(shí)驗(yàn)結(jié)果

中心向量相似閾值

訓(xùn)練集文本總數(shù)

簇總數(shù)0.81193385150.8520萬1154360.85

30萬

163653

隨著訓(xùn)練文本數(shù)的增加，簇總數(shù)在整個訓(xùn)練文本總數(shù)中所占比重逐步下降，從實(shí)驗(yàn)結(jié)果來看在訓(xùn)練樣本較多的情況下，簇總數(shù)約為訓(xùn)練文本總數(shù)的一半左右。因此在訓(xùn)練文本總數(shù)較大的情況下，基于簇的文本分類能極大地降低相似度的計算次數(shù)，提高分類速度。基于簇的KNN分類器的實(shí)驗(yàn)結(jié)果如表2所示。

基于簇的KNN分類器的準(zhǔn)確度經(jīng)過多次實(shí)驗(yàn)得到的結(jié)

果大約是93%，由于很多的產(chǎn)品頁(描述產(chǎn)品的網(wǎng)頁)存在一些缺陷，例如廠家將自己的產(chǎn)品歸入多個不同的類，產(chǎn)品的描述多變、不夠規(guī)范，類目較細(xì)，所以試驗(yàn)得出的分類精度是切合實(shí)際的。

5結(jié)束語

本文針對傳統(tǒng)KNN算法在尋找待分類文本的k個鄰居

時，相似度計算過多的缺點(diǎn)，提出了基于簇的KNN分類算法。從實(shí)驗(yàn)結(jié)果來看，在訓(xùn)練樣本較多的情況下，簇總數(shù)約為訓(xùn)練文本總數(shù)的一半左右，因此基于簇的KNN分類算法使時間復(fù)雜度降低到原來的一半左右，提高了分類器的性能。如果能夠找到較好的訓(xùn)練樣本，有望提高分類精度。

同時本文根據(jù)相同的特征項出現(xiàn)在文本中的位置不同，對分類的貢獻(xiàn)也不同，應(yīng)賦予不同的權(quán)重這一假設(shè)，改進(jìn)了TF-IDF公式。

參考文獻(xiàn):

[1]臺德藝,謝飛,胡學(xué)剛.文本分類技術(shù)研究[J].合肥學(xué)院學(xué)報(自然科學(xué)版),2007,17(3):61-64.

[2]王煜.基于決策樹和K最近鄰算法的文本分類研究[D].天津大學(xué),2006.

[3]盧葦,彭雅.幾種常用文本分類算法性能比較與分析[J].湖南大學(xué)學(xué)報:自然科學(xué)版,2007,34(6):67-69.

[4]劉華.基于關(guān)鍵短語的文本分類研究[J].中文信息學(xué)報.2007年,第21卷,第4期:34-41.

[5]

KristofCoussenment,DirkVandenPoel.Inprovingcustomercomplaintmanagementbyautomaticemailclassificationusinglinguisticstylefeaturesaspredictors[EB/OL].,2007.[6]

林永民,朱衛(wèi)東.模糊KNN在文本分類中的應(yīng)用研究[J].計算機(jī)應(yīng)用與軟件,2008,25(9):185-187.

[7]黃旭,朱艷琴,羅喜召.實(shí)時文本分類系統(tǒng)的研究與實(shí)現(xiàn)[J].計算機(jī)工程,2008,34(18):87-88.

[8]

秦玉平,艾青,王秀坤,等.基于支持向量機(jī)的兼類文本分類算法研究[J].計算機(jī)工程與設(shè)計,2008,29(2):408-410.

  本文關(guān)鍵詞：基于決策樹和K最近鄰算法的文本分類研究，由筆耕文化傳播整理發(fā)布。