（計(jì)算機(jī)應(yīng)用技術(shù)專(zhuān)業(yè)論文）高性能特征選擇及文本分類(lèi)算法研究.pdf

華北電力大學(xué)碩士學(xué)位論文 摘要 從大量繁雜的文本信息中獲取有用的信息是信息處理的一大任務(wù)，而文本分類(lèi) 是實(shí)現(xiàn)這個(gè)任務(wù)的最重要的方法之一。特征選擇和文本分類(lèi)算法是文本分類(lèi)的兩個(gè) 重要的研究方向，特征選擇是為了選取最能表示文本內(nèi)容的特征來(lái)對(duì)龐大的文本空 間進(jìn)行約減，既提高了文本分類(lèi)的效率又可以通過(guò)去除噪音特征提高分類(lèi)精度，而 好的分類(lèi)方法能夠有效地提高分類(lèi)的效果。 本文針對(duì)現(xiàn)有特征選擇算法沒(méi)有利用有用的詞條頻率信息。沒(méi)有定性分析的現(xiàn) 狀，提出了基于詞條頻率的改進(jìn)特征選擇算法，對(duì)特征選擇算法進(jìn)行了定性分析，提 出了構(gòu)造高效特征選擇方法的約束條件和步驟，構(gòu)造出一種高效的特征選擇方法， 并用實(shí)驗(yàn)證明了改進(jìn)方法的有效性。 關(guān)鍵詞：文本分類(lèi)、特征選擇、詞條頻率、t c c a b s t r a c t a b s o l u t e l y , d r w a i n g t h ev a l u e di n f o r m a t i o nf r o mt h e l a r g eq u a n t i t y o f m i s c e l l a n e o u st e x ti sah a r da s s i g n m e n t ，w h i l et e x tc a t e g o r i z a t i o ni sj u s tt h a ts o l u t i o nt o i m p l e m e n tt h i s a m o n gw h i c h , t h ef e t u r es e l e c t i o na n dt e s tc a t e g o r i z a t i o na r i t h m e t i ca r et h e t w ok e yr e s e a r c hd i r e c t i o n s r e g a r d i n gt h ef e t u r es e l e c t i o n , t h eg o a lo fi ti st os e l e c tt h em o s t r e p r e s e n t a t i v ef e a t u r e , b yw h i c ht h et e x ts p a c ec a l lb ec o td o w n a tt h es a m et i m e ，n o to n l y t h et e x tc a t e g o r i z a t i o ne f f i c i e n c yi se n h a n c e d ，b u ta l s ot h ec a t e g o r i z e dp r e c i s i o ni si m p r o v e d b ya v o i d i n gv o i c ec h a t r a c t o r s o nt h eo t h e rs i d e ，t h el a t t e ro ni sas t r o n gw c a p o nt oa d v a n c e t h ec a t e g o r i z a t i o ne f f e c t u n d e rt h ec o n d i t i o n st h a tt h ee x i s t e df e a t u r es e l e c t i o nm e t h o dh a v en o tt a k e n a d v a n t a g eo ft h eu s e f u lt e r mf r e q u e n c yi n f o r m a t i o n ，a n db e i n gs h o r to fq u a l i t a t i v e a n a l y s i s t h i sd i s s e r t a t i o na c h i e v e sa sf o l l o w i n g , p r o p o s i n gaf e a t u r es e l e c t i o nm e t h o db a s e d o nt h et e r mf r e q u e n c y , a n a l y z i n gq u a l i t a t i v e l yt of e a t u r es e l e c t i o nm e t h o d ，i n n o v a t i n g t h ec o n s t r a i n e dc o n d i t i o na n ds t e p so fc o n s t r u t i n gh i g he f f i c i e n c yf e t u r es e l e c t i o nm e t h o d , f o r m a t t i n gah i g he f f i c i e n c yf e a t u r es e l e c t i o nm e t h o da n dp r o v i n gt h ea b o v em e t h o db y e x p e r i m e n t a s u n c h u n m i n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f l i nb i y i n g k e yw o r d s ：t e x tc a t e g o r i z a t i o n ，f e a t u r es e l e c t i o n ，t e r mf r e q u e n c y , t c c i 聲明 本人鄭重聲明：此處所提交的碩士學(xué)位論文高性能特征選擇及文本分類(lèi)算法 研究，是本人在華北電力大學(xué)攻讀碩士學(xué)位期間，在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作 和取得的研究成果。據(jù)本人所知，除了文中特別加以標(biāo)注和致謝之處外，論文中不 包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果，也不包含為獲得華北電力大學(xué)或其他教 育機(jī)構(gòu)的學(xué)位或證書(shū)而使用過(guò)的材料。與我一同工作的同志對(duì)本研究所做的任何貢 獻(xiàn)均己在論文中作了明確的說(shuō)明并表示了謝意。 學(xué)位論文作者簽名：塑! 盤(pán)蜩 日期：塑：! ! ! 三 關(guān)于學(xué)位論文使用授權(quán)的說(shuō)明 本人完全了解華北電力大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定即：學(xué)校有權(quán) 保管、并向有關(guān)部門(mén)送交學(xué)位論文的原件與復(fù)印件；學(xué)校可以采用影印、縮印或 其它復(fù)制手段復(fù)制并保存學(xué)位論文；學(xué)?？稍试S學(xué)位論文被查閱或借閱；學(xué)校 可以學(xué)術(shù)交流為目的，復(fù)制贈(zèng)送和交換學(xué)位論文：同意學(xué)?？梢杂貌煌绞皆诓煌?媒體上發(fā)表、傳播學(xué)位論文的全部或部分內(nèi)容。 ( 涉密的學(xué)位論文在解密后遵守此規(guī)定) 作者簽名：圣盔蜩 日 期：型丑：! ：墾 導(dǎo)師簽名：壹鹺耋 日期：逝z ：三：省 華北電力大學(xué)碩士學(xué)位論文 1 1研究背景 第一章引言 我們正處在一個(gè)信息爆炸的時(shí)代l 全世界每年出版圖書(shū)8 0 多萬(wàn)種，期刊4 0 萬(wàn) 種，其他文獻(xiàn)信息資料4 0 0 萬(wàn)種；發(fā)表的科學(xué)論文大約5 0 0 萬(wàn)篇。加利福尼亞大學(xué) 伯克利分校的一項(xiàng)研究表明【1 】過(guò)去3 年中全球信息量翻了一番，據(jù)他們統(tǒng)計(jì)所得， 僅2 0 0 2 年全球由紙張、膠片及電子介質(zhì)所記錄的信息總量達(dá)到5 萬(wàn)兆字節(jié)，約等 于1 9 9 9 年的兩倍，也就是說(shuō)1 9 9 9 到2 0 0 2 年的三年問(wèn)，全世界的信息量以平均每 年3 0 左右的速度飛速增長(zhǎng)。i n t e r n e t 是信息增長(zhǎng)的另一個(gè)主要增長(zhǎng)渠道。隨著 i n t e r n e t 的日益普及，i n t e r n e t 上的信息量也飛速膨脹。1 9 9 9 年的統(tǒng)計(jì)結(jié)果表明， i n t e r n e t 上約有3 5 億個(gè)靜態(tài)h t m l 頁(yè)面，每天增加約1 0 0 萬(wàn)，截至到2 0 0 4 年1 2 月，g o o g l c 宣稱(chēng)已經(jīng)索引的網(wǎng)頁(yè)數(shù)量已經(jīng)超過(guò)了8 0 億。 面對(duì)如此龐大而且還在飛速膨脹的信息海洋，我們迫切需要一種有效的，高速 的工具來(lái)幫助組織與管理這些海量信息，其中一種有效的方法就是對(duì)這些信息進(jìn)行 分類(lèi)。由于這些信息大都是文本信息，文本分類(lèi)就顯得非常的重要。 本文主要工作是在中科院計(jì)算所信息檢索實(shí)驗(yàn)室完成，受到北京市自然科學(xué)基 金資助。 1 2 研究意義 文本分類(lèi)作為信息過(guò)濾、信息檢索、文本數(shù)據(jù)庫(kù)、數(shù)字化圖書(shū)館和郵件分類(lèi)等 領(lǐng)域的技術(shù)基礎(chǔ)，有著廣泛的應(yīng)用前景。 ( 1 ) 信息過(guò)濾 網(wǎng)絡(luò)的發(fā)展與普及，大大方便了我們獲取信息。但信息量之大給人們對(duì)信息的 處理帶來(lái)的很大困難，無(wú)法快速地得到所需的信息，同時(shí)還會(huì)帶來(lái)一些反面的信息。 信息過(guò)濾技術(shù)可以用來(lái)解決這些問(wèn)題，信息過(guò)濾的本質(zhì)是一個(gè)分類(lèi)問(wèn)題，既可以用 來(lái)將用戶反感的信息濾掉，也可以用來(lái)將用戶感興趣的信息過(guò)濾出來(lái)，主動(dòng)地推送 給用戶，方便了用戶快速準(zhǔn)確地獲得信息。 ( 2 ) 信息檢索 把大量的文本信息按主題層次歸類(lèi)組織可以極大地簡(jiǎn)化對(duì)信息的檢索。如果按 照類(lèi)別對(duì)文檔進(jìn)行檢索或?qū)z索結(jié)果進(jìn)行一次文檔分類(lèi)，都可以提高檢索的查準(zhǔn) 率。目前很多w e b 搜索引擎站點(diǎn)都使用了w e b 文檔層次化分類(lèi)組織。只是，目前主要 以人工分類(lèi)為主。 1 華北電力大學(xué)碩士學(xué)位論文 ( 3 ) 文本數(shù)據(jù)庫(kù) 隨著研究的深入，文本數(shù)據(jù)庫(kù)的功能已經(jīng)不再局限于存儲(chǔ)、組織和查詢(xún)文檔信 息，而是要提供多層次的服務(wù)，如文本挖掘等。文本分類(lèi)技術(shù)不僅對(duì)文本數(shù)據(jù)庫(kù)如 何存儲(chǔ)、組織文檔具有重要的意義，而且也是文本挖掘的重要內(nèi)容。 ( 4 ) 數(shù)字化圖書(shū)館 圖書(shū)館的數(shù)字化管理是大勢(shì)所趨，圖書(shū)期刊全文數(shù)字化的比重正日益增大。對(duì) 圖書(shū)進(jìn)行歸類(lèi)時(shí)，圖書(shū)管理員不可能對(duì)各個(gè)學(xué)科都非常了解，使用自動(dòng)文本分類(lèi)技 術(shù)，可以幫助圖書(shū)管理員正確地對(duì)圖書(shū)資料進(jìn)行歸類(lèi)。 ( 5 ) 郵件分類(lèi) 電子郵件作為最廣泛和成功的i n t e r n e t 服務(wù)已經(jīng)成為人們?nèi)粘Ｉ钪胁豢扇?少的組成部分。但是在給人帶來(lái)巨大方便的同時(shí)，也日益顯示出其負(fù)面影響，那就 是我們每天收到的郵件中有很大一部分是那種“不請(qǐng)自來(lái)”的所謂“垃圾”郵件， 它們或者是推銷(xiāo)廣告，或者是一些有害的不良信息，甚至還有病毒。這些垃圾郵件 不僅對(duì)網(wǎng)絡(luò)安全形成威脅，而且還造成了各方面資金上的巨大浪費(fèi)。2 0 0 2 年由于垃 圾郵件造成的損失大約在9 0 億至1 0 0 億美金，2 0 0 3 年這個(gè)數(shù)據(jù)是成倍增加。2 0 0 4 年7 月，中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心( c n n i c ) 發(fā)布的第十四次中國(guó)互聯(lián)網(wǎng)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào) 告顯示垃圾郵件在數(shù)量上是正常郵件的兩倍。對(duì)垃圾郵件進(jìn)行“圍剿”已經(jīng)刻不 容緩。目前郵件分類(lèi)可以看作通常的文本分類(lèi)問(wèn)題，它可以分為兩種模式。其一是 兩類(lèi)模式，即按照垃圾與非垃圾來(lái)分類(lèi)；另一種是多類(lèi)模式，比如工作、會(huì)議、垃 圾等。 1 3 本文工作 近些年來(lái)，文本分類(lèi)中的特征選擇和分類(lèi)算法的研究取得了很大的發(fā)展，但是 在特征選擇中有一些信息并沒(méi)有充分利用也沒(méi)有構(gòu)造特征選擇算法的標(biāo)準(zhǔn)。在分類(lèi) 算法中，對(duì)于最近鄰和貝葉斯等模型簡(jiǎn)單，分類(lèi)效果較差的改進(jìn)也不盡如人意，本 文針對(duì)這些做了以下工作： 1 利用文本中的1 1 p 信息對(duì)d f 、i o 、m i 等經(jīng)典特征選擇方法做了改進(jìn)，并通 過(guò)試驗(yàn)證明改進(jìn)的特征選擇方法有效地提高文本分類(lèi)的效果 2 對(duì)特征選擇方法進(jìn)行定性分析，提出有效的特征選擇方法必須滿足的三個(gè)約 束條件，并根據(jù)這些約束條件構(gòu)造一個(gè)有效的特征選擇方法，并實(shí)驗(yàn)驗(yàn)證其有效性。 3 分析最近鄰和貝葉斯等弱文本分類(lèi)器分類(lèi)效果較差的原因，實(shí)驗(yàn)驗(yàn)證k n n 分類(lèi)器的分類(lèi)器偏差，提出弱文本分類(lèi)器改進(jìn)的方向。 2 華北電力大學(xué)碩士學(xué)位論文 1 4 論文組織 本文從對(duì)文本分類(lèi)性能有重大影響的兩個(gè)方面：特征選擇和分類(lèi)算法兩個(gè)方面 進(jìn)行闡述。 第一章介紹了文本分類(lèi)的研究背景，從多個(gè)方面闡述了文本分類(lèi)的重要意義 第二章對(duì)文本的表示方法、特征選擇、文本分類(lèi)的應(yīng)用及文本分類(lèi)算法等方面 做了詳細(xì)的介紹。 第三章介紹了一種d f 的粗糙集解釋?zhuān)⑻岢隽艘环N基于t f 的改進(jìn)特征選擇方 法。 第四章分析了特征選擇算法的特點(diǎn)，指出高性能特征選擇算法的構(gòu)造方法，并 構(gòu)造出一種高性能的特征選擇方法，并用試驗(yàn)驗(yàn)證。 第五章分析了弱分類(lèi)器的分類(lèi)效果較差的原因和一些改進(jìn)的算法，并指出了弱 文本分類(lèi)器改進(jìn)的方向。 第六章總結(jié)與展望，對(duì)本文工作進(jìn)行總結(jié)，指出下一步工作的方向。 3 華北電力大學(xué)碩士學(xué)位論文 第二章特征選擇及文本分類(lèi)綜述 2 1文本的表示方法 計(jì)算機(jī)并不能讀懂文章，從根本上說(shuō)，它只認(rèn)識(shí)0 和1 。因此，跟所有機(jī)器學(xué)習(xí) 問(wèn)題一樣，要想讓計(jì)算機(jī)自動(dòng)對(duì)文本進(jìn)行分類(lèi)，就需要把一篇文本表示成一個(gè)個(gè)特 征，比如詞( 包括字) 、n - g r s m 、詞組、概念等等。下面介紹文本的表示方法。 2 1 1 詞 詞是應(yīng)用的最廣范的特征。對(duì)于英文或相似語(yǔ)種來(lái)說(shuō)，由于單詞之間由空格或 標(biāo)點(diǎn)符號(hào)隔開(kāi)，因而取得英文單詞是非常容易的。對(duì)于中文而言，詞與詞之間沒(méi)有 明顯的界限，取得詞就比較困難，需要進(jìn)行分詞。 通常在文章中會(huì)有很多詞對(duì)于文章的內(nèi)容沒(méi)有很大的影響，例如中文中的“的、 地、得”，英文中的“a ，a l l ，t h e ”等等，這些詞我們稱(chēng)之為停用詞，為了文本分 類(lèi)的速度，我們會(huì)在預(yù)處理階段把停用詞都去掉。 由于英文中存在各種時(shí)態(tài)、語(yǔ)態(tài)及名詞的單復(fù)數(shù)，因此英文單詞常常有多種形 式，如m a k e 就可以以四種形式出現(xiàn)，即m a k e 、m a k e s 、m a k i n g 、m a d e 。但是這些形 式都基本表示一個(gè)意思，于是，人們常常借助于詞干還原來(lái)壓縮詞空間。 2 1 2 n - g r a m 在英語(yǔ)等西方語(yǔ)言中顯得非常簡(jiǎn)單的分詞問(wèn)題，在漢語(yǔ)等亞洲語(yǔ)言中卻顯得十 分困難。因?yàn)榉衷~是一項(xiàng)非常復(fù)雜的工作它的性能常常依賴(lài)于詞典的質(zhì)量與規(guī)模； 另外，鑒于語(yǔ)言的領(lǐng)域相關(guān)性和隨時(shí)間變化的特性，采用詞語(yǔ)作為文檔屬性的方法 和系統(tǒng)需要不斷修正和擴(kuò)充詞典，并改進(jìn)分詞技術(shù)，以適應(yīng)語(yǔ)言環(huán)境變化因此， 獨(dú)立于語(yǔ)言的文本表示方式一字符串( n 掣a m ) 方式l2 l 逐步受到人們的重視。字符串方 式根本不考慮組成文本的語(yǔ)義單位是字、詞還是詞組，而是將整個(gè)文本看成是由不 同字符組成的字符串，因而可以方便地表示包括漢語(yǔ)、阿拉伯語(yǔ)在內(nèi)的各種語(yǔ)言文 本文檔。在著名的t r e c 5 和t r e c 5 中，人們作了幾組實(shí)驗(yàn)，用以比較基于詞的 中文信息檢索和基于n g r a m 的中文信息檢索例。實(shí)驗(yàn)結(jié)果表明，兩種方法可得到近 似的檢索效果。但n g r a m 也有其不足之處。一個(gè)顯著的缺點(diǎn)就是它的計(jì)算量大。同 時(shí)n g r a m 表示還存在著數(shù)據(jù)噪聲大、易于過(guò)學(xué)習(xí)等缺點(diǎn)。 此外，還有詞組、概念等表示方法，詳細(xì)介紹請(qǐng)參考文獻(xiàn)【4 l 【5 】【6 】用。 4 華北電力大學(xué)碩士學(xué)位論文 2 2 降維技術(shù) 文本分類(lèi)中存在兩大難題，即數(shù)據(jù)的“高維性”和“稀疏性”，這兩個(gè)問(wèn)題在 時(shí)間和精度上影響著文本分類(lèi)的結(jié)果。因而，文本特征空間的降維就有著重要的現(xiàn) 實(shí)意義。文本空間的降維技術(shù)主要有兩類(lèi)；特征選擇和特征提取( 特征重構(gòu)) 。 2 2 1 特征選擇 特征選擇就是透過(guò)某種選擇標(biāo)準(zhǔn)，去除對(duì)文本分類(lèi)貢獻(xiàn)較小的特征從而達(dá)到降 維的且的。主要的特征選擇方法有：文檔頻率、信息增益、互信息、期望交叉熵、 文本證據(jù)權(quán)、奇異率、x 2 統(tǒng)計(jì)量。 ( 1 ) 基于文檔頻率( d o c u m e n tf r e q u e n c y ) 方法 d f 是指在語(yǔ)料集中包含某個(gè)詞條的文檔數(shù)目通過(guò)統(tǒng)計(jì)語(yǔ)料集中每個(gè)詞條的 d f 值，去除d f 值小于預(yù)定閥值的詞條。d f 是一種經(jīng)驗(yàn)方法，并沒(méi)有明確的理論解 釋( 稍候給出一種基于粗糙集的d f 的理論解釋) ，但是因?yàn)閐 f 方法簡(jiǎn)單，執(zhí)行效 率較高，效果與復(fù)雜的統(tǒng)計(jì)學(xué)方法相差不多，因而也有較廣的應(yīng)用 ( 2 ) 互信息( m u t u a li n f o r m a t i o n ) 項(xiàng)t 和類(lèi)c 之間的互信息定義如下： m ，( f ，c ) - i o g2p ( f c ) 一i o g2p ( f ) “等 倍- ， 乩g ：揣 對(duì)予一個(gè)項(xiàng)t 和一個(gè)類(lèi)c ，我們可以得到如下數(shù)據(jù)：a 為項(xiàng)t 在文本中出現(xiàn)并且 該文本屬于類(lèi)c 的文本數(shù)，b 為項(xiàng)t 在文本中出現(xiàn)但該文本不屬于類(lèi)c 的文本數(shù)，c 為項(xiàng)t 在文本中沒(méi)有出現(xiàn)但該文本屬于類(lèi)c 的文本數(shù)，d 為項(xiàng)t 在文本中沒(méi)有出現(xiàn)而 該文本不屬于類(lèi)c 的文本數(shù)。如表2 - 1 所示。 表2 - 1 項(xiàng)、類(lèi)關(guān)系表 cc t a b f cd 設(shè)n 為u i l 練文本的總數(shù)，則我們可以用下面的公式來(lái)近似的表示項(xiàng)t 和類(lèi)別c 5 華北電力大學(xué)碩士學(xué)位論文 之間的互信息： 柳( f ，c ) - l 0 9 2 麗百a x 麗nj ( 2 - 2 ) 式( 2 - 2 ) 表示的是一個(gè)項(xiàng)和一個(gè)類(lèi)別之間的互信息，而我們通常用平均互信 息和最大互信息來(lái)衡量一個(gè)項(xiàng)和語(yǔ)料集之間的互信息： m i 舶) - 藝p ( c f m ( f ，q ) ( 2 3 ) 柳一( f ) i m ，q ) ) ( 2 4 ) 互信息的缺點(diǎn)在于，沒(méi)有考慮項(xiàng)出現(xiàn)的頻率，在很大程度上會(huì)受到項(xiàng)的邊緣分 布的影響，由前面的公式可知，在條件概率相同的情況下，稀有詞匯將獲得更高的 互信息量，從而造成了互信息評(píng)價(jià)函數(shù)常傾向于選擇稀有單詞，因而這種方法不適 合于對(duì)那些出現(xiàn)頻率差別很大的項(xiàng)進(jìn)行比較評(píng)估。 ( 3 ) 信息增益( i n f o r m a t i o ng a i n ) 方法 信息增益是通過(guò)計(jì)算一個(gè)詞項(xiàng)能帶來(lái)多少用于分類(lèi)的信息，來(lái)衡量詞項(xiàng)對(duì)于分 類(lèi)的重要度。 設(shè)s 是n 個(gè)文本構(gòu)成的訓(xùn)練集合。c ： c 1 ，c 2 ，q ) 為類(lèi)別集合。設(shè)墨是s 中屬于 類(lèi)別a 的文本數(shù)，則一個(gè)文本關(guān)于其類(lèi)別的熵( 即期望不確定度) 為： 7 瓴，礦，凡) - 一著p f l o g z ) ( 2 - 5 ) 其中，a 是任意樣本屬于類(lèi)q 的概率，該概率可用墨s 來(lái)估計(jì)。 設(shè)根據(jù)項(xiàng)t 是否在文本中出現(xiàn)，可把樣本集分為兩類(lèi)，一類(lèi)a 是t 在其內(nèi)容中 出現(xiàn)了的文本，另一類(lèi)b 是t 沒(méi)有在內(nèi)容中出現(xiàn)的文本。則a 類(lèi)中的文本關(guān)于其類(lèi) 別的熵為： e ( f ) - 一善p i f ) 1 0 9 ：p l f ) ( 2 - 6 ) 其中，p i f ) 表示當(dāng)t 出現(xiàn)在文本中時(shí)，文本屬于類(lèi)q 的概率，可以用a 中屬 于類(lèi)q 的文本數(shù)與a 中所有的文本數(shù)的比值來(lái)估計(jì)與之類(lèi)似，b 類(lèi)中的文本關(guān)于 其類(lèi)別的熵為：t e ( - ) 一一吝p 瓴l - ) l o g ：p ( c l i 乃 6 ( 2 - 7 ) 華北電力大學(xué)碩士學(xué)位論文 其中，p i f ) 表示當(dāng)t 沒(méi)有出現(xiàn)在文本中時(shí)，文本屬于類(lèi)別q 的概率，可用b 中屬于類(lèi)c 。的文本數(shù)與b 中所有文本數(shù)的比值來(lái)估計(jì)。 因而，如果訓(xùn)練文本集按項(xiàng)t 來(lái)劃分的話，文本關(guān)于其類(lèi)別的熵將變?yōu)椋?，( f ) - p o ) e o ) + p ( f ) e ( f ) 一p ( f ) 多p i t ) l o g ：p 心i t ) 一p ( - ) 窆p ( c fi t ) l o g ：p i - ) ( 2 8 ) 其中，p ( t ) 為項(xiàng)t 在文本中出現(xiàn)的概率，可用l a i s 來(lái)估計(jì)，p ( t ) 為項(xiàng)t 不在 文本中出現(xiàn)的概率，可用l b l s 來(lái)估計(jì)。一般情況下，此時(shí)的熵將比原來(lái)的熵 i ( s l ，s 2 ，s n ) 更小，即這個(gè)項(xiàng)給我們提供了一定的信息，使得分類(lèi)時(shí)的不確定 程度降低了。它提供的信息量的多少可以用信息增益來(lái)表示： r e ( t ) i x ( s x ，屯，) 一x ( o 哪) 砉p ) l 0 9 2 雩學(xué)+ p ( - ) 砉p 1 0 9 ：號(hào)學(xué) 。， 信息增益的不足之處在于，它考慮了項(xiàng)未出現(xiàn)的情況，即( 2 - 9 ) 的右邊后半 部分。雖然某個(gè)項(xiàng)不出現(xiàn)也可能對(duì)判斷文本類(lèi)別有貢獻(xiàn)，但實(shí)驗(yàn)證明【羽，這種貢獻(xiàn) 往往遠(yuǎn)遠(yuǎn)小于它所帶來(lái)的干擾，特別是在類(lèi)分布和項(xiàng)分布高度不平衡的情況下。對(duì) 某一類(lèi)來(lái)說(shuō)，絕大多數(shù)項(xiàng)都是“不出現(xiàn)”的，即p ( t ) p ( t ) ，此時(shí)信息增益的 主要部分是信息增益公式中后一部分( 代表項(xiàng)不出現(xiàn)的情況) ，而不是前一部分( 代 表項(xiàng)出現(xiàn)的情況) ，這時(shí)信息增益的效果就會(huì)大大降低了。通過(guò)實(shí)驗(yàn)得到，原始t f i d f 法的分類(lèi)精度為7 3 ，用信息增益進(jìn)行特征選擇后精度提高到8 2 ，但在處理上述 。高度不平衡”數(shù)據(jù)集時(shí)，精度下降到7 5 。 上面三種特征選擇方法是最常用和效果效率較好的特征選擇方法，剩余的像期 望交叉熵、文本證據(jù)權(quán)、奇異率、x 2 統(tǒng)計(jì)量等特征選擇方法這里就不詳細(xì)介紹了， 有興趣的讀者可以參考文獻(xiàn)【9 】。 2 2 2 特征提取 特征提取( f e a t u r ee x t r a c t i o n ) 又稱(chēng)綜合評(píng)估法，它是將原有的特征集t 加以 聯(lián)系和轉(zhuǎn)化以構(gòu)建新特征集t 的過(guò)程，一般i t l 1 ，那么w ( 1 ，n 2 ) = w ( 1 ，1 ) + w ( 1 ，2 - 1 ) ( 由定義1 ( 5 ) 知) = 1 + w ( 1 ，n 2 1 ) ；= 1 1 2 同樣的，w ( n l ，n z ) = w ( n 2 ，n 1 ) ( 由定義1 ( 3 ) 知) = w ( 1 1 2 , 1 ) + w ( n 2 ，n 1 1 ) = = n l w ( n 2 ，1 ) = n l w ( 1 ，n 2 )- - n l x n 2 = 羅弗fx 捍， l f 乃2 所以等式成立。 當(dāng)m 一1 拍2 時(shí)w ( n 1 ，1 1 2 ，s i n 1 ) = 羅廳f 廳，那么 w ( n l ，n 2 ，n m ) = w “l(fā) 訂：_ 一l b b n 2 + + n m n 叭n 2 ，n 2 ”n m b n l “n 2 + + n m ) + ：渤煳廠。澀枷， ( 由定義i ( 4 ) 知) 由歸納法可知原等式成立。 5 d f 的粗糙集的具體解釋 下面我們給出d f 的粗糙集的具體解釋。 給出一個(gè)文本分類(lèi)的信息系統(tǒng)的四元組 ，u - - d 。d 。 為文檔集合， 1 3 華北電力大學(xué)碩士學(xué)位論文 a = t l ，“，t 。 為特征( 詞條) 集合， 為一個(gè)u v 的信息函數(shù)： l 3 a 毪：搬潛叭i v 是t 。( 1 i k ) 的取值范圍，v _ 0 ，1 ，f ( 3 - 1 ) 表3 1 是一個(gè)信息表的例子，每一行代表每一個(gè)類(lèi)別d i ，d 。d 。，每個(gè)文檔 的屬性t l ，t 。t 。，l ，t i 代表詞條( 特征) 。 表3 - 1 一個(gè)文檔的信息表 ! !1 2b旦 d t o 0 1l d ，o1o1 d 3 1 o1 1 d 4 0011 d so00 1 d o1o1 在表3 - 1 中，t 。只在d 。中出現(xiàn)，t 將 d 。，d ：，d b ) 劃分成兩個(gè)等價(jià)類(lèi) d 。，d 。，d 。， d 。，d 。 和 d 。 ，每個(gè)等價(jià)類(lèi)中文檔的數(shù)目分別為n l = 5 ，r l z = 1 。 根據(jù)定理1 ，t l 對(duì)于 d 。d ：d 。 的區(qū)分能力( t 。的知識(shí)量) 為 礦k 翟刑，。5 姐。5 。 同樣的：乃24 2 = 8 ，乃23 x 3 = 9 ，l 廳，2 0 7 ，r 3 以 丑 丑 u 代表一個(gè)語(yǔ)料集中的所有文檔，n 代表u 中的文檔數(shù)目，m 代表文檔中出現(xiàn) 詞條t 的文檔個(gè)數(shù)，那么t 的知識(shí)量定義為： ，。= w ( 1 ，1 ) m ( n m )( w ( 1 ，1 ) 是一個(gè)常量) ( 3 2 ) 在式( 3 2 ) 中。= w ( 1 ，1 ) m ( n m ) a ( n m ) 表明： ( 1 ) 當(dāng)r e = n 2 時(shí)，形r 。最大。 ( 2 ) 如果m 1 啦s n 2 ，那么矸0 山山 ( 3 ) 如果m l m m 2 n 2 ，那么， 矸0 ，： 我們計(jì)算訓(xùn)練集中每個(gè)詞條的知識(shí)量并且去除特征空間中知識(shí)量小于某一個(gè) 預(yù)定閥值的詞條，這就是我們提出的不考慮詞條頻率的基于粗糙集的特征選擇方 法。詞條的信息量排列和d f 排列是相同的。這就是d f 方法的解釋。 3 3 改進(jìn)的d f d f 沒(méi)有考慮詞條頻率，在一個(gè)文檔中出現(xiàn)多次的詞條可能比只出現(xiàn)一次的詞條 1 4 華北電力大學(xué)碩士學(xué)位論文 有更多的信息，因而我們把文檔分為3 個(gè)等價(jià)類(lèi)而不是2 個(gè) 給定一個(gè)四元組 代表信息系統(tǒng)，u = d b ，d 。 為文檔的集合，a = t 。，t 。 為特征( 詞條) 集合，v 是t 。( 1 $ i k ) 的取值范圍，v = 0 ，1 ，2 ) ，定義一 個(gè)信息函數(shù)f ，u v ： f ( d 3 ；e ：竺翟竺竺& ，一加島。鼬脅( 3 - 3 ) 表3 2 給出一個(gè)這樣的信息表的例子 表3 - 2 文檔信息表( 考慮詞條頻率) 在表3 - 2 中，詞條t ，在d - 和d 5 中出現(xiàn)一次，t 2 在d l 中出現(xiàn)一次，在d 5 中出 現(xiàn)不止一次，t l 和t ：的文檔頻率相同，但是 曠。融舢，觀娟。8 礦 = ( 1 x l + l x 4 + 1 x 4 ) = 9 ， ，馬 ，五 1 3 代表語(yǔ)料中的文檔數(shù)目，詞條t 把文檔分成3 個(gè)等價(jià)類(lèi)，這三個(gè)等價(jià)類(lèi)中的 文檔數(shù)目分別為n 。r t 。，1 1 。，n t 代表t 沒(méi)有出現(xiàn)的文檔數(shù)目，n 2 代表t 只出現(xiàn)一次的文 檔數(shù)目，m 代表t 至少出現(xiàn)一次的文檔數(shù)目。t 的知識(shí)量可以定義為； 廠，。薈y 雄，( 3 - 4 ) 對(duì)于訓(xùn)練集，我們按照( 3 4 ) 式計(jì)算每個(gè)詞條t 的d v ( t ) ，并對(duì)所有的詞條排序， 去掉特征空間中值較低的詞條。這就是我們改進(jìn)的d f 方法，稱(chēng)之為i m p r o v e d d f 。 3 4 改進(jìn)的信息增益 改進(jìn)的信息增益通過(guò)一個(gè)詞條在文檔中出現(xiàn)一次、多次還是沒(méi)有出現(xiàn)來(lái)計(jì)算分 類(lèi)的信息量?；?。代表目標(biāo)空間中的類(lèi)別集合，毛代表t 出現(xiàn)一次，f 2 代表t 出現(xiàn) 多次。那么t 的信息增益定義為： g ( f ) 一一：= i b 如) 1 0 9p ，( c j ) + p ，6 ) 墨p ， i ；) l o g p ，( c li - ) 1 5 霄 華北電力大學(xué)碩士學(xué)位論文 + p ，瓴) = d b t z ) l o g p , ( qi ) + b ( f 2 ) 二p ，( c l t 2 ) l o g p , ( qi t 2 ) ( 3 - 5 ) 這就是我們改進(jìn)的i m p r o v e d i g 方法。 3 5 改進(jìn)的互信息 對(duì)于給定的類(lèi)別c 和一個(gè)詞條t ，a 。表示c 類(lèi)文檔中包含t 的文檔個(gè)數(shù)( t 只出 現(xiàn)一次) ，a 2 表示c 類(lèi)文檔中包含t 的文檔個(gè)數(shù)( t 至少出現(xiàn)兩次) 。b l 表示非c 類(lèi) 文檔中包含t 的文檔個(gè)數(shù)( t 只出現(xiàn)一次) ，b 2 表示非c 類(lèi)文檔中包含t 的文檔個(gè)數(shù) ( t 至少出現(xiàn)兩次) ，c 表示c 類(lèi)文檔中不包含t 的文檔個(gè)數(shù)，n 表示c 中所有文檔 的數(shù)目。那么t 和c 之間的互信息定義為： 地，c ) 一l o g p ，p 博 ( j t l 。 肼c 西) ，斷) - l o g 而p r 萬(wàn)0 2 云c 麗) ( 3 - 6 ) - 7 以近似的表示為： c ) - l o g 幣 j ) 禮g 瓦麗a 2 麗x n 那么平均互信息為： k ( f ) - 三。b v 瓴，q ) + ：。p ，( c i v 也，q ) 這就是我們改進(jìn)的i m p r o v e d - m i 方法。 3 6d f 的進(jìn)一步改進(jìn) ( 3 7 ) ( 3 8 ) ( 3 - 9 ) 本文上面利用t f 信息對(duì)d f 進(jìn)行改進(jìn)的部分，只是將文檔分成三個(gè)等價(jià)類(lèi)，將 詞條出現(xiàn)一次的等價(jià)類(lèi)和出現(xiàn)多次的等價(jià)類(lèi)同等對(duì)待，而事實(shí)上，我們認(rèn)為詞條出 現(xiàn)多次的等價(jià)類(lèi)比出現(xiàn)一次的等價(jià)類(lèi)重要，由于公式( 3 - 4 ) 為一個(gè)遞增函數(shù)，因而 我們可以進(jìn)一步改進(jìn)加入1 1 f 信息的d f 方法。 d f ( 0 一( ，l lx l 2 + c ( x n 3 + n 2 塢) ) ( 3 1 0 ) 其中c 1 。 由語(yǔ)料的分布特點(diǎn)我們可以預(yù)測(cè)c 為大于1 的值，而且隨著c 值的增大，起初 t f 值大的詞條的權(quán)重排名會(huì)逐漸增加，也就是說(shuō)在用d f 特征選擇方法進(jìn)行特征選 擇時(shí)，d f 值相近而 i t 值大的特征會(huì)被首先選擇出來(lái)，而隨著c 的值逐步增大，會(huì) 】6 華北電力大學(xué)碩士學(xué)位論文 有一個(gè)臨界點(diǎn)，在c 達(dá)到這個(gè)臨界點(diǎn)后，特征選擇的排名會(huì)在一個(gè)基本穩(wěn)定的狀態(tài)， 在分類(lèi)效果的曲線上我們可一看到前面是一個(gè)向上的曲線而后基本是一條直線。 3 7 試驗(yàn)結(jié)果及分析 3 7 1 語(yǔ)料集及分類(lèi)器 在這個(gè)試驗(yàn)中我們使用的語(yǔ)料集為r e u t e r - 2 9 ，它是路透社1 9 8 7 間播發(fā)的2 1 ，5 7 8 篇財(cái)經(jīng)新聞。每篇新聞可能屬于一個(gè)或多個(gè)類(lèi)別。最多的達(dá)1 6 個(gè)，平均1 2 個(gè)。而且 這2 1 。5 7 8 篇財(cái)經(jīng)新聞還