肖利軍，郭繼昌，顧翔元

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

特征選擇的目的是在全部特征中挑選出最具代表性的特征子集，實現(xiàn)數(shù)據(jù)降維，從而減少后期數(shù)據(jù)處理所需時間[1]。根據(jù)選擇策略的不同，特征選擇算法可以分為3種[2]：嵌入式、封裝式和過濾式。在過濾式算法[3-5]中，信息理論中的互信息是衡量特征關(guān)系的常用指標(biāo)，其中特征間的互信息用于描述特征間的冗余性，特征與類標(biāo)簽間的互信息用于描述特征的相關(guān)性，三路交互信息常用于描述特征與類標(biāo)簽間的交互性。

基于互信息的特征選擇算法大多通過消除冗余特征、保留相關(guān)特征實現(xiàn)特征選擇[6-7]。互信息最大化算法[8]將特征與類標(biāo)簽間的互信息作為特征相關(guān)性的評價指標(biāo)，考慮了特征與類標(biāo)間的相關(guān)性，但由于忽略了特征間的冗余性，算法性能不理想。針對互信息最大化算法中存在的問題，互信息特征選擇算法[9]、最小冗余-最大相關(guān)算法[10]和條件互信息算法[11]，通過引入候選特征與已選特征間的互信息，考慮了特征間的冗余性，性能得到一定提升，但忽略了特征與類標(biāo)簽間的交互性，使目標(biāo)函數(shù)丟失一部分有用信息。因此，一些基于三維互信息的特征選擇算法相繼被提出。DWFS[12]算法和IWFS[13]算法采用一種動態(tài)更新候選特征權(quán)重的方法，通過特征與類標(biāo)簽間的三路交互信息度量特征的交互性，取得了不錯的結(jié)果。但其權(quán)重更新系數(shù)忽略了對特征間冗余性的考慮，因此算法性能仍有提升空間。

針對該問題，筆者在考慮特征的相關(guān)性和交互性的基礎(chǔ)上，進一步利用了特征間的冗余性，提出一種采用冗余性動態(tài)權(quán)重的特征選擇算法(Dynamic Weights Using Redundancy, DWUR)。該算法采用一種動態(tài)更新特征權(quán)重的方法，在每一輪特征選擇之后，計算候選特征與本輪已選特征間的對稱不確定性及與類標(biāo)簽間的三路交互信息，生成權(quán)重更新系數(shù)。通過權(quán)重計算特征的目標(biāo)函數(shù)值，并挑選目標(biāo)函數(shù)值最大的候選特征。在此過程中，算法同時考慮了特征的冗余性、相關(guān)性和交互性信息，以盡量減少目標(biāo)函數(shù)中有用信息的丟失。

1 相關(guān)基礎(chǔ)

假設(shè)X、Y和Z為離散隨機變量，候選特征集為F，候選特征fi∈F，已選特征集為S，已選特征fs∈S，類標(biāo)簽為C?；バ畔⒈硎倦S機變量X與Y共同享有的信息量，定義如下：

(1)

其中，p(x)為概率密度函數(shù)，p(x,y)為聯(lián)合概率密度函數(shù)?；バ畔⒈硎緸殪剡\算的形式如下：

I(X;Y)=H(X)-H(X|Y) ，

(2)

其中，H(X)和H(X|Y)分別為信息熵和條件信息熵。

大多數(shù)特征選擇算法將互信息作為評價特征相關(guān)性的標(biāo)準(zhǔn)，但與類標(biāo)簽互信息值大的特征并不能保證好的分類結(jié)果?；バ畔顾惴▋A向于選擇多值特征，缺乏選擇的公平性，因此使用對稱不確定性描述候選特征fi與類標(biāo)簽C間的相關(guān)性，用S(fi;C)表示。其值越大，代表相關(guān)性越強，如式(3)所示：

(3)

其中,fi與fs間的對稱不確定性代表特征間冗余性系數(shù)，用RR(fi;fs)表示。其值越大，特征間冗余性越強。

(4)

