基于信息增益的中文網(wǎng)頁SVM分類研究

,

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

0 引 言

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

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

1 特征降維方法

1.1 詞性過濾

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

1.2 同義詞歸并處理

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

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

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

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

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

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

(1)

(2)

(3)

(4)

2 改進的信息增益公式

2.1 傳統(tǒng)信息增益公式

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

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

(5)

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

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

(6)

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

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

(7)

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

(8)

2.2 傳統(tǒng)信息增益的改進

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

(9)

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

(10)

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

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

(11)

3 SVM分類算法

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

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

(1) 線性核函數(shù):

(12)

(2) 多項式核函數(shù):

(13)

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

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

(14)

(4) Sigmoid核函數(shù):

(15)

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

4 實驗結(jié)果和分析

4.1 評估指標

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

(1) 準確率(precision):

P=系統(tǒng)預測相關(guān)文檔數(shù)/文檔集中相關(guān)文檔總數(shù) .

(16)

(2) 召回率 (recall):

R=系統(tǒng)預測相關(guān)文檔數(shù)/系統(tǒng)返回相關(guān)文檔總數(shù) .

(17)

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

(18)

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

(19)

4.2 實驗結(jié)果與分析

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

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

表2 封閉測試集中不同核函數(shù)不同方法下分類測試結(jié)果

表3 開放測試集中不同核函數(shù)不同方法下分類測試結(jié)果

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

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

5 結(jié)束語

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

參考文獻:

[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] 張玉芳,陳小莉,熊忠陽.基于信息增益的特征詞權(quán)重調(diào)整算法研究[J].計算機工程與應用,2007,43(35):159-161.

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

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

[6] 周萌清.信息理論基礎(chǔ)[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] 賈泂,梁久禎.基于支持向量機的中文網(wǎng)頁自動分類[J].計算機工程,2005,31(10):145-147

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