基于粗糙集的文本分類研究

基于粗糙集的文本分類研究

　　摘 要：文本分類是信息檢索和數據挖掘等領域的研究熱點。在現有的一些文本分類方法中，文本都是基于向量空間模型表示的，所形成的特征空間維數相當高，導致分類算法效率不高，分類精度不理想。粗糙集應用到文本分類可以在不影響分類精度的條件下降低特征向量的維數，并且可以得到的顯式表達的分類規則。本文旨在介紹文本分類一般過程，分析將粗糙集理論應用到文本分類中關鍵步驟，總結粗糙集與其他分類算法結合應用到文本分類的情況。

　　關鍵詞：文本分類;粗糙集理論;屬性約簡

　　1. 引言

　　近年來隨著網絡和信息技術的發展，我們的工作和生活得到了極大的便利，可獲得的信息量急劇增長。但我們在得到便利的同時也被浩如煙海的數據所淹沒，想要快速有效的找到所需的內容也越來越困難，若用傳統的手工分類和處理不但耗費大量的人力和物力，而且在速度和精度方面也遠遠不能滿足要求，這對文本的分類技術提出了迫切的要求。

　　文本分類是信息檢索和信息智能處理的基礎，近年來受到了廣泛的關注，很多學者對此做了深入的研究。目前基于統計方法和機器學習的方法的已經應用到文本分類，并且取得了豐碩的成果。目前在文本分類中常用的分類方法有：樸素貝葉斯(Na?ve Bayes)、支持向量機(SVM)、決策樹、K-緊鄰(KNN)、人工神經網絡等。在文本分類中，廣泛使用向量空間模型(VSM)來表示文本。由于自然語言的復雜特性，文本的特征空間的維數會特別高，如中文字Bigram 特征集的大小高達上百萬，如此高維的特征空間使得一些算法無法進行或者效率非常低。為此有些系統在頻率統計的基礎上，使用閾值過濾掉一些特征來降低維數，但是這樣會造成信息的丟失，特別是對分類重要的低頻特征，從而影響了分類效果。

　　粗糙集理論(Rough Set)是由波蘭數學家Pawlak在1982 年提出的一種能夠處理不精確、不一致、不完整信息與知識的數學理論。粗糙集理論能夠有效的分析和處理不完備信息，已經成為一種重要的信息處理技術，并在機器學習、數據挖掘、決策支持與分析等方面得到了廣泛的應用。粗糙集理論是建立在分類機制的基礎上的，將分類理解為在特定空間上的等價關系，而等價關系構成了對該空間的劃分，粗糙集理論用上下近似來描述這種劃分。

　　上近似和下近似對應著確定屬于給定類的最大的對象集合和可能屬于給定類的最小的對象集合。通過其知識約簡理論得到屬性的最小子集，能夠很好的近似分類，并可以顯式表示分類規則。

　　本文主要介紹文本分類的一般過程與框架，粗糙集理論的特性以及應用到文本分類的可行性，然后分析基于粗糙集理論的文本分類模型。

　　2. 文本分類一般過程與框架

　　文本分類是基于文本的內容將未知類別標號的文本劃分到一個或者多個預先給定的類別中，從而提高信息檢索等應用的效率。文本分類的一般過程包括：文本的向量表示、特征降維、特征加權、分類器的構建與訓練、分類結果的評價與反饋等。圖1 是一個簡單的文本分類系統的簡單的框架圖，其中實線表示分類器建立過程中的數據流，虛線表示分類器測試過程中的數據流。

　　2.1 文本的向量表示

　　將文檔表示成計算機能處理的形式是進行文本分類的基礎工作，目前廣泛使用向量空間模型VSM 來表引文本，即把每個文本看作是由一系列特征詞構成的集合。這部分工作主要包括處理亂碼以及非文本內容、過濾停用詞、合并詞干、對中文文本進行分詞處理等。中文分詞技術目前比較有影響力的是中科院開發的漢語詞法分析系統(ICTCLAS)，目前已經在文本分類系統中得到廣泛應用。

　　2.2 特征降維

