稀疏样本自表达子空间聚类算法

林大华,杨利锋,邓振云,李永钢,罗

(1.广西电化教育馆，广西 南宁 530022； 2.广西师范大学 广西多源信息挖掘与安全重点实验室，广西 桂林 541004)



稀疏样本自表达子空间聚类算法

林大华1,杨利锋2,邓振云2,李永钢2,罗2

(1.广西电化教育馆，广西 南宁 530022； 2.广西师范大学 广西多源信息挖掘与安全重点实验室，广西 桂林 541004)

针对现有子空间聚类算法在构造相似度矩阵时，没有同时利用样本自表达和稀疏相似度矩阵以及去除噪音、离群点的干扰相结合，提出了一种新的稀疏样本自表达子空间聚类方法。该方法通过样本自表达而充分利用样本间固有相关性的本质，创新性地同时使用L1-范数和L2,1-范数正则化项惩罚相似度矩阵，即对所有测试样本进行稀疏样本自表达，从而确保每个测试样本由与其相关性强的样本表示，并使所获得的相似度矩阵具有良好的子空间结构和鲁棒性。通过Hopkins155和人脸图像等大量数据集的实验结果表明，本文方法在实际数据的子空间聚类中能够获得非常好的效果。

子空间聚类; 谱聚类; 子空间结构; 相似度矩阵; 样本自表达

近几年来，子空间聚类[1]方法作为一种实现高维数据聚类的有效途径，在机器学习、图像处理和计算机视觉等领域已得到广泛应用。其中基于稀疏表示(sparse representation)和低秩表示(low-rank representation)的子空间聚类方法，通过与图划分的谱聚类方法相结合，在运动图像分割、人脸识别等高维数据的聚类方面得到了较好的效果。

子空间聚类又称子空间分割是指把数据的原始特征空间分割为不同的特征子集，从不同的子空间角度考察各个样本聚类划分的意义，同时在聚类过程中为每个样本寻找相应的特征子空间。目前实现子空间聚类的方法主要归为以下4类：基于代数的，如GPCA算法[2]；基于迭代的，如K-subspaces[3]；基于统计的，如PCA和RANSAC算法[4]；以及基于谱聚类的，如SSC(sparse subspace clustering)[5]，LRR(low-rank representation)[6]和LSR(least squares regression)[7]算法等。其中，基于谱聚类的子空间聚类算法利用样本的局部或全局信息去构建一个相似度矩阵，然后通过谱聚类算法对样本进行聚类。该类方法能较好地处理具有噪音和离群点的数据，不需要事先知道子空间的个数以及维数，因此在手写体识别、人脸识别以及运动分割等多个应用领域获得非常好的效果。

目前比较流行的算法有基于谱聚类的SSC和LRR算法，它们主要是对每个样本都找到一组稀疏或低秩的线性表示去构建相似度矩阵，然后利用谱聚类得到最终的结果。其中，SSC算法能够很好地结合样本自表达和稀疏相似度矩阵，通过稀疏相似度矩阵可使每个样本由与其相似性很强的一些样本表示，这些具有强相似性的样本往往在同一个子空间里，所以具有一定稀疏性的相似度矩阵往往可以提高子空间聚类的效果。但是，在数据的信噪比小、子空间不相互独立的情况时，该方法的聚类效果就不是很好。而LRR算法可以很好地使样本自表达和去除噪音、离群点相结合，但是其通过低秩表示构造的相似度矩阵往往不稀疏，没有很好地利用样本间的强相关性，这会影响子空间聚类的效果。

因此，合理地结合利用样本自表达和稀疏相似度矩阵以及去除噪音、离群点的干扰，能够实现构造一个良好的相似度矩阵而获得更好的子空间聚类效果的目的。所以，本文提出的方法首先从样本之间的相关性出发，对所有测试样本进行样本自表达，并同时通过L1-norm和L2,1-norm正则化项惩罚相似度矩阵，进行稀疏约束得到全局最优的相似度矩阵。然后，利用谱聚类得到最终的子空间聚类结果。在样本自表达过程中，L1-norm正则化项用来实现相似度矩阵的稀疏，确保每个测试样本都由与之相关性强的样本表示，能很好地解决样本自表达和稀疏相似度矩阵相结合的问题；而L2,1-norm通过控制相似度矩阵的行稀疏解决噪音和离群点的干扰，使其具有更好的鲁棒性，最终可以实现样本自表达和稀疏相似度矩阵以及去除噪音、离群点的干扰相结合，提高子空间聚类的效果。本文将所提出的方法称为稀疏样本自表达子空间聚类算法，简称为SSR_SC(sparse sample self-representation for subspace clustering)。

