摘  要： 在文本分類中，特征空間維數(shù)可以達到數(shù)萬維。使用信息度量的方法，如文檔頻率、信息增益、互信息等，對特征進行選擇后的維數(shù)通常還是很大，降低閾值或減小最小特征數(shù)可能會降低分類效果。針對這個問題，提出基于粗糙集的二次屬性約簡。實驗表明，該方法在有效降低特征維數(shù)的同時保證了分類效果。

　　關(guān)鍵詞： 文本分類；粗糙集；屬性約簡

0 引言

　　特征選擇在文本分類中有十分重要的作用，使用不同的特征選擇方法會對文本分類的準確率有很大影響。常用的特征選擇方法有文本頻率（Document Frequency）、信息增益（Information Gain）、互信息（Mutual Information）、統(tǒng)計量（CHI Squared）、幾率比（Odds Ratio）等。其中，信息增益在文本分類中有較好的效果。本文通過實驗證明，上述方法在屬性數(shù)目降低到一定程度時分類器準確率會達到瓶頸，繼續(xù)減少屬性可能會降低分類的準確率。

　　粗糙集理論是一種新型的處理不確定性和模糊性的數(shù)學工具，基于粗糙集理論的屬性約簡是該理論的一個重要分支。處理大數(shù)據(jù)集時，如果直接使用粗糙集進行約簡，生成的決策表規(guī)模將會十分大，對于離散化和基于粗糙集的屬性約簡來說，計算復雜度太高，難以完成[1]。因此對于擁有成千上萬維的文本集來說，直接使用粗糙集理論進行約簡會顯得笨拙且性能低下。

　　在上述背景下，本文提出了一種基于粗糙集的二次屬性約簡方法。該方法使用信息增益的方法對大數(shù)據(jù)集進行第一次約簡，刪除對分類無用或只含有少量信息的屬性，使數(shù)據(jù)規(guī)模適用于粗糙集約簡算法，得到的結(jié)果使用粗糙集進行二次約簡，這樣在保證分類準確率的情況下進一步對特征進行約簡。最后通過實驗驗證了該方法的有效性。

1 常用特征選擇方法

　　1.1 文檔頻率

　　文檔頻率DF（ti）表示訓練文檔中出現(xiàn)特征ti項的文檔數(shù)，出現(xiàn)特征項多的文檔包含更多對分類有用的信息，被保留的可能性大。在使用該方法時，需要設(shè)置閾值，小于該閾值的特征項全部去除。文檔頻率的缺點為可能會刪除出現(xiàn)次數(shù)較少但是包含重要信息的稀有詞。

　　1.2 信息增益

　　信息增益是最有效的特征選擇方法之一，可以理解為特征項在文本中出現(xiàn)前后的信息熵之差。特征項的信息增益值越大，說明該特征項包含更多對分類有幫助的信息[2]。本文將使用信息增益進行第一次特征選擇。特征項t的信息增益表示為：

　　其中，n是文檔類別總數(shù)，P（ci）表示ci類文檔出現(xiàn)的概率；P（t）表示特征項t出現(xiàn)在文檔集中的概率；P（ci|t）表示出現(xiàn)特征項t的文檔中，該文檔屬于ci類的概率；P（t）表示不包含特征項t的文檔的概率；P（ci|t）表示不包含特征項t的文檔中，屬于ci類文檔的概率。

　　1.3 統(tǒng)計量

　　統(tǒng)計量用來描述實際值與理論值的偏差，根據(jù)結(jié)果判斷一個結(jié)論是否正確。在文本分類中，可以用來檢驗特征項t和ci類之間是獨立還是相關(guān)關(guān)系。特征項t和ci類的統(tǒng)計量表示為：

　　其中，A是特征項t和ci類文檔同時出現(xiàn)的次數(shù)；B是特征項t出現(xiàn)而ci類文檔不出現(xiàn)的次數(shù)；C是不包含特征項t的ci類文檔出現(xiàn)的次數(shù)；D是特征項t和ci類文檔同時不出現(xiàn)的次數(shù)；N是訓練集所包含的文本總數(shù)。

　　1.4 互信息

　　互信息用來度量特征項t與ci類別同時出現(xiàn)的關(guān)系。在類ci中出現(xiàn)概率高的特征項t比其他類別具有更高的互信息值。MI表示為：

　　其中，P（t|ci）表示ci類文檔中特征項t出現(xiàn)的概率；P（t）表示特征項t出現(xiàn)的概率；P（ci）表示ci類文檔的概率。

　　1.5 幾率比

　　幾率比著重關(guān)注目標類ci的值，其特別適用于二元分類器。特征項t的幾率比表示為：

　　其中，P（t|pos）表示正例中特征項t出現(xiàn)的概率；P（t|neg）表示負例中特征項t出現(xiàn)的概率。

