基于混合遺傳算法與互信息分析的高維小樣本特征選擇

2020-01-14 06:34:32姚樹春

計算機應用與軟件 2020年1期

關鍵詞：特征

姚樹春劉正,2 張強

1(蘇州工業園區服務外包職業學院信息工程學院江蘇蘇州 215123)2(蘇州大學電子信息學院江蘇蘇州 215006)3(蘇州邁科網絡安全技術股份有限公司江蘇蘇州 215123)

0 引言

特征選擇是許多實際應用問題的預處理步驟，能夠有效地降低數據的維度與計算復雜度。在微陣列分析、文本分類[1]、人臉識別[2]、多標簽學習和網絡流量分類[3]等問題中，數據集具有維度高、樣本量少和類別數少的特點。傳統分類方法對于此類數據的性能較差，容易出現過擬合的問題，導致無法完成有效的分類或識別[4]。特征選擇算法選出判別力強的特征子集，刪除不相關特征和冗余特征，提高分類器的效果。

特征選擇是高維小樣本數據分析的關鍵步驟，現有的特征選擇算法主要可分為4種類型，分別為：過濾式方法、封裝式方法、嵌入式方法和集成式方法[5]。不同類型的特征選擇方法均具有不同的優點與缺點，例如：過濾式方法具有時間效率高、可擴展性好和可解釋性強的優點，但也存在分類準確率不足、特征冗余度高的缺點[6]。為了解決高維小樣本數據特征選擇方法的不足之處，許多專家提出了新的解決方案。文獻[7]針對Relief算法特征冗余度高的問題，通過隨機森林算法選出模型準確率高的特征子集，再通過域粗糙集對連續的特征進行尋優，該算法有效地降低了特征子集的冗余度，但是其分類準確率依然不高。文獻[8]以高維小樣本的安全數據分類作為研究目標，利用最小二乘支持向量機易于求解的特點構造分類器，以分類的準確率作為文化基因算法的適應度函數，該算法對于不同的模式數量表現出不穩定的分類性能。互信息(Mutual Information, MI)是信息領域的概念，度量了某個隨機變量包含另一個隨機變量的信息量，表示兩個隨機變量間的相關性。文獻[9]利用信息熵度量特征間的獨立程度和冗余程度，充分考慮了特征子集中不同特征間的多變量關系，研究表明互信息能夠有效地降低特征之間的冗余度，提高特征選擇的效率。文獻[10]提出一種基于核互信息的彈性特征選擇方法，研究表明互信息在刪除不相關特征與冗余特征上的顯著效果，但該文獻同時認為互信息對于不同數據分布的穩定性較差。將互信息應用于高維小樣本數據特征的選擇問題已成為當前該領域的一個研究方向，其中大多數方案直接將特征與類別的互信息作為特征的評價指標[11-12]，通過不同的人工智能算法做尋優處理[13]，然后選出排名較高的特征子集。

本文對互信息和特征選擇問題進行了深入分析，給出了特征選擇問題的互信息目標函數和約束條件，并且基于互信息將特征分為4個子類型，分別為：不相關特征、冗余特征、相關特征和完全相關特征。在迭代選擇特征子集的過程中，刪除冗余特征，選擇完全相關特征，保留不相關特征和相關特征做進一步篩選。及時選出完全相關特征、刪除冗余特征不僅有助于減少這兩種特征對后續特征處理的干擾，并且也能夠提高特征選擇處理的計算效率。

高維小樣本數據大多存在多個維度的屬性，例如：基因微陣列數據包括基因表達譜數據和甲基化位點數據，網絡流量數據包括網絡日志數據和網絡監控的實時數據。為了充分利用數據集不同角度的屬性數據，提出了混合的遺傳算法，確定主種群和次種群，在每次迭代中利用次種群的結果引導主種群的演化，從而緩解小樣本數據帶來的過擬合問題。

1 信息熵與互信息

1.1 信息熵

設P(A)表示A的概率。

定義1離散隨機向量X的熵定義為：

(1)

給定一個離散隨機向量Y，X對于Y的條件熵為：

P(Y=y)lnP(X=x|Y=y)

(2)

