程璐+李欣+王薇+邓佳颖+邢阳阳

摘要：文章在分析两种基因数据分析技术的基础上，提出一种基于K-S检验与Relief特征选择算法相结合的基因识别方法。首先采用K-S检验选择出具有一定区分能力的基因，然后利用Relief算法对筛选出来的基因子集进行特征选择，将该方法分别与K-S检验、Relief算法进行对比，以验证该算法的可行性。

关键词：基因数据；K-S检验；Relief基因特征选择算法；分类精度

适合度检验法（Kolmogorov-Smirnov，K-S）是一种常用的非参数统计方法，对两类样本的分布形状差异很敏感，主要用于比较两类样本是否同分布。Relief根据特征评估近距离样本的区分能力特征，简单易用并能取得良好的特征选择效果，但是该特征选择方法在搜索时不能处理冗余特征的问题，本文将K-S检验与Relief算法相结合，提出一种基于K-S检验的Relief基因特征选择方法，通过K-S检验过滤掉大部分冗余和噪声基因，保留具有显著区分能力的基因，有效增强了种群基因的多样性；再通过Relief算法对这些基因进行特征选择，避免粒子搜索时不考虑特征之间的相关性而陷入局部最优，从而获得较高的分类准确度，快速获得最优特征子集，最后将该方法分别与K-S检验、Relief算法进行对比。

1 相关知识1.1K-S检验算法

K-S检验基于累积分布函数，是一种典型的非参数检验方法，用以检验一个累积分布是否符合某种理论分布，或者比较两个累积分布是否存在显著性差异。本文利用K-S检验判断肿瘤患者与正常人的各基因是否存在显著差异。

数据中包含正类和负类两组独立的样本，对基因数据集的特征值进行降序排列，取其中某个正类基因X，其观测值为基因数据集的样本数，从而得到次序观测值…，则基因的累积分布函数定义见式⑴。

根据公式（1）计算出正类样本的累积分布函数巧w与负类样本的累积分布函数，则K-S检验统计量T见式（2）。

是在显著性水平下样本统计量的临界值，当得到的样本统计量r大于或等于^寸，认为在置信水平下，该基因在正类与负类中存在显著性差异；反之，没有显著性差异。

1.2 Relief特征选择算法

Relief是由Kira和Rendell年提出的一种著名的多变量过滤式特征选择算法，它也是一种基于样本学习的特征权重计算算法。Relief算法作为目前应用广泛的特征评估算法之一，是一种经典的过滤式特征选择算法，基于实例的非线性特征，为特征空间中的每维特征赋予一个权值，以权值表征特征与类别的相关程度。

从待选择的基因数据集中随机选择〖个基因样本，根据欧氏距离找出每个所选择的样本在其同类基因样本中的最近邻点和在其非同类基因样本中的最近邻点。

设基因样本空间中两个输入样本向量分别为'和；则其欧氏距离为：

假设候选特征变量有//个，待选择的基因样本有其中第w个特征的权值%通过多次迭代得到，通过公式（4）计算每个属性的权值，最后，筛选出权值较大的特征作为最终结果。

2 基于K-S检验的Relief基因特征选择算法

针对上述算法中存在的部分缺点，本文结合K-S检验算法和ReUe償法提出了一种新的基因特征选择算法，假设基因数据集的样本数为凡特征数为&本文算法的具体实现步骤如下。

（1）将待检测的正类样本和负类样本的y个特征值代入累积分布函数中，分别得出正类与负类的累积分布函数值和恳W（2）根据式（2）计算出基因Z的K-S检验统计

量，并与alpha对应的基因临界值rei.it进行对比，筛选出大于该临界值且具有显著区分能力的基因构成预选择基因子集A；（3）对基因子集A进行表达谱数据归一化；⑷依据公式

（4）求出每个基因的权重向量，并利用MATLAB作出基因分类权重散点图和基因分类权重的柱图；（5）设定基因权重阈值和相关系数阈值；（6）对选出的权重较大基因进行两两冗余分析，去掉冗余基因。

3 实验结果与分析3.1实验数据

为了阐明本文提出的算法是有效的，在前列腺癌（Prostate）、白血病（Leukemia）和肺癌（Lung）数据集上进行试验，该数据集来自于http：//bioinformatics.rutgers.ed/Static/Supplemens/CompCancer/datasets.htm上的公开数据集。实验中使用的计算机系统为WindowslO，64位操作系统、内存为8GB、处理器为；。所有实验都是在MatlabR2016b和weka3.9.0中实现的。

3.2 K-S算法、Relief算法与基于K-S检验的Relief基因特征选择算法对比

利用3个数据集：Prostate，Leukemia和Lung进行实验，

基于K-S检验的Relief基因特征选择算法对基因数据集的特征选择能力明显优于K-S算法。在Prostate基因数据中，首先使用K-S检验算法剔除无关基因进行粗提取，再利用Relief算法进行特征选择，对比只使用K-S算法的结果发现，基因数据集Prostate中，共有54个样本、12600基因特征值，通过K-S检验进行粗提取，从中筛选12437个特征值，只剔除了原来基因总数的1.293%，没有考虑到基因的相关性；而通过基于K-S的Relief算法对K-S检验过后的基因进行特征选择，从中筛选出了5个特征值，其基因权重阈值设为4000，相关系数阈值设为0.9，筛选率高达99.96%，并在怀卡托智能分析环境下对分类结果进行检测，发现其分类准确率达到98.5714%。以此类比，分别得出Leukemia和Lung的筛选结果，再结合图像对比3组数据的分类精度值得出实验结论：K-SReliefX寸基因的特征提取效果优于K-S检验。

3.3 特征选择算法的对比

为了进一步验证基于K-S检验的Relief特征选择算法的适用性，实验分别采用了以F-sore作为评价准则的Filter操作，与SVM-RFE方法进行了分类准确度对比，通过分类精度来评价选择方法的优劣，Leukemia在F+SVMRFE方法下分类精度为81.8%，而在基于K-S检验的Relief特征选择算法下分类精度为87.024%，选择结果更优。

4 结语

本文提出了一种基于K-S检验的Relief基因特征选择算法，重新构造了基因识别的方法。将粗提取与特征选择相结合，使得在面对大量基因数据集时的处理方法更加简便，得出的分类结果更加精确。利用Lung，Prostate，Leukemia3个基因数据集进行实验，将该实验结果与只进行K-S检验和Rdief基因特征选择算法的两个实验结果进行对比，实验结果均表明改进算法优于原算法，从而验证了改进算法的有效性。

[参考文献]

[1]李萍.基于基因表达数据的胃癌特征基因选取研究[D].北京：北京工业大学，2009.

[2]谢娟英，胡秋锋，董亞非.K-S检验与mRMR相结合的基因选择算法[J].计算机应用研究，2016（4）：1001-3695.

[3]杨昆.基因表达数据分析和处理关键技术[D].哈尔滨：哈尔滨工业大学，2008.

[4]李萍.基于基因表达数据的胃癌特征基因选取研究[D].北京：北京工业大学，2009.endprint