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

姚樹春 劉 正,2 張 強(qiáng)

1(蘇州工業(yè)園區(qū)服務(wù)外包職業(yè)學(xué)院信息工程學(xué)院 江蘇 蘇州 215123)2(蘇州大學(xué)電子信息學(xué)院 江蘇 蘇州 215006)3(蘇州邁科網(wǎng)絡(luò)安全技術(shù)股份有限公司 江蘇 蘇州 215123)

0 引 言

特征選擇是許多實(shí)際應(yīng)用問題的預(yù)處理步驟，能夠有效地降低數(shù)據(jù)的維度與計(jì)算復(fù)雜度。在微陣列分析、文本分類[1]、人臉識(shí)別[2]、多標(biāo)簽學(xué)習(xí)和網(wǎng)絡(luò)流量分類[3]等問題中，數(shù)據(jù)集具有維度高、樣本量少和類別數(shù)少的特點(diǎn)。傳統(tǒng)分類方法對(duì)于此類數(shù)據(jù)的性能較差，容易出現(xiàn)過擬合的問題，導(dǎo)致無法完成有效的分類或識(shí)別[4]。特征選擇算法選出判別力強(qiáng)的特征子集，刪除不相關(guān)特征和冗余特征，提高分類器的效果。

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

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

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

1 信息熵與互信息

1.1 信息熵

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

定義1離散隨機(jī)向量X的熵定義為：

(1)

給定一個(gè)離散隨機(jī)向量Y，X對(duì)于Y的條件熵為：

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

(2)

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

根據(jù)定義1可推導(dǎo)出連接規(guī)則：

(3)

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

1.2 差分熵

為了將信息熵應(yīng)用于連續(xù)隨機(jī)向量數(shù)據(jù)，將離散隨機(jī)向量的概率函數(shù)替換為連續(xù)隨機(jī)向量的概率密度函數(shù)，將該情況的熵稱為差分熵。設(shè)fX表示一個(gè)連續(xù)隨機(jī)向量X的概率密度函數(shù)。

定義2連續(xù)隨機(jī)向量X的差分熵定義為：

(4)

給定一個(gè)連續(xù)隨機(jī)向量Y，根據(jù)連接規(guī)則，(X,Y)也是連續(xù)向量，X對(duì)于Y的條件差分熵為：

(5)

1.3 互信息

互信息度量了兩個(gè)隨機(jī)向量之間的線性關(guān)系和非線性關(guān)系。

1.3.1離散數(shù)據(jù)

定義3兩個(gè)離散隨機(jī)向量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)成立的條件是當(dāng)且僅當(dāng)X與Y均為獨(dú)立的隨機(jī)向量。根據(jù)式(3)可獲得：

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

(9)

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

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

(10)

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

H(X|Y)≤H(X)

(11)

式中:X與Y是兩個(gè)隨機(jī)向量。

1.3.2連續(xù)數(shù)據(jù)

定義4X與Y是兩個(gè)絕對(duì)連續(xù)的隨機(jī)向量，那么(X,Y)也是絕對(duì)連續(xù)的隨機(jī)向量，從而可得：

MI(X,Y)=

連續(xù)隨機(jī)向量的MI屬性對(duì)于離散數(shù)據(jù)也成立。

1.3.3連續(xù)隨機(jī)向量和離散隨機(jī)向量的互信息

定義5連續(xù)隨機(jī)向量X和離散隨機(jī)向量Y之間的MI定義為：

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

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

(12)

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

(13)

因?yàn)镠(X|Y)為非負(fù)值，所以可基于式(13)計(jì)算MI(X,Y)的上界。

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

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

1.4.1條件互信息

定義6兩個(gè)隨機(jī)向量X與Y對(duì)于隨機(jī)向量Z的條件MI定義為：

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

(14)

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

MI(X,Y|Z)=

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

(15)

參考定義6和定義3可獲得以下關(guān)系：

(16)

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

MI(X,Y|Z)≥0

(17)

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

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

(18)

1.4.2三元互信息TMI

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

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

根據(jù)MI和TMI的定義，可獲得以下關(guān)系：

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

(19)

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

2.1 特征選擇的目標(biāo)函數(shù)

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

(20)

