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

周傳華，李 鳴，吳幸運(yùn)

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

0 引 言

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

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

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

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

1 相關(guān)理論

1.1 特征選擇過(guò)程

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

圖1 特征選擇過(guò)程

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

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

評(píng)價(jià)函數(shù)的改進(jìn)是特征選擇的研究熱點(diǎn)，在特征選擇過(guò)程中起著重要作用，將評(píng)價(jià)準(zhǔn)則大致分為五種：距離度量、信息度量、依賴性度量、一致性度量和分類器錯(cuò)誤率度量。

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

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

1.2 互信息理論

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

(1)

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

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

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

(3)

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

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

(4)

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

(5)

I(X;Y;Z)越大，隨機(jī)變量X、Y和Z三者間的相關(guān)性越強(qiáng)，反之越弱。當(dāng)I(X;Y;Z)=0時(shí)，表示隨機(jī)變量X、Y和Z三者相互獨(dú)立。

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

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

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

(6)

其中，I(Xk;C|S)是獨(dú)立于特征子集S的新分類信息，稱為新分類信息，I(Xk;C|S)越大說(shuō)明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)是一個(gè)定值，則I(S;C;Xk)?I(Xk;C|S)-I(S;C;Xk)。因此，ICI平等權(quán)衡了新分類信息和特征冗余。Xj和Xk的獨(dú)立分類信息表示為：

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

(7)

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

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

(8)

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

(9)

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

(10)

MRICIM算法步驟如下所示：

輸入：特征集合F，特征選擇個(gè)數(shù)K，類別Y

輸出：特征子集S

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

2.計(jì)算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.計(jì)算Xi與類別Y的互信息I(Xi;Y)

7.ForXjinS:

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

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

11.S=S+X*

12.F=F-S

13.k=k+1

3 實(shí)驗(yàn)及結(jié)果分析

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

3.2 實(shí)驗(yàn)設(shè)置

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

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

圖2 實(shí)驗(yàn)流程

3.3 實(shí)驗(yàn)結(jié)果和分析

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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