基于遺傳算法與支持向量機(jī)的癌癥特征基因提取

唐銘一 鄭虹 韓立權(quán)

摘要：針對(duì)癌癥基因特征提取問(wèn)題，根據(jù)遺傳算法中不同迭代時(shí)期的種群特性，設(shè)計(jì)了新的突變方法。多突變基因庫(kù)與種群代數(shù)相關(guān)的設(shè)計(jì)，使得算法能夠較快地收斂到最優(yōu)解而又避免其過(guò)早陷入局部最優(yōu)解中;選擇算子中包括個(gè)體對(duì)種群的基因豐富度貢獻(xiàn);針對(duì)種群中大量的重復(fù)個(gè)體，加入重復(fù)控制，去除重復(fù)個(gè)體，提高個(gè)體與種群基因的多樣性。算法在幾種實(shí)驗(yàn)數(shù)據(jù)集上均取得了較好的結(jié)果。

關(guān)鍵詞： 遺傳算法; 支持向量機(jī); 特征提取; 選擇算子; 變異算子

中圖分類號(hào)：TP181? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）26-0010-03

Abstract： A new mutation method was designed according to the population characteristics of different iteration periods in genetic algorithm to solve the problem of cancer gene extraction. Multi-mutation gene bank is designed to related with population algebra， so the algorithm converge to the optimal solution quickly and avoid falling into the local optimal solution too early. Selection operator is designed to relate with population， including the contribution of individuals to the genetic richness of the population， the MIC evaluation of individuals， and the redundancy of genes within individuals， which makes the algorithm pay attention to both the population and the characteristics of individuals. The genetic diversity of individuals and populations are improved? by eliminating duplicates.

Key words：genetic algorithm;? support vector machine;? feature extraction;? selection operator;? mutation operator

1 引言

基因芯片，又稱DNA微陣列，是利用核苷酸雜交技術(shù)檢測(cè)生物基因的表達(dá)，采用高度集成的方法，將事先設(shè)計(jì)好的核苷酸序列組合成微陣列，以達(dá)到高通量檢測(cè)的目標(biāo)，是一個(gè)融合生命科學(xué)、計(jì)算機(jī)科學(xué)、化學(xué)等多學(xué)科高度結(jié)合的技術(shù)，廣泛應(yīng)用于基因測(cè)序、生物表達(dá)分析、癌癥致病基因的發(fā)現(xiàn)與分析等方面[1]。利用基因芯片技術(shù)進(jìn)行癌癥分類，不僅可以幫助診斷疾病，而且可以幫助研究者了解疾病在分子層面上的成因。但由于微陣列數(shù)據(jù)的特殊性，使得基因芯片數(shù)據(jù)集具有少樣本，高維度的特點(diǎn)，過(guò)高的維數(shù)會(huì)產(chǎn)生維數(shù)災(zāi)難的問(wèn)題[2]，而且數(shù)量眾多的特征里又存在很多冗余和噪聲基因，使得分類器不能以較高的準(zhǔn)確率分類，同時(shí)基因芯片數(shù)據(jù)集通常是多患病樣本，這造成分類樣本不平衡的問(wèn)題[3-4]，分類器一般基于數(shù)據(jù)是平衡的這一假設(shè)，這些也是大部分研究者正在著手解決的問(wèn)題。

對(duì)于基因芯片數(shù)據(jù)集樣本少、高維度、高冗余的特點(diǎn)，一般要對(duì)數(shù)據(jù)進(jìn)行特征提取，根據(jù)特征提取方法與分類器結(jié)合方式的不同，又分為filter和wapper方法[5]，其中filter方法的特征提取與分類器分離，僅僅利用數(shù)據(jù)的數(shù)字特征進(jìn)行相關(guān)性分析，剔除無(wú)效特征，這種方法與分類器無(wú)關(guān)，擴(kuò)展性強(qiáng)，并且輕量，但篩選出的特征基因在不同分類器上的分類效果差異性大，篩選出的特征的分類效果一般。wapper方法，分類器與特征提取算法是一體的，特征評(píng)分標(biāo)準(zhǔn)是分類器的分類效果，因此提取出的特征，對(duì)特定分類器的分類效果是最優(yōu)的。

目前比較常用的特征提取算法有遺傳算法與支持向量機(jī)（svm）結(jié)合[6-7]，粒子群算法與svm結(jié)合，退火算法與svm結(jié)合的，等等。本文根據(jù)遺傳算法中不同迭代時(shí)期的種群特性，設(shè)計(jì)了新的突變方法，在選擇算子中加入種群相關(guān)的評(píng)價(jià)方法，結(jié)合svm給出了一種特征基因提取算法。

2 特征基因提取的遺傳算法設(shè)計(jì)

2.1 染色體編碼

遺傳算法的第一步是要構(gòu)建染色體，代表問(wèn)題解集中的一個(gè)解，將染色體的長(zhǎng)度設(shè)置為所提取的特征子集的大小，每個(gè)位置的數(shù)值代表基因的索引，如圖1所示。

2.2 種群的初始化和適應(yīng)度函數(shù)

本算法對(duì)種群進(jìn)行隨機(jī)初始化，即每個(gè)染色體的基因都是隨機(jī)生成的，并且染色體中沒(méi)有重復(fù)的基因。種群大小設(shè)置為100，適應(yīng)度函數(shù)使用svm分類器的分類準(zhǔn)確度給出，進(jìn)行5折交叉驗(yàn)證，即首先將數(shù)據(jù)集5等分，測(cè)試集依次取5等分的一份，生成5種不同的訓(xùn)練和測(cè)試集[8]，然后同時(shí)訓(xùn)練5個(gè)分類器，并對(duì)5個(gè)分類器在測(cè)試集上的分類準(zhǔn)確度加和求平均得到個(gè)體的適應(yīng)度。

2.3 遺傳算子設(shè)計(jì)

2.3.1 選擇算子

選擇適應(yīng)度排名前10%的個(gè)體為精英個(gè)體，精英個(gè)體全部保留為下一代個(gè)體。

2.3.2 交叉算子

采用中點(diǎn)交叉互換法，如圖2所示，從種群中隨機(jī)選出兩個(gè)個(gè)體，以解的中點(diǎn)為界，交叉互換兩個(gè)解的一部分。本算法中交叉互換率設(shè)置為0.7，本算法在此步添加了重復(fù)控制，當(dāng)chromosome中包含重復(fù)基因時(shí)，此次交叉互換失效，重新進(jìn)行。

2.3.3 變異算子

變異過(guò)程是增加種群基因豐富度的關(guān)鍵步驟，本算法在這里進(jìn)行了仔細(xì)的設(shè)計(jì)。

采用單基因突變，如圖3所示，隨機(jī)選取解的一個(gè)基因進(jìn)行突變，本算法在突變的過(guò)程中添加了重復(fù)控制，突變時(shí)進(jìn)行檢查，如果突變基因在原來(lái)的解中，則需要重新進(jìn)行突變，這一步和交叉互換中的重復(fù)控制保證了所有的染色體符合解約束（特征子集數(shù)），突變率設(shè)置為0.3。

本算法設(shè)計(jì)了一個(gè)基于最大信息系數(shù)（MIC）打分，并與種群代數(shù)相關(guān)的突變方法進(jìn)行突變基因的選擇。MIC又稱最大相互信息系數(shù)，是基于信息的非參數(shù)性方法，用于衡量?jī)蓚€(gè)變量之間的線性或非線性的強(qiáng)度。本算法先利用MIC計(jì)算基因與類別的相關(guān)性，并將相關(guān)性作為基因的分?jǐn)?shù)。

突變基因的集合稱為突變基因庫(kù)，算法設(shè)計(jì)了兩個(gè)突變基因庫(kù)，每次突變只以一定概率選擇其中的一個(gè)基因庫(kù)，同時(shí)選擇概率也隨種群代數(shù)變化而變化。

1）優(yōu)勢(shì)基因庫(kù)，挑選MIC打分排名前25%的基因構(gòu)成此庫(kù)，并且打分越高的基因其在庫(kù)中的重復(fù)基因就越多。具體是這樣設(shè)計(jì)的：

上式中G為基因庫(kù)，[gi]為第i個(gè)基因，基因庫(kù)由MIC分?jǐn)?shù)前25%的基因組成，[gscorei]為第i個(gè)基因的MIC分?jǐn)?shù)，[Sumscore]為[G]中所有基因的分?jǐn)?shù)和，[ gweighti]為基因[gi]的權(quán)重，[gweightmin]為G中最小的權(quán)重，[Gsize]為基因庫(kù)的大?。ò貜?fù)基因），其中滿足[gscorei=gscoremin]的基因[gi]不重復(fù)，[gnumi]為G中基因[gi]重復(fù)的次數(shù)，優(yōu)勢(shì)基因庫(kù)由[gi]和[gnumi]確定。

2）全量基因庫(kù)，由所有基因構(gòu)成，每個(gè)基因等概率被選擇。

選擇突變基因庫(kù)的策略是隨著種群代數(shù)越多越傾向于選擇全量基因庫(kù)，這是因?yàn)閮?yōu)勢(shì)基因庫(kù)的作用是向種群中快速引入優(yōu)勢(shì)基因，同時(shí)使得算法的隨機(jī)性減小，后期傾向于以大的隨機(jī)性選擇突變基因，目的是防止陷入局部最優(yōu)點(diǎn)，選擇全量基因庫(kù)的概率為[g/100]，其中g(shù)表示種群的代數(shù)。突變基因的概率分布由基因MIC分?jǐn)?shù)的分布漸變?yōu)榫鶆蚍植肌?/p>

2.4 移除重復(fù)個(gè)體

上述流程會(huì)產(chǎn)生大量重復(fù)的個(gè)體，雖然個(gè)體的重復(fù)有一定的概率意義，即優(yōu)勢(shì)個(gè)體的重復(fù)多，保留下來(lái)的概率大，但其極大影響了種群的豐富度，還會(huì)導(dǎo)致算法過(guò)早收斂陷入局部最優(yōu)解當(dāng)中。

圖4是使用種群個(gè)體去重操作前的結(jié)果圖，左圖表示的是基因重復(fù)數(shù)排名前10的基因占到種群基因總數(shù)的比例， 在一定程度上反映了種群中基因的集中程度，右圖是每代種群中基因的種類數(shù)，反映了種群中基因的豐富程度，由上圖我們可以發(fā)現(xiàn)，基因的豐富度減小的極快而且非常集中，基因的豐富度小，算法的隨機(jī)性差，很容易陷入局部最優(yōu)解而過(guò)早收斂。

圖5是采用個(gè)體去重的結(jié)果圖?？梢园l(fā)現(xiàn)由于在每一代個(gè)體都進(jìn)行了去重，重復(fù)基因數(shù)量排名前10的基因，基因總數(shù)最多只占到基因總數(shù)的60%左右，基因的種類也維持在100個(gè)左右，由于基因的豐富度增大了，算法的隨機(jī)性便增強(qiáng)了，有效地避免了算法收斂到局部最優(yōu)解。

3 實(shí)驗(yàn)結(jié)果

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

實(shí)驗(yàn)使用了5種不同的基因芯片公開數(shù)據(jù)集來(lái)驗(yàn)證本算法的有效性，數(shù)據(jù)集包含了二分類數(shù)據(jù)集和多分類數(shù)據(jù)集，其中二分類數(shù)據(jù)集包括colon，carcinoma，leukemia數(shù)據(jù)集，其中colon和carcinama包含兩個(gè)類別，一個(gè)是患病類，一個(gè)是正常類，leukemia則包含兩個(gè)患病類，他們分別是急性淋巴細(xì)胞白血?。ˋLL）和急性髓性細(xì)胞白血?。ˋML）。多類別數(shù)據(jù)集有SRBCT和MLL，其中SRBCT數(shù)據(jù)集包含4種癌癥類別，他們分別是尤文氏肉瘤（EWS），非霍奇金淋巴瘤（NHL），神經(jīng)母細(xì)胞瘤（NB）和橫紋肌肉瘤（RMS），MLL數(shù)據(jù)集包含3種類別，分別是急性淋巴細(xì)胞白血?。ˋLL），急性髓性細(xì)胞白血?。ˋML）和混合血統(tǒng)白血病（MLL）。

3.2 實(shí)驗(yàn)結(jié)果分析

在各數(shù)據(jù)集上獨(dú)立重復(fù)進(jìn)行20次，與其他算法相對(duì)比，結(jié)果見表1。

4 結(jié)論

本文從選擇算子，變異算子和種群個(gè)體冗余入手，改進(jìn)了遺傳算法挑選特征基因和變異的方法。通過(guò)實(shí)驗(yàn)得出，僅改變選擇和變異算子，算法準(zhǔn)確率有所提升，考慮種群去重和選擇算子之間的相互作用時(shí)，準(zhǔn)確率相對(duì)差一些，這是后續(xù)的研究中需要解決的一個(gè)問(wèn)題。

參考文獻(xiàn)：

[1] 王翔，胡學(xué)鋼.高維小樣本分類問(wèn)題中特征選擇研究綜述[J]. 計(jì)算機(jī)應(yīng)用，2017（9）：2433-2438.

[2] 劉金勇.基因表達(dá)譜數(shù)據(jù)特征選擇與提取方法研究[D].杭州：中國(guó)計(jì)量學(xué)院，2014.

[3] 翟云，楊炳儒，曲武. 不平衡類數(shù)據(jù)挖掘研究綜述[J]. 計(jì)算機(jī)科學(xué)， 2010， 37（10）：27-32.

[4] 于化龍， 高尚， 趙靖， 等. 基于過(guò)采樣技術(shù)和隨機(jī)森林的不平衡微陣列數(shù)據(jù)分類方法研究[J]. 計(jì)算機(jī)科學(xué)， 2012（5）：196-200.

[5] 陳巖， 來(lái)海鋒， 王清， 等. 基于filter-wrapper的兩步特征變量提取方法[J]. 機(jī)電工程， 2010（4）： 67-71.

[6] Li S ， Wu X ， Hu X . Gene Selection Using Genetic Algorithm and Support Vectors Machines[J]. Soft Computing， 2008， 12（7）：693-698.

[7] Motieghader H， Najafi A， Sadeghi B， et al. A Hybrid Gene Selection Algorithm for Microarray Cancer Classification Using Genetic Algorithm and Learning Automata[J]. Informatics in Medicine Unlocked， 2017： 246-254.

[8] 胡局新， 張功杰. 基于K折交叉驗(yàn)證的選擇性集成分類算法[J]. 科技通報(bào)， 2013（12）：123-125.

【通聯(lián)編輯：唐一東】