顧翔元，郭繼昌，李重儀，肖利軍

(天津大學電氣自動化與信息工程學院，天津 300072)

計算機技術的快速發(fā)展，使得各種數(shù)據(jù)量快速增長，智能信息處理所需數(shù)據(jù)集的特征維數(shù)也越來越高.數(shù)據(jù)集特征維數(shù)的增加，會帶來分類準確率下降、計算耗時多等問題．因此有必要進行特征選擇[1-4].

特征子集選擇是特征選擇的一種重要方法[5]，它利用某種度量標準對特征與類標簽的相關性以及特征間的冗余性進行度量，消除不相關特征和冗余特征．度量標準是影響特征子集選擇算法效果好壞的關鍵．

文獻[6-7]利用互信息實現(xiàn)了特征選擇，互信息是一種常用的度量標準，它具有可描述特征間的非線性相關性和空間變換不變性等優(yōu)點[8]，但其優(yōu)先選取的特征不能保證取得較好的分類效果．文獻[9]對互信息進行了歸一化處理，提出了對稱不確定性(symmetric uncertainty，SU)度量標準．FCBF[10]和FCBF-MIC 算法[11]利用對稱不確定性進行了特征子集選擇．FCBF 算法采用對稱不確定性度量特征與類標簽的相關性以及特征間的冗余性，并將特征與類標簽的對稱不確定性和特征間對稱不確定性做比較來消除冗余特征．FCBF-MIC 算法分別采用對稱不確定性和最大信息系數(shù)對特征與類標簽的相關性以及特征間的冗余性進行度量，并利用特征與類標簽的最大信息系數(shù)和特征間的最大信息系數(shù)的比較結果來消除冗余特征．由于僅利用對稱不確定性或最大信息系數(shù)等某一種度量標準來評價冗余特征，F(xiàn)CBF 和FCBF-MIC 等算法存在將相關特征當作冗余特征而消除的問題．

針對上述問題，本文提出一種基于對稱不確定性和三路交互信息的特征子集選擇算法，首先利用對稱不確定性進行相關性分析，消除不相關特征，然后分別利用對稱不確定性和三路交互信息進行冗余性分析和交互性分析，消除冗余特征．本算法由于利用了對稱不確定性和三路交互信息兩種度量標準而減少了相關特征的誤消除，使得有效特征得以保留，因此算法獲得了更好的性能．

1 三路交互信息和馬爾可夫毯

1.1 三路交互信息

信息熵被用來量化某隨機變量信息量的大小，其定義如式(1)所示．

式中p(x)為一離散隨機變量X取值為x的概率．

互信息被用來表述兩變量所包含信息量的多少，兩變量X和Y的互信息I(X；Y)定義如式(2)所示．

式中：p(x，y)為兩變量的聯(lián)合概率密度函數(shù)；p(y)為變量Y取值為y的概率．I(X；Y)值越大，表明X和Y所包含的共同信息越多．

三路交互信息I(X；Y；Z)是互信息的擴展，其可為正、負和零．當I(X；Y；Z)為正值時，表明兩變量X和Y共同提供關于Z的信息要大于它們單獨提供關于Z信息的和，此時表明X和Y在提供關于Z的信息上是互補的；其值為負值時，表明X和Y在提供關于Z的信息上是冗余的；其值為零值時，表明兩變量在提供關于Z的信息上是獨立的．

1.2 馬爾可夫毯

馬爾可夫毯可被用于特征選擇中，其定義[10]如下．

定義1(馬爾可夫毯) 給定一個特征fj，類標簽c，一個特征集F和F中一個特征子集Gj．假設Gj?F(fj?Gj)，Gj為fj的馬爾可夫毯的條件是概率p(F－Gj－{fj}，c|fj，Gj)＝p(F－G－{fj}，c|Gj) ．