　　文檔經過預處理以后，其特征空間通常是高維空間，這會導致一些分類算法無法進行或者效率非常低，所以必須對特征空間進行降維處理。特征降維的方法主要有兩種：特征選擇和特征抽取。特征選擇就是從原特征集中選擇一個真子集作為其特征集，選擇的依據是特征對分類作用的大小，通常使用一個統計量來度量，如特征頻度、文本頻度、特征熵、互信息、信息增益、相關系數、Chi-square 等。特征抽取則是把高維的特征空間轉換成一個低維的特征空間，實現降維，常用的特征抽取方法有三類：特征聚類、主成分分析和潛在語義表引。特征降維不僅能夠大大降低處理開銷，而且在很多情況下可以改善分類器的分類效果。

　　2.3 特征加權

　　為了更準確的描述特征在文本中的重要性，在文本用向量表示后，需要對文本向量中的特征賦予一定的權重。這主要通過詞對分類的貢獻程度的分析，把分類貢獻大的特征賦予高的權值，而貢獻度小的或不相關的數據則賦予低的權值。采用合理特征加權方式有助于增大特征詞之間的差異、凸顯文本的特性和提高分類的精度。目前有很多權重函數來計算關鍵字在文檔向量中的權重，如布爾權重函數、TF-IDF 權重函數、ITC 權重函數、Okapi 權重函數等。

　　2.4 分類器的構建與訓練

　　選擇不同分類算法決定著分類器的性能好壞，目前基于統計方法和機器學習的文本分類比較成熟，在很多文本分類系統中得到應用。另外還有基于語義和概念網絡的文本分類方法，但是由于自然語言處理領域的研究進展相對較慢，所以在這方面還沒有太大發展。常用的分類算法有：支持向量機(SVM)、樸素貝葉斯(Na?ve Bayes)、K 近鄰方法(KNN)、Rocchio、TFIDF、決策樹、神經網絡等。

　　2.5 組合分類器

　　各種分類器都有自己分類優勢，如果將多個分類器的分類結果優化組合起來會比單個分類器的分類效果好。已有學者證明，如果單個分類器相互獨立，當分類器的個數趨于無窮時，組合分類器的分類錯誤會趨向于零。組合的策略主要有多數選舉、加權組合、動態分類器選擇和自適應分類器組合等。組合分類器已在文本分類系統中廣泛的應用，并取得了不錯的分類效果。

　　2.6 評價標準

　　文本分類的評價是通過實驗數據分析獲得的，在該部分把測試集中的每個文本進行預處理后，輸入到分類器進行分類。通過對分類結果的統計分析然后進行評價�，F在常用的評價標準有：準確率/召回率、break-even 點、F-measure、11 點平均準確率圖、精度/錯誤率等;另外還有微平均和宏平均分別用來描述一個類和全部類的分類情況。

　　2.7 數據集

　　在構建和測試文本分類系統的時候需要用到大量的文本資料，如果能使用一個標準的數據集進行研究，不僅可以減少建設數據集的費用，而且可以使得不同研究者的分類結果具有可比性�，F在國際上用于文本分類的英文標準數據集主要有以下幾個：Reuters-21578，OHSUMED，20Newsgroups 和TREC 等。目前為止還沒有標準的中文數據集，不過研究中比較常用的有搜狗語料庫、復旦大學中文語料庫和北京大學語料庫等等。

　　3. 基于粗糙集理論的文本分類模型

　　粗糙集理論是一種分析不確定知識的強有力的數學工具，可以對不精確、不一致、不完整等各種不完備信息進行有效分析和處理，并從中發現隱含的知識，揭示信息中潛在的規律。粗糙集理論研究的是不同類中的對象組成的集合關系，利用不可分辨關系進行分類[16~18]。無需提供除所需處理的數據集合外的任何先驗信息，對問題的處理比較客觀。通過對原始決策表的約簡，可以在保持決策一致(即分類能力不發生改變)的前提下對屬性進行約簡，可以大大降低特征向量的維數，從而方便處理提高效率。通過粗糙集理論進行分類，可以得到最約簡顯式表達的分類規則。

　　盡管粗糙集理論在處理不確定性不完備的信息有著不可替代的優勢，但是粗糙集理論也存在著某些片面性和不足。粗糙集理論模型要處理的分類必須是完全正確或肯定的，嚴格的按照等價類進行分類，所以在實際應用中多使用粗糙集理論的改進模型，如Ziarko[19]基于多數包含關系的提出的可變精度粗糙集模型等。

　　將粗糙集理論應用到文本分類模型，主要是利用了粗糙集理論對知識等價劃分的思想。

