基于對(duì)稱不確定性和三路交互信息的特征子集選擇算法

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

(天津大學(xué)電氣自動(dòng)化與信息工程學(xué)院，天津 300072)

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

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

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

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

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

1.1 三路交互信息

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

式中p(x)為一離散隨機(jī)變量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)是互信息的擴(kuò)展，其可為正、負(fù)和零．當(dāng)I(X；Y；Z)為正值時(shí)，表明兩變量X和Y共同提供關(guān)于Z的信息要大于它們單獨(dú)提供關(guān)于Z信息的和，此時(shí)表明X和Y在提供關(guān)于Z的信息上是互補(bǔ)的；其值為負(fù)值時(shí)，表明X和Y在提供關(guān)于Z的信息上是冗余的；其值為零值時(shí)，表明兩變量在提供關(guān)于Z的信息上是獨(dú)立的．

1.2 馬爾可夫毯

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

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

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

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

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

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

2 本文算法

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

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

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

2.1 相關(guān)特征的評(píng)價(jià)

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

式中SU(c，fi) ∈[0 ，1] ．與類標(biāo)簽的對(duì)稱不確定性值越大，表明該特征與類標(biāo)簽越相關(guān)；當(dāng)與類標(biāo)簽的對(duì)稱不確定性值為零時(shí)，表明該特征與類標(biāo)簽是不相關(guān)的．定義3 給出相關(guān)特征的評(píng)價(jià)方法．

定義 3(相關(guān)特征的評(píng)價(jià)方法)fi是相關(guān)特征當(dāng)且僅當(dāng)滿足SU(c，fi)＞0．

2.2 冗余特征的評(píng)價(jià)

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

冗余性通常是指特征間的關(guān)系．利用對(duì)稱不確定性進(jìn)行冗余性分析．

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

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

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

定義 4(近似馬爾可夫毯)fs是fi的近似馬爾可夫毯當(dāng)且僅當(dāng)同時(shí)滿足 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 可知，同時(shí)滿足SU(fi，fs)＞SU(c，fi)和R(fi，fs)＞R(c，fi)條件的特征才是冗余特征，可以保證效果較顯著的特征被保留．由于只考慮一種度量標(biāo)準(zhǔn)，會(huì)存在將相關(guān)特征當(dāng)作冗余特征而消除的問題．鑒于此，接著進(jìn)行交互性分析．

交互性通常是指兩個(gè)或多個(gè)特征與類標(biāo)簽的關(guān)系．利用三路交互信息進(jìn)行交互性分析．

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

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

在近似馬爾可夫毯的基礎(chǔ)上，引入三路交互信息來評(píng)價(jià)冗余特征，可以進(jìn)一步減少將效果顯著的相關(guān)特征當(dāng)作冗余特征而消除的情況．

2.3 算法實(shí)現(xiàn)

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

SUTII 算法分為兩部分：第1 部分(第1～8 行)，先對(duì)候選特征集X、已選特征集S和與c相關(guān)的特征集Y進(jìn)行初始化，然后計(jì)算X中的特征與c的SU，將與c相關(guān)的特征放入Y中，并將這些特征做降序排序；第2 部分(第9～32 行)，先從Y中取出一個(gè)SU為最大值的特征，并放入S中；然后計(jì)算fi與S中特征的SU 和c、fi與S中特征的三路交互信息，并分別對(duì)SU(c，fi)和SU(fi，fs)進(jìn)行排序處理，得到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(jié)中的特征少于2 個(gè)結(jié)束．最后，如果Y中有一個(gè)特征，將該特征放入S中．

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

3.1 數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

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

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

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

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

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

表4 利用Na?ve Bayes分類器選擇特征的平均分類準(zhǔn)確率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 算法的特征選擇用時(shí)較少，明顯少于NFCBF 和FCBFMIC 算法；NFCBF 算法在如arcene、CLL_SUB_111和GLI_85 等數(shù)據(jù)集上的用時(shí)較多，而FCBF-MIC 算法在如Mfeat_fac、Isolet 和ORL 等數(shù)據(jù)集上的用時(shí)較多．

表6 各算法的用時(shí)Tab.6 Time of different algorithms s

4 結(jié) 語

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