1 相关理论

高维数据一般可由多个低维结构表示，且具有很强相似度的样本往往在同一低维结构里，否则在不同的结构。每个低维结构对应为一个子空间，所以对数据的聚类可以通过对子空间的划分来聚类，即子空间聚类。

目前基于谱聚类的子空间聚类算法的主要步骤是：1)根据子空间策略构造样本集的相似度矩阵S；2)通过计算相似度矩阵或拉普拉斯矩阵的前k个特征值与特征向量，构建特征向量空间；3)利用K-means算法对特征向量空间中的特征向量进行聚类，从而实现子空间的聚类。由上述的过程可知，该类方法的主要挑战就是构造一个良好的相似度矩阵S。而通过一个良好矩阵S得到的子空间的特征表现为：子空间内的样本具有高度的相似性，不同子空间的样本不相似或差异性大，且所有子空间呈块对角化结构[8]。

因此，本文提出了SSR_SC算法，充分利用样本间的相关性进行样本自表达，并通过L1-norm和L2,1-norm正则化项对相似度矩阵进行稀疏约束，从而能很好地实现构造一个良好的相似度矩阵的目的。

2 SSR_SC算法

对于样本空间X中的一个样本x，用同一空间中的其他样本对x进行线性表示的过程称为样本自表达。同一子空间中的样本之间往往具有很强的相关性，不同子空间的样本之间为无相关性或弱相关性，所以通过样本自表达能很好地利用样本之间的相关性来提高子空间聚类的效果。假设样本空间为X=[x1x2…xn]∈Rd×n，其中n为样本数，xi(i=1,2,…,n)为具有d维属性的样本点。根据上述样本自表达的定义，即找出这样一个列向量zi∈Rn×1，使得xi可以通过Xzi表示。

但是样本空间X中往往存在噪音和离群点等干扰，其用e表示，则xi=Xzi+e，而这些干扰通常会影响子空间聚类的效果。因此本文算法希望找到这样一个相似度矩阵Z=[z1z2…zn]∈Rn×n，使得X与XZ的误差尽可能小。这通常可采用岭回归(ridge regression)实现：

假定通过目标函数(2)得到如下矩阵Z，其中diag(Z)=0，表明样本不能将自身作为相关性样本进行线性表示。

本文提出的SSR_SC算法的具体步骤如下：

算法1SSR_SC算法

输入参数λ1和λ2，以及样本空间：

X=[x1x2…xn]∈Rd×n。

输出聚类结果C∈Rn×1。

3)利用谱聚类算法得到最终的聚类结果C∈Rn×1。

3 目标函数优化

目标函数(2)是一个凸函数，但是L1-norm和L2,1-norm是非光滑的，无法直接求得解析解。为此，本文提出了一种有效的优化算法来解决这个问题，最后解出目标函数的最优化结果。

对目标函数(2)中的Z的每一行Zi求导,然后令其为0，得到式(3)

算法2目标函数优化算法

输入数据集X；

输出Z(t)∈Rn×n；

初始化Z(1)∈Rn×n，t=1；

do{

2)For每个i(1≤i≤n)，计算

3)t=t+1；

}until收敛。

由式(5)，可得

Tr(X-XZ(t+1))T(X-XZ(t+1))+

Tr(X-XZ(t))T(X-XZ(t))+

于是，可推导出

Tr(X-XZ(t+1))T(X-XZ(t+1))+

Tr(X-XZ(t))T(X-XZ(t))

4 实验分析与讨论

4.1 实验数据集及评价指标

本文算法通过MATLAB语言编程，且所有实验都是在win7系统下的MATLAB 2014软件上运行测试。实验用到的数据集介绍如下。

Hopkins155[15]数据集被广泛用来测试各种子空间聚类算法。该数据集由156个视频序列组成，一个序列对应一个数据集，所以其共有156个数据集，并且每个序列中包含2或3个运动物体目标。

Jaffe[16]数据集由日本ATR表情识别研究协会提供，该数据集包含10个人的213张表情图像，每张表情图像经过预处理被裁剪为32像素×32像素大小的尺度。

USPS[17]数据集是由美国国家邮政局提供，数据集含有9 298个0～10的手写数字数据集，每个手写数字数据经预处理都被裁剪为16像素×16像素大小的尺度。用每个数字的前100个图像进行实验。

ORL[18]数据集是由剑桥Olivetti实验室提供，数据集包含40人的共400张面部图像，每张人脸数据经预处理被裁剪为16像素×16像素大小的尺度。