2 基于粗糙集的屬性約簡

　　2.1 粗糙集預備知識

　　粗糙集是繼概率論、模糊集、證據(jù)理論之后的又一個處理不確定性的數(shù)學工具[3]?；诖植诩膶傩约s簡是粗糙集理論的一個重要分支，其核心思想是在不影響原模型表達能力的情況下刪除冗余屬性。屬性約簡方法主要分為兩類：基于可分辨矩陣的約簡算法和啟發(fā)式約簡算法。本文采用Johnson約簡算法[4]。在具體介紹算法之前，先進行以下定義。

　　定義1 決策系統(tǒng)由四元組S=（U，A，V，F(xiàn)）表示。其中U稱為論域，是有限對象的集合；A是屬性的集合，也可以表示為A=C∪D，C∩D=，C代表條件屬性，D代表決策屬性。

　　定義2 在決策系統(tǒng)中，假設(shè)存在屬性集A，且BA，則A和B的不可區(qū)分關(guān)系可定義為：

　　其中，IND（A）表示一個等價關(guān)系，A中的所有等價關(guān)系的集合記為U/IND（A）。

　　定義3 假設(shè)R是等價關(guān)系族，令Q=R-{r}，r∈R且r≠，當IND（R）=IND（Q）時，r代表冗余屬性，而Q稱為R的一個約簡。R中所有必要關(guān)系的集合稱為P的核，記為CORE（R）。

　　定義4 假設(shè)存在決策系統(tǒng)S，簡寫為S=（U，C∪D），可辨識矩陣[5]M=（mij）表示為：

　　2.2 屬性約簡算法

　?。?）基于可辨識矩陣的屬性約簡算法

　　該方法的基本思想是決策系統(tǒng)的約簡與可辨識矩陣的任意非空項的交集不為空，并且可辨識矩陣中單個元素構(gòu)成的項的并集就是決策系統(tǒng)的核。

　?。?）啟發(fā)式約簡算法

　　目前主要的啟發(fā)式約簡算法有兩種，一種是基于可辨識矩陣，算法的基本思想是可辨識矩陣中出現(xiàn)頻率越大的屬性越重要，區(qū)分對象的能力也越強；另一種是基于屬性重要性，算法以核作為起點，以屬性依賴度作為啟發(fā)式信息，對屬性空間進行搜索，一般情況下能夠得到?jīng)Q策系統(tǒng)的最小約簡[6]。

　　本文采用Johnson約簡算法，該算法是上面第一種基于可辨識矩陣的啟發(fā)式約簡算法，算法描述如下：

　　輸入：決策系統(tǒng)S=（U，A，V，F(xiàn)），其中A=C∪D，C=ai。

　　輸出：決策系統(tǒng)的相對約簡RED

　?。?）令；

　?。?）計算可辨識矩陣M，As={mij:mij≠}；

　　（3）計算屬性ai在As中出現(xiàn)的次數(shù)ai（As）；

　?。?）選擇ai（As）值最大的屬性，記為a，RED=RED∪{a}；

　?。?）清除As中包含屬性a的項；

　?。?）如果As=，則停止；否則轉(zhuǎn)入步驟（3）。

3 實驗結(jié)果與分析

　　3.1 性能評測

　　假設(shè)任務(wù)為一個二分類問題，即實例只能被分為正例和負例。如果一個正例被預測為正類，則稱為真正類（True positive），若被預測為負類，則稱為假負類（False negative）。同理，如果一個負例被預測為負類，則稱為真負類（True negative），若被預測為正類，則稱為假正類（False positive）。二分類問題的混合矩陣如表1所示。

　?。?）準確率（Accuracy）

　　準確率是指一個分類器正確預測類標號未知實例的能力。準確率表示為：

　　（2）召回率（Recall）

　　召回率又稱為查全率，廣泛應(yīng)用于信息檢索和統(tǒng)計學，在數(shù)據(jù)挖掘領(lǐng)域中通常表示為正確分類正例數(shù)占所有正例數(shù)的比率。召回率表示為：

　?。?）F值（F-Measure）

　　F值是準確率和召回率的綜合指標，能夠更好地反應(yīng)一個分類器的性能。F值表示為：

　?。?）約簡率（Reduction Rate）

　　在特征選擇中，約簡率代表數(shù)據(jù)集中特征的約簡程度。約簡率表示為：

　　其中，RAAR（Reduced Attributes After Reduction）表示約簡掉的屬性個數(shù)，AOOD（Attributes Of the Original Data set）表示原數(shù)據(jù)集屬性個數(shù)。

　　3.2 實驗結(jié)果分析

　　本實驗數(shù)據(jù)來源于數(shù)據(jù)堂中文文本分類語料庫，適用于小規(guī)模的研究。數(shù)據(jù)集共分為10個分類，分別是環(huán)境、計算機、交通、教育、經(jīng)濟、軍事、體育、醫(yī)藥、藝術(shù)和政治，共有2 816篇短文檔。各類文檔分布如表2所示。

