摘 要： 基因芯片是近年发展起来的生物技术，其数据典型特征是基因数多而样本少，因此必须及时采取有效方法来处理这些以指数级增长的数据。流行学习算法在高维数据方面有着广泛应用，但在基因芯片数据分析的应用还比较少。为了能得到在基因芯片数据分析中更好的处理方法，文章应用三种非线性降维提取海量基因芯片数据的特征，然后利用支持向量机作为分类器，判断样本的类属。实验结果表明，通过LLE特征提取之后，能获得与原基因芯片更为接近的成分，类属判断结果更为准确，为基因芯片数据分析提供了一定的科学指导。
关键词： 基因芯片； 流行学习； 高维数据； 支持向量机； LLE
中图分类号：TP3-05 文献标志码：A 文章编号：1006-8228（2013）11-06-03
0 引言
流行学习是近来发展起来的维数约减算法，在图像处理和指纹识别方面有很好应用。它要求基于非线性的数据结构，这与生物系统的非线性特点相适应。基于流行学习的非线性降维包含两类：①全局方法，包括等距映射算法（ISOMAP）与最大方差展开（MVU）[1-3]；②局部方法，包括局部线性嵌入算法（LLE）、拉普拉斯特征映射算法（LE）和局部切空间排列（LTSA）[1，4]。
基因芯片是崭新的生物学技术，与传统的基因检测技术比较，基因芯片最大特点是能同时定量和定性检测成千上万个基因信息。但对于不断增多的实验数据，若不能及时有效地处理，就会导致“数据资源”变为“数据灾难”。基因芯片数据特点是基因数多而样本数少，即存在维数高、样本少的“维数灾难”问题。所以解决的方法就是通过维数约减。本文主要应用等距映射算法、局部线性嵌入算法和局部切空间排列算法来处理高维基因芯片数据。
我们对基因芯片数据的分析主要通过三个步骤：数据预处理；数据降维；支持向量机分类。我们的主要工作是比较三种基于流行学习的非线性降维在基因表达数据分析中的分类效果。
1 流行学习算法
1.1 局部线性嵌入（LLE）
LLE算法总体由三部分组成，即先找出K个近邻点，再计算出局部重建权值矩阵，最后由局部重建权值矩阵与其近邻点计算出该样本点输出值。具体过程如下。
步骤1 计算出每个样本的K个近邻点。所谓近邻点就是相对所求样本点距离最近的K各样本点，其中，K是一个自己输入的数值。常用的距离主要有欧式距离，但在高维空间数据非线性分布中，欧式距离效果往往没那么显著，这时，可以采用Dijstra距离。这是一种测地距离，它能够保持样本点之间曲面特性，在其他非线性降维算法中也有着广泛的应用。
步骤2 计算局部重建权值矩阵，定义重构误差函数：
M是一个n*n的对称矩阵，M=（I-E）T（I-E）[4-5]。
最优解Y*是由矩阵M最小第d+1个至最小第2个特征值所对应的特征向量组成，因为最小的特征值为零。LLE算法问题归结为稀疏矩阵特征向量求解，计算量相对较小，不过算法不能提供从高维空间到低维空间的投影映射[4-5]。
1.2 等距离映射算法（ISOMAP）
等距离映射算法的重要之处在于两点间距离的测定，测地距离近似计算有两种，一种是样本点xi和它的领域点间的测地距离使用它们之间的欧式距离来替代；另一种是，样本点xi与它领域外的点用它们之间最短路径来替代[3，6]。其计算步骤如下。
步骤1 建立领域关系图G（V，E），根据每个xi（i=1，2，…，n）计算k个近邻记作Nj，根据点xi为顶点，欧氏距离d（xi，xj）为边，建立了邻域关系图G（V，E）。
其中，确定近邻点常用如下两种方法：一是利用ε-近邻方法，考虑点对xi，xj是其近邻点，若；二是利用k-近邻方法，要事先给定k，然后确定其近邻点。
步骤2 计算出测地距离矩阵D（dij）n*m，在邻域关系图G（V，E）寻找最短路径，即
步骤3 在距离矩阵D（dij）n*m运行在古典MDS上，寻找其低维构造点Y={y1，y2，…，yn}[5]。
ISOMAP算法用残差E来衡量降维误差，即E=1-R2（DG，DY），这里DG为距离矩阵，DY是d维空间中欧氏距离矩阵，R2是线性相关系数。一般，降维维数d越高，E就越小。通过E曲线出现拐点或者E已经小到一定阈值就可以来确定降维的维数d[7]。
1.3 局部切空间排列（LTSA）
局部切空间排列是浙江大学张振跃等人在2004年提出的非线性降维方法[8]，LTSA基本思想是采用样本点所在领域的切空间以表示点的领域，并对每一个点建立了领域切空间，而后将这些局部切空间排列起来建立流形的全局坐标。LTSA首先也需要选择各样本点的近邻点[9]。具体计算步骤如下。
步骤1 选取领域
计算每个样本点的领域。记Xp=[xp1，…，xpk]是样本点Xp包含自身在内的最近k个近邻点。
步骤2 局部线性投影
对Xp进行中心化处理，得到，再对进行奇异值分解，即，获得右奇异向量组成的矩阵Vp。
步骤3 局部坐标系统的排列
构造排列矩阵，这里，Wp=I-[lk/，Vp][lk/，Vp]T。计算的最小d+1个特征值所对应的特征向量u2，…，ud+1，T=[u2，…，ud+1]T即为计算的嵌入结果[8，10]。
2 支持向量机（SVM）
支持向量机分类实际上是通过非线性变换将输入空间变换到一个高维空间，然后在这个新空间中求取最优线性分类面，这种非线性变换是通过定义适当的内积函数来实现[11-12]。
为了解决两类不平衡问题，这里需要引入惩罚因子C，当yi=+1类时，0⩽αi⩽C+；当yi=-1时，0⩽αi⩽C-。
内积函数K=（xi，x）也称核函数，目前常用的核函数主要有三种：
⑴ 多项式形式的内积函数，即：
K（x，xi）=[（x·xi）+1]q
这里得到的支持向量机是一个q阶多项式分离器。
⑵ 径向基内积函数
径向基内积函数是普遍使用的核函数，因为它对应的特征空间是无穷维的，有限的数据样本在该特征空间中肯定是线性可分。
⑶ S形函数内积
K（x，xi）=tanh（v（x·xi）+c）
这里，支持向量机实现的是一个两层的多层感知器神经网络[11-12]。
3 实验方法
在基因变量里，存在噪声基因，这些基因对分类意义不大，因此，在进行降维前，需对数据进行预处理，即基因筛选。本文预处理方法采用t值统计方法[13-16]。
其中，与是一类中，同一个基因的平均值，n1与n2是每类的样本数量，s1与s2是类的方差。计算出每个基因的t值，在按照t值大小排序，一般认为，基因排序靠前的对应在一类有较高表达值，而排在后面的对应另一类有较高表达值。我们取出t值较大的与t值较小的基因作数据分析。
本文使用的支持向量机以径向基BRF作为核函数，为了选取一个较好的σ以及惩罚因子参数C，选用5-倍交叉验证方法，得到交叉验证准确率来确定。处理过程如下。
（a） 计算t值统计量，选出前100个t值最大基因和后100个t值最小基因。
（b） 对预处理之后数据，基于流行学习的数据降维分析。
（c） 经降维之后的训练集采用5-倍交叉验证方法，计算出最优的σ与C，构造分类器模型。
（d） 用分类器模型对测试集进行测试，计算识别率。
4 实验结果与分析
本文选用的基因数据来源于Leukemia的组织样本，共有7129个基因。其中，训练集包含38个样本（27个ALL，11个AML），测试集包含34个样本（20个ALL，14个AML）[13]。数据集可以从网站http：//datam.i2r.a-star.edu.sg/datasets/krbd/获得[17]。
通过处理，得到不同特征基因数三种方法识别率比较，如图1所示。
图1表明非线性降维LLE最优识别率比其他两种方法高，在维数2与3时得到最优识别率为97.0588%，34个测试样本有33个被正确识别。等距离映射ISOMAP效果最差，而且各维识别率都较低，在基因表达数据应用并不适合。经过流行学习算法处理与未处理的最优识别率比较如表1所示。
从表1可以看出，经过LLE的降维后，34个测试样本有33个被正确识别，识别率达到97.0588%，也远高于未经任何降维处理的识别率。
从图2可以看出错误划分的样本便是划横线的那个。
5 结束语
本文根据基因芯片数据的特点，把新的基于流行学习的非线性降维算法应用于该数据。通过预处理可以去掉与分类无关的噪声基因，而非线性降维则可以提取特征基因，消除对分类不良影响的冗余特征。通过比较三种算法可知，局部线性嵌入（LLE）的识别率优于其他两种，也高于未经降维处理的数据。面对海量数据的工业应用，LLE可以提高基因芯片数据分析的准确性。
参考文献：
[1] 刘小明.数据降维及分类中的流行学习研究[D].浙江大学博士论文，
2007.
[2] Tenenbaum JB， de Silva V， Langford JC. A global geometric framework for nonlinear dimensionality reduction[J]. Science，2000.290（5500）：2319-2323
[3] M. Balasubramanian and E.L. Schwartz. The Isomap algorithm and topological stability[J].Science，2002.295（5552）：7
[4] S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction bylocally linear embedding[J]. Science，2000.290：2323-2326
[5] 姜伟，杨炳儒.基于流行学习的维数约简算法[J].计算机工程，2010.36（12）：25-27
[6] 肖传乐，曹槐.基于流行学习的基因表达谱数据可视化[J].生物信息学，2009.7（1）：48-51
[7] Peterson L E.Partitioning large-sample microarray-based gene expression profiles using principal components analysis[J]. Comput Methods Programs Biomed，2003.70（2）：107-119
[8] Z. Zhang and H. Zha. Principal manifolds and nonlinear dimensionality reduction via local tangent space alignment[J]. SIAM Journal of Scientific Computing，2004.26（1）：31-338
[9] 李波.基于流行学习的特征提前方法及其应用研究[D].中国科学技术大学博士论文，2008.
[10] 黄启宏.流行学习方法理论研究及图像中的应用[D].电子科技大学博士论文，2007.
[11] 白鹏.支持向量机理论及工程应用实例[M].西安电子科技大学出版社，2008.
[12] 边肇祺.模式识别[M].清华大学出版社，2000.
[13] T. R. Golub， D. K. Slonim. Molecular Classification of Cancer： Class Discovery and Class Prediction by Gene Expression Monitoring [J].Science，1999.286（15）：531-535
[14] 胡煜.降维方法与有监督分类在基因芯片数据分析中的应用比较[D].中山大学硕士论文，2007.
[15] 高利宏，曹佳.基因芯片可靠性分析及数据处理[J].第三军医大学学报，2006.28（1）：80-82
[16] 刘春菊，刘自伟.基因表达数据在数据库中的预处理[J].电脑知识与技术，2009.5（16）：4101-4105
[17] Kent Ridge Bio-medical Dataset[EB/OL]. http：//datam.i2r.a-star.edu.sg/datasets/krbd/