中国科技论文在线 http://www.paper.edu.cn 基于肿瘤基因表达数据的一种新的组合降 维方法# 李建更，逄泽楠，苏磊* 5 10 15 20 25 30 35 （北京工业大学电子信息与控制工程学院，北京 100124） 摘要：本文提出了一种新的组合降维方法，叫做 PLF(PCA+LLRFC)，它可以对肿瘤基因进 行降维以达到良好的分类效果。事实上，基因表达数据集一般是高维的，它的数据结构不仅 是线性的而且还有非线性的。因此，基因表达数据里一定存在了很多的冗余信息，除此之外， 在处理有不同标签信息的数据集时，局部线性嵌入算法(LLE)往往由于没有将类别信息考虑 进去而达不到良好的特征提取效果。为了解决以上问题，我们提出了一种新的组合方法 PLF，。PLF 是将主成分分析方法（PCA）与基于 Fisher 准则的局部线性嵌入算法（LLRFC） 结合起来。新的方法不仅可以将类别信息考虑进去，而且可以降低大量的计算量以节省时间。 最后 SRBCT 数据集被应用到我们的方法中来说明可行性，并用支持向量机（SVM）进行分 类说明其有效性。 关键词：主成分分析算法；局部线性嵌入算法；基因表达数据 中图分类号：U 461; TP 308 A Novel Combined Dimension Reduction Method Based on Gene Expression Data LI Jiangeng, PANG Zenan, SU Lei (College of Electronic Information and Control Engineering, Beijing University of Technology, Beijing 100124) Abstract: In this paper a novel combined dimension reduction method is proposed, namely PLF (PCA+LLRFC), which is proposed to reduce the dimension of gene expression data for tumor classification. In fact, the gene expression data set is high-dimensional data set, a mixture set with linear and nonlinear structures. A lot of redundant information is bound to exist. Besides, in face with data set in different classes, the manifold learning method LLE is also not efficiently extract features for classification due to not take the label information into account. To solve above problems, PLF is proposed. PLF is combined by Principle Component Analysis (PCA) and Locally Linear Embedding Representation Fisher Criterion (LLRFC). The novel method can take class information into account and reduce the amount of computations. Two well-known microarray datasets (obtained from http://www.gems-system.org) are used by PLF to demonstrate the feasibility. The effectiveness of PLF is evaluated by the classification accuracy of SVM classifier. Key words: PCA; LLE; Gene Expression Data 0 引言 随着 DNA 微阵列技术的发展，我们可以获得越来越多的肿瘤基因表达数据。通常，从 40 微阵列实验中获得的基因表达数据是有很多的特征基因于很少不同的样本组成的高维数据 集，怎样在高维的数据集里有效的分析、挖掘和发现有意义的信息已经变成一个很严峻的课 题。 基金项目：国家科技重大专项资助项目(2011BAC12B0304);北京市教育委员会科技计划项目 （JC002011200903） 作者简介：李建更（1965- ），男，教授，主要研究对象模式识别、生物信息学、自动化、计算机方面的 研究. E-mail: jiangengli@gmail.com - 1 - 

中国科技论文在线 http://www.paper.edu.cn 数据降维方法是试图降低数据集的复杂度和保存低维的数据可以代表高维数据。在线性 降维算法里，作为传统的特征提取方法主成分分析（PCA）[1]可以有效地处理高维线性数据。 它通过找到一个可以获取到主成分向量的相互正交基函数和保存前面的主成分向量，然 而，由于缺少后面的主成分向量，将会造成缺少在高维数据的非线性信息。流行学习算法[2] 是一个很好地数据挖掘工具，它可以很好地发现高维数据集的结构，最终对数据有很好地解 释。局部线性嵌入算法（LLE）[3]在流形学习里是表现最优秀的特征提取算法，而且等距特 征映射算法（ISOMAP）[4]是表现的其次最好的降维方法。局部线性嵌入算法可以通过保存 局部的邻域信息来挖掘非线性流形的全局结构，然后把局部邻域信息投影到低维空间。但是， 相关研究[5]已经很好地解释了 LLE 是个无监督的流形学习算法，不能充分利用到数据的类 别信息。现在的研究[6]已经在将类别信息应用到传统的 LLE 中有很多尝试，而且与传统的 LLE 相比有表现了很好地特征提取能力。 Li.等[7]提出判别流形方法，叫做 LLRFC。它是基于 Fisher 准则利用 LLE 求解类内与类 外图。但是，这个方法存在大量的计算量，要求的计算机设备配置比较高，并且不能排除大 量的冗余信息，为了解决这些问题，我们提出了一个新的组合降维方法，叫做 PLF，可以作 45 50 55 为一个新的特征提出方法进行数据分析和在分类模型。 1 基于 Fisher 准则的局部线性嵌入算法 处理具有不同类别的基因表达数据集时，局部线性嵌入算法总是由于没有考虑到类别信 60 息而不能有效的提取特征基因致使分类效果不佳。因此，有必要对局部线性嵌入算法进行改 进，既要保存在流形结构上的邻域信息又要在降维过程中考虑到类别信息。 假设一组数据集 ，让 表示在 类内的 个数据样本。局部线性嵌入 算法可以计算在相同标签和不同标签下样本点的最近邻域和最优重构权，因此按照如下建立 类内图和类外图： 65 1、类内图 可以通过排序欧式距离，让相同标签的样本点尽可能相邻，让不同标签的样本点尽可能 远离，这样类内样本点的重构权可以按如下公式构建： (1) 这里,样本点 是在相同类 下的 的近邻。 70 2、类外图 可以通过排序欧氏距离，让相同标签的样本点尽可能远离，让不同标签的样本点尽可能 相邻，这样类外样本点的重构权可以按如下公式构建： (2) 这里，样本点 是样本点 的近邻， 、 分别是类 、 下的样本点。 75 按 Fisher 准则可以让最大化类间的散点图、最小化类内的散点图以使相同类的样本点尽 可能聚类、不同标签的样本点尽可能远离，因此 Fisher 判别准则可以变形为： (3) - 2 - {},{1,,}nixicinin1()argminiinsniiciwxwxicxiinx1()argminijndnijnjwxwxjnxinxinxjnxij{}()argmax{}TdTstrYMYJYtrYMY

中国科技论文在线 http://www.paper.edu.cn 其中， 80 (4) (5) 线性变换 引入到公式（3）中，采用拉格朗日橙子算法求解到线性变换矩阵 如下： (6) 这里， 是由上面一般特征方程前 个特征值相关的特征向量组成。 85 2 PLF 算法 通常，从 DNA 序列里获得的高维基因表达数据集市一个复杂的数据集，不仅有线性和 非线性的结构，而且还有类别信息。基于 Fisher 准则的局部线性嵌入算法（LLRFA）可以 在高维数据集里有良好的表现，但是，在高维数据集里有很多的冗余信息，因此，没有必要 直接对高维数据集应用 LLRFC。事实上，LLRFC 在处理高维数据集时，需要很高的计算量， 90 浪费太多的时间。PCA 寻求一个投影方向的最大方差，留下最重要的成份去除一些没有意 义的成份。可以先应用 PCA 将数据集降到一定程度，得到一个输出的数据集，然后再将 LLRFC 应用到输出的数据集里。具体的 PLF 算法步骤如下： 1.去除冗余信息。首先通过 PCA 将数据集投影到一定的程度。让 表示 PCA 算法的 转换矩阵，因此输出的数据集为： 95 (7) 2.计算类内与类外的重构权。首先计算出类内与类外样本点的邻域，然后采用公式（1）、 （2）计算最优重构权 、 。 3.计算最后的线性投影矩阵 。线性变换 引入到公式（3）中，因此最后的 判别函数为： 100 4.最后的输出矩阵为： 3 实验 (8) (9) 在实验中，虚拟了一组三维的 Swiss Roll 数据集，它包含 1000 个样本分别两类，散点 105 图如图 1。 通过组合降维方法 PLF 对 Swiss Roll 数据集进行降维，然后通过支持向量机(SVM)进行 分类来说明其可行性。实验结果如图 2 所示。通过结果，可以发现 PLF 与 LLRFC 在达到了 相同的降维效果，可能是由于冗余信息比较少，再冗余信息对分类的影响比较小。但是，在 降维过程中，PLF 付出了很少的时间代价，并且结果在某些程度上说明了它的可行性。 - 3 - ()()TsssMIwIw()()TdddMIwIw*YWX*W*TTdsXMXXMXW*WPCAA*PCAPCAXXAswdw*W*YWX*argmaxTTdTTsWXMXWWWXMXW**PCAYXW

中国科技论文在线 http://www.paper.edu.cn 110 图 1 Swiss Roll Fig.1 Swiss Roll 图 2 Swiss Roll 数据集的分类准确率 115 Fig.2 Accuracy Classification of Swiss Roll Based on LLRFC and PLF 事实上，LLRFC 算法在进行数据降维时，将会产生大量的计算量，以致付出更高的时 间代价，不仅如此，还会要求计算机配置比较高，以防计算时超出内存限制。SRBCT 数据 集是一个包含 2308 个样本的数据集，如表 1 所示。实验按照 1:1 的比例将 SRBCT 数据集分 120 成训练集和测试集，这样 LLRFC 与 PLF 都可以很容易的处理，通过这样来说明提出的组合 降维方法 PLF 的有效性。 表 1 SRBCT 数据集 Tab.1 The SRBCT dataset NO. of samples DIM. Classes SRBCT 83 2308 4 125 实验分类时，最后的输出矩阵分别降到 1:20 维来进行分类准确率对比，实验结果如图 3 所示。结果展示了组合降维方法 PLF 良好的降维效果。 - 4 - -10-5051015010203040-20-1001020XYZ23020406080维数准确率(%) LLRFCPLF

中国科技论文在线 http://www.paper.edu.cn Fig.3 Accuracy Classification of SRBCT Based on LLRFC and Improved LLRFC 图 3 SRBCT 数据集的分类准确率 130 正在实验中看到的，提出的组合降维方法 PLF 在肿瘤基因表达数据降维过程中具有良 好的表现。它充分结合了 PCA 方法和 LLRFC 方法的优势，PCA 算法通过保存主要的成份 向量来去除一些冗余信息，再通过 LLRFC 在低维空间里保存流形的邻域信息，因此 PLF 会 比 LLRFC 节省很多的时间，并且有更高的分类准确率。 135 4 结论 本文给出了一种新的组合降维方法 PLF 来处理肿瘤基因表达数据。新的方法可以充分 利用 PCA 与 LLRFC 方法的优势降低计算的复杂度，PCA 是通过寻求一个投影方向的最大 方差，留下最重要的成份去除一些没有意义的成份，因此它可以剔除一些冗余信息，然后再 利用 LLRFC 花费很小的时间代价处理输出的数据集。最后 PLF 比 LLRFC 算法有了更好的 140 降维效果，因此新的组合降维方法 PLF 是一个简单有效的方法。 [参考文献] (References) [1] QI Z H, WEI R Y. A combination dimensionality reduction approach to codon position patterns of eubacteria based on their complete genomes[J]. Journal of Theoretical Biology, 2011, 272(2011): 26-34. [2] Yan S C, XU D, ZHANG B Y et.al. A general framework for dimensionality reduction[J]. IEEE Transactions on Patern Analysis and Machine Intelligence, 2007, 29(1): 40-51. [3] S.T. Roweis and L.K Saul. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5500): 2323-2326. [4] CARLOTTA O. , CARLO V. . A comparative study of nonlinear study learning methods for cancer microarray data classification[J]. IEEE Expert Systems with Applications, 2013, 40(6): 2189-2197. [5] Shi C, Chen L H. Feature dimension reduction for microarray data analysis using locally linear embedding[C]. APBC, 2005, 1: 211-217. [6] HIJAZI H., BAZZI O., BIGAND A.. A new nonlinear discriminant analysis algorithm using a combined version of LDA and LLE[C]. ICIC, 2013, 7996: 443-449. [7] LI B, TIAN B B, LIU J. Tummor Gene Expression Data Classification Based on Locally Linear Repression Fisher Creterion[C]. ICIC, 2013, 7996: 443-449. 145 150 155 - 5 - 051015200102030405060708090100维数准确率 (%) PLFLLRFC