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

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

關鍵詞：向量空間模型；文本分類；多主題；數據挖掘

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

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

0引言

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

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在文檔中的權重。可以將d中出現的所有詞作為ti，但這樣就會使得特征向量的維數特別高，包含噪聲，特征不明顯。而一個文檔的內容主要是由動詞、名詞、形容詞等實詞決定的，虛詞和一些在所有文檔中均出現的高頻詞對分類是沒有任何意義的，所以必須進行特征提取，降低特征空間的維數，以達到降低計算的復雜度、提高分類準確率的目的。

1．1．1特征提取

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

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

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

2多主題Web分類方法

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

2．1動態閾值的計算

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

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

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

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

4結束語

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

參考文獻：

［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]劉嬌蛟，龔麗，李建華.基于本體實現對網頁文本的自動主題分類[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].情報學報，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.

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