基于動態(tài)相關性的特征選擇算法

陳永波，李巧勤，劉勇國

（電子科技大學信息與軟件工程學院，成都 610054）

0 引言

特征選擇可以從高維數(shù)據(jù)中抽取相關特征，剔除無關和冗余特征，減小數(shù)據(jù)維度，縮短數(shù)據(jù)處理和模型訓練的時間。按照特征選擇過程與分類算法的不同結合方式，可分為封裝式、嵌入式和過濾式。封裝式特征選擇結合某特定分類算法，根據(jù)分類算法的分類結果以度量特征重要性。此類方法在特征選擇過程中與后續(xù)分類算法相結合，所以選擇的特征子集較好。但該方法效率較低，每次選擇特征時均要執(zhí)行分類算法以判斷特征子集優(yōu)劣。嵌入式特征選擇是將特征選擇過程作為分類算法的一部分，在學習和優(yōu)化算法的過程中，自動地完成特征選擇。如決策樹分類算法通過持續(xù)尋找最優(yōu)特征，使用最優(yōu)特征將數(shù)據(jù)集進行劃分，當數(shù)據(jù)集不可再分或無法選擇最優(yōu)特征時，算法結束并完成特征選擇［1］。此類方法避免每次添加新特征時對模型進行訓練，但較難構建優(yōu)化模型。過濾式特征選擇獨立于分類算法，不使用分類算法的分類結果去評估某個特征，通過評價函數(shù)對數(shù)據(jù)進行特征選擇。相較于前兩類方法，此類方法不依賴任何分類算法，易于理解，簡單高效。過濾式特征選擇常見的評價函數(shù)包括距離度量、依賴性度量、信息度量等。距離度量評價樣本間距離，距離越小，樣本間相似度越高，越可能同屬于一個類別。依賴性度量評價特征與特征或類別與特征間的相關性，與類別相關性大的特征，被認為是好特征。信息度量常用互信息評價特征的優(yōu)劣，特征與類別的互信息越大，特征與類別相關性越高?；バ畔⒌睦碚摶A是信息熵，可以有效地評估變量之間的關系，經常作為過濾式特征選擇的評價函數(shù)；然而基于互信息的傳統(tǒng)過濾式特征選擇，沒有在特征選擇過程中，探究已選特征與類別的動態(tài)變化，可能會造成候選特征的錯誤選擇。針對此類情況，Gao 等［2］提出已選特征和類別動態(tài)變化（Dynamic Change of Selected Feature with the class，DCSF）算法，算法使用條件互信息，計算已選特征和類別間信息量的動態(tài)變化。但DCSF 算法在特征選擇過程中，沒有同時度量候選特征、已選特征、類別間關系，即交互相關性，造成特征與類別的相關性計算不夠精準，導致特征選擇的分類準確率低。

針對DCSF 算法存在的問題，本文提出基于動態(tài)相關性的特征選擇（Dynamic Relevance based Feature Selection，DRFS）算法，利用條件互信息，衡量已選特征/候選特征出現(xiàn)的條件下，候選特征/已選特征和類別的條件相關性，利用交互信息，衡量候選特征-已選特征-類別的交互相關性，以提升特征選擇的分類準確率。實驗結果表明，本文所提算法優(yōu)于對比特征選擇算法，驗證了算法有效性。

1 相關理論

1.1 信息熵

信息理論提供評估隨機變量信息的方法，信息熵用于評估隨機變量不確定程度［3-4］。給定離散型隨機變量X=｛x1，x2，…，xn｝，xi的概率用p（xi）表示，信息熵H（X）定義如式（1）：

給定離散型隨機變量Y={y1，y2，…，ym}，p(xi，yj)表示X和Y的聯(lián)合概率，其中i=1，2，…，n，j=1，2，…，m。聯(lián)合熵H(X，Y)表示X和Y同時出現(xiàn)時的信息量，定義如式（2）：

在Y已知的條件下，X的不確定程度由條件熵度量。設p(xi|yj)表示條件概率，條件熵H(X|Y)的定義如式（3）：

1.2 互信息