为了验证算法的性能，将目前较好的子空间聚类算法LSR、LRR和SSC与本文算法进行对比实验。为了保证算法的公平性，所有算法都没有对数据进行后期处理。

子空间聚类的重要挑战是处理存在于数据中的错误。因此，本文将子空间聚类错误率作为衡量各个算法性能的评价标准。其中，错误率越小，子空间聚类效果越好；反之，则越差。其定义为

4.2 实验结果与分析

4.2.1 Hopkins155数据集上的实验

由于Hopkins155数据集包含156个不同的数据集，根据文献[19]，本文将156个数据集中的子空间聚类错误率的最大值(Max)、均值(Mean)和中值(Median)以及标准差(Std)作为评价指标。对LSR，LRR，SSC以及本文算法SSR_SC在该数据集进行了对比，实验结果如表1所示。

通过分析表1可知，在Hopkins155数据集上，本文提出的SSR_SC比LSR、LRR和SSC获得了更好的子空间聚类效果。具体地，SSR_SC与LSR算法对比，错误率均值小2.38%，标准差小3.12%。LSR中使用L2-norm正则化项约束相似度矩阵Z，能使Z具有很好的块对角化结构，但是其并没有对Z稀疏而影响其最终的聚类效果。SSR_SC与LRR算法对比，最大错误率小7.16%，均值小3.30%，标准差小4.53%。其中LRR利用L2,1-norm项惩罚相似度矩阵Z而可以去除噪音和离群点的影响，但是，其没有对Z稀疏。而本文提出的SSR_SC算法通过L2,1-norm正则化项惩罚相似度矩阵而使其具有鲁棒性，且还对Z进行稀疏，所以能获得更好的子空间聚类效果。与SSC算法比较，本文算法SSR_SC也取得了更好的效果，最大错误率小0.96%，均值错误率小1.19%，标准差错误率小2.14%。Hopkins155数据集的大部分数据都是比较干净的，只有很小部分数据受到污染，这样的条件下SSC稀疏Z而更充分地利用了样本间的强相关性，从表1中可以看到SSC比LRR的子空间聚类效果更好。

表1 LSR、LRR、SSC和SSR_SC在Hopkins155数据集上实验的子空间聚类错误率

4.2.2 数字图像和人脸图像上的实验

为了证明本文算法SSR_SC在实际数据集中也具有适用性，本文还在USPS、ORL以及Jaffe等数字图像和人脸图像数据集也进行了对比实验。实验结果如表2所示。

表2 LSR、LRR、SSC和SSR_SC分别在Jaffe和ORL 以及USPS数据集实验的子空间聚类错误率

从表2数据可知，SSR_SC算法在Jaffe数据集上取得了最优的效果，其子空间聚类错误率为1.41%，远远低于LSR，LRR和SSC 算法的错误率，效果与LRR和SSC相比提升了10倍，甚至比LSR算法提高了接近40倍。而在USPS和ORL数据集上同样也取得了较低的子空间聚类错误率，其中在USPS数据集上，相比LSR、LRR和SSC分别提高了13.70%、24.30%、35.10%；在ORL数据集上分别提高了1.50%、34.25%、1.75%。因此，可以认为本文提出的SSR_SC算法是一种高效的子空间聚类算法。

为了更加直观地对比LRR、SSC和SSR_SC算法的子空间聚类效果，选取ORL数据集里100张图片(10人，每人10张)进行实验，得到的实验结果如图1所示。

(a)SSC

(b)LRR

(c)SSR_SC

图1中，每行都代表一个子空间，短划线方框区域表示错误聚类的图片。从图1可以直观的看出，本文提出的SSR_SC算法取得的子空间聚类效果明显好于LRR算法和SSC算法。其中，SSR_SC只将该数据集的2个人错误地聚类到其他子空间，而LRR和SSC算法聚类错误的图片数量分别为17张和19张，其中还存在将同一个人的图像平均的聚类为2个子空间的情况，如图1(a)方点线方框所示，甚至出现将不同2组人聚类到同一个子空间的情况。综上分析，SSR_SC算法比现有的子空间聚类方法有更好的子空间聚类效果。

5 结束语

