基于核最小二乘回归子空间分割的高维小样本数据聚类

简彩仁,翁 谦,陈晓云

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

0 引言

高维小样本数据广泛存在于现实生活中,如基因表达数据、 人脸图像数据等,如何识别高维小样本数据是近年来模式识别研究的热点[1-6]. 高维小样本数据集的样本数量通常为几十到几百个,然而特征属性往往是成千上万的. 高维小样本数据集往往是非线性的,因此,许多传统的线性模式识别方法难以适应高维小样本数据的识别[2-5]. 针对高维小样本数据提出一种基于子空间分割的非线性聚类方法.

子空间分割方法是近年来聚类方法研究的热点问题[7-10],其目标是将数据集分割(或聚集)成几个簇,并使每一个簇对应于一个子空间. 子空间分割方法已经成功应用在机器学习和计算机视觉等相关研究中. 同一类的数据样本构成一个子空间,不同的子空间混合构成混合子空间,而现实中的数据近乎可以视为是混合子空间,因此子空间分割方法在图像聚类、 图像分割、 运动物体识别和基因表达数据识别等领域有着广泛的应用[7-10]. 子空间分割的目标是将混合采样的数据集分割成不同的子空间,从而实现聚类.

近几年的子空间分割研究得到了很好的发展,基于表示理论的子空间分割方法的优势是对噪声是鲁棒的. 其主要思想是利用表示理论得到表示矩阵,接着用表示矩阵构建相似矩阵,最后利用文献[11]提出一种经典的谱聚类方法： 标准化分割方法实现聚类. 例如,低秩表示子空间分割方法[8]旨在通过秩最小化来构建相似矩阵; 最小二乘回归子空间分割方法[9]通过F-范数正则化达到内聚度. 现实中的数据往往在非线性流形上采样,高维小样本数据是非线性的,因此基于线性表示理论的子空间分割方法,不利于发现高维小样本数据集的本质特征. 为了弥补这一不足,受非线性表示理论的启发,利用核理论改进最小二乘回归子空间分割方法,将其推广到非线性数据集的识别中.

1 基于表示理论的子空间分割法

例如,最小二乘回归子空间分割方法最小化Z的F-范数

针对噪声数据的扩展模型为

最小二乘回归子空间分割方法对噪声是鲁棒的,并且有很好的聚集性能. 然而高维小样本数据往往是非线性的,因此基于线性表示理论的最小二乘回归子空间分割方法不能很好地适应高维小样本数据的非线性性质.

2 核最小二乘回归子空间分割法

最小二乘回归子空间分割方法是在线性空间考虑的,不利于发现高维小样本数据的非线性性质. 针对这一不足,本研究利用核理论将最小二乘回归子空间分割方法扩展成适合非线性流形学习的核最小二乘回归子空间分割法.

给定非线性特征空间映射Φ:Rm→M,其中Rm是高维样本空间,M是低维流形空间,因此原始高维数据X的低维流形表示为Φ(X). 对低维流形样本Φ(X)进行子空间分割研究,因此非线性的最小二乘回归子空间分割方法可以写为

其中,λ>0是正则参数,diag(Z)=0表示方阵Z的主对角线为0.

对问题(1)的求解，

一种简单的思路是分别对每个样本求解表示系数. 对第i个样本求解表示系数[Z*]i,假设Φ(X)=[Φ(x1),Φ(x2), …,Φ(xn)]∈Rm×n,去掉Φ(X)的第i列,得到Φ(Yi)=[Φ(x1), …,Φ(xi-1),Φ(xi+1), …,Φ(xn)],则问题(1)变为

显然这样对每个样本求解的方法是低效的. 下面的证明过程给出了一种可以并行求解问题(1)的方法,该问题的解析解为Z*=-D(diag(D))-1, diag(Z*)=0,其中,D=(Φ(X)TΦ(X)+λI)-1.

证明 利用D=(Φ(X)TΦ(X)+λI)-1来计算[Z*]i.