互信息I(X；Y) 可衡量X和Y的獨立程度，定義如式（4）：

由式（4）可知，互信息I(X；Y)可等價為給定X的條件下，Y的不確定程度的減少量。如果X可以確定Y，則I(X；Y)的值為H(Y)。如果X和Y無關，即H(Y|X)=H(Y)，則I(X；Y)的值為0。

設Z={z1，z2，…，zk}為離散型隨機變量，條件互信息I(X；Y|Z)表示給定Z，由于Y的加入，X的不確定程度的減少量，定義如式（5）：

其中H(X|Y，Z)是條件熵，表示給定Y和Z條件下，X的不確定程度。聯(lián)合互信息I(X，Y；Z)定義如式（6）：

互信息可度量變量之間雙向相互作用。對于變量X、Y、Z間相互作用，由交互信息I(X；Y；Z) 度 量，定 義［5］如式（7）：

I(X；Y；Z) ＞0 時，表示X和Y發(fā)揮協(xié)同作用，提供X或者Y單獨存在時不能夠提供的信息；I(X；Y；Z) ＜0 時，表明它們提供相同的信息；I(X；Y；Z)=0 時，表示Y(X)的加入，不影響X(Y)與Z的關系。

2 相關工作

基于互信息的過濾式特征選擇，因其易于理解、過程簡單、計算復雜度低等優(yōu)點，得到廣泛研究［6］?；バ畔⒆畲蠡∕utual Information Maximization，MIM）算法［7］根據(jù)候選特征和類別間的互信息值大小，對特征的重要性進行排序，完成特征子集的選擇，評價函數(shù)如式（8）：

其中：Fm表示候選特征，C表示類別。MIM 算法雖然考慮特征相關性，獲得類別相關的特征，但是沒有考慮候選特征和已選特征之間的冗余性，即特征冗余性。良好的候選特征與類別高度相關，而且可以提供已選特征無法提供的信息。

為了彌補MIM 算法的不足，Battiti［8］提出互信息特征選擇（Mutual Information Feature Selection，MIFS）算法，評價函數(shù)如式（9）：

其中：Fj表示已選特征，S表示已選特征集合，β∈[0，1]是調節(jié)特征相關性和特征冗余性的平衡參數(shù)。MIFS 算法第一部分是特征相關性I(Fm；C)，第二部分是特征冗余性I(Fm；Fj)。MIFS 評價函數(shù)的第二項是累加項，隨著S的增大，冗余信息不斷增大，去除冗余特征和選擇相關特征變得困難。針對此問題，Peng 等［9］提出最小冗余性最大相關性（minimal-Redundancy-Maximal-Relevance，mRMR）算法，評價函數(shù)如式（10）：

mRMR 與MIFS 的評價函數(shù)相似，兩者不同之處是平衡參數(shù)，mRMR 算法使用已選特征集合基數(shù)的倒數(shù)，避免隨著已選特征數(shù)量增加，冗余信息不斷增大的問題。

Yang 等［10］提出基 于聯(lián)合 互信息（Joint Mutual Information，JMI）算法。該算法認為候選特征和已選特征具有交互性，評價函數(shù)如式（11）：

由式（11）可知，JMI 算法使用I(Fm；C|Fj)-I(Fm；C)=I(Fm；C；Fj)度量特征交互性。

3 已選特征和類別動態(tài)變化算法

現(xiàn)有基于互信息的特征評價函數(shù)，忽略了已選特征是動態(tài)變化的，只關注候選特征和類別的相關性，沒有思考已選特征和類別的相關性，致使無法區(qū)分候選特征的重要性，如表1 和2［11］所示。

表1 中假設F1為已選擇特征，F(xiàn)2和F3為候選特征，C為類別；表2 分別計算上述特征與類別間互信息、條件互信息以及聯(lián)合互信息。由表2 可 知，I(F1；C|F2)＜I(F1；C)，I(F1；C|F3)＞I(F1；C)，選擇特征F1后，給出候選特征F2和F3，已選特征F1和類別間的信息量是不同的，說明加入候選特征，會導致已選特征與類別的互信息發(fā)生變化，故需揭示信息量變化以評價候選特征。