提出一种综合稀疏学习和样本自表达的子空间聚类方法称为稀疏样本自表达算法。该算法通过充分考虑样本之间的相关性而进行样本自表达，并且通过稀疏学习理论进行优化，即通过L1-norm使相似度矩阵得到适当稀疏而让每个样本由与其相似性高的样本进行表达，通过L2,1-norm解决样本自表达过程中噪音和离群点的干扰。与SSC算法和LRR算法比较，SSR_SC算法具有更好的鲁棒性和实现构造一个良好相似度矩阵的目的。此外，在Hopkinss155、USPS、ORL和Jaffe等数据集上实验的结果表明，SSR_SC算法在实际数据集，如运动目标分割和图像聚类等方面，能获得更好的子空间聚类效果。此后工作将提出的方法应用于更广泛的领域，如医学数据、文本数据以及金融数据等高维数据的聚类分析。

[1]王卫卫, 李小平, 冯象初, 等. 稀疏子空间聚类综述[J]. 自动化学报, 2015, 41(8): 1373-1384. WANG Weiwei, LI Xiaoping, FENG Xiangchu, et al. A survey on sparse subspace clustering[J]. Acta automatica sinica, 2015, 41(8): 1373-1384.

[2]VIDAL R, MA Yi, SASTRY S. Generalized principal component analysis (GPCA)[J]. IEEE transactions on pattern analysis and machine intelligence, 2005, 27(12): 1945-1959.

[3]TSENG P. Nearest q-flat to m points[J]. Journal of optimization theory and applications, 2000, 105(1): 249-252.

[4]FISCHLER M A, BOLLES R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[5]ELHAMIFAR E, VIDAL R. Sparse subspace clustering: algorithm, theory, and applications[J]. IEEE transactions on pattern analysis and machine intelligence, 2013, 35(11): 2765-2781.

[6]LIU Guangcan, LIN Zhouchen, YAN Shuicheng, et al. Robust recovery of subspace structures by low-rank representation[J]. IEEE transactions on pattern analysis and machine intelligence, 2013, 35(1): 171-184.

[7]LU Canyi, MIN Hai, ZHAO Zhongqiu, et al. Robust and efficient subspace segmentation via least squares regression[C]//Proceedings of the 12th European Conference on Computer Vision. Berlin Heidelberg, 2012: 347-360.

[8]FENG Jiashi, LIN Zhouchen, XU Huan, et al. Robust subspace segmentation with block-diagonal prior[C]//Proceedings of Conference on Computer Vision and Pattern Recognition. Columbus, OH, USA, 2014: 3818-3825.

[9]欧阳佩佩, 赵志刚, 刘桂峰. 一种改进的稀疏子空间聚类算法[J]. 青岛大学学报: 自然科学版, 2014, 27(3): 44-48. OUYANG Peipei, ZHAO Zhigang, LIU Guifeng. An improved sparse subspace clustering algorithm[J]. Journal of Qingdao university: natural science edition, 2014, 27(3): 44-48.

[10]杨国亮, 罗璐, 丰义琴, 等. 基于低秩稀疏图的结构保持投影算法[J]. 计算机工程与科学, 2015, 37(8): 1584-1590. YANG Guoliang, LUO Lu, FENG Yiqin, et al. Structure preserving projection algorithm based on low rank and sparse graph[J]. Computer engineering and science, 2015, 37(8): 1584-1590.

[11]ZHU Xiaofeng, HUANG Zi, YANG Yang, et al. Self-taught dimensionality reduction on the high-dimensional small-sized data[J]. Pattern recognition, 2013, 46(1): 215-229.

[12]ZHANG Shichao, QIN Zhenxing, LING C X, et al. “Missing is useful”: missing values in cost-sensitive decision trees[J]. IEEE transactions on knowledge and data engineering, 2005, 17(12): 1689-1693.

[13]ZHU Xiaofeng, HUANG Zi, CUI Jiangtao, et al. Video-to-shot tag propagation by graph sparse group lasso[J]. IEEE transactions on multimedia, 2013, 15(3): 633-646.

[14]ZHU Xiaofeng, ZHANG Lei, HUANG Zi. A sparse embedding and least variance encoding approach to hashing[J]. IEEE transactions on image processing, 2014, 23(9): 3737-3750.

[15]TRON R, VIDAL R. A benchmark for the comparison of 3-D motion segmentation algorithms[C]//Proceedings of Conference on Computer Vision and Pattern Recognition. Minneapolis, MN, USA, 2007: 1-8.

[16]LYONS M, AKAMATSU S, KAMACHI M, et al. Coding facial expressions with gabor wavelets[C]//Proceedings of the 3rd IEEE International Conference on Automatic Face and Gesture Recognition. Nara, 1998: 200-205.

[17]HULL J J. A database for handwritten text recognition research[J]. IEEE transactions on pattern analysis and machine intelligence, 1994, 16(5): 550-554.