首先,利用初等变换Φ(X)P=[Φ(Yi)Φ(xi)]将Φ(X)重新排序,其中P是置换矩阵,PPT=PTP=I. 则有

[PT(Φ(X)TΦ(X)+λI)P]-1=PTDP

(2)

接着,利用Woodbury公式[12]计算

其中

[Z*]i=-bi正是本研究所要求解的,由P的性质从式子(2)可以得到bi,于是

可以将这一结果写为Z*=-D(diag(D))-1, diag(Z*)=0.

更一般的,去掉约束条件diag(Z)=0,问题(1)退化成岭回归方程

(3)

Z=(Φ(X)TΦ(X)+λI)-1Φ(X)TΦ(X)

直接定义非线性映射Φ(X)是困难的,而核表示理论给出了一种不需要定义非线性映射的技术[2, 13]. 设KYY∈Rn×n是一个半正定核矩阵,它们的元素定义为

[KYY]ij=[(Φ(X),Φ(X))M]ij=Φ(xi)TΦ(xj)=k(xi,xj)

根据核表示理论,将非线性最小二乘回归子空间分割方法扩展为核最小二乘回归子空间分割法,因此问题(1)的解可以写为

Z*=-D(diag(D))-1, diag(Z*)=0

(4)

问题(3)的解可以写为

Z*=DK

(5)

其中:D=(K+λI)-1,K是核矩阵.

类似于LSR,核最小二乘回归空间分割方法也是一种基于谱聚类的子空间分割方法,首先通过式(4)～(5)得到该问题的解Z*,那么仿射矩阵为(|Z*|+|(Z*)T|)/2,接着应用标准分割方法(normalized cuts,NC)[11]对仿射矩阵进行分割. 至此,本研究归纳核最小二乘回归子空间分割(kernel least square regression subspace segmentation,KLSR)方法如下

算法:核最小二乘回归子空间分割算法(KLSR)Input:数据矩阵X,正则参数λ,核函数参数σ,类数kOutput:k个类簇Step1:通过解决问题得到矩阵Z*Step2:计算仿射矩阵Z*+(Z*)T()/2;Step3:应用标准分割方法将数据分成k个子空间.

3 实验验证

为验证核最小二乘回归子空间分割方法的有效性,本节将用KLSR和子空间分割方法, 即最小二乘回归子空间分割法(least square regression subspace segmentation,LSR)[9],低秩表示子空间分割法(low rank representation,LRR)[8], 以及传统的聚类算法： K均值聚类法(K-means)和层次聚类法(hierarchical clustering,HC)从聚类准确率的角度进行比较. 为区别问题(1)和问题(3),将式(4)、 (5)分别记为KLSR1、 KLSR2. 聚类准确率的定义如下，

对一个给定的样本,令ri和si分别为聚类算法得到的类标签和样本自带的类标签,那么准确率的计算公式[14]为

(6)

其中:n为样本总数；δ(x,y)是一个函数,当x=y时,值为1,否则为0；map(ri)是一个正交函数,将每一个类标签ri映射成与样本自带的类标签等价的类标签.

参数设置如下,子空间分割法的正则参数统一设置为{0.000 1,0.001,0.01,0.1,1,2,3,4,5,10},KLSR的核函数选用高斯核函数,其参数σ设置为{0.5,1.0,1.5,2.0,2.5,3.0,3.5,5.0}. 实验过程采用遍历以上实验参数的方法给出实验结果.

3.1 数据集

本研究选用10个广泛应用在模式识别研究的高维小样本数据集作为研究. 它们是基因表达数据集：ALLAML、CLL_SUB_111、leukemia、lymphoma、nci9 、TOX_171 和图像数据集：ORL、pixraw10P、warpPIE10P、Yale. 将它们的简要信息整理归纳,见表1.

表1 数据集描述Tab.1 Summary of the data sets

3.2 实验结果与分析