表1 人工數(shù)據(jù)集Tab.1 Artificial dataset

表2 特征和類別之間的信息量Tab.2 Amount of information between feature and class

針對以上情況，Gao 等［2］在2018 年提出已選特征和類別動態(tài)變化（DCSF）算法，評價函數(shù)如式（12）：

其中：I(Fm；C|Fj)表示在已選特征Fj出現(xiàn)的條件下，候選特征Fm和類別C的相關性；I(Fj；C|Fm)表示在候選特征Fm出現(xiàn)的條件下，已選特征Fj和類別C的相關性；I(Fm；Fj)評估特征的冗余性。DCSF 算法基于條件互信息，在特征選擇過程中，度量已選特征和類別之間動態(tài)變化的信息量。

4 動態(tài)相關性特征選擇算法

DCSF 算法雖然考慮了已選特征和類別的動態(tài)變化，但忽略了交互相關性，對候選特征、已選特征、類別間相關性計算不精確，造成特征選擇分類準確率不足。圖1 展示了DCSF 算法存在的問題。

可見，候選特征Fm的信息量包括：1）已選特征Fj出現(xiàn)，候選特征Fm提供的額外信息量，表示為I(Fm；C|Fj)，即圖1中的第2 部分；2）候選特征Fm出現(xiàn)，提供的額外信息量，表示為I(Fj；C|Fm)，即圖1 中的第3 部分。候選特征Fm的加入，不僅提供了與類別相關的信息量，也提供了冗余的信息量，表示為I(Fm；Fj)?？梢姡珼CSF 算法用條件相關性度量候選特征Fm提供的相關信息，特征冗余性度量候選特征Fm帶來的冗余信息。

由圖1 可知，I(Fm；Fj)包含的信息有第1 部分交互信息和第4 部分類外冗余信息。其中第4 部分是類外冗余信息，與類別無關，無法提供與類別相關的信息［12］。第1 部分是交互信息，候選特征Fm和已選特征Fj可能產生交互性相關性，發(fā)揮正向協(xié)同作用，提供與類別有關的信息［5］。

圖1 特征與類別的關系Fig.1 Relationship between feature and class

由上述可知，DCSF 算法在特征選擇過程中，雖考慮了已選特征和類別的動態(tài)變化信息量，但忽略了交互相關性，對特征與類別的相關性計算不夠精準。針對DCSF 算法存在的上述問題，本文提出基于動態(tài)相關性的特征選擇（DRFS）算法，評價函數(shù)如式（13）：

評價函數(shù)第一項的I(Fj；C|Fm)，度量已選特征Fj和類別C的信息量，隨候選特征Fm的出現(xiàn)，所發(fā)生的動態(tài)變化。出現(xiàn)式（14）的情形：

表示已選特征和候選特征不分享共同的信息，由已選特征提供類別的信息量不會發(fā)生變化。出現(xiàn)式（15）的情形：

表示候選特征的加入，產生冗余且無法提供新的信息，已選特征為類別提供的信息量減少。出現(xiàn)式（16）的情形：

表示候選特征帶來新信息，已選特征為類別提供的信息量增加。

由式（14）～（16）可知，評價函數(shù)第一項的I(Fj；C|Fm)，度量候選特征的加入，已選特征和類別信息量的變化，其值越大，越有利于分類。評價函數(shù)第一項的I(Fm；C|Fj)，由第4章動態(tài)相關性特征選擇算法可知，表示已選特征存在的前提下，候選特征與類別的信息量，度量候選特征對類別的貢獻度。

但是，評價函數(shù)第一項的I(Fm；C|Fj)+I(Fj；C|Fm)是一個線性累加過程，當數(shù)值不斷增大，會產生候選特征錯選的問題［13-14］。DRFS 采用［0-1］標準化，緩解此問題，方法如下。

由互信息、交互信息、條件互信息定義［15］可得：

由式（17）、（18）及信息熵取值范圍［16］，可得：

同理可得：

式（19）和（20）聯(lián)立［9］，可得：