式中:Xj為F的一個(gè)特征;Xi使特征與類的相關(guān)性最大。

2.1.1目標(biāo)函數(shù)：最大化互信息

因?yàn)镸I(С,S∪{Xi})=MI(С,S)+MI(С,Xi|S)，所以候選特征Xi的評(píng)價(jià)方法定義為：

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)

特征選擇算法通過優(yōu)化技術(shù)逼近該目標(biāo)函數(shù)。因?yàn)轫?xiàng)MI(С,S)不依賴Xi，所以可將逼近關(guān)系轉(zhuǎn)化為簡(jiǎn)化的目標(biāo)函數(shù)形式：

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

(22)

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

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

(23)

2.1.2目標(biāo)函數(shù)的邊界條件

根據(jù)式(6)和式(23)可總結(jié)出第二個(gè)目標(biāo)函數(shù)：

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

(24)

根據(jù)互信息的分析可獲得目標(biāo)函數(shù)的邊界條件：

定理1給定候選特征Xi，Xi應(yīng)滿足以下關(guān)系：

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

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

證明根據(jù)式(21)與式(23)，OF(Xi)=H(С)-H(С|Xi,S)=H(С)-H(С|S)+MI(С,Xi|S)，因?yàn)镸I(С,Xi|S)≥0，所以O(shè)F(Xi)≥H(С)-H(С|S)，因此定理1(1)得以證明。觀察式(14)與式(22)，可推導(dǎo)出OF′(Xi)=MI(С,Xi|S)≥0，因此定理1(2)得以證明。

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

定義8給定一個(gè)選擇的特征子集S，類別設(shè)為Χ，候選特征為Xi。如果MI(С,Xi|S)=0∧H(Xi|S)>0，那么Xi為不相關(guān)特征。如果H(Xi|S)=0，那么Xi為冗余特征。如果H(Xi|S)=0，那么MI(С,Xi|S)>0，Xi為相關(guān)特征。如果H(С|Xi，S)=0∧H(С|S)>0，那么Xi為(С,S)的完全相關(guān)特征。

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

定理2如果一個(gè)特征是關(guān)于S的冗余特征，那么該特征也是關(guān)于S′的冗余特征，S?S′。

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

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

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

證明參考式(21)與式(22)，如果Xi是關(guān)于(С,S)的完全相關(guān)特征，那么H(С|Xi,S)=0，定理3(1)得以證明。假設(shè)Xi是關(guān)于(С,S)的不相關(guān)特征，因此MI(С,Xi|S)=0，根據(jù)OF′(Xi)=MI(C,Xi|S)，可得OF′(Xi)=0。根據(jù)式(22)和式(14)，可得OF(Xi)=H(С)-H(С|S)+MI(С,Xi|S)，可推理出OF(Xi)=H(С)-H(С|S)，定理3(2)得以證明。定理3(3)、定理3(4)與定理3(2)的證明方式相似。

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

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

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

圖1 特征選擇過程的實(shí)例

3.1 HGA算法

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

圖2 高維小樣本數(shù)據(jù)特征選擇的流程

3.2 預(yù)處理步驟

(1) 刪除冗余特征。在基因表達(dá)譜數(shù)據(jù)集中存在大量缺失表達(dá)譜數(shù)據(jù)的基因，這些基因?qū)τ诜诸惼鳑]有任何貢獻(xiàn)，應(yīng)當(dāng)在預(yù)處理步驟將此類數(shù)據(jù)刪除。

(2) 基于T檢驗(yàn)的特征預(yù)處理?；虮磉_(dá)譜數(shù)據(jù)中存在大量的不相關(guān)或者冗余的基因。T檢驗(yàn)是一種高效的過濾式特征選擇方法，處理步驟為：

Step1樣本分為兩個(gè)類：正常類與癌癥類。

Step2計(jì)算每個(gè)特征的p-值。

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

Step4選出最優(yōu)的特征子集。

3.3 基于HGA的特征選擇方法

HGA由MGA和SGA組成，MGA的輸入為基因表達(dá)譜數(shù)據(jù)，輸出結(jié)果為最優(yōu)的基因子集，SGA的輸入為DNA甲基化數(shù)據(jù)，輸出結(jié)果為最優(yōu)的甲基化位點(diǎn)子集。MGA的每次迭代中運(yùn)行一次SGA，產(chǎn)生甲基化位點(diǎn)子集，采用位點(diǎn)子集引導(dǎo)MGA的搜索過程。

