基于向量空間模型的多主題Ｗｅｂ文本分類方法

摘要：對給定的網(wǎng)頁，提取其特征向量，計算網(wǎng)頁特征向量與分類特征向量的相似度，使用K means聚類方法尋找歸屬類得到動態(tài)閾值，提出了一種基于動態(tài)閾值的向量空間模型多主題Web文本分類方法。該方法通過網(wǎng)頁與每個類的相似度和動態(tài)閾值的比較，實現(xiàn)了將包含多個主題的網(wǎng)頁劃分到相應(yīng)的多個類中。實驗證明，這種方法具有較好的精確度和召回率。

關(guān)鍵詞：向量空間模型；文本分類；多主題；數(shù)據(jù)挖掘

中圖分類號：TP311．13文獻標志碼：A

文章編號：1001－3695(2008)01－0142－03

0引言

Web文本分類是當(dāng)前文本挖掘的研究熱點之一。其分類方法較多，主要有貝葉斯分類算法[1](naive Bayesian classi fier)、最近鄰接參照分類算法[2，3](K nearest neighbor)和基于本體的文本分類算法[4]等。這些算法均將Web頁面分到某個類中進行處理。實際上幾乎每個網(wǎng)頁均包含多個不同的主題，如使用上述算法就要求將頁面分到特定的類中。例如某個網(wǎng)頁A是關(guān)于教育亂收費的，就要求將網(wǎng)頁A分到教育和法制法規(guī)兩個類中；網(wǎng)頁B主要內(nèi)容是關(guān)于農(nóng)作物的價格報道，就要求將該網(wǎng)頁分到農(nóng)業(yè)和財經(jīng)兩個類中。對于此類問題，普遍采用的方法是首先設(shè)定一個固定閾值，然后分別計算待測文檔與每個類之間的相似度。當(dāng)待測文檔與某個類的相似度大于設(shè)定的閾值時，就將待測文檔分到這個類中。這種方法中，閾值的大小對分類的精確度和召回度的影響較大，如果閾值過大，則有可能將原本屬于某個類的文檔排除在外，召回率變小；如果閾值太小，則將原本不屬于某個類的文檔劃分到這個類中，精確度變小。因而設(shè)置一個恰當(dāng)?shù)拈撝凳峭瑫r保證較高精確度和召回率的關(guān)鍵，在Web文本分類研究中具有重要的實際意義。為改變固定閾值分類方法的不足，本文提出了基于動態(tài)閾值的多主題Web分類方法。首先提出了該動態(tài)閾值分類方法的實現(xiàn)結(jié)構(gòu)，然后根據(jù)待分頁面與所有類之間的相似度動態(tài)地計算一個閾值。

1基于向量空間模型的文檔分類

1．1Web文檔的表示

目前文檔的表示模型有很多，其中最普遍使用的是向量空間模型（VSM）。在這種模型中，每個文檔被表示成特征向量：V(d)=(t1，w1(d);t2，w2(d);…；tn，wn(d))。其中：ti為特征詞條；wi(d)為特征詞條i在文檔中的權(quán)重?？梢詫中出現(xiàn)的所有詞作為ti，但這樣就會使得特征向量的維數(shù)特別高，包含噪聲，特征不明顯。而一個文檔的內(nèi)容主要是由動詞、名詞、形容詞等實詞決定的，虛詞和一些在所有文檔中均出現(xiàn)的高頻詞對分類是沒有任何意義的，所以必須進行特征提取，降低特征空間的維數(shù)，以達到降低計算的復(fù)雜度、提高分類準確率的目的。

1．1．1特征提取

特征提取即對特征空間中的所有特征項進行特征評估，利用特征評估函數(shù)對每個特征項計算一個評估值，然后將所有的特征項按照評估值的大小排序，選擇適當(dāng)數(shù)目的最佳特征項作為樣本的特征。常用的特征函數(shù)有以下幾種形式：詞條的χ2統(tǒng)計、信息增益、期望交叉熵、文本證據(jù)權(quán)、詞條與類別互信息等。這些方法均有較好的準確率，本文采用詞條的χ2統(tǒng)計方法進行特征提取。

1．1．2特征向量的計算

特征項在文檔中的權(quán)重wi(d)的計算對Web文本分類是至關(guān)重要的一步，wi(d)一般被定義為ti在文檔d中出現(xiàn)的頻率tfi(d)的函數(shù)，即wi(d)=F(tfi(d))。常有的F有布爾函數(shù)、平方根函數(shù)、對數(shù)函數(shù)、TF IDF[6，7]函數(shù)。而TF IDF公式是一種有效而較普遍使用的方法。目前這種方法存在許多變體公式。本文采用的公式[8]為

2多主題Web分類方法

如前所述，當(dāng)前許多基于向量空間模型的Web文本自動分類方法均是通過比較某個網(wǎng)頁與所有類之間的相似度，將相似度最大的類作為網(wǎng)頁的歸屬類，這樣只是籠統(tǒng)地將網(wǎng)頁劃分到最相似的類中，沒有考慮到存在多個主題的網(wǎng)頁應(yīng)該被劃分到多個類的情況。針對這種不足，本文提出了一種多主題分類方法，實現(xiàn)了將包含多個主題的網(wǎng)頁劃分到相應(yīng)的多個類中。其實現(xiàn)過程結(jié)構(gòu)如圖1所示。

