基于最大互信息最大相關熵的特征選擇方法
2009-01-01 00:00:00趙軍陽張志利
計算機應用研究 2009年1期
（第二炮兵工程學院， 西安710025）
摘 要：特征選擇算法主要分為filter和wrapper兩大類，并已提出基于不同理論的算法模型，但依然存在算法處理能力不強、子集分類精度不高等問題。基于模糊粗糙集的信息熵模型提出最大互信息最大相關熵標準，并根據該標準設計了一種新的特征選擇方法，能同時處理離散數據、連續數據和模糊數據等混合信息。經UCI數據集試驗，表明該算法與其他算法相比，具有較高的精度，且穩定性較高，是有效的。
關鍵詞：模糊粗糙集；信息熵；特征選擇；互信息；相關熵
中圖分類號：TP181 文獻標志碼：A
文章編號：10013695(2009)01023303
Feature subset selection based on max mutual information and max correlation entropy
ZHAO Junyang，ZHANG Zhili
(The Second Artillery Engineering Institute，Xi’an 710025， China)
Abstract:Feature selection algorithms broadly fall into two categories: the filter model and the wrapper model. A great many algorithms had been proposed， but the problems of weak process ability and low classification accuracy still exists. To solve these problems，this paper proposed a max mutual information and max correlation entropy criterion based on fuzzy rough information entropy model and designed a new feature selection algorithm based on this criterion. The algorithm can deal with discrete data， continuous data， fuzzy and hybrid data. According to tests on UCI datasets， the algorithm is effective， and has higher accuracy and stability compared to three other common feature selection algorithms.
Key words:fuzzy rough set；information entropy；feature selection；mutual information；correlation entropy隨著計算機和數據庫技術的發展，數據的信息量越來越大，理想情況下希望所提供的信息都是有用的，但實際上數據集中往往包含冗余信息。因此，在利用數據集之前，需要對數據進行預處理，去除包含冗余信息的特征，特征選擇就是一種重要的數據預處理方法。特征選擇是指從高維特征集合中根據某種評估標準選擇輸出性能最優的特征子集，其目的是尋求保持數據集感興趣特性的低維數據集合，通過低維數據的分析來獲得相應的高維數據特性，從而達到簡化分析、獲取數據有效特征以及可視化數據的目標。根據是否依賴機器學習算法，特征選擇算法可以分為兩大類，即filter型算法和wrapper型算法。Filter型特征選擇算法獨立于機器學習算法，具有計算代價小、效率高但降維效果一般等特點；而wrapper型特征選擇算法則需要依賴某種或多種機器學習算法，具有計算代價大、效率低，但降維效果好等特點。目前比較常見的算法有BB[1]、Focus[2]、Relief[3]、LVF[4]、CFS[5]等。
1982年Pawlak提出了粗糙集理論，并基于該理論提出能有效處理不確定信息的REDUCT屬性約簡算法[6]。目前基于粗糙集的特征選擇主要分為兩類，即基于區分矩陣的約簡和基于依賴度的約簡。隨著粗糙集理論的發展，R. Jensen等人提出基于模糊粗糙集模糊屬性依賴度的選擇算法[7~9]，2006年Q. H. Hu利用模糊粗糙集熵理論對不確定信息進行度量，并提出基于信息熵的混合數據約簡算法[10]。本文首先提出新的模糊粗糙集信息熵模型，然后給出基于信息熵模型的最大互信息最大相關熵標準，并基于該標準設計了一種新的特征選擇算法，最后通過實驗進行了驗證。
1 模糊粗糙集的信息熵模型
往往粗糙數據中包含有模糊信息，而模糊數據中也存在粗糙分類，關于如何測量數據的不確定，1999年Wierman提出了測量粗糙集不確定性的信息熵定義：
定義1 設U為有限論域，R是U上的等價關系，關于R的等價劃分為{X1，X2，…，Xk}，則近似空間（U，R）的信息熵定義為[11]
E(R)=-ki=1|Xi|/|U|log2 |Xi|/|U|（1）
該定義反映了粗糙分類的信息量，但卻只關注了類別內的信息，而沒有考慮類別外的信息如何度量，因此該定義并不完整。2002年梁吉業定義了一種新的信息熵模型，考慮了類別劃分的補集，見式（2）。
定義2 設U為有限論域，R是U上的等價關系，關于R的等價劃分為{X1，X2，…，Xk}，則近似空間（U，R）的信息熵定義為[12]
E(R)=ki=1|Xi|/|U|(1- |Xi|/|U|)（2）
上述定義對關系R要求比較嚴格，而在很多情形下是無法保證R滿足等價關系的，不能適應模糊粗糙集條件下的不確定測量[13]，為此對上式在連續和模糊情況下進行拓展。
定義3 設U={x1，x2，…，xn}為有限論域，R是U上的任意模糊關系，則近似空間（U，R）的信息熵定義為[14]
H(R)=ni=11/|U|(1- |[xi]R|/|U|)（3）
其中:|[xi]R|=nj=1rij表示對象xi在模糊關系R下的勢，rij表示兩個對象的相似度。
定理1 設R是U上的自反模糊關系，則
a）H(R)的最大值為1-1/|U|，且H(R)=1-1/|U|[xi]R={xi}，i∈n；
b）H(R)的最大值為0，且H(R)=0[xi]R=U，i∈n。
定理2 設R是U上的等價關系，則H（R）=E（R）。
定義4 設U為有限論域，P和Q是U上的任意模糊關系，[xi]P和[xi]Q是P和Q生成的包含xi的模糊等價類，則P和Q的條件熵定義為
H(Q|P)=ni=1(1/|U| )(|[xi]P-[xi]Q|/|U|)（4）
定義5 設U為有限論域，P和Q是U上的任意模糊關系，[xi]P和[xi]Q是P和Q生成的包含xi的模糊等價類，則P和Q的互信息定義為
I(Q;P)=ni=11/|U|(1- |[xi]P∪[xi]Q|/|U|)（5）
2 基于最大互信息最大相關熵的特征選擇算法
21 特征相關性定義
根據文獻[15]對特征相關性可將特征分為三類，即強相關特征、弱相關特征和不相關特征。設原始特征集為A=C∪d，特征ai∈C，S為已選特征子集，對特征的相關性的定義如下：
定義6 如果I(d/S∪ai)≠I(d/S)，則稱特征ai為強相關特征。
定義7 如果I(d/S∪ai)≠I(d/S)，且SiS，I(d/Si∪ai)≠I(d/Si)，則稱特征ai為弱相關特征。
定義8 如果SiS，I(d/Si∪ai)=I(d/Si)，則稱特征ai為不相關特征。
強相關特征是必須保留的，否則會嚴重影響分類性能；弱相關特征并不是一定需要的，但有時又是必需的，因而需要視情況取舍；不相關特征則完全沒必要保留，需要去除。
22 最大互信息和最大相關熵準則
相關性定義不僅可以反映屬性之間的關系，也可以表現屬性與類之間的關系。類似于文獻[16]的方式，本文中的最大相關標準以依據式（5）計算得到的條件屬性與決策屬性之間的最大互信息來定義，即如式（6）所示的屬性子集中單個屬性與決策類之間互信息均值的最大值：
max M(S∪ai，d)，M=1/|S|ai∈SI(ai;d)（6）
盡管與決策類越相關的屬性區分能力越強，但由于所選屬性之間存在相互交叉冗余，往往所選擇的最相關的子集在構建分類器時是次優解，其分類精度未必比相關性相對較弱的屬性子集高，因此必須考慮屬性之間的冗余性或獨立性，使所選擇的屬性子集不僅具有較強的相關性，而且屬性間的冗余度最小。為此，采用文獻[10]的相關熵來度量條件屬性集的獨立性，定義如下：
HCE（S）=-Ni=1λi/Nlog Nλi/N （7）
其中λi代表屬性集相關系數矩陣的第i個特征值。
相關熵越大，則屬性集的相關性越小，也即獨立性越大；反之，則相反。如果所有屬性線性相關，則相關熵為0；如果所有屬性均相互獨立，則相關熵為1。要使所選擇的屬性集具有最小冗余度，則需滿足以下最大相關熵準則：
maxHCE(S∪ai) ai∈C-S（8）
23 特征選擇算法模型
基于最大互信息最大相關熵標準MmiMce，提出一種新的特征選擇算法FSmMC。該算法采用啟發式前向搜索，初始為空集，每次選擇具有最大互信息的屬性添加到特征子集中，如果該屬性使子集的相關熵增大，即冗余性減少，則保留該屬性，否則去除該屬性，如此重復添加直至相關熵不再增大，算法停止。具體描述如下：
算法：FSmMC
輸入：決策信息系統DIS〈U，A，V，f〉，A=C∪d
輸出：系統的最優屬性子集
a)S=，HCE (S)=0；
b）ai∈CS，Calculate M(S∪ai，d)，
Choose M(a)=max M(S∪ai，d)；
c）Compute HCE(S∪a)，
if HCE(S∪a)-HCE(S)＞0，
then S=S∪a，
elseend；
d）return S
為分析算法復雜性，假設總共有N個條件屬性，計算每個屬性的模糊關系的時間復雜度為O(N)，在循環條件下可能需要對所有屬性進行搜索，也可能僅需搜索一次，其平均時間復雜度為O(N log N)，故算法的總時間復雜度為O(N log N)。
3 實驗驗證
為驗證算法的可行性和選擇效果，采用UCI數據庫中的12個數據集對算法進行測試，如表1所示，除Bc和Lc是純符號性數據外，其余數據集均包含連續數據或混合數據。結合新西蘭Waikato大學開發的WEKA軟件，將選擇結果與CFS、Relief和InfoGain算法進行了比較，并分別在C4.5、Bagging和NaiveBayes條件下對每種算法選擇的各個數據集的特征子集進行分類精度評價。對比結果如表2~4所示。
從表2分析可得，對于不同的數據集，每種算法的表現不盡相同。每一種算法均在部分數據集上獲得最高分類精度，但無法在全部數據集上表現優異，如表2中，InfoGain算法在Bc數據集上分類精度最高，但在其他數據集上表現一般，這也正符合No Free Lunch理論，即不同的算法通常各有其優劣，沒有哪種算法絕對優于另一種算法[17]。而且每種算法所選擇的特征子集在不同的分類器下的表現也不相同，如CFS算法選擇的子集在C4.5條件下表現一般，但在Bagging和NaiveBayes分類器下表現出的性能卻相對較好；Relief算法選擇的子集在C4.5和Bagging條件下均表現出較出色的性能，但在NaiveBayes條件下卻略顯落后。雖然本文算法在部分數據集上，如Ion、Wdbc上表現可能不如其他三種算法，但總體而言， FSmMC表現較為穩定，在將近半數的數據集上具有最高分類精度，且在C4.5、Bagging和NaiveBayes條件下均獲得最高平均分類精度（圖1），尤其在諸如Cle、Lc數據集上性能提升更為明顯。如表3中針對Cle，FSmMC在選擇的特征數至少減少一半的前提下，比其他算法精度提高了15.52%；表4中針對Lc，算法在子集特征數減少了將近一半，精度卻提高
選擇子集的分類精度是特征選擇的一個重要方面，同時也要考慮選擇的子集所包含特征數的多少，即算法能否在保持較高分類精度的同時選擇盡量少的特征。根據圖2可知，相對于原始特征數，各算法均對特征數量進行了較大幅度的約簡，而且對特征數越多的數據集，約簡的幅度更大。其中，本文算法選擇的子集包含的平均特征數最少，平均為6.6個，相比于原始特征約簡了68.7%，相比于其他算法也至少約簡了14.3%，而且精度還得到了提高。
由上述分析知，相比于其他三種算法，FSmMC算法在保持選擇較小數量特征的子集同時，所選的子集具有較高的平均分類精度，因此該算法是穩定有效的。
4 結束語
特征選擇是機器學習領域的一個重要研究方向，雖然這方面的研究取得了很多成果，但依然存在一些問題，如算法處理能力單一等。實際的數據集包含的數據類型往往有多種，既可能有離散型數據，也可能有連續型或模糊類型，一個好的算法必須能應對多種數據類型的挑戰。本文算法能夠處理混合數據，且具有較高的精度和穩定性，是一種有效的算法。
參考文獻：
[1]NARENDRA P M，FUKUNAGA K A.Brand and bound algorithm for feature subset selection[J].IEEE Trans on Computer，1977，26(9): 917922.
[2]ALMUALLIM H，DIETTERICH T G.Learning with many irrelevant features[C]//Proc of the 9th Nat’l Conf Artificial Intelligence.1991：547552.
[3]KIRA K，RENDELL L A.The feature selection problem:traditional methods and a new algorithm[C]//Proc of the 10th Nat’l Conf Artificial Intelligence.1992：129134.
[4]LIU Huan，SETIONO R.A probabilistic approach to feature selection：a filter solution[C]//Proc of the 13th International Conf Machine Learning.1996：319327.
[5]HALL M A.Correlationbased feature selection for discrete and numeric class machine learning[C]//Proc of the 17th International Conf Machine Learning.2000:359366.
[6]PAWLAK Z.Rough sets:theoretical aspects of reasoning about data[M].Boston:Kluwer Academic Publishers，1991.
[7]JENSEN R，SHEN Qiang.Fuzzyrough attribute reduction with application to Web categorization[J].Fuzzy Sets and Systems，2004，141(3):469485.
[8]JENSEN R，SHEN Q.Fuzzyrough sets assisted attribute reduction[J].IEEE Trans on Fuzzy Systems，2007，15(1):7389.
[9]BHATT R B，GOPAL M.On fuzzyrough sets approach to feature selection[J].Pattern Recognition Letters，2005，26(7):965975.
[10]HU Qinghua，YU Daren，XIE Zongxia.Informationpreserving hybrid data reduction based on fuzzyrough techniques[J].Pattern Recognition Letters，2006，27(5):414423.
[11]WIERMAN M J.Measuring uncertainty in rough set theory[J].International Journal of General Systems，1999，28(45):283297.
[12]LIANG Jiye，CHIN K S，DANG Chuangyin，et al.A new method for measuring uncertainty and fuzziness in rough set theory[J].International Journal of General Systems，2002，31(4):331342.
[13]YU D，HU Q H，WU C X.Uncertainty measures for fuzzy relations and their applications[J].Appl Soft Comput，2007，7(3):11351143.
[14]ZHAO J Y，ZHANG Z L.Fuzzyrough data reduction based on information entropy[C]//Proc of International Conference of Machine Learning and Cybernetics(ICMLC2007).2007:37083712.
[15]KOHAVI R，JOHN G H.Wrappers for feature subset selection[J].Artificial Intelligence，1997，97(12):273324.
[16]PENG H C，LONG F H，DING C.Feature selection based on mutual information: criteria of maxdependency， maxrelevance， and minredundancy[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2005，27(8):12261237.
[17]王瑋，周志華，周傲英.機器學習及其應用[M]. 北京:清華大學出版社， 2006：175178.
［18］DASH M，LIU H.Feature slection for classification[J].Intelligent Data Analysis，1997，1(3):131156.
[19]LIU H，YU L.Toward integrating feature selection algorithms for classification and clustering[J].IEEE Trans on Knowledge and Data Engineering，2005，17(4): 491502.