三維互信息包括條件互信息、三路交互信息以及聯(lián)合互信息。條件互信息是指在隨機變量Z給定的情況下，X和Y之間的互信息，定義如下：

(5)

其中，p(x,y,z)表示隨機變量X、Y和Z的聯(lián)合概率密度函數(shù)，p(x,y|z)表示當(dāng)Z給定時X和Y的聯(lián)合概率密度函數(shù)，p(x|z)和p(y|z)表示當(dāng)Z給定時X和Y的概率密度函數(shù)。條件互信息還可以表示為

I(X;Y|Z)=H(X|Z)-H(X|Y,Z) ，

(6)

其中，H(X|Z)和H(X|Y,Z)分別表示當(dāng)Z和Y、Z給定情況下，X的條件熵。

三路交互信息表示隨機變量X、Y和Z共同享有的信息，其與條件互信息具有如下關(guān)系：

I(X;Y;Z)=I(X;Y|Z)-I(X;Y) 。

(7)

基于互信息的特征選擇算法一般將fi、fs和C間的三路交互信息作為評價三者之間交互性的指標(biāo)：

I(fi;fs;C)=I(fi;C|fs)-I(fi;C) 。

(8)

為方便計算，對上式進行歸一化，得到特征與類標(biāo)簽間的交互性系數(shù)，用IR(fi;fs;C)表示

(9)

當(dāng)IR(fi;fs;C)取值為正時，fi和fs之間存在交互信息，指在fs給定的情況下，fi能為分類提供更多有效信息，值越大，交互性越強；為負時，fi和fs之間存在冗余；為零時，fi和fs間相互獨立，互不影響。

2 采用冗余性動態(tài)權(quán)重的特征選擇算法

假設(shè)有候選特征集F，fi∈F(i=1,2,...,N)，為候選特征，N為候選特征總數(shù)，設(shè)有已選特征集S，fj∈S，表示已選特征集中最近被選入特征。所提算法在每一輪特征選擇中，根據(jù)fi與fj的交互性和冗余性信息，動態(tài)更新候選特征fi的權(quán)重系數(shù)，該權(quán)重系數(shù)限制了對應(yīng)候選特征在下一輪選擇中的表現(xiàn)能力，權(quán)重越大，表明其與最近已選特征間交互性越強，冗余性越小。特征權(quán)重的更新方法為

W(fi)k+1=W(fi)k(1+IR(fi;fj;C))(1-βRR(fi;fj))，k=1,2,...,K-1 ，

(10)

其中，W(fi)k代表候選特征fi在第k輪挑選中的權(quán)重，W(fi)k+1代表候選特征fi根據(jù)第k輪所選特征fj更新得到的下一輪權(quán)重，β為系數(shù)項，K代表預(yù)先設(shè)定的特征選擇數(shù)目。RR(fi;fj)與IR(fi;fj;C)分別為特征間的冗余性系數(shù)和特征與類標(biāo)簽間的交互性系數(shù)。

fi與C間的相關(guān)性在特征的目標(biāo)函數(shù)中體現(xiàn)，其定義為

JDWUR(fi)k=W(fi)kS(fi;C) ，k=1,2,...,K，

(11)

式中，JDWUR(fi)k代表在第k輪挑選中fi的目標(biāo)函數(shù)值，W(fi)k代表fi在本輪的權(quán)重，S(fi;C)為fi與C間的對稱不確定性，代表候選特征與類標(biāo)簽間的相關(guān)性。由式(10)和(11)可知，算法在考慮特征相關(guān)性和交互性的基礎(chǔ)上，同時考慮了特征間的冗余性，保證特征的目標(biāo)函數(shù)能最大程度地保留有用信息，消除冗余信息。在每一輪選擇中，算法挑選目標(biāo)函數(shù)值最大的候選特征加入到已選特征集S，并將其作為新的已選特征fj，繼續(xù)下一輪的權(quán)重更新和特征挑選，直到所有特征被挑選完畢或特征選擇數(shù)目達到K。具體執(zhí)行過程的偽代碼如下：

輸入：原始特征集X，類標(biāo)簽C，閾值K，候選特征集F