[18]SAMARIA F S, HARTERT A C. Parameterisation of a stochastic model for human face identification[C]//Proceedings of the 2nd IEEE Workshop on Applications of Computer Vision. Sarasota, FL, USA, 1994: 138-142.

[19]FENG Jiashi, LIN Zhouchen, XU Huan, et al. Robust subspace segmentation with block-diagonal prior[C]//Proceedings of Conference on Computer Vision and Pattern Recognition. Columbus, OH, USA, 2014: 3818-3825.

林大华，男，1979年生，主要研究方向为机器学习、数据挖掘。

杨利锋，男，1989年生，硕士研究生，主要研究方向为数据挖掘和机器学习。

邓振云，男，1991年生,硕士研究生，主要研究方向为机器学习、数据挖掘。发表学术论文8篇，其中被SCI、EI检索4篇。

2017国际群体智能会议

The Eighth International Conference on Swarmb Intelligence (ICSI’2017)

July 27-August 01, 2017, Fukuoka, Japan

The Eighth International Conference on Swarm Intelligence (ICSI’2017) serves as an important forum for researchers and practitioners to exchange latest advantages in theories, technologies, and applications of swarm intelligence and related areas. The ICSI’2017 is the eighth annual event in this high-reputation ICSI series after Bali event (ICSI’2016), Beijing joint event (ICSI-CCI’2015), Hefei event (ICSI’2014), Harbin event (ICSI’2013), Shenzhen event (ICSI’2012), Chongqing event (ICSI’2011) and Beijing event (ICSI’2010). Papers presented at the ICSI’2017 will be published in Springer’s Lecture Notes in Computer Science (indexed by EI Compendex, ISTP, DBLP, SCOPUS, Web of Science ISI Thomson, etc.), some high-quality papers will be selected for SCI-indexed Transaction and Journal (including IEEE/ACM Transactions on CBB, NC, CC, IJSIR, IJCIPR, etc.).

The ICSI’2017 will be held in the center of the Fukuoka City. Historical city, Fukuoka, is the 5th largest city in Japan with 1.55 million populations and is the 7th most liveable city in the world according to the 2016 Quality of Life Survey by Monocle. Fukuoka locates at the northern end of the Kyushu Island and is the economic and cultural center of whole Kyushu Island. Because of its closeness to the Asian mainland, Fukuoka has been an important harbor city for many centuries. Today's Fukuoka is the product of the fusion of two cities in the year 1889, when the port city of Hakata and the former castle town of Fukuoka were united into one city called Fukuoka.

Website: http://www.ic-si.org/

Sparse sample self-representation for subspace clustering

LIN Dahua1, YANG Lifeng2, DENG Zhenyun2, LI Yonggang2, LUO Yan2

(1.Guangxi Center for Educational Technology, Nanning 530022, China; 2. Guangxi Key Lab of Multi-source Information Mining & Security, Guilin 541004, China)

Existing subspace clustering methods do not combine sample self-representation well with affinity matrix sparsity, for example, by removing disturbances from noise, outliers, etc., when constructing the affinity matrix. This paper proposes a novel subspace clustering method called sparse sample self-representation for subspace clustering. This method fully considers the correlation between the samples, and also takes advantage ofL1-norm andL2,1-norm terms to “penalize” the affinity matrix; that is, it conducts sparse sample self-representation for all test samples, to guarantee every sample can be expressed by any other samples with strong similarity and make it more robust. The experimental results of the Hopkins155 dataset and some facial image datasets show that the proposed method outperforms the LSR, SSC, and LRR methods in terms of the subspace clustering error.

subspace clustering; spectral clustering; subspace structure; similarity matrix; sample self-representation

2016-01-04.

日期：2016-07-18.

国家自然科学基金项目(61263035, 61573270, 61450001)；国家973计划项目(2013CB329404)；中国博士后科学基金项目(2015M570837)；广西自然科学基金项目(2015GX NSFCB139011)；广西研究生教育创新计划项目(YCSZ2016046, YCSZ2016045).

杨利锋. E-mail:517567113@qq.com.

TP181

A

1673-4785(2016)05-0696-07

10.11992/tis.201601005

http://www.cnki.net/kcms/detail/23.1538.TP.20160718.1521.006.html

林大华,杨利锋,邓振云，等.稀疏样本自表达子空间聚类算法[J]. 智能系统学报， 2016, 11(5):696-702.

英文引用格式：LIN Dahua, YANG Lifeng, DENG Zhenyun, et al. Sparse sample self-representation for subspace clustering[J]. CAAI transactions on intelligent systems, 2016,11(5):696-702.