敖　培,李　賀,李　明,楊百順,李延強(qiáng)（.河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院；.河南師范大學(xué)軟件學(xué)院；. 河南師范大學(xué)政治與公共管理學(xué)院,河南 新鄉(xiāng) 45007）

基于聚類和貓群優(yōu)化的基因選擇算法

敖培1,李賀1,李明2,楊百順2,李延強(qiáng)3
（1.河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院；2.河南師范大學(xué)軟件學(xué)院；3. 河南師范大學(xué)政治與公共管理學(xué)院,河南 新鄉(xiāng) 453007）

本文提出一種基于聚類和貓群優(yōu)化基因選擇算法，用來剔除大量冗余基因，提高樣本預(yù)測(cè)的準(zhǔn)確率。首先采用k-均值聚類算法將基因分成固定數(shù)目的簇，并采用ELM分類器評(píng)價(jià)篩選特征基因，構(gòu)成備選基因庫；然后采用基于CSO和ELM的纏繞法從備選基因庫中選擇同時(shí)具備最大分類準(zhǔn)確率和最小數(shù)目的基因子集。通過與經(jīng)典方法的比較，本文提出的方法能夠以較少的基因獲得更高的分類性能。

k-均值；貓群算法；基因選擇

1　引言

微陣列數(shù)據(jù)的顯著特點(diǎn)是基因維數(shù)大、樣本維數(shù)小。在應(yīng)用微陣列數(shù)據(jù)進(jìn)行分類的過程中，數(shù)據(jù)往往存在大量與分類無關(guān)的冗余基因，因此有必要在分類之前采用基因選擇方法剔除冗余基因。為了克服傳統(tǒng)的基因選擇方法會(huì)選擇大量冗余基因而導(dǎo)致樣本預(yù)測(cè)準(zhǔn)確率下降的缺陷，本文提出一種基于聚類和貓群優(yōu)化（CatSwarmOptimization,CSO）的基因選擇算法。通過對(duì)急性白血病和結(jié)腸癌兩個(gè)微陣列數(shù)據(jù)進(jìn)行基因篩選的實(shí)驗(yàn)結(jié)果可以看出，與其他方法相比較，本文方法能成功選擇較少數(shù)目但有較高分類率的基因子集。

2 　貓群算法

貓群算法[1]是一種基于貓的搜尋行為和跟蹤行為的全局優(yōu)化算法。CSO算法的步驟如下：

Step1：初始化N只貓，每只貓具有D維位置坐標(biāo)值，xi,d代表第ith只貓第dth維的位置坐標(biāo)值。

Step2：為每一維位置隨機(jī)初始化速度Vi,d。

Step3：評(píng)估每一只貓的適應(yīng)函數(shù)值，將具有最優(yōu)適應(yīng)函數(shù)值的貓作為局部最優(yōu)貓Lb。

Step4：根據(jù)MR（定義了貓群中有多少只貓進(jìn)入搜尋模式，多少只貓進(jìn)入跟蹤模式）的大小，貓群被隨機(jī)分配到搜尋模式，或跟蹤模式。

Step5：評(píng)估所有貓將具有最優(yōu)適應(yīng)函數(shù)值的貓極為Lb。

Step6：檢查終止條件，如果不滿足則重復(fù)執(zhí)行Step4和Step5，都則結(jié)束。

3 　判別熵

判別熵[2]是用來表征不同分布間區(qū)別大小的熵函數(shù)。對(duì)于二分類問題，基因微陣列數(shù)據(jù)中某組特征基因在不同類別間的概率密度為w1(xi)與w2(xi)，其差別程度定義為相對(duì)熵V(w1,w2)=-∑w1(xi) log[w1(xi)/w2(xi)]≤0，則判別熵定義為：

4 　基于聚類和貓群優(yōu)化的基因選擇算法

針對(duì)微陣列數(shù)據(jù)具有高維小樣本的特點(diǎn)，本文提出一種基于聚類和貓群優(yōu)化的基因選擇算法。首先對(duì)于相似度高的基因，采用k-均值聚類算法將聚成一簇，然后對(duì)各簇的基因分類性能采用ELM算法進(jìn)行分析，篩選出具有高分類性能簇的基因子集，組成一個(gè)冗余度較低的初始基因庫，最后對(duì)于初始基因庫采用CSO結(jié)合ELM算法找出分類性能最優(yōu)的基因組合。算法步驟如下：

Step1：生成微陣列數(shù)據(jù)訓(xùn)練集和測(cè)試集，按照第3節(jié)計(jì)算各個(gè)基因?qū)Σ煌悇e的判別熵值，并按照絕對(duì)值排序篩選判別熵絕對(duì)值較大的基因構(gòu)成備選基因庫。然后訓(xùn)練集再分為訓(xùn)練集和驗(yàn)證集兩部分。

Step2：采用k-均值聚類算法在訓(xùn)練集上對(duì)選出的基因進(jìn)行聚類，根據(jù)樣本類別特點(diǎn)確定聚類數(shù)目。

Step3：將每簇基因作為一個(gè)搜索空間，以獲取每個(gè)聚類中基因?qū)Ψ诸惖挠绊?。在搜索空間內(nèi)，對(duì)貓的位置和速度進(jìn)行隨機(jī)初始化，一個(gè)基因子集就是一只貓。子基因庫由經(jīng)CSO算法在一個(gè)簇中篩選出的分類性能較高的基因組。

Step4：計(jì)算每個(gè)基因子集的適應(yīng)度值，并根據(jù)ELM分類器在驗(yàn)證集上的準(zhǔn)確率評(píng)價(jià)適應(yīng)度值。全局最優(yōu)解的獲得則通過貓群的位置和速度不斷更新來搜索。

Step5：如果迭代條件沒有滿足，并且沒有達(dá)到最大迭代次數(shù)，則轉(zhuǎn)至Step4。最終的基因子集是驗(yàn)證準(zhǔn)確率最優(yōu)、數(shù)目最小的基因子集。

5 　實(shí)例分析

本文實(shí)驗(yàn)采用Golub等公布的急性白血病數(shù)據(jù)集和Alon等公布的結(jié)腸癌數(shù)據(jù)集兩個(gè)微陣列數(shù)據(jù)集，如表1所示。在實(shí)驗(yàn)中，對(duì)于第一個(gè)數(shù)據(jù)集隨機(jī)劃分為38例訓(xùn)練集和34例測(cè)試集；對(duì)于第二個(gè)數(shù)據(jù)集隨機(jī)劃分為40例訓(xùn)練集和22例測(cè)試集。將本文方法與其他經(jīng)典的基因選擇方法進(jìn)行比較以驗(yàn)證本文基因選擇方法的有效性。采用相關(guān)方法所獲取的最小基因子集及相應(yīng)的最大分類準(zhǔn)確率如表2所示。從表2中可以看出，本文算法對(duì)于白血病數(shù)據(jù)集在達(dá)到100%分類率的情況下，選擇的基因子集數(shù)目最少；在選擇相同數(shù)目的基因子集的情況下，本文算法對(duì)于結(jié)腸癌數(shù)據(jù)集樣本的分類率最高。綜上，與其他方法相比較，采用本文基因選擇方法能夠在選出小冗余基因的同時(shí)保證高的樣本分類率。

表1 　微陣列數(shù)據(jù)集

表2 　數(shù)據(jù)集中結(jié)構(gòu)類的組成

6 　結(jié)語

本文提出一種基于聚類和CSO優(yōu)化的基因選擇算法，以期在進(jìn)行微陣列基因選擇時(shí)，降低基因冗余度。采用k-均值聚類算法將基因分成固定數(shù)目的簇，并采用ELM分類器評(píng)價(jià)篩選特征基因，將基因簇中貢獻(xiàn)大的基因子集組成基因庫，作為CSO的搜索空間。通過實(shí)驗(yàn)可以看出，本文提出的方法能夠以較少的數(shù)目的基因子集獲得較高的分類精度。

[1]孔令平.基于貓群算法的無線傳感器網(wǎng)絡(luò)路由優(yōu)化算法研究[D].哈爾濱工業(yè)大學(xué)碩士學(xué)位論文,2013.

[2]關(guān)健,韓飛,楊善秀.基于粒子群優(yōu)化和判別熵信息的基因選擇算法[J].計(jì)算機(jī)工程,2013,39(11):187-196.

敖培（1979-），女，蒙古族，遼寧省沈陽市人，講師，博士研究生，研究領(lǐng)域?yàn)橹悄苄畔⑻幚怼?/p>

河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目基礎(chǔ)研究計(jì)劃No.13A413506;河南師范大學(xué)青年科學(xué)基金項(xiàng)目No.01116400031。