由定義1 可知，如果選取fj，前后概率不變，則Gj為fj的馬爾可夫毯．基于馬爾可夫毯，對冗余特征有這樣的定義：假設F是當前特征集，F(xiàn)中的一個特征fj是冗余特征當且僅當存在Gj?F(fj?Gj)為fj的馬爾可夫毯[10]．

馬爾可夫毯可以被用來評價冗余特征，然而由于運算量較大，其很少被使用，通常利用不同形式的近似馬爾可夫毯．如定義2 所示，文獻[10]給出一種近似馬爾可夫毯來評價冗余特征．

定義 2(近似馬爾可夫毯) 特征fs是特征fi的近似馬爾可夫毯當且僅當同時滿足SU(c，fs)≥SU(c，fi)和SU(fi，fs)≥SU(c，fi) ．

由定義2 的SU(fi，fs)≥SU(c，fi)可知，文獻[10]將特征與類標簽的對稱不確定性和特征間的對稱不確定性做比較，利用比較結果來評價冗余特征．由于只考慮兩個特征來評價冗余特征，使得滿足SU(fi，fs)≥SU(c，fi)條件的特征未必是冗余特征，會將一些相關特征當作冗余特征而消除．

2 本文算法

本文算法主要分為兩個步驟：首先消除不相關特征，然后消除冗余特征，具體過程如圖1 所示．

圖1 中，首先計算特征與類標簽的對稱不確定性值，消除其值為零的特征；然后，計算特征間的對稱不確定性值，按其和特征與類標簽的對稱不確定性值的大小確定它們的序值，并計算特征與類標簽的三路交互信息值．若某特征滿足以下條件：其與其他特征的對稱不確定性值和序值分別大于其與類標簽的對稱不確定性值和序值，其與其他特征、類標簽的三路交互信息值小于零，則將其作為冗余特征消除．

圖1 本文算法的框架Fig.1 Framework of the proposed algorithm

2.1 相關特征的評價

相關性通常是指單個特征與類標簽的關系．利用對稱不確定性進行相關性分析，特征fi與類標簽c的對稱不確定性SU(c，fi)如式(3)所示．

式中SU(c，fi) ∈[0 ，1] ．與類標簽的對稱不確定性值越大，表明該特征與類標簽越相關；當與類標簽的對稱不確定性值為零時，表明該特征與類標簽是不相關的．定義3 給出相關特征的評價方法．

定義 3(相關特征的評價方法)fi是相關特征當且僅當滿足SU(c，fi)＞0．

2.2 冗余特征的評價

利用定義3 將不相關特征從原始特征集中消除后，需要消除冗余特征．接下來進行冗余性分析．

冗余性通常是指特征間的關系．利用對稱不確定性進行冗余性分析．

鑒于文獻[10]中近似馬爾可夫毯存在的問題，分別利用排序?qū)U(c，fi)和SU(fi，fs)進行處理，得到其序值R(c，fi)和R(fi，fs) ．由于對稱不確定性的最大值為1，最小值為0，而不同序值間最小的差別為1．所以，對于不同的fi，R(c，fi)間的差別要大于SU(c，fi)間的差別；對于同一個fi和不同的fs，R(fi，fs)間的差別要大于SU(fi，fs)間的差別．使得R(c，fi)和R(fi，fs)的部分比較結果較SU(c，fi)和SU(fi，fs)的比較結果有一定的優(yōu)勢．

如果只利用R(c，fi)和R(fi，fs)的比較結果來定義近似馬爾可夫毯，由于量級不對等，會存在一些比較結果不準確的問題．

而將SU(c，fi)和SU(fi，fs)的比較結果與R(c，fi)和R(fi，fs)的比較結果相結合來定義近似馬爾可夫毯，不但可以減少將相關特征當作冗余特征而消除的情況，而且結果也更為準確．所以，如定義4 所示，給出一種近似馬爾可夫毯．