X的熵依賴向量的概率，并不依賴向量的具體值。式(1)中各個項均為非負項，所以信息熵也是非負。

根據定義1可推導出連接規則：

(3)

式(3)中的隨機向量序列(X1,X2,…,Xn)和(Xi-1,Xi-2,…,X1)為集成多個元素的隨機向量。

1.2 差分熵

為了將信息熵應用于連續隨機向量數據，將離散隨機向量的概率函數替換為連續隨機向量的概率密度函數，將該情況的熵稱為差分熵。設fX表示一個連續隨機向量X的概率密度函數。

定義2連續隨機向量X的差分熵定義為：

(4)

給定一個連續隨機向量Y，根據連接規則，(X,Y)也是連續向量，X對于Y的條件差分熵為：

(5)

1.3 互信息

互信息度量了兩個隨機向量之間的線性關系和非線性關系。

1.3.1離散數據

定義3兩個離散隨機向量X與Y之間的MI定義為：

MI(X,Y)=

MI具有如下屬性：

MI(X,Y)=H(X)-H(X|Y)

(6)

MI(X,Y)≥0

(7)

MI(X,X)=H(X)

(8)

式(7)成立的條件是當且僅當X與Y均為獨立的隨機向量。根據式(3)可獲得：

MI(X,Y)=H(X)+H(Y)-H(X,Y)

(9)

根據式(6)可獲得另一個重要的屬性：

MI(X,Y)≤min(H(X),H(Y))

(10)

觀察式(6)和式(7)，可知對于任意的隨機向量X和Y，有：

H(X|Y)≤H(X)

(11)

式中:X與Y是兩個隨機向量。

1.3.2連續數據

定義4X與Y是兩個絕對連續的隨機向量，那么(X,Y)也是絕對連續的隨機向量，從而可得：

MI(X,Y)=

連續隨機向量的MI屬性對于離散數據也成立。

1.3.3連續隨機向量和離散隨機向量的互信息

定義5連續隨機向量X和離散隨機向量Y之間的MI定義為：

對于定義5的情況，離散數據的大多數屬性依然成立，式(6)的屬性可改寫為：

MI(X,Y)=h(X)-h(X|Y)

(12)

MI(X,Y)=H(Y)-H(Y|X)

(13)

因為H(X|Y)為非負值，所以可基于式(13)計算MI(X,Y)的上界。

1.4 三元互信息與條件互信息

討論三個隨機向量之間的三元互信息(Triple Mutual Information,TMI)，高維數據特征選擇問題的目標函數與TMI具有直接的關系。

1.4.1條件互信息

定義6兩個隨機向量X與Y對于隨機向量Z的條件MI定義為：

MI(X,Y|Z)=H(X|Z)-H(X|Y,Z)

(14)

基于式(14)與連接規則將條件熵定義為：

MI(X,Y|Z)=

H(X|Z)+H(Y|Z)-H(X,Y|Z)

(15)

參考定義6和定義3可獲得以下關系：

(16)

考慮式(7)和式(16)，可獲得以下關系：

MI(X,Y|Z)≥0

(17)

由式(14)和式(17)可得出以下的關系：

H(X|Y,Z)≤H(X|Z)

(18)

1.4.2三元互信息TMI

在高維數據的特征選擇問題中，三元互信息具有重要的意義。

定義7三個隨機向量X、Y和Z之間的三元互信息TMI定義為：

根據MI和TMI的定義，可獲得以下關系：

TMI(X,Y,Z)=MI(X,Y)-MI(X,Y|Z)

(19)

2 基于互信息的特征選擇問題

2.1 特征選擇的目標函數

設С為類別，S(F)為某次迭代所選擇的特征子集。所有的輸入特征集均具有屬性：S∪F，S∩F=?。特征選擇的目標是從一個給定特征集中選出一個候選特征子集Xj∈F，表示為：

(20)

式中:Xj為F的一個特征;Xi使特征與類的相關性最大。

2.1.1目標函數：最大化互信息

因為MI(С,S∪{Xi})=MI(С,S)+MI(С,Xi|S)，所以候選特征Xi的評價方法定義為：