由式（17）～（21）可知，評價函數(shù)第一項的I(Fm；C|Fj)+I(Fj；C|Fm)完成［0-1］標準化，緩解線性累加所產生的候選特征錯選問題。

評價函數(shù)第二項的I(Fj；Fm；C)，度量候選特征Fm和已選特征Fj的協(xié)同作用。由交互信息定義，可得：

出現(xiàn)式（23）的情形：

表示已選特征和候選特征一起出現(xiàn)時，與類別產生的信息量，大于兩者單獨與類別產生的信息量之和，即發(fā)揮正向協(xié)同作用。出現(xiàn)式（24）的情形：

表示已選特征和候選特征相互獨立，與類別的信息量不產生關聯(lián)作用。出現(xiàn)式（25）的情形：

表示已選特征和候選特征存在冗余，發(fā)揮負向協(xié)同作用。

由式（22）～（25）可知，評價函數(shù)第二項的I(Fj；Fm；C)，度量候選特征和已選特征的交互相關性。

同樣地，DRFS 采用［0-1］標準化，緩解評價函數(shù)第二項的I(Fj；Fm；C)線性累加，造成候選特征的錯選問題，方法如下。

由互信息定義，可得：

由互信息性質，可得：

由聯(lián)合熵及聯(lián)合互信息的性質［17］，可得：

由互信息性質，可得：

由式（22）、（28）～（30）聯(lián)立［18］，可得：

由式（26）～（33）可知，評價函數(shù)第二項的I(Fj；Fm；C)完成［0-1］標準化，緩解候選特征的錯選問題［19］。

綜上所述，DRFS 評價函數(shù)第一項的I(Fm；C|Fj)+I(Fj；C|Fm)，采用條件互信息，基于條件相關性，既度量了候選特征對類別的貢獻度，又探究了已選特征和類別的動態(tài)信息量變化；DRFS 評價函數(shù)第二項的I(Fj；Fm；C)，采用交互信息，基于交互相關性，度量了候選特征和已選特征的協(xié)同作 用 ；DRFS 同時將I(Fm；C|Fj)+I(Fj；C|Fm) 和I(Fj；Fm；C)進行［0-1］標準化，盡可能防止在特征選擇過程，因計算線性累加導致候選特征的錯選問題。

DRFS 算法偽代碼如算法1 所示。

算法1 DRFS算法。

DRFS 算法首先初始化變量（第1）～2）行）；然后計算每個特征與類別的互信息值（第3）～5）行）；篩選與標簽具有最大互信息值的特征并添加到已選特征集合S中，完成第一個特征的選擇（第6）～9）行）；最后，根據(jù)式（13）計算每個特征的條件相關性和交互相關性，確定最大信息量特征添加到已選特征集合S，并將其從原始集合F中刪除，直到滿足選擇特征數(shù)K為止（第10）～18）行）。

5 實驗

通過12 個數(shù)據(jù)集進行實驗驗證，以評估DRFS 算法的特征選擇性能。仿真實驗基于Windows 10 操作系統(tǒng)，處理器為Intel，3.30 GHz，內存為8 GB 的PC，通過Matlab 語言編程實現(xiàn)。

5.1 數(shù)據(jù)集

為驗證所提算法的有效性，選取12 個數(shù)據(jù)集，其具體信息如表3 所示。

表3 實驗數(shù)據(jù)集描述Tab.3 Description of experimental datasets

5.2 實驗設置

仿真實驗采用10 重交叉驗證，每項實驗運行10 次。本文算法與JMI［10］、mRMR［9］、最大相關和最大獨立性（Max-Relevance and max-Independence，MRI）［20］、DCSF［2］、最小冗余性和最大依賴性（Min-Redundancy and Max-Dependency，MRMD）［21］算法通過分類準確率對比，選擇特征數(shù)K=50。實驗算法屬于過濾式特征選擇方法，故選擇分類算法支持向量機（Support Vector Machine，SVM）和最近k鄰居（k-Nearest Neighbor，kNN，k=3）進行分類。數(shù)據(jù)集的連續(xù)型數(shù)據(jù)采用分箱離散法處理，箱數(shù)設為5。

