基于遺傳算法和互信息公式結(jié)合的特征選擇

涂昌慧，葛 紅 ，胡天亮

(華南師范大學(xué)計算機(jī)學(xué)院，廣州510631)

特征選擇是統(tǒng)計學(xué)、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域中的經(jīng)典問題. 在模式識別中，它根據(jù)一些準(zhǔn)則，在刪除一組不相關(guān)、冗余的特征后，選出對分類最有效的特征以達(dá)到降低特征空間維數(shù)，使得如分類、回歸模型等任務(wù)達(dá)到和特征選擇前近似甚至更好的預(yù)測精度［1］.

特征選擇方法大致可以分為封裝式(Wrapper)、過濾式(Filter)和嵌入式(Embedded)等3 類.封裝式特征選擇方法準(zhǔn)確率較高，但容易出現(xiàn)過擬合現(xiàn)象，魯棒性較差，依賴具體的學(xué)習(xí)算法，不適合大規(guī)模數(shù)據(jù)集［2］.過濾式特征選擇方法的評估依賴于數(shù)據(jù)集本身，其可擴(kuò)展性、魯棒性高，適合大規(guī)模數(shù)據(jù)集［3］，但沒有考慮與學(xué)習(xí)算法間的關(guān)系，得到的子集性能較差，嵌入式特征選擇方法運(yùn)行速度較快，選擇的特征與分類性能有關(guān)，但其依賴于學(xué)習(xí)算法的選擇，魯棒性不高.

遺傳算法是一種自適應(yīng)的全局搜索方法，具有并行性和適合于解決多目標(biāo)優(yōu)化等特性. 互信息是2個隨機(jī)變量統(tǒng)計相關(guān)性的測度.在特征選擇中，互信息度量特征與類別標(biāo)簽的相關(guān)性是一種基于相關(guān)性的過濾式特征選擇方法. 為了充分利用遺傳算法和互信息的優(yōu)點(diǎn)，本文結(jié)合遺傳算法和互信息進(jìn)行特征選擇.

1 相關(guān)概念

1.1 遺傳算法

遺傳算法(Genetic Algorithm，GA)是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法. 其基本思想是從任意初始群體出發(fā)，通過隨機(jī)選擇、交叉和變異操作，產(chǎn)生一群更適應(yīng)環(huán)境的個體.

遺傳算法首先需實(shí)現(xiàn)從表現(xiàn)型到基因型的映射，即編碼.初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生更好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度大小選擇個體，并借助于遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新解集的種群.遺傳算法在進(jìn)化搜索過程中僅以適應(yīng)度函數(shù)為依據(jù)，所以適應(yīng)度函數(shù)直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解［4］. 遺傳算法的3個基本操作:

(1)選擇.根據(jù)個體的適應(yīng)度值，按照一定的規(guī)則或方法，從上一代群體中選擇出一些優(yōu)良的個體遺傳到下一代種群中. 選擇的依據(jù)是適應(yīng)性強(qiáng)的個體為下一代貢獻(xiàn)一個或多個后代的概率大.

(2)交叉.交叉是把2個父個體的部分結(jié)構(gòu)加以替換而生成新個體的操作.交叉操作產(chǎn)生的新一代個體，既保留了雙親的部分基因，又引入新的基因.

(3)變異. 變異可以防止求解過程中過早收斂產(chǎn)生局部最優(yōu)解而非總體最優(yōu)解.其操作為:對種群中的每個個體，以變異概率改變某一個或多個基因座上的基因值.變異本身是一種局部隨機(jī)搜索，與選擇算子結(jié)合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機(jī)搜索能力，同時保持種群的多樣性，防止出現(xiàn)非成熟收斂.

1.2 互信息

互信息(Mutual Information，MI)是信息論中的一個基本概念.它表示2個變量間共同擁有信息的含量.系統(tǒng)的不確定性或復(fù)雜性可以用信息熵來描述.對于一個隨機(jī)變量集X，其中任一xX，其概率分布函數(shù)用PX(x)表示，則集合X 的熵H(X)定義如下:

如果系統(tǒng)越有序，它的不確定性就越小，即熵值也越小，所含的確定信息越大.

給定2個隨機(jī)變量集X 和Y，其條件熵分別定義:

隨機(jī)變量集X 和Y 間的統(tǒng)計相關(guān)性可以用聯(lián)合熵來描述，其定義:

其中，H(X)表示Y 未知時的熵，即X 的不確定性;H(X|Y)表示已知Y 后X 的不確定性，那么在知道Y后X 的不確定性減少量為H(X)－H(X|Y).這個不確定性的減少量即為互信息，它反映了Y 包含X 中信息的多少，可以描述為:

對于2個離散的隨機(jī)變量X 和Y 還可以用2個變量的聯(lián)合概率密度分布PXY(x，y)與2個變量完全獨(dú)立時的聯(lián)合概率分布PX(x)·PY(y)來表示互信息:

