张鹏涛，陈晓云，简彩仁

(1.福州大学 数学与计算机科学学院，福建 福州 350116；2.厦门大学 嘉庚学院，福建 漳州 363105)



基于局部坐标稀疏表示和最小二乘的基因表达数据分类

张鹏涛1，陈晓云1，简彩仁2

(1.福州大学 数学与计算机科学学院，福建 福州 350116；2.厦门大学 嘉庚学院，福建 漳州 363105)

局部坐标稀疏表示可以使测试样本由其近邻样本线性近似表示，借鉴此思想，在稀疏表示模型中引入局部距离加权并添加非负约束，求解得到测试样本在训练集上的表示系数，根据表示系数的大小剔除训练集中的噪声点，在新的训练集上进行最小二乘子空间分类。在6个基因表达数据集上的实验结果表明，所提算法可以进一步改善分类质量。

局部坐标表示；稀疏表示；最小二乘

0 引言

DNA微阵列技术[1]的出现使得人们可以获得大量的基因表达数据，如何对这些数据进行分析、整理、归纳、注释对研究人类的基因突变以及重大疾病有着重大现实意义，这也是分子生物信息学[2]的重点研究课题。

基因表达数据存在着高维、小样本、多噪声等复杂特性[3]，致使直接利用基因表达数据进行肿瘤分类面临严峻挑战。近年来，大量学者通过对基因表达数据建立有效的分类模型，实现了在分子水平上对肿瘤类型准确识别。文献[4]中对多种类的微阵列基因数据分类模型进行了全面评估，结果表明多类支持向量机(SVM)算法优于k-近邻算法、反向传播和概率神经网络模型，并建立了一个可以公开使用的基因表达模型选择系统(Gene Expression Model Selector ,GEMS)。

稀疏表示分类最早在人脸识别[5]方面取得成功应用。文献[6]中进一步将稀疏表示模型应用到基因表达数据分类，提出稀疏表示分类算法(SRC)，该算法将测试样本用训练样本的线性组合表示，通过L1-正则约束计算出表示系数进而重构测试样本，最后通过最小化每一类的重构残差以达到分类的目的。实验结果显示该算法优于SVM算法。然而SRC模型的求解需要用到牛顿内点法[7]迭代计算,时间复杂度较高。文献[8]进一步提出一种有效的交替方向优化算法解决SRC稀疏模型。文献[9]中利用同样的自表示方法提出非负最小二乘算法(NNLS)，对缺失值和噪声点有很好的强健性。文献[10]进一步提出最小二乘回归分类算法(LSRC)，可以对肿瘤数据有效分类，但LSRC依赖于正则参数的选择，容易出现奇异矩阵求逆的问题，并且上述模型都没有考虑到待测样本和训练集之间的距离关系，训练集中可能存在噪声样本，直接利用原始训练集表示测试样本会引起分类精度降低。针对此，本文借鉴局部坐标表示的思想，引入局部距离加权信息和非负约束到稀疏表示模型中，利用得到的表示系数剔除训练集中与测试样本相关性小的噪声样本，再结合最小二乘模型和最近邻子空间准则进行分类。

1 稀疏表示

给定n个类标签已知的训练样本X=[x1,x2,…,xn]∈Rd×n，考虑一个类标签未知的测试样本y∈Rd，通过下式用训练样本线性表示该测试样本：

y=x1z1+x2z2+…+xnzn

(1)

其中zi(i=1,2,…,n)是表示系数，zi值越大表示测试样本y与训练样本xi的相关程度越大，能更好地表示y。通常为方便写成如下矩阵形式：

y=Xz

(2)

其中z=[z1,z2,…,zn]T∈Rn。

在稀疏表示分类模型(SRC)[6]中,通过下列模型求得测试样本y在训练集X上的表示系数：

(3)

在有噪声的情况下，转换为下列模型：

(4)

2 局部坐标稀疏表示最小二乘分类

2.1 局部坐标稀疏表示剔除噪声

尽管SRC模型得到的表示系数通常能较好地分类，但它容易出现过稀疏[11]的情况，且运行速度很慢。针对训练集X中存在噪声的问题，本文引入局部坐标编码的思想，提出局部坐标稀疏表示模型剔除噪声样本。