5.3 實驗結果與分析

表4 和5 給出實驗算法在仿真數(shù)據(jù)集的實驗結果。

表4 不同算法在3NN分類器上的分類準確率對比 單位：%Tab.4 Comparison of classification accuracy of different algorithms on 3NN classifier unit：%

由表4 可見，DRFS 算法在10 個數(shù)據(jù)集上達到最優(yōu)；由表5 可見，DRFS 算法在9 個數(shù)據(jù)集上達到最優(yōu)。在3NN 分類器上，DRFS 算法與DCFS 算法相比，分類準確率最高提升14.8個百分點，數(shù)據(jù)集lung_discrete、madelon、Yale、warpAR10P、lung、TOX_171、Prostate_GE、leukemia、nci9 的分類準確率提升約6.89 個百分點，數(shù)據(jù)集ORL、lymphoma、GLIOMA 的分類準確率相近。在SVM 分類器上，DRFS 算法與DCFS 算法相比，分類準確率最高提升5.4 個百分點，數(shù)據(jù)集lung_discrete、Yale、ORL、warpAR10P、lung、lymphoma、leukemia、nci9 的分類準確率提升約1.75 個百分點，數(shù)據(jù)集madelon、GLIOMA、TOX_171、Prostate_GE 的分類準確率接近。

表5 不同算法在SVM分類器上的分類準確率對比 單位：%Tab.5 Comparison of classification accuracy of different algorithms on SVM classifier unit：%

由實驗結果可知，mRMR 算法達到最優(yōu)次數(shù)為5 次，僅次于DRFS 算法，根據(jù)式（10）分析，該算法采用了“最小冗余性-最大相關性”原則，并且使用已選特征集合基數(shù)的倒數(shù)緩解線性累加，但是沒有度量交互相關性。JMI 算法達到最優(yōu)次數(shù)為4 次，根據(jù)式（11）分析，該算法雖然度量交互相關性，但是計算平均條件相關，包含部分冗余信息，使得算法分類準確率下降。對于MRMD 算法，分析文獻［21］，該算法提出了一個新的特征冗余項，它既包括了候選特征和已選特征之間的冗余，又考慮了候選特征和給定已選特征的類別之間的相關性。對于MRI 算法，分析文獻［20］，該算法定義了一個新的互信息項，它既包含了候選特征提供的獨立信息，又包含了已選特征保留的獨立信息。MRMD 算法和MRI 算法，都從不同的角度評估已選特征和候選特征的關系，盡可能利用候選特征和已選特征提供的信息。

由實驗結果可知，DRFS 算法總體優(yōu)于DCSF 算法。由于DCSF 算法在特征選擇過程中忽略交互信息帶來的與分類有關的信息量，導致部分候選特征未選出，進而不能產生良好的特征子集。DRFS 算法從三個方面入手，1）采用條件互信息，在特征選擇過程中動態(tài)地衡量已選特征與類別的條件相關性，同時度量候選特征提供的信息量；2）采用交互信息，度量候選特征和已選特征的交互相關性，即二者的協(xié)同作用。3）采用［0-1］標準化方法，一定程度上解決了線性累加導致的候選特征錯選問題。由評價函數(shù)式（13）的理論分析及實驗結果，表明DRFS 算法可以促進相關性計算更加準確，能夠更好地選擇特征子集。

6 結語

針對DCSF 算法在特征選擇過程中忽略交互相關性的問題，提出基于動態(tài)相關性的特征選擇算法DRFS。DRFS 算法使用條件互信息和交互信息，度量特征與類別的條件相關性和交互相關性，以提高特征選擇分類準確率。實驗結果表明，所提算法與DCSF 算法及其他特征選擇算法相比，分類準確率有所提升。

DRFS 算法在度量條件相關性時僅考慮一個候選特征和一個已選特征，但特征選擇過程中存在候選特征與多個已選特征具有條件相關性現(xiàn)象，故后續(xù)將會考慮使用多變量的條件互信息，度量候選特征與多個已選特征之間的條件相關性，進一步提升特征選擇的分類準確率。