基于聚類和貓群優化的基因選擇算法

敖　培,李　賀,李　明,楊百順,李延強（.河南師范大學計算機與信息工程學院；.河南師范大學軟件學院；. 河南師范大學政治與公共管理學院,河南 新鄉 45007）

基于聚類和貓群優化的基因選擇算法

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

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

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

1　引言

微陣列數據的顯著特點是基因維數大、樣本維數小。在應用微陣列數據進行分類的過程中，數據往往存在大量與分類無關的冗余基因，因此有必要在分類之前采用基因選擇方法剔除冗余基因。為了克服傳統的基因選擇方法會選擇大量冗余基因而導致樣本預測準確率下降的缺陷，本文提出一種基于聚類和貓群優化（CatSwarmOptimization,CSO）的基因選擇算法。通過對急性白血病和結腸癌兩個微陣列數據進行基因篩選的實驗結果可以看出，與其他方法相比較，本文方法能成功選擇較少數目但有較高分類率的基因子集。

2 　貓群算法

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

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

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

Step3：評估每一只貓的適應函數值，將具有最優適應函數值的貓作為局部最優貓Lb。

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

Step5：評估所有貓將具有最優適應函數值的貓極為Lb。

Step6：檢查終止條件，如果不滿足則重復執行Step4和Step5，都則結束。

3 　判別熵

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

4 　基于聚類和貓群優化的基因選擇算法

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

Step1：生成微陣列數據訓練集和測試集，按照第3節計算各個基因對不同類別的判別熵值，并按照絕對值排序篩選判別熵絕對值較大的基因構成備選基因庫。然后訓練集再分為訓練集和驗證集兩部分。

Step2：采用k-均值聚類算法在訓練集上對選出的基因進行聚類，根據樣本類別特點確定聚類數目。

Step3：將每簇基因作為一個搜索空間，以獲取每個聚類中基因對分類的影響。在搜索空間內，對貓的位置和速度進行隨機初始化，一個基因子集就是一只貓。子基因庫由經CSO算法在一個簇中篩選出的分類性能較高的基因組。

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

Step5：如果迭代條件沒有滿足，并且沒有達到最大迭代次數，則轉至Step4。最終的基因子集是驗證準確率最優、數目最小的基因子集。

5 　實例分析

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

表1 　微陣列數據集

表2 　數據集中結構類的組成

6 　結語

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

[1]孔令平.基于貓群算法的無線傳感器網絡路由優化算法研究[D].哈爾濱工業大學碩士學位論文,2013.

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

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

河南省教育廳科學技術研究重點項目基礎研究計劃No.13A413506;河南師范大學青年科學基金項目No.01116400031。