林莉媛1，陈晓云1，简彩仁2

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

       摘要：有效分类基因表达数据有助于癌症的诊断，而基因表达数据的高维数、小样本特点使基因表达数据分类困难。针对这个问题，在最小二乘回归子空间分割算法中考虑距离信息，提出融入距离信息的最小二乘回归子空间分割算法。融入距离信息的最小二乘回归子空间分割模型除了考虑数据之间的相关性，还考虑了数据之间的距离信息。在基因表达数据集上的实验结果表明，所提出的算法是有效的聚类方法。

　　关键词：基因表达数据；聚类；距离；子空间分割

0引言

　　基因表达数据的研究有助于准确识别癌症［1］，因此有效处理基因表达数据尤为重要。但基因表达数据小样本、高维数［2］的特点令这项工作困难重重。近几十年来，很多分类和聚类方法成功应用在基因表达数据上，如凸非负矩阵分解（Convex Nonnegative Matrix Factorization，C_NMF）、半非负矩阵分解（Seminonnegative Matrix Factorization，S_NMF）［3］、基因数据分析半监督学习［2］以及根据基因表达数据特点改进的谱聚类算法［4］等。基因表达数据的聚类分为基因聚类、样本聚类和双向聚类［5］，本文对肿瘤基因表达数据样本聚类。

　　子空间分割方法是近年流行的方法［6］，如稀疏子空间聚类SSC［7］、低秩表示子空间聚类LRR［8］、最小二乘回归子空间聚类LSR［9］等，并成功用于图像分割、图像压缩以及混合系统鉴定等领域［6］。子空间分割方法可使高维数据有效聚类，这适用于基因表达数据，因此本文将提出新的用于基因表达数据聚类的子空间分割方法。LSR使同类相关性强的样本聚集，但没考虑距离信息，针对这点，本文对LSR进行改进，融入距离信息，并将改进后的模型应用在基因表达数据中，通过与其他用于基因表达数据的聚类方法以及子空间分割算法进行实验比较，证明本文方法是有效的。

1子空间分割

　　子空间聚类又称子空间分割［6］，目标是寻找多个低维子空间，将数据归到相应子空间中，数学定义为［6］：设{xi∈Rd}ni=1是从k≥1个维数未知的子空间或仿射空间{Si}ki=1中采样获得的点集，各子空间维数为mi,0<mi<d，i=1,…,k。子空间描述为Si={x∈Rd:x=ui+Uiy},i=1,…,k,ui∈Rd是子空间Si的任意点（线性空间ui=0)，Ui∈Rd×mi是Si的一个基，y∈Rmi是x的低维表示。子空间聚类是找子空间个数k、维数{mi}ki=1、基{Ui}ki=1、点{ui}ki=1，并将点集分割到子空间中。

　　LSR［9］是基于谱聚类的子空间聚类方法，与其他基于谱聚类的方法一样，先构造仿射矩阵，再将谱聚类方法应用在仿射矩阵上，模型为：

　　minZZF，s.t.X=XZ

　　噪声的扩展模型为：

　　minZX－XZ2F+λZ2F(1)

　　其中，λ>0，·F是F范数，参考文献［9］给出式(1)的计算方法，并证明LSR有聚集性，是高效、鲁棒的方法。

2融入距离信息的最小二乘回归子空间分割

　　2.1样本数据点的距离信息

　　由参考文献［10］可知彼此间距离近的数据点更可能来自同一子空间，因此本文假设彼此间距离近的数据点可分配到更大的权重系数。设样本集为{x1,x2,...,xn}，X∈Rd×n，xi∈Rd×1。根据上述假设，对于任意样本xi，希望：

　　min∑nj=1xi－xj2zij

　　其中，zi∈Rn×1，zij是zi的第j个元素，矩阵形式为：

　　min Tr(ZΤD)(2)

　　其中，D为距离矩阵，xi－xj2是D的第i行的第j个元素，Z={z1,z2,…,zn}。

　　2.2融入距离信息的最小二乘回归子空间分割模型

　　将式(2)与最小二乘回归子空间分割模型相结合，得到融入距离信息的最小二乘回归子空间分割模型为：

　　minZ12X－XZ2F+λ2Z2F+βTr(ZΤD)(3)

　　其中，λ>0、β>0是两个可调节的参数,·F表示F范数，Tr(·)表示迹。令：

　　对L(Z)求导,并令其导数为0，即L=－XΤX+XΤXZ+λZ+βD=0，可得到式（3）的最优解：Z*=(XTX+λI)－1(XTX－βD)。

　　通过(|Z*|+|(Z*)T|)/2构造仿射矩阵，再用标准聚类方法（Normalized Cuts, Ncut）［11］分割彷射矩阵。融入距离信息的最小二乘回归子空间分割(Subspace Segmentation via Least Squares Regression including Information about Distance, DLSR)算法如下：

　　输入：数据矩阵X，类别数为k，参数β、λ

　　（1）解决问题式（3）得到解Z*；

　　（2）通过(|Z*|+|(Z*)T|)/2计算仿射矩阵；

　　（3）应用Ncut方法将数据分成k个子空间。

　　输出：聚类结果

3实验

