摘 要：文字分類是資訊檢索和數據挖掘等領域的研究熱點。在現有的一些文字分類方法中，文字都是基於向量空間模型表示的，所形成的特徵空間維數相當高，導致分類算法效率不高，分類精度不理想。粗糙集應用到文字分類可以在不影響分類精度的條件下降低特徵向量的維數，並且可以得到的顯式表達的分類規則。本文旨在介紹文字分類一般過程，分析將粗糙集理論應用到文字分類中關鍵步驟，總結粗糙集與其他分類算法結合應用到文字分類的情況。
關鍵詞：文字分類;粗糙集理論;屬性約簡
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 評價標準
文字分類的評價是透過實驗數據分析獲得的，在該部分把測試集中的每個文字進行預處理後，輸入到分類器進行分類。透過對分類結果的統計分析然後進行評價。現在常用的評價標準有：準確率/召回率、break-even 點、F-measure、11 點平均準確率圖、精度/錯誤率等;另外還有微平均和宏平均分別用來描述一個類和全部類的分類情況。
2.7 數據集
在構建和測試文字分類系統的時候需要用到大量的文字資料，如果能使用一個標準的數據集進行研究，不僅可以減少建設數據集的費用，而且可以使得不同研究者的分類結果具有可比性。現在國際上用於文字分類的英文標準數據集主要有以下幾個：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 值約簡和規則合成