基于信息增益的中文網頁SVM分類研究

,

(上海師范大學 信息與機電工程學院, 上海 200234)

0 引 言

隨著互聯網信息的迅猛發展,對海量信息進行有效組織和分類整理顯得日益重要,而傳統的人工分類方式已經變得幾乎不可能,網頁文本自動分類突顯重要作用.文本分類是把未知文檔歸為已知類別中的一個或多個.目前,絕大多數文本分類模型采用空間向量形式表示文本文檔,即文檔向量由若干無序的詞或詞組形式特征項組成,但是,這些特征項的向量維數往往過高或者代表性不強,從而導致分類運算開銷大、準確率低等缺點.所以特征降維方法的優劣成為影響文本分類效果好壞的關鍵因素.

一般的特征降維方法是從源文檔特征集中抽取出對分類貢獻大且具有代表性的特征項,本文作者結合詞性過濾和同義詞歸并處理技術對特征項進行第一次降維處理.然后,選擇有效特征選擇方法對特征項進行二次處理,文獻[1]指出目前比較成熟的特征選擇方法包括文檔頻率法(DF)、信息增益法(IG)、互信息法(MI)和X2統計法(CHI)等等.文獻[2]表明,在英文測試集上信息增益和CHI的效果最優,認真分析了傳統信息增益方法的不足并對其做出改進,最后在傳統信息增益基礎上提出特征加權方法選擇特征項.之后根據支持向量機(SVM)分類算法對包含特征項的中文網頁文檔集進行文本分類.目前,SVM分類算法被公認為是文本分類效果中比較好的一種文本分類方法.本文作者將通過理論分析和實驗途徑來對比中文網頁文本分類中此方法改進前后分類效果.

1 特征降維方法

1.1 詞性過濾

待歸類的文檔往往采用特征項向量形式表示,最基本的方法是把文檔中所有詞或詞組作為特征項構成特征空間,然而文本中包含的詞或詞組的數量一般較龐大,如果將所有詞或詞組作為特征項則向量維數往往過高而導致數據稀疏[3]和計算量巨大等問題,這些問題會明顯加大文本分類的時間和空間復雜度，從而降低文本分類效率.所以如何在不影響分類精度和效果的同時，盡量控制向量的維數成為一個重要問題,文獻[4]表明文本分類預處理時詞性選擇非常重要.考慮到漢語當中很多詞性表現力不強或并無實際意義,假如去掉這些字詞不僅不會影響分類效果反而縮短了分類時間,所以選擇在文本預處理時對特征項進行詞性過濾.

1.2 同義詞歸并處理