(1)初始化參數(shù)：k= 0 ,S=Φ,F=X

(2)初始化候選特征權(quán)重：W(fi)1=1 (?fi∈F,i=1,2,...,N)

(3)for eachfi∈F

(4) 根據(jù)式(3)計算各候選特征與類標(biāo)簽間的對稱不確定性

(5)end for

(6)whilek

(7) for eachfi∈F

(8) 根據(jù)式(11)計算各候選特征在當(dāng)前輪的目標(biāo)函數(shù)值JDWUR(fi)k

(9) end for

(11) 將fj添加到已選特征集S=S∪{fj}

(12) 從候選特征集中將fj去除F=F-{fj}

(13) for eachfi∈F

(14) 根據(jù)式(4)計算冗余性系數(shù)

(15) 根據(jù)式(9)計算交互性系數(shù)

(16) 根據(jù)式(10)更新fi的權(quán)重

(17) end for

(18)k=k+ 1

(19)end while

輸出：已選特征集S

(1)～(2)行是初始化過程，設(shè)置特征選擇數(shù)目閾值K，已選特征數(shù)目k= 0，已選特征集S為空集，候選特征集為原始特征集，候選特征初始權(quán)重均為1；(3)～(5)行計算每個候選特征與類標(biāo)簽間的對稱不確定性作為候選特征相關(guān)性的指標(biāo)；(6)～(12)行計算每個候選特征在本輪挑選中的目標(biāo)函數(shù)值，并選擇最大值對應(yīng)的特征作為被選特征，加入到已選特征集S中；(13)～(19)行根據(jù)本輪挑選結(jié)果，動態(tài)更新候選特征集剩余特征對應(yīng)的權(quán)重，用于下輪選擇中目標(biāo)函數(shù)的計算。

假設(shè)原始特征集中特征總數(shù)為N，要計算各特征與類別標(biāo)簽的對稱不確定性(3～5行)，時間復(fù)雜度為O(N)；設(shè)已選特征數(shù)目為k，則候選特征數(shù)目為N-k。在每一輪挑選中，要對每一候選特征計算目標(biāo)函數(shù)值(7～9行)，時間復(fù)雜度為O(N-k)；挑選完成后，計算剩余N-k-1個候選特征對應(yīng)的相關(guān)性系數(shù)、交互性系數(shù)、更新候選特征權(quán)重(13～17行)，時間復(fù)雜度為O(N-k-1)；當(dāng)預(yù)設(shè)的特征選擇數(shù)目閾值為K時，算法總的時間復(fù)雜度為O(NK)。在最壞情況下，當(dāng)N=K，即依次選取全部特征時，算法時間復(fù)雜度為O(N2)。

3 實驗研究

在10個數(shù)據(jù)集上對所提算法進行對比實驗，具體數(shù)據(jù)集信息描述如表1所示。

表1 數(shù)據(jù)集描述

表1中，前6種數(shù)據(jù)集來自于UCI機器學(xué)習(xí)數(shù)據(jù)集，后4種數(shù)據(jù)集來自于ASU數(shù)據(jù)集[14]。實驗選用數(shù)據(jù)集特征數(shù)目分布均勻，Mfeat_zer數(shù)據(jù)集特征數(shù)目最少為47，特征集gisette特征數(shù)目最多為5 000。樣本數(shù)目分布為210～7 000，類別數(shù)目分布為2～40；除Musk1與gisette為2分類數(shù)據(jù)集外，其它均為多分類數(shù)據(jù)集。10個數(shù)據(jù)集中8個為連續(xù)數(shù)據(jù)集，實驗采用MDL離散方法對連續(xù)數(shù)據(jù)集進行離散化。在式(10)中，為保證權(quán)重計算結(jié)果非負，為交互性系數(shù)添加常數(shù)項1。為著重考慮特征間冗余性對特征選擇性能的影響，對冗余性系數(shù)項中的β參數(shù)進行多種取值。實驗證明，在β=0.5時，算法性能較好，因此實驗中β取值為0.5。

利用所提算法和7種基于互信息的算法在上述10個數(shù)據(jù)集上進行對比實驗，對比算法包括CMI[11]、DWFS[12]、IWFS[13]、JMI[15]、CIFE[16]、JMIM[17]和CFR[18]。其中CMI利用特征的相關(guān)性和冗余性構(gòu)建目標(biāo)函數(shù)，其余算法目標(biāo)函數(shù)中引入了三維互信息來考慮特征的交互性。DWFS、IWFS與文中所提算法同屬于動態(tài)更新權(quán)重類方法，其特征選擇性能的對比具有代表性意義。

對特征選擇結(jié)果通過10次10折交叉驗證方法，分別利用3種分類器C4.5、IB1和樸素貝葉斯進行分類，并計算3種分類器的平均分類準(zhǔn)確率。實驗中依次選取前50個特征進行分類，數(shù)據(jù)集特征數(shù)目不足50時選取全部特征進行分類。實驗結(jié)果如圖1所示。其中，橫坐標(biāo)表示依次遞增的所選特征數(shù)目，縱坐標(biāo)表示3種分類器的平均分類準(zhǔn)確率。

由圖1可知，所提算法在10個數(shù)據(jù)集上均取得了不錯的分類結(jié)果，說明所提算法對高維和低維、2分類和多分類數(shù)據(jù)集均具有不錯的特征選擇性能。值得注意的是，相比于DWFS和IWFS算法，由于所提算法在候選特征權(quán)重更新系數(shù)中增加了特征間冗余性的考慮，所以在WarpPIE10P、gisette、Movement_libras、Musk1、Mfeat_pix、Semeion這6個數(shù)據(jù)集上取得了明顯優(yōu)于DWFS和IWFS算法的結(jié)果，說明特征間的冗余性是影響特征選擇算法性能的一個重要因素。

圖1 各算法在10個數(shù)據(jù)集上3個分類器的平均分類準(zhǔn)確率

表2進一步列出了各算法在10個數(shù)據(jù)集上所有分類準(zhǔn)確率的平均值，加粗數(shù)字表示在該數(shù)據(jù)集上達到的最好結(jié)果。

表2 各算法在10個數(shù)據(jù)集上所有平均分類準(zhǔn)確率的平均值

表2顯示，相比于其他算法，所提算法在所有數(shù)據(jù)集上分類準(zhǔn)確率的平均值均最高。對比于DWFS算法，文中所提算法性能提升明顯，進一步說明了在特征權(quán)重更新階段，加入特征間冗余性考慮是有必要的。

表3列出了各算法在10個數(shù)據(jù)集上所有平均分類準(zhǔn)確率的最大值。

由表3可知，文中所提算法在5種數(shù)據(jù)集上效果達到了最好，而且在另外5種數(shù)據(jù)集上表現(xiàn)都是最接近最好結(jié)果的算法，如在Movement_libras數(shù)據(jù)集上雖沒有達到最好結(jié)果，但是其最高平均分類精度為70.80%，基本等于該數(shù)據(jù)集上達到最好結(jié)果的CMI算法的70.81%。

表3 各算法在10個數(shù)據(jù)集上所有平均分類準(zhǔn)確率的最大值

4 結(jié)束語

針對基于互信息特征選擇算法的不足，提出一種采用冗余性動態(tài)權(quán)重的特征選擇算法。算法除考慮特征相關(guān)性和交互性外，還同時利用了特征間的冗余性，以盡可能保證目標(biāo)函數(shù)不丟失有用信息。首先，依據(jù)信息理論給出相關(guān)性、冗余性和交互性的理論說明和客觀評價指標(biāo)，給出了算法的實現(xiàn)過程；然后，在10種數(shù)據(jù)集上采用3種分類器同7種相關(guān)算法做了對比實驗。實驗結(jié)果表明，相比于其他算法，該算法具有明顯的優(yōu)勢。由于數(shù)據(jù)維度高速增長，探究多維特征間的關(guān)系，構(gòu)建更有效的評價指標(biāo)將是今后工作的重點。