　　中文分詞階段使用Lucene中文分詞系統(tǒng)，去除停用詞、稀有詞后，選擇詞頻大于5的特征詞，共有505個特征詞。為了盡量減小實驗誤差，采用十折交叉驗證的方法進行實驗。

　　實驗首先使用信息增益的方法對特征進行選擇，通過設(shè)定不同的最小特征數(shù)選取指定數(shù)量的特征，并分別使用NaiveBayes、KNN和C4.5三種分類器對不同特征數(shù)目下的數(shù)據(jù)集進行分類實驗，得到分類準確率、召回率和F值，實驗結(jié)果如圖1~圖3所示。

　　由圖1~圖3可以看出，準確率、召回率和F值三個指標均顯示出隨著特征的選擇，分類器的性能逐步提高。而且，當特征數(shù)目在100~130之間時，三種分類器性能達到最高值。特征數(shù)目為100時，雖然KNN和C4.5兩種分類器的性能有一定程度的提高，但是三個指標都顯示出NaiveBayes的性能已經(jīng)出現(xiàn)了明顯的下滑趨勢。所以認為，特征數(shù)在減少到130個時，特征選擇達到瓶頸，各個分類器總體表現(xiàn)最好，繼續(xù)減少特征數(shù)，分類器性能會出現(xiàn)顯著的下降趨勢。

　　此時將第一步處理結(jié)果中整體準確率表現(xiàn)最佳的特征集（130維）作為第二步粗糙集屬性約簡的輸入，使用Johnson約簡算法計算出相對約簡，計算結(jié)果包含70個特征項，根據(jù)式（10）可計算出約簡率為46.2%，相對于原特征空間，第一步約簡率74%，第二步約簡率86%，整體提升了12%，在使用信息度量的方法已經(jīng)無法繼續(xù)減少特征數(shù)時，進一步壓縮了特征空間。將使用粗糙集屬性約簡前后三種分類器的準確率、召回率和F值進行對比，結(jié)果如表3所示。

　　由表3可以看出，使用粗糙集進行屬性約簡后，NaiveBayes在準確率、召回率和F值三項指標上都有所提高，KNN和C4.5有所降低，但是增加和減少的幅度均較小。根據(jù)表中數(shù)據(jù)可以分析出，三種分類器的性能基本保持不變。說明該方法在使用信息增益的方法進行特征選擇的基礎(chǔ)上，能進一步刪除冗余屬性并且不對分類器性能造成較大影響，驗證了基于粗糙集二次屬性約簡的有效性。

4 結(jié)束語

　　本文提出一種基于粗糙集的二次屬性約簡方法，該方法相比單獨的信息增益特征選擇和粗糙集屬性約簡有以下優(yōu)點：

　?。?）信息增益在處理不平衡數(shù)據(jù)時性能很差，并且缺少對特征項的進一步篩選[7]。使用基于粗糙集的二次屬性約簡可以剔除冗余屬性，一定程度上彌補了信息增益的缺點；

　?。?）粗糙集具有一定的局限性，在處理大數(shù)據(jù)集時效率非常低[8]，因此面對大數(shù)據(jù)集時，先采用信息增益處理可以得到適用于粗糙集的數(shù)據(jù)集，減小粗糙集的計算復雜度。

　　參考文獻

　　[1] 張翔，周明全，耿國華．基于粗糙集的中文文本特征選擇方法研究[J].計算機應(yīng)用與軟件，2010，27（3）：4-5.

　　[2] Yang Yiming， PEDERSON J O． A comparative study on feature selection in text categorization[C]. Proceedings of the 14th International Conference on Machine Learning，Nashville： Morgan Kaufmann， 1997：412-420.

　　[3] 王平．基于粗糙集屬性約簡的分類算法研究與應(yīng)用[D]．大連：大連理工大學，2013.

　　[4] 陳桂芬，馬麗，董瑋，等．聚類、粗糙集與決策樹的組合算法在地力評價中的應(yīng)用[J]．中國農(nóng)業(yè)科學，2011，44（23）：4833-4840.

　　[5] 楊傳健，葛浩，李龍澍．可分辨矩陣及其求核方法[J]．計算機工程，2010，36（9）：87-89.

　　[6] 洪雪飛．基于粗糙集的數(shù)據(jù)挖掘算法的研究與應(yīng)用[D]．北京：北京交通大學，2008.

　　[7] 任永功，楊榮杰，尹明飛，等．基于信息增益的文本特征選擇方法[J]．計算機科學，2012，39（11）：127-130.

　　[8] 史軍．基于粗糙集理論的屬性約簡算法研究[D]．青島：青島大學，2009.