本文摒棄了常用的隨機(jī)初始化策略，采用最優(yōu)甲基化位點(diǎn)的基因組作為OGA-SVM的初始化種群。因此HGA的最終解結(jié)合了基因表達(dá)譜數(shù)據(jù)與DNA甲基化位點(diǎn)數(shù)據(jù)。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)；

//計(jì)算SGA的適應(yīng)度

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()；

//選擇最優(yōu)值

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的染色體結(jié)構(gòu)。設(shè)染色體CH由n個(gè)特征組成，表示為CH=(x1,x2, …,xn)。每個(gè)特征xi為一個(gè)整型值，表示該特征在特征集S中的索引。圖4是遺傳算法的染色體結(jié)構(gòu)示意圖。

3312574 345……127

圖4 遺傳算法的染色體結(jié)構(gòu)示意圖

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

計(jì)算MGA當(dāng)前迭代的每個(gè)染色體適應(yīng)度值mfi，將互信息做為適應(yīng)度函數(shù)，計(jì)算每個(gè)染色體的互信息mfi。

(3) 檢查結(jié)束條件。MGA設(shè)立了兩個(gè)結(jié)束條件：① 適應(yīng)度達(dá)到預(yù)設(shè)的閾值；② 達(dá)到預(yù)設(shè)的最大迭代次數(shù)。

(4) 遺傳算子。① 精英機(jī)制。保留當(dāng)前迭代的最優(yōu)染色體，作為下一代種群的基礎(chǔ)。② 單點(diǎn)交叉算子。通過輪盤賭策略選擇交叉算子的染色體子集，設(shè)染色體子集長(zhǎng)度為lc，設(shè)當(dāng)前迭代的適應(yīng)度之和為fsum，交叉算子選擇染色體子集的步驟為：

Step1產(chǎn)生[0,fsum]區(qū)間的隨機(jī)數(shù)r；

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

Step3重復(fù)Step 1與Step 2直至選出lc個(gè)染色體。

對(duì)隨機(jī)選擇的兩個(gè)父染色體應(yīng)用交叉算子處理，創(chuàng)建兩個(gè)新染色體。采用單點(diǎn)交叉算子，圖5是單點(diǎn)交叉算子的示意圖。

圖5 單點(diǎn)交叉算子的示意圖

③ 變異算子。隨機(jī)選擇長(zhǎng)度lm的染色體，基于變異率Pm對(duì)染色體應(yīng)用單點(diǎn)隨機(jī)變異算子處理。

3.5 SGA的算法流程

(1) 適應(yīng)度評(píng)價(jià)。SGA是封裝式特征選擇方案，計(jì)算SGA當(dāng)前迭代中每個(gè)染色體的適應(yīng)度，記為sfi。將SVM作為適應(yīng)度函數(shù)，采用5折交叉驗(yàn)證方案基于訓(xùn)練數(shù)據(jù)集來訓(xùn)練SVM，然后對(duì)測(cè)試數(shù)據(jù)集進(jìn)行分類處理，迭代地選出最優(yōu)的甲基化位點(diǎn)。

(2) 遺傳算子。SGA算法的遺傳算子與MGA算法的遺傳算子相同。應(yīng)用SGA選擇當(dāng)前的最優(yōu)染色體，應(yīng)用SGA搜索當(dāng)前的最優(yōu)甲基化位點(diǎn)子集，搜索對(duì)應(yīng)的微陣列來組成k個(gè)SGA染色體。

(3) 檢查結(jié)束條件。SGA設(shè)立了兩個(gè)結(jié)束條件：① 適應(yīng)度達(dá)到預(yù)設(shè)的閾值；② 達(dá)到預(yù)設(shè)的最大迭代次數(shù)。

3.6 增量特征選擇程序

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

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集與參數(shù)設(shè)置

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

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

算法的參數(shù)設(shè)置如表2所示。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

續(xù)表2

4.2 實(shí)驗(yàn)設(shè)計(jì)與性能評(píng)價(jià)

4.2.1實(shí)驗(yàn)設(shè)計(jì)

