2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

局部子空间聚类

刘展杰,  陈晓云

文章导航 > 自动化学报  > 2016 >  42(8): 1238-1247
刘展杰, 陈晓云. 局部子空间聚类. 自动化学报, 2016, 42(8): 1238-1247. doi: 10.16383/j.aas.2016.c150335
引用本文: 刘展杰, 陈晓云. 局部子空间聚类. 自动化学报, 2016, 42(8): 1238-1247. doi: 10.16383/j.aas.2016.c150335
shu
LIU Zhan-Jie, CHEN Xiao-Yun. Local Subspace Clustering. ACTA AUTOMATICA SINICA, 2016, 42(8): 1238-1247. doi: 10.16383/j.aas.2016.c150335
Citation: LIU Zhan-Jie, CHEN Xiao-Yun. Local Subspace Clustering. ACTA AUTOMATICA SINICA, 2016, 42(8): 1238-1247. doi: 10.16383/j.aas.2016.c150335
shu

局部子空间聚类

doi: 10.16383/j.aas.2016.c150335

  • 福州大学数学与计算机科学学院 福州 350116

基金项目: 

国家自然科学基金 71273053, 11571074

福建省自然科学基金 2014J01009

详细信息
    作者简介:

    刘展杰 福州大学数学与计算机科学学院硕士研究生.主要研究方向为数据挖掘,模式识别.E-mail:liufzu@gmail.com

    通讯作者:

    陈晓云 福州大学数学与计算机科学学院教授.主要研究方向为数据挖掘、模式识别.本文通信作者.E-mail:cxiaoyun@21cn.com

Local Subspace Clustering

  • College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116

Funds: 

National Natural Science Foundation of China 71273053, 11571074

Natural Science Foundation of Fujian Province 2014J01009

More Information
    Author Bio:

    Master student at the College of Mathematics and Computer Science, Fuzhou University. His research interest covers data mining and pattern recognition.E-mail:

    Corresponding author: CHEN Xiao-Yun Professor at the College of Mathematics and Computer Science, Fuzhou University. Her research interest covers data mining and pattern recognition.

