基于演化學(xué)習(xí)超網(wǎng)絡(luò)的微陣列數(shù)據(jù)分類

王 進，黃萍麗，孫開偉，蔡 通

(重慶郵電大學(xué)計算智能重慶市重點實驗室，重慶400065)

癌癥治療是人類難以攻克的難題.DNA微陣列技術(shù)的出現(xiàn)為從分子水平研究癌癥的發(fā)病機理和臨床診斷提供了強有力的手段.如何從眾多的微陣列數(shù)據(jù)中挖掘與癌癥相關(guān)的基因以及基因間的相互作用是當(dāng)前研究的熱點問題［1-3］.目前已有多種傳統(tǒng)模式識別技術(shù)用于分析處理DNA微陣列基因表達譜數(shù)據(jù)，如支持向量機［4］、人工神經(jīng)網(wǎng)絡(luò)［5］等.然而傳統(tǒng)模式識別方法的學(xué)習(xí)結(jié)果通常難以解讀，對與癌癥診斷密切相關(guān)的基因高階關(guān)聯(lián)關(guān)系的挖掘也缺乏相應(yīng)工具.

超網(wǎng)絡(luò)(hypernetwork)是受生物分子網(wǎng)絡(luò)啟發(fā)而建立的一種基于超圖(hypergraph)的認知學(xué)習(xí)模型［6］，能夠表示模式特征間的高階關(guān)聯(lián)關(guān)系.超網(wǎng)絡(luò)模型的超邊庫可以存儲訓(xùn)練集的部分信息，同時表示樣本的不同屬性以及屬性和樣本類別之間的關(guān)聯(lián)程度.目前超網(wǎng)絡(luò)已被成功應(yīng)用于解決多種模式識別與認知問題［7-9］.演化學(xué)習(xí)是超網(wǎng)絡(luò)模型的關(guān)鍵環(huán)節(jié)，其目標(biāo)是從訓(xùn)練集中尋找最佳的特征組合，其學(xué)習(xí)過程直接影響超網(wǎng)絡(luò)的分類效果［9］.傳統(tǒng)超網(wǎng)絡(luò)的學(xué)習(xí)方法主要包括2種，一種是梯度下降法［7］:在演化過程中，根據(jù)某種策略對初始化后的超邊權(quán)值進行調(diào)整.該學(xué)習(xí)方法簡單且易操作，其主要局限在于超網(wǎng)絡(luò)對超邊空間的搜索具有局部性.如果在初始化過程中超網(wǎng)絡(luò)沒有提取出有用的特征組合，往往無法取得較好的分類效果.另一種常用的學(xué)習(xí)方法是超邊替代法［8-9］，它采用隨機搜索的方式尋找超邊，雖然可以擴大搜索空間，但隨機搜索效率較低且不穩(wěn)定.

針對傳統(tǒng)超網(wǎng)絡(luò)學(xué)習(xí)算法的局限，文中將遺傳算法與超網(wǎng)絡(luò)模型相結(jié)合，提出一種基于遺傳算法的演化超網(wǎng)絡(luò)模型(genetic algorithm-based evolutionary hypernetworks，GA-HN).采用遺傳算法中的錦標(biāo)賽選擇算子對超邊進行選擇，并通過交叉和變異算子產(chǎn)生新的超邊后代.

1 超網(wǎng)絡(luò)模型

1.1 超網(wǎng)絡(luò)定義

超網(wǎng)絡(luò)是超圖的推廣，在介紹超網(wǎng)絡(luò)模型之前先給出超圖的數(shù)學(xué)定義.超圖G是由超邊組成的無向圖，超邊可以連接任意多個頂點，即G=(V，E)［9］.其中V={v1，v2，…，vn}是包含n個頂點的集合，E={e1，e2，…，em}是包含m條超邊的集合.E中每個元素ei={vi1，vi2，…，vik}(k≥1)是一條連接k個頂點的超邊.

