一種有效的DNA微陣列數據特征基因提取方法

魏峻

摘 要： 對于癌癥分類來說，最重要的一個問題就是識別出對癌癥分類最有貢獻的基因。提出一種新的特征基因選擇方法（ReliefF_DE），選取了4個公共微陣列基因數據集進行仿真實驗，實驗結果表明該方法可以在較少的特征基因下取得較高精度，且所選的特征基因與癌癥密切相關，進一步驗證了方法的可行性和有效性。

關鍵詞： DNA微陣列； 支持向量機； 特征基因； 特征選取

中圖分類號： TN911.7?34； TP18 文獻標識碼： A 文章編號： 1004?373X（2014）13?0095?04

Method of effective DNA microarray data feature extraction

WEI Jun

（College of Mthematics and Computer Science， Shaanxi University of Technology， Hanzhong 723000， China）

Abstract： As for cancer classification， it is important to identify the genes contributing to cancer classification. A new feature gene selection method （ReliefF_DE） is presented in this paper. Four public microarray gene data sets were selected to carry on the simulation experiment. The experimental results show that the method can achieve high identification accuracy in the case of a few feature genes， and the selected feature genes are closely related to cancers. The feasibility and effectiveness of the method were verified further.

Keywords： DNA microarray； support vector machine； feature gene； feature extraction

0 引 言

微陣列數據[1]廣泛而成功地應用于生物醫學的癌癥分類研究。一個典型的微陣列數據集包含大量（通常成千上萬，甚至數十萬）的基因和相對較少（往往少于一百）的樣本。在這成千上萬的基因中，只有一小部分基因有助于癌癥分類。因此，對于癌癥的分類，如何找到對于樣本分類來說起決定性作用的一組基因作為樣本的分類特征基因，是建立一個有效分類模型的關鍵所在，同時也是發現腫瘤分類與分型的基因標記物及藥物治療潛在靶點的重要手段。

鑒于特征基因的選取在腫瘤分類中的重要作用，研究者們針對該問題提出了大量研究方案[2?6]。本文在分析腫瘤基因表達譜特征的基礎上，提出了基于ReliefF_DE的基因特征選擇方法。首先采用ReliefF算法計算每個基因與分類屬性的相關性，并進行降序排列，取[N]個關聯性較大的基因作為候選基因子集；再使用差分進化算法對候選基因子集進行特征基因選擇。本文選取了4個公共微陣列基因數據集進行仿真實驗，實驗結果表明，本文算法不僅可以在特征屬性的選擇上剔除了大量的冗余屬性，而且分類精度有較大的提高。

1 ReliefF算法

1992年Kira和Rendell首先提出Relief算法[7]，算法首先對隨機選擇的[m]個樣本的假設間隔進行計算，然后將計算結果累加起來作為屬性的權值，最后根據屬性權值的大小就可以近似地估計出對于分類最有用的特征子集。

假設間隔定義為在保持樣本分類不變的情況下決策面能夠移動的最大距離，可表示為：

[θ=12x-M（x）-x-H（x）] （1）

式中：[H（x），][M（x）]分別是與[x]同類和非同類最近鄰點。

樣本[x]更新屬性[p]的權值可表示為：

[Wi+1p=Wip-diff（p，x，H（x））m+diff（p，x，M（x））m] （2）

最初，Relief算法主要針對兩類問題。于是1994年Kononenko對Relief算法進行了改進[8]，提出ReliefF算法。算法的思想是將分類問題視為一類對多類關系加以解決，使算法可以解決多類問題和回歸問題。其改進主要是在權值更新上，權值更新公式為：

[Wi+1p=Wip-j=1kdiff（p，x，Hj（x））m×k+C≠class（x）P（C）1-P（class（x））i=1kdiff（p，x，Mj（x））m×k] （3）

ReliefF算法的基本步驟：從訓練樣本集中隨機抽取出一個樣本[x]；從與[x]同類的樣本集中找出樣本[x]的[k]個近鄰樣本；從與[x]每個不同類的樣本集中找出[k]個近鄰樣本；根據式（3）更新每個特征的權值。

ReliefF算法的優點：運行效率高、多類型問題處理、特征間的關系不敏感。缺點：不能很好地處理冗余特征，對與類別相關性高的特征都賦予較高的權值，而不考慮它們之間是否存在冗余特征。

2 差分進化算法

差分進化算法（Differential Evolution，DE）[9?10]是基于群體搜索的啟發式算法，通過種群內個體間的合作與競爭來實現對優化問題的求解。算法的基本步驟[11?12]如下：

（1） 初始化種群

初始種群[x0i=xLi+rand（0，1）×（xUi-xLi），][i=1，2，…，NP。]其中[x0i]表示種群中第[0]代的第[i]條“染色體”（或個體），[NP]表示種群的大小，[rand（0，1）]表示在[（0，1）]區間均勻分布的隨機數。

（2） 變異操作

從種群中隨機選擇4個不同個體生成差分矢量對每代最優個體進行變異操作，這樣既能提高算法的收斂速度，又能在一定程度上保持較高的種群多樣性。

變異操作方式為：

[vg+1i=xg+1best+k[（xg+1s1-xg+1s2）+（xg+1s3-xg+1s4）]] （4）

式中：[vg+1i]是對每一個[g] 代個體 [xgi] 利用式（4）進行變異操作而得到的變異個體；[xg+1best]是[g+1]中的最優個體；[g]是當前代；[s1，s2，s3，s4∈1，2，…，N] 是互不相同與[i]不同的隨機數；[k∈0，1.5]為縮放因子，對差分量進行放大和縮小控制。

（3） 交叉操作

為了提高種群的多樣性，交叉操作方式為：

[yg+1i=vg+1i，j，rand（j）≤CRxgi，j，rand（j）>CR] （5）

式中：[yg+1i]是利用式（5）對[xgi]和由式（4）生成的變異個體進行交叉操作而得到的試驗個體；[rand（j）]是[[0，1]]之間的均勻分布隨機數；[CR∈[0，1]]為交叉概率。[CR]越大，[vg+1i]對[yg+1i]的貢獻越多，當[CR=1]時，[vg+1i=yg+1i，]有利于局部搜索和加速收斂速率；[CR]越小，[xgi]對[yg+1i]的貢獻越多，當[CR=0]時，[xgi=yg+1i]有利于保持種群的多樣性和全局搜索能力。

（4） 選擇操作

采用“貪婪”搜索策略，經過變異和交叉操作后生成的試驗個體[yg+1i]與[xgi]進行競爭。只有當[yg+1i]的適應度比[xgi]更優時才被選作子代；否則，[xgi]直接將作為子代。

選擇操作方式為：

[xg+1i=yg+1i，f（yg+1i）

式中[f]為目標函數。

DE算法具有如下優點：算法通用，不依賴于問題信息；算法原理簡單，容易實現；群體搜索，具有記憶個體最優解的能力；協同搜索，具有利用個體局部信息和群體全局信息指導算法進一步搜索的能力；易于與其他算法混合，構造出具有更優性能的算法。

3 基于ReliefF_DE的基因特征選擇方法

支持向量機[13?14]（Support Vector Machine，SVM）是以結構風險最小為原則的一種機器學習算法，在研究小樣本、高維性的問題中具有突出的優勢，因此本文使用SVM作為分類器。

本文算法的具體步驟為：

步驟1：數據的標準化處理。

利用[x*=x-xminxmax-xmin]對數據進行標準化處理，消除量綱等的影響。

步驟2：基于ReliefF算法的基因初選。

采用ReliefF算法計算每個基因與分類屬性的相關性，并進行降序排列，取[N]個關聯性較大的基因作為候選基因子集。

步驟3：基于DE算法的特征基因選擇。

（1） 設置參數：種群的大小NP；變量的維數[D；]放大因子[F；]交叉概率CR；迭代次數[T；]

（2） 初始化種群：[t=0，]利用[xti=round（rand（1，D））]，[（i=1，2，…，NP）]隨機產生NP個長度為[D]由0、1組成的向量。其中向量中的‘1代表該位置對應的基因被選擇，‘0代表該位置對應的基因不被選擇；

（3） 計算當前種群中個體適應度：根據[xti]生成對應的訓練子集和測試子集，利用支持向量機進行訓練測試，把在測試集上的分類精度作為這個個體的適應度值[fti=f（xti）；]

（4） 利用式（4）進行變異操作，產生變異個體[vg+1i]；

（5） 利用式（5）進行交叉操作，產生交叉個體[yg+1i]；

（6） 利用式（6）進行選擇操作，產生新一代種群；

（7） 判斷算法是若達到最大迭代次數或達到誤差要求，若達到終止條件則輸出最優個體；否則回到步驟（3）繼續執行。

4 仿真實驗

4.1 實驗數據

為了驗證本文算法的有效性和實用性，選取了4個公共微陣列基因數據集進行仿真實驗。數據集描述具體見表1。

4.2 實驗結果及分析

相關參數設置：ReliefF算法中參數[k=5]（近鄰樣本個數）；DE算法中參數[T=500]（最大迭代次數），[NP=15]（種群大小），[F=1]（放大因子），CR=0.5（交叉概率）。

（1） 實驗1：利用ReliefF算法所獲得的基因個數對分類精度的影響

圖1顯示了排序靠前的基因個數與分類精度之間的關系。可以清楚的看到，分類精度并沒有隨著基因個數的增加而提高，而是在上升到一定分類精度后隨著基因個數的增加反而下降很快，這說明冗余基因對分類精度的影響很大，對分類有重要貢獻的只是一少部分基因。

（2） 實驗2：本文算法的性能比較

圖2分別顯示了利用本文算法的迭代過程。從圖上清楚的看到，4個數據集均在500次迭代以內，算法達到收斂，并獲得了SVM分類的最優適應度值及其對應的最優個體。

表2給出了本文算法的實驗結果。

圖1 排序靠前的基因個數與分類精度之間的關系

數據集Leukemia1的屬性個數從4 606個減少到11個，而分類精度從48%提高到100%；數據集Leukemia2的屬性個數從7 129個減少到10個，而分類精度從55.8%提高到100%；數據集MLLLeukemia的屬性個數從12 582個減少到33個，而分類精度從68.8%提高到100%；數據集ALL的屬性個數從12 625個減少到41個，而分類精度從68%提高到98%。這說明，本文算法不僅在分類精度有較大的提高，而且在特征屬性的選擇上剔除了大量的冗余屬性。

圖2 本文算法的迭代過程

所以本文算法對基因屬性的特征選擇是有效的，所獲得的最優個體能較大的提高分類精度和減少屬性的個數。

5 結 論

針對DNA微陣列基因表達數據樣本小、維數高的特點，本文提出了基于ReliefF_DE的微陣列基因特征提出的算法。實驗表明，本文算法不僅可以在特征屬性的選擇上剔除了大量的冗余屬性，而且分類精度有較大的提高。說明本文算法具有一定的實用性，值得進一步的理論研究。

參考文獻

[1] SCHENA M. Quantitative monitoring of gene expression patterns with a DNA microarray [J]. Science， 1995， 270（5235） ： 467?470.

[2] 李凌波，張靜，陳丹.基于SVM和平均影響值的人腫瘤信息基因提取[J].生物信息學，2013（1）：72?78.

[3] 李建更，李輝，阮曉鋼.一種有效的腫瘤特征基因篩選方法[J].中南大學學報：自然科學版，2013（z2）：284?288.

[4] 秦傳東，劉三陽，張市芳.一種腫瘤基因的支持向量機提取方法[J].西安電子科技大學學報，2012（1）：191?196.

[5] 張靖，胡學鋼，張玉紅，等.K?split Lasso：有效的腫瘤特征基因選擇方法[J].計算機科學與探索，2012（12）：1136?1143.

[6] 于彬，張巖.基于GA?SVM方法的結腸癌基因表達譜數據分析[J].青島科技大學學報：自然科學版，2012（6）：587?592.

[7] KIRA K，RENDELL L A. The feature selection problem： traditional methods and a new algorithm [C]// Proceedings of the 10th National Conference on Artificial Intelligence. Cambridge， MA： The MIT Press， 1992： 129?134.

[8] KONONENKO I. Estimation attributes： analysis and extensions of RELIEF [C]// Proceedings of the 1994 European Conference on Machine Learning. [S. l.]： ACM Press， 1997： 273?324.

[9] STORN R， PDEE K. Differential evolution： a simple and efficient heuristie for global optimization over continuous spaees [J]. Joumal of Global Optsmization， 1997， 11（4）： 341?359.

[10] STORN R， PRICE K. Differential evolution： a simple and efficient adaptive seheme for global optimization over continuous spaees，TR?95?012 [R]. Berkeley， USA： International Computer Seienee Institute， University of California， 1995.

[11] 陳濤.基于DE?SVM非線性組合預測模型的研究[J].計算機工程與應用，2011（13）：33?36.

[12] 陳濤.基于差分進化算法的支持向量回歸機參數優化[J].計算機仿真，2011（6）：198?201.

[13] VAPNIK V N. The nature of statistical learning theory [M]. New York： Springer?Verlag Inc， 1995.

[14] CRISTIANINI N， SHAWE?TAYLOR J. An introduction to support vector machines [M]. Cambridge： Cambridge University Press， 2000.

數據集Leukemia1的屬性個數從4 606個減少到11個，而分類精度從48%提高到100%；數據集Leukemia2的屬性個數從7 129個減少到10個，而分類精度從55.8%提高到100%；數據集MLLLeukemia的屬性個數從12 582個減少到33個，而分類精度從68.8%提高到100%；數據集ALL的屬性個數從12 625個減少到41個，而分類精度從68%提高到98%。這說明，本文算法不僅在分類精度有較大的提高，而且在特征屬性的選擇上剔除了大量的冗余屬性。

圖2 本文算法的迭代過程

所以本文算法對基因屬性的特征選擇是有效的，所獲得的最優個體能較大的提高分類精度和減少屬性的個數。

5 結 論

針對DNA微陣列基因表達數據樣本小、維數高的特點，本文提出了基于ReliefF_DE的微陣列基因特征提出的算法。實驗表明，本文算法不僅可以在特征屬性的選擇上剔除了大量的冗余屬性，而且分類精度有較大的提高。說明本文算法具有一定的實用性，值得進一步的理論研究。

參考文獻

[1] SCHENA M. Quantitative monitoring of gene expression patterns with a DNA microarray [J]. Science， 1995， 270（5235） ： 467?470.

[2] 李凌波，張靜，陳丹.基于SVM和平均影響值的人腫瘤信息基因提取[J].生物信息學，2013（1）：72?78.

[3] 李建更，李輝，阮曉鋼.一種有效的腫瘤特征基因篩選方法[J].中南大學學報：自然科學版，2013（z2）：284?288.

[4] 秦傳東，劉三陽，張市芳.一種腫瘤基因的支持向量機提取方法[J].西安電子科技大學學報，2012（1）：191?196.

[5] 張靖，胡學鋼，張玉紅，等.K?split Lasso：有效的腫瘤特征基因選擇方法[J].計算機科學與探索，2012（12）：1136?1143.

[6] 于彬，張巖.基于GA?SVM方法的結腸癌基因表達譜數據分析[J].青島科技大學學報：自然科學版，2012（6）：587?592.

[7] KIRA K，RENDELL L A. The feature selection problem： traditional methods and a new algorithm [C]// Proceedings of the 10th National Conference on Artificial Intelligence. Cambridge， MA： The MIT Press， 1992： 129?134.

[8] KONONENKO I. Estimation attributes： analysis and extensions of RELIEF [C]// Proceedings of the 1994 European Conference on Machine Learning. [S. l.]： ACM Press， 1997： 273?324.

[9] STORN R， PDEE K. Differential evolution： a simple and efficient heuristie for global optimization over continuous spaees [J]. Joumal of Global Optsmization， 1997， 11（4）： 341?359.

[10] STORN R， PRICE K. Differential evolution： a simple and efficient adaptive seheme for global optimization over continuous spaees，TR?95?012 [R]. Berkeley， USA： International Computer Seienee Institute， University of California， 1995.

[11] 陳濤.基于DE?SVM非線性組合預測模型的研究[J].計算機工程與應用，2011（13）：33?36.

[12] 陳濤.基于差分進化算法的支持向量回歸機參數優化[J].計算機仿真，2011（6）：198?201.

[13] VAPNIK V N. The nature of statistical learning theory [M]. New York： Springer?Verlag Inc， 1995.

[14] CRISTIANINI N， SHAWE?TAYLOR J. An introduction to support vector machines [M]. Cambridge： Cambridge University Press， 2000.

數據集Leukemia1的屬性個數從4 606個減少到11個，而分類精度從48%提高到100%；數據集Leukemia2的屬性個數從7 129個減少到10個，而分類精度從55.8%提高到100%；數據集MLLLeukemia的屬性個數從12 582個減少到33個，而分類精度從68.8%提高到100%；數據集ALL的屬性個數從12 625個減少到41個，而分類精度從68%提高到98%。這說明，本文算法不僅在分類精度有較大的提高，而且在特征屬性的選擇上剔除了大量的冗余屬性。

圖2 本文算法的迭代過程

所以本文算法對基因屬性的特征選擇是有效的，所獲得的最優個體能較大的提高分類精度和減少屬性的個數。

5 結 論

針對DNA微陣列基因表達數據樣本小、維數高的特點，本文提出了基于ReliefF_DE的微陣列基因特征提出的算法。實驗表明，本文算法不僅可以在特征屬性的選擇上剔除了大量的冗余屬性，而且分類精度有較大的提高。說明本文算法具有一定的實用性，值得進一步的理論研究。

參考文獻

[1] SCHENA M. Quantitative monitoring of gene expression patterns with a DNA microarray [J]. Science， 1995， 270（5235） ： 467?470.

[2] 李凌波，張靜，陳丹.基于SVM和平均影響值的人腫瘤信息基因提取[J].生物信息學，2013（1）：72?78.

[3] 李建更，李輝，阮曉鋼.一種有效的腫瘤特征基因篩選方法[J].中南大學學報：自然科學版，2013（z2）：284?288.

[4] 秦傳東，劉三陽，張市芳.一種腫瘤基因的支持向量機提取方法[J].西安電子科技大學學報，2012（1）：191?196.

[5] 張靖，胡學鋼，張玉紅，等.K?split Lasso：有效的腫瘤特征基因選擇方法[J].計算機科學與探索，2012（12）：1136?1143.

[6] 于彬，張巖.基于GA?SVM方法的結腸癌基因表達譜數據分析[J].青島科技大學學報：自然科學版，2012（6）：587?592.

[7] KIRA K，RENDELL L A. The feature selection problem： traditional methods and a new algorithm [C]// Proceedings of the 10th National Conference on Artificial Intelligence. Cambridge， MA： The MIT Press， 1992： 129?134.

[8] KONONENKO I. Estimation attributes： analysis and extensions of RELIEF [C]// Proceedings of the 1994 European Conference on Machine Learning. [S. l.]： ACM Press， 1997： 273?324.

[9] STORN R， PDEE K. Differential evolution： a simple and efficient heuristie for global optimization over continuous spaees [J]. Joumal of Global Optsmization， 1997， 11（4）： 341?359.

[10] STORN R， PRICE K. Differential evolution： a simple and efficient adaptive seheme for global optimization over continuous spaees，TR?95?012 [R]. Berkeley， USA： International Computer Seienee Institute， University of California， 1995.

[11] 陳濤.基于DE?SVM非線性組合預測模型的研究[J].計算機工程與應用，2011（13）：33?36.

[12] 陳濤.基于差分進化算法的支持向量回歸機參數優化[J].計算機仿真，2011（6）：198?201.

[13] VAPNIK V N. The nature of statistical learning theory [M]. New York： Springer?Verlag Inc， 1995.

[14] CRISTIANINI N， SHAWE?TAYLOR J. An introduction to support vector machines [M]. Cambridge： Cambridge University Press， 2000.