基于最大相關(guān)最小冗余聯(lián)合互信息的多標(biāo)簽特征選擇算法

張俐，王樅

（1. 北京郵電大學(xué)軟件學(xué)院，北京 100876；2. 北京郵電大學(xué)可信分布式計(jì)算與服務(wù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100876）

1 引言

近年來，大數(shù)據(jù)、云計(jì)算和人工智能等技術(shù)的迅速發(fā)展，給人類社會生產(chǎn)和生活帶來了前所未有的變化，在這之中就產(chǎn)生了大量的數(shù)據(jù)[1]。這些數(shù)據(jù)逐漸呈現(xiàn)出復(fù)雜化與高維化的趨勢，同時，這些高維數(shù)據(jù)存在著大量的冗余性和無關(guān)性的特征。而這些特征增加了機(jī)器學(xué)習(xí)算法的復(fù)雜度和運(yùn)行時間，同時降低了模型預(yù)測的準(zhǔn)確性，由此帶來了“維數(shù)災(zāi)難”的問題[2]。特征選擇就是通過選取具有代表性的特征子集，用選擇好的特征子集代替全集進(jìn)行學(xué)習(xí)模型的構(gòu)建與訓(xùn)練。簡單說，特征選擇可以通過降低特征維數(shù)，提升學(xué)習(xí)模型的訓(xùn)練速度從而達(dá)到比較好的訓(xùn)練效果。它通常的做法是通過挖掘特征與目標(biāo)對象的相關(guān)性以及特征間冗余性的關(guān)系尋找最佳的特征子集對象。顯然，特征選擇算法已經(jīng)成為大數(shù)據(jù)、云計(jì)算、人工智能背景下企業(yè)商務(wù)活動和經(jīng)濟(jì)決策的重要研究方向，從而引起了國內(nèi)外眾多學(xué)者的關(guān)注[3～6]。目前，常見的降維方法主要分為2類：特征提取和特征選擇。特征提取方法主要是將已經(jīng)存在的特征集轉(zhuǎn)換為一種新的低維特征空間，新的特征集合是以線性或非線性的方式創(chuàng)建的，它代表的方法有線性判別分析[7]（LDA, linear discriminate analysis）、獨(dú)立成分分析（ICA, independent component analysis）和主成分分析[8]（PCA,principal component analysis）；而特征選擇方法是從原始特征集合中選擇出一些最有效的特征以降低數(shù)據(jù)集維度的過程。目前，特征選擇技術(shù)大量被應(yīng)用到數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、圖像處理和自然語言處理等方面。特征選擇算法主要分為2類：一種是依賴分類器模式（wrapper方法[9]和embedded方法），另一種是不依賴分類器模式（filter方法）。wrapper方法是把各種特征子集當(dāng)作測試對象，然后通過某個分類器的分類準(zhǔn)確率作為該組特征子集性能度量指標(biāo)，最后根據(jù)測試的結(jié)果得到最優(yōu)的特征子集。它的主要問題為：一是計(jì)算量非常巨大；二是它采用了窮舉的方式去搜索所有可能的特征組合，方法笨拙且不利于推廣；三是對某個分類器過分依賴，容易出現(xiàn)“過擬合”現(xiàn)象。embedded方法集成在學(xué)習(xí)訓(xùn)練過程中，較wrapper方法計(jì)算簡單而且出現(xiàn)“過擬合”較少，但是尋找適應(yīng)當(dāng)前樣本的函數(shù)模型非常困難。filter方法依據(jù)特征與標(biāo)簽的相關(guān)性進(jìn)行特征排序。filter方法主要優(yōu)點(diǎn)有3個：一是在特征降維方面高效和擴(kuò)展性強(qiáng)；二是它獨(dú)立于某個具體的分類器；三是信息論理論廣泛應(yīng)用在filter方法中，使 filter方法擁有比較扎實(shí)的理論基礎(chǔ)。例如，文獻(xiàn)[10～17]提出的互信息、交互信息、條件互信息和聯(lián)合互信息等。

本文將依賴于信息論的基本理論知識，提出一種新的基于非線性的特征選擇方法——JMMC。該算法的目的就是要克服當(dāng)前 filter方法的某些局限性，例如，對某些特征的高估往往會導(dǎo)致其相關(guān)性和冗余性無法識別等問題。同時，本文算法借用前向搜索方法和最大最小的特征選擇原則，得到更好的特征子集，它能更高效地處理高維數(shù)據(jù)集。在UCI中的9個公開數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn)，結(jié)果顯示本文所提JMMC方法能夠有效地降低數(shù)據(jù)維度，并且也能夠提高不同分類器的分類準(zhǔn)確度。

2 相關(guān)工作

filter方法[18～24]是當(dāng)前特征選擇的一個研究熱點(diǎn)。因此，本節(jié)將詳細(xì)介紹最近幾年基于 filter方法的特征選擇算法。

