《電子技術應用》
您所在的位置:首頁 > 嵌入式技術 > 設計應用 > 粗糙集屬性約簡在文本分類中的性能研究
粗糙集屬性約簡在文本分類中的性能研究
2015年微型機與應用第21期
趙 靖1,2,皮建勇1,2
(1.貴州大學 計算機科學與技術學院,貴州 貴陽 550025; 2.貴州大學 云計算與物聯(lián)網研究中心,貴州 貴陽 550025)
摘要: 在文本分類中,特征空間維數可以達到數萬維。使用信息度量的方法,如文檔頻率、信息增益、互信息等,對特征進行選擇后的維數通常還是很大,降低閾值或減小最小特征數可能會降低分類效果。針對這個問題,提出基于粗糙集的二次屬性約簡。實驗表明,該方法在有效降低特征維數的同時保證了分類效果。
Abstract:
Key words :

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

  關鍵詞: 文本分類;粗糙集;屬性約簡

0 引言

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

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

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

1 常用特征選擇方法

  1.1 文檔頻率

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

  1.2 信息增益

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

  1.png

  其中,n是文檔類別總數,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 2TMOT{N9)@TI[Y~G5O63(12.jpg統(tǒng)計量

  2TMOT{N9)@TI[Y~G5O63(12.jpg統(tǒng)計量用來描述實際值與理論值的偏差,根據結果判斷一個結論是否正確。在文本分類中,可以用來檢驗特征項t和ci類之間是獨立還是相關關系。特征項t和ci類的2TMOT{N9)@TI[Y~G5O63(12.jpg統(tǒng)計量表示為:

  2.png

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

  1.4 互信息

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

  3.png

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

  1.5 幾率比

  幾率比著重關注目標類ci的值,其特別適用于二元分類器。特征項t的幾率比表示為:

  4.png

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

2 基于粗糙集的屬性約簡

  2.1 粗糙集預備知識

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

  定義1 決策系統(tǒng)由四元組S=(U,A,V,F(xiàn))表示。其中U稱為論域,是有限對象的集合;A是屬性的集合,也可以表示為A=C∪D,C∩D=CS`W}}3NFE%_6[U2ZH3VYUV.jpg,C代表條件屬性,D代表決策屬性。

  定義2 在決策系統(tǒng)中,假設存在屬性集A,且BJ1{~[N9Y7QNC}JG)R[ZSG]5.pngA,則A和B的不可區(qū)分關系可定義為:

  5.jpg

  其中,IND(A)表示一個等價關系,A中的所有等價關系的集合記為U/IND(A)。

  定義3 假設R是等價關系族,令Q=R-{r},r∈R且r≠CS`W}}3NFE%_6[U2ZH3VYUV.jpg,當IND(R)=IND(Q)時,r代表冗余屬性,而Q稱為R的一個約簡。R中所有必要關系的集合稱為P的核,記為CORE(R)。

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

  6.png

  2.2 屬性約簡算法

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

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

  (2)啟發(fā)式約簡算法

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

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

  輸入:決策系統(tǒng)S=(U,A,V,F(xiàn)),其中A=C∪D,C=)38%{IP{RTHMV2~K0[A6W07.pngai。

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

 ?。?)令8}4`V2WY67~4MEE)}M}4X2D.png;

 ?。?)計算可辨識矩陣M,As={mij:mij≠CS`W}}3NFE%_6[U2ZH3VYUV.jpg};

 ?。?)計算屬性ai在As中出現(xiàn)的次數ai(As);

 ?。?)選擇ai(As)值最大的屬性,記為a,RED=RED∪{a};

 ?。?)清除As中包含屬性a的項;

  (6)如果As=CS`W}}3NFE%_6[U2ZH3VYUV.jpg,則停止;否則轉入步驟(3)。

3 實驗結果與分析

  3.1 性能評測

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

002.jpg

 ?。?)準確率(Accuracy)

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

  48]@V~78SPK2}S$7H]$4DN4.png

 ?。?)召回率(Recall)

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

  8.png

 ?。?)F值(F-Measure)

  F值是準確率和召回率的綜合指標,能夠更好地反應一個分類器的性能。F值表示為:

  9.png

 ?。?)約簡率(Reduction Rate)

  在特征選擇中,約簡率代表數據集中特征的約簡程度。約簡率表示為:

 10.png

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

  3.2 實驗結果分析

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

003.jpg

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

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

001.jpg

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

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

004.jpg

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

4 結束語

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

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

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

  參考文獻

  [1] 張翔,周明全,耿國華.基于粗糙集的中文文本特征選擇方法研究[J].計算機應用與軟件,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] 王平.基于粗糙集屬性約簡的分類算法研究與應用[D].大連:大連理工大學,2013.

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

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

  [6] 洪雪飛.基于粗糙集的數據挖掘算法的研究與應用[D].北京:北京交通大學,2008.

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

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


此內容為AET網站原創(chuàng),未經授權禁止轉載。