　　本节在基因表达数据集上用聚类准确率验证提出的DLSR，与本文方法比较的现有方法为：传统聚类方法kmeans和层次聚类（Hierarchical Clustering, HC），子空间分割方法LRR［8］和LSR［9］，非负矩阵分解扩展方法C_NMF和S_NMF［3］。

　　3.1数据集

　　实验使用公开基因表达数据集: 9_Tumor［12］、Brain_Tumor［13］、Leukemia［14］、Leukemia［13］、Leukemia［15］、DLBCL［13］，数据集信息如表1所示。表1数据集信息数据集诊断内容样本个数基因个数类别数9_Tumor人类肿瘤605 7269Brain_Tumor1脑癌1905 9205Leukemia白血病727 1292DLBCL弥漫性大B细胞淋巴瘤和

　　滤泡性淋巴瘤775 4692Leukemia1白血病1725 3273Leukemia2白血病28311 2253

　　3.2实验结果与分析

　　准确率计算公式为：

　　其中，ri是得到的类标签；si是样本本身的类标签；n为样本数；map(ri)是将ri映射成与si等价的类标签；δ(x,y)是一个函数，δ(x,y)=1x=y

　　0x≠y。

　　实验中，DLSR、LSR、LRR都需设置参数，本文的参数选择方法是让参数取多个不同的值，实验时遍历这些值，最后取使结果最好的值。DLSR还有另一个参数β，取值策略与λ相同。实验时，HC运行一次，其余算法运行10次，取准确率的平均值，结果如表2所示。

　　6个数据集上的实验表明，除Leukemia外，DLSR与其他方法相比，都取得较优准确率。kmeans虽然在Leukemia中准确率最高，但在其余数据集中的结果并不都好。总的来说，DLSR还是优于kmeans。因此，本文算法对基因表达数据的聚类更有效。

　　值得注意的是，DLSR优于LSR，因此在LSR中融入距离信息，可以提供一定的额外信息，有利于提高算法聚类能力。

　　3.3参数选择

　　DLSR模型有两个参数β和λ。本节设置参数β的变化范围为{0.002,0.004,0.01,0.04,0.6,0.7,1,100,10 000, 100 000}，参数λ的变化范围为{0.005,0.01,0.05, 0.1,0.5,1,10,100,1 000}。图1描述了这两个参数变化对聚类准确率的影响。平稳的地方说明参数取在那部分时准确率变化较稳定。可看出DLSR对参数β和λ的选取都较敏感，聚类准确率随参数变化呈现出一定波动。总体上看，参数β选在0.002~0.6范围内可找到较理想的聚类准确率，参数λ选在0.05~10范围内可找到较好的聚类准确率。

　　4结论

　　本文在最小二乘回归子空间分割模型的基础上，考虑距离信息，提出融入距离信息的最小二乘回归子空间分割模型，并应用在基因表达数据上。实验表明，对于给出的基因表达数据集，DLSR与子空间分割算法LRR、LSR以及原先用于基因表达数据的方法相比更有效。而且，在LSR的基础上融入了距离信息，确实可提高聚类能力，对LSR有一定的优化。但是介于参数的选取对实验结果较为敏感，如何高效地选取参数是今后要研究的问题。

参考文献

　　［1］ 黄德双. 基因表达谱数据挖掘方法研究［M］.北京：科学出版社, 2009.

　　［2］ 刘德山, 孙丽, 闫德勤. 一种基因数据分析的半监督学习算法［J］. 微型机与应用, 2014, 33(12): 4447.

　　［3］ DING C, Li Tao, JORDAN M. Convex and seminonnegative matrix factorizations［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(1): 4555.

　　［4］ 王俊生, 王年, 郭秀丽, 等. 基于 Normalized Cut 的基因表达数据聚类［J］. 安徽大学学报(自然科学版),2012, 36(4): 6872.

　　［5］ Jiang Daxin, Tang Chun, Zhang Aidong. Cluster analysis for gene expression data: a survey［J］. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(11): 13701386.

　　［6］ VIDAL R. A tutorial on subspace clustering［J］. IEEE Signal Processing Magazine, 2010, 28(2): 5268.

　　［7］ ELHAMIFAR E, VIDAL R. Sparse subspace clustering［C］. IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2009, IEEE, 2009: 27902797.

　　［8］ Liu Guangcan, Lin Zhouchen, Yu Yong. Robust subspace segmentation by lowrank representation［C］. Proceedings of the 27th International Conference on Machine Learning (ICML10), 2010: 663670.

　　［9］ Lu Canyi, Min Hai, Zhao Zhongqiu, et al. Robust and efficient subspace segmentation via least squares regression［C］. European Conference on Computer Vision, ECCV 2012, 2012,7578(1): 347360.

　　［10］ Nie Feiping, Wang Xiaoqian, Huang Heng. Clustering and projected clustering with adaptive neighbors［C］. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2014: 977986.

　　［11］ Shi Jianbo, MALIK J. Normalized cuts and image segmentation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888905.

　　［12］ STAUNTON J E, SLONIM D K, COLLER H A, et al. Chemosensitivity prediction by transcriptional profiling［J］. Proceedings of the National Academy of Sciences, 2001, 98(19): 1078710792.