定義 4(近似馬爾可夫毯)fs是fi的近似馬爾可夫毯當且僅當同時滿足 SU(c，fs)＞SU(c，fi)、SU(fi，fs)＞SU(c，fi)和R(fi，fs)＞R(c，fi)．其中，R(c，fi)和R(fi，fs)分別是SU(c，fi)和SU(fi，fs)經(jīng)排序而得到的序值．

由定義4 可知，同時滿足SU(fi，fs)＞SU(c，fi)和R(fi，fs)＞R(c，fi)條件的特征才是冗余特征，可以保證效果較顯著的特征被保留．由于只考慮一種度量標準，會存在將相關特征當作冗余特征而消除的問題．鑒于此，接著進行交互性分析．

交互性通常是指兩個或多個特征與類標簽的關系．利用三路交互信息進行交互性分析．

由第1.1 節(jié)可知，當I(fi；fs；c)＜0 時，特征fi與fs 共同提供關于類標簽c的信息要小于它們單獨提供關于c信息的和，可以表明fi與fs在提供關于c的信息上是冗余的．因此，在定義4 的基礎上，引入三路交互信息，給出冗余特征的評價方法．

定義 5(冗余特征的評價方法) 候選特征fi是冗余特征當且僅當同時滿足 SU(fi，fs)＞SU(c，fi)、R(fi，fs)＞R(c，fi)和I(fi；fs；c)＜0．

在近似馬爾可夫毯的基礎上，引入三路交互信息來評價冗余特征，可以進一步減少將效果顯著的相關特征當作冗余特征而消除的情況．

2.3 算法實現(xiàn)

利用定義3 和定義5，本文實現(xiàn)一種基于對稱不確定性和三路交互信息的特征子集選擇算法(簡記為SUTII)，該算法的偽代碼如下．

SUTII 算法分為兩部分：第1 部分(第1～8 行)，先對候選特征集X、已選特征集S和與c相關的特征集Y進行初始化，然后計算X中的特征與c的SU，將與c相關的特征放入Y中，并將這些特征做降序排序；第2 部分(第9～32 行)，先從Y中取出一個SU為最大值的特征，并放入S中；然后計算fi與S中特征的SU 和c、fi與S中特征的三路交互信息，并分別對SU(c，fi)和SU(fi，fs)進行排序處理，得到R(c，fi)和R(fi，fs)；接著將SU(fi，fs)與SU(c，fi)、R(fi，fs)與R(c，fi)以及I(fi；fs；c)與零值做比較，如果SU(fi，fs)大于SU(c，fi)、R(fi，fs)大于R(c，fi)和I(fi；fs；c)小于零，將fi從Y中消除．按照上述步驟選取特征，直到Y中的特征少于2 個結束．最后，如果Y中有一個特征，將該特征放入S中．

3 實驗結果

3.1 數(shù)據(jù)集和實驗設置

表1 給出用到的數(shù)據(jù)集，它們均取自UCI 機器學習數(shù)據(jù)庫[12]和ASU 特征選擇數(shù)據(jù)庫[13]．采用J48、IB1 和Na?ve Bayes 分類器，其參數(shù)取WEKA[14]默認參數(shù)．采用最小描述長度離散方法[15]．特征選擇過程用到ASU 特征選擇軟件包[16]．實驗中，SUTII算法的參數(shù)δ取10-10．

為減小隨機性對最終結果的影響，進行10 次十折交叉驗證方法[17]處理，將10 次結果的平均值作為最終結果，十折交叉驗證是將數(shù)據(jù)集分成10 等份，其中9 份作為訓練集，剩余的1 份作為測試集，依次進行，直至所有的數(shù)據(jù)集都為測試集；此外，利用顯著性水平為5%的單邊配對樣本t檢驗進行顯著性檢驗．

表1 實驗中用到的數(shù)據(jù)集Tab.1 Used datasets in the experiment