本研究的实验环境为Windows7系统,内存2 GB,所有方法都用Matlab2011b编程实现,为避免聚类过程的随机性,实验过程中每种方法运行50次,求取聚类准确率的平均值. 表2以聚类准确率的均值±标准差的形式给出实验结果.

表2的实验结果表明,在所有的数据集上,KLSR都有较好的聚类结果,在ALLAML和leukemia数据集上的聚类准确率比其它方法高出20%. 将KLSR的方法去掉限制条件diag(Z)=0的扩展方法KLSR2也可以取到较理想的聚类准确率.

表2 聚类准确率对比Tab.2 Clustering accuracy comparison (%)

对比经典的非线性子空间分割方法LSR和LRR,两种KLSR方法都可以取到较理想的聚类准确率,这表明基于核理论的非线性子空间分割方法能更适合高维小样本数据的聚类研究. 因此,KLSR可以较好地反映高维小样本数据的非线性性质,取得较好的聚类准确率.

与传统的聚类方法K-means和HC对比,子空间分割方法的聚类准确率明显优于传统的聚类方法. 原因是因为传统聚类方法以欧氏距离为度量,不能很好适应高维小样本数据的非线性性质. 与传统的聚类方法对比,KLSR的聚类优势更加明显,这也显示出KLSR可以较好地适应高维小样本数据的聚类.

上述的实验结果比较表明KLSR是一种有效的适合高维小样本数据聚类的一种方法.

3.3 运行时间比较

KLSR能较好地适应高维小样本数据的非线性,本节讨论KLSR的运行效率. 对比各种方法的运行时间,KLSR、 LSR和LRR等三种子空间分割方法的正则参数选定为0.01,KLSR的核函数参数选为1,各种方法运行50次,取平均运行时间进行对比,表3给出了所有方法的平均运行时间.

表3 运行时间对比Tab.3 Running time comparison (s)

从表3的运行时间对比分析,发现LSR的运行效率最高,这是因为LSR有解析解的缘故. 由于KLSR需要构造核函数并且也有解析解,因此KLSR的运行时间比LSR的略长. 此外本研究注意到,除了ORL数据集和Yale数据集,KLSR方法会比传统方法有更好的运行效率,其原因是ORL数据集和Yale数据集的属性与样本比是所有数据集中最小的,也体现了KLSR能更好地适应高维小样本数据的聚类.

3.4 参数选择

KLSR能适应高维小样本数据的非线性性质,需要构造核函数,与经典的子空间分割方法对比,多了一个参数σ. 本节讨论,正则参数λ和核函数参数σ的变化对聚类准确率的影响.

图1显示了正则参数λ和核函数参数σ的变化对聚类准确率的影响. 不同的参数设置会得到不同的聚类准确率. 总体来说,较小的λ具有较高的聚类准确率,这和LSR[9]的研究结论是一致的. 当给定一个较小的λ时,较大的参数σ有较好聚类准确率,这说明较大的σ更能适应高维小样本数据的非线性性质. 另一方面,较大的参数σ,有较好的平滑程度,因此有较好的容噪能力,从而得到更好的聚类准确率. 从图1的实验结果分析,较小的正则参数λ和较大的核函数参数σ是一组较为理想的参数选择. 这使得KLSR有很好的应用价值.

(a) ALLAML

(b) CLL_SUB_111

(c) leukemia

(d) lymphoma

(e) nci9

(f) TOX_171

(g) ORL

(h) pixraw10P

(i) warpPIE10P

(j) Yale图1 λ, σ不同时KLSR在10个数据集上的聚类准确率Fig.1 Clustering accuracy of KLSR on 10 datasets with different λ and σ

3.5 不同核函数的影响