　　首先將文本的特征詞作為條件屬性，類別作為決策屬性，構建決策表;通過加權規則對特征值進行加權;然后對加權后的權值進行離散處理;再利用粗糙集理論的知識約簡在決策表中得到最分類規則;最后建立相應的匹配規則，通過對測試集分類對該分類器性能進行評估。

　　概括起來主要有四個步驟：文本預處理、屬性約簡、構建分類器和性能評價。基于粗糙集理論的文本分類模型，其中實線表示分類器建立過程中的數據流，虛線代表分類器測試過程中的數據流。

　　3.1 關鍵步驟

　　3.1.1 構建決策表

　　利用粗糙集理論獲得規則是通過對決策表里面的條件屬性和決策屬性進行屬性的約簡得到的，在此訓練集的文本要表示成本粗糙集理論能夠處理的決策表形式。使用向量空間模型VSM 來表引文本，將文本的特征詞作為條件屬性，文本的類別作為決策屬性，構建決策表。

　　3.1.2 數據離散

　　粗糙集理論分析要求數據的值必須以離散的形式表達，然而在實際應用中對特征進行加權后得到的權值的值域為連續值，所以在應用粗糙集理論方法處理之前，必須采用一種適宜的離散方法將連續數據轉化為離散區間，經過數據離散后可能會減小原始數據表示的精度，但將會提高其一般性。

　　數據離散的結果直接影響到分類的效果。在粗糙集理論中應用的離散算法很多，大體上可以將其分為兩類：一類是直接借用其它學科中的離散算法，如等距離劃分、等頻率劃分等;另一類是考慮到粗糙集理論對決策表的特殊要求，采用結合的方法來解決離散化問題，如Na?ve Scaler 算法，Semi Na?ve Scaler 算法，布爾邏輯和Rough 集理論相結合，以及基于斷點重要性、屬性重要性和聚類的離散算法等。

　　3.1.3 屬性約簡

　　屬性約簡是粗糙集理論的核心內容之一，也是應用粗糙集理論構建分類器的重要部分。

　　屬性約簡的目標就是要從條件屬性集合中找出部分必要條件屬性，使得這部分條件屬性和所有的條件屬性相對于決策屬性有相同的分類能力。經過屬性約簡去除了不必要的屬性，實現信息屬性的約簡，從而分析所得約簡中的條件屬性對于決策屬性的決策規則。

　　目前常用的約簡算法可分為兩類，一類是不借助任何啟發信息的屬性約簡，另一類是啟發式算法，如基于屬性重要度的屬性約簡算法、基于Skowron 差別矩陣的屬性約簡算法、以及基于信息熵的屬性約簡算法等，基于蟻群算法的屬性約簡算法等。

　　3.1.4 值約簡和規則合成

　　通過屬性約簡得到的約簡并不是唯一的，但是還沒有充分去掉決策表中的冗余信息，還需要進一步對決策表進行處理，得到更加簡化的決策表，這部分工作就是決策表值約簡。然后按照一定的策略將多個約簡表中的相應規則進行合成，得到最終的分類決策規則。決策表值約簡算法有一般值約簡算法、歸納值約簡算法、啟發式值約簡算法和基于決策矩陣的值約簡算法等。

　　3.2 粗糙集理論與其他算法構建的文本分類模型

　　粗糙集理論的屬性約簡理論可以降低文本分類過程中的向量維數，減少特征數，從而提高了分類速度。利用這一優勢可以與其他分類算法結合構成性能不錯的分類器。李鈍等在空間向量模型的基礎上將文本聚類和粗糙集理論的屬性約簡相結合，提出了一種新的文本分類方法，實驗表明該方法可提高文本分類效率。張著英將粗糙集理論應用到KNN 算法中,實現屬性約簡,提出了一種新的KNN 分類方法,解決了KNN 算法分類效率低的缺點，從而可使KNN 算法能夠得到更廣泛的應用。王效岳等結合粗糙集理論的屬性約簡和神經網絡的分類機理提出一種混合算法，分類速度得到提高，并體現較好的穩定性及容錯性。