(1) 第一組實(shí)驗(yàn)。本文HGA算法是兩個(gè)GA算法的混合算法，將HGA與單一的GA算法做比較，評(píng)估HGA算法對(duì)于基因表達(dá)譜數(shù)據(jù)集的效果。采用GA_SVM[16]與GA_NNW[17]兩個(gè)單一GA的封裝式特征選擇算法作為對(duì)比算法，GA_SVM是將GA作為優(yōu)化算法以及將SVM作為性能評(píng)價(jià)的封裝式特征選擇算法，GA_NNW是將GA作為優(yōu)化算法以及將人工神經(jīng)網(wǎng)絡(luò)作為性能評(píng)價(jià)的封裝式特征選擇算法。將TCGA基因表達(dá)譜數(shù)據(jù)集作為第一組實(shí)驗(yàn)的數(shù)據(jù)集。

(2) 第二組實(shí)驗(yàn)。將HGA算法與單一的GA算法GA_SVM、GA_NNW做比較，評(píng)估混合GA算法對(duì)于DNA位點(diǎn)數(shù)據(jù)集的效果。將全部的結(jié)腸癌DNA位點(diǎn)數(shù)據(jù)集作為第二組實(shí)驗(yàn)的數(shù)據(jù)集。

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

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

表3 肺癌數(shù)據(jù)集的基本屬性

4.2.2性能評(píng)價(jià)方法

采用SVM和5折交叉驗(yàn)證評(píng)估分類的準(zhǔn)確率，分類準(zhǔn)確率的計(jì)算方法為：

(25)

式中:TP、TN、FP、FN分別為真正、真負(fù)、假正、假負(fù)的樣本分類結(jié)果。

4.3 特征子集評(píng)價(jià)

4.3.1第一組實(shí)驗(yàn)的結(jié)果與分析

圖6是3個(gè)算法對(duì)于基因表達(dá)譜數(shù)據(jù)的平均分類結(jié)果。比較混合GA與單一GA的分類結(jié)果可看出,對(duì)于不同數(shù)量的基因，三個(gè)GA算法的分類準(zhǔn)確率均高于0.9，但混合GA均優(yōu)于單一的GA?；驍?shù)為3時(shí)，GA_SVM的性能略高于GA_NNW，而基因數(shù)為4時(shí)，GA_SVM的性能則略低于GA_NNW，所以單一的GA算法表現(xiàn)得不夠穩(wěn)定，因此本文設(shè)計(jì)了HGA算法以提高特征選擇的穩(wěn)定性與魯棒性。

圖6 混合GA與單一GA的平均分類結(jié)果

4.3.2第二組實(shí)驗(yàn)的結(jié)果與分析

圖7是3個(gè)算法對(duì)于甲基化位點(diǎn)數(shù)據(jù)的平均分類結(jié)果。比較混合GA與單一GA的分類結(jié)果可看出,對(duì)于不同數(shù)量的基因，三個(gè)GA算法的分類準(zhǔn)確率較為接近，但混合GA均優(yōu)于單一的GA。位點(diǎn)數(shù)較少時(shí)，兩個(gè)單一GA算法的分類準(zhǔn)確率較低，HGA的準(zhǔn)確率則依然高于0.9。本文的HGA算法有效地提高了特征選擇的穩(wěn)定性與魯棒性。

圖7 混合GA與單一GA的平均分類結(jié)果

4.3.3第三組實(shí)驗(yàn)的結(jié)果與分析

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

圖8 三個(gè)特征選擇算法的分類準(zhǔn)確率結(jié)果

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

圖9 三個(gè)特征選擇算法的平均處理時(shí)間

5 結(jié) 語

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

本文采用的混合遺傳算法在特征提取過程中取得較好的穩(wěn)定性和尋優(yōu)質(zhì)量，但是計(jì)算時(shí)間較長(zhǎng)，可通過并行計(jì)算實(shí)現(xiàn)混合遺傳算法來提高計(jì)算效率。本文算法重點(diǎn)在基因微陣列數(shù)據(jù)集做了實(shí)驗(yàn)和驗(yàn)證，未來將評(píng)估本文算法對(duì)于其他類型高維小樣本數(shù)據(jù)集的性能。