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

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

0 引言

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

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

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

1 常用特征選擇方法

　　1.1 文檔頻率

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

　　1.2 信息增益

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

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

　　1.3 統(tǒng)計(jì)量

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

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

　　1.4 互信息

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

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

　　1.5 幾率比

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

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

2 基于粗糙集的屬性約簡(jiǎn)

　　2.1 粗糙集預(yù)備知識(shí)

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

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

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

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

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

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

　　2.2 屬性約簡(jiǎn)算法

　?。?）基于可辨識(shí)矩陣的屬性約簡(jiǎn)算法

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

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

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

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

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

　　輸出：決策系統(tǒng)的相對(duì)約簡(jiǎn)RED

　?。?）令；

　?。?）計(jì)算可辨識(shí)矩陣M,，As={mij:mij≠}；

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

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

　　（5）清除As中包含屬性a的項(xiàng),；

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

3 實(shí)驗(yàn)結(jié)果與分析

　　3.1 性能評(píng)測(cè)

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

　　（1）準(zhǔn)確率（Accuracy）

　　準(zhǔn)確率是指一個(gè)分類器正確預(yù)測(cè)類標(biāo)號(hào)未知實(shí)例的能力,。準(zhǔn)確率表示為：

　?。?）召回率（Recall）

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

　?。?）F值（F-Measure）

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

　?。?）約簡(jiǎn)率（Reduction Rate）

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

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

　　3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

　　參考文獻(xiàn)

　　[1] 張翔,，周明全,，耿國(guó)華．基于粗糙集的中文文本特征選擇方法研究[J].計(jì)算機(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] 王平．基于粗糙集屬性約簡(jiǎn)的分類算法研究與應(yīng)用[D]．大連：大連理工大學(xué),，2013.

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

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

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

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

　　[8] 史軍．基于粗糙集理論的屬性約簡(jiǎn)算法研究[D]．青島：青島大學(xué),，2009.