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

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