最大相關與獨立分類信息最大化特征選擇算法

周傳華，李 鳴，吳幸運

(1.安徽工業大學 管理科學與工程學院，安徽 馬鞍山 243002；2.中國科學技術大學 計算機科學與技術學院，安徽 合肥 230026)

0 引 言

隨著大數據技術的發展，高維數據已遍布模式識別、自然語言處理和生物信息學等各個領域。數據中包含大量的無關與冗余特征，極大地降低了分類性能，造成“維數災難”[1]。同時，高維數據增加了模型訓練周期，造成計算開銷大、處理效率低。數據降維能有效應對“維數災難”，并縮短模型訓練周期。

數據降維分為特征抽取和特征選擇。特征抽取將高維空間的樣本通過映射或轉化到低維空間，如PCA[2]、LDA[3]等，存在計算效率低、轉化后的特征可解釋性差等問題[4]。特征選擇是從原始特征中去除無關和冗余特征。按照評價準則，特征選擇可分為filter、wrapper和embedded三種模式。wrapper和embedded都是結合分類器來評價特征子集。其中wrapper方法利用分類精度評價特征子集，計算開銷大且易造成模型過擬合，embedded方法在構造分類器的過程中選擇特征，其計算效率高于wrapper方法，但無法避免造成模型過擬合。filter模式以距離、信息、依賴性和一致性等指標作為評價依據，獨立于分類器的學習過程，計算效率高，且易于理解。

基于互信息的評價方法能檢測特征與類別、特征之間的線性和非線性依賴關系，在filter方法中廣泛運用[5]。按照特征評價準則的不同，其可分為最小化特征冗余和最大化新分類信息兩類[3]。最小化特征冗余偏向于選擇與已選特征子集冗余度較少的特征，代表性算法有MIFS[6]、MIFS-ND[7]、mRMR[8]、CMIFS[9]等。最大化新分類信息的方法偏向選擇能貢獻較多的已選特征子集未能提供的分類信息的特征，代表性算法如JMI[10]、JMIM、CMIM[11]、IF[12]、DISR[13]等。在特征選擇過程中，備選特征的冗余性較低，不一定包含較高的新分類信息，反之亦然。特征選擇所選的特征應具有較高的類分辨能力和較低的特征之間的冗余性，需要綜合考慮備選特征的冗余性和提供的新分類信息，Wang等人[14]在2017年提出獨立分類信息(ICI)這一新概念，并提出了基于最大相關性最大獨立性(MRI)的特征選擇算法，其運用ICI綜合衡量特征冗余與新分類信息，并運用互信息衡量特征相關性，選擇出較優的特征子集。Gao等人[15]提出最小冗余最大新分類信息的特征選擇算法(MR-MNCI)，結合mRMR和CMIM的特征評價準則，平衡特征冗余和新分類信息的重要性，取得了較好的效果。Gao等人[16]還通過分析特征相關性的組成，提出了一種考慮特征相關性組合的特征選擇算法(CFR)，運用條件互信息來衡量新分類信息，并利用交互信息評價特征之間的冗余性，選擇出具有高類辨別能力和低冗余的特征。

可見，同時考慮特征冗余與新分類信息的特征選擇算法可獲得具有高類辨別能力和低冗余的特征。但該類算法運用累加求和的方法衡量新分類信息和特征冗余，過高地評價了特征的重要性。因此提出了最大相關與獨立分類信息最大化(MRICIM)特征選擇算法，該算法以互信息衡量特征與類別之間的相關性，運用獨立分類信息綜合衡量特征提供的新分類信息和冗余性，結合最大最小準則構建非線性特征評價準則，來刪除無關特征和冗余特征，從而獲得最佳特征子集。

1 相關理論

1.1 特征選擇過程

特征選擇的具體執行過程如圖1所示，由產生過程、評價函數、停止準則和驗證過程組成。

圖1 特征選擇過程

上圖描繪了候選子集的產生過程，其實質就是特征子集的搜索過程，通過相關評估函數對搜索結果進行評估，特征子集經過相關評估函數后再判斷是否滿足停止準則，若滿足則進一步驗證子集，若不滿足返回重新開始。

對原始數據集進行搜索的過程就是產生候選特征的過程，主要策略包括：全局搜索、啟發式搜索和隨機搜索。其中，全局搜索策略就是從所有可能的特征組合當中選出最優特征子集。這種策略適用于特征個數較少的情況，特征維度較高時，會付出很大代價。常見的全局搜索策略包括分支限界法、廣度優先搜索等。啟發式搜索主要包括序列前向選擇搜索、序列后向選擇搜索以及雙向搜索等。

評價函數的改進是特征選擇的研究熱點，在特征選擇過程中起著重要作用，將評價準則大致分為五種：距離度量、信息度量、依賴性度量、一致性度量和分類器錯誤率度量。

停止準則能決定何時結束算法，停止搜索，利用合適的停止準則可以防止特征的搜索陷入無限循環，而影響停止準則的主要包括搜索算法和評價準則，其中，常見的評價準則一般包括設置特征子集的數目閾值、設置搜索循環的次數閾值、設置評價函數的目標值和搜索的特征子集已經達到最優。

為了對特征子集結果進行有效性驗證，通常進行特征選擇驗證，具體過程就是將特征選擇之后的新數據集在分類器上進行訓練和測試，并與其他特征選擇算法在相關測試集上進行預測對比或將預測的結果與原始數據集進行比較，得到算法的分類性能等。

1.2 互信息理論

信息熵[5]是由香農提出的用來衡量隨機變量的平均不確定程度或信息量，信息熵越大表示隨機變量的不確定性越大，反之越小。對于隨機變量X={x1,x2,…,xm}和Y={y1,y2,…,yn}，p(xi)和p(yj)分別表示隨機變量X=xi、Y=yj時的概率，信息熵H(X)定義如下：

(1)

條件熵表示的是在隨機變量Y已知的條件下，隨機變量X的不確定性，其定義如下：

條件熵可衡量兩隨機變量之間的相互依賴程度，H(X|Y)=H(X)表示兩隨機變量相互獨立。互信息表示的是兩個隨機變量相互依賴的程度，即對于隨機變量X和Y，其中一個隨機變量已知的情況下，另一個隨機變量不確定性的變化情況，隨機變量X和Y之間的互信息I(X;Y)定義為：

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

(3)

I(X;Y)越大表示隨機變量X和Y之間的依賴或相關性越大，反之，依賴或相關性越小。條件互信息指的是在隨機變量Z={z1,z2,…,zk}已知的情況下，隨機變量X和Y的互信息。條件互信息I(X;Y|Z)定義為：

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

(4)

交互信息是衡量三個隨機變量之間共有的不確定性或信息量，X、Y和Z三個隨機變量之間的交互信息I(X;Y;Z)定義為：

(5)

I(X;Y;Z)越大，隨機變量X、Y和Z三者間的相關性越強，反之越弱。當I(X;Y;Z)=0時，表示隨機變量X、Y和Z三者相互獨立。

2 最大相關與獨立分類信息最大化特征選擇算法

假設特征全集為F，已選特征子集為S，Xk∈F-S，即Xk為備選特征，Xj∈S，類別為C。Xk與特征子集S的獨立分類信息[14]可表示為：

ICI(C;Xk,S)=I(Xk;C|S)+I(S;C|Xk)

(6)

其中，I(Xk;C|S)是獨立于特征子集S的新分類信息，稱為新分類信息，I(Xk;C|S)越大說明Xk能夠提供更多的辨別類別的信息，I(S;C|Xk)表示再加入Xk后，特征子集S所保留的分類信息，稱為剩余分類信息。I(S;C|Xk)=I(S;C)-I(S;C;Xk)，I(S;C|Xk)越大，則I(S;C;Xk)越小，I(S;C;Xk)為Xk與特征子集S關于類別C的冗余信息。在一輪特征選擇中，I(S;C)是一個定值，則I(S;C;Xk)?I(Xk;C|S)-I(S;C;Xk)。因此，ICI平等權衡了新分類信息和特征冗余。Xj和Xk的獨立分類信息表示為：

ICI(C;Xk,Xj)=I(Xk;C|Xj)+I(Xj;C|Xk)

(7)

引理：對于Xk、Xi∈F-S，若Xk與S中所有Xj的最小獨立分類信息都小于Xk與S中所有Xj的獨立分類信息，則ICI(C;Xk,S)>ICI(C;Xi,S)。

ICI計算時涉及到單個特征與特征子集之間的獨立分類信息的度量，而該信息量求解的難度大，可操作性低。利用兩兩特征獨立分類信息累加求和的方式計算備選特征與特征子集之間的獨立分類信息，計算方法為：

(8)

為了解決累加求和方式對獨立分類信息的衡量過高，運用上述最小新分類信息和最大最小準則，提出最大相關與獨立分類信息最大化(MRICIM)特征選擇算法，其評價準則模型為：

(9)

根據最小獨立分類信息定義，xk最小獨立分類信息f(Xk)可表示為：

(10)

MRICIM算法步驟如下所示：

輸入：特征集合F，特征選擇個數K，類別Y

輸出：特征子集S

1.初始化S=?,F={X1,X2,…,Xm},k=0;

2.計算I(Xi;Y),Xi∈F

3.S={max(I(Xi;Y)},F=F-max(I(Xi,Y),k=k+1

4.whilek

5.ForXiinF-S:

6.計算Xi與類別Y的互信息I(Xi;Y)

7.ForXjinS:

8.計算當前Xi的新分類信息I(Xi;C|Xj)、Xj的剩余分類信息I(Xj;C|Xi)

10.計算X*=argmax(I(Xi;Y)+F(Xi))

11.S=S+X*

12.F=F-S

13.k=k+1

3 實驗及結果分析

為了驗證該算法的有效性，將與mRMR、JMIM、MRI以及CFR四個具有代表性算法進行比較。統一實驗平臺配置為：操作系統為win10，處理器為Intel(R)core(TM)i5-4200U @1.6 GHz，內存為8 G，實驗環境為Pycharm，語言為python。

3.1 實驗數據

為了能全面地比較特征選擇算法的性能，選擇6個基準評測數據集，這些數據集來源于UCI和文獻[15-16]，其中包含文本數據(BASEHOCK、RELATHE)、生物領域數據(TOX_171)、圖像識別領域數據(COIL20、ORL)等，所選數據集包含離散和連續型數據，詳細描述見表1。

表1 實驗數據集

3.2 實驗設置

對數據集進行預處理，使其滿足分類任務。將名義變量轉化為數值變量，對連續變量按照等寬法進行離散化，設置間隔數為5。在未劃分的數據集上運行特征選擇算法，選擇前25個特征進行比較實驗，選擇KNN(n=3)和NB兩個分類器，采用10折交叉驗證的方式來檢驗分類效果。

利用平均分類準確率、最高分類準確率以及F-measure綜合評價分類性能。其中運用配對樣本的雙尾T檢驗來驗證MRICIM算法與其他算法平均準確率是否有顯著性差異，置信度設置為95%。具體實驗流程如圖2所示。所選算法皆以貪婪策略搜索特征子集，將算法選取的前25個特征分為25組特征子集，每一組較前一組多一個特征(從第二組開始)，在6個數據集上運用NB和KNN分別評估25個特征子集的分類性能。

圖2 實驗流程

3.3 實驗結果和分析

表2和表3分別表示在KNN和NB作為分類器時，各算法在25組特征子集上的平均分類準確率及標準差。“+/=/-”分別表示MRICIM算法在平均準確率上大于/等于/小于其他算法(T檢驗)，“W/T/L”分別表示MRICIM算法在平均準確率上大于/等于/小于其他算法的次數(粗體表示當前數據集上該算法平均分類準確率最高)。就平均分類準確率而言，MRICIM取得了不錯的成績，在所有數據集上平均準確率未低于其他算法，僅在BASEHOCK數據集上與其他算法平均準確率基本相同。綜合考慮KNN和NB分類器的平均分類準確率，在BASEHOCK數據集上MRICIM相對于JMIM最大提升了0.7個百分點，與其他算法表現無差異。在COIL20數據集上MRICIM相對于JMIM最大提升5.4個百分點，相對于mRMR最大提升3.4個百分點，相對于CFR和MRI最大提升1個左右百分點。在Isolet數據集上，MRICIM相對于mRMR最大提升了9.7個百分點，相對于CFR最大提升了2個百分點，相對JMIM最大提升了8.1個百分點，相對于MRI最大提升了3.8個百分點。在ORL數據集上，MRICIM表現很突出，相對于mRMR最大提升了1.5個百分點，相對于CFR最大提升12.5個百分點，相對于JMIM最大提升9.5個百分點，相對于MRI最大提升8.8個百分點。在RELATHE，相對于mRMR最大提升2.3個百分點，相對于CFR最大提升3.4個百分點，相對于JMIM最大提升1.7個百分點，相對于MRI最大提升3.6個百分點。在TOX_171數據集上，相對于mRMR最大提升5.3個百分點，相對于CFR最大提升4.8個百分點，相對于JMIM最大提升4.3個百分點，相對于MRI最大提升4.7個百分點。

表2 各特征選擇算法在KNN上的平均分類準確率(mean±std.)

表3 各特征選擇算法在NB上的平均分類準確率(mean±std.)

圖3給出了各算法在不同數據集上KNN和NB分類器的平均分類準確率的變化情況。橫坐標為特征數量，縱坐標為對應特征數量的情況下，兩分類器的平均分類準確率。在BASEHOCK數據集上，在特征達到一定數量后與JMIM、CFR和MRI取得差不多的效果。在其他數據集上，MRICIM在特征達到一定數量后，MRICIM在兩分類器上的平均分類準確率上基本會一直高于其他方法，且保持上升趨勢。這是由于隨著特征數量的增加，mRMR、CFR和MRI這類用累加求和的方式評價特征會高估特征的重要性，而JMIM雖是非線性的評價準則，但其側重于考慮新分類信息，對冗余信息關注不夠。MRICIM能夠很好地衡量特征相關、特征冗余和新分類信息。需要注意的是在特征選擇的前期，MRICIM選擇的特征可能會較其他算法表現不佳，這是運用最大最小準則無法避免的，這是由于前期用這種非線性評價準則可能會對特征的重要性評價不足，但最終的特征子集具有優秀的分類能力，能夠選擇出較好的特征子集。

圖3 各算法在NB和KNN上的平均準確率變化情況

表4和圖4分別表示NB作為分類器時，各算法在數據集上的最大分類準確度和F1-measure,顯然這兩個方面MRICIM都獲得了很好的效果，基本上優于其他算法。

表4 各特征算法在NB上最大分類準確率(特征數量)

圖4 各算法在NB上的F1-meature

4 結束語

MRICIM在特征選擇過程中綜合考慮了特征與類別的相關性、特征之間的冗余性，以及特征包含的新分類信息，結合最大最小準則對特征的重要性進行非線性評價。實驗結果表明，MRICIM能夠選擇出較高類辨別能力和較低冗余性的特征。但MRICIM在特征選擇的前期表現不是很出眾，基于此，未來將結合其他方法構建一個動態的評價準則，在提升分類效果的同時，減少特征子集的規模。