2．1動態(tài)閾值的計算

閾值的確定是分類的關(guān)鍵，因為待分類頁面與所有類的相似度可能都很小也可能都很大，在分類前確定一個固定閾值是比較困難的，也是不恰當(dāng)?shù)?，可以根?jù)每個待分類頁面與各個類的相似度的實際情況動態(tài)地計算出一個閾值。這樣每個待分類頁面在分類時使用的閾值是不相同的，不是固定的。簡單地將動態(tài)閾值設(shè)定為所有相似度的平均值，即vt=1/nni=1si。

在計算相似度時筆者發(fā)現(xiàn)，相似度小的值比較多而相似度大的值比較少，這樣得到的閾值往往均偏小，導(dǎo)致原本不屬于某個類c的網(wǎng)頁錯誤地劃分到類c中，即分類的精確度較差；另外在進行網(wǎng)頁分類時，一般分類規(guī)則是將相似度最大的類作為網(wǎng)頁的歸屬類，所以修改以上方法，盡量讓動態(tài)閾值偏向于較大相似度。

從表1的測試結(jié)果可以看出，本文提出的方法對多主題文本分類達到了很好的分類效果，平均精確度和平均召回率分別為83.2%和87.2%。除了汽車和軍事的精確度大于召回率，其余大部分精確度均小于召回率，因此本文提出的方法更加有利于得到高的召回率。另外，本文提出的方法也能用于單主題文本分類，將本文的單主題實驗結(jié)果與傳統(tǒng)的基于分類方法的實驗結(jié)果進行比較，傳統(tǒng)的方法是將相似度最大的類作為待分文本的歸屬類。其比較如圖2、3所示。

從圖2、3可以看出，在單主題分類中，本文方法的精確度基本能夠達到傳統(tǒng)方法的精確度，但召回率卻比傳統(tǒng)方法要高得多。

4結(jié)束語

本文主要討論了Web多主題分類的問題，根據(jù)固定閾值分類方法的不足，筆者提出了動態(tài)閾值分類方法：對給定的一個網(wǎng)頁，提取其特征向量，計算與所有類的相似度；然后根據(jù)文中計算分類動態(tài)閾值的算法，將所有的相似度與這個閾值進行比較，如果某個相似度大于這個閾值，則該網(wǎng)頁就屬于相應(yīng)的類。動態(tài)閾值分類方法不但能夠?qū)Χ嘀黝}文檔進行很好的分類，同時也適應(yīng)單主題文檔的分類。實際數(shù)據(jù)的實驗證明這種方法有較好的精確度和召回率。當(dāng)然在實際應(yīng)用這種方法時還需要進一步減少該算法的時間復(fù)雜度，提高分類時的精確度。

參考文獻：

［1］BAI Jing，NIE Jian yun，CAO Gui hong.Integrating compound terms in Bayesian text classification[C]//Proc of IEEE /WIC/ACM International Conference.2005:598－601.

[2]FANG Yuan，LIU Yang，GE Yu.Improving the k nn and applying to Chinese text classification[C]//Proc of the 4th IEEE Int Confe renceson Machine Learning and Cybernetics.2005：1547 1553.

[3]LI Bao li，LU Q，YU Shi wen.An adaptive knearest neighbor text categorization strategy[J].ACM Transactions on Asian Language Information Processing，2004，12(31):215－226.

[4]劉嬌蛟，龔麗，李建華.基于本體實現(xiàn)對網(wǎng)頁文本的自動主題分類[J].計算機工程，2003，29(11):95－97.

[5]LARSEN B，AONE C.Fast and effective text mining using linear time document clustering[C]//Proc of the 4th ACM SIGKDD Int Confe rences on Knowledge Discovery and Data Mining.1999：16－22.

[6]LEWIS D，et al.Training algorithms for linear text classifiers[C]//Proc of the 19th International ACM SIGIR Conference on Research and Development in Information Retrieval.1996：298－306. 

[7]SALTON G，BUCKLEY C.Term weighting approaches in automatic text retrieval[C]//Proc ofMgt.1988:513－523.

[8]凌云，劉軍，王勛.多層次Web文本分類[J].情報學(xué)報，2005，24(6):684－689.

[9]MAEDCHE A，STAB S.Ontology learning for the semantic Web[J].IEEE Intelligent Systems，2001，6(2):72－76.

[10]AHN B S，CHO S S，KIM C.The integrated methodology of rough set theory and artificial neural network for business failure predication[J].Expert Systems withApplications，2000，18(2):65 74.

[11]KEHAGIAS A，PETRIDIS V，et al.A comparison of word and sense based text categorization using several classification algorithms[J].Journal of Intelligent Information Systems，2003，11(3):227－247.

[12]HUANG C C，CHUANG S L，CHEN L F.Live classifier:creating hierarchical text classifiers through Web corpora[C ]//Proc of the 13th Int Conferences on World Wide Web.2004:184 192.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”