由定義可知，當(dāng)變量X 和Y 完全無關(guān)或相互獨(dú)立時，它們的互信息為0，說明它們之間不存在相同的信息;反之，當(dāng)互信息值越大，它們間的相互依賴度越高，包含的相同信息也越多.

條件互信息是指在給定某個隨機(jī)變量的條件下，其他2個變量之間的相互依賴程度.假如隨機(jī)變量Z 已知，那么變量X 和Y 關(guān)于Z 的條件互信息為:

其中PXYZ(x，y，z)為聯(lián)合概率分布，P(x|z)、P(y|z)和P(x，y|z)均為條件概率分布.

1.3 BP 神經(jīng)網(wǎng)絡(luò)

BP 神經(jīng)網(wǎng)絡(luò)是一種多層前饋神經(jīng)網(wǎng)絡(luò)，該網(wǎng)絡(luò)的主要特點(diǎn)是信號向前傳遞的，而誤差反向傳播.在前向傳遞中，輸入信號從輸入層經(jīng)隱含層逐層處理，直至輸出層.如果輸出層得不到期望輸出，則轉(zhuǎn)入反向傳播，根據(jù)預(yù)測誤差調(diào)整網(wǎng)絡(luò)的權(quán)值和閾值，從而使BP 神經(jīng)網(wǎng)絡(luò)預(yù)測輸出不斷逼近期望輸出. 由于BP 神經(jīng)網(wǎng)絡(luò)包含多個隱含層，故其具備處理線性不可分問題的能力.

1.4 概率神經(jīng)網(wǎng)絡(luò)

網(wǎng)絡(luò)概率神經(jīng)網(wǎng)絡(luò)(Probabilistic Neural Networks，PNN)是一種徑向基神經(jīng)網(wǎng)絡(luò)，在RBF 網(wǎng)絡(luò)的基礎(chǔ)上，融合了密度函數(shù)估計和貝葉斯決策理論.概率神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)簡單，能用線性學(xué)習(xí)算法實(shí)現(xiàn)非線性學(xué)習(xí)算法的功能［5］.PNN 不像傳統(tǒng)的多層前向網(wǎng)絡(luò)那樣需要用BP 算法進(jìn)行反向誤差傳播的計算，而是完全前向的計算過程.在某些易滿足的條件下，以PNN 實(shí)現(xiàn)的判別邊界漸進(jìn)地融入貝葉斯最佳判定面. PNN 訓(xùn)練時間短、不易產(chǎn)生局部最優(yōu)，且它的分類正確率較高. 研究表明概率神經(jīng)網(wǎng)絡(luò)收斂速度快，具有很強(qiáng)的容錯性、擴(kuò)充性能好等特性.

2 GA-MI 算法研究

由于特征評價函數(shù)與遺傳算法的收斂速度和最優(yōu)解息息相關(guān)，所以提出以互信息作為算法的特征評價函數(shù).而標(biāo)準(zhǔn)互信息只考慮了單個特征的影響，沒有考慮兩兩特征和多個特征間的相互影響，因此，本文引入改進(jìn)的互信息公式結(jié)合遺傳算法來進(jìn)行特征選擇方法:將遺傳算法里的特征評價函數(shù)用改進(jìn)互信息公式進(jìn)行替換. 遺傳算法是一種基于封裝式的特征選擇算法，互信息是一種基于過濾式的特征選擇算法，故GA-MI 算法是對封裝式和過濾式這2種特征選擇算法的結(jié)合.具體方法如下:

(1)將解空間映射到編碼空間，每個編碼對應(yīng)問題的一個解.本文采用經(jīng)典的二進(jìn)制編碼.

(2)設(shè)P 為種群的大小，L 為個體的長度;N 表示初始種群的大小，為用戶自定義的參數(shù)，且1≤N≤P.分別對初始種群中的個體隨機(jī)附上二進(jìn)制值，以這N 組串結(jié)構(gòu)作為初始點(diǎn)開始迭代.

(3)計算種群的適應(yīng)度. 本文選取改進(jìn)的互信息公式［6］作為適應(yīng)度函數(shù):

其中，n 表示特征總數(shù)，Xn表示n個特征里面任一特征值，Xk表示第k 列的特征值，Y 表示標(biāo)簽列，參數(shù)β 和γ 在［0，1］里面取值. 上式第1 項(xiàng)為所有特征與標(biāo)簽的互信息的和，第2 項(xiàng)為所有不相同的2個特征的互信息的和，第3 項(xiàng)為所有不相同的2個特征與標(biāo)簽項(xiàng)的互信息的和，其中第2 項(xiàng)、第3 項(xiàng)分別乘以參數(shù)β、γ，以此來削弱它們在互信息公式中的影響力.當(dāng)β 和γ 均為0 時，式(8)為最原始的互信息公式.

