涂昌慧，葛 紅 ，胡天亮

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

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

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

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

1 相關概念

1.1 遺傳算法

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

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

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

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

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

1.2 互信息

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

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

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

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

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

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

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

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

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

1.3 BP 神經網絡

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

1.4 概率神經網絡

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

2 GA-MI 算法研究

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

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

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

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

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

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

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

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

(6)執(zhí)行交叉操作. 本實驗的交叉操作采用單點交叉算子.

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

(7)執(zhí)行變異操作. 本實驗的變異操作采用單點變異算子.

(8)返回4).

3 實驗方法

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

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

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

3.2 實驗方法

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

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

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

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

4 結果與分析

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

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

為了對比PNN 和BP 網絡的優(yōu)劣及驗證所選擇特征的情況，我們將以上3 種方法選出的特征分別應用在PNN 和BP 這2 種神經網絡的分類器中，其分類正確率見表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ù)情況下，采用選擇后的特征子集進行分類，分類精度都會有所提高，這充分說明了特征選擇對于提高整體性能的必要性和重要性.對比表2 和表4，盡管用GA-MI 方法選擇的特征個數(shù)比用GA-PNN 或GA-PNN-MI 方法選擇的特征個數(shù)少，但是用于分類時分類精度并未比其他方法有顯著下降，說明GA-MI 算法可以選擇出更為有效的特征變量;更重要的是，對比表4 和表5，不難發(fā)現(xiàn)，在改用BP 網絡分類器進行分類時，GA-PNN和GA-PNN-MI 這2 種方法的分類精度都有所下降，而GA-IM 算法的精度基本保持不變.其他2 種方法分類精度下降的原因是這2 種方法采用PNN 的分類精度作為特征選擇的標準，因此，改用BP 網絡分類時精度就發(fā)生變化，這一結果說明GA-IM 方法具有較好的泛化特性. 另一方面，從表4 還可看到，對于數(shù)據(jù)維度較低的數(shù)據(jù)集GA-MI 方法在降維和分類精度方面都比其他2 種方法要好，但是，對于數(shù)據(jù)維度較高的Wine 數(shù)據(jù)集(13 維)，GA-MI 所選的特征子集在分類時的精度低于其他2 種方法，其原因在于，采用GA-MI 方法進行特征選擇時，為控制算法運行時間，并未達到最優(yōu)結果就人為停止算法過程，所以選出的特征子集并非最優(yōu)子集，從而導致其分類精度較差.

5 結束語

本文提出一種由遺傳算法和改進的互信息公式結合的特征選擇方法. 將遺傳算法里的特征評價函數(shù)換為改進的互信息公式來對特征進行選擇，結合了過濾式和封裝式這2 種特征選擇方法的優(yōu)點. 實驗結果表明采用GA-MI 方法不僅選出真正有效的特征顯著從而降低數(shù)據(jù)的維度，而且所選出的特征具有較好的泛化能力，對于不同的分類器具有更好的適應性.但是，程序編寫只考慮了方法的實現(xiàn)，沒有考慮程序的執(zhí)行效率，造成對于高維數(shù)據(jù)程序運行需要的時間較長. 在未來的工作中將進一步改進算法效率，進行高維度數(shù)據(jù)的特征選擇實驗，更好地驗證該方法的優(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］蔣盛益，王連喜. 基于特征相關性的特征選擇［J］.計算機工程與應用，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］王小平，曹立明.遺傳算法理論應用與軟件實現(xiàn)［M］.西安:西安交通大學出版社，2002.

［5］陳明.MATLAB 神經網絡原理與實例精解［M］.北京:清華大學出版社，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.