HTML全文

    摘要
  • 摘要: 现有子空间聚类方法通常以数据全局线性为前提，将每个样本点表示为其他样本点的线性组合，因而导致常见子空间聚类方法不能很好地应用于非线性数据.为克服全局线性表示的局限，借鉴流形学习思想，用k近邻局部线性表示代替全局线性表示，与稀疏子空间聚类和最小二乘子空间聚类方法相结合，提出局部稀疏子空间聚类和局部最小二乘子空间聚类方法，统称局部子空间聚类方法.在双月形数据、6个图像数据集和4个基因表达数据集上进行实验，实验结果表明该方法是有效的.
    Abstract: Existing subspace clustering methods usually rest on a global linear data set, which expresses each data point as a linear combination of all other data points, and thus common methods are not well suited for the nonlinear data. To overcome this limitation, the local sparse subspace clustering and local least squares regression subspace clustering are proposed. The idea of the two new methods comes from manifold learning which expresses each data point as a linear combination of its k nearest neighbors, and is combined with sparse subspace clustering and least squares subspace clustering respectively. Experimental results show that our method is effective on two-moon synthetic data, six image data sets and four gene expression data sets.
    • HTML全文

  • 许多现实采样的数据特征复杂,呈非线性分布,变量之间存在高度非线性相关性.大部分情况下,图像数据被视为一种具有非线性结构的数据.因图像易受外界因素的干扰,使得数据具有很强的不确定性.例如人脸图像会受光照、表情和姿态等因素的影响,通常导致图像中的像素值发生非线性的变化.同样,现实中采集到的基因表达数据也常呈现出高维、小样本、多噪声和非线性等特征,且大部分数据不含类别信息,因此聚类技术作为一种典型无监督技术而被广泛使用.故本文从非线性角度研究图像数据和基因表达数据的聚类问题.

    近年来,子空间聚类作为一种热点聚类方法被广泛研究,并被应用到机器视觉领域,如图像分割领域[1]、动态分割领域[2]和人脸聚类领域[3];此外图像表达[4]和混合识别系统[5]等图像处理领域中,子空间聚类方法也被成功使用.目前,已有许多经典的子空间聚类算法被提出,如稀疏子空间聚类(Sparsesubspace clustering,SSC)[6]、 低秩表达(Low rankrepresentation,LRR)[7] 和最小二乘子空间聚类(Least squaresregression,LSR)[8] 等,三者都是基于谱聚类的子空间聚类算法.SSC可实现从全局角度自动选择近邻点,消除数据之间的相关性;LRR保持仿射矩阵的低秩性;LSR保持数据的聚集性.在这些方法基础之上改进得到鲁棒潜在低秩表达子空间聚类(Robustlatent low rank representation,RLLRR)[9]、光滑表达子空间聚类(Smooth representation clustering,SMR)[10]、 鲁棒SSC (Robust SSC,R-SSC)[11]、块对角SSC (Block-diagonal SSC,BD-SSC)和块对角LRR (Block-diagonalLRR,BD-LRR)[12]等.

    上述的大部分方法都以数据全局线性为前提,每个样本点可以利用其余样本点线性重构.从回归模拟角度来看,上述方法可看作线性回归模型.故SSC是LASSO (Least absolute shrinkageand selectionator operator)[13]的变形,LSR是岭回归 (Ridgeregression)[14]的变形.LASSO以l1范数作为惩罚项来压缩模型回归系数,l1范数在原点处不可导,通常采用迭代方法求解模型的回归系数.因求解会得到许多为0的回归系数,所对应的回归变量在线性回归模型中不起作用,以此达到压缩变量的目的[15]. 但对有较多变量的模型来说,压缩变量的效果会变差.岭回归是一种较稳定的连续型模型,但它不能压缩变量,这导致模型中变量过多,不能得到一个简单且解释性强的模型.对于线性相关程度大的数据,LASSO和岭回归的效果较好; 反之,这两种方法的回归效果较差.在子空间聚类方法中,SSC和LSR也保持着同样的优缺点.因此对于非线性数据,SSC和LSR的聚类效果不理想,如图 1 所示.

    图 1  在双月形数据上学习的邻接图
    Fig. 1  Learned adjacency graph on the two-moon synthetic data
    下载: 全尺寸图片 幻灯片

    图 1是LSR和SSC在双月形数据上学习得到的仿射矩阵画出的邻接图.由图 1(a)可见,LSR用除本身外的其余点做线性表示,不能将两类数据区分开.由图 1(b)中亦可见,SSC虽然能自动选取样本点进行线性表示,但样本点的选取不理想.可见LSR和SSC都不能达到图 1(c)的理想效果,二者不能够将两类数据准确地区分开,因此不适合对非线性数据进行聚类.

    流形学习是近年来处理流形数据和非线性数据的常用方法,许多经典流形学习方法被提出,如局部保持投影(Locality preservingprojections,LPP)[16]、 局部线性嵌入(Locally linearembedding,LLE)[17]和近邻保持嵌入(Neighborhood preservingembedding,NPE)[18]等. LPP、 LLE和NPE有一个共同点就是假设数据是局部线性的,每个样本点均可利用其近邻样本进行线性表示.同样,在聚类问题中,相互靠近的样本点往往被视为同类,这样便可以利用近邻点对数据线性表示.因此,受流形学习局部线性表示思想的启发,结合子空间聚类,本文提出局部子空间聚类算法(Local subspace clustering,LSC),并应用于图像和基因表达谱等具有明显非线性特征的高维数据.

    本文提出的局部子空间聚类利用样本点的k个近邻进行线性表示.值得注意的是:1) k近邻法的关键是近邻参数k的选取,本文提出的子空间聚类方法能够自适应地调整近邻点个数. 2) 通常采用k近邻法只选取适当少的近邻点,但局部子空间聚类算法既可以取适当少,也可以取适当多的近邻点.当选取适当少的近邻点时,可剔除大量样本点,计算便捷; 当选取适当多的近邻点时,可剔除一些噪声点,使算法更具鲁棒性.

    1.   子空间聚类

    子空间聚类目标是将样本数据分割或聚集成几个簇,每个簇对应一个子空间,因此也称为子空间分割.

    定义 1[8]. 子空间聚类(Subspace clustering):给定的从c个子空间{Si}i=1c采样的数据向量集合 $X=[{{X}_{1}},{{X}_{2}},\cdots ,{{X}_{c}}]=[{{x}_{1}},{{x}_{2}},\cdots ,{{x}_{n}}]\in {{\mathbf{R}}^{d\times n}},{{X}_{i}}$ 是从子空间Si中采样的ni个数据向量构成的集合,.子空间聚类的目标是根据它们采样的基子空间分割数据.

    子空间聚类算法根据表示方式不同可以粗略分为四类[8]:代数方法、 迭代方法、 统计方法和谱聚类方法,本文重点研究最后一种.基于谱聚类的子空间聚类方法核心在于求解仿射矩阵Z=(zij)n×n,zij用来度量两个样本xi 和xj的相似度.典型的相似度度量zij=exp(-||xi-xj||2/σ),σ>0不能很好地刻画数据的本质特征[8].稀疏子空间聚类SSC、低秩表达子空间聚类LRR和最小二乘回归子空间聚类LSR提出了新的仿射矩阵计算方法.这些方法将每个样本点xi表示为其他样本点的线性组合:

    $x_i=\sum_{jeq i}x_jz_{ij} $

    		(1)

    其中zij是表示权重的常数.利用表示系数(|zij|+|zji|)/2度量xi和xj之间的相似度.

    SSC的目标函数:

    $\begin{align} & \min_z \| Z \|_1\\ & {\rm s.t.} \quad X=XZ,\quad {\rm diag}{Z}=0 \end{align}$

    		(2)

    其中,||Z||1是Z的l1范数,定义为仿射矩阵Z的所有元素的绝对值之和.文献[6]还将SSC扩展到噪声模型,目标函数如下:

    $\begin{align} &\min_z \frac{\lambda}{2} \| X-XZ \|^2_F+ \| Z \|_1\\ & {\rm s.t.} \quad {\rm diag}{Z}=0 \end{align}$

    		(3)

    LSR最小化Z的Frobenius范数:

    $\begin{align} & \min_z \| Z \|^2_F\\ & {\rm s.t.} \quad X=XZ,\quad {\rm diag}{Z}=0 \end{align}$

    		(4)

    对于有噪声的模型,可以扩展为

    $\begin{align} &\min_z \| X-XZ \|^2_F+\lambda \| Z \|^2_F\\ & {\rm s.t.} \quad {\rm diag}{Z}=0 \end{align}$

    		(5)

    去除约束条件 ,扩展为

    $ \min_z \| X-XZ \|^2_F+\lambda \| Z \|^2_F$

    		(6)

    其中,λ >0,||Z||F是矩阵Z的Frobenius范数.

    2.   局部子空间聚类

    为解决子空间聚类方法不能直接应用于非线性图像数据的不足,本文引入k近邻局部线性表示思想,将其分别与经典子空间聚类方法SSC和LSR相结合,提出局部子空间聚类(Local subspace clustering,LSC),其中k近邻局部线性表示与LSR结合,命名为局部最小二乘回归子空间聚类(Local least squares regression,LLSR); 与SSC结合,命名为局部稀疏子空间聚类(Local sparse subspaceclustering,LSSC).

    2.1   局部最小二乘回归子空间聚类

    LLSR算法主要利用k近邻[18]求取k个近邻点,以局部线性为依据对数据进行线性表示.具体步骤如下:

    1) 以样本点间的欧氏距离作为相似性度量,距离越小表示样本相似性越高.样本点xi的k个近邻点(不包含自身)集用Nk(xi)={xi1,xi2,…,xik}表示.

    模型(3)和模型(5)中,对角为0的约束本质上是从样本点xi用除自身以外的样本点线性表示得来,即zii=0 (i=1,2,…,n),因此k个近邻点中不包含xi自身的目的是为保持模型中对角元素为0的约束.

    2) LLSR子空间聚类的目标函数为

    $ \min_z \sum_i {\| x_i-\sum_{x_j\in N_k(x_i)}x_jz_{ij} \|^2_F}+\lambda \| Z \|^2_F$

    		(7)

    其中若xj∉ Nk(xi),则令zij=0.由于每个xi相互独立,故上式亦可表示为

    $ \min_{\tilde{z}_i} \| x_i-N_k(x_i)\tilde{z}_{i} \|^2_F+\lambda \| \tilde{z}_i \|^2_F$

    		(8)

    利用最小二乘思想求解式(8),得到解析解为

    $\tilde{z}_i=(N_k(x_i)^{\rm T}N_k(x_i)+\lambda I)^{-1}N_k(x_i)^{\rm T}x_i $

    		(9)

    对于每个样本点xi,LLSR都可求解出一个解 ${{\tilde{z}}_{i}}$ .对任意 $i,z_{i{{i}_{m}}}^{*}={{\tilde{z}}_{i{{i}_{m}}}}\$,\$m=1,2,\cdots ,k$ ,其余为0,故可得到模型(7)的解Z*.

    2.2   局部稀疏子空间聚类

    由于近邻参数k值固定,不能根据样本点分布的疏密自主确定近邻点个数,导致第2.1节提出的LLSR方法存在局限,为此本节提出局部稀疏子空间聚类LSSC. LSSC利用l1范数具有稀疏的性质,在k近邻点选取过程中可自适应地调整近邻点个数.由于SSC与LSR的正则参数项位置不同,为了让正则参数项的作用统一,将SSC改写成:

    $ \min_z \frac{1}{2} \| X-XZ \|^2_F+\lambda \| Z \|_1$

    		(10)

    此式可利用交替方向乘子法(Alternating direction method ofmultipliers,ADMM)[19]的思想求解.本文的LSSC在式(10)上进行局部线性化改进,其算法步骤与LLSR相同.先选取每个样本点 的k个近邻点,再从近邻点中二次筛选,自动调整近邻. LSSC目标函数如下:

    $ \min_z \frac{1}{2} \sum_i {\| x_i-\sum_{x_j\in N_k(x_i)}x_jz_{ij} \|^2_F}+\lambda \| Z \|_1$

    		(11)

    其中,若xjotin Nk(xi),则令zij=0.同样,每个xi相互独立,故式(11)亦可为

    $ \min_{\tilde{z}_i} \frac{1}{2} \| x_i-N_k(x_i){\tilde{z}_i} \|^2_F+\lambda \| {\tilde{z}_i} \|_1$

    		(12)

    此目标函数与LASSO的回归模型等价,利用ADMM,目标函数(12)转化为

    $\begin{align} &\min_{\tilde{z}_i}\frac{1}{2} \| x_i-N_k(x_i)\tilde{z}_i \|^2_F+\lambda \| \beta \|_1\\ & {\rm s.t.} \quad \tilde{z_i}-\beta=0 \end{align}$

    		(13)

    其中β是对偶变量.进一步可写成:

    $\begin{align} & \min_{\tilde{z}_i,\beta,U} \frac{1}{2} \|x_i-N_k(x_i)\tilde{z}_i\|^2_F+\lambda \| \beta \|_1+\\ & \quad\quad \|\frac{\rho}{2}\| \tilde{z}_i-\beta-U \|^2_F \end{align}$

    		(14)

    其中ρ是拉格朗日乘子,在实验中设为常数1,U是对偶变量.模型(14)的ADMM步骤如下:

    $\begin{align} & {\tilde{z}_i}^{K+1}:=(N_k(x_i)^{\rm T}N_k(x_i)+\rho I)^{-1}(N_k(x_i)x_i+\\ & \quad\quad \quad \quad \rho \beta^K-U^K)\\ & \beta^{K+1}:=S_{\frac{\lambda}{\rho}}({\tilde{z}_i}^{K+1}+\frac{U^K}{\rho}) \\ & U^{K+1}:=U^K+\rho(\tilde{z}_i^{K+1}-\beta^{K+1})\end{align}$

    		(15)

    其中K是更新次数, ${{S}_{\alpha }}(v)={{(v-\alpha )}_{+}}-{{(-v-\alpha )}_{+}}$ ,具体算法参见文献[19],由此可求得 ${{\tilde{z}}_{i}}$ .对任意i,在相应位置上 $z_{i{{i}_{m}}}^{*}={{\tilde{z}}_{i{{i}_{m}}}},m=1,2,\cdots ,k$ ,其余为0,可得到LSSC 模型(11)的解矩阵Z*.

    2.3   局部子空间聚类算法

    类似于SSC、LRR和LSR,局部子空间聚类算法LSC也是基于谱聚类的子空间聚类方法. LSC算法如下:

    算法 1. 局部子空间聚类算法

    输入. 数据矩阵X,正则参数λ,近邻点个数k,类数c.

    输出. c个类簇.

    1) 利用k近邻求每个样本点的k个近邻;

    2) 通过LLSR目标函数(7)或LSSC目标函数(11)求解矩阵Z*;

    3) 计算仿射矩阵(|Z*|+|(Z*)T|)/2;

    4) 应用标准分割方法[20]将数据分成c个子空间.}

    值得注意的是,文献[8]证明了LSR具有聚集性,同样我们可以证明LLSR具有局部聚集性.

    定理 1. 给定向量y∈ Rd ,矩阵Nk(y)∈ Rd× k和参数λ >0,假设Nk(y)={y(1),y(2),…,y(k)}已经按列标准化,z*是如下LLSR 问题的解:

    $ \min_z \| y-N_k(y)z^* \|^2_2+\lambda \| z \|^2_2$

    		(16)

    那么

    $\frac{\| z^*_{(i)}-z^*_{(j)} \|_2}{\| y \|_2}\leq\frac{1}{\lambda}\sqrt{2(1-r)} $

    		(17)

    其中r=y(i)T y(j)是样本相关系数.

    证明 . 令 $L(z)=\|y-{{N}_{k}}(y){{z}^{*}}\|_{2}^{2}+\lambda \|z\|_{2}^{2}$ ,且

    $ \frac{\partial L(z^*)}{\partial z_k}=0$

    		(18)

    有:

    $-2y_{(i)}^{\text{T}}(y-{{N}_{k}}(y){{z}^{*}})+2\lambda z_{(i)}^{*}=0$

    		(19)

    $-2y^{\rm T}_{(j)}(y-N_k(y)z^* )+2\lambda z^*_{(j)}=0 $

    		(20)

    由式(19)和式(20)得

    $z^*_{(i)}-z^*_{(j)}=\frac{1}{\lambda}(y^{\rm T}_{(i)}-y^{\rm T}_{(j)})(y-N_k(y)z^* ) $

    		(21)

    且Nk(y)已经按列标准化,r=y(i)T y(j),得

    $\| y_{(i)}-y_{(j)} \|_2=\sqrt{2(1-r)} $

    		(22)

    又因为z*是问题(16)的最优解,得

    $\| y-N_k(y)z^* \|^2_2 +\lambda \| z^* \|^2_2=L(z^*)\leq L(0)=\| y\|^2_2 $

    		(23)

    因此 ,结合式(21)和式(22)可得

    $\frac{\| z^*_{(i)}-z^*_{(j)} \|_2}{\| y \|_2}\leq\frac{1}{\lambda}\sqrt{2(1-r)} $

    		(24)

    定理 1 证明了LLSR的局部聚集能力.假如y(i)和y(j)是高度相关的,如r=1,则定理1表明y(i)和y(j)对应的系数z(i)和z(j)的差异性接近为0,这样y(i)和y(j)就会聚成相同的簇.

    3.   实验

    为验证局部子空间聚类方法的有效性,本节选用经典聚类方法:K均值(K-means)、层次聚类方法(Hierarchical clustering,HC),以及子空间聚类方法: SSC[6]、 LRR[7]、LSR[8]、 BD-LRR[12]、RLLRR[9]和SMR[10],与本文提出的LLSR和LSSC进行比较,并从聚类准确率(Accuracy,ACC)[21]的角度对比各种方法的聚类能力,其中ACC 定义如下:

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

    $ACC=\frac{\sum\limits_{i=1}^{n} \delta(s_i,map(r_i))}{n} $

    		(25)

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

    本文采用双月形数据、图像数据集和基因表达数据集,其中图像数据集包括:ORL10P1、 PIX10P1、PIE10P1、Umist[22]、 USP-S[10]、COIL202;基因数据集3包括: Leukemia1、 SRBCT、 Lung_Cancer、 Prostate_Tumor. 在参数设置方面,LRR、 LSR和LLSR的正则参数λ取值为 {0.0001,0.001,0.005,0.01,0.05,0.1,0.5,1,10}, SSC和LSSC的λ取值为 {0.0001,0.001,0.005,0.01,0.05,0.1}; BD-LRR、 RLLRR和SMR的参数取 {0.08,0.1,0.5,1,5,10,50,100,500,1000};近邻点个数k取3~10.每个算法运行10次,取聚类准确率的平均值.本文的实验环境为Winows 7系统,内存4GB和i5处理器,所有方法都用Matlab2012b编程实现.

    3.1   人造数据

    利用人造双月形实验数据说明LSC的有效性,同时展示近邻点k值和正则参数λ的选取对聚类准确率的影响.

    双月形数据是由两类数据组成的非线性数据,形状如两个弯月,如图 2所示.我们的目标是希望能找到一个好的仿射矩阵,将数据准确地分成两类.利用LLSR和LSSC学习得到的邻接图如图 3所示.

    图 2  双月形数据
    Fig. 2  The two-moon synthetic data
    下载: 全尺寸图片 幻灯片
    图 3  LSC在双月形数据学习得到的邻接图
    Fig. 3  Learned adjacency graph by LSC on the two-moon synthetic data
    下载: 全尺寸图片 幻灯片

    结合图 1和图 3,易知LLSR和LSSC能够很好地将两类数据分开,便于聚类.比较图 3中LLSR 和 LSSC的邻接图,后者以稀疏为目的能够自动筛选近邻点,故邻接边较少.表 1给出各对比方法在双月形数据上的聚类准确率(参数)和运行时间.由表 1可以看出LLSR和LSSC很大程度地提升了聚类准确率,二者均能达到100\%的准确率,而其余方法基本在50\%左右.比较SSC和LSSC运行时间可以看出,LSSC利用局部线性的思想明显提升了运行速度. LSSC和LLSR的运行时间包括近邻点计算的耗时. 得的仿射矩阵效果并不理想; 反观,LLSR和LSSC两种方法都能得到对角形式的仿射矩阵,且LSSC能得到更稀疏的仿射矩阵.综上,对于双月形数据,原有LSR和SSC方法受全局线性限制,不能得到理想结果,而局部子空间聚类LSC的两种方法利用局部线性思想得到较好的结果,更好地解决非线性数据的聚类问题.

    表 1  双月形数据上聚类准确率(%)和运行时间(s)的对比
    Table 1  Clustering accuracy (%) and running time (s)comparison on the two-moon synthetic data
    HC K-meansLRR SSC LSR BD-LRRRLLRRSMRLSSCLLSR
    ACC100.0072.0053.5053.50 50.0050.00 52.0051.50100.00100.00
    (0.001)(0.005)(0.0001)(0.08)(0.1)(0.001) (0.0001,5)(0.0001,5)
    Time 0.00100.00261.894.80 0.0008 19.150.330.0450.94 0.10
    下载: 导出CSV 
    | 显示表格

    图 4给出LSR、 SSC、 LLSR和LSSC四种方法的仿射矩阵图.对于双月形数据,LSR和SSC所

    图 4  双月形数据上的仿射矩阵
    Fig. 4  The affinity matrixes on the two-moon synthetic data
    下载: 全尺寸图片 幻灯片

    在双月形数据实验中研究正则参数λ和近邻点k的选取对聚类准确率的影响,结果如图 5所示.

    图 5  在双月形数据上LSC的参数学习
    Fig. 5  Study on the LSC's parameters on the two-moon synthetic data
    下载: 全尺寸图片 幻灯片

    由图 5(a)可知,将LSR和SSC应用在非线性数据上,正则参数λ的改变不会使聚类准确率发生较大变化; 而对于LLSR,由于采用局部线性思想,相当于在很大程度上剔除了许多不相关点,因此λ 的变化也不会影响其聚类准确率; LSSC也是如此,在大部分λ取值下,得到的结果是稳定的,但当λ取值越大时,l1 范数的作用越大,会导致最终获得的近邻点减少,甚至近邻点个数为0,得到的仿射矩阵为0矩阵,影响了聚类准确率.所以,图 5(a)中SSC和LSSC在取较大正则参数时,聚类准确率均发生下降,甚至在过大的正则参数下无法进行有效聚类.图 5(b)显示近邻点个数的变化会导致聚类准确率的变化,当k取过小或过大,都会使得聚类准确率降低,当k取5~7时,LLSR和LSSC会得到较好的结果. LLSR整体上比LSSC更稳定,有更高的聚类准确率.在选取近邻点时,LSSC的k值一般比LLSR小.且实验中发现,LSSC虽然能自动调整近邻点,但当近邻点数k过大时,l1 范数自动调整近邻点的效果变差.

    3.2   图像数据

    本实验采用的6个图像数据中,前4个是人脸图像数据,第5个是手写数字图像数据,第6个为物品数据.数据集描述如表 2.且图 6列出6个图像数据集中的部分样本图像.

    表 2  数据集描述
    Table 2  Summary of the data sets
    数据集样本长宽类别
    ORL10P1001129210
    PIX10P10010010010
    PIE10P210554410
    Umist575282320
    USPS1 000161610
    COIL201 440323220
    下载: 导出CSV 
    | 显示表格
    图 6  部分样本图像
    Fig. 6  Sample images
    下载: 全尺寸图片 幻灯片
    3.2.1   聚类准确率

    实验时,使用PCA统一将6个图像数据降至60维.实验结果如表 3.

    表 3  聚类准确率
    Table 3  Clustering accuracy (%)
    HCK-meansLRRSSCLSRBD-LRRRLLRRSMRLSSCLLSR
    ORL10P41.0073.4079.0071.0083.0070.3074.7078.0086.0087.00
    PIX10P77.0079.9087.0086.0085.0076.8056.1088.0096.0097.00
    PIE10P70.9532.95100.0090.0090.0080.0079.43100.0098.57100.00
    Umist45.5747.5852.1761.5752.3548.3550.9669.9176.8774.09
    USPS10.9073.1478.6060.8071.3063.9065.5077.1081.2091.20
    COIL2053.4760.1065.6972.0163.4067.7268.8067.1578.2679.58
    下载: 导出CSV 
    | 显示表格

    由表 3可知,局部子空间聚类方法 LLSR 和 LSSC利用局部线性思想,在所有测试数据集上都取得最好结果.在大部分图像数据中,LSC的聚类准确率提高明显.对比两种不同的局部子空间聚类方法可以发现:LLSR的聚类准确率除Umist 数据集外均优于LSSC,较好地改进了最小二乘子空间聚类算法.值得注意的是,在PIE10P实验中,其他传统子空间聚类方法也取得90\%以上较高的聚类准确率,说明该数据集的线性相关度非常高,因此k 值选取较大,局部近邻点几乎包括全部样本数据.由此可见LSC还具有剔除噪声点的作用.在其余5个数据集中,近邻点k都在5~7之间.实验结果表明局部子空间聚类方法能更好地处理具有非线性特征的图像数据,可以更好地反映图像数据的本质结构.

    3.2.2   运行时间

    表 4给出几种对比算法的运行时间,数据集按样本数由少到多排列.由表 4可以看出随着样本数的增大,各算法的运行时间也相应增加.几种子空间聚类方法中LSR速度最快,最慢的方法是SSC.在大部分实验中,LSC的两个方法会比SSC、 LRR、BD-LRR和RLLRR快.特别是由SSC改进而来的LSSC,仅选取少数近邻点学习仿射矩阵,其计算量明显减少,因此运行时间比SSC节省很多,且随着数据集规模的增大,LSSC较之SSC的优势也更明显.

    表 4  运行时间的对比(s)
    Table 4  Running time (s) comparison
    HCK-meansLRRSSCLSRBD-LRRRLLRRSMRLSSCLLSR
    ORL10P0.00110.00710.540.210.000787.291.690.0140.140.034
    PIX10P0.000950.00621.040.330.000737.601.720.0121.250.035
    PIE10P0.00230.0114.512.530.001522.232.140.0570.320.13
    Umist0.0110.03725.1462.270.015240.7013.480.711.520.92
    USPS0.0340.091130.61124.570.044884.42120.334.533.572.75
    COIL200.0720.071423.542.511446.67926.78134.8618.9218.975.69
    下载: 导出CSV 
    | 显示表格
    3.2.3   PCA对聚类准确率的影响

    PCA是一种线性降维方法,使得数据在降维后既能尽量保持原有数据信息,又能使算法更快运行,因此被广泛使用.由于图像高维性的限制,若直接采用原始图像数据会因计算机内存不足而导致算法无法执行,故本实验先对图像数据进行PCA降维.针对本文提出的局部子空间聚类算法,讨论PCA降维对局部子空间聚类算法的影响.分别将6个图像数据集降至20,40,60和80维,实验结果如图 7.

    图 7  PCA对不同图像数据和算法的影响
    Fig. 7  PCA on the image data and algorithms
    下载: 全尺寸图片 幻灯片

    图 7中LSSC和LLSR取固定的近邻数 k (k=5).由图 7可知,在数据为20,40,60和80维时,LLSR和LSSC 大部分都能取得最好的结果.SSC在大部分维数高的情况下,聚类准确率反而下降,而LSSC与SSC相反; LLSR不随维数的变化而产生大变化,说明其是一种比较稳定的算法.图 7(d)是侧脸渐变数据,正脸与侧脸的样本数据差异较大; 用原始SSC和LSR算法所得的聚类准确率不高,说明该数据全局线性相关性不强,而LSSC和LLSR的聚类准确率会随着维数的增高而增加.

    3.3   基因数据

    实验时,用PCA统一将4个基因表达数据降至60维.4个基因数据主要信息如表 5所示.

    表 5  数据集描述
    Table 5  Summary of the data sets
    数据集样本基因类别
    Leukemia1725 3273
    SRBCT832 3084
    Lung_Cancer20312 6005
    Prostate_Tumor10210 5092
    下载: 导出CSV 
    | 显示表格

    由表 6给出的各类算法的聚类准确率可知,在4个基因表达数据集上,局部子空间聚类方法LLSR和LSSC都取得最好的聚类效果.且在大部分数据集上,LLSR和LSSC的聚类准确率比其他方法提高10%.一般情况下参数设置为k取5到7.特别对于Lung_Cancer数据,LSR的聚类准确率达92%,这说明数据全局线性相关,故选取较大k值.实验结果表明,局部子空间聚类方法在基因表达数据上也能取得更好的聚类结果.

    表 6  聚类准确率(%)
    Table 6  Clustering accuracy (%)
    HCK-meansLRRSSCLSRBD-LRRRLLRRSMRLSSCLLSR
    Leukemia154.1769.3186.1158.3377.7879.1754.1777.7890.2890.28
    SRBCT36.1453.7368.4340.1254.2260.2446.9963.6874.7074.46
    Lung_Cancer78.3383.5087.3983.7492.6185.2284.2490.6491.6392.61
    Prostate_Tumor51.9663.7362.7556.8662.7560.7860.7859.8066.6769.61
    下载: 导出CSV 
    | 显示表格

    3.4   参数选择

    LSC模型有两个参数: 正则参数 和近邻数k. 从图 5(a)可以看出, LSC聚类准确率对参数λ的变化不敏感,主要因为剔除大量不相关样本点,使得参数λ对实验结果的影响减弱,但还是建议将λ选在0.001~0.1之间.因为λ过大,LSSC求出的仿射矩阵将是0矩阵.另一个参数k通常取5~7之间能取得理想结果,大部分情况下k过大或过小可能导致准确率降低;而对于线性相关程度较大的数据,k 值可取较大值,这样可起到剔除噪声点的作用.综上,对于大部分数据集,λ取0.001~0.1 且k取5~7 时,LSC会得到较为理想的聚类结果.

    4.   结论

    考虑到实际应用中很多数据具有非线性特征,将k近邻局部线性表示引入子空间聚类,分别提出LSSC 和LLSR两种局部子空间聚类算法,两种算法均能较好克服原有算法全局线性的局限,较好地应用于非线性数据.同时,证明了LLSR模型具有局部聚集性,能够聚集局部样本.在图像数据和基因表达数据的实验中,发现LSSC 和LLSR均优于传统子空间聚类方法和其他对比方法,不仅在聚类准确率上有较大提高,且在运行时间上LSSC也取得明显改进.研究中发现LLSR和LSSC的聚类效果受k值影响,如何高效选取近邻数k将在以后的研究中给出.

  • 图  1  在双月形数据上学习的邻接图

    Fig.  1  Learned adjacency graph on the two-moon synthetic data

    下载: 全尺寸图片 幻灯片

    图  2  双月形数据

    Fig.  2  The two-moon synthetic data

    下载: 全尺寸图片 幻灯片

    图  3  LSC在双月形数据学习得到的邻接图

    Fig.  3  Learned adjacency graph by LSC on the two-moon synthetic data

    下载: 全尺寸图片 幻灯片

    图  4  双月形数据上的仿射矩阵

    Fig.  4  The affinity matrixes on the two-moon synthetic data

    下载: 全尺寸图片 幻灯片

    图  5  在双月形数据上LSC的参数学习

    Fig.  5  Study on the LSC's parameters on the two-moon synthetic data

    下载: 全尺寸图片 幻灯片

    图  6  部分样本图像

    Fig.  6  Sample images

    下载: 全尺寸图片 幻灯片

    图  7  PCA对不同图像数据和算法的影响

    Fig.  7  PCA on the image data and algorithms

    下载: 全尺寸图片 幻灯片

    表  1  双月形数据上聚类准确率(%)和运行时间(s)的对比

    Table  1  Clustering accuracy (%) and running time (s)comparison on the two-moon synthetic data

    HC K-meansLRR SSC LSR BD-LRRRLLRRSMRLSSCLLSR
    ACC100.0072.0053.5053.50 50.0050.00 52.0051.50100.00100.00
    (0.001)(0.005)(0.0001)(0.08)(0.1)(0.001) (0.0001,5)(0.0001,5)
    Time 0.00100.00261.894.80 0.0008 19.150.330.0450.94 0.10
    下载: 导出CSV

    表  2  数据集描述

    Table  2  Summary of the data sets

    数据集样本长宽类别
    ORL10P1001129210
    PIX10P10010010010
    PIE10P210554410
    Umist575282320
    USPS1 000161610
    COIL201 440323220
    下载: 导出CSV

    表  3  聚类准确率

    Table  3  Clustering accuracy (%)

    HCK-meansLRRSSCLSRBD-LRRRLLRRSMRLSSCLLSR
    ORL10P41.0073.4079.0071.0083.0070.3074.7078.0086.0087.00
    PIX10P77.0079.9087.0086.0085.0076.8056.1088.0096.0097.00
    PIE10P70.9532.95100.0090.0090.0080.0079.43100.0098.57100.00
    Umist45.5747.5852.1761.5752.3548.3550.9669.9176.8774.09
    USPS10.9073.1478.6060.8071.3063.9065.5077.1081.2091.20
    COIL2053.4760.1065.6972.0163.4067.7268.8067.1578.2679.58
    下载: 导出CSV

    表  4  运行时间的对比(s)

    Table  4  Running time (s) comparison

    HCK-meansLRRSSCLSRBD-LRRRLLRRSMRLSSCLLSR
    ORL10P0.00110.00710.540.210.000787.291.690.0140.140.034
    PIX10P0.000950.00621.040.330.000737.601.720.0121.250.035
    PIE10P0.00230.0114.512.530.001522.232.140.0570.320.13
    Umist0.0110.03725.1462.270.015240.7013.480.711.520.92
    USPS0.0340.091130.61124.570.044884.42120.334.533.572.75
    COIL200.0720.071423.542.511446.67926.78134.8618.9218.975.69
    下载: 导出CSV

    表  5  数据集描述

    Table  5  Summary of the data sets

    数据集样本基因类别
    Leukemia1725 3273
    SRBCT832 3084
    Lung_Cancer20312 6005
    Prostate_Tumor10210 5092
    下载: 导出CSV

    表  6  聚类准确率(%)

    Table  6  Clustering accuracy (%)

    HCK-meansLRRSSCLSRBD-LRRRLLRRSMRLSSCLLSR
    Leukemia154.1769.3186.1158.3377.7879.1754.1777.7890.2890.28
    SRBCT36.1453.7368.4340.1254.2260.2446.9963.6874.7074.46
    Lung_Cancer78.3383.5087.3983.7492.6185.2284.2490.6491.6392.61
    Prostate_Tumor51.9663.7362.7556.8662.7560.7860.7859.8066.6769.61
    下载: 导出CSV
    • 参考文献(22)
  • [1] Yang A Y, Wright J, Ma Y, Sastry S S. Unsupervised segmentation of natural images via lossy data compression. Computer Vision and Image Understanding, 2008, 110(2):212-225 doi: 10.1016/j.cviu.2007.07.005
    [2] Vidal R, Tron R, Hartley R. Multiframe motion segmentation with missing data using power factorization and GPCA. International Journal of Computer Vision, 2008, 79(1):85-105 doi: 10.1007/s11263-007-0099-z
    [3] 王卫卫, 李小平, 冯象初, 王斯琪. 稀疏子空间聚类综述. 自动化学报, 2015, 41(8):1373-1384 http://www.aas.net.cn/CN/abstract/abstract18712.shtml

    Wang Wei-Wei, Li Xiao-Ping, Feng Xiang-Chu, Wang Si-Qi. A survey on sparse subspace clustering. Acta Automatica Sinica, 2015, 41(8):1373-1384 http://www.aas.net.cn/CN/abstract/abstract18712.shtml
    [4] Hong W, Wright J, Huang K, Ma Y. Multiscale hybrid linear models for lossy image representation. IEEE Transactions on Image Processing, 2006, 15(12):3655-3671 doi: 10.1109/TIP.2006.882016
    [5] Vidal R, Favaro P. Low rank subspace clustering (LRSC). Pattern Recognition Letters, 2014, 43:47-61 doi: 10.1016/j.patrec.2013.08.006
    [6] Elhamifar E, Vidal R. Sparse subspace clustering. In:Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Miami, FL, USA:IEEE, 2009.2790-2797 https://www.computer.org/csdl/proceedings/cvpr/2009/3992/00/index.html
    [7] Liu G C, Lin Z C, Yu Y. Robust subspace segmentation by low-rank representation. In:Proceedings of the 27th International Conference on Machine Learning (ICML). Haifa, Israel, 2010.663-670
    [8] Lu C Y, Min H, Zhao Z Q, Zhu L, Huang D S, Yan S C. Robust and efficient subspace segmentation via least squares regression. In:Proceedings of the 12th European Conference on Computer Vision (ECCV). Florence, Italy:Springer, 2012.347-360
    [9] Zhang H Y, Lin Z C, Zhang C, Cao J B. Robust latent low rank representation for subspace clustering. Neurocomputing, 2014, 145:369-373 doi: 10.1016/j.neucom.2014.05.022
    [10] Hu H, Lin Z C, Feng J J, Zhou J. Smooth representation clustering. In:Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Columbus, OH, USA:IEEE, 2014.3834-3841
    [11] Soltanolkotabi M, Elhamifar E, Candés E J. Robust subspace clustering. The Annals of Statistics, 2014, 42(2):669-699 doi: 10.1214/13-AOS1199
    [12] Feng J S, Lin Z C, Xu H, Yan S C. Robust subspace segmentation with block-diagonal prior. In:Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Columbus, OH, USA:IEEE, 2014.3818-3825
    [13] Tibshirani R. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological), 1996, 58(1):267-288 http://cn.bing.com/academic/profile?id=2135046866&encoded=0&v=paper_preview&mkt=zh-cn
    [14] Hoerl A E, Kennard R W. Ridge regression:biased estimation for nonorthogonal problems. Technometrics, 1970, 12(1):55-67 doi: 10.1080/00401706.1970.10488634
    [15] Fan J Q, Li R Z. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, 2001, 96(456):1348-1360 doi: 10.1198/016214501753382273
    [16] Lee S R, Heo G S, Lee C Y. Representation and symbolization of motion captured human action by locality preserving projections. Applied Mathematics & Information Sciences, 2014, 8(1):441-446 http://cn.bing.com/academic/profile?id=2324349122&encoded=0&v=paper_preview&mkt=zh-cn
    [17] Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding. Science, 2000, 290(5500):2323-2326 doi: 10.1126/science.290.5500.2323
    [18] Tang Y Y, Yuan H L, Li L Q. Manifold-based sparse representation for hyperspectral image classification. IEEE Transactions on Geoscience and Remote Sensing, 2014, 52(12):7606-7618 doi: 10.1109/TGRS.2014.2315209
    [19] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 2011, 3(1):1-122 http://cn.bing.com/academic/profile?id=2164278908&encoded=0&v=paper_preview&mkt=zh-cn
    [20] Shi J B, Malik J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8):888-905 doi: 10.1109/34.868688
    [21] Cai D, He X F, Wu X Y, Han J W. Non-negative matrix factorization on manifold. In:Proceedings of the 8th IEEE International Conference on Data Mining (ICDM). Pisa:IEEE, 2008.63-72
    [22] Hou C P, Nie F P, Yi D Y, Tao D C. Discriminative embedded clustering:a framework for grouping high-dimensional data. IEEE Transactions on Neural Networks and Learning Systems, 2015, 26(6):1287-1299 doi: 10.1109/TNNLS.2014.2337335
    • 相关文章
    • 施引文献
  • 资源附件(0)
  • 加载中
图(7) / 表(6)
计量
  • 文章访问数:  2616
  • HTML全文浏览量:  793
  • PDF下载量:  1168
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-05-29
  • 录用日期:  2015-11-26
  • 刊出日期:  2016-08-01

目录

摘要
HTML全文

  • 1.   子空间聚类

  • 2.   局部子空间聚类

  • 2.1   局部最小二乘回归子空间聚类

  • 2.2   局部稀疏子空间聚类

  • 2.3   局部子空间聚类算法

  • 3.   实验

  • 3.1   人造数据

  • 3.2   图像数据

  • 3.3   基因数据

  • 3.4   参数选择

  • 4.   结论

参考文献(22)
相关文章
施引文献
资源附件(0)

/

返回文章
返回

版权所有 © 《自动化学报》编辑部  京ICP备14019135号-6

地址：北京中关村东路95号邮政编码：100190E-mail：aas_editor@ia.ac.cn

电话：010-82544677 (日常咨询和稿件处理)，010-82544653(费用管理、寄刊)

本系统由 北京仁和汇智信息技术有限公司 开发 技术支持： info@rhhz.net   百度统计