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

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

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

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

中圖分類號：TP181? ? ? ? 文獻標識碼：A

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

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

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

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

2.1 染色體編碼

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

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

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

2.3 遺傳算子設(shè)計

2.3.1 選擇算子

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

2.3.2 交叉算子

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

2.3.3 變異算子

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

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

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

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

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

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

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

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

2.4 移除重復(fù)個體

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

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

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

3 實驗結(jié)果

3.1 實驗數(shù)據(jù)集

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

3.2 實驗結(jié)果分析

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

4 結(jié)論

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

參考文獻：

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

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

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

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

[5] 陳巖， 來海鋒， 王清， 等. 基于filter-wrapper的兩步特征變量提取方法[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折交叉驗證的選擇性集成分類算法[J]. 科技通報， 2013（12）：123-125.

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