劉金勇 鄭恩輝 陸慧娟

（1.中國計量學院機電工程學院，杭州，310018；2.中國計量學院信息科學學院，杭州，310018）

引 言

基因表達譜數(shù)據(jù)又叫做微陣列數(shù)據(jù)，它是利用基因芯片技術(shù)測得的高通量基因在不同生理階段的表達數(shù)據(jù)值。其中“基因表達”是指細胞在聲明過程中，把儲存在DNA中的遺傳信息經(jīng)過轉(zhuǎn)錄和翻譯，轉(zhuǎn)變成具有生物活性的蛋白質(zhì)分子?！盎虮磉_水平”是指某個基因在一定時間內(nèi)控制產(chǎn)生的蛋白質(zhì)的量，它表明了細胞當前的生理狀態(tài)［1，2］。通過合理的方法對這種高通量的基因表達數(shù)據(jù)進行分析，可以得到哪些基因之間存在調(diào)控關(guān)系、不同樣本之間哪些基因的表達水平發(fā)生了變化、不同的生理階段如何影響基因的活動。

基因選擇是采用某種優(yōu)化算法從基因表達譜數(shù)據(jù)的所有屬性中選擇出一個最具有疾病識別能力的基因子集的過程［3，4］。選擇出的基因子集在腫瘤識別過程中發(fā)揮著至關(guān)重要的作用?；诨蛐畔⑴判虻倪^濾法［5］和依賴具體分類器選取基因的纏繞法［6，7］是兩種主要的基因選擇方法。基于排序的過濾法如、信噪比［8］、信息增益［9，10］等具有簡單快速的特點，但它們都是按照單個基因蘊含的分類信息多少為標準的，沒有考慮基因之間的相互聯(lián)系，而含有分類信息高的基因組合并不一定是最優(yōu)的組合［11］。纏繞法與具體分類器（如支持向量機（Support vector machine，SVM），ELM 等）結(jié)合，將分類器預(yù)測正確率作為評價基因組合好壞的標準，這種方法可以找出最優(yōu)的基因組合，同時最小化基因子集，但算法每次評價一個基因組合都要進行分類器訓練，時間復(fù)雜度較高，而且選擇出的基因子集在其他類型的分類器中的泛化能力不高。

粒子群優(yōu)化算法是一種新興的基于群體智能的啟發(fā)式全局搜索算法，通過粒子間的競爭和協(xié)作以實現(xiàn)在復(fù)雜搜索空間中尋找全局最優(yōu)點。本文中使用粒子群算法來進行特征選擇，但是由于大多數(shù)PSO算法在應(yīng)用的過程中，其初始化都是隨機的，不能保證初始群體粒子的合理分布，在PSO搜索過程中，就容易出現(xiàn)大部分粒子均被相同的局部極值所限制時，導(dǎo)致當前的粒子群失去多樣性，陷入局部最好解，出現(xiàn)“早熟現(xiàn)象”，最終影響最優(yōu)解的搜索。為了解決這一缺陷，在PSO算法進行搜索之前，先對基因進行聚類，并對聚類結(jié)果進行初步選擇，將被選中的簇的中心作為PSO的初始值，每個被選中的簇作為一個搜索空間，并利用ELM的分類精度作為特征選擇的適應(yīng)評價標準。

這種將基因聚類提取基因先驗信息并耦合進PSO算法進行特征選擇的思想，由于其初始化都是固定的，且符合數(shù)據(jù)本身特點，在很大程度上代表了本來的數(shù)據(jù)，這樣就保證了初始群體粒子的合理分布，在PSO搜索過程中，不容易出現(xiàn)大部分粒子均被相同的局部極值所限制的情況，避免出現(xiàn)局部最好解，最終得到的解便是最優(yōu)解，且限制搜索范圍能夠減少搜索的時間，減少時間復(fù)雜度。

1 相關(guān)知識點

1.1 熵與信息增益

令X為隨機變量，X的不同取值xi，i＝1，2，… 對應(yīng)著不同的概率P（xi），i＝1，2，… ，那么X的信息熵定義為

對于分類系統(tǒng)來說，類別C（c1，c2，…cl）是變量，因此分類系統(tǒng)的熵就可以定義為

式（2）表示特征的變化越大，它所代表的信息也就越多。特別地，對于兩類分類問題，信息熵可以表示為

基因表達譜數(shù)據(jù)的信息增益是對每一個基因而言的，對應(yīng)特定的含有n種情況的基因X，它所對應(yīng)的條件熵為

其中P（ci｜xj）代表基因xj屬于類別ci的條件概率。該基因X為整個分類系統(tǒng)所帶來的信息增益，可以用原系統(tǒng)的信息熵與基因X固定之后的條件熵之間的差值，用式（5）表示。

IG（X）便代表了基因表達譜數(shù)據(jù)中每個基因的信息增益，信息增益值越大，則該基因代表的分類信息就越多。

1.2 微粒群優(yōu)化算法

PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中，每個優(yōu)化問題的潛在解都是搜索空間中的一只鳥，稱之為粒子。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適值，每個粒子還有一個速度決定它們飛翔的方向和距離，然后粒子們就追隨當前的最優(yōu)粒子在解空間中搜索。

PSO初始化為一群隨機粒子（隨機解），然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己；第一個就是粒子本身所找到的最優(yōu)解，這個解稱為個體極值；另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。

假設(shè)在一個D維的目標搜索空間中，有N個粒子組成一個群落，其中第i個粒子表示為一個D維的向量

第i個粒子的“飛行 ”速度也是一個D維的向量

第i個粒子迄今為止搜索到的最優(yōu)位置稱為個體極值，記為

整個微粒群迄今止搜索到的最優(yōu)位置為全局極值，記為

在找到這兩個最優(yōu)值時，粒子根據(jù)式（10，11）來更新自己的速度和位置

式中：c1和c2為學習因子，也稱加速常數(shù)，r1和r2為［0，1］范圍內(nèi)的均勻隨機數(shù)。式（6）右邊由3部分組成，第1部分為“慣性”部分，反映了粒子的運動“習慣”，代表粒子有維持自己先前速度的趨勢；第2部分為“認知”部分，反映了粒子對自身歷史經(jīng)驗的記憶，代表粒子有向自身歷史最佳位置逼近的趨勢；第3部分為“社會”部分，反映了粒子間協(xié)同合作與知識共享的群體歷史經(jīng)驗，代表粒子有向群體或鄰域歷史最佳位置逼近的趨勢，根據(jù)經(jīng)驗，通常c1＝c2＝2。vid是粒子的速度，vid∈［-vmax，vmax］，vmax是常數(shù)，由用戶設(shè)定用來限制粒子的速度。r1和r2是介于 ［0，1］之間的隨機數(shù)。

1.3 極限學習機

式中：βi為連接第i個隱層節(jié)點與輸出神經(jīng)元的輸出權(quán)值，ai為連接輸入神經(jīng)元與第i個隱層節(jié)點的輸入權(quán)值，bi為第i個隱層節(jié)點的偏置，oj為第j個輸入樣本的輸出值，j＝1，…，N。

如果含有L個隱層節(jié)點，且激活函數(shù)為g（x）的單隱層前饋神經(jīng)網(wǎng)絡(luò)可以零誤差逼近于N個訓練樣本，即存在βi，ai和bi，使得

成立，并且

其中式（13）可以表示為

其中H稱為ELM的隱層輸出矩陣

如果隱層節(jié)點個數(shù)L和樣本數(shù)量N是相等的，那么可以很容易的知道式（13，14）是成立的，但是當L＜N時，單隱層前饋神經(jīng)網(wǎng)絡(luò)并不能零逼近于N個訓練樣本。這時式（15）可以表示為

E＝ ［e1，e2，…，eN］T被稱為是訓練誤差。這里訓練一個ELM也即計算訓練誤差E的最小范數(shù)

因此，通過式（18）并利用最小二乘的方法計算得到輸出權(quán)重

其中H＊為矩陣H的Moore-Penrose廣義逆。

2 基于聚類與PSO的基因選擇

在基因組學中，聚類算法是研究基因間相互關(guān)系的最基本手段。聚類算法能夠?qū)⒛切┚哂邢嗨乒δ芴攸c的基因聚在一起，根據(jù)聚類的結(jié)果，可以預(yù)測未知基因的功能，尋找基因之間的調(diào)控關(guān)系以及發(fā)現(xiàn)共同的模式。其中比較流行的啟發(fā)式方法是K-means方法。在對基因進行聚類時聚類數(shù)目的選擇有兩種方法，一種是隨機選取，但是這種選取方法沒有任何的針對性，需要迭代的次數(shù)較多，計算量也比較大；另外一種是根據(jù)某種準則選取，對基因表達譜數(shù)據(jù)的基因進行聚類時，需要結(jié)合數(shù)據(jù)本身的特點，包括數(shù)據(jù)的類別信息和冗余度信息等，如針對包含兩種類別的樣本進行聚類的時候，基因可以分為與樣本類別相關(guān)的2簇以及1簇對樣本分類無關(guān)的冗余基因，所以可以確定聚類數(shù)目為3。

將基因表達譜數(shù)據(jù)分成訓練集和測試集，通過信息增益的方法選擇前n個信息熵最大的基因。接下來便是利用聚類算法對初選的基因子集進行聚類，聚類方法采用K-means方法，聚類數(shù)目按照上述方法給出，如對于兩類樣本，聚類數(shù)目選擇為3，k類樣本則對應(yīng)聚類數(shù)目為k＋1。借助分類器對各簇的基因分類性能進行分析，將具有高分類性能的簇選擇出來，排除對分類影響較小的簇，這些被選擇的簇所包含的基因構(gòu)成一個冗余度較低的特征基因子集。

最后將被選中的簇的中心作為初始位置，每一簇作為一個搜索空間，利用PSO進行Wrapper式的特征選擇，本文采用ELM來評價基因優(yōu)劣。根據(jù)ELM分類器返回的驗證集上的準確率評價每個粒子的適應(yīng)度值，通過不斷更新PSO中群體粒子的位置和速度來搜索全局最優(yōu)解。

對選取的基因的評價，利用ELM分類器計算PSO和聚類算法選擇出來的特征基因的適應(yīng)度，評價函數(shù)為

在特征選擇過程中，應(yīng)該選擇樣本測試精度高、基因個數(shù)少的粒子，即要選擇適應(yīng)度值最大的那個粒子，所選擇的基因是依賴于ELM分類器的。在PSO中，一個粒子代表選擇的一組基因子集，粒子在搜索過程中通過基因子集在分類器中評價，即PSO的適應(yīng)值函數(shù)，更新個體最好位置和全局最好位置，直到達到最大迭代次數(shù)得到一組最優(yōu)基因子集，最后利用分類器得到測試準確率，較好的即為提取到的關(guān)鍵基因。其中基因子集的評價函數(shù)的過程中，樣本測試精度通過ELM分類器來完成的。選擇出特征基因之后采用ELM建立分類模型，然后根據(jù)建立的模型測試分類正確率。

算法步驟描述如下：

（1）利用信息增益方法，對原始基因進行過濾，形成精簡的基因子集FS；

（2）利用K均值聚類方法對FS進行聚類，將FS聚類為規(guī)定的簇數(shù)；

（3）使用ELM判斷每一簇中基因的分類性能，并選擇具有較高分類性能的簇中的基因作為特征基因子集FSC；

（4）將FSC的聚類中心作為PSO的初始化位置，每一個簇作為單獨的搜索空間進行PSO搜索；

（5）對選取的基因的評價，如果滿足要求的指標，則基因的選擇過程結(jié)束，接下來進行步驟6；如果不滿足要求，則采用式（10）和式（11）進行最優(yōu)值和粒子位置和速度的更新，重新進行特征選擇；

（6）選擇出特征基因之后采用ELM建立分類模型，然后根據(jù)建立的模型測試分類正確率。

3 實驗結(jié)果分析

為了驗證算法的有效性，本文在3個基因表達數(shù)據(jù)集上進行仿真實驗。白血病（Leukemia）、結(jié)腸癌（colon）、小圓藍細胞（SRBCTs）。試驗中用到的所有仿真都是在Matlab 2010a中實現(xiàn)的，所用計算機的配置為酷睿雙核2.5GHz，2GB內(nèi)存。由于基因表達譜數(shù)據(jù)的樣本數(shù)非常少，所有的實驗都采用K-折交叉驗證的方法，其中k值均選擇為5。

在開始特征選擇算法之前，把數(shù)據(jù)集進行歸一化處理，使得樣本的每一維特征向量的均值為0，方差為1。接下來對基因表達譜數(shù)據(jù)使用信息增益的方法進行初步的選擇，確定初選的基因子集，一般選擇前200個信息增益值最大的基因構(gòu)成候選基因子集。然后對這個子集進行k均值聚類，最佳的k值根據(jù)樣本類別數(shù)而定，3個數(shù)據(jù)集分別為3，3和5。對基因表達譜數(shù)據(jù)的訓練集的基因進行聚類后，將ELM作用于每個簇，得到該簇中最優(yōu)基因子集的分類性能。圖1～3分別為白血病、結(jié)腸癌和小圓藍細胞數(shù)據(jù)集的每個聚類簇中不同數(shù)目的基因組合得到的最好分類精度。其中ELM分類器使用的激活函數(shù)為sigmoid函數(shù)，最優(yōu)隱藏層節(jié)點數(shù)通過遞增的方式從1增加到與訓練樣本數(shù)相等。

從圖1～3中可以看出，隨著選擇基因數(shù)目的增多，分類正確率都基本呈現(xiàn)先增加后減少的趨勢。在白血病數(shù)據(jù)集中單獨使用簇1和簇3對樣本進行分類獲得的分類精度較簇3高；結(jié)腸癌數(shù)據(jù)集中簇2和簇3獲得較簇1高的分類精度；小圓藍細胞中簇1相較其他簇獲得的分類精度比較低。所以根據(jù)2節(jié)中的描述，白血病數(shù)據(jù)集中簇2被視為冗余基因的集合，結(jié)腸癌數(shù)據(jù)集中簇1被視為冗余基因的集合，小圓藍細胞中簇1被視為冗余基因的集合。

通過以上對基因聚類結(jié)果的分析，分別得到了3個數(shù)據(jù)集的備選特征基因子集。再用PSO結(jié)合ELM搜索最優(yōu)基因子集。在搜索過程中PSO算法的種群規(guī)模設(shè)置為10，最大迭代次數(shù)為100，初始學習因子c1＝2，c2＝2，慣性權(quán)重w＝0.8；ELM分類器使用sigmoid激活函數(shù)，最優(yōu)隱藏層節(jié)點數(shù)通過遞增的方式獲得（從1增加到與訓練樣本數(shù)相等），適應(yīng)度調(diào)節(jié)參數(shù)α設(shè)置為0.8。

圖1 白血病數(shù)據(jù)不同簇中不同基因子集的分類性能Fig.1 The Leukemia dataset′s classification accuracy when sub-genes come from different clusters

圖2 結(jié)腸癌數(shù)據(jù)不同簇中不同基因子集的分類性能Fig.2 The colon dataset′s classification accuracy when sub-genes come from different clusters

圖3 小圓藍細胞數(shù)據(jù)不同簇中不同基因子集分類性能Fig.3 The SRBCT dataset′s classification accuracy when sub-genes come from different clusters

當適應(yīng)度值達到一定的閾值或者不在變化的時候，或者迭代達到最大次數(shù)時，搜索過程便結(jié)束。最大適應(yīng)度值時對應(yīng)的被搜索到的基因也就是該算法獲得的最優(yōu)關(guān)鍵基因。

適應(yīng)度的設(shè)定是分類精度和被選擇基因個數(shù)的綜合指標，適應(yīng)度值越高，說明分類精度越高，被選擇的基因個數(shù)越少。分類精度越高則表明癌癥的診斷率越高，被選擇的基因個數(shù)越少表明獲得的靶向基因越精確。

對使用本文方法選擇后的樣本進行分類，最優(yōu)關(guān)鍵基因的個數(shù)和分類精度的結(jié)果在表1中給出。其中平均分類精度是30次結(jié)果的平均值。

表1 關(guān)鍵基因個數(shù)與分類精度Table 1 Relationship between key genes′number and classification accuracy %

從分類結(jié)果可以看出使用該方法獲得的關(guān)鍵基因子集能夠獲得非常高的分類精度，且能夠盡可能多的消除冗余基因。在白血病數(shù)據(jù)集上，只需要3個關(guān)鍵基因，就可以獲得100%的分類精度；在小圓藍細胞數(shù)據(jù)集上只需要9個關(guān)鍵基因即可以獲得100%的分類精度；在較難分類的結(jié)腸癌數(shù)據(jù)集上，只需要3個關(guān)鍵基因便可以獲得93.62%的平均分類精度，但是在分類效果較好的時候能夠獲得100%的分類精度。3個數(shù)據(jù)集上的關(guān)鍵基因可以用表2描述。

表2 本文方法選擇的關(guān)鍵基因描述Table 2 Description of the genes selected by the proposed method

經(jīng)查閱相關(guān)資料［2-3］可以發(fā)現(xiàn)，使用此方法獲得的特征基因，確實是該基因表達譜數(shù)據(jù)對應(yīng)的癌癥的關(guān)鍵基因。因此該方法是具有很強的適用價值，不僅能夠提高癌癥的診斷率，而且能夠有效獲得靶向基因，為生物醫(yī)學提供診斷的依據(jù)。

最后將本文所提方法與幾種經(jīng)典方法以及第3章中提出的PSO-Selection方法進行比較，包括分類精度和選擇基因個數(shù)以及算法的耗時3個方面，比較結(jié)果見表3～5。

表3 本文方法與其他方法在白血病數(shù)據(jù)集上的比較Table 3 Comparison of the proposed method with other method on Leukemia dataset

表4 本文方法與其他方法在結(jié)腸癌數(shù)據(jù)集上的比較Table 4 Comparison of the proposed method with other method on SRBCT dataset

表5 本文方法與其他方法在小圓藍細胞數(shù)據(jù)上的比較Table 5 Comparison of the proposed method with other method on colon dataset

從表3～5中可以看出，本文方法與其他6種方法相比，使用最少的基因子集便可以獲得與經(jīng)典的Wrapper方法近似的分類精度，在3個數(shù)據(jù)集上，白血病和小圓藍細胞均獲得100%的分類精度，在比較難分類的結(jié)腸癌數(shù)據(jù)集上獲得的分類精度只比最優(yōu)秀的特征選擇方法低了0.03%。從算法的耗時上分析，可以看出本文方法雖然遠高于T-statistic、信噪比和PSO-Selection方法，但是選擇的基因子集個數(shù)比這3種方法少很多，且分類精度普遍高于這3種方法；而與PSO-ELM，GASVM，PSO-SVM 方法相比［15，16］，在 基本上 沒有降低分類精度的前提下，大大地降低了算法的耗時。雖然本文方法比PSO-ELM方法多了基因聚類以及聚類后簇的選擇過程，但是在進行PSO搜索之前已經(jīng)將搜索范圍縮小，且使用聚類中心作為PSO的初始位置使得搜索過程更快趨于最優(yōu)，這兩個因素都使得本文方法的耗時遠低于PSOELM方法。

4 結(jié)束語

為了有效降低基因表達譜數(shù)據(jù)基因之間的冗余度，本文提出了一種基于聚類和粒子群算法的基因選擇方法。因為聚類算法可以根據(jù)基因的功能將具有相同功能的基因聚成一簇，不同功能的基因聚在不同的簇，通過合理的預(yù)處理，含有大量噪聲的信息簇被移除，而具有高貢獻度的基因簇的基因子集構(gòu)成候選特征基因作為PSO的搜索空間。從實驗結(jié)果可以看出，本文方法能夠成功選擇較少數(shù)目但是有較高分類率的基因子集。

［1］黃德雙.基因表達譜數(shù)據(jù)挖掘方法研究［M］.北京：科學出版社，2009.

Huang Deshuang.Research on data mining of gene expression［M］.Beijing：Science Press，2009.

［2］鄭繼平.基因表達調(diào)控［M］.合肥：中國科學技術(shù)出版社，2012.

Zheng Jiping.Regulation of gene expression［M］.He fei：Chinese Science and Technology Press，2012.

［3］楊華.基于粒子群算法的特征選擇方法研究［D］.長沙：湖南大學，2010.

Yang Hua.Research on significant genes selection method based on PSO algorithm［D］.Changshang：Hunan University，2010.

［4］Golub T R，Slonim D K，Tamayo P，et al.Class discovery and class prediction by gene expression monitoring［J］.Science，1999，286：531-537.

［5］Liu H Q，Li J Y，Wong L.A comparative study on feature selection and classification methods using Gene expression profiles and proteomic patterns［J］.Genome Informatics，2002，13：51-60.

［6］Zhao Z，Wang L，Liu H.Efficient spectral feature selection with minimum redundancy［C］∥Proceedings of the National Conference on Artificial Intelligence.Atlanta，Georgia，USA：［s.n.］，2010，1：673-678.

［7］Chris D，PengH C.Minimum redundancy feature selection from microarray gene expression data ［J］J Bioinform Comput Biol，2005，3（2）：185-205.

［8］Hu Y，Loizou P C.Speech enhancement based on wavelet thresholding the multitaper Spectrum ［J］.IEEE Trans on Speech and Audio Processing，2004，12（1）：59-67.

［9］劉慶和，梁正友.一種基于信息增益的特征優(yōu)化選擇方法［J］.計算機工程與應(yīng)用，2011，47（12）：130-132.

Liu Qinghe，Liang Zhengyou.Optimized approach of feature selection based on information gain［J］.Computer Engineering and Application，2011，47（12）：130-132.

［10］任江濤，孫婧昊，黃煥宇.一種基于信息增益及遺傳算法的特征選擇算法［J］.計算機科學，2006，10（33）：193-196.

Ren Jiangtao，Sun Jinghao，Huang Huanyu.Feature selection based on information gain and GA ［J］.2006，10（33）：193-196.

［11］Leung Y K，Hung Y.A multiple filter multiple wrapper approach to gene selection and microarray data classification［J］.IEEE/ACM Transactions on Computational Biology and Bioinformatics，2010，7（1）：108-117.

［12］Huang G B，Ding X J，Zhou H M.Optimization method based extreme learning machine for classification［J］.Neurocomputing，2010，74：155-163.

［13］Huang G B，Zhu Q Y，Siew C K.Extreme learning machine：theory and applications［J］.Neurocomputing，2006（70）：489-501.

［14］Huang G B，Zhu Q Y，Siew C K.Extreme learning machine：a new learning scheme of feedforward neural networks［C］∥Proceedings of International Joint Conference on Neural Networks（DCNN2004）.Budapest，Hungary：［s.n.］，2004：25-29.

［15］陸慧娟.基于極限學習機集成的腫瘤基因表達數(shù)據(jù)分類［D］.徐州：中國礦業(yè)大學，2013.

Lu Huijuan.Research on tumor gene expression data classification［D］.Xuzhou：China Mining University，2013.

［16］鄭馨，王勇，汪國有.EM聚類和SVM自動學習的白細胞圖像分割算法［J］.數(shù)據(jù)采集與處理，2013，28（5）：614-619

Zheng Xin，Wang Yong，Wang Guoyou.White blood cell segmentation using expectation-maximization and automatic support vector machine learning［J］.Journal of Data Acquisition and Processing，2013，5（28）：614-619.