為驗證SUTII 算法的特征選擇效果，將其與FCBF-MIC[11]、SAOLA[6-7]、FCBF[10]和 NFCBF 算法[18]做比較．表2～表4 分別給出這些算法利用J48、IB1 和Na?ve Bayes 分類器選取特征的分類準確率，W/T/L 行給出利用單邊配對t檢驗而得到的值，其中，W、T 和L 分別表示SUTII 算法顯著優(yōu)于、無顯著和顯著劣于其他算法的數(shù)據(jù)集數(shù)．表5 給出這些算法選取的特征數(shù)，表6 給出這些算法特征選擇的用時．

3.2 實驗結果與分析

由表 2 可知，SUTII 算法的平均值最大，而FCBF-MIC 算法的平均值最?。蒞/T/L 值可以得到，SUTII 算法優(yōu)于NFCBF、FCBF-MIC、SAOLA 和FCBF 算法的數(shù)據(jù)集數(shù)分別為4、10、2 和2 個，而劣于這些算法的數(shù)據(jù)集數(shù)分別為2、0、0 和0 個，從而得知SUTII 算法的特征選擇效果優(yōu)于另外4 種算法.

表3 表明，SUTII 算法的平均值最大．由W/T/L值可知，SUTII 算法優(yōu)于 NFCBF、FCBF-MIC、SAOLA 和FCBF 算法的數(shù)據(jù)集數(shù)分別為6、8、8 和3個，與表2 相比，SUTII 算法較SAOLA 和FCBF 算法的優(yōu)勢有所增加．

表4 中，NFCBF 算法的平均值較大．W/T/L 值表明SUTII 算法的特征選擇效果略優(yōu)于FCBF 算法、顯著優(yōu)于FCBF-MIC 和SAOLA 算法，而和NFCBF 算法相當．

由表5 的平均值可知，SAOLA 算法選取的特征最少，SUTII 算法選取的特征與FCBF 算法相當，而多于FCBF-MIC 和SAOLA 算法，NFCBF 算法選取的特征最多，明顯多于其他4 種算法．SUTII 算法在如Sonar 和 Mfeat_fac 等數(shù)據(jù)集上選取的特征占數(shù)據(jù)集全部特征的比重較大，而在如 arcene、CLL_SUB_111 和GLI_85 等數(shù)據(jù)集上選取的特征占的比重較?。?/p>

表2 利用J48分類器選擇特征的平均分類準確率Tab.2 Average accuracy with J48 classifier on the selected features %

表3 利用IB1分類器選擇特征的平均分類準確率Tab.3 Average accuracy with IB1 classifier on the selected features %

表4 利用Na?ve Bayes分類器選擇特征的平均分類準確率Tab.4 Average accuracy with Na?ve Bayes classifier on the selected features %

表5 各算法選擇的特征數(shù)Tab.5 Number of selected features of different algorithms

表6 中，平均值表明SUTII、SAOLA 和FCBF 算法的特征選擇用時較少，明顯少于NFCBF 和FCBFMIC 算法；NFCBF 算法在如arcene、CLL_SUB_111和GLI_85 等數(shù)據(jù)集上的用時較多，而FCBF-MIC 算法在如Mfeat_fac、Isolet 和ORL 等數(shù)據(jù)集上的用時較多．

表6 各算法的用時Tab.6 Time of different algorithms s

4 結 語

本文采用對稱不確定性進行相關性分析和冗余性分析，利用三路交互信息進行交互性分析，提出一種基于對稱不確定性和三路交互信息的特征子集選擇算法SUTII．為驗證SUTII 算法的性能，利用J48、IB1 和Na?ve Bayes 分類器將其與另外4 種特征子集選擇算法NFCBF、FCBF-MIC、SAOLA 和FCBF 在3個UCI 數(shù)據(jù)集和9 個ASU 數(shù)據(jù)集上做對比實驗．實驗結果表明，SUTII 算法能夠取得較好的特征選擇效果，同時選取的特征較FCBF-MIC、SAOLA 和FCBF算法有所增加，驗證了所提冗余特征的評價方法能夠減少將相關特征當作冗余特征而消除的情況，使一些效果較顯著的特征得以保留．