一种有效的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.