超網(wǎng)絡(luò)模型對超圖的每條超邊賦予權(quán)值和類別標(biāo)識，可以用一個三元組H表示，H=(V，E，W).其中V是特征變量集合，E={e1，e2，…，em}為超網(wǎng)絡(luò)的超邊集合.超邊ei={vi1，vi2，…，vik，yi}由k個特征及類別標(biāo)識yi組成，k稱為超邊的階數(shù)(1≤k≤n)，n表示特征空間V的大小.W={w1，w2，…，wm}是超邊的權(quán)值集合.圖1是一個包含7個特征4條超邊的超網(wǎng)絡(luò)，圖中超邊線條的粗細代表了超邊權(quán)值的大小.

圖1 一個包含7個特征4條超邊的超網(wǎng)絡(luò)

1.2 超網(wǎng)絡(luò)分類器

根據(jù)超網(wǎng)絡(luò)定義，可以把超網(wǎng)絡(luò)看作一個分類器.超網(wǎng)絡(luò)的超邊作為決策規(guī)則，對輸入模式的類型進行判斷.當(dāng)輸入一個待識別樣本X，超網(wǎng)絡(luò)分類器利用所有超邊共同做出決策，輸出該模式所對應(yīng)的類別Y.

根據(jù)輸入訓(xùn)練集D，對其中每個樣本的特征進行多次隨機采樣，建立一個初始化超邊庫，如圖2所示.(超網(wǎng)絡(luò)初始化及演化學(xué)習(xí)過程詳見第2.2節(jié)).D具有以下形式:

式中:Xi為第i個訓(xùn)練樣本;yi為Xi的類別標(biāo)識;N為訓(xùn)練集樣本總數(shù);xij為第i個樣本的第j維特征的表達值;n表示特征的空間大小.超網(wǎng)絡(luò)分類器H(X)可以表示輸入樣本X與輸出類別Y∈{0，1}的聯(lián)合概率P(X，Y).該聯(lián)合概率可以通過對超邊進行點估計近似得到:

圖2 超網(wǎng)絡(luò)分類器的建立過程

式中:|L|為超邊庫的規(guī)模;MY表示與輸入樣本X正確匹配且類別為Y的超邊數(shù);(xi1，xi2，…，xik，Y)為第i條超邊的決策規(guī)則.當(dāng)?shù)趇條超邊和樣本X正確匹配時，(xi1，xi2，…，xik，Y)為 1，否則為 0.

超邊與樣本正確匹配定義如下:超邊包含的頂點特征值與樣本對應(yīng)的特征值相等，且超邊的類別標(biāo)識與樣本的類別相同.例如:對于一個k(k=3)階超網(wǎng)絡(luò)模型，輸入樣本X={x1=1，x2=0，x3=0，x4=1，y=0}.若一條超邊ei的頂點為xi1=1，xi3=0，xi4=1，則稱超邊ei與樣本X匹配.若ei與樣本X匹配且類別相等，則稱超邊ei與樣本X匹配正確，反之匹配錯誤.

在分類應(yīng)用中，超網(wǎng)絡(luò)首先計算輸入X屬于每個類別的條件概率，然后取條件概率最大的類別作為分類結(jié)果:

也就是說，給定一個輸入樣本X，超網(wǎng)絡(luò)將所有超邊與X進行匹配，并將匹配的超邊按類別進行劃分.取匹配數(shù)量最多的一類超邊類別作為該輸入樣本X的分類結(jié)果y*=H(X).若無任何超邊與X匹配或者匹配的兩類超邊數(shù)相等，即樣本被判為任何一類的概率相等，超網(wǎng)絡(luò)將該樣本判為類別1.

超網(wǎng)絡(luò)分類器的分類過程如下:

1)輸入待分類樣本X;

2)根據(jù)以下步驟對輸入樣本X進行分類:

①將X與L中所有超邊進行匹配運算，并將與X匹配的超邊放入集合M中.

②根據(jù)超邊的類別標(biāo)識，對集合M中的超邊進行劃分:類別為0的超邊歸類到M0中，將類別為1的超邊歸類到M1中.

式中:P(X)≈|M|/|L|表示輸入樣本X被超網(wǎng)絡(luò)學(xué)習(xí)記憶的概率，該值通過計算所有與輸入樣本X匹配的超邊數(shù)|M|與超邊總數(shù)的比值得出.由式(4)和式(5)得

在這一過程中，超網(wǎng)絡(luò)利用超邊數(shù)量眾多這一特性，使分類結(jié)果具有較強的魯棒性.

2 基于遺傳算法的超網(wǎng)絡(luò)演化學(xué)習(xí)

2.1 超網(wǎng)絡(luò)的遺傳算法編解碼

演化學(xué)習(xí)以超邊的頂點組合為對象，將特征變量空間進行二進制遺傳算法編碼.初始化后，超邊所包含的特征變量用二進制編碼表示，得到的二進制串作為遺傳算法染色體.在整個演化學(xué)習(xí)過程中，超邊庫中的超邊以染色體編碼串形式存在，超邊頂點對應(yīng)的屬性值被隱藏.最后需根據(jù)訓(xùn)練集對演化后的超邊進行解碼，返回超邊頂點對應(yīng)的屬性值.

當(dāng)特征空間大小為n時，每個特征需用t位二進制數(shù)進行編碼表示，其中2t≥n.具有k(k表示超邊的階數(shù))個頂點的超邊需要長度為kt+1的染色體來表示，其中最后一位用于表示超邊的類別標(biāo)識.遺傳算法在超網(wǎng)絡(luò)中的編解碼過程如圖3所示.

圖3 超邊的遺傳算法編解碼過程

2.2 超網(wǎng)絡(luò)演化學(xué)習(xí)

學(xué)習(xí)算法的性能直接影響超網(wǎng)絡(luò)的學(xué)習(xí)速度和識別率.文中采用并行遺傳算法對超網(wǎng)絡(luò)進行演化，演化流程如圖4所示.

圖4 超網(wǎng)絡(luò)演化學(xué)習(xí)流程圖

演化的具體步驟如下.

1)初始化超邊

初始化超網(wǎng)絡(luò)的子種群.對于訓(xùn)練集D中的每個樣本xi，從n個特征中隨機抽取k個特征，組成一條k階超邊li，初始化超邊的適應(yīng)值fit(li)=0.對每個樣本生成T條超邊，最終構(gòu)成具有|D|×T條超邊的超邊庫L，其中，|D|為訓(xùn)練集樣本總數(shù).將初始化后的超邊庫L進行編碼，并隨機分成M個子種群，每個子種群包含m條超邊(每條超邊對應(yīng)子種群中的一個個體).由于各個子種群都執(zhí)行相似的演化學(xué)習(xí)過程，下面以其中一個子種群為例，說明其演化學(xué)習(xí)過程.

2)超網(wǎng)絡(luò)分類

根據(jù)1.2節(jié)中介紹的分類過程，由每條超邊對訓(xùn)練集進行分類.

3)個體適應(yīng)值的計算

個體適應(yīng)值表征超邊的分類能力.根據(jù)超邊對訓(xùn)練集的分類結(jié)果，計算個體適應(yīng)值，以評估超邊的分類性能.當(dāng)超邊與訓(xùn)練集某個樣本正確匹配時，該超邊的準(zhǔn)確值#c加1;否則，超邊的錯誤值#w加1.個體適應(yīng)值定義為

式中:α=100為錯誤預(yù)期值;β=1為正確預(yù)期值.

3)錦標(biāo)賽選擇

每次從子種群中隨機抽取a個個體進行適應(yīng)值對比(文中取a=2)，其中適應(yīng)值最大的個體將被遺傳到下一代;重復(fù)以上過程m次，就可得到下一代種群的m個個體.

4)遷移

對經(jīng)錦標(biāo)賽選擇后的超邊按適應(yīng)值大小進行排序，將適應(yīng)值最大的q條超邊遷移到左鄰接子種群，代替其中適應(yīng)值最低的q條超邊，保證優(yōu)良個體及時擴展到鄰接子種群中.

5)交叉操作

從步驟4)得到的子種群中，以一定的交叉概率pc隨機選擇類別相同的2條超邊，在超邊的某一頂點處進行單點交叉操作，產(chǎn)生2個新的個體.

6)變異操作

采用基本位變異法，按一定的變異概率pm隨機指定某個體編碼串中的一位基因進行變異操作.若被指定進行變異操作的二進制位為0，則將其變?yōu)?;反之，若為1，則將其變?yōu)?.

7)返回步驟2)，直到超網(wǎng)絡(luò)完成預(yù)定的演化代數(shù)epoch.

3 試驗結(jié)果分析

為了驗證GA-HN的分類性能，文中采用急性白血病、肺癌、前列腺3個數(shù)據(jù)集作為試驗用例.急性白血病數(shù)據(jù)集來源于麻省理工學(xué)院采集的72個不同病人的白血病樣本，每個樣本包含6 817個基因，分為ALL和AML 2種類型.其中38個樣本(27個ALL，11個AML)作為訓(xùn)練集;另外獨立的34個樣本(20個ALL，14個AML)作為測試集.肺癌數(shù)據(jù)集包含惡性胸膜間皮瘤(malignant pleural mesothelioma，MPM)和肺腺瘤(lung adenocarcinoma，ADCA)兩種類型，共181個樣本，每個樣本12 533個基因.其中32個樣本(16個MPM，16個ADCA)作為訓(xùn)練集;另外獨立的149個樣本(15個MPM，134個ADCA)作為測試集.前列腺數(shù)據(jù)集包含102個訓(xùn)練集樣本(52個癌細胞樣本和50個正常樣本)和34個測試集樣本(包含25個癌細胞樣本和9個正常樣本)，樣本基因數(shù)為12 600.通過對3個癌癥數(shù)據(jù)集進行信噪比特征選擇［10］，文中選取樣本中的32個基因進行分類試驗.表1給出了GA-HN在急性白血病、肺癌和前列腺3個數(shù)據(jù)下遺傳算法的相關(guān)參數(shù)設(shè)定.文中所有平均識別率都是基于對測試集100次測試的結(jié)果.

表1 GA-HN參數(shù)設(shè)定

在基于遺傳算法的超網(wǎng)絡(luò)演化學(xué)習(xí)方法中，超邊階數(shù)的設(shè)定對超網(wǎng)絡(luò)的分類結(jié)果有直接影響.如圖5所示，針對不同的數(shù)據(jù)集，超網(wǎng)絡(luò)的平均識別率都隨階數(shù)的變化而變化.超邊階數(shù)過低或過高，分類的效果都不理想.這是由于當(dāng)超邊的階數(shù)過低時，超邊中所包含的特征信息過少，遺漏了某些關(guān)鍵屬性;而當(dāng)階數(shù)過高時，超邊包含的噪聲和冗余信息過多，也會降低超網(wǎng)絡(luò)的分類效果.由圖可得超網(wǎng)絡(luò)階數(shù)分別設(shè)為12，5，11時，超網(wǎng)絡(luò)分類器對急性白血病、肺癌和前列腺數(shù)據(jù)集的識別準(zhǔn)確率最高.

圖5 超網(wǎng)絡(luò)識別率隨階數(shù)的變化

表2給出了GA-HN對3種數(shù)據(jù)集的試驗結(jié)果.由表2可以看出，在給定參數(shù)條件下，GA-HN具有較高的分類正確率;在對急性白血病、肺癌、前列腺3個數(shù)據(jù)集100次的分類試驗中，GA-HN分類準(zhǔn)確率的標(biāo)準(zhǔn)差非常小，分別為2.84%，0.20%，2.90%，說明GA-HN系統(tǒng)穩(wěn)定性良好.這是由于超網(wǎng)絡(luò)利用眾多的超邊共同做出決策，因此分類器表現(xiàn)出較好的穩(wěn)定魯棒性.

表2 GA-HN對3種癌癥數(shù)據(jù)的識別率 %

超網(wǎng)絡(luò)演化學(xué)習(xí)策略的選擇對系統(tǒng)分類性能也有較大影響.表3給出了GA-HN與基于超邊替代策略的超網(wǎng)絡(luò)(random feature subset hypernetworks，RFS-HN)以及基于梯度下降策略的超網(wǎng)絡(luò)(gradient descent-based hypernetworks，GD-HN)在對3個癌癥數(shù)據(jù)集下的對比試驗結(jié)果.由表3可見，與傳統(tǒng)的RFS-HN和GD-HN相比，文中所提出的方法具有更高的平均識別率.

表3 基于不同演化學(xué)習(xí)策略的超網(wǎng)絡(luò)平均識別率對比%

表4，5，6給出了GA-HN與其他傳統(tǒng)模式識別方法包括神經(jīng)網(wǎng)絡(luò)(neutral network，NN)、遺傳規(guī)劃(genetic program，GP)、演化硬件(evolvable hardware，EHW)、基于 Bagging的決策樹 C4.5 算法(Bagging-C4.5)、組合GAM和CCM分類算法(ensemble algorithm based on GCM and CCM，EAGC)對3個癌癥數(shù)據(jù)集的識別結(jié)果對比，可見對于急性白血病和前列腺數(shù)據(jù)集，GA-HN的識別率均在該領(lǐng)域傳統(tǒng)方法的平均水平之上;而對于肺癌數(shù)據(jù)集，GA-HN在識別率上相對 Bagging-C4.5有較大提升.

表4 不同分型方法對急性白血病數(shù)據(jù)集的識別率對比

表5 不同分型方法對肺癌數(shù)據(jù)集的識別率對比

表6 不同分型方法對前列腺數(shù)據(jù)集的識別率對比

超邊的適應(yīng)值可以表征超網(wǎng)絡(luò)的識別性能.圖6是GA-HN和RFS-HN在演化過程中超邊庫平均適應(yīng)值的變化曲線.

圖6 基于不同學(xué)習(xí)策略的超網(wǎng)絡(luò)演化過程

圖6a，b，c分別為3類數(shù)據(jù)集的試驗結(jié)果，由圖6可見，超網(wǎng)絡(luò)在演化學(xué)習(xí)過程中，超邊庫的平均適應(yīng)值均呈上升趨勢.說明超邊可以對其所覆蓋的大部分訓(xùn)練集數(shù)據(jù)進行正確分類，超邊的分類能力隨學(xué)習(xí)進程不斷增強.RFS-HN采用超邊替代的策略進行演化學(xué)習(xí)，在超邊替代過程中，新的超邊通過隨機選擇產(chǎn)生.該方式雖然擴大了超邊的搜索空間，但具有不確定性，因此其超邊庫適應(yīng)值的上升速度明顯低于文中提出的GA-HN.由圖6還可以看出，經(jīng)過10代基于遺傳算法的演化學(xué)習(xí)，超網(wǎng)絡(luò)超邊庫的平均適應(yīng)值趨于平穩(wěn)，說明超網(wǎng)絡(luò)趨于收斂.

通過演化學(xué)習(xí)，超網(wǎng)絡(luò)能夠有效挖掘與模式識別相關(guān)的特征組合.表7給出了GA-HN發(fā)現(xiàn)的與肺癌相關(guān)的前10個具有較高適應(yīng)值的5階基因組合.包含這些基因組合及相應(yīng)特征取值的超邊可以有效識別相應(yīng)的樣本類型，使試驗結(jié)果具有良好的可讀性.例如，從表7中可以看出，當(dāng)超邊包含特征組合{35276-at，291-s-at，39409-at，2047-s-at，266-s-at}，且對應(yīng)取值為0，0，1，0，0時，超邊對16個ADCA類型的訓(xùn)練樣本分類完全正確.意味著當(dāng)樣本中包含上述基因組合及相應(yīng)屬性取值時，超網(wǎng)絡(luò)可以以很大的概率將其判定為ADCA類別.

表7 與肺癌相關(guān)的高階基因組合

續(xù)表

4 結(jié)論

文中將遺傳算法引入超網(wǎng)絡(luò)的演化學(xué)習(xí)過程，提出了一種基于遺傳算法的演化學(xué)習(xí)超網(wǎng)絡(luò)模型，得到如下結(jié)論:

1)基于遺傳算法演化學(xué)習(xí)的超網(wǎng)絡(luò)分類器具有較高的分類準(zhǔn)確率，并且其演化學(xué)習(xí)結(jié)果易于理解.

2)超網(wǎng)絡(luò)分類器利用數(shù)量眾多的超邊進行分類，其結(jié)果具有更高的可靠性和穩(wěn)定性.

3)演化超網(wǎng)絡(luò)能有效挖掘癌癥基因?qū)﹂g的相互作用.因此，超網(wǎng)絡(luò)模型可作為生物信息處理，尤其是疾病診斷方面的有效數(shù)據(jù)挖掘工具.

References)

［1］于化龍，顧國昌，趙 靖，等.基于DNA微陣列數(shù)據(jù)的癌癥分類問題研究進展［J］.計算機科學(xué)，2010，37(10):16-22.Yu Hualong，Gu Guochang，Zhao Jing，et al.State of the art on cancer classification problems based on DNA microarray data［J］.Computer Science，2010，37(10):16-22.(in Chinese)

［2］Dagliyan O，Uney-Yuksektepe F，Kavakli I H，et al.Optimization based tumor classification from microarray gene expression data［J］.PLoS One，2011，6(2):e14579.

［3］王 年，莊振華，范益政，等.癌癥基因分類的Laplace譜方法［J］.電子學(xué)報，2011，39(7):1594-1597.Wang Nian，Zhuang Zhenhua，F(xiàn)an Yizheng，et al.Classification of tumor gene expression data based on laplacian spectra of graphs［J］.Acta Electronica Sinica，2011，39(7):1594-1597.(in Chinese)

［4］Nanni L，Brahnam S，Lumini A.Combining multiple approaches for gene microarray classification［J］.Bioinformatics，2012，28(8):1151-1157.

［5］Cho S B，Won H H.Cancer classification using ensemble of neural networks with multiple significant gene subsets［J］.Applied Intelligence，2007，26(3):243-250.

［6］Lee J H，Lee B，Kim J S，et al.A molecular evolutionary algorithm for learning hypernetworks on simulated DNA computers［C］∥Proceedings of2011IEEE Congress of Evolutionary Computation.New Orleans:IEEE Computer Society，2011:2735-2742.

［7］Bootkrajang J，Kim S，Zhang B T.Evolutionary hypernetwork classifiers for protein-protein interaction sentence filtering［C］∥Proceedings of Genetic and Evolutionary Computation Conference.New York:ACM，2009:185-194.

［8］王 進，金理雄，孫開偉.基于演化超網(wǎng)絡(luò)的中文文本分類方法［J］.江蘇大學(xué)學(xué)報:自然科學(xué)版，2013，34(2):196-201.Wang Jin，Jin Lixiong，Sun Kaiwei.Chinese text categorization based on evolutionary hypernetwork［J］.Journal of Jiangsu University:Natural Science Edition，2013，34(2):196-201.(in Chinese)

［9］王 進，孫開偉，李鐘浩.超網(wǎng)絡(luò)道路限速標(biāo)志識別［J］.小型微型計算機系統(tǒng)，2012，33(12):2709-2714.Wang Jin，Sun Kaiwei，Lee Chong-ho.Hypernetworks for road speed limit sign recognition［J］.Journal of Chinese Computer Systems，2012，33(12):2709-2714.(in Chinese)

［10］王 進，陳 文，李鐘浩.用于癌癥分子分型的虛擬可重構(gòu)結(jié)構(gòu)演化硬件［J］.華中科技大學(xué)學(xué)報:自然科學(xué)版，2012，40(4):23-28.Wang Jin，Chen Wen，Lee Chong-ho.Virtual reconfigurable architecture-based evolvable hardware for molecular classification of cancers［J］.Journal of Huazhong U-niversity of Science and Technology:Natural Science Edition，2012，40(4):23-28.(in Chinese)

［11］Liu Kunhong，Xu Chungui.A genetic programmingbased approach to the classification of multiclass microarray datasets［J］.Bioinformatics，2009，25(3):331-337.

［12］Tan A C，Gilbert D.Ensemble machine learning on gene expression data for cancer classification［J］.Applied Bioinformatics，2003，2(3 suppl):75-83.

［13］盧新國，林亞平，駱嘉偉，等.癌癥識別中一種基于組合GCM和CCM 的分類算法［J］.軟件學(xué)報，2010，21(11):2838-2851.Lu Xinguo，Lin Yaping，Luo Jiawei，et al.Classification algorithm combined GCM with CCM in cancer recognition［J］.Journal of Software，2010，21(11):2838-2851.(in Chinese)