局部坐标编码(LocalCoordinateCoding，LCC)[12]的思想是:在给定字典下，寻找一个测试样本的稀疏表示，并且它的表示系数是由该测试样本的局部近邻字典的线性组合所编码。本文在SRC模型的基础上，同时借鉴LCC局部近邻表示的思想，用训练集X作为字典矩阵，添加非负约束，旨在用测试样本的局部近邻样本重构测试样本，得到以下局部坐标稀疏表示(LCSR)模型：

s.t.z≥0

(5)

其中X*i表示训练集中的第i个样本,zi表示系数z的第i个元素，上面模型中第一项表示重构误差，第二项为正则项，确保测试样本由局部近邻样本线性近似表示。近邻样本通常属于同一类，这样近邻样本在重构表示测试样本时占有较大的比重，式(5)第二项能自适应地给这些近邻样本分配较大的权重系数。文献[13]进一步指出局部性比稀疏性更重要，因为局部性通常可以得到一个较好的稀疏性，但反过来稀疏性通常并不能得到局部性，这样引入局部信息得到的表示系数更具有判别能力。

式(5)也相当于在SRC模型中添加距离加权和非负约束，得到的表示系数z具有稀疏性、非负和局部近邻表示的性质，这样通过设置一个相关程度阈值ε，剔除zi<ε所对应的训练样本xi，得到新的训练集Xnew。本文采用文献[8]中提出的非负加权稀疏编码算法解决式(5)表示的模型。

2.2 最小二乘模型

对于基因表达数据,通常d>>n,因此(2)式是一个超定方程，求精确解没有意义，本文采用最小二乘法得到以下模型：

(6)

z=(XTX)-1XTy

(7)

但上式中矩阵XTX极易接近奇异矩阵，为此，文献[10]在上面模型中添加L2-范数正则项，提出LSRC模型：

(8)

其中λ是正则参数，式(8)表示的模型是凸问题，可直接求导得到解析解：

z=(XTX+λI)-1XTy

(9)

式(9)可以在一定程度上避免奇异矩阵求逆的问题，也可得到较好的分类效果，但该模型依赖于参数λ的选择，并且没有考虑到训练集中存在噪声样本的情况。因此，本文在新的训练集Xnew上通过最小二乘模型求得测试样本y新的表示系数znew，将Xnew代入到式(7)得：

(10)

2.3 最近邻子空间准则分类[10]

假设训练集有K个类标签l1,l2,…,lK，求得测试样本y在训练集X上的表示系数向量z，定义y在第k类训练样本上的重构余量如下

(11)

其中y是测试样本，X是训练集，δk(z):Rn→Rn表示y在第k类样本的重构系数，定义如下：

(12)

最后，测试样本y所属的类标签为：

(13)

2.4 局部坐标稀疏表示最小二乘分类

通常可以把同一类的样本视为一个子空间，理想情况下，测试样本仅由属于同一子空间的样本数据线性表示,而与其他子空间的样本线性无关，表示系数为0或者非常小,属于同一子空间样本的表示系数相对较大。本文利用最近邻子空间分类准则，将2.1节得到的训练样本集Xnew和式(10)求得的表示系数znew代入式(11)～(13)得到y的类标签，具体算法如下：

局部坐标稀疏表示最小二乘分类算法(LCSR-LSC)

输入：训练集Xtrain，测试样本y，参数λ,训练集类标签ltrain，阈值ε

输出：测试样本y的类标签ltest

表2 分类准确率(ACC+time,对比试验降维) (s)

1.将数据标准化预处理；

2.求解LCSR模型式(5)得到表示系数z，根据阈值ε剔除zi<ε所对应的训练样本xi，得到新的训练样本集Xnew；

3.将Xnew代入到公式(10)求得新的表示系数znew；

4.利用最近邻子空间准则公式(11)～(13)得到待测样本y的类标签ltest。

3 实验