互信息法[6,14]主要依賴特征與目標(biāo)對象的互信息值大小來排列特征的次序。當(dāng)然在其中可能存在若干個冗余特征。因此，它對于高維特征集合就顯得力不從心。

Kwak等[18]提出了統(tǒng)一信息分布下的互信息特征選擇（MIFS-U, mutual information feature selection under uniform information distribution）方法去改進(jìn)MIFS方法，該方法依然采用特征與目標(biāo)對象去衡量互信息的值，只不過它采用的是基于貪婪性的方法去搜索最有用的特征。

文獻(xiàn)[19,20]提出了MIFS方法的改進(jìn)版本——?dú)w一化互信息的特征選擇方法（NMIFS），它用標(biāo)準(zhǔn)化的互信息取代了原來的互信息，這種做法的優(yōu)點(diǎn)可以避免互信息值在多值時取0的可能。

文獻(xiàn)[21]提出了聯(lián)合互信息的特征選擇方法（JMI, joint mutual information），他們認(rèn)為在聯(lián)合互信息中所選特征子集中特征累加和值最大就是候選特征，那么由這些候選特征構(gòu)成的特征子集就是最優(yōu)子集。

Peng等[22]提出了最小冗余最大相關(guān)特征搜索（minimal redundancy and maximal relevance）算法以及標(biāo)準(zhǔn)mRMR[23]。它們都使用基于互信息值對特征與類標(biāo)簽集C的相關(guān)性以及與所得特征子集S的冗余性進(jìn)行打分，并將得分最高的特征加入S中。mRMR算法的優(yōu)點(diǎn)是它將對特征子集的評價轉(zhuǎn)化為對單個特征的評價，同時將當(dāng)前特征子集中特征間的平均相關(guān)性來表示候選特征與當(dāng)前特征子集之間的冗余性。

文獻(xiàn)[15]提出了 FCBF（fast correlation basd filter solution），這是基于系統(tǒng)不確定性原理的特征選擇方法。它通過候選特征與類別相關(guān)性來進(jìn)行特征排除，然后采用一個近似馬爾可夫毯原理對所得特征子集中冗余特征進(jìn)行刪減。

文獻(xiàn)[24]提出了多標(biāo)簽的特征選擇算法，它主要通過多標(biāo)簽的方式去尋找重要的特征，從而構(gòu)成特征子集。

綜上所述，目前，絕大多數(shù)特征選擇算法關(guān)注的重點(diǎn)依然是特征與標(biāo)簽之間的相關(guān)性和特征之間的冗余性。當(dāng)然，上面介紹的特征選擇方法都有它們各自的局限性。例如，MIFS-U就是當(dāng)所選特征在增加的時候，特征子集的數(shù)目也在增加，同時特征間的冗余性也同樣在增加；mRMR和 NMIFS在每次計(jì)算中僅涉及2個特征間的冗余性度量，這很容易造成某些特征重要性被過分夸大。

3 最大聯(lián)合互信息算法分析與研究

3.1 熵、條件熵、互信息和交互信息

定義1 熵[25]是香農(nóng)在1948年提出的，它主要用來解決信息量化度量的問題。設(shè)隨機(jī)變量Y= {y1,… ,yn}，p(yi)為yi的先驗(yàn)概率，那么H(Y)的熵就可以表示為

從式(1)可知，Y不確定性越大，H(Y)也就越大，那么所需要的信息量也就越大。

定義2 設(shè)隨機(jī)變量X= {x1,… ,xn}，p(xi)為xi的先驗(yàn)概率，Y={y1,… ,ym}，p(yj)為yj的先驗(yàn)概率，那么隨機(jī)變量X和隨機(jī)變量Y的聯(lián)合可以熵表示為

定義3 設(shè)隨機(jī)變量X= {x1,… ,xn}，p(xi)為xi的先驗(yàn)概率，Y={y1,… ,ym}，p(yj)為yj的先驗(yàn)概率，那么隨機(jī)變量Y下隨機(jī)變量X的條件熵可以表示為

定義 4 條件熵與聯(lián)合熵之間的關(guān)系如式(4)所示。

定義 5 互信息[6]是信息論里的一種信息度量工具，它表示一個隨機(jī)變量X中包含的關(guān)于另一個隨機(jī)變量Y的信息量。設(shè)變量X和變量Y，聯(lián)合概率密度函數(shù)是p(xy)，它們邊緣概率密度函數(shù)分別是p(x)、p(y)，那么它們的互信息I(X;Y)可以表示為

同理，根據(jù)式(1)～式(5)，互信息與熵、條件熵和聯(lián)合熵之間的關(guān)系可以表示為

定義6 條件互信息。設(shè)有3個隨機(jī)變量分別是X、Y、C，它們的聯(lián)合概率密度函數(shù)分別是p(XYC)、p(X|C)和p(Y|C)以及條件概率密度函數(shù)p(XY|C)，假設(shè)隨機(jī)變量C是已知的，那么隨機(jī)變量X和隨機(jī)變量Y關(guān)于隨機(jī)變量C的條件互信息I(X;Y|C)可以表示為