由于式(8)為該種群所有特征的互信息，所以單個特征的互信息應(yīng)除以所選特征變量的個數(shù)，即:

(4)判斷是否達(dá)到迭代次數(shù)，若是，則輸出當(dāng)前的最優(yōu)特征子集，否則執(zhí)行以下步驟.

(5)執(zhí)行選擇操作. 本文的選擇操作選用比例選擇算子，即個體被選中并遺傳到下一代種群中的概率與該個體的適應(yīng)度大小成正比.

(6)執(zhí)行交叉操作. 本實(shí)驗(yàn)的交叉操作采用單點(diǎn)交叉算子.

式中：Kj(Nx)表示待評對象Nx關(guān)于等級j的綜合關(guān)聯(lián)度；kj(xj)表示待評對象Nx關(guān)于等級j的單指標(biāo)關(guān)聯(lián)度j=(1,2,…,m)；ai表示各指標(biāo)的權(quán)重。若

(7)執(zhí)行變異操作. 本實(shí)驗(yàn)的變異操作采用單點(diǎn)變異算子.

(8)返回4).

3 實(shí)驗(yàn)方法

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

本次實(shí)驗(yàn)數(shù)據(jù)選自UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫和人工數(shù)據(jù)集.從UCI 中選取了IRIS 數(shù)據(jù)集和Wine 數(shù)據(jù)集;設(shè)置了2 組人工數(shù)據(jù)集，選擇數(shù)據(jù)集和異或數(shù)據(jù)集.其中，選擇數(shù)據(jù)集(Select)為512* 10 維的數(shù)據(jù):前9 列為特征項(xiàng)，其中第1、2 列的4 種排列組合的值，順序選擇第6、7、8 或9 列，所選的那一列對應(yīng)的值即為第10 列標(biāo)簽項(xiàng)的值. 異或數(shù)據(jù)集(XOR)為32* 6 維的數(shù)據(jù):前5 列為特征項(xiàng)，第6 列標(biāo)簽項(xiàng)的值為第1 列和第5 列異或的結(jié)果.在每次實(shí)驗(yàn)時，我們都會將數(shù)據(jù)集順序打亂. 選擇其中2/3 的數(shù)據(jù)為訓(xùn)練數(shù)據(jù)集，1/3 的數(shù)據(jù)為測試數(shù)據(jù)集.表1 為實(shí)驗(yàn)的數(shù)據(jù)集.

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

3.2 實(shí)驗(yàn)方法

為了驗(yàn)證所提出方法的有效性，采用GA-PNN算法和GA-PNN-MI 算法與本文所提出的方法進(jìn)行比較.

GA-PNN 算法是將遺傳算法中的初始種群特征值隨機(jī)選擇改為用PNN 進(jìn)行選擇. 具體實(shí)現(xiàn):首先用PNN 預(yù)測每個特征單獨(dú)使用時的情況，并算出每個基因位的方差，然后選擇方差倒數(shù)值不小于均方差倒數(shù)值的基因位，此基因位的特征即作為遺傳算法初始種群的特征. 選擇、交叉、變異操作同前面的GA-MI 方法，適應(yīng)度函數(shù)為測試集數(shù)據(jù)誤差平方和的倒數(shù).

GA-PNN-MI 算法是在GA-PNN 算法的基礎(chǔ)上，將GA-PNN 中的適應(yīng)度函數(shù)變?yōu)楦倪M(jìn)的互信息公式.

GA-MI 算法與GA-PNN-MI 算法最大的區(qū)別在于后者用PNN 對遺傳算法里的初始種群進(jìn)行選擇，而非隨機(jī)選擇選擇初始種群.

4 結(jié)果與分析

對每種方法各做15 組實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果顯示，遺傳算法中初始種群大小N 取10，互信息公式中參數(shù)β、γ 取值分別為0.5、0.6 時，實(shí)驗(yàn)結(jié)果較為理想.對于表1 中的每一個數(shù)據(jù)集，分別運(yùn)行GA-MI、GAPNN 和GA-PNN-MI 算法，記錄下各算法得到的特征子集.統(tǒng)計每次實(shí)驗(yàn)所得特征子集的個數(shù)，取這15 組數(shù)據(jù)的平均值，即為所選擇特征子集個數(shù). 特征個數(shù)采用向上取整的方法.所選特征為15 組數(shù)據(jù)中出現(xiàn)次數(shù)最多的特征. 特征個數(shù)及所選特征見表2 和表3. 表2 列出了采用3 種不同特征選擇方法得到的特征子集中所包含的特征的個數(shù)，表3 列出了對應(yīng)的特征子集所包含的具體特征的下標(biāo).顯然，采用本文提出的GA-MI 方法選出的特征子集規(guī)模小于或等于其他2 種方法.