傳統特征降維方法僅僅基于統計學而忽略了特征項之間蘊含的語義關聯.漢語詞義豐富、表達多元,不同詞語之間往往包含相同或相似的內在聯系,比如“比賽”和“競賽”屬于相同語義關系,“科技”和“高科技”屬于相關語義關系等等,所以作者將同一文檔中出現的若干同義詞進行歸并降維處理.《哈工大信息檢索研究室同義詞詞林擴展版》(http://www.ir-lab.org/)在《同義詞詞林》[5]原有3層分類體系基礎上細分類增加2層最終得到5層分類體系,共收詞53,859條,同時提供5層編碼.其中詞分為大、中、小3類,大類有12個,中類有97個,小類有1,400個.每個小類里都有很多詞或詞組,這些詞或詞組根據詞義遠近和相關性分成若干個詞群(段落).每個段落中詞語又進一步分成若干行,同一行詞語或詞義相同(有的詞義十分接近),或詞義有很強相關性.

表1 文檔集特征項同義詞歸并處理示例

結合以上兩者方法的特征降維步驟如下:

(1) 采用中科院分詞工具(ICTCLAS)進行切詞和詞性標注,然后僅選擇漢語中的名詞、動詞和形容詞以及中英文縮寫詞等較具代表性的詞性建立詞性過濾表,將通過詞性過濾表處理后的詞項組成文檔特征項.

(2) 完成步驟(1)后,進一步采用《哈工大信息檢索研究室同義詞詞林擴展版》詞典對詞項進行同義詞歸并處理,即將具有相同字典編碼的詞項文檔頻率進行加權合并,如表1所示.

如表1所示,文檔集中文本經過分詞后的“科技”和“科學”兩個詞語分別為“科技/n/Dk03”和“科學/n/Dk03”,此兩個詞語的后綴字典編碼相同,則歸為相同詞項,假如給定文本類別Ci,文檔集D和特征項t及其同義詞s,其相關文檔頻率概率公式如下:

(1)

(2)

(3)

(4)

2 改進的信息增益公式

2.1 傳統信息增益公式

1850年,熵由物理學家克勞修斯提出,用來表示一種能量在空間中分布的均勻程度,其中能量分布越均勻越不確定熵就越大.1948年,信息論之父Shannon將熵應用于信息處理并提出了“信息熵”概念.

文獻[6]指出信息熵被描述為信息量的不確定程度度量.如果設X為隨機變量,那么描述它不確定程度的信息熵[6]被定義如下:

(5)

通過觀察隨機變量Y后獲得的X的不確定程度描述為條件熵[6],定義為:

H(X|Y)=-∑xyp(xy)logp(x|y) .

(6)

信息增益為兩者熵之差,表示為消除不確定程度后獲得的信息量,定義為:

IG(X)=H(X)-H(X|Y) .

(7)

在文本分類領域,把類別C看成一個符合某種概率分布的信息源,則根據文檔類別C的信息熵和是否存在特征項T后的條件熵的差值可以確定該特征項T的貢獻的信息量,即特征項T的信息增益.所以傳統的信息增益計算公式[7]如下:

(8)

2.2 傳統信息增益的改進

觀察公式(8)發現傳統信息增益方法根據特征的文本數考察了特征對整個系統的分類貢獻.所以在不同類中分布相同或相近的特征項信息增益最小,即在所有類中都分布均勻的特征項對系統貢獻最低,這說明該方法特別適合用來做全局的特征選擇,即所有的類使用相同的特征集合,但是,每一個類別都有自己的特征集合,特別是只在1個類內，分布比較均勻的特征項往往對此類具有更好的代表性和區分能力.為了提高分類精度,嘗試彌補和改進傳統信息增益方法.

(9)

使用歸一化的特征項t的平均偏差平方來近似表示方差D(t),代入公式(9),則有公式為:

(10)

如果特征項t在某類文檔中分布越均勻則D(t)越小,相應的就越大.所以本文選擇使用加權因子D(t)來改進特征項t的信息增益權重.

結合1.2節中同義詞歸并處理算法,將公式(1)～(4)帶入公式(8),再結合特征項加權公式(10),得到改進信息增益公式如下:

(11)

3 SVM分類算法

在特征提取后將選擇采用SVM分類算法來測試特征降維方法和改進的信息增益方法對文本分類效果的影響.當前較為著名的文本分類算法包括支持向量機(SVM),K近鄰法(KNN),樸素貝葉斯法(NB),神經網絡法(NNet),線性最小二乘法(LLSF)等.其中支持向量機(SVM)算法憑借其理論和實踐上的優勢被廣泛應用于文本分類領域.

1963年,支持向量機[7](SVM)由Vapnik等人提出并應用于函數模擬、模式識別和數據分類等領域,其方法建立在統計學的VC維理論和結構風險最小原理基礎之上,具體實現思想是通過內積函數定義的非線性變換把輸入向量映射到一個高維特征空間,然后在這個空間中構造最優超平面來進行文本分類.其中文本分類效果的好壞取決于核函數是否擇優選擇.常用的核函數[8]包括以下4種:

(1) 線性核函數:

(12)

(2) 多項式核函數:

(13)

(3) 徑向基(RBF)核函數:

K(xi,xj)=exp(-γ||Xi-Xj||2),γ>0 .

(14)

(4) Sigmoid核函數:

(15)

其中γ,r和d都是核函數參數.文獻[9]和文獻[10]都表明針對不同的數據集選擇不同的核函數會有不同的分類效果.其中文獻[8]指出對于數據量偏大的文本分類選擇線性核函數較好.作者將在實驗部分做出對比測試和分析.

4 實驗結果和分析

4.1 評估指標

評估文本分類系統好壞的2個常用指標分別為準確率(precision)和召回率(recall).其中,準確率反映了返回文檔集中相關文檔在所有相關文檔集中所占比重,而召回率反映了有多少相關文檔出現在返回文檔集中.兩者公式如下:

(1) 準確率(precision):

P=系統預測相關文檔數/文檔集中相關文檔總數 .

(16)

(2) 召回率 (recall):

R=系統預測相關文檔數/系統返回相關文檔總數 .

(17)

準確率和召回率反映了文本分類的兩個不同方面,一般情況下二者不能偏廢，必須綜合考慮,則釆用F-測度(F-measure)來表示準確率和召回率的調和加權平均,其公式如下:

(18)

通常情況下,取參數a為1,則得到綜合考慮的評估指標F1公式如下:

(19)

4.2 實驗結果與分析

從兩大門戶網站騰訊網(http://www.qq.com/)和新浪網(http://www.sina.com.cn/)中科技欄目和包括體育、財經、教育、軍事等在內的非科技欄目爬蟲下載網頁文章,經過文本解析處理后選擇平均長度為500～600字左右的4000篇文檔作為語料庫.其中選取科技和非科技各1600篇文章共3200篇文檔作為訓練集,并從訓練集中隨機抽取800篇文章作為封閉測試集,剩余800篇文章作為開放測試集.

目前,應用比較成熟的SVM分類器主要有LibSVM[9]和SVMLight兩種.在本實驗中采用臺灣大學林智仁教授開發的LibSVM軟件包進行分類測試,此軟件包操作方便分類快速有效,可以解決分類問題(包括c-SVC和n-SVC)、回歸問題(包括e-SVR和n-SVR)以及分布估計(one-class-SVM)等問題,作者選擇此分類器工具和其提供的4個常用核函數進行文本分類實驗,將經過詞性過濾、同義詞歸并處理及特征加權和未經相關處理的信息增益方法進行封閉測試和開放測試對比,具體實驗結果及分析如下:

表2 封閉測試集中不同核函數不同方法下分類測試結果

表3 開放測試集中不同核函數不同方法下分類測試結果

如表2所示,在封閉測試集中,特征降維和改進信息增益方法使文本分類準確率和召回率均有所提高,其宏平均F1值也明顯優于傳統信息增益方法,此外,選擇線性核函數的性能最優,多項式和徑向基核函數次之,Sigmoid核函數較差.事實上,詞性過濾方法大大降低了文本向量空間的稀疏性和運算量,同義詞歸并處理和特征加權算法提高了類別區分能力,綜合以上幾點很大程度上提高了分類效率.由表3知,在開放測試集中,分類精度均有所下降,但是改進的信息增益方法分類準確率、召回率和F1值均有較大提高,而且線性核函數分類精度仍為最高,多項式和徑向基核函數次之,Sigmoid核函數的精度最低.

綜上,特征降維和改進信息增益方法使4種核函數的分類精度均有很大提高.其中,線性核函數的分類精度最優,多項式和徑向基核函數次之,Sigmoid核函數的精度較差.故此實驗表明使用詞性過濾、同義詞歸并處理和特征加權算法后確實提高了中文網頁分類系統的精度并且效果顯著.

5 結束語

在傳統信息增益基礎上引入詞性過濾、同義詞歸并處理和特征加權算法,改進了特征降維和傳統信息增益方法的缺點和不足,提出并應用了特征降維和一種優化的信息增益公式(11),該公式充分考慮了同義詞特征項和類內部分布均勻特征項對判別該類的重要影響,從而大大提高了中文網頁分類系統的效率和精度.在下一步工作中,將考慮將此方法應用于更多的分類領域來檢驗它的適用性,并進一步完善此特征加權算法公式來更好地提高系統性能和分類精度.

參考文獻:

[1] MANNING C D,RAGHAVAN P,SCHüTZE H.Introduction to information retrieval[M].Cambridge:Cambridge University Press,2008.

[2] YANG Y M,PEDERSON J O.A comparative study on feature selection in text categorization[C]∥ICML′97 Proceeding of the Fourteenth International Coference on Machine Learing.San Francisco:Morgan Kaufmann Publishers Inc,1997.

[3] 張玉芳,陳小莉,熊忠陽.基于信息增益的特征詞權重調整算法研究[J].計算機工程與應用,2007,43(35):159-161.

[4] 李英.基于詞性選擇的文本預處理方法研究[J].情報科學,2009,27(5):717-719.

[5] 梅家駒,竺一鳴,高蘊琦,等.同義詞詞林[M].上海:上海辭書出版社,1983.

[6] 周萌清.信息理論基礎[M].北京:北京航空航天大學出版社,2002.

[7] VAPNIK V.The nature of statistical learning theory[M].New York:springer,1999.

[8] CHANG C C,LIN C J.LIBSVM:a library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology (TIST),2011,2(3):27.

[9] 賈泂,梁久禎.基于支持向量機的中文網頁自動分類[J].計算機工程,2005,31(10):145-147

[10] 張國梁,肖超鋒.基于 SVM 新聞文本分類的研究[J].電子技術,2011,38(8):16-17.