文本分類中改進的特征加權(quán)方法_圖文

1、收稿日期 :2008-09-18 修回日期 :2008-10-28基金項目 :山東省中青年科學家科研獎勵基金項目 個性化智能商務服務中心的談判技術(shù)研究 (編號 :2006BS01021 。作者簡介 :趙中英 , 女 , 1983年生 , 博士研究生 , 研究方向為人工智能 ; 梁永全 , 男 , 1967年生 , 教授 , 博 士生導師 , 研究方向 為人工智 能、 電子商 務 ; 紀淑娟 , 女 , 1977年生 , 博士 , 碩士生導師 , 研究方向為人工智能、 電子商務 ; 李 超 , 男 , 1984年生 , 碩士研究生 , 研究方向為人工智能。文本分類中改進的特征加權(quán)方法*A Mod

2、ified Feature Weighting Approach in Text Classification趙中英 梁永全 紀淑娟 李 超(山東科技大學信息科 學與工程學院 青島 266510摘 要 針對科研論文往往具有統(tǒng)一的結(jié)構(gòu) , 將詞 項的位置信息考慮在內(nèi) , 給出一種新的詞 項特征加權(quán) 方法 。 利用 A daBoosting 分類算法進行實驗 , 結(jié)果表明該方 法在準確率 、 查全率和 F -M easure 方面都具有更好的文本分類性能 。 關(guān)鍵詞 文本分類 預處理 特征加權(quán)中圖分類號 T P182 文獻標識碼 A 文章編號 1002-1965(2009 04-0147-03文本

3、分類是指基于文本內(nèi)容將待定文本劃分到一 個或多個預先定義的類中。一般來講 , 文本分類需經(jīng) 過四個步驟 :獲取訓練文本集 ; 選擇分類方法并訓練分 類模型 ; 用訓練的分類模型對待分類文本進行分類 ; 根 據(jù)分類結(jié)果評價分類模型。文本分類的效果一般與數(shù) 據(jù)集本身的特點有關(guān)。目前普遍認為不存在某種方法 適用于各種特點的數(shù)據(jù)12。針對科研論文具有統(tǒng)一的模式或結(jié)構(gòu) , 特征詞項 所處的位置往往更能反映該文本所屬的類別 , 我們引 入詞項的位置信息 , 對傳統(tǒng)的 T F-IDF 特征加權(quán)方法 進行改進 , 并用實驗對改進后方法的分類性能進行評 價。文章第一節(jié)介紹幾種主要的文本分類方法 ; 第二 節(jié)對文

4、本預處理的主要步驟進行闡述 ; 第三節(jié)引入特 征詞的位置信息 , 給出改進的特征加權(quán)方法 ; 第四節(jié)設(shè) 計實驗 , 對改進的特征加權(quán)方法的分類性能進行評價。1 已有的文本分類方法1. 1 樸素貝葉斯方法 樸素貝葉斯方法是最早用 于文本分類的分類器算法 , 概率分類器基于貝葉斯理 論來計算待定文檔 d j 與已知各類的條件概率 , 用 P(c i |d j 來表示 :P(c i |d j =P(c P(d |c P (d j 其中 P(d j 對計算結(jié)果無影響 , 因此可以不計算。 貝葉斯方法的基本假設(shè)是詞項之間的獨立性 , 于是P(d j |c i =rk =1P(w k j|c i P(c

5、i 和 P(w k j |c i 可用以下公式來估算 :P (c =c i =n ig P (w k j |c i =1+n ki r +k =1n k i其中 , n i 為類 c i 中的文檔數(shù)目 , n ki 為詞項 t k 在類 c i中出現(xiàn)的詞頻總數(shù)?；谏鲜黾僭O(shè)的概率分類器一般稱為貝葉斯分類 器。貝葉斯分類器是應用比較廣泛的文本分類器 , 在 很多文獻中都有出現(xiàn) 34。貝葉斯分類器易于理解 ,計算簡單 , 分類效果基本能滿足要求 , 但其關(guān)于詞項獨 立性的假設(shè)受到很多研究者的質(zhì)疑 5。1. 2 基于實例的文本分類 基于實例的分類器又 稱 懶惰學習系統(tǒng) , 這種方法不對類別建立明確的

6、、 直接的表達 , 而是依賴于訓練集文檔的分類來推斷待 定文檔的類別 68。最常見的基于實例的分類器為 K NN 分類器 , 其基本思想是 :給定一個測試文檔 , 系統(tǒng) 在訓練集中查找離它最近的 k 個鄰居 , 根據(jù)這些鄰居 的分類來給該文檔的候選分類評分 , 并用鄰居與文檔 d j 之間的相似度來加權(quán)。 文檔之間的相似度衡量可用 基于向量的評價和概率評價來完成 , 其閾值 k 的確定 一般通過實驗的方法來進行 , 即通過校驗集來確定該 值。1. 3 支持向量機 (SV M 支持向量機 (Support V ector M ac hines, SVM 由 V apnik 在 1995年提出 ,

7、 用 于解決二分類模式識別問題 9。 Joachims 最早將 SV M第 28卷 第 4期 2009年 4月 情 報 雜 志 JOURNAL OF INT ELL IGENCEVol. 28 N o. 4Apr. 2009方法用于文本分類 8。支持向量機集成了降維和分 類 , 它將文本分類問題變?yōu)橐幌盗卸诸悊栴}。 SV M 方法有很堅實的理論基礎(chǔ) , SVM 訓練的本質(zhì)是解決一 個二次規(guī)劃 (QP 問題 , 得到的是全局最優(yōu)解 , 這使它 有著其他統(tǒng)計學習技術(shù)難以比擬的優(yōu)越性。 SV M 分 類器的文本分類效果很好 , 是最好的分類器之一。其 缺點是核函數(shù)的選擇缺乏指導 , 難以針對具體問

8、題選 擇最佳的核函數(shù) ; 另外 SVM 訓練速度極大地受到訓 練集規(guī)模的影響 , 計算開銷比較大 , 針對 SVM 的訓練 速度問題 , 研究者提出了很多改進方法 , 包括 Chunking 方法10、 Osuna 算法11以及 SM O 算法12。1. 4 神經(jīng)網(wǎng)絡(luò) 神經(jīng)網(wǎng)絡(luò) (Neural Net work, N Net 技術(shù)是人工智能中的成熟技術(shù)。神經(jīng)網(wǎng)絡(luò)由一組神經(jīng) 元組成 , 其輸入單元通常代表詞項 , 輸出單元表示類別 或類別興趣度 , 神經(jīng)元的連接權(quán)重表示條件依賴關(guān)系。 Wiener 和 N g 曾分別將該技術(shù)用于文本分類 , 文檔向 量權(quán)重通常作為輸入 , 其訓練通常用 BP 算

9、法來進行 , 時間開銷一般很大 13。2 文本預處理已有的文本表示模型有 :布爾模型、 向量空間模 型、 概率模型、 基于知識的模型等 , 而向量空間模型 (VSM 將文本內(nèi)容形式化為高維空間中的一個點 , 并 以向量的形式表示 , 大大提高了自然語言文本的可計 算性和可操作性。本節(jié)將采用向量空間模型表示文 本?；谙蛄靠臻g模型的文本預處理主要分為以下幾 個步驟 :詞干抽取 :詞干抽取是將文本中具有相同或相近 的單詞合并成一個語義單元或詞項的過程 , 主要有兩 種方法 :基于規(guī)則的方法和基于詞典的方法。前者依 據(jù)一定的規(guī)則逐個剝離單詞的后綴得到能表達基本含 義的詞根。后者是將所有含義相同的單詞

10、歸為一類 , 并編制專門的同義詞詞典。去停用詞 :去停用詞指的是那些出現(xiàn)頻率很高但 對文本分類卻沒有太大作用的單詞 , 如 :a, an, the, of 等。特征選取 :為降低文本特征空間的維數(shù) , 需進行特 征選取。目前已經(jīng)出現(xiàn)了很多特征選取方法 :信息增 益、 期望交叉熵、 互信息、 單詞權(quán)、 文檔頻、 2統(tǒng)計等。 信息增益被證明是最為有效的特征選擇方法之一 , 它 能在不降低文本分類性能的前提下移走高達 98%的 單詞 14。特征加權(quán) :特征選取之后得到的詞項對文檔分類 的影響往往是不同的 , 有些詞項區(qū)分類別的能力強 , 有 步的加權(quán)處理 , 最常用的算法是 TF-IDF 方法。 T

11、F-IDF 算法依據(jù)每個詞的詞頻 (T erm Frequency 和其出 現(xiàn)過的文檔頻 (Doc ument Frequency 來計算該詞在整 個文本集中的權(quán)重。標準 T F-IDF 加權(quán)的計算公式 為 :T F-IDF (t k , d j =T F (t k , d j IDF (t k , d j 即 :T F -IDF (t k , d j =T F (t k , d j log|D |DF (t k 其中 , T F (t k , d j 表示詞項 t k 在文檔 d j 中出現(xiàn)的 頻率 , |D |是文檔總數(shù) , DF (t k 是在所有文本中詞項 t k 出現(xiàn)的頻率。由該公式

12、可得 :一個單詞在一個文本 中出現(xiàn)的次數(shù)越多 , 它的權(quán)重就越高。一個單詞在越 多的文本中出現(xiàn) , 它的重要性就越低。這種方法對信 息檢索來說是有效的 , 但是對于文本分類和聚類來說 并不那么有效。對于文本分類和聚類來說 , 文檔頻率 高的單詞比文檔頻率低的單詞更為重要 14, 這點與信 息檢索中的 IDF 觀點正好相反。3 改進的特征加權(quán)方法考慮到我們平時所閱讀的科研論文或科研書籍往 往具有統(tǒng)一的結(jié)構(gòu) , 我們引入位置信息來提高文本分 類的性能。 S. Teufel 和 M. M oens 指出 , 在科學文獻 中 , 作者往往會遵循一定的模式來表達自己的觀點。 引言和結(jié)論中往往會表達作者的

13、主要思想 , 題目、 摘要 和關(guān)鍵詞描述的是最核心的想法。這種位置信息已經(jīng) 被研究者們用于自動摘要生成方法中 1516。我們利用詞項的位置信息來改進 TF -IDF 加權(quán) 方法。在某個類內(nèi) , 主要的特征詞項往往會出現(xiàn)在該 類的所有文檔中 , 因此 IDF 已經(jīng)不再適用 , 我們將其去 掉。另外 , 如果某個詞項在標題、 摘要、 關(guān)鍵詞中都有 出現(xiàn) , 說明該詞項對該文檔的分類越重要。下面將給 出新的詞項 t k 的權(quán)重計算公式 :w eigh (t k , d j =(1+log 2(1+N (t i *TF (t k , d j 其中 , N (t i 表示 t i 在標題、 摘要、 關(guān)鍵

14、詞中所出 現(xiàn)的總次數(shù)。 由公式可得 , 若 t k 沒有出現(xiàn)在標題、 摘要、 關(guān)鍵詞中 , 即 N (t k =0, 則 weigh (t k , d j =TF (t k , d j 。 若 t k 出現(xiàn)在標題、 摘要、 關(guān)鍵詞中 , 且出現(xiàn)的次數(shù) 較多 , 則說明 t i 對該文檔的分類越重要 , 因此 weigh i 越 高。即對于通常詞項的權(quán)重 , 我們只考慮了詞頻 , 摒棄 了反文檔頻率。對處于特殊位置 (標題、 摘要、 關(guān)鍵詞 的詞項 , 其權(quán)重會由它在這些位置出現(xiàn)的次數(shù)來決定 , 次數(shù)越多 , 權(quán)重越大。4 實驗驗證148 情 報 雜 志 第 28卷都有過擬合訓練樣本的傾向 ,

15、僅用訓練樣本的分類準 確率還不能完全反映出分類模型性能的優(yōu)劣。因此 , 通常采用保持 (holdout 和 k-折交叉驗證 (k-fold cross validation 兩種重采樣技術(shù)評價分類模型。針對 不同的目的 , 人們提出了許多文本分類評價指標 :精確 率和召回率、 BEP(Break-even point s 、 F-M easure 、 微 平均與宏平均等。本文采用交叉驗證方法 , 并從準確 率、 召回率和 F-M easure 方面來評價分類的性能。 4. 2 實驗設(shè)計及實驗結(jié)果 為了驗證我們改進的 特征加權(quán)方法 , 我們做了如下實驗。實驗采用的數(shù)據(jù) 集來自互聯(lián)網(wǎng) , 該數(shù)據(jù)集

16、包括 348篇全部被 EI 檢索的 人工智能類論文 , 論文的類別為 EI 檢索項 (main head ings , 這些論文分布于 以下四個類別 :Multi -agent System 、 Ont ology 、 Learning syst em 、 Dat a mining 。實驗 的評價采用三份交叉驗證方法。首先將整個數(shù)據(jù)集分 成三份 , 然后選擇其中的兩份進行訓練、 剩余一份做測 試 , 再把這三次的平均結(jié)果作為實驗結(jié)果。分類的評 價指標采用準確率、 召回率和 F-M easure 值。實驗工具 :wordsmith -4、 weak 3. 5. 7、 M atlab 6. 5。

17、實驗步驟 :a. 對數(shù)據(jù)集進行預處理 , 即將 pdf 格式 轉(zhuǎn)化為純文本格式 ; b. 利用 Porter Stemming 算法抽取 詞干 , 達到降維目的 ; c. 消除停止詞 , 在本實驗中 , 我 們采用 SM ART Project 所提供的停止詞列表 17; d. 采 用信息增益方法選取文本特征 , 利用改進的特征加權(quán) 方法計算出詞項的權(quán)重 , 得到文檔的兩種向量空間模 型 ; e. 使用 weka3. 5. 7中的 AdaBoosting 分類器對文檔 進行分類 , 并將我們的結(jié)果與傳統(tǒng)的方法進行比較 , 分 類的結(jié)果如圖 1和圖 2所示。由圖 1和圖 2可以看出 , 與傳統(tǒng)的

18、 T F-IDF 方法 相比 , 改進的特征加權(quán)方法在準確率、 查全率和 F-Measure 方面都有了明顯的提高 , 且一直保持在 0. 85以上 , 即改進的特征加權(quán)方法分類性能更好。圖 1 傳統(tǒng)的 T F-IDF 方法的分類性能圖 2 改進的特征加權(quán)方法的分類性能5 總 結(jié)本文將文 本表示 成向量 空間模 型 , 利 用 port er stemming 算法抽取詞干對文檔降維 , 使用信息增益實 現(xiàn)文檔的特征選取 , 針對科研論文的結(jié)構(gòu)性 , 將詞項的 位置信息考慮在內(nèi) , 給出一種新的詞項特征加權(quán)方法。 利用 AdaBoosting 分類器設(shè)計實驗測試其分類性能 , 并 與傳統(tǒng)的 T

19、F-IDF 方法進行比較 , 結(jié)果表明該方法在 準確率、 查全率和 F-Measure 方面都有了明顯提高。參 考 文 獻1 J Li, G Dong, K Ramamohanarao. M aking Use of the M ost Expressive Jumping Emerging Patterns for Classification C . In Pro ceedings of the Fourth Pacific-Asi a Conference on Know ledge Dis covery and Data M ining, 2000:220-2322 J Li, G D

20、ong, K Ramamohanarao. DeEps :Ins tance-Based Classifi cati on by Emerging Patterns J . Technical Report, Dept of CSS E, University of M elbourne, 20003 David D Lew is. Nave (Bayes at Forty:Th e Independence Assumpti on i n Information RetrievalC. In:Proceedings of 10th European Conference on M achin

21、e L earning (ECM L-98 , 1998:4-184 Yang Yiming, Liu Xin. A Re-Examination of Text CategorizationM ethods C . In:Proceedings of ACM SIGIR Conference on Re search and Development in Information Retrieval (SIGIR -99 , 1999:42-495 Sebasti ani F. A T utorial on Automated Text Categorizati onC. In:Proceed

22、ings of Argentinian Symposium Arti ficial Intelligence (ASAI -99, 1st , 1999:7-356 Yang Yiming. An Evaluation of S tatistical Approaches to T ext CategorizationJ. Journal of Information Retrieval, 1999, 1(1/2 :67-887 Li Y H, Jain A K. Classification of Text DocumentsJ. T he Computer Journal, 1998, 4

23、1(8 :537-5468 Joachims T. T ext Categori zation with Support Vector M achines:Learning With M any Relevant Features C .In :Proceedings of10th European Con feren ce on M ach i ne Learning (ECM L-98 ,(下轉(zhuǎn)第 153頁 由于 j , k 是非負整數(shù)解 , 由此易知 X 均為非負整 數(shù)解 , 若取 j =1, k =1, 則可得到 X =1, 2, 3, 1, 1, 1, 1, 1, 1, 1T 。 并

24、且 X 是從 M 0狀態(tài)到 M 1狀態(tài)的唯一解。 通過運行 N 可以驗證 , 存在變遷序列 T1, T 2, T 3, T 8, T 2, T 3, T 7, T 3, T 4, T 5, T 6, 說明 M 1是從 M 0可達的。 該 Petri 網(wǎng)中所有狀態(tài)的可達性 , 都可以通過上述方法 求得并且結(jié)果都證明了該 Petri 網(wǎng)建模系統(tǒng)的可達性。 Pet ri 網(wǎng)中有界性分析反映被模擬系統(tǒng)運行過程中 對有關(guān)資源的容量要求。作為 Petri 網(wǎng)從定義上對每 個庫所的容量無限制 , 但庫所 p 所表示的資源 , 在本系 統(tǒng)的設(shè)計分析中 , 是服務器的內(nèi)存 , 對于面向?qū)ο箝_發(fā) 中、 每一個標記

25、在系統(tǒng)中表示一個對象 , 每一個對象在 系統(tǒng)運行中都會暫存在內(nèi)存中 , 消耗一定的內(nèi)存。如 果某個庫所是無界的 , 那么無限累積的標記將會使系 統(tǒng)的內(nèi)存耗盡而系統(tǒng)崩潰 , 在本建模系統(tǒng)中 , 通過對系 統(tǒng)的可達性分析 , 運行狀態(tài)方程的解后 , 發(fā)現(xiàn)所有庫所 的界都是 1。 根據(jù) Petri 網(wǎng)有界性的定義 :設(shè) N =(S , T ; F, M 0 為一個 Pet ri 網(wǎng) , 如果每個都是有界的 , 則稱 N 為有界 Petr i 網(wǎng) , 稱 B (N =max B(s |為 Petri 網(wǎng) 的界 , 當 B(N =1時 , 稱 N 為安全的。 由此可見 , Big6信息問題解決模式的 P

26、etri 網(wǎng)建模不僅是有界的 , 而且 是安全的。通過以上基于 Pet ri 網(wǎng)的矩陣分析 , 根據(jù)有界性、 可達性的定義可知圖 2所構(gòu)建的基于 Big6教學過程的 Pet ri 網(wǎng)模型有界的、 安全的、 可達的 , 也說明了該流程 在實際工作中的可行性。3 結(jié) 論本文在對基于 Big6信息問題解決模式的個性化 的信息素養(yǎng)網(wǎng)上課程系統(tǒng)的分析和設(shè)計中 , 將 Big6信 息問題解決模式轉(zhuǎn)化為工作流問題 , 使用形式化的 Pet ri 網(wǎng)輔助建模 , 清晰地表達了 Big6教學過程的工作 流程 , 為下一步的基于 Big6信息問題解決模式的個性 化的信息素養(yǎng)網(wǎng)上課程系統(tǒng)的詳細設(shè)計奠定了良好的 基礎(chǔ)

27、。下一步工作將是再進一步細化用 Petri 網(wǎng)對信 息素養(yǎng)能力培養(yǎng)的每個階段的工作流的建模 , 以形成 層次 Petri 網(wǎng) , 并引入面向服務的架構(gòu)與工作流組合 , 使系統(tǒng)各子模塊的耦合度降低 , 以實現(xiàn)基于 Big6信息 問題解決模式的個性化的信息素養(yǎng)網(wǎng)上課程系統(tǒng)真正 實現(xiàn)多校聯(lián)合 , 共建共享的目標。參 考 文 獻1 王 帆 . 信息素養(yǎng)培養(yǎng)模式 Big6 對兩個 Big6課例的評述 J. 信 息技術(shù)教育 , 2004(11 :96-982 呂海蓮 , 劉建粉 , 李 波 . 美國高等教育信息素養(yǎng)能 力標準 對畢 業(yè)設(shè)計的啟示 J. 職業(yè)技術(shù)教育 , 2007(8 :84-863 W i

28、l Van der Aalst, Kees van Hee. 工作流管理 M . 北京 :清華大學 出版社 , 2004:1-324 吳哲輝 . Petri 網(wǎng)導論 M . 北京 :機械工業(yè)出版社 , 2006:1-125 彭奇志 . 學習型網(wǎng)絡(luò)信息素質(zhì)教育平臺的 研發(fā) J. 情報理論與實 踐 , 2007, 30(6 :812-8156 韓 濤 . 采用 任 務驅(qū) 動法 培 養(yǎng)學 生 信息 素養(yǎng) J . 天 津 教育 , 2007(11 :50-517 姚中平 . 信息素質(zhì)與 文獻檢索與利用 課 程教學改革的 研討 J. 上海高校圖書情報工作研究 , 2006, 16(2 :54-578 鄭

29、 萍 . 基于建構(gòu) 主義 的文獻 檢索 課網(wǎng) 絡(luò)教 學 J . 福建社 科情 報 , 2003(6 :51-52(責編 :白燕瓊 (上接第 149頁 Chemnitz, DE, 1998:137-1429 Vapnik V. Nature of Statistical Learning Theory (2n d edi tion M . New York:Springer Press, 200010Cortes C, Vapnik V. Support Vector Networks J . M achine Learning, 1995(20 :273-29711Osuna E, Freund R, Girosi F. An Improved T raining Algori thm for Support Vector M achines C. In:Proceed