表2 3 種特征選擇算法得到的特征子集大小Table 2 The feature subset size in three feature selection algorithm

為了對比PNN 和BP 網(wǎng)絡(luò)的優(yōu)劣及驗(yàn)證所選擇特征的情況，我們將以上3 種方法選出的特征分別應(yīng)用在PNN 和BP 這2 種神經(jīng)網(wǎng)絡(luò)的分類器中，其分類正確率見表4 和表5.

表3 3 種特征選擇算法得到的特征子集Table 3 The feature subset in three feature selection algorithm

表4 PNN 分類器在各特征子集上的分類精度對比Table 4 The comparison of classification accuracy in each PNN classifiers with feature subsets %

表5 BP 分類器在各特征子集上的分類精度對比Table 5 The comparison of classification accuracy in each BP classifier with feature subset %

從表4 和表5 看出，大多數(shù)情況下，采用選擇后的特征子集進(jìn)行分類，分類精度都會有所提高，這充分說明了特征選擇對于提高整體性能的必要性和重要性.對比表2 和表4，盡管用GA-MI 方法選擇的特征個數(shù)比用GA-PNN 或GA-PNN-MI 方法選擇的特征個數(shù)少，但是用于分類時分類精度并未比其他方法有顯著下降，說明GA-MI 算法可以選擇出更為有效的特征變量;更重要的是，對比表4 和表5，不難發(fā)現(xiàn)，在改用BP 網(wǎng)絡(luò)分類器進(jìn)行分類時，GA-PNN和GA-PNN-MI 這2 種方法的分類精度都有所下降，而GA-IM 算法的精度基本保持不變.其他2 種方法分類精度下降的原因是這2 種方法采用PNN 的分類精度作為特征選擇的標(biāo)準(zhǔn)，因此，改用BP 網(wǎng)絡(luò)分類時精度就發(fā)生變化，這一結(jié)果說明GA-IM 方法具有較好的泛化特性. 另一方面，從表4 還可看到，對于數(shù)據(jù)維度較低的數(shù)據(jù)集GA-MI 方法在降維和分類精度方面都比其他2 種方法要好，但是，對于數(shù)據(jù)維度較高的Wine 數(shù)據(jù)集(13 維)，GA-MI 所選的特征子集在分類時的精度低于其他2 種方法，其原因在于，采用GA-MI 方法進(jìn)行特征選擇時，為控制算法運(yùn)行時間，并未達(dá)到最優(yōu)結(jié)果就人為停止算法過程，所以選出的特征子集并非最優(yōu)子集，從而導(dǎo)致其分類精度較差.

5 結(jié)束語

本文提出一種由遺傳算法和改進(jìn)的互信息公式結(jié)合的特征選擇方法. 將遺傳算法里的特征評價函數(shù)換為改進(jìn)的互信息公式來對特征進(jìn)行選擇，結(jié)合了過濾式和封裝式這2 種特征選擇方法的優(yōu)點(diǎn). 實(shí)驗(yàn)結(jié)果表明采用GA-MI 方法不僅選出真正有效的特征顯著從而降低數(shù)據(jù)的維度，而且所選出的特征具有較好的泛化能力，對于不同的分類器具有更好的適應(yīng)性.但是，程序編寫只考慮了方法的實(shí)現(xiàn)，沒有考慮程序的執(zhí)行效率，造成對于高維數(shù)據(jù)程序運(yùn)行需要的時間較長. 在未來的工作中將進(jìn)一步改進(jìn)算法效率，進(jìn)行高維度數(shù)據(jù)的特征選擇實(shí)驗(yàn)，更好地驗(yàn)證該方法的優(yōu)良性能.

［1］Liu H，Yu L. Toward integrating feature selection algorithms for classification and clustering［J］. IEEE Trans on Knowledge and Data Engineering，2005，17(3):491－502.

［2］蔣盛益，王連喜. 基于特征相關(guān)性的特征選擇［J］.計算機(jī)工程與應(yīng)用，2010，46(20):153－156.Jiang S Y，Wang L X. Feature selection based on feature similarity measure［J］. Computer Engineering and Application，2010，46(20):153－156.

［3］Zhang D Q，Chen S C，Zhou Z H. Constraint score:A new filter method for feature selection with pair-wise constraints［J］. Pattern Recognition，2008，41(5):1440－1451.

［4］王小平，曹立明.遺傳算法理論應(yīng)用與軟件實(shí)現(xiàn)［M］.西安:西安交通大學(xué)出版社，2002.

［5］陳明.MATLAB 神經(jīng)網(wǎng)絡(luò)原理與實(shí)例精解［M］.北京:清華大學(xué)出版社，2013.

［6］Brown G. A new perspective for information theoretic feature selection［C］∥International conference on artificial intelligence and statistics.MA，USA:Microtome Publishing，2009:49－56.