　　上述模型主要是應用粗糙集理論的屬性約簡作為分類系統的預處理器，把冗余的屬性從決策表中刪去，然后運用其他分類算法進行分類。還有一些研究者將粗糙集理論以其他的方式應用到文本分類中，比如Miao 等提出基于變精度粗糙集的混合算法，利用KNN 和粗糙集理論對樣本空間進行劃分，然后用簡單快速的Rocchio 進行分類，并取得了不錯的分類結果;將粗糙集理論的分類質量應用到特征加權[27], 改進了文本樣本在整個空間中的分布，使得類內距離減少，類間距離增大，提高樣本的可分性等。

　　4. 總結

　　文本分類近年來已經得到很大的發展，有很多比較成熟的分類算法得到了應用，但是過高的特征空間維數限制了分類的效率和精度。特征選擇雖然可以降低特征數量，但也不可避免的造成了有用信息的丟失，降低了分類效果。將粗糙集理論應用到的文本分類模型中，可以利用粗糙集理論知識約簡理論，在保持分類能力的情況下得到最小的屬性約簡并得到顯式的規則。不過由于粗糙集理論本身限制條件較強，在實際應用中多利用其擴展模型或與其他算法相結合的方式，概括來說有三種方式：一是利用粗糙集理論作為預處理器，實現降維，結合其他分類算法構建分類器;二是利用粗糙集理論的約簡理論直接得到分類規則構建分類器;三是利用粗糙集理論的上下近似對樣本空間進行劃分，提高樣本的可分性。

　　參考文獻

　　[1] 王國胤，姚一豫，于洪.粗糙集理論與應用研究綜述[J].計算機學報，2009，32(7):1229-1246.

　　[2] 張文修，吳偉志.粗糙集理論介紹和研究綜述[J].模糊系統與數學，2000，14(4): 1-12.

　　[3] 唐春生，張磊，潘東，等.文本分類研究進展

　　[4] 靳小波.文本分類綜述[J].自動化博覽. 2006 23(z1): 24-29.

　　[5] 薛德軍.中文文本自動分類中的關鍵問題研究[D].北京：清華大學，2004.

　　[6] 蘇金樹，張博鋒，徐昕.基于機器學習的文本分類技術研究進展[J].軟件學報2006, 17(9):1848-1855.

　　[7] 蒲筱哥.Web 自動文本分類技術研究綜述[J].情報學報 2009,28(2):233-241.

　　[8] 錢曉東.數據挖掘中分類方法綜述[J].圖書情報工作，2007，51(3):68-71.

　　[9] 王國胤.Rough 集理論與知識獲取[M]. 西安：西安交通大學出版社，2001.

　　[10] 菅利榮.面向不確定性決策的雜合粗糙集方法及其應用[M]. 科學出版社，2008.

　　[11] Ziarko W.. A variable precision rough set model [J]. Journal of Computer and System Sciences, 1993, 46:39-59.

　　[12] 汪慶， 張巍， 劉鵬. 連續特征離散化方法綜述[EB/OL].

　　[13] 王國胤，劉靜，胡峰. 基于斷點辨別力的粗糙集離散化算法[J].重慶郵電大學學報(自然科學版)，2009，21(3)：388-392.

　　[14] 劉業政，焦寧，姜元春.連續屬性離散化算法比較研究[J]. 計算機應用研究，2007，24(9)：28-33.

　　[15] 李鈍，梁吉業.利用聚類和粗糙集進行文本分類研究[J].計算機工程與應用，2003，39(7)：186-188.

　　[16] 張著英，黃玉龍，王翰虎.一個高效的KNN 分類算法[J].計算機科學，2008 ，35(3)：170-172

　　[17] 王效岳，白如江.一種基于粗糙集-神經網絡的文本自動分類方法[J].情報學報. 2006,25(4) 475-480

　　[18] 胡清華，謝宗霞，于達仁. 基于粗糙集加權的文本分類方法研究[J].情報學報，2005，24(1):59-63.

　　[19] 苗奪謙，李道國. 粗糙集理論、算法與應用[M]. 北京：清華大學出版社 2008.4.

【基于粗糙集的文本分類研究】相關文章：

基于分形維數的圖像分類研究03-07

基于BP網遙感影像分類研究與應用02-25

基于BP神經網絡的遙感影像分類方法研究03-07

基于Web服務的集成研究03-08

基于ＡＨＰ的企業外包研究03-22

基于ＳＮＭＰ的拓撲發現的研究03-03

基于內容的圖像檢索研究11-20

基于ＥＶＡ的價值創造研究03-07

基于分類技術的Blog用戶興趣挖掘03-09