在6个基因表达数据上验证所提算法LCSR-LSC的有效性，对比算法有：传统分类算法1-NN、SVM、稀疏表示分类SRC、最小二乘回归分类LSRC,非负最小二乘分类NNLS以及LCSR模型结合最近邻子空间准则算法LCSR-C。

表3 分类准确率(ACC+time,对比试验未降维) (s)

实验环境：Windows 7系统，内存4 GB，MATLAB2012b，所有实验统一在GEMS系统[14]下按十字交叉法进行，将数据集分为十组，九组用于训练，一组用于测试。

LCSR-LSC正则参数λ取(0.001,0.005,0.01，0.02,0.03,0.04,0.05,0.06,0.07，0.08, 0.09, 0.1)，相关程度阈值ε取很小的正常数(实验选取3×10-5)，SVM算法选择libsvm工具箱[15]，取RBF核函数，默认核参数1。

3.1 数据集

实验选用GEMS公开的基因表达数据集[14]：SRBCT、Leukemia1、Leukemina2、DLBCL、Prostate_Tumor、11_Tumors，数据集描述如表1所示。

表1 数据集描述

所有样本数据进行规范化处理：

(14)

其中x表示一个样本数据。

3.2 实验结果与分析

实验结果用计算得到的类标签与真实类标签求得分类准确率(ACC)以及算法运行时间(T(s))衡量。本文用PCA将训练样本和测试样本降到m维(m≤d),实验取m=100，由于本文算法用PCA降维，而对比试验有些算法并没有进行降维处理，为了试验对比的合理性，分别将本文算法得到的实验结果与对比试验在降维和未降维两种情况下进行比较，结果见表2和表3。

在6个数据集上的实验结果如图1所示。结果表明，对于降维和未降维数据，LCSR-LSC算法的分类准确率都高于对比算法，其中SRC和LSRC算法对数据降维最为敏感，降维后的分类精度大幅度降低，甚至低于传统的分类算法1-NN、SVM和LCSR-C算法，NNLS算法在降维前后都能取得较高的分类准确率，未降维的LSRC算法的分类准确率优于SRC和NNLS算法，而未降维的SRC、NNLS、LSRC都优于传统的1-NN、SVM算法，说明采用稀疏表示和最小二乘的算法能取得较好的分类效果，并且这三种算法分类效果也优于LCSR-C算法，但分类准确率低于LCSR-LSC算法，可以看出本文提出的先用LCSR剔除噪声点的方法可以进一步增强LSRC的分类效果。

从运行时间上分析，在保证较高分类准确率的情况下，由于未降维SRC采用内点法迭代求解，时间开销远远大于其他几种算法，LSRC、1-NN的运行时间低于NNLS、SVM，而LCSR-LSC的时间成本远远低于SRC，也能实现较为理想的时间开销。

3.3 降维以及参数选择

讨论降维维数以及参数对分类准确率的影响，在6个基因表达数据集上降维维数分别取{10,20, 30,40,50,60,70,80,90, 100}，参数λ取{0.001,0.005,0.01,0.02, 0.03,0.04,0.05, 0.06, 0.07,0.08, 0.09, 0.1}，得到不同的分类准确率，如图2所示。通过分析可以看出，所选取的维数以及参数并没有引起分类准确率很大的改变，当正则参数λ取0.05～0.08时，降维数取80～100时可以得到较高的分类精度。此外，LCSR-LSC算法的正则参数出现在LCSR模型中，用于剔除噪声样本，相比于LSRC、SRC、NNLS其他模型直接用于求得表示系数对分类准确率影响较小。

图1 降维和参数λ取不同位时LCSR-LSC在6组数据集上的分类准确率

4 结论

本文利用局部坐标稀疏表示模型求得的表示系数具有稀疏、非负以及局部近邻表示的良好性质，剔除训练集的噪声样本，然后在新的训练集上结合最小二乘模型和最近邻子空间准则进行分类，并应用在基因表达数据集上，可以取得理想的分类效果，进一步提高LSRC的分类准确率，且能高于SRC、NNLS算法的准确率，时间成本低于SRC算法。如何设计更有效的解决稀疏表示的优化算法以及怎样更为有效地剔除噪声样本是今后需要研究的问题。

