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

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

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

本文提出一種基于聚類和貓群優(yōu)化基因選擇算法，用來剔除大量冗余基因，提高樣本預(yù)測的準(zhǔn)確率。首先采用k-均值聚類算法將基因分成固定數(shù)目的簇，并采用ELM分類器評價篩選特征基因，構(gòu)成備選基因庫；然后采用基于CSO和ELM的纏繞法從備選基因庫中選擇同時具備最大分類準(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)的基因選擇方法會選擇大量冗余基因而導(dǎo)致樣本預(yù)測準(zhǔn)確率下降的缺陷，本文提出一種基于聚類和貓群優(yōu)化（CatSwarmOptimization,CSO）的基因選擇算法。通過對急性白血病和結(jié)腸癌兩個微陣列數(shù)據(jù)進(jìn)行基因篩選的實驗結(jié)果可以看出，與其他方法相比較，本文方法能成功選擇較少數(shù)目但有較高分類率的基因子集。

2 　貓群算法

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

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

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

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

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

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

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

3 　判別熵

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

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

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

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

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

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

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

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

5 　實例分析

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

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

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

6 　結(jié)語

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

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

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

敖培（1979-），女，蒙古族，遼寧省沈陽市人，講師，博士研究生，研究領(lǐng)域為智能信息處理。

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