OF(Xi)=MI(С,S)+MI(С,Xi|S)=

MI(С,S)+MI(С,Xi)-TMI(С,Xi,S)=

MI(С,S)+MI(С,Xi)-MI(Xi,S)+MI(Xi,S|С)

(21)

特征選擇算法通過優化技術逼近該目標函數。因為項MI(С,S)不依賴Xi，所以可將逼近關系轉化為簡化的目標函數形式：

OF′(Xi)=MI(C,Xi)-MI(Xi,S)+MI(Xi,S|C)

(22)

OF與OF′兩個目標函數可表示為熵的形式，基于式(6)與式(14)可獲得第一個目標函數：

OF(Xi)=H(С)-H(С|Xi,S)

(23)

2.1.2目標函數的邊界條件

根據式(6)和式(23)可總結出第二個目標函數：

OF′(Xi)=H(С|S)-H(С|Xi,S)

(24)

根據互信息的分析可獲得目標函數的邊界條件：

定理1給定候選特征Xi，Xi應滿足以下關系：

(1)H(С)-H(С|S)≤OF(Xi)≤H(С)；

(2) 0≤OF′(Xi)≤H(С|S)。

2.2 基于互信息的特征類型劃分

定義8將不相關特征分為兩個子類型：不相關特征和冗余特征。相關特征也分為兩個子類型：完全相關特征和相關特征。本文將不相關特征和冗余特征分開的原因在于特征選擇程序中這兩種特征表現出不同的變化趨勢：冗余特征始終為冗余特征，而不相關特征則可能被選為相關特征。

定理2如果一個特征是關于S的冗余特征，那么該特征也是關于S′的冗余特征，S?S′。

證明假設Xi是關于S的冗余特征，可得H(Xi|S)=0，S?S′。根據式(18)可得H(Xi|S′)=0，所以Xi也是關于S′的冗余特征。

定理2說明在特征選擇程序的迭代中發現冗余特征，即可直接從候選特征集中刪除該特征，避免后續處理帶來的計算負擔。根據上述的特征分類，特征選擇程序在迭代中選擇完全相關特征，刪除冗余特征，保留不相關特征與相關特征。

定理3(1) 如果Xi是一個關于(С,S)的完全相關特征，那么OF(Xi)=H(С)，OF′(Xi)=H(С|S)，即目標函數的最大可能值。(2)如果Xi是一個關于(С,S)的不相關特征，那么OF(Xi)=H(С)-H(С|S)，OF′(Xi)=0，即目標函數的最小可能值。(3)如果Xi是一個關于S的冗余特征，那么OF(Xi)=H(С)-H(С|S)，OF′(Xi)=0，即目標函數的最小可能值。(4)如果Xi是一個關于(С,S)的相關特征(非完全相關)，那么H(С)-H(С|S)

綜上所述，完全相關特征實現了目標函數的最大值，相關特征的目標值在最小值與最大值之間，根據該屬性在特征選擇程序中將特征排序。通過評價H(Xi|S)來判斷不相關特征和冗余特征。

3 基于混合GA算法的高維特征選擇

基因微陣列數據是一種典型的高維小樣本數據集，借助基因微陣列特征選擇問題描述本文算法的細節。首先，使用T檢驗技術對數據集做預處理，然后通過HGA選擇最優的特征子集。HGA包括主GA(Main Genetic Algorithm, MGA)與次GA(Secondary Genetic Algorithm, SGA)兩個GA算法，MGA處理微陣列基因表達譜數據集，SGA處理微陣列甲基化位點數據集。圖1所示為特征選擇過程的實例，首先應用T檢驗技術初選特征子集，然后采用迭代的HGA逐步選出最優的特征子集。圖中：(1) 表示不相關特征；(2) 表示冗余特征；(3) 表示相關特征；(4) 表示完全相關特征。在迭代選擇特征子集的過程中，刪除冗余特征，選擇完全相關特征，保留不相關特征和相關特征做進一步的篩選。

圖1 特征選擇過程的實例

3.1 HGA算法