核最小二乘回归子空间分割方法是以核表示理论为基础的,因此核函数的选择对聚类准确率会产生影响. 本节在不同的核函数下,对KLSR的聚类准确率进行分析. 选用多项式核函数(Poly)与高斯核函数(Gauss)进行对比,高斯核函数参数σ设置为{0.5,1.0,1.5,2.0,2.5,3.0,3.5,5.0},多项式核函数的a设为0,b设置为{0.5,1.0,1.5,2.0,2.5,3.0,3.5,5.0}. 表4以平均聚类准确率的形式给出实验结果.

表4 不同的核函数下KLSR在10个数据集上的聚类准确率Tab.4 Clustering accuracy of KLSR on 10 datasets with different kernel function (%)

注： 限于篇幅,表4的数据集名称用表1中的序号代替.

从表4的实验结果不难发现核函数的选择会影响KLSR的聚类准确率,这反映了高维小样本数据聚类研究的复杂性. 在第2个和第6个数据集上,多项式核函数下KLSR的聚类准确率更为理想,但总体来说高斯核函数的聚类准确率优于多项式核函数的聚类准确率,这说明高斯核函数具有更好的鲁棒性. 此外,两种核函数下的KLSR的聚类准确率都优于其他方法,因此提出的KLSR针对高维小样本数据的聚类有一定的优势.

4 结论

本研究提出一种非线性子空间分割方法： 核最小二乘回归子空间分割方法(KLSR),并将其成功应用在高维小样本数据的聚类研究中. 实验结果表明, KLSR可以很好地适应基因表达数据和图像数据等高维小样本数据的非线性性质,比现有的LSR和LRR等子空间分割方法更适合高维小样本数据的聚类. 但基于表示理论的子空间分割方法存在如何自动识别聚类类簇等问题的不足,这需要更多的理论支持,将在今后的研究给出.

[1] BROWN P O, BOTSTEIN D. Exploring the new world of the genome with DNA microarrays[J]. Nature Genetics, 1999, 21: 33-37.

[2] BISHOP C M. Pattern recognition and machine learning(information science and statistics)[M]. New York: Springer-Verlag Inc, 2006.

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

[4] ZHU X, HUANG Z, YANG Y,etal. Self-taught dimensionality reduction on the high-dimensional small-sized data[J]. Pattern Recognition, 2012, 46(1): 215-229.

[5] 何进荣, 丁立新, 崔梦天, 等. 基于矩阵指数变换的边界Fisher分析[J]. 计算机学报, 2014, 37(10): 2196-2205.

[6] 王文俊. 基于稀疏类别保留投影的基因表达数据降维方法[J]. 电子学报, 2016, 44(4): 873-877.

[7] ELHAMIFAR E, VIDAL R. Sparse subspace clustering[C]//Proceedings of the 23rd IEEE Conference on Computer Vision and Pattern Recognition. Miami: [s.n.], 2009: 2790-2797.

[8] LIU G, LIN Z, YU Y. Robust subspace segmentation by low-rank representation[C]// Proceedings of the 27th International Conference on Machine Learning. Haifa: [s.n.], 2010: 663-670.

[9] LU C Y, MIN H, ZHAO Z Q,etal. Robust and efficient subspace segmentation via least squares regression[C]// Proceedings of the 12th Computer Vision. Florence: Springer, 2012: 347-360.

[10] 简彩仁, 陈晓云. 基于投影最小二乘回归子空间分割的基因表达数据聚类[J]. 模式识别与人工智能, 2015, 28(8): 728-734.

[11] SHI J, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.

[12] 张贤达. 矩阵分析与应用[M]. 2版. 北京: 清华大学出版社, 2013.

[13] SCHÖLKOPF B, SUNG K K, BURGES C J C,etal. Comparing support vector machines with Gaussian kernels to radial basis function classifiers[J]. IEEE Transactions on Signal Processing, 1996, 45(11): 2758-2765.

[14] CAI D, HE X, WU X,etal. Non-negative matrix factorization on manifold[C]// Proceedings of the 8th IEEE International Conference on Data Mining. Pisa: IEEE, 2008: 63-72.