依據(jù)互信息和熵的定義，聯(lián)合互信息可以表示為

定義7 交互信息[26]是指在任何特征子集中不存在，但是它卻被所有特征所共享的信息。通常，交互信息I(X;Y;C)與聯(lián)合互信息、互信息之間的關(guān)系可以表示為

通常來說，交互信息值可以是正、負(fù)或 0。當(dāng)隨機(jī)變量X、Y組合在一起共同提交的信息不包含它們各自提交的信息時，交互信息表示為正，而最大交互信息是指隨機(jī)變量X、Y組合在一起所獲得的最大信息值；當(dāng)隨機(jī)變量X、Y各自提交信息包括某些相同的一些信息時，交互信息表示為負(fù)；當(dāng)隨機(jī)引入某個隨機(jī)變量時，并不影響隨機(jī)變量X（或Y）和C之間的關(guān)系時，交互信息表示為0。

3.2 特征的相關(guān)性、冗余性和交互信息

特征相關(guān)性的分析是描述特征重要性的關(guān)鍵方法之一。在信息論中，特征的相關(guān)性根據(jù)其特點(diǎn)可以分為相關(guān)、冗余、無關(guān)和交互。John等[27]將特征分為3類：強(qiáng)相關(guān)、弱相關(guān)和無關(guān)特征。而在一個最優(yōu)特征集合中通常應(yīng)該包括所有的強(qiáng)相關(guān)特征和一部分弱相關(guān)特征，不包括無關(guān)特征等。由于弱相關(guān)特征的組成相當(dāng)復(fù)雜，如何從這些特征中進(jìn)一步篩選出冗余特征，對特征選擇算法性能提升至關(guān)重要。文獻(xiàn)[18～24]提出了許多特征選擇算法中都存在著選擇了一些冗余和不相關(guān)的特征。

因此，下面將結(jié)合信息論中互信息、條件互信息和交換信息的概念，給出判斷特征相關(guān)性的標(biāo)準(zhǔn)。

定義8 假設(shè)數(shù)據(jù)樣本集D= (T,F,C)，n表示樣本的數(shù)量，樣本空間維數(shù)為m，T= {t1,… ,tn}表示樣 本 集 合 ，C= {c1,… ,ck}表 示 標(biāo) 簽 集 合 ，F(xiàn)= {f1,… ,fm}表示特征集合。fi∈F,fj∈F，其中fi≠fj。S?F表示S是F的子集，S′=F?S表示S′是F的子集。

定義 9 特征相關(guān)性。在S已知的情況下，當(dāng)fi?S、fj?S時，如果存在I(fi,C;S) ＞I(fj,C;S)，就表示fi與目標(biāo)標(biāo)簽C的相關(guān)性大于fj與目標(biāo)標(biāo)簽C的相關(guān)性。那么，可以進(jìn)一步推導(dǎo)出，如果fi與fj存在依賴關(guān)系，并且fi?S，S=fj∪S，就可以說明特征fi與目標(biāo)標(biāo)簽C的相關(guān)性會因?yàn)閒j的加入而提高，即I(fi,C;S) ＞I(fi,C)。

定義10 特征冗余性。在S已知的情況下，如果fi與fj存在依賴關(guān)系，fj是冗余特征，并且fi?S，S=fj∪S，那么就可以說明特征fi與目標(biāo)標(biāo)簽C的相關(guān)性會因?yàn)閒j的加入而減少，即I(fi,C;S)＜I(fi,C)。同時，也可以進(jìn)一步表示為I(F;C)≤I(S;C) +I(S′;C)。

定義11 特征無關(guān)性。在S已知的情況下，如果fi與fj之間是無關(guān)的，即表示fi與fj相互獨(dú)立，那么就可以說明特征fi與目標(biāo)標(biāo)簽C的相關(guān)性不會因?yàn)閒j的加入而提高，即I(fi,C;S) =I(fi,C)。

定義12 特征間交互信息。設(shè)fi∈S′，fj∈S，根據(jù)式(9)，如果I(F;C)≥I(S;C) +I(S′;C)，就表示在F集合中的任何一個特征的缺失都會導(dǎo)致降低對目標(biāo)標(biāo)簽C的預(yù)測能力。同時，交互信息值還可以進(jìn)一步表示為當(dāng)不同的特征fj加入S時，特征fi與目標(biāo)標(biāo)簽S的相關(guān)性的值就可以表示為I(fi,C;fj)，那么加入的特征的最小值就可以表示為

3.3 算法推導(dǎo)

從3.2節(jié)可以知道，特征之間、特征與目標(biāo)標(biāo)簽C之間的相關(guān)性完全可以通過I(S′,C;S)與I(S′;C)、I(S′;S)之間的大小差值進(jìn)行確定。因此，I(S′,C;S)與I(S′;C)、I(S′;S)之間的關(guān)系決定了該特征是否是相關(guān)特征、冗余特征和無關(guān)特征。

根據(jù)文獻(xiàn)[3]和文獻(xiàn)[11]，給出特征評價準(zhǔn)則為其中，D(F)表示特征F與標(biāo)簽C的相關(guān)性；Rs(F)表示特征F與所選擇集合S中的特征之間的冗余性；Cs(F)表示特征F與所選擇集合S中的特征之間的交互信息。

再根據(jù)式(8)～式(10)以及文獻(xiàn)[21]就可以推導(dǎo)出最終所要的結(jié)果

將式(11)右邊計(jì)算式展開，設(shè)fi、fj為特征，C為標(biāo)簽，fi∈F?S，fj∈S，ijf≠f，根據(jù)交互信息規(guī)則[24]又有

結(jié)合式(4)～式(12)，有

在實(shí)際中，I(fi;fj|C)求解非常困難，因此本文結(jié)合文獻(xiàn)[11,28～30]給出一種近似求解方法。

令當(dāng)C給定時，Wi,j會因?yàn)镃的存在而不發(fā)生任何變化。因此，可以得出

最后綜合式(13)～式(15)可以得出

3.4 算法描述

通過上面的分析可以知道，在進(jìn)行特征選擇時，除了要充分考慮特征相關(guān)性、冗余性外，還要考慮特征間與標(biāo)簽之間的交互信息，而在第 2節(jié)所分析的特征排序算法中，有些算法只是考慮了特征與標(biāo)簽之間的相關(guān)性；有些算法在考慮特征與標(biāo)簽之間的相關(guān)性以及特征與特征之間的冗余性的同時，卻往往忽略了特征之間還有交互信息的存在[31～36]。因此，本文提出了最大聯(lián)合互信息算法（JMMC），充分考慮了特征與標(biāo)簽之間的相關(guān)性，更進(jìn)一步考慮了某些重要特征對標(biāo)簽?zāi)酥琳麄€數(shù)據(jù)集產(chǎn)生的影響，并且也兼顧考慮了特征與特征之間交互信息，同時也借用了最大相關(guān)最小冗余的思想。下面，給出JMMC特征選擇算法偽代碼實(shí)現(xiàn)，具體如算法1所示。

算法1 JMMC特征選擇

輸入 原始數(shù)據(jù)集D；原始特征集F；類標(biāo)簽集合C

輸出 期望所選的特征排序集S

1) 初始化

2)S←φ;

3) 計(jì)算最大互信息

4) for each ?fi∈Fdo

5) 計(jì)算每一個特征的互信息I(fi;C)，并存入relevant_mi_set集合中

6)fmax=max_sort(relevant_mi_set)

7)F←Ffmax;S←fmax

8) 使用貪婪搜索方法尋找下一個特征

9) repeat untilF集合不為空：

10) 選擇下一個特征方法：

11) 根據(jù)式(16)進(jìn)行計(jì)算

12)F←Ffmax

13)S←S∪fmax

14) 當(dāng)F集合為空時，跳出循環(huán)

15) 輸出所要的排序集合S

步驟1)～步驟2)，初始化最優(yōu)特征集S；步驟3)～步驟7)，選擇和標(biāo)簽類別相關(guān)性最大的特征變量，存入S集合中；步驟8)～步驟14)，使用前向貪婪性搜索方法并結(jié)合式(16)，得到與標(biāo)簽最大相關(guān)且與其他特征兩兩之間最小冗余的特征fmax并加入S中，循環(huán)結(jié)束的標(biāo)志是F特征集合為空。步驟15)，算法就得到了最優(yōu)集S。

4 實(shí)驗(yàn)研究

本節(jié)將對JMMC算法進(jìn)行有效性驗(yàn)證，主要從以下 2個方面證明其有效性：1) 看 JMMC算法是否具有特征降維效果，并能同時提高模型的準(zhǔn)確度；2) 與其他特征選擇方法相比較，JMMC算法是否能有更好的降維效果。本文實(shí)驗(yàn)的研究框架具體如圖1所示。

4.1 特征選擇方法

JMMC算法在設(shè)計(jì)之初，就充分考慮了特征與標(biāo)簽的相關(guān)性以及特征之間的冗余性和交互信息，目的是有效地識別在特征集合中是否有冗余特征和無關(guān)特征的存在。為了解決上面實(shí)驗(yàn)考慮的問題，本文選擇4類具有代表性的特征選擇方法作為 JMMC算法的比較對象，它們分別是FullSet、IG、ReliefF和 FCBF。

1) FullSet方法就是原始特征集合，選擇它的目的就是要研究JMMC算法做的特征選擇是否真的有效，即是否具有特征降維效果，并同時提高模型的準(zhǔn)確度。

2) IG全稱為信息增益（information gain）[6,14]，是一種經(jīng)典的特征排序算法，它主要研究候選特征與標(biāo)簽的相關(guān)性，也就是說候選特征與分類標(biāo)簽越相關(guān)，它們之間的信息增益越大，該特征越重要。最后，根據(jù)特征與標(biāo)簽的相關(guān)性大小順序，進(jìn)行特征排序并輸出。因此，IG特征算法是特征選擇領(lǐng)域中檢驗(yàn)所提算法有效性時最常見的基準(zhǔn)算法之一。

3) ReliefF算法[11]是一種經(jīng)典的基于特征距離的排序算法。它從樣本中的類內(nèi)距離和類間距離來衡量特征之間的差異。一般認(rèn)為好的特征應(yīng)該屬于同一類并且是該樣本的最近的鄰居，而屬于不同標(biāo)簽的樣本應(yīng)該在該特征上取值盡可能不同。在本文中，ReliefF算法中近鄰數(shù)和設(shè)置為 5。

圖1 研究框架

4) FCBF算法在第2節(jié)已有介紹，在此不再贅述。

4.2 分類模型

本文的實(shí)驗(yàn)環(huán)境是lenovo-ThinkPad筆記本，處理器是 Intel(R)-Core(TM) i7-4500UCPU@1.80 GHz,2.4 GHz，內(nèi)存是8 GB，Windows 7 64位操作系統(tǒng)，pycharm和 Anaconda2-(64-bit)開發(fā)環(huán)境，python的運(yùn)行環(huán)境版本是2.7.12。同時，本文采用幾種頻率高的分類器模型，具體如下所示。

1) 近鄰（KNN,k-nearest neighbor）算法，指當(dāng)一個樣本在特征空間中有k個最相鄰的樣本，而這些樣本中的大多數(shù)屬于某一個類別，那么該樣本也屬于這個類別。KNN近鄰分類器是最為經(jīng)典的分類器算法。KNN的近鄰數(shù)設(shè)置為3。

2) 分類與回歸樹（C4.5, classification and regression tree）算法通過entropy或基尼系數(shù)來選擇特征進(jìn)行分叉。最終將具有p維特征的n個樣本分到c個類別中去。在本文中，C4.5采用基尼系數(shù)進(jìn)行特征分叉。

3) 支持向量機(jī)（SVM, support vector machine），指通過升維把低維樣本向高維空間做映射，使原本在低維樣本空間中非線性可分的問題轉(zhuǎn)化為在特征空間中線性可分的問題。SVM分類器的參數(shù)都使用sklearn包的默認(rèn)參數(shù)設(shè)置。

4) 混合分類器，就是將3KNN、C4.5和SVM進(jìn)行混合來看它們整體的分類結(jié)果，在這里，3KNN、C4.5和SVM中的權(quán)重均取。

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

本文選擇的實(shí)驗(yàn)數(shù)據(jù)全部來自國際通用的UCI機(jī)器學(xué)習(xí)的數(shù)據(jù)集，它們分別是 heart、dermatology、movement_libra、wdbc、arrhythmia、musk、mfeat-kar、mushroom、kr-vs-kp這 9個數(shù)據(jù)集，詳細(xì)內(nèi)容如表1所示。樣本數(shù)據(jù)分類數(shù)為2～15個，樣本數(shù)為270～8 124個，樣本的特征數(shù)為14～279維。為了保證數(shù)據(jù)更有說服性，整個實(shí)驗(yàn)過程采用 10折交叉驗(yàn)證[37]對實(shí)驗(yàn)數(shù)據(jù)集進(jìn)行測試和評價，最后，通過對10次實(shí)驗(yàn)求均值得到最后的實(shí)驗(yàn)結(jié)果。

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

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

本文均采用Accuracy預(yù)測特征算法的優(yōu)劣。同時，為了進(jìn)一步說明不同算法在不同分類器和數(shù)據(jù)集的優(yōu)劣，本文使用 Win/Draw/Loss來統(tǒng)計(jì)并分析算法兩兩之間的差異。Win表示算法A好于B，Draw表示算法A等于B，Loss表示算法A差于B。

4.5 小樣本低維數(shù)據(jù)集的分析

在小樣本數(shù)據(jù)集合中，平均樣本數(shù)為390個，平均特征數(shù)為 42.75。表 2～表 4給出了所選擇 4種數(shù)據(jù)集上不同分類器（3KNN、C4.5和SVM）采用 10折交叉驗(yàn)證法所獲得的平均分類準(zhǔn)確率和特征數(shù)。表5給出了所選擇4種數(shù)據(jù)集上混合分類器（由3KNN、C4.5和SVM組成）采用10折交叉驗(yàn)證法所獲得的平均分類準(zhǔn)確率和特征數(shù)。圖2～圖5給出了這4種數(shù)據(jù)集合的顯示混合分類器效果，其中，橫坐標(biāo)表示依次遞増的所選特征子集數(shù)目，縱坐標(biāo)表示平均分類率準(zhǔn)確率。根據(jù)表 2～表 5以及圖 2～圖 5所示的實(shí)驗(yàn)結(jié)果，JMMC算法使用3KNN分類器在heart數(shù)據(jù)集、dermatology數(shù)據(jù)集、movement_libra數(shù)據(jù)集和wdbc數(shù)據(jù)集上比FullSet要高出4.074%、0.833%、0.666%和1.391%；并且，JMMC算法使用C4.5分類器在 heart數(shù)據(jù)集、dermatology數(shù)據(jù)集、movement_libra數(shù)據(jù)集和 wdbc數(shù)據(jù)集上比FullSet要高出1.852%、0.833%、0.666%和1.391%；JMMC算法使用 SVM 分類器在 heart數(shù)據(jù)集、dermatology數(shù)據(jù)集、movement_libra數(shù)據(jù)集和wdbc數(shù)據(jù)集上比FullSet要高出1.481%、0.294%、

0.889%和 5.596%；JMMC算法使用混合分類器在heart數(shù)據(jù)集、dermatology數(shù)據(jù)集、movement_libra數(shù)據(jù)集和wdbc數(shù)據(jù)集上比FullSet要高出10.745%、1.23%、0.889%和6.625%。通過對以上4種數(shù)據(jù)集在不同分類器以及它們的混合分類器來看，JMMC算法均起到了降低數(shù)據(jù)冗余度、提高分類準(zhǔn)確度的效果，同時，從表2～表5可以看出，由于分類器從弱變強(qiáng)，分類的效果也會變好，并且所需要的平均特征數(shù)也會相應(yīng)減少?，F(xiàn)在，再來對比JMMC算法和其他特征排序算法，從表2～表5可以看出，JMMC算法在絕大多數(shù)情況下均優(yōu)于其他所選擇的特征排序算法，具體描述可以從表6看出。

表2 基于3KNN分類器的所選特征集平均準(zhǔn)確率

表3 基于C4.5分類器的所選特征集平均準(zhǔn)確率

表4 基于SVM分類器的所選特征集平均準(zhǔn)確率

表5 基于混合分類器和不同算法的平均準(zhǔn)確率

綜上可得，在小樣本集中，JMMC算法在特征的選擇上由于更多地考慮了特征間冗余性與交互信息，所以說分類的準(zhǔn)確率更好一些。

圖2 heart數(shù)據(jù)集不同算法的平均正確率

圖3 dermatology數(shù)據(jù)集不同算法的平均正確率

圖4 movement_libra數(shù)據(jù)集不同算法的平均正確率

圖5 wdbc數(shù)據(jù)集不同算法的平均正確率

4.6 大樣本高維數(shù)據(jù)集的分析

在大樣本數(shù)據(jù)集合中，平均樣本數(shù)是2 843個，平均特征數(shù)為114。表7～表9給出了所選擇5種數(shù)據(jù)集上不同分類器（3KNN、C4.5和SVM）采用 10折交叉驗(yàn)證法所獲得的平均分類準(zhǔn)確率和特征數(shù)。表10給出了所選擇5種數(shù)據(jù)集上混合分類器（由3KNN、C4.5和SVM組成）采用10折交叉驗(yàn)證法所獲得的平均分類準(zhǔn)確率和特征數(shù)。圖6～圖10給出了這5種數(shù)據(jù)集合的顯示混合分類器效果，其中橫坐標(biāo)表示依次遞増的所選特征子集數(shù)目，縱坐標(biāo)表示平均分類率準(zhǔn)確率。根據(jù)表7～表10以及圖6～圖10所示的實(shí)驗(yàn)結(jié)果，JMMC算法使用 3KNN分類器在 arrhythmia數(shù)據(jù)集、musk數(shù)據(jù)集、mfeat-kar數(shù)據(jù)集、mushroom數(shù)據(jù)集和kr-vs-kp數(shù)據(jù)集上比FullSet要高出0.933%、1.549%、0、0和 3.538%；并且，JMMC算法使用C4.5分類器在arrhythmia數(shù)據(jù)集、musk數(shù)據(jù)集、mushroom數(shù)據(jù)集和kr-vs-kp數(shù)據(jù)集上比FullSet要高出5.456%、0.195%、0和0；JMMC算法使用SVM分類器在arrhythmia數(shù)據(jù)集、musk數(shù)據(jù)集、mfeat-kar數(shù)據(jù)集、mushroom數(shù)據(jù)集和 kr-vs-kp數(shù)據(jù)集上比FullSet要高出2.066%、2.789%、0、1.476%和 0；JMMC算法使用混合分類器在arrhythmia數(shù)據(jù)集、musk數(shù)據(jù)集、mfeat-kar數(shù)據(jù)集、mushroom數(shù)據(jù)集和 kr-vs-kp數(shù)據(jù)集上比FullSet要高出1.082%、0.286%、0.133%、0.607%和 1.18%。從以上的數(shù)據(jù)分析可以看出，JMMC算法只是在使用C4.5分類器時在mfeat-kar數(shù)據(jù)集上略低于FullSet，其他均優(yōu)于或等同于FullSet。同時，通過對以上5種數(shù)據(jù)集在不同分類器以及它們的混合分類器來看，JMMC算法起到了降低數(shù)據(jù)冗余度、提高分類準(zhǔn)確度的效果，同時，從表 8～表 10可以看出，由于分類器從弱變強(qiáng)，分類的效果也會變好，并且，所需要的平均特征數(shù)也會相應(yīng)減少，其中在基于 SVM 的分類器表現(xiàn)得尤為明顯，特征數(shù)平均只需要32.4個。現(xiàn)在，再來對比JMMC算法和其他特征排序算法，從表7～表9可以看出，JMMC算法大部分均優(yōu)于其他所選擇的特征排序算法，可能由于分類器的原因造成在個別數(shù)據(jù)集上和不同分類器上存在JMMC算法略低于其他特征排序算法，這些具體情況都可以從表11看出?，F(xiàn)在，可以得出在大樣本集中，JMMC算法在特征的選擇上由于充分地考慮了特征間冗余性與交互信息，分類準(zhǔn)確率相比其他算法要更好一些。

表6 JMMC算法與其他基于特征排序算法的Win/Draw/Loss分析

表7 基于3KNN分類器的所選特征集平均準(zhǔn)確率

表8 基于C4.5分類器的所選特征集平均準(zhǔn)確率

表9 基于SVM分類器的所選特征集平均準(zhǔn)確率

表10 基于不同分類器和不同算法的平均準(zhǔn)確率

表11 JMMC算法與其他基于特征排序算法的Win/Draw/Loss分析

圖6 arrhythmia數(shù)據(jù)集不同算法的正確率

圖7 musk數(shù)據(jù)集不同算法的平均正確率

圖8 mfeat-kar數(shù)據(jù)集不同算法的平均正確率

圖9 mushroom數(shù)據(jù)集不同算法的平均正確率

圖10 kr-vs-kp數(shù)據(jù)集不同算法的平均正確率

5 結(jié)束語

特征選擇算法主要是盡可能尋找較小的特征子集，從而獲得較高分類預(yù)測準(zhǔn)確率。本文通過引入條件互信息和交互信息，并依賴最大最小原則建立新的特征排序算法（JMMC算法）。它不僅考慮特征的相關(guān)性、冗余性和無關(guān)性，也充分考慮了特征間與目標(biāo)標(biāo)簽之間的交互信息。首先，依據(jù)信息論理論，重新定義了相關(guān)性、冗余性、無關(guān)性和交互信息。其次，給出了 JMMC算法的推導(dǎo)和實(shí)現(xiàn)過程。在UCI公開的9個樣本集和4種不同的分類器（3KNN、C4.5、SVM和混合分類器）中，JMMC算法在絕大多數(shù)情況下，平均分類準(zhǔn)確率均優(yōu)于其他特征排序算法。

綜上可知，JMMC算法不僅能有效識別出相關(guān)特征、冗余特征和無關(guān)特征，而且也能識別出特征間產(chǎn)生交互信息的那些特征。因此，JMMC算法可以有效地提高分類的準(zhǔn)確度，并且降低特征的維數(shù)。下一步的工作將是對交互信息、條件互信息等理論進(jìn)行更進(jìn)一步的研究，以便能提出更加有效的特征排序算法來優(yōu)化選擇出的特征子集并進(jìn)一步提高它們分類的準(zhǔn)確率。

[1] GEORGE G, HAAS M R, PENTLAND A. Big data and management[J]. Academy of Management Journal,2014,57(2)∶321-326.

[2] XIE J Y, XIE W X. Several selection algorithms based on the discernibility of a feature subset and support vector machines[J].Chinese Journal of Computers, 2014,37(8)∶1704-1718.

[3] BROWN G, POCOCK A, ZHAO M J, et al. Conditional likelihood maximisation-a unifying framework for information theoretic feature selection[J].Journal of Machine Learning Research, 2012,13∶27-66.

[4] CHENG H G, QIN Z, FENG C, et al. Conditional mutual information based feature selection analysing for synergy and redundancy[J].Electronics and Telecommunications Research Institute, 2011(33)∶210-218.

[5] CHANDRASHEKAR G, SAHIN F .A survey on feature selection methods[J].Computers and Electrical Engineering, 2014(40)∶16-28.

[6] ZHANG Z H, LI S N, LI Z G, et al. Multi-label feature selection algorithm based on information entropy[J].Journal of Computer Research and Development, 2013,50(6)∶1177-1184.

[7] YU H, YANG J.A direct LDA algorithm for high-dimensional data with application to face recognition[J].Pattern Recognition, 2001(34)∶2067-2070.

[8] BAJWA I S, NAWEED M S, ASIF M N, et al. Feature based image classification by using principal component analysis[J].ICGST International Journal on Graphics Vision and Image Processing, 2009(9)∶ 11-17.

[9] MALDONADO S, WEBER R. A wrapper method for feature selection using support vector machine[J].Information Science, 2009, 179(13)∶2208-2217.

[10] PENG C. DistributedK-Means clustering algorithm based on Fisher discriminant ratio[J].Journal of Jiangsu University, 2014, 35(4)∶422-427.

[11] ZHANG Y S, YANG A, XIONG C, et al. Feature selection using data envelopment analysis[J].Knowledge-Based Systems,2014(64)∶70-80.

[12] YU L, LIU H. Feature selection for high-dimensional data∶ a fast correlation-based filter solution[C]//The 20th International Conferences on machine learning. 2003∶ 856-863.

[13] HUANG D, CHOW T W S. Effective feature selection scheme using mutual information[J]. Neurocomputing,2005 (63)∶325-343.

[14] LIU H W, SUN J G, LIU L, et al. Feature selection with dynamic mutual information[J]. IEEE Transactions on Neural Networks, 2009,20(2)∶ 189-201.

[15] DUAN H X, ZHANG Q Y, ZHANG M.FCBF algorithm based on normalized mutual information for feature selection[J].Journal Huazhong University of Science & Technology(Natural Science Edition), 2017,45(1)∶52-56.

[16] SUN G L, SONG Z C, LIU J L, et al. Feature selection method based on maximum information coefficient and approximate markov blanket[J]. Acta Automatica Sinica, 2017,43(5)∶795-805.

[17] VERGARA J R, ESTEVEZ P.A review of feature selection methods based on mutual information[J].Neural Computing and Applications,2014,24(1)∶175-186.

[18] KWAK N, CHOI C H. Input feature selection for classification problems[J]. IEEE Transactions on Neural Networks, 2002(13)∶143-159.

[19] ESTéVEZ P A, TESMER M, PEREZ C A, et al. Normalized mutual information feature selection[J].IEEE Transaction on Neural Networks,2009(20)∶189-201.

[20] HOQUE N, BHATTACHARYYA D K, KALITA J K.MIFS-ND∶a mutual information-based feature selection method[J]. Expert Systems with Applications,2014,41(14)∶6371-6385.

[21] HOWARD H Y, JOHN M. Feature selection based on joint mutual information[C]//Advances in Intelligent Data Analysis (AIDA), Computational Intelligence Methods and Applications (CIMA), International Computer Science Conventions Rochester New York. 1999∶ 1-8.

[22] PENG H, LONG F, DING C, Feature selection based on mutual in-formation∶ criteria of max-dependency, max-relevance, and min- redundancy[C]//IEEE Transaction on Pattern Analysis & Machine Intelligence. 2005, 27 (8)∶ 1226-1238

[23] VINH L T, THANG N D, LEE Y K. An improved maximum relevance and minimum redundancy feature selection algorithm based on normalized mutual information[C]//Tenth International Symposium on Applications and the Internet. 2010∶ 395-398.

[24] LEE J, KIM D W. Mutual information-based multi-label feature selection using interaction information[J].Expert Systems with Applications,2015(42)∶ 2013-2025.

[25] COVER T, THOMAS J.Elements of theory[M]. New York∶ John Wiley & Sons, 2002.

[26] JAKULIN A. Attribute interactions in machine learning (Master thesis)[M]//Lecture Notes in Computer Science. 2003.

[27] JOHN G H, KOHAVI R, PFLEGER K. Irrelevant features and the subset selection problem[C]//The Eleventh International Conference on Machine Learning, 1994∶ 121-129.

[28] BENNASAR M, HICKS Y, SETCHI R. Feature selection using Joint mutual information maximisation[J]. Expert System Application,2015(42)∶ 8520-8532.

[29] ZHANG Y S, ZHANG Z G. Feature subset selection with cumulate conditional mutual information minimization[J]. Expert Systems with Applications, 2012,39(5)∶6078-6088.

[30] YU L, LIU H. Efficient feature selection via analysis of relevance and redundancy[J]. Journal of Machine Learning Research, 2004, 5(12)∶1205-1224.

[31] TAPIA E, BULACIO P, ANGELONE L F. Sparse and stable gene selection with consensus SVM-RFE[J]. Pattern Recognition Letters,2012,33(2)∶164-172.

[32] UNLER A, MURAT A, CHINNAM R B. mr2PSO∶ a maximum relevance minimum redundancy feature selection method based on swarm intelligence for support vector machine classification[J]. Information Sciences, 2011(20)∶ 4625-4641.

[33] CHE J X, YANG Y L LI L, et al. Maximum relevance minimum common redundancy feature selection for nonlinear data[J]. Information Sciences, 2017(5)∶68-89.

[34] CHAKRABORTY R, PAL N R. Feature selection using a neural framework with controlled redundancy[J].IEEE Transactions on Neural Networks and Learning Systems, 2015,26 (1) ∶35-50.

[35] AKADI A E, OUARDIGHI A, ABOURAJDINE D.A powerful feature selection approach based on mutual information[J]. International Journal of Computer Science and Network Security, 2008(8)∶116-211.

[36] FLEURET F. Fast binary feature selection with conditional mutual information[J]. Journal of Machine Learning Research, 2004(5)∶1531-1555.

[37] NIU X T. Support vector extracted algorithm based on KNN and 10 fold cross-validation method[J].Journal of Huazhong Normal University, 2014,48(3)∶335-338.