HGA算法的流程如圖2所示。采用T檢驗對基因表達譜數據與DNA甲基化數據做預處理，初步篩選特征子集，將高排名的基因表達譜與甲基化位點選為特征子集。將初選的基因子集輸入MGA模型，甲基化位點集輸入SGA模型。分析基因表達譜與甲基化位點之間的關系，可計算出解的數量N。根據基因的被選頻率將N個解按降序排列。

圖2 高維小樣本數據特征選擇的流程

3.2 預處理步驟

(1) 刪除冗余特征。在基因表達譜數據集中存在大量缺失表達譜數據的基因，這些基因對于分類器沒有任何貢獻，應當在預處理步驟將此類數據刪除。

(2) 基于T檢驗的特征預處理。基因表達譜數據中存在大量的不相關或者冗余的基因。T檢驗是一種高效的過濾式特征選擇方法，處理步驟為：

Step1樣本分為兩個類：正常類與癌癥類。

Step2計算每個特征的p-值。

Step3按照p-值將特征降序排列。

Step4選出最優的特征子集。

3.3 基于HGA的特征選擇方法

HGA由MGA和SGA組成，MGA的輸入為基因表達譜數據，輸出結果為最優的基因子集，SGA的輸入為DNA甲基化數據，輸出結果為最優的甲基化位點子集。MGA的每次迭代中運行一次SGA，產生甲基化位點子集，采用位點子集引導MGA的搜索過程。

本文摒棄了常用的隨機初始化策略，采用最優甲基化位點的基因組作為OGA-SVM的初始化種群。因此HGA的最終解結合了基因表達譜數據與DNA甲基化位點數據。HGA算法的流程如圖3所示，其偽代碼如算法1所示。

圖3 HGA算法的流程圖

算法1HGA算法

輸入：特征集S

輸出：選擇的特征子集MCH

1.MCH=random_init();

2. foreach i from 0 toM_maxiterdo

3.M_p=init_pop_SGA(MCH)；

//初始化SGA種群

4. foreachjfrom 0 toM_maxiterdo

5.S_value=fit(S_p)；

//計算SGA的適應度

6. if (S_value≥expect_value)

7. break；

8. else

9.in_E=elitism()；

//精英算子

10.srw=RouleteWheel()；

//輪盤賭策略

11.in_C=Crossover(srw)；

//交叉算子

12.in_U=Mutation(srw)；

//變異算子

13.in_p=Replace_pop(in_E,in_C,in_U)；

//種群交換

14. endif

15. endfor

16.M_p=initMpop(S_p,N)；

//初始化主種群

17.S_value=fit(M_p)；

18. if(M_value≥expect_value)

19.M_CH=select_optimal()；

//選擇最優值

20. break；

21. else

22.S_E=elitism()；

//精英算子

23. srw=RouleteWheel()；

//輪盤賭策略

24.M_C=Crossover(srw)；

//交叉算子

25.M_U=Mutation(srw)；

//變異算子

26.M_p=Replace_pop(M_E,M_C,M_U)；

//種群交換

27. endif

28. endfor

3.4 MGA算法的流程

(1) HGA的染色體結構。設染色體CH由n個特征組成，表示為CH=(x1,x2, …,xn)。每個特征xi為一個整型值，表示該特征在特征集S中的索引。圖4是遺傳算法的染色體結構示意圖。

3312574 345……127

圖4 遺傳算法的染色體結構示意圖

(2) HGA的種群初始化。初始化MGA的種群pi，設pi共有Y個染色體，每個染色體有y個甲基化位點。每個染色體表示為一個序列{y1,y2,…,yfc}，fc表示甲基化位點的數量。HGA的第1次迭代隨機初始化MGA的染色體，在后續的每次迭代中，使用MGA優化的染色體初始化MGA的染色體種群。甲基化位點與基因表達譜數據的轉換采用DNA甲基化分析軟件實現，如minfi、IlluminaHumanMethylation和missMethyl等，minfi、IlluminaHumanMethylation和missMethyl均為DNA甲基化分析的專用R包。將每個基因映射為0∶50的甲基化位點。

計算MGA當前迭代的每個染色體適應度值mfi，將互信息做為適應度函數，計算每個染色體的互信息mfi。

(3) 檢查結束條件。MGA設立了兩個結束條件：① 適應度達到預設的閾值；② 達到預設的最大迭代次數。

(4) 遺傳算子。① 精英機制。保留當前迭代的最優染色體，作為下一代種群的基礎。② 單點交叉算子。通過輪盤賭策略選擇交叉算子的染色體子集，設染色體子集長度為lc，設當前迭代的適應度之和為fsum，交叉算子選擇染色體子集的步驟為：

Step1產生[0,fsum]區間的隨機數r；

Step2檢查當前迭代的每個染色體，觀察其適應度是否小于r，如果小于r則選擇該染色體，并返回Step1；否則，檢查下一個染色體。

Step3重復Step 1與Step 2直至選出lc個染色體。

對隨機選擇的兩個父染色體應用交叉算子處理，創建兩個新染色體。采用單點交叉算子，圖5是單點交叉算子的示意圖。

圖5 單點交叉算子的示意圖

③ 變異算子。隨機選擇長度lm的染色體，基于變異率Pm對染色體應用單點隨機變異算子處理。

3.5 SGA的算法流程

(1) 適應度評價。SGA是封裝式特征選擇方案，計算SGA當前迭代中每個染色體的適應度，記為sfi。將SVM作為適應度函數，采用5折交叉驗證方案基于訓練數據集來訓練SVM，然后對測試數據集進行分類處理，迭代地選出最優的甲基化位點。

(2) 遺傳算子。SGA算法的遺傳算子與MGA算法的遺傳算子相同。應用SGA選擇當前的最優染色體，應用SGA搜索當前的最優甲基化位點子集，搜索對應的微陣列來組成k個SGA染色體。

(3) 檢查結束條件。SGA設立了兩個結束條件：① 適應度達到預設的閾值；② 達到預設的最大迭代次數。

3.6 增量特征選擇程序

在每次迭代中按照互信息的計算結果，增量地添加選擇的特征，假設S為選擇的特征子集，在每次迭代中計算互信息目標函數和邊界條件。首先，刪除不滿足邊界條件的特征，刪除冗余特征。然后，將完全相關特征添加至S中，保留不相關特征和相關特征，在下一次迭代中做進一步處理。

4 實驗

4.1 實驗數據集與參數設置

采用結腸癌基因表達譜數據作為實驗數據集(The Cancer Genome Atlas,TCGA)，下載地址為https://tcga-data.nci.nih.gov/tcga/，采用IHM-27k平臺的TCGA DNA甲基化數據集作為實驗數據。采用高通量基因表達數據集(Gene Expression Omnibus，GEO)作為第三方獨立測試數據集。具體實驗數據集如表1所示。

表1 實驗數據集

算法的參數設置如表2所示。

表2 實驗參數設置

續表2

4.2 實驗設計與性能評價

4.2.1實驗設計

(1) 第一組實驗。本文HGA算法是兩個GA算法的混合算法，將HGA與單一的GA算法做比較，評估HGA算法對于基因表達譜數據集的效果。采用GA_SVM[16]與GA_NNW[17]兩個單一GA的封裝式特征選擇算法作為對比算法，GA_SVM是將GA作為優化算法以及將SVM作為性能評價的封裝式特征選擇算法，GA_NNW是將GA作為優化算法以及將人工神經網絡作為性能評價的封裝式特征選擇算法。將TCGA基因表達譜數據集作為第一組實驗的數據集。

(2) 第二組實驗。將HGA算法與單一的GA算法GA_SVM、GA_NNW做比較，評估混合GA算法對于DNA位點數據集的效果。將全部的結腸癌DNA位點數據集作為第二組實驗的數據集。

(3) 第三組實驗。第一組、第二組實驗均為癌癥檢測的二分類問題，為了評估本文算法對于多分類特征的選擇效果，采用多子類數據集測試本文算法對于多分類問題的特征選擇效果。將HGA算法與其他的特征選擇算法橫向比較，評估本算法的性能。采用近期的CBRGB算法[18]和WGEP_CI算法[19]作為對比方案。CBRGB算法是一種基于梯度boosting的肺癌基因特征選擇算法，該算法對于肺癌表現出較高的性能；WGEP_CI算法則是一種基于連接信息的肺癌基因特征選擇算法，該算法采用的連接信息與本文算法的互信息具有相似性，因此選擇該文獻與本算法比較。

每個特征選擇算法的輸入均為T檢驗初步帥選后的特征子集，將TCGA基因表達譜與DNA甲基化數據集作為訓練數據集。將GEO基因表達譜數據集中的肺癌數據集作為測試數據集，肺癌數據集包含了肺腺癌和肺鱗癌兩種子類型。表3所示是GEO數據集中肺癌數據集的基本屬性。

表3 肺癌數據集的基本屬性

4.2.2性能評價方法

采用SVM和5折交叉驗證評估分類的準確率，分類準確率的計算方法為：

(25)

式中:TP、TN、FP、FN分別為真正、真負、假正、假負的樣本分類結果。

4.3 特征子集評價

4.3.1第一組實驗的結果與分析

圖6是3個算法對于基因表達譜數據的平均分類結果。比較混合GA與單一GA的分類結果可看出,對于不同數量的基因，三個GA算法的分類準確率均高于0.9，但混合GA均優于單一的GA。基因數為3時，GA_SVM的性能略高于GA_NNW，而基因數為4時，GA_SVM的性能則略低于GA_NNW，所以單一的GA算法表現得不夠穩定，因此本文設計了HGA算法以提高特征選擇的穩定性與魯棒性。

圖6 混合GA與單一GA的平均分類結果

4.3.2第二組實驗的結果與分析

圖7是3個算法對于甲基化位點數據的平均分類結果。比較混合GA與單一GA的分類結果可看出,對于不同數量的基因，三個GA算法的分類準確率較為接近，但混合GA均優于單一的GA。位點數較少時，兩個單一GA算法的分類準確率較低，HGA的準確率則依然高于0.9。本文的HGA算法有效地提高了特征選擇的穩定性與魯棒性。

圖7 混合GA與單一GA的平均分類結果

4.3.3第三組實驗的結果與分析

(1) 分類的準確率結果。圖8是三個特征選擇算法的比較結果，結果顯示本算法對于不同數量的位點數據均明顯地優于CBRGB算法和WGEP_CI算法。隨著位點數量的升高，CBRGB算法表現出性能衰減的趨勢，其原因在于CBRGB算法所采用的boosting模型對于高維數據的性能弱于低維數據，而WGEP_CI通過連接信息實現了較為穩定的性能，對于位點數量具有魯棒性和穩定性。本算法采用了互信息和詳細的剪枝機制，實現了高效、準確地特征選擇過程，并且利用混合遺傳算法實現了快速、準確的尋優效果。

圖8 三個特征選擇算法的分類準確率結果

(2) 分類的時間效率。圖9是三個特征選擇算法的平均處理時間，三個算法均針對高維小樣本數據做出了針對“維數災難”的解決方案，并且都實現了可接受的時間效率。本文算法在迭代選擇特征子集的過程中，刪除冗余特征，選擇完全相關特征，保留不相關特征和冗余特征做進一步的篩選。及時選出完全相關特征、刪除冗余特征不僅有助于消除這兩種特征對后續特征處理的干擾，并且也能夠提高特征選擇處理的計算效率。

圖9 三個特征選擇算法的平均處理時間

5 結語

本文對互信息和特征選擇問題進行了深入的分析，給出了特征選擇問題的互信息目標函數和約束條件，并且基于互信息將特征分為4個子類型。計算互信息目標函數和邊界條件，刪除不滿足邊界條件的特征和冗余特征，提取出完全相關特征，剩下的特征在下一次迭代中做進一步處理。及時選出完全相關特征、刪除冗余特征不僅有助于消除這兩種特征對后續特征處理的干擾，并且也能夠提高特征選擇處理的計算效率。

本文采用的混合遺傳算法在特征提取過程中取得較好的穩定性和尋優質量，但是計算時間較長，可通過并行計算實現混合遺傳算法來提高計算效率。本文算法重點在基因微陣列數據集做了實驗和驗證，未來將評估本文算法對于其他類型高維小樣本數據集的性能。