周傳華，李 鳴，吳幸運

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

0 引 言

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

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

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

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

1 相關(guān)理論

1.1 特征選擇過程

特征選擇的具體執(zhí)行過程如圖1所示，由產(chǎn)生過程、評價函數(shù)、停止準則和驗證過程組成。

圖1 特征選擇過程

上圖描繪了候選子集的產(chǎn)生過程，其實質(zhì)就是特征子集的搜索過程，通過相關(guān)評估函數(shù)對搜索結(jié)果進行評估，特征子集經(jīng)過相關(guān)評估函數(shù)后再判斷是否滿足停止準則，若滿足則進一步驗證子集，若不滿足返回重新開始。

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

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

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

為了對特征子集結(jié)果進行有效性驗證，通常進行特征選擇驗證，具體過程就是將特征選擇之后的新數(shù)據(jù)集在分類器上進行訓(xùn)練和測試，并與其他特征選擇算法在相關(guān)測試集上進行預(yù)測對比或?qū)㈩A(yù)測的結(jié)果與原始數(shù)據(jù)集進行比較，得到算法的分類性能等。

1.2 互信息理論

信息熵[5]是由香農(nóng)提出的用來衡量隨機變量的平均不確定程度或信息量，信息熵越大表示隨機變量的不確定性越大，反之越小。對于隨機變量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之間的依賴或相關(guān)性越大，反之，依賴或相關(guān)性越小。條件互信息指的是在隨機變量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三者間的相關(guān)性越強，反之越弱。當(dāng)I(X;Y;Z)=0時，表示隨機變量X、Y和Z三者相互獨立。

2 最大相關(guān)與獨立分類信息最大化特征選擇算法

假設(shè)特征全集為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關(guān)于類別C的冗余信息。在一輪特征選擇中，I(S;C)是一個定值，則I(S;C;Xk)?I(Xk;C|S)-I(S;C;Xk)。因此，ICI平等權(quán)衡了新分類信息和特征冗余。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)

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

(9)

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

(10)

MRICIM算法步驟如下所示：

輸入：特征集合F，特征選擇個數(shù)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.計算當(dāng)前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 實驗及結(jié)果分析

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

3.1 實驗數(shù)據(jù)

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

表1 實驗數(shù)據(jù)集

3.2 實驗設(shè)置

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

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

圖2 實驗流程

3.3 實驗結(jié)果和分析

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

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

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

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

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

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

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

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

4 結(jié)束語

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