,

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

0 引 言

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

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

1 特征降維方法

1.1 詞性過(guò)濾

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

1.2 同義詞歸并處理

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

表1 文檔集特征項(xiàng)同義詞歸并處理示例

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

(1) 采用中科院分詞工具(ICTCLAS)進(jìn)行切詞和詞性標(biāo)注,然后僅選擇漢語(yǔ)中的名詞、動(dòng)詞和形容詞以及中英文縮寫(xiě)詞等較具代表性的詞性建立詞性過(guò)濾表,將通過(guò)詞性過(guò)濾表處理后的詞項(xiàng)組成文檔特征項(xiàng).

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

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

(1)

(2)

(3)

(4)

2 改進(jìn)的信息增益公式

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

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

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

(5)

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

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

(6)

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

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

(7)

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

(8)

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

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

(9)

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

(10)

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

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

(11)

3 SVM分類算法

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

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

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

(12)

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

(13)

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

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

(14)

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

(15)

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

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

4.1 評(píng)估指標(biāo)

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

(1) 準(zhǔn)確率(precision):

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

(16)

(2) 召回率 (recall):

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

(17)

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

(18)

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

(19)

4.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn):

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

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

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

[6] 周萌清.信息理論基礎(chǔ)[M].北京:北京航空航天大學(xué)出版社,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ī)的中文網(wǎng)頁(yè)自動(dòng)分類[J].計(jì)算機(jī)工程,2005,31(10):145-147

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