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

肖利軍，郭繼昌，顧翔元

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

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

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

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

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

假設(shè)X、Y和Z為離散隨機變量，候選特征集為F，候選特征fi∈F，已選特征集為S，已選特征fs∈S，類標簽為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)性的標準，但與類標簽互信息值大的特征并不能保證好的分類結(jié)果?；バ畔顾惴▋A向于選擇多值特征，缺乏選擇的公平性，因此使用對稱不確定性描述候選特征fi與類標簽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)表示當Z給定時X和Y的聯(lián)合概率密度函數(shù)，p(x|z)和p(y|z)表示當Z給定時X和Y的概率密度函數(shù)。條件互信息還可以表示為

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

(6)

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

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

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

(7)

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

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

(8)

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

(9)

當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ù)和特征與類標簽間的交互性系數(shù)。

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

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

(11)

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

輸入：原始特征集X，類標簽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)計算各候選特征與類標簽間的對稱不確定性

(5)end for

(6)whilek

(7) for eachfi∈F

(8) 根據(jù)式(11)計算各候選特征在當前輪的目標函數(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)行計算每個候選特征與類標簽間的對稱不確定性作為候選特征相關(guān)性的指標；(6)～(12)行計算每個候選特征在本輪挑選中的目標函數(shù)值，并選擇最大值對應(yīng)的特征作為被選特征，加入到已選特征集S中；(13)～(19)行根據(jù)本輪挑選結(jié)果，動態(tài)更新候選特征集剩余特征對應(yīng)的權(quán)重，用于下輪選擇中目標函數(shù)的計算。

假設(shè)原始特征集中特征總數(shù)為N，要計算各特征與類別標簽的對稱不確定性(3～5行)，時間復(fù)雜度為O(N)；設(shè)已選特征數(shù)目為k，則候選特征數(shù)目為N-k。在每一輪挑選中，要對每一候選特征計算目標函數(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)；當預(yù)設(shè)的特征選擇數(shù)目閾值為K時，算法總的時間復(fù)雜度為O(NK)。在最壞情況下，當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)建目標函數(shù)，其余算法目標函數(shù)中引入了三維互信息來考慮特征的交互性。DWFS、IWFS與文中所提算法同屬于動態(tài)更新權(quán)重類方法，其特征選擇性能的對比具有代表性意義。

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

由圖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個分類器的平均分類準確率

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

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

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

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

由表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ù)集上所有平均分類準確率的最大值

4 結(jié)束語

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