[1] SABER H B, ELLOUMI M. DNA microarray data analysis: a new survey on biclustering[J]. International Journal for Computational Biology (IJCB), 2015, 4(1): 21-37.

[2] GOLUB T R, SLONIM D K, TAMAYO P, et al. Molecular classification of cancer: class discovery and class prediction by gene expression monitoring[J]. Science, 1999, 286(5439): 531-537.

[3] 林莉媛, 陈晓云, 简彩仁. 融入距离信息的最小二乘回归子空间分割[J]. 微型机与应用, 2016, 35(6):63-65.

[4] STATNIKOV A, ALIFERIS C F, TSAMARDINOS I, et al. A comprehensive evaluation of multicategory classification methods for microarray gene expression cancer diagnosis[J]. Bioinformatics, 2005, 21(5): 631-643.

[5] WRIGHT J, YANG A Y, GANESH A, et al. Robust face recognition via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(2): 210-227.

[6] Hang Xiyi, Wu Fengxiang. Sparse representation for classification of tumors using gene expression data[J]. BioMed Research International, 2009(403689).

[7] KIM S J, KOH K, LUSTIG M, et al. An interior-point method for large-scale-regularized least squares[J]. IEEE Journal of Selected Topics in Signal Processing, 2007,1(4): 606-617.

[8] Yang Junfeng, Zhang Yin. Alternating direction algorithms forell_1-problems in compressive sensing[J]. SIAM Journal on Scientific Computing, 2011, 33(1): 250-278.

[9] Li Yifeng, NGOM A. Classification approach based on non-negative least squares[J]. Neurocomputing, 2013, 118(2): 41-57.

[10] Chen Xiaoyun, Jian Cairen. A tumor classification model using least square regression[C].International Conference on Natural Computation. IEEE, 2014:753-758.

[11] Zhang Zheng, Xu Yong, Yang Jian, et al. A survey of sparse representation: algorithms and applications[J]. IEEE Access, 2015,3: 490-530.

[12] Yu Kai, Zhang Tong, Gong Yihong. Nonlinear learning using local coordinate coding[C].Advances in Neural Information Processing Systems, 2009: 2223-2231.

[13] Wang Jinjun, Yang Jianchao, Yu Kai, et al. Locality-constrained linear coding for image classification[C]. Computer Vision and Pattern Recognition, 2010: 3360-3367.

[14] STATNIKOV A, TSAMARDINOS I, DOSBAYEV Y, et al. GEMS: a system for automated cancer diagnosis and biomarker discovery from microarray gene expression data[J]. International Journal of Medical Informatics, 2005, 74(7): 491-503.

[15] CHANG C C, LIN C J. LIBSVM: a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2011, 2(3): 27.

Gene expression data classification based on local coordinate sparse representation and least squares

Zhang Pengtao1, Chen Xiaoyun1, Jian Cairen2

(1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China；2. Tan Kah Kee Colleage, Xiamen University, Zhangzhou 363105, China)

The local coordinate sparse representation can ensure that each test sample can be locally approximated by a linear combination of its nearby train samples. Based on the idea, the local weighted distance and negative constraint are introduced into the sparse representation model in this paper, and we obtain the representation coefficients of the test sample in the trainset by solving the model. Then, according to the size of representation coefficient, the noise points are eliminated and we use the least squares and the nearest neighbor subspace criteria for classification in the new training set. Experimental results on six genetic expression data show that our proposed method can further improve the quality of classification.

local coordinate coding; sparse representation; least squares

TP391; TP311

A

10.19358/j.issn.1674- 7720.2017.12.006

张鹏涛，陈晓云，简彩仁.基于局部坐标稀疏表示和最小二乘的基因表达数据分类[J].微型机与应用，2017,36(12)：19-22,28.

2016-12-28)

张鹏涛(1991-)，男，硕士研究生，主要研究方向：数据挖掘、模式识别。

陈晓云(1970-)，通信作者，女，博士，教授，主要研究方向：数据挖掘、模式识别。E-mail:c_xiaoyun@21cn.com。

简彩仁(1988-)，男，硕士研究生，主要研究方向：数据挖掘、模式识别等。