《智能系统学报》：稀疏样本自表达子空间聚类算法

第11卷第5期 智能系统学报 Vol.11 No.5 2016年10月 CAAI Transactions on Intelligent Systems 0ct.2016 D0I:10.11992/is.201601005 网络出版地址：htp:/www.cnki.net/kcms/detail/23.1538.TP.20160718.1521.006.html 稀疏样本自表达子空间聚类算法 林大华1，杨利锋2，邓振云2，李永钢2，罗䶮2 (1.广西电化教育馆，广西南宁530022：2.广西师范大学广西多源信息挖掘与安全重点实验室，广西桂林541004) 摘要：针对现有子空间聚类算法在构造相似度矩阵时，没有同时利用样本自表达和稀疏相似度矩阵以及去除噪 音、离群点的干扰相结合，提出了一种新的稀疏样本自表达子空间聚类方法。该方法通过样本自表达而充分利用样 本间固有相关性的本质，创新性地同时使用L~范数和L2.~范数正则化项惩罚相似度矩阵，即对所有测试样本进行 稀疏样本自表达，从而确保每个测试样本由与其相关性强的样本表示，并使所获得的相似度矩阵具有良好的子空间 结构和鲁棒性。通过Hopkins155和人脸图像等大量数据集的实验结果表明，本文方法在实际数据的子空间聚类中 能够获得非常好的效果。 关键词：子空间聚类；谱聚类；子空间结构；相似度矩阵；样本自表达 中图分类号：TP181文献标志码：A文章编号：1673-4785(2016)05-0696-07 中文引用格式：林大华，杨利锋，邓振云，等.稀疏样本自表达子空间聚类算法[J].智能系统学报，2016,11(5)：696-702. 英文引用格式：LIN Dahua,YANG Lifeng,DENG Zhenyun,etal.Sparse sample self-.representation for subspace clustering[J]. CAAI transactions on intelligent systems,2016,11(5):696-702. Sparse sample self-representation for subspace clustering LIN Dahua',YANG Lifeng',DENG Zhenyun2,LI Yonggang?,LUO Yan2 (1.Guangxi Center for Educational Technology,Nanning 530022,China;2.Guangxi Key Lab of Multi-source Information Mining Security,Guilin 541004,China) Abstract: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 cluste- ring.This method fully considers the correlation between the samples,and also takes advantage of L-norm and L2.-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. Keywords:subspace clustering;spectral clustering;subspace structure;similarity matrix;sample self-representa- tion 近几年来，子空间聚类]方法作为一种实现高 示(sparse representation)和低秩表示(low-rank rep- 维数据聚类的有效途径，在机器学习、图像处理和计 resentation)的子空间聚类方法，通过与图划分的谱 算机视觉等领域已得到广泛应用。其中基于稀疏表 聚类方法相结合，在运动图像分割、人脸识别等高维 数据的聚类方面得到了较好的效果。 收稿日期：2016-01-04.网络出版日期：2016-07-18. 子空间聚类又称子空间分割是指把数据的原始 基金项目：国家自然科学基金项目(61263035,61573270,61450001)： 特征空间分割为不同的特征子集，从不同的子空间 国家973计划项目(2013CB329404):中国博士后科学基金项 目(2015M570837):广西自然科学基金项目(2015GX 角度考察各个样本聚类划分的意义，同时在聚类过 NSFCB139011):广西研究生教育创新计划项目(YC- 程中为每个样本寻找相应的特征子空间。目前实现 SZ2016046,YCSZ2016045). 通信作者：杨利锋.E-mail:517567113@qg.com. 子空间聚类的方法主要归为以下4类：基于代数的

第 １１ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．５ ２０１６ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０１００５ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０７１８．１５２１．００６．ｈｔｍｌ 稀疏样本自表达子空间聚类算法 林大华１ ，杨利锋２ ，邓振云２ ，李永钢２ ，罗２ （１．广西电化教育馆，广西 南宁 ５３００２２； ２．广西师范大学 广西多源信息挖掘与安全重点实验室，广西 桂林 ５４１００４） 摘 要：针对现有子空间聚类算法在构造相似度矩阵时，没有同时利用样本自表达和稀疏相似度矩阵以及去除噪 音、离群点的干扰相结合，提出了一种新的稀疏样本自表达子空间聚类方法。 该方法通过样本自表达而充分利用样 本间固有相关性的本质，创新性地同时使用 Ｌ１ ⁃范数和 Ｌ２，１ ⁃范数正则化项惩罚相似度矩阵，即对所有测试样本进行 稀疏样本自表达，从而确保每个测试样本由与其相关性强的样本表示，并使所获得的相似度矩阵具有良好的子空间 结构和鲁棒性。 通过 Ｈｏｐｋｉｎｓ１５５ 和人脸图像等大量数据集的实验结果表明，本文方法在实际数据的子空间聚类中 能够获得非常好的效果。 关键词：子空间聚类； 谱聚类； 子空间结构； 相似度矩阵； 样本自表达 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０５⁃０６９６⁃０７ 中文引用格式：林大华，杨利锋，邓振云，等．稀疏样本自表达子空间聚类算法［Ｊ］． 智能系统学报， ２０１６， １１（５）：６９６⁃７０２． 英文引用格式：ＬＩＮ Ｄａｈｕａ， ＹＡＮＧ Ｌｉｆｅｎｇ， ＤＥＮＧ Ｚｈｅｎｙｕｎ， ｅｔ ａｌ． Ｓｐａｒｓｅ ｓａｍｐｌｅ ｓｅｌｆ⁃ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（５）：６９６⁃７０２． Ｓｐａｒｓｅ ｓａｍｐｌｅ ｓｅｌｆ⁃ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ ＬＩＮ Ｄａｈｕａ １ ， ＹＡＮＧ Ｌｉｆｅｎｇ ２ ， ＤＥＮＧ Ｚｈｅｎｙｕｎ ２ ， ＬＩ Ｙｏｎｇｇａｎｇ ２ ， ＬＵＯ Ｙａｎ ２ （１．Ｇｕａｎｇｘｉ Ｃｅｎｔｅｒ ｆｏｒ Ｅｄｕｃａｔｉｏｎａｌ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｎｉｎｇ ５３００２２， Ｃｈｉｎａ； ２． Ｇｕａｎｇｘｉ Ｋｅｙ Ｌａｂ ｏｆ Ｍｕｌｔｉ⁃ｓｏｕｒｃｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｍｉｎｉｎｇ ＆ Ｓｅｃｕｒｉｔｙ， Ｇｕｉｌｉｎ ５４１００４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｅｘｉｓｔｉｎｇ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄｓ ｄｏ ｎｏｔ ｃｏｍｂｉｎｅ ｓａｍｐｌｅ ｓｅｌｆ⁃ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｗｅｌｌ ｗｉｔｈ ａｆｆｉｎｉｔｙ ｍａｔｒｉｘ ｓｐａｒｓｉｔｙ， ｆｏｒ ｅｘａｍｐｌｅ， ｂｙ ｒｅｍｏｖｉｎｇ ｄｉｓｔｕｒｂａｎｃｅｓ ｆｒｏｍ ｎｏｉｓｅ， ｏｕｔｌｉｅｒｓ， ｅｔｃ．， ｗｈｅｎ ｃｏｎｓｔｒｕｃｔｉｎｇ ｔｈｅ ａｆｆｉｎｉｔｙ ｍａｔｒｉｘ． Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｎｏｖｅｌ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ ｃａｌｌｅｄ ｓｐａｒｓｅ ｓａｍｐｌｅ ｓｅｌｆ⁃ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅ⁃ ｒｉｎｇ． Ｔｈｉｓ ｍｅｔｈｏｄ ｆｕｌｌｙ ｃｏｎｓｉｄｅｒｓ ｔｈｅ ｃｏｒｒｅｌａｔｉｏｎ ｂｅｔｗｅｅｎ ｔｈｅ ｓａｍｐｌｅｓ， ａｎｄ ａｌｓｏ ｔａｋｅｓ ａｄｖａｎｔａｇｅ ｏｆ Ｌ１ ⁃ｎｏｒｍ ａｎｄ Ｌ２，１ ⁃ｎｏｒｍ ｔｅｒｍｓ ｔｏ “ｐｅｎａｌｉｚｅ” ｔｈｅ ａｆｆｉｎｉｔｙ ｍａｔｒｉｘ； ｔｈａｔ ｉｓ， ｉｔ ｃｏｎｄｕｃｔｓ ｓｐａｒｓｅ ｓａｍｐｌｅ ｓｅｌｆ⁃ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ ａｌｌ ｔｅｓｔ ｓａｍｐｌｅｓ， ｔｏ ｇｕａｒａｎｔｅｅ ｅｖｅｒｙ ｓａｍｐｌｅ ｃａｎ ｂｅ ｅｘｐｒｅｓｓｅｄ ｂｙ ａｎｙ ｏｔｈｅｒ ｓａｍｐｌｅｓ ｗｉｔｈ ｓｔｒｏｎｇ ｓｉｍｉｌａｒｉｔｙ ａｎｄ ｍａｋｅ ｉｔ ｍｏｒｅ ｒｏｂｕｓｔ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｆ ｔｈｅ Ｈｏｐｋｉｎｓ１５５ ｄａｔａｓｅｔ ａｎｄ ｓｏｍｅ ｆａｃｉａｌ ｉｍａｇｅ ｄａｔａｓｅｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｏｕｔｐｅｒｆｏｒｍｓ ｔｈｅ ＬＳＲ， ＳＳＣ， ａｎｄ ＬＲＲ ｍｅｔｈｏｄｓ ｉｎ ｔｅｒｍｓ ｏｆ ｔｈｅ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ ｅｒｒｏｒ． Ｋｅｙｗｏｒｄｓ：ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ； ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅｒｉｎｇ； ｓｕｂｓｐａｃｅ ｓｔｒｕｃｔｕｒｅ； ｓｉｍｉｌａｒｉｔｙ ｍａｔｒｉｘ； ｓａｍｐｌｅ ｓｅｌｆ⁃ｒｅｐｒｅｓｅｎｔａ⁃ ｔｉｏｎ 收稿日期：２０１６⁃０１⁃０４． 网络出版日期：２０１６⁃０７⁃１８． 基金项目：国家自然科学基金项目（ ６１２６３０３５， ６１５７３２７０， ６１４５０００１）； 国家 ９７３ 计划项目（２０１３ＣＢ３２９４０４）；中国博士后科学基金项 目 （ ２０１５Ｍ５７０８３７ ）； 广 西 自 然 科 学 基 金 项 目 （ ２０１５ＧＸ ＮＳＦＣＢ１３９０１１）； 广 西 研 究 生 教 育 创 新 计 划 项 目 （ ＹＣ⁃ ＳＺ２０１６０４６， ＹＣＳＺ２０１６０４５）． 通信作者：杨利锋． Ｅ⁃ｍａｉｌ：５１７５６７１１３＠ ｑｑ．ｃｏｍ． 近几年来，子空间聚类［１］ 方法作为一种实现高 维数据聚类的有效途径，在机器学习、图像处理和计 算机视觉等领域已得到广泛应用。 其中基于稀疏表 示（ｓｐａｒｓｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ） 和低秩表示（ ｌｏｗ⁃ｒａｎｋ ｒｅｐ⁃ ｒｅｓｅｎｔａｔｉｏｎ）的子空间聚类方法，通过与图划分的谱 聚类方法相结合，在运动图像分割、人脸识别等高维 数据的聚类方面得到了较好的效果。 子空间聚类又称子空间分割是指把数据的原始 特征空间分割为不同的特征子集，从不同的子空间 角度考察各个样本聚类划分的意义，同时在聚类过 程中为每个样本寻找相应的特征子空间。 目前实现 子空间聚类的方法主要归为以下 ４ 类：基于代数的

第5期 林大华，等：稀疏样本自表达子空间聚类算法 ·697. 如GPCA算法2；基于迭代的，如K-subspacest);基 很强相似度的样本往往在同一低维结构里，否则在 于统计的，如PCA和RANSAC算法[4：以及基于谱 不同的结构。每个低维结构对应为一个子空间，所 聚类的，如SSC(sparse subspace clustering)),LRR 以对数据的聚类可以通过对子空间的划分来聚类， (low-rank representation)ISR(least squares re- 即子空间聚类。 gression)【算法等。其中，基于谱聚类的子空间聚 子空间聚类(subspace clustering)的定义：给定 类算法利用样本的局部或全局信息去构建一个相似 一个足够大的数据集X=[x,…x…xn]∈R,其 度矩阵，然后通过谱聚类算法对样本进行聚类。该 中x:表示一个具有d维属性的样本点，n为样本数。 类方法能较好地处理具有噪音和离群点的数据，不 假设这些样本点是分别从k个不同的子空间{S:}, 需要事先知道子空间的个数以及维数，因此在手写 (i=1,2,…,k)里提取出来的，子空间聚类的目的就 体识别、人脸识别以及运动分割等多个应用领域获 是将这些样本点正确地聚类到其所属的子空间。 得非常好的效果。 目前基于谱聚类的子空间聚类算法的主要步骤 目前比较流行的算法有基于谱聚类的SSC和 是：1)根据子空间策略构造样本集的相似度矩阵S; LRR算法，它们主要是对每个样本都找到一组稀疏 2)通过计算相似度矩阵或拉普拉斯矩阵的前k个特 或低秩的线性表示去构建相似度矩阵，然后利用谱 征值与特征向量，构建特征向量空间：3)利用K- 聚类得到最终的结果。其中，SSC算法能够很好地 means算法对特征向量空间中的特征向量进行聚 结合样本自表达和稀疏相似度矩阵，通过稀疏相似 类，从而实现子空间的聚类。由上述的过程可知，该 度矩阵可使每个样本由与其相似性很强的一些样本 类方法的主要挑战就是构造一个良好的相似度矩阵 表示，这些具有强相似性的样本往往在同一个子空 S。而通过一个良好矩阵S得到的子空间的特征表 间里，所以具有一定稀疏性的相似度矩阵往往可以 现为：子空间内的样本具有高度的相似性，不同子空 提高子空间聚类的效果。但是，在数据的信噪比小、 间的样本不相似或差异性大，且所有子空间呈块对 子空间不相互独立的情况时，该方法的聚类效果就 角化结构[劉。 不是很好。而LRR算法可以很好地使样本自表达 为了能构造一个良好的相似度矩阵而获得很好 和去除噪音、离群点相结合，但是其通过低秩表示构 的子空间聚类效果，E.Elhamifar等1提出了稀疏子 造的相似度矩阵往往不稀疏，没有很好地利用样本 空间聚类算法SSC(sparse subspace clustering),将每 间的强相关性，这会影响子空间聚类的效果。 个样本用空间里的其他样本来线性表示，通过L 因此，合理地结合利用样本自表达和稀疏相似 nom正则化项确保所获得的相似度矩阵是稀疏的。 度矩阵以及去除噪音、离群点的干扰，能够实现构造 而Liu等[6提出低秩自表达LRR(low-rank represen- 一个良好的相似度矩阵而获得更好的子空间聚类效 tation),通过核范数利用数据的全局信息寻找低秩 果的目的。所以，本文提出的方法首先从样本之间 样本自表达，并用L2,1-nom项去除噪音和离群点， 的相关性出发，对所有测试样本进行样本自表达，并 使所构造的相似度矩阵具有鲁棒性。由u等[]提 同时通过L,-nom和L2,1~nom正则化项惩罚相似度 出的LSR(least squares regression),通过优化求解最 矩阵，进行稀疏约束得到全局最优的相似度矩阵。 小二乘回归的目标函数min-XZ‖子+入IZI子， 然后，利用谱聚类得到最终的子空间聚类结果。在 能获得具有良好块对角化结构的相似度矩阵。但 样本自表达过程中，L,-nom正则化项用来实现相似 是，这些方法都没有同时利用样本自表达和稀疏相 度矩阵的稀疏，确保每个测试样本都由与之相关性 似度矩阵以及去除噪音、离群点的干扰相结合来构 强的样本表示，能很好地解决样本自表达和稀疏相 造相似度矩阵。 似度矩阵相结合的问题；而L2,1-nom通过控制相似 因此，本文提出了SSR_SC算法，充分利用样本 度矩阵的行稀疏解决噪音和离群点的干扰，使其具 间的相关性进行样本自表达，并通过L,-nom和 有更好的鲁棒性，最终可以实现样本自表达和稀疏 L2.1-nom正则化项对相似度矩阵进行稀疏约束，从而 相似度矩阵以及去除噪音、离群点的干扰相结合，提 能很好地实现构造一个良好的相似度矩阵的目的。 高子空间聚类的效果。本文将所提出的方法称为稀 疏样本自表达子空间聚类算法，简称为SSR_SC(sparse 2 SSR SC算法 sample self-representation for subspace clustering). 对于样本空间X中的一个样本x,用同一空间 中的其他样本对x进行线性表示的过程称为样本自 相关理论 表达。同一子空间中的样本之间往往具有很强的相 高维数据一般可由多个低维结构表示，且具有 关性，不同子空间的样本之间为无相关性或弱相关

如 ＧＰＣＡ 算法［２］ ；基于迭代的，如 Ｋ⁃ｓｕｂｓｐａｃｅｓ ［３］ ；基 于统计的，如 ＰＣＡ 和 ＲＡＮＳＡＣ 算法［４］ ；以及基于谱 聚类的，如 ＳＳＣ（ ｓｐａｒｓｅ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ） ［５］ ，ＬＲＲ （ｌｏｗ⁃ｒａｎｋ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ） ［６］ 和 ＬＳＲ（ ｌｅａｓｔ ｓｑｕａｒｅｓ ｒｅ⁃ ｇｒｅｓｓｉｏｎ） ［７］算法等。 其中，基于谱聚类的子空间聚 类算法利用样本的局部或全局信息去构建一个相似 度矩阵，然后通过谱聚类算法对样本进行聚类。 该 类方法能较好地处理具有噪音和离群点的数据，不 需要事先知道子空间的个数以及维数，因此在手写 体识别、人脸识别以及运动分割等多个应用领域获 得非常好的效果。 目前比较流行的算法有基于谱聚类的 ＳＳＣ 和 ＬＲＲ 算法，它们主要是对每个样本都找到一组稀疏 或低秩的线性表示去构建相似度矩阵，然后利用谱 聚类得到最终的结果。 其中，ＳＳＣ 算法能够很好地 结合样本自表达和稀疏相似度矩阵，通过稀疏相似 度矩阵可使每个样本由与其相似性很强的一些样本 表示，这些具有强相似性的样本往往在同一个子空 间里，所以具有一定稀疏性的相似度矩阵往往可以 提高子空间聚类的效果。 但是，在数据的信噪比小、 子空间不相互独立的情况时，该方法的聚类效果就 不是很好。 而 ＬＲＲ 算法可以很好地使样本自表达 和去除噪音、离群点相结合，但是其通过低秩表示构 造的相似度矩阵往往不稀疏，没有很好地利用样本 间的强相关性，这会影响子空间聚类的效果。 因此，合理地结合利用样本自表达和稀疏相似 度矩阵以及去除噪音、离群点的干扰，能够实现构造 一个良好的相似度矩阵而获得更好的子空间聚类效 果的目的。 所以，本文提出的方法首先从样本之间 的相关性出发，对所有测试样本进行样本自表达，并 同时通过 Ｌ１ ⁃ｎｏｒｍ 和 Ｌ２，１ ⁃ｎｏｒｍ 正则化项惩罚相似度 矩阵，进行稀疏约束得到全局最优的相似度矩阵。 然后，利用谱聚类得到最终的子空间聚类结果。 在 样本自表达过程中，Ｌ１ ⁃ｎｏｒｍ 正则化项用来实现相似 度矩阵的稀疏，确保每个测试样本都由与之相关性 强的样本表示，能很好地解决样本自表达和稀疏相 似度矩阵相结合的问题；而 Ｌ２，１ ⁃ｎｏｒｍ 通过控制相似 度矩阵的行稀疏解决噪音和离群点的干扰，使其具 有更好的鲁棒性，最终可以实现样本自表达和稀疏 相似度矩阵以及去除噪音、离群点的干扰相结合，提 高子空间聚类的效果。 本文将所提出的方法称为稀 疏样本自表达子空间聚类算法，简称为 ＳＳＲ＿ＳＣ（ｓｐａｒｓｅ ｓａｍｐｌｅ ｓｅｌｆ⁃ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ）。 １ 相关理论 高维数据一般可由多个低维结构表示，且具有 很强相似度的样本往往在同一低维结构里，否则在 不同的结构。 每个低维结构对应为一个子空间，所 以对数据的聚类可以通过对子空间的划分来聚类， 即子空间聚类。 子空间聚类（ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ） 的定义：给定 一个足够大的数据集 Ｘ ＝ ［ ｘ１… ｘｉ… ｘｎ ］∈Ｒ ｄ×ｎ ，其 中 ｘｉ 表示一个具有 ｄ 维属性的样本点，ｎ 为样本数。 假设这些样本点是分别从 ｋ 个不同的子空间 Ｓｉ { } ｋ ｉ ＝ １ （ｉ ＝ １，２，…，ｋ）里提取出来的，子空间聚类的目的就 是将这些样本点正确地聚类到其所属的子空间。 目前基于谱聚类的子空间聚类算法的主要步骤 是：１）根据子空间策略构造样本集的相似度矩阵 Ｓ； ２）通过计算相似度矩阵或拉普拉斯矩阵的前 ｋ 个特 征值与特征向量，构建特征向量空间；３） 利用 Ｋ⁃ ｍｅａｎｓ 算法对特征向量空间中的特征向量进行聚 类，从而实现子空间的聚类。 由上述的过程可知，该 类方法的主要挑战就是构造一个良好的相似度矩阵 Ｓ。 而通过一个良好矩阵 Ｓ 得到的子空间的特征表 现为：子空间内的样本具有高度的相似性，不同子空 间的样本不相似或差异性大，且所有子空间呈块对 角化结构［８］ 。 为了能构造一个良好的相似度矩阵而获得很好 的子空间聚类效果，Ｅ． Ｅｌｈａｍｉｆａｒ 等［５］提出了稀疏子 空间聚类算法 ＳＳＣ（ｓｐａｒｓｅ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ），将每 个样本用空间里的其他样本来线性表示，通过 Ｌ１ ⁃ ｎｏｒｍ 正则化项确保所获得的相似度矩阵是稀疏的。 而 Ｌｉｕ 等［６］提出低秩自表达 ＬＲＲ（ｌｏｗ⁃ｒａｎｋ ｒｅｐｒｅｓｅｎ⁃ ｔａｔｉｏｎ），通过核范数利用数据的全局信息寻找低秩 样本自表达，并用 Ｌ２，１ ⁃ｎｏｒｍ 项去除噪音和离群点， 使所构造的相似度矩阵具有鲁棒性。 由 Ｌｕ 等［７］ 提 出的 ＬＳＲ（ｌｅａｓｔ ｓｑｕａｒｅｓ ｒｅｇｒｅｓｓｉｏｎ），通过优化求解最 小二乘回归的目标函数ｍｉｎ Ｚ ‖Ｘ－ＸＺ‖２ Ｆ ＋λ ‖Ｚ‖２ Ｆ ， 能获得具有良好块对角化结构的相似度矩阵。 但 是，这些方法都没有同时利用样本自表达和稀疏相 似度矩阵以及去除噪音、离群点的干扰相结合来构 造相似度矩阵。 因此，本文提出了 ＳＳＲ＿ＳＣ 算法，充分利用样本 间的相关性进行样本自表达，并通过 Ｌ１ ⁃ｎｏｒｍ 和 Ｌ２，１ ⁃ｎｏｒｍ 正则化项对相似度矩阵进行稀疏约束，从而 能很好地实现构造一个良好的相似度矩阵的目的。 ２ ＳＳＲ＿ＳＣ 算法 对于样本空间 Ｘ 中的一个样本 ｘ，用同一空间 中的其他样本对 ｘ 进行线性表示的过程称为样本自 表达。 同一子空间中的样本之间往往具有很强的相 关性，不同子空间的样本之间为无相关性或弱相关 第 ５ 期 林大华，等：稀疏样本自表达子空间聚类算法 ·６９７·

·698. 智能系统学报 第11卷 性，所以通过样本自表达能很好地利用样本之间的 相关性来提高子空间聚类的效果。假设样本空间为 (x1)×(z),x4=(x1x2)× 其中矩阵Z的第3 X=[x1x2…xn]∈R,其中n为样本数，x,(i=1, 行全为0，这是L2.1-nom对矩阵Z进行行稀疏的效 2,…,n)为具有d维属性的样本点。根据上述样本 果，表明对样本x1、x2、x4而言，x3为不相关样本即 自表达的定义，即找出这样一个列向量z:∈R1,使 噪音样本。 得x:可以通过X:表示。 根据以上分析可知，本文提出的目标函数(2)， 但是样本空间X中往往存在噪音和离群点等 不仅通过L,-nom确保每个样本都由与之具有强相 干扰，其用e表示，则x,=Xz+e,而这些干扰通常会 关性的样本表示，而且利用L2,1-norm避免噪音和离 影响子空间聚类的效果。因此本文算法希望找到这 群点的干扰，使其具有更好的鲁棒性。注意，此时得 样一个相似度矩阵Z=[z1z2…乙n]∈R“,使得X与 到的相似度矩阵Z是稀疏的且充分考虑了样本间 XZ的误差尽可能小。这通常可采用岭回归(ridge 的相关性以及去除了噪音和离群点的干扰，然后通 regression)实现： 过矩阵Z构造矩阵S=(|Z+|Z|)/2,接着利用谱 mm立x,-x,l+1zl= 聚类算法进行最终的聚类，这样得到的子空间便具 有了子空间内的样本相似性高，不同子空间的样本 minll,s.t.diag(Z)=0 差异性大，且所有子空间呈块对角化结构的特征，很 (1) 好地解决了基于谱聚类的子空间聚类问题中构造一 式中：‖·‖？为Frobenius范数，根据岭回归求解 个良好相似性矩阵的问题。 可得Z·=(XX+入I)XX。但是这样得到的矩阵 本文提出的SSR SC算法的具体步骤如下： Z通常不稀疏，并且不能很好地解决噪音和离群点 算法1 SSR_SC算法 的千扰。因此本文算法利用L,-nom和L2,1-nom替 输入参数入，和入2，以及样本空间： 代目标函数(1)中L2-nom,得到如下目标函数： X=[x1x2…xn]eRm。 min‖X-Xz‖+A,IZ‖，+入2lZ‖2，， 输出聚类结果C∈Rm 1)根据算法2，迭代求解目标函数 s.t.diag(Z)=0 (2) min‖X-XZI+入，‖Z‖，+入2川Z‖2.，获得其最 式中：1z1,=名三A作为m的参 优化矩阵Z: 数，用于控制矩阵Z整体的稀疏性)，使得每个样 2)根据样本相似度矩阵Z去构造矩阵S= 本x:都由与之具有强相关性的样本表示： (|Z+|ZI)/2: 3)利用谱聚类算法得到最终的聚类结果C∈ Iz1名（名1，P),面A,作为am的 R。 i=1 参数，用于调整矩阵Z整行的稀硫性，可以去除噪 3目标函数优化 音和离群点的干扰[。此时，通过该目标函数构造 获得的相似度矩阵，能很好地同时利用样本自表达 目标函数(2)是一个凸函数，但是L,-nom和 和稀疏相似度矩阵以及去除噪音、离群点的干扰相 L2.1nom是非光滑的，无法直接求得解析解。为 结合，使得子空间聚类的效果更好。 此，本文提出了一种有效的优化算法来解决这个问 假定通过目标函数(2)得到如下矩阵Z,其中 题，最后解出目标函数的最优化结果。 diag(Z)=0,表明样本不能将自身作为相关性样本 对目标函数(2)中的Z的每一行Z:求导，然后 进行线性表示。 令其为0，得到式(3) 0 0.80.10.7 XXZ:-XX +A DZ:+A DZ:=0 (3) 0.6 0 0 0.4 式中：D.(1≤i≤n)是一个对角矩阵，其第k个对角 Z= 0 0 0 0 0.50.9 0 0 元素为2乙D也是一个对角矩阵，其第k个对角 根据样本自表达定义可知，矩阵Z的第一列即 元素为1 因此可以将式(3)表示为 样本x1,可以通过样本x2和样本x4线性表示，即 21z1。 12 Z:=(Xx+AD:+D)-XX (4) x=(x2x4)× 同理x2=(x1x4)× Z42 此时，数据集X和X已知，入，和入，为调制参

性，所以通过样本自表达能很好地利用样本之间的 相关性来提高子空间聚类的效果。 假设样本空间为 Ｘ＝ ［ｘ１ ｘ２… ｘｎ ］∈Ｒ ｄ×ｎ ，其中 ｎ 为样本数，ｘｉ（ ｉ ＝ １， ２，…，ｎ）为具有 ｄ 维属性的样本点。 根据上述样本 自表达的定义，即找出这样一个列向量 ｚｉ∈Ｒ ｎ×１ ，使 得 ｘｉ 可以通过 Ｘｚｉ 表示。 但是样本空间 Ｘ 中往往存在噪音和离群点等 干扰，其用 ｅ 表示，则 ｘｉ ＝ Ｘｚｉ ＋ｅ，而这些干扰通常会 影响子空间聚类的效果。 因此本文算法希望找到这 样一个相似度矩阵 Ｚ ＝ ［ｚ１ ｚ２… ｚｎ ］∈Ｒ ｎ×ｎ ，使得 Ｘ 与 ＸＺ 的误差尽可能小。 这通常可采用岭回归（ ｒｉｄｇｅ ｒｅｇｒｅｓｓｉｏｎ）实现： ｍｉｎ Ｚ ∑ ｎ ｉ ＝ １ ‖ｘｉ － Ｘｚｉ‖２ ２ ＋ ‖Ｚ‖２ ２ ＝ ｍｉｎ Ｚ ‖Ｘ － ＸＺ‖２ Ｆ ＋ λ ‖Ｚ‖２ ２ ，ｓ．ｔ． ｄｉａｇ（Ｚ） ＝ ０ （１） 式中：‖·‖２ Ｆ 为 Ｆｒｏｂｅｎｉｕｓ 范数，根据岭回归求解 可得 Ｚ ∗ ＝ （Ｘ ＴＸ＋λＩｎ ） －１Ｘ ＴＸ。 但是这样得到的矩阵 Ｚ 通常不稀疏，并且不能很好地解决噪音和离群点 的干扰。 因此本文算法利用 Ｌ１ ⁃ｎｏｒｍ 和 Ｌ２，１ ⁃ｎｏｒｍ 替 代目标函数（１）中 Ｌ２ ⁃ｎｏｒｍ，得到如下目标函数： ｍｉｎ Ｚ ‖Ｘ － ＸＺ‖２ Ｆ ＋ λ１ ‖Ｚ‖１ ＋ λ２ ‖Ｚ‖２，１ ， ｓ．ｔ． ｄｉａｇ（Ｚ） ＝ ０ （２） 式中： ‖Ｚ‖１ ＝ ∑ ｎ ｉ ＝ １ ∑ ｎ ｊ ＝ １ ｚｉｊ ，λ１ 作为 Ｌ１ ⁃ｎｏｒｍ 的参 数，用于控制矩阵 Ｚ 整体的稀疏性［９］ ，使得每个样 本 ｘｉ 都 由 与 之 具 有 强 相 关 性 的 样 本 表 示； ‖Ｚ‖２，１ ＝∑ ｎ ｉ ＝ １ （∑ ｎ ｊ ＝ １ ｚｉｊ ２ ） １ ２ ， 而 λ２ 作为 Ｌ２，１ ⁃ｎｏｒｍ 的 参数，用于调整矩阵 Ｚ 整行的稀疏性，可以去除噪 音和离群点的干扰［１０］ 。 此时，通过该目标函数构造 获得的相似度矩阵，能很好地同时利用样本自表达 和稀疏相似度矩阵以及去除噪音、离群点的干扰相 结合，使得子空间聚类的效果更好。 假定通过目标函数（２） 得到如下矩阵 Ｚ，其中 ｄｉａｇ（Ｚ）＝ ０，表明样本不能将自身作为相关性样本 进行线性表示。 Ｚ ＝ ０ ０．８ ０．１ ０．７ ０．６ ０ ０ ０．４ ０ ０ ０ ０ ０．５ ０．９ ０ ０ é ë ê ê ê ê ê ù û ú ú ú ú ú 根据样本自表达定义可知，矩阵 Ｚ 的第一列即 样本 ｘ１ ，可以通过样本 ｘ２ 和样本 ｘ４ 线性表示，即 ｘ１ ＝ （ ｘ２ ｘ４ ） × ｚ２１ ｚ４１ æ è ç ö ø ÷ ，同理 ｘ２ ＝ （ ｘ１ ｘ４ ） × ｚ１２ ｚ４２ æ è ç ö ø ÷ ， ｘ３ ＝ （ｘ１ ）× ｚ１３ ( ) ，ｘ４ ＝ （ｘ１ ｘ２ ）× ｚ１４ ｚ２４ æ è ç ö ø ÷ 。 其中矩阵 Ｚ 的第 ３ 行全为 ０，这是 Ｌ２，１ ⁃ｎｏｒｍ 对矩阵 Ｚ 进行行稀疏的效 果，表明对样本 ｘ１ 、ｘ２ 、ｘ４ 而言，ｘ３ 为不相关样本即 噪音样本。 根据以上分析可知，本文提出的目标函数（２）， 不仅通过 Ｌ１ ⁃ｎｏｒｍ 确保每个样本都由与之具有强相 关性的样本表示，而且利用 Ｌ２，１ ⁃ｎｏｒｍ 避免噪音和离 群点的干扰，使其具有更好的鲁棒性。 注意，此时得 到的相似度矩阵 Ｚ 是稀疏的且充分考虑了样本间 的相关性以及去除了噪音和离群点的干扰，然后通 过矩阵 Ｚ 构造矩阵 Ｓ ＝ （ Ｚ ＋ Ｚ Ｔ ） ／ ２，接着利用谱 聚类算法进行最终的聚类，这样得到的子空间便具 有了子空间内的样本相似性高，不同子空间的样本 差异性大，且所有子空间呈块对角化结构的特征，很 好地解决了基于谱聚类的子空间聚类问题中构造一 个良好相似性矩阵的问题。 本文提出的 ＳＳＲ＿ＳＣ 算法的具体步骤如下： 算法 １ ＳＳＲ＿ＳＣ 算法 输入 参数 λ１ 和 λ２ ，以及样本空间： Ｘ ＝ ［ｘ１ ｘ２ … ｘｎ ］ ∈ Ｒ ｄ×ｎ 。 输出 聚类结果 Ｃ∈Ｒ ｎ×１ 。 １） 根 据 算 法 ２， 迭 代 求 解 目 标 函 数 ｍｉｎ Ｚ ‖Ｘ－ＸＺ‖２ Ｆ ＋λ１ ‖Ｚ‖１ ＋λ２ ‖Ｚ‖２，１ ， 获 得 其 最 优化矩阵 Ｚ； ２） 根据样本相似度矩阵 Ｚ 去构造矩阵 Ｓ ＝ （ Ｚ ＋ Ｚ Ｔ ） ／ ２； ３）利用谱聚类算法得到最终的聚类结果 Ｃ∈ Ｒ ｎ×１ 。 ３ 目标函数优化 目标函数（２） 是一个凸函数，但是 Ｌ１ ⁃ｎｏｒｍ 和 Ｌ２，１ ⁃ｎｏｒｍ 是非光滑的，无法直接求得解析解。 为 此，本文提出了一种有效的优化算法来解决这个问 题，最后解出目标函数的最优化结果。 对目标函数（２）中的 Ｚ 的每一行 Ｚｉ 求导，然后 令其为 ０，得到式（３） Ｘ ＴＸＺｉ － Ｘ ＴＸ ＋ λ１ ＤｉＺｉ ＋ λ２ Ｄ ～ Ｚｉ ＝ ０ （３） 式中：Ｄｉ（１≤ｉ≤ｎ）是一个对角矩阵，其第 ｋ 个对角 元素为 １ ２ Ｚｋｉ ；Ｄ ～ 也是一个对角矩阵，其第 ｋ 个对角 元素为 １ ２ ‖Ｚ ｋ‖２ 。 因此可以将式（３）表示为 Ｚｉ ＝ （Ｘ ＴＸ ＋ λ１ Ｄｉ ＋ λ２ Ｄ ～ ） －１ Ｘ ＴＸ （４） 此时，数据集Ｘ Ｔ 和 Ｘ 已知，λ１ 和 λ２ 为调制参 ·６９８· 智 能 系 统 学 报 第 １１ 卷

第5期 林大华，等：稀疏样本自表达子空间聚类算法 ·699. 数。但值得注意的是，D,和D依赖于Z,因此也是未 是式(3)的一个全局最优解，因此，算法2可将问题 知的。根据文献[11-13]，本文提出了一种迭代算法 (3)收敛到全局最优解。另外，在每一次迭代时都 去求解这个问题。 有封闭形式的解，因此我们的算法收敛非常快。 算法2目标函数优化算法 4实验分析与讨论 输入数据集X; 输出Z()E Rkn; 4.1实验数据集及评价指标 初始化Z)∈R",t=1: 本文算法通过MATLAB语言编程，且所有实验 do 都是在win7系统下的MATLAB2014软件上运行测 试。实验用到的数据集介绍如下。 1)计算对角矩阵D.o(1≤i≤n)和Do其中 Hopkins155[1]数据集被广泛用来测试各种子 D,的第k个对角元素为1 Do的第k个对 空间聚类算法。该数据集由156个视频序列组成， 2|Z0 一个序列对应一个数据集，所以其共有156个数据 角元素为 1 2I(Zo)*I, 集，并且每个序列中包含2或3个运动物体目标。 Jaffe[16]数据集由日本ATR表情识别研究协会 2)For每个i(1≤i≤n),计算 提供，该数据集包含10个人的213张表情图像，每 Z(D)=(XX+A D(+A2 D()-XX 张表情图像经过预处理被裁剪为32像素×32像素 3)t=t+1: 大小的尺度。 }until收敛。 USPs1刊数据集是由美国国家邮政局提供， 由上述算法2的描述知，优化目标函数的关键 数据集含有9298个0~10的手写数字数据集，每个 是目标值Z)要在迭代中收敛。下面证明目标函 手写数字数据经预处理都被裁剪为16像素×16像 数(2)的目标值在每一次迭代中都会减小。根据算 素大小的尺度。用每个数字的前100个图像进行 法2的第2步，可得 实验。 Z(D)minTr (X -XZ)"(-XZ) ORLi)数据集是由剑桥Olivetti实验室提供， AD Z+ATr Z Dz 数据集包含40人的共400张面部图像，每张人脸数 (5) 据经预处理被裁剪为16像素×16像素大小的尺度。 由式(5)，可得 为了验证算法的性能，将目前较好的子空间聚 Tr (X-XZ(D))T(X-XZ(D))+ 类算法LSR、LRR和SSC与本文算法进行对比实 A宫(2)rnzw+ 验。为了保证算法的公平性，所有算法都没有对数 据进行后期处理。 A2Tr(Z+)TDZ+1)≤ 子空间聚类的重要挑战是处理存在于数据中的 Tr (X-XZ()(X-XZ())+ 错误。因此，本文将子空间聚类错误率作为衡量各 A()D()D 个算法性能的评价标准。其中，错误率越小，子空间 聚类效果越好：反之，则越差。其定义为 于是，可推导出 Tr (X-XZ(+D)T(X-XZ(D)+ 子空间聚类错误率=错误分类的样本数 样本总数 A豆三z1+A三 I(Z+)I2≤ 4.2实验结果与分析 4.2.1 Hopkins155数据集上的实验 Tr(X-XZ)T(X-XZo)》 由于Hopkins155数据集包含156个不同的数 A三含1四 ,‖(Zo)I2 据集，根据文献[19]，本文将156个数据集中的子 空间聚类错误率的最大值(Max)、均值(Mean)和中 根据文献[14]，对于任意向量Z和Z。,有 值(Median)以及标准差(Std)作为评价指标。对 z且≤1z21ZT 1Z,1212Z12 IZoll 。由以上分 LSR,LRR,SSC以及本文算法SSR_SC在该数据集 进行了对比，实验结果如表1所示。 析可知，算法2中的目标值在每一次迭代中都会减 通过分析表1可知，在Hopkins155数据集上， 小。ZD(1≤i≤n)和D在收敛处满足等式 本文提出的SSR_SC比LSR、LRR和SSC获得了更 (5),且目标函数(2)是凸函数，于是此时得到的Z 好的子空间聚类效果。具体地，SSR_SC与LSR算

数。 但值得注意的是，Ｄｉ 和Ｄ ～ 依赖于 Ｚ，因此也是未 知的。 根据文献［１１⁃１３］，本文提出了一种迭代算法 去求解这个问题。 算法 ２ 目标函数优化算法 输入 数据集 Ｘ； 输出 Ｚ （ｔ）∈Ｒ ｎ×ｎ ； 初始化Ｚ （１）∈Ｒ ｎ×ｎ ，ｔ ＝ １； ｄｏ｛ １）计算对角矩阵Ｄｉ （ｔ） （ １≤ｉ≤ｎ） 和Ｄ ～ （ｔ） 其中 Ｄｉ （ｔ）的第 ｋ 个对角元素为 １ ２ Ｚ （ｔ） ｋｉ ，Ｄ ～ （ｔ） 的第 ｋ 个对 角元素为 １ ２ ‖（Ｚ （ｔ） ） ｋ‖２ ； ２）Ｆｏｒ 每个 ｉ（１≤ｉ≤ｎ），计算 Ｚ （ｔ＋１） ｉ ＝ （Ｘ ＴＸ ＋ λ１ Ｄ （ｔ） ｉ ＋ λ２ Ｄ ～ （ｔ） ） －１ Ｘ ＴＸ ３）ｔ ＝ ｔ＋１； ｝ｕｎｔｉｌ 收敛。 由上述算法 ２ 的描述知，优化目标函数的关键 是目标值Ｚ （ｔ＋１） ｉ 要在迭代中收敛。 下面证明目标函 数（２）的目标值在每一次迭代中都会减小。 根据算 法 ２ 的第 ２ 步，可得 Ｚ （ｔ＋１） ＝ ｍｉｎ Ｚ Ｔｒ （Ｘ － ＸＺ） Ｔ （Ｘ － ＸＺ） ＋ λ１∑ ｎ ｉ ＝ １ Ｚ Ｔ ｉ Ｄ （ｔ） ｉ Ｚｉ ＋ λ２Ｔｒ Ｚ Ｔ Ｄ ～ （ｔ）Ｚ （５） 由式（５），可得 Ｔｒ （Ｘ － ＸＺ （ｔ＋１） ） Ｔ （Ｘ － ＸＺ （ｔ＋１） ） ＋ λ１∑ ｎ ｉ ＝ １ （Ｚ （ｔ＋１） ｉ ） Ｔ Ｄ （ｔ） ｉ Ｚ （ｔ＋１） ｉ ＋ λ２Ｔｒ （Ｚ （ｔ＋１） ） Ｔ Ｄ ～ （ｔ） Ｚ （ｔ＋１） ≤ Ｔｒ （Ｘ － ＸＺ （ｔ） ） Ｔ （Ｘ － ＸＺ （ｔ） ） ＋ λ１∑ ｎ ｉ ＝ １ （Ｚ （ｔ） ｉ ） Ｔ Ｄ （ｔ） ｉ Ｚ （ｔ） ｉ ＋ λ２Ｔｒ （Ｚ （ｔ） ） Ｔ Ｄ ～ （ｔ） Ｚ （ｔ） 于是，可推导出 Ｔｒ （Ｘ － ＸＺ （ｔ＋１） ） Ｔ （Ｘ － ＸＺ （ｔ＋１） ） ＋ λ１∑ ｄ ｉ ＝ １ ∑ ｎ ｊ ＝ １ ‖Ｚ （ｔ＋１） ｉｊ ‖ ＋ λ２∑ ｄ ｋ ＝ １ ‖ （Ｚ （ｔ＋１） ） ｋ‖２ ≤ Ｔｒ （Ｘ － ＸＺ （ｔ） ） Ｔ （Ｘ － ＸＺ （ｔ） ） λ１∑ ｄ ｉ ＝ １ ∑ ｎ ｊ ＝ １ （‖Ｚ （ｔ） ｉｊ ‖） ＋ λ２∑ ｄ ｋ ＝ １ ‖ （Ｚ （ｔ） ） ｋ‖２ 根据文献 ［ １４］， 对于任意向量 Ｚ 和 Ｚ０ ， 有 ‖Ｚ２‖－ ‖Ｚ‖２ ２ ２ ‖Ｚ０‖２ ≤‖Ｚ０‖２ － ‖Ｚ０‖２ ２ ２ ‖Ｚ０‖２ 。 由以上分 析可知，算法 ２ 中的目标值在每一次迭代中都会减 小。 Ｚ （ｔ） 、Ｄ （ｔ） ｉ （１≤ｉ≤ｎ） 和Ｄ ～ （ｔ） 在收敛处满足等式 （５），且目标函数（２）是凸函数，于是此时得到的 Ｚ 是式（３）的一个全局最优解，因此，算法 ２ 可将问题 （３）收敛到全局最优解。 另外，在每一次迭代时都 有封闭形式的解，因此我们的算法收敛非常快。 ４ 实验分析与讨论 ４．１ 实验数据集及评价指标 本文算法通过 ＭＡＴＬＡＢ 语言编程，且所有实验 都是在 ｗｉｎ７ 系统下的 ＭＡＴＬＡＢ ２０１４ 软件上运行测 试。 实验用到的数据集介绍如下。 Ｈｏｐｋｉｎｓ１５５ ［１５］数据集被广泛用来测试各种子 空间聚类算法。 该数据集由 １５６ 个视频序列组成， 一个序列对应一个数据集，所以其共有 １５６ 个数据 集，并且每个序列中包含 ２ 或 ３ 个运动物体目标。 Ｊａｆｆｅ ［１６］数据集由日本 ＡＴＲ 表情识别研究协会 提供，该数据集包含 １０ 个人的 ２１３ 张表情图像，每 张表情图像经过预处理被裁剪为 ３２ 像素×３２ 像素 大小的尺度。 ＵＳＰＳ ［１７］数据集是由 美 国 国 家 邮 政 局 提 供， 数据集含有 ９ ２９８ 个 ０～１０ 的手写数字数据集，每个 手写数字数据经预处理都被裁剪为 １６ 像素×１６ 像 素大小的尺度。 用每个数字的前 １００ 个图像进行 实验。 ＯＲＬ ［１８］数据集是由剑桥 Ｏｌｉｖｅｔｔｉ 实验室提供， 数据集包含 ４０ 人的共 ４００ 张面部图像，每张人脸数 据经预处理被裁剪为 １６ 像素×１６ 像素大小的尺度。 为了验证算法的性能，将目前较好的子空间聚 类算法 ＬＳＲ、ＬＲＲ 和 ＳＳＣ 与本文算法进行对比实 验。 为了保证算法的公平性，所有算法都没有对数 据进行后期处理。 子空间聚类的重要挑战是处理存在于数据中的 错误。 因此，本文将子空间聚类错误率作为衡量各 个算法性能的评价标准。 其中，错误率越小，子空间 聚类效果越好；反之，则越差。 其定义为 子空间聚类错误率＝ 错误分类的样本数 样本总数 ４．２ 实验结果与分析 ４．２．１ Ｈｏｐｋｉｎｓ１５５ 数据集上的实验 由于 Ｈｏｐｋｉｎｓ１５５ 数据集包含 １５６ 个不同的数 据集，根据文献［１９］，本文将 １５６ 个数据集中的子 空间聚类错误率的最大值（Ｍａｘ）、均值（Ｍｅａｎ）和中 值（Ｍｅｄｉａｎ） 以及标准差（ Ｓｔｄ） 作为评价指标。 对 ＬＳＲ，ＬＲＲ，ＳＳＣ 以及本文算法 ＳＳＲ＿ＳＣ 在该数据集 进行了对比，实验结果如表 １ 所示。 通过分析表 １ 可知，在 Ｈｏｐｋｉｎｓ１５５ 数据集上， 本文提出的 ＳＳＲ＿ＳＣ 比 ＬＳＲ、ＬＲＲ 和 ＳＳＣ 获得了更 好的子空间聚类效果。 具体地，ＳＳＲ＿ＳＣ 与 ＬＳＲ 算 第 ５ 期 林大华，等：稀疏样本自表达子空间聚类算法 ·６９９·

·700 智能系统学报 第11卷 法对比，错误率均值小2.38%，标准差小3.12%。 上同样也取得了较低的子空间聚类错误率，其中在 LSR中使用L,-nom正则化项约束相似度矩阵Z,能 USPS数据集上，相比LSR,LRR和SSC分别提高了 使Z具有很好的块对角化结构，但是其并没有对Z 13.70%、24.30%、35.10%:在0RL数据集上分别提 稀疏而影响其最终的聚类效果。SSR_SC与LRR算 高了1.50%、34.25%、1.75%。因此，可以认为本文 法对比，最大错误率小7.16%，均值小3.30%，标准 提出的SSR_SC算法是一种高效的子空间聚类 差小4.53%。其中LRR利用L2.nom项惩罚相似 算法。 度矩阵Z而可以去除噪音和离群点的影响，但是， 为了更加直观地对比LRR、,SSC和SSR_SC算 其没有对Z稀疏。而本文提出的SSR_SC算法通过 法的子空间聚类效果，选取0L数据集里100张图 L2.-nom正则化项惩罚相似度矩阵而使其具有鲁 片(10人，每人10张)进行实验，得到的实验结果如 棒性，且还对Z进行稀疏，所以能获得更好的子空 图1所示。 间聚类效果。与SSC算法比较，本文算法SSR_SC 也取得了更好的效果，最大错误率小0.96%，均值错 误率小1.19%，标准差错误率小2.14%。Hopkins155 数据集的大部分数据都是比较干净的，只有很小部 分数据受到污染，这样的条件下SSC稀疏Z而更充 分地利用了样本间的强相关性，从表1中可以看到 SSC比LRR的子空间聚类效果更好。 表1LSR、LRR、SSC和SSR SC在Hopkins1:55 数据集上实验的子空间聚类错误率 专西店店店志店因 Table 1 Subspace clustering errors of LSR,LRR,SSC and SSR_SC on Hopkins155 dataset (a)SSC 错误率 LSR LRR SSC SSR_SC 最大值 0.3971 0.47640.4144 0.4048 平均值 0.0421 0.0513 0.0302 0.0183 中位数 0.0052 0.0053 0 0 8老专古图 标准差 0.0860 0.10010.0762 0.0548 否香5图所所 4.2.2数字图像和人脸图像上的实验 为了证明本文算法SSR_SC在实际数据集中也 具有适用性，本文还在USPS、ORL以及Jaffe等数字 BeS因G8国 图像和人脸图像数据集也进行了对比实验。实验结 果如表2所示。 (b)LRR 表2LSR、LRR、SSC和SSR_SC分别在Jaffe和ORL 以及USPS数据集实验的子空间聚类错误率 66日 雪因传香香名图 Table 2 Subspace clustering errors of LSR,LRR,SSC and SSR_SC on Jaffe,ORL and USPS dataset 数据集 LSR LRR SSC SSR_SC 因香因香香®6香质因 USPS 0.2610 0.36700.4750 0.1240 ORL 0.22250.55000.2250 0.2075 Jaffe 0.37910.13620.1174 0.0141 从表2数据可知，SSR_SC算法在Jafe数据集 (c)SSR_SC 上取得了最优的效果，其子空间聚类错误率为 图1SSC算法、LRR算法和SSR_SC算法分别对ORL 1.41%,远远低于LSR,LRR和SSC算法的错误率 数据集聚类的效果 效果与LRR和SSC相比提升了10倍，甚至比LSR Fig.1 The subspace clustering effect of SSC,LRR and 算法提高了接近40倍。而在USPS和ORL数据集 SSR_SC on ORL dataset

法对比，错误率均值小 ２． ３８％，标准差小 ３． １２％。 ＬＳＲ 中使用 Ｌ２ ⁃ｎｏｒｍ 正则化项约束相似度矩阵 Ｚ，能 使 Ｚ 具有很好的块对角化结构，但是其并没有对 Ｚ 稀疏而影响其最终的聚类效果。 ＳＳＲ＿ＳＣ 与 ＬＲＲ 算 法对比，最大错误率小 ７．１６％，均值小 ３．３０％，标准 差小 ４．５３％。 其中 ＬＲＲ 利用 Ｌ２，１ ⁃ｎｏｒｍ 项惩罚相似 度矩阵 Ｚ 而可以去除噪音和离群点的影响，但是， 其没有对 Ｚ 稀疏。 而本文提出的 ＳＳＲ＿ＳＣ 算法通过 Ｌ２，１ ⁃ｎｏｒｍ 正则化项惩罚相似度矩阵而使其具有鲁 棒性，且还对 Ｚ 进行稀疏，所以能获得更好的子空 间聚类效果。 与 ＳＳＣ 算法比较，本文算法 ＳＳＲ＿ＳＣ 也取得了更好的效果，最大错误率小 ０．９６％，均值错 误率小 １．１９％，标准差错误率小 ２．１４％。 Ｈｏｐｋｉｎｓ１５５ 数据集的大部分数据都是比较干净的，只有很小部 分数据受到污染，这样的条件下 ＳＳＣ 稀疏Ｚ而更充 分地利用了样本间的强相关性，从表 １ 中可以看到 ＳＳＣ 比 ＬＲＲ 的子空间聚类效果更好。 表 １ ＬＳＲ、ＬＲＲ、ＳＳＣ 和 ＳＳＲ＿ＳＣ 在 Ｈｏｐｋｉｎｓ１５５ 数据集上实验的子空间聚类错误率 Ｔａｂｌｅ １ Ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ ｅｒｒｏｒｓ ｏｆ ＬＳＲ， ＬＲＲ， ＳＳＣ ａｎｄ ＳＳＲ＿ＳＣ ｏｎ Ｈｏｐｋｉｎｓ１５５ ｄａｔａｓｅｔ 错误率 ＬＳＲ ＬＲＲ ＳＳＣ ＳＳＲ＿ＳＣ 最大值 ０．３９７ １ ０．４７６ ４ ０．４１４ ４ ０．４０４ ８ 平均值 ０．０４２ １ ０．０５１ ３ ０．０３０ ２ ０．０１８ ３ 中位数 ０．００５ ２ ０．００５ ３ ０ ０ 标准差 ０．０８６ ０ ０．１００ １ ０．０７６ ２ ０．０５４ ８ ４．２．２ 数字图像和人脸图像上的实验 为了证明本文算法 ＳＳＲ＿ＳＣ 在实际数据集中也 具有适用性，本文还在 ＵＳＰＳ、ＯＲＬ 以及 Ｊａｆｆｅ 等数字 图像和人脸图像数据集也进行了对比实验。 实验结 果如表 ２ 所示。 表 ２ ＬＳＲ、ＬＲＲ、ＳＳＣ 和 ＳＳＲ＿ＳＣ 分别在 Ｊａｆｆｅ 和 ＯＲＬ 以及 ＵＳＰＳ 数据集实验的子空间聚类错误率 Ｔａｂｌｅ ２ Ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ ｅｒｒｏｒｓ ｏｆ ＬＳＲ， ＬＲＲ， ＳＳＣ ａｎｄ ＳＳＲ＿ＳＣ ｏｎ Ｊａｆｆｅ， ＯＲＬ ａｎｄ ＵＳＰＳ ｄａｔａｓｅｔ 数据集 ＬＳＲ ＬＲＲ ＳＳＣ ＳＳＲ＿ＳＣ ＵＳＰＳ ０．２６１ ０ ０．３６７ ０ ０．４７５ ０ ０．１２４ ０ ＯＲＬ ０．２２２ ５ ０．５５０ ０ ０．２２５ ０ ０．２０７ ５ Ｊａｆｆｅ ０．３７９ １ ０．１３６ ２ ０．１１７ ４ ０．０１４ １ 从表 ２ 数据可知，ＳＳＲ＿ＳＣ 算法在 Ｊａｆｆｅ 数据集 上取得 了 最 优 的 效 果， 其 子 空 间 聚 类 错 误 率 为 １．４１％，远远低于 ＬＳＲ，ＬＲＲ 和 ＳＳＣ 算法的错误率， 效果与 ＬＲＲ 和 ＳＳＣ 相比提升了 １０ 倍，甚至比 ＬＳＲ 算法提高了接近 ４０ 倍。 而在 ＵＳＰＳ 和 ＯＲＬ 数据集 上同样也取得了较低的子空间聚类错误率，其中在 ＵＳＰＳ 数据集上，相比 ＬＳＲ、ＬＲＲ 和 ＳＳＣ 分别提高了 １３．７０％、２４．３０％、３５．１０％；在 ＯＲＬ 数据集上分别提 高了 １．５０％、３４．２５％、１．７５％。 因此，可以认为本文 提出的 ＳＳＲ ＿ ＳＣ 算法是一种高效的子空间聚类 算法。 为了更加直观地对比 ＬＲＲ、ＳＳＣ 和 ＳＳＲ＿ＳＣ 算 法的子空间聚类效果，选取 ＯＲＬ 数据集里 １００ 张图 片（１０ 人，每人 １０ 张）进行实验，得到的实验结果如 图 １ 所示。 （ａ）ＳＳＣ （ｂ）ＬＲＲ （ｃ）ＳＳＲ＿ＳＣ 图 １ ＳＳＣ 算法、ＬＲＲ 算法和 ＳＳＲ＿ＳＣ 算法分别对 ＯＲＬ 数据集聚类的效果 Ｆｉｇ．１ Ｔｈｅ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ ｅｆｆｅｃｔ ｏｆ ＳＳＣ， ＬＲＲ ａｎｄ ＳＳＲ＿ＳＣ ｏｎ ＯＲＬ ｄａｔａｓｅｔ ·７００· 智 能 系 统 学 报 第 １１ 卷

第5期 林大华，等：稀疏样本自表达子空间聚类算法 ·701· 图1中，每行都代表一个子空间，短划线方框区 2765-2781 域表示错误聚类的图片。从图1可以直观的看出， [6]LIU Guangcan,LIN Zhouchen,YAN Shuicheng,et al.Ro- 本文提出的SSR_SC算法取得的子空间聚类效果明 bust recovery of subspace structures by low-rank representa- 显好于LRR算法和SSC算法。其中，SSR_SC只将 tion[J].IEEE transactions on pattern analysis and machine intelligence,2013,35(1):171-184. 该数据集的2个人错误地聚类到其他子空间，而 [7]LU Canyi,MIN Hai,ZHAO Zhonggiu,et al.Robust and LRR和SSC算法聚类错误的图片数量分别为17张 efficient subspace segmentation via least squares regression 和19张，其中还存在将同一个人的图像平均的聚类 [C]//Proceedings of the 12th European Conference on 为2个子空间的情况，如图1(a)方点线方框所示， Computer Vision.Berlin Heidelberg,2012:347-360. 甚至出现将不同2组人聚类到同一个子空间的情 [8]FENG Jiashi,LIN Zhouchen,XU Huan,et al.Robust sub- 况。综上分析，SSR_SC算法比现有的子空间聚类 space segmentation with block-diagonal prior[C]//Proceed- 方法有更好的子空间聚类效果。 ings of Conference on Computer Vision and Pattern Recogni- tion.Columbus,OH,USA,2014:3818-3825 5结束语 [9]欧阳佩佩，赵志刚，刘桂峰.一种改进的稀疏子空间聚 提出一种综合稀疏学习和样本自表达的子空间 类算法[J].青岛大学学报：自然科学版，2014,27(3)： 44-48 聚类方法称为稀疏样本自表达算法。该算法通过充 OUYANG Peipei,ZHAO Zhigang,LIU Guifeng.An im- 分考虑样本之间的相关性而进行样本自表达，并且 proved sparse subspace clustering algorithm[].Journal of 通过稀疏学习理论进行优化，即通过L,-nom使相 Qingdao university:natural science edition,2014,27(3): 似度矩阵得到适当稀疏而让每个样本由与其相似性 44-48. 高的样本进行表达，通过L2.1-nom解决样本自表达 [10]杨国亮，罗璐，丰义琴，等.基于低秩稀疏图的结构保 过程中噪音和离群点的干扰。与SSC算法和LRR 持投影算法[J].计算机工程与科学，2015,37(8)： 算法比较，SSR_SC算法具有更好的鲁棒性和实现 1584-1590. 构造一个良好相似度矩阵的目的。此外，在Hop YANG Guoliang,LUO Lu,FENG Yigin,et al.Structure kinss155、USPS、ORL和Jafe等数据集上实验的结 preserving projection algorithm based on low rank and 果表明，SSR_SC算法在实际数据集，如运动目标分 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."Miss- ing is useful":missing values in cost-sensitive decision [1]王卫卫，李小平，冯象初，等.稀疏子空间聚类综述[J] trees[J].IEEE transactions on knowledge and data engi- 自动化学报，2015,41(8)：1373-1384. neering,2005,17(12):1689-1693. WANG Weiwei,LI Xiaoping,FENG Xiangchu,et al.A [13]ZHU Xiaofeng,HUANG Zi,CUI Jiangtao,et al.Video-to- survey on sparse subspace clustering[J].Acta automatica shot tag propagation by graph sparse group lasso[J].IEEE sinica,2015,41(8):1373-1384 transactions on multimedia,2013,15(3):633-646 [2]VIDAL R,MA Yi,SASTRY S.Generalized principal com- [14]ZHU Xiaofeng,ZHANG Lei,HUANG Zi.A sparse em- ponent analysis(GPCA)[J].IEEE transactions on pattern bedding and least variance encoding approach to hashing analysis and machine intelligence,2005,27(12):1945- [J].IEEE transactions on image processing,2014,23 1959. (9):3737-3750. [3]TSENG P.Nearest q-flat to m points[J].Journal of optimi- [15]TRON R,VIDAL R.A benchmark for the comparison of 3- zation theory and applications,2000,105(1):249-252. D motion segmentation algorithms [C]//Proceedings of [4]FISCHLER M A,BOLLES R C.Random sample consen- Conference on Computer Vision and Pattern Recognition. sus:a paradigm for model fitting with applications to image Minneapolis,MN,USA,2007:1-8. analysis and automated cartography J.Communications of [16]LYONS M,AKAMATSU S,KAMACHI M,et al.Coding the ACM.1981,24(6):381-395 facial expressions with gabor wavelets C//Proceedings of [5]ELHAMIFAR E,VIDAL R.Sparse subspace clustering:al- the 3rd IEEE International Conference on Automatic Face gorithm,theory,and applications[J].IEEE transactions on and Gesture Recognition.Nara,1998:200-205 pattern analysis and machine intelligence,2013,35(11): [17]HULL J J.A database for handwritten text recognition re-

图 １ 中，每行都代表一个子空间，短划线方框区 域表示错误聚类的图片。 从图 １ 可以直观的看出， 本文提出的 ＳＳＲ＿ＳＣ 算法取得的子空间聚类效果明 显好于 ＬＲＲ 算法和 ＳＳＣ 算法。 其中，ＳＳＲ＿ＳＣ 只将 该数据集的 ２ 个人错误地聚类到其他子空间，而 ＬＲＲ 和 ＳＳＣ 算法聚类错误的图片数量分别为 １７ 张 和 １９ 张，其中还存在将同一个人的图像平均的聚类 为 ２ 个子空间的情况，如图 １（ａ）方点线方框所示， 甚至出现将不同 ２ 组人聚类到同一个子空间的情 况。 综上分析，ＳＳＲ＿ＳＣ 算法比现有的子空间聚类 方法有更好的子空间聚类效果。 ５ 结束语 提出一种综合稀疏学习和样本自表达的子空间 聚类方法称为稀疏样本自表达算法。 该算法通过充 分考虑样本之间的相关性而进行样本自表达，并且 通过稀疏学习理论进行优化，即通过 Ｌ１ ⁃ｎｏｒｍ 使相 似度矩阵得到适当稀疏而让每个样本由与其相似性 高的样本进行表达，通过 Ｌ２，１ ⁃ｎｏｒｍ 解决样本自表达 过程中噪音和离群点的干扰。 与 ＳＳＣ 算法和 ＬＲＲ 算法比较，ＳＳＲ＿ＳＣ 算法具有更好的鲁棒性和实现 构造一个良好相似度矩阵的目的。 此外，在 Ｈｏｐ⁃ ｋｉｎｓｓ１５５、ＵＳＰＳ、ＯＲＬ 和 Ｊａｆｆｅ 等数据集上实验的结 果表明，ＳＳＲ＿ＳＣ 算法在实际数据集，如运动目标分 割和图像聚类等方面，能获得更好的子空间聚类效 果。 此后工作将提出的方法应用于更广泛的领域， 如医学数据、文本数据以及金融数据等高维数据的 聚类分析。 参考文献： ［１］王卫卫， 李小平， 冯象初， 等． 稀疏子空间聚类综述［Ｊ］． 自动化学报， ２０１５， ４１（８）： １３７３⁃１３８４． ＷＡＮＧ Ｗｅｉｗｅｉ， ＬＩ Ｘｉａｏｐｉｎｇ， ＦＥＮＧ Ｘｉａｎｇｃｈｕ， ｅｔ ａｌ． Ａ ｓｕｒｖｅｙ ｏｎ ｓｐａｒｓｅ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ ［ Ｊ］． Ａｃｔａ ａｕｔｏｍａｔｉｃａ ｓｉｎｉｃａ， ２０１５， ４１（８）： １３７３⁃１３８４． ［２］ＶＩＤＡＬ Ｒ， ＭＡ Ｙｉ， ＳＡＳＴＲＹ Ｓ． Ｇｅｎｅｒａｌｉｚｅｄ ｐｒｉｎｃｉｐａｌ ｃｏｍ⁃ ｐｏｎｅｎｔ ａｎａｌｙｓｉｓ （ＧＰＣＡ） ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００５， ２７ （ １２）： １９４５⁃ １９５９． ［３］ＴＳＥＮＧ Ｐ． Ｎｅａｒｅｓｔ ｑ⁃ｆｌａｔ ｔｏ ｍ ｐｏｉｎｔｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｏｐｔｉｍｉ⁃ ｚａｔｉｏｎ ｔｈｅｏｒｙ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， ２０００， １０５（１）： ２４９⁃２５２． ［４］ ＦＩＳＣＨＬＥＲ Ｍ Ａ， ＢＯＬＬＥＳ Ｒ Ｃ． Ｒａｎｄｏｍ ｓａｍｐｌｅ ｃｏｎｓｅｎ⁃ ｓｕｓ： ａ ｐａｒａｄｉｇｍ ｆｏｒ ｍｏｄｅｌ ｆｉｔｔｉｎｇ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ ｉｍａｇｅ ａｎａｌｙｓｉｓ ａｎｄ ａｕｔｏｍａｔｅｄ ｃａｒｔｏｇｒａｐｈｙ［ Ｊ］． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ， １９８１， ２４（６）： ３８１⁃３９５． ［５］ＥＬＨＡＭＩＦＡＲ Ｅ， ＶＩＤＡＬ Ｒ． Ｓｐａｒｓｅ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ： ａｌ⁃ ｇｏｒｉｔｈｍ， ｔｈｅｏｒｙ， ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１３， ３５（ １１）： ２７６５⁃２７８１． ［６］ＬＩＵ Ｇｕａｎｇｃａｎ， ＬＩＮ Ｚｈｏｕｃｈｅｎ， ＹＡＮ Ｓｈｕｉｃｈｅｎｇ， ｅｔ ａｌ． Ｒｏ⁃ ｂｕｓｔ ｒｅｃｏｖｅｒｙ ｏｆ ｓｕｂｓｐａｃｅ ｓｔｒｕｃｔｕｒｅｓ ｂｙ ｌｏｗ⁃ｒａｎｋ ｒｅｐｒｅｓｅｎｔａ⁃ ｔｉｏｎ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１３， ３５（１）： １７１⁃１８４． ［７］ＬＵ Ｃａｎｙｉ， ＭＩＮ Ｈａｉ， ＺＨＡＯ Ｚｈｏｎｇｑｉｕ， ｅｔ ａｌ． Ｒｏｂｕｓｔ ａｎｄ ｅｆｆｉｃｉｅｎｔ ｓｕｂｓｐａｃｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｖｉａ ｌｅａｓｔ ｓｑｕａｒｅｓ ｒｅｇｒｅｓｓｉｏｎ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １２ｔｈ Ｅｕｒｏｐｅａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ， ２０１２： ３４７⁃３６０． ［８］ＦＥＮＧ Ｊｉａｓｈｉ， ＬＩＮ Ｚｈｏｕｃｈｅｎ， ＸＵ Ｈｕａｎ， ｅｔ ａｌ． Ｒｏｂｕｓｔ ｓｕｂ⁃ ｓｐａｃｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｗｉｔｈ ｂｌｏｃｋ⁃ｄｉａｇｏｎａｌ ｐｒｉｏｒ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄ⁃ ｉｎｇｓ ｏｆ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉ⁃ ｔｉｏｎ． Ｃｏｌｕｍｂｕｓ， ＯＨ， ＵＳＡ， ２０１４： ３８１８⁃３８２５． ［９］欧阳佩佩， 赵志刚， 刘桂峰． 一种改进的稀疏子空间聚 类算法［Ｊ］． 青岛大学学报： 自然科学版， ２０１４， ２７（３）： ４４⁃４８． ＯＵＹＡＮＧ Ｐｅｉｐｅｉ， ＺＨＡＯ Ｚｈｉｇａｎｇ， ＬＩＵ Ｇｕｉｆｅｎｇ． Ａｎ ｉｍ⁃ ｐｒｏｖｅｄ ｓｐａｒｓｅ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｑｉｎｇｄａｏ ｕｎｉｖｅｒｓｉｔｙ： ｎａｔｕｒａｌ ｓｃｉｅｎｃｅ ｅｄｉｔｉｏｎ， ２０１４， ２７（３）： ４４⁃４８． ［１０］杨国亮， 罗璐， 丰义琴， 等． 基于低秩稀疏图的结构保 持投影算法［ Ｊ］． 计算机工程与科学， ２０１５， ３７ （ ８）： １５８４⁃１５９０． ＹＡＮＧ Ｇｕｏｌｉａｎｇ， ＬＵＯ Ｌｕ， ＦＥＮＧ Ｙｉｑｉｎ， ｅｔ ａｌ． Ｓｔｒｕｃｔｕｒｅ ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｊｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｌｏｗ ｒａｎｋ ａｎｄ ｓｐａｒｓｅ ｇｒａｐｈ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ｓｃｉｅｎｃｅ， ２０１５， ３７（８）： １５８４⁃１５９０． ［１１］ ＺＨＵ Ｘｉａｏｆｅｎｇ， ＨＵＡＮＧ Ｚｉ， ＹＡＮＧ Ｙａｎｇ， ｅｔ ａｌ． Ｓｅｌｆ⁃ ｔａｕｇｈｔ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅｄｕｃｔｉｏｎ ｏｎ ｔｈｅ ｈｉｇｈ⁃ｄｉｍｅｎｓｉｏｎａｌ ｓｍａｌｌ⁃ｓｉｚｅｄ ｄａｔａ［ Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１３， ４６（ １）： ２１５⁃２２９． ［１２］ＺＨＡＮＧ Ｓｈｉｃｈａｏ， ＱＩＮ Ｚｈｅｎｘｉｎｇ， ＬＩＮＧ Ｃ Ｘ， ｅｔ ａｌ． “Ｍｉｓｓ⁃ ｉｎｇ ｉｓ ｕｓｅｆｕｌ”： ｍｉｓｓｉｎｇ ｖａｌｕｅｓ ｉｎ ｃｏｓｔ⁃ｓｅｎｓｉｔｉｖｅ ｄｅｃｉｓｉｏｎ ｔｒｅｅｓ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｋｎｏｗｌｅｄｇｅ ａｎｄ ｄａｔａ ｅｎｇｉ⁃ ｎｅｅｒｉｎｇ， ２００５， １７（１２）： １６８９⁃１６９３． ［１３］ＺＨＵ Ｘｉａｏｆｅｎｇ， ＨＵＡＮＧ Ｚｉ， ＣＵＩ Ｊｉａｎｇｔａｏ， ｅｔ ａｌ． Ｖｉｄｅｏ⁃ｔｏ⁃ ｓｈｏｔ ｔａｇ ｐｒｏｐａｇａｔｉｏｎ ｂｙ ｇｒａｐｈ ｓｐａｒｓｅ ｇｒｏｕｐ ｌａｓｓｏ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｍｕｌｔｉｍｅｄｉａ， ２０１３， １５（３）： ６３３⁃６４６． ［１４］ ＺＨＵ Ｘｉａｏｆｅｎｇ， ＺＨＡＮＧ Ｌｅｉ， ＨＵＡＮＧ Ｚｉ． Ａ ｓｐａｒｓｅ ｅｍ⁃ ｂｅｄｄｉｎｇ ａｎｄ ｌｅａｓｔ ｖａｒｉａｎｃｅ ｅｎｃｏｄｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｈａｓｈｉｎｇ ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｍａｇｅ ｐｒｏｃｅｓｓｉｎｇ， ２０１４， ２３ （９）： ３７３７⁃３７５０． ［１５］ＴＲＯＮ Ｒ， ＶＩＤＡＬ Ｒ． Ａ ｂｅｎｃｈｍａｒｋ ｆｏｒ ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ３⁃ Ｄ ｍｏｔｉｏｎ ｓｅｇｍｅｎｔａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ［ Ｃ ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ． Ｍｉｎｎｅａｐｏｌｉｓ， ＭＮ， ＵＳＡ， ２００７： １⁃８． ［１６］ＬＹＯＮＳ Ｍ， ＡＫＡＭＡＴＳＵ Ｓ， ＫＡＭＡＣＨＩ Ｍ， ｅｔ ａｌ． Ｃｏｄｉｎｇ ｆａｃｉａｌ ｅｘｐｒｅｓｓｉｏｎｓ ｗｉｔｈ ｇａｂｏｒ ｗａｖｅｌｅｔｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ３ｒｄ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｕｔｏｍａｔｉｃ Ｆａｃｅ ａｎｄ Ｇｅｓｔｕｒｅ Ｒｅｃｏｇｎｉｔｉｏｎ． Ｎａｒａ， １９９８： ２００⁃２０５． ［１７］ＨＵＬＬ Ｊ Ｊ． Ａ ｄａｔａｂａｓｅ ｆｏｒ ｈａｎｄｗｒｉｔｔｅｎ ｔｅｘｔ ｒｅｃｏｇｎｉｔｉｏｎ ｒｅ⁃ 第 ５ 期 林大华，等：稀疏样本自表达子空间聚类算法 ·７０１·

·702 智能系统学报 第11卷 search[J].IEEE transactions on pattern analysis and ma- 杨利锋，男，1989年生，硕士研究 chine intelligence,1994,16(5):550-554. 生，主要研究方向为数据挖掘和机器 [18]SAMARIA FS,HARTERT A C.Parameterisation of a sto- 学习。 chastic model for human face identification[C]//Proceed- ings of the 2nd IEEE Workshop on Applications of Comput- er Vision.Sarasota,FL,USA,1994:138-142. [19]FENG Jiashi,LIN Zhouchen,XU Huan,et al.Robust subspace segmentation with block-diagonal prior C]// 邓振云，男，1991年生，硕士研究 Proceedings of Conference on Computer Vision and Pattern 生，主要研究方向为机器学习、数据挖 Recognition.Columbus,OH,USA,2014:3818-3825. 掘。发表学术论文8篇，其中被SCI、El 作者简介： 检索4篇。 林大华，男，1979年生，主要研究方 向为机器学习、数据挖掘。 2017国际群体智能会议 The Eighth International Conference on Swarm 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 re- searchers and practitioners to exchange latest advantages in theories,technologies,and applications of swarm intel- ligence and related areas.The ICSI'2017 is the eighth annual event in this high-reputation ICSI series after Bali e- vent (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 se- lected for SCI-indexed Transaction and Journal including IEEE/ACM Transactions on CBB,NC,CC,IJSIR, IJCIPR,ete.). 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 har- bor 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

ｓｅａｒｃｈ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａ⁃ ｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， １９９４， １６（５）： ５５０⁃５５４． ［１８］ＳＡＭＡＲＩＡ Ｆ Ｓ， ＨＡＲＴＥＲＴ Ａ Ｃ． Ｐａｒａｍｅｔｅｒｉｓａｔｉｏｎ ｏｆ ａ ｓｔｏ⁃ ｃｈａｓｔｉｃ ｍｏｄｅｌ ｆｏｒ ｈｕｍａｎ ｆａｃｅ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄ⁃ ｉｎｇｓ ｏｆ ｔｈｅ ２ｎｄ ＩＥＥＥ Ｗｏｒｋｓｈｏｐ ｏｎ Ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔ⁃ ｅｒ Ｖｉｓｉｏｎ． Ｓａｒａｓｏｔａ， ＦＬ， ＵＳＡ， １９９４： １３８⁃１４２． ［１９］ ＦＥＮＧ Ｊｉａｓｈｉ， ＬＩＮ Ｚｈｏｕｃｈｅｎ， ＸＵ Ｈｕａｎ， ｅｔ ａｌ． Ｒｏｂｕｓｔ ｓｕｂｓｐａｃｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｗｉｔｈ ｂｌｏｃｋ⁃ｄｉａｇｏｎａｌ ｐｒｉｏｒ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ． Ｃｏｌｕｍｂｕｓ， ＯＨ， ＵＳＡ， ２０１４： ３８１８⁃３８２５． 作者简介： 林大华，男，１９７９ 年生，主要研究方 向为机器学习、数据挖掘。 杨利锋，男，１９８９ 年生，硕士研究 生，主要研究方向为数据挖掘和机器 学习。 邓振云，男，１９９１ 年生，硕士研究 生，主要研究方向为机器学习、数据挖 掘。 发表学术论文 ８ 篇，其中被 ＳＣＩ、ＥＩ 检索 ４ 篇。 ２０１７ 国际群体智能会议 Ｔｈｅ Ｅｉｇｈｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｗａｒｍ Ｉｎｔｅｌｌｉｇｅｎｃｅ （ ＩＣＳＩ’２０１７） Ｊｕｌｙ ２７－Ａｕｇｕｓｔ ０１， ２０１７， Ｆｕｋｕｏｋａ， Ｊａｐａｎ Ｔｈｅ Ｅｉｇｈｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｗａｒｍ Ｉｎｔｅｌｌｉｇｅｎｃｅ （ＩＣＳＩ’２０１７） ｓｅｒｖｅｓ ａｓ ａｎ ｉｍｐｏｒｔａｎｔ ｆｏｒｕｍ ｆｏｒ ｒｅ⁃ ｓｅａｒｃｈｅｒｓ ａｎｄ ｐｒａｃｔｉｔｉｏｎｅｒｓ ｔｏ ｅｘｃｈａｎｇｅ ｌａｔｅｓｔ ａｄｖａｎｔａｇｅｓ ｉｎ ｔｈｅｏｒｉｅｓ， ｔｅｃｈｎｏｌｏｇｉｅｓ， ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｓｗａｒｍ ｉｎｔｅｌ⁃ ｌｉｇｅｎｃｅ ａｎｄ ｒｅｌａｔｅｄ ａｒｅａｓ． Ｔｈｅ ＩＣＳＩ’２０１７ ｉｓ ｔｈｅ ｅｉｇｈｔｈ ａｎｎｕａｌ ｅｖｅｎｔ ｉｎ ｔｈｉｓ ｈｉｇｈ－ｒｅｐｕｔａｔｉｏｎ ＩＣＳＩ ｓｅｒｉｅｓ ａｆｔｅｒ Ｂａｌｉ ｅ⁃ ｖｅｎｔ （ＩＣＳＩ’２０１６）， Ｂｅｉｊｉｎｇ ｊｏｉｎｔ ｅｖｅｎｔ （ ＩＣＳＩ －ＣＣＩ’ ２０１５）， Ｈｅｆｅｉ ｅｖｅｎｔ （ ＩＣＳＩ’ ２０１４）， Ｈａｒｂｉｎ ｅｖｅｎｔ （ ＩＣＳＩ’ ２０１３）， Ｓｈｅｎｚｈｅｎ ｅｖｅｎｔ （ＩＣＳＩ’２０１２）， Ｃｈｏｎｇｑｉｎｇ ｅｖｅｎｔ （ ＩＣＳＩ’ ２０１１） ａｎｄ Ｂｅｉｊｉｎｇ ｅｖｅｎｔ （ ＩＣＳＩ’ ２０１０）． Ｐａｐｅｒｓ ｐｒｅｓｅｎｔｅｄ ａｔ ｔｈｅ ＩＣＳＩ’ ２０１７ ｗｉｌｌ ｂｅ ｐｕｂｌｉｓｈｅｄ ｉｎ Ｓｐｒｉｎｇｅｒ’ ｓ Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ （ ｉｎｄｅｘｅｄ ｂｙ ＥＩ Ｃｏｍｐｅｎｄｅｘ， ＩＳＴＰ， ＤＢＬＰ， ＳＣＯＰＵＳ， Ｗｅｂ ｏｆ Ｓｃｉｅｎｃｅ ＩＳＩ Ｔｈｏｍｓｏｎ， ｅｔｃ．）， ｓｏｍｅ ｈｉｇｈ－ｑｕａｌｉｔｙ ｐａｐｅｒｓ ｗｉｌｌ ｂｅ ｓｅ⁃ ｌｅｃｔｅｄ ｆｏｒ ＳＣＩ－ｉｎｄｅｘｅｄ Ｔｒａｎｓａｃｔｉｏｎ ａｎｄ Ｊｏｕｒｎａｌ （ ｉｎｃｌｕｄｉｎｇ ＩＥＥＥ ／ ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ＣＢＢ， ＮＣ， ＣＣ， ＩＪＳＩＲ， ＩＪＣＩＰＲ， ｅｔｃ．）． Ｔｈｅ ＩＣＳＩ’２０１７ ｗｉｌｌ ｂｅ ｈｅｌｄ ｉｎ ｔｈｅ ｃｅｎｔｅｒ ｏｆ ｔｈｅ Ｆｕｋｕｏｋａ Ｃｉｔｙ． Ｈｉｓｔｏｒｉｃａｌ ｃｉｔｙ， Ｆｕｋｕｏｋａ， ｉｓ ｔｈｅ ５ｔｈ ｌａｒｇｅｓｔ ｃｉｔｙ ｉｎ Ｊａｐａｎ ｗｉｔｈ １．５５ ｍｉｌｌｉｏｎ ｐｏｐｕｌａｔｉｏｎｓ ａｎｄ ｉｓ ｔｈｅ ７ｔｈ ｍｏｓｔ ｌｉｖｅａｂｌｅ ｃｉｔｙ ｉｎ ｔｈｅ ｗｏｒｌｄ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ２０１６ Ｑｕａｌｉｔｙ ｏｆ Ｌｉｆｅ Ｓｕｒｖｅｙ ｂｙ Ｍｏｎｏｃｌｅ． Ｆｕｋｕｏｋａ ｌｏｃａｔｅｓ ａｔ ｔｈｅ ｎｏｒｔｈｅｒｎ ｅｎｄ ｏｆ ｔｈｅ Ｋｙｕｓｈｕ Ｉｓｌａｎｄ ａｎｄ ｉｓ ｔｈｅ ｅｃｏｎｏｍｉｃ ａｎｄ ｃｕｌｔｕｒａｌ ｃｅｎｔｅｒ ｏｆ ｗｈｏｌｅ Ｋｙｕｓｈｕ Ｉｓｌａｎｄ． Ｂｅｃａｕｓｅ ｏｆ ｉｔｓ ｃｌｏｓｅｎｅｓｓ ｔｏ ｔｈｅ Ａｓｉａｎ ｍａｉｎｌａｎｄ， Ｆｕｋｕｏｋａ ｈａｓ ｂｅｅｎ ａｎ ｉｍｐｏｒｔａｎｔ ｈａｒ⁃ ｂｏｒ ｃｉｔｙ ｆｏｒ ｍａｎｙ ｃｅｎｔｕｒｉｅｓ． Ｔｏｄａｙ＇ｓ Ｆｕｋｕｏｋａ ｉｓ ｔｈｅ ｐｒｏｄｕｃｔ ｏｆ ｔｈｅ ｆｕｓｉｏｎ ｏｆ ｔｗｏ ｃｉｔｉｅｓ ｉｎ ｔｈｅ ｙｅａｒ １８８９， ｗｈｅｎ ｔｈｅ ｐｏｒｔ ｃｉｔｙ ｏｆ Ｈａｋａｔａ ａｎｄ ｔｈｅ ｆｏｒｍｅｒ ｃａｓｔｌｅ ｔｏｗｎ ｏｆ Ｆｕｋｕｏｋａ ｗｅｒｅ ｕｎｉｔｅｄ ｉｎｔｏ ｏｎｅ ｃｉｔｙ ｃａｌｌｅｄ Ｆｕｋｕｏｋａ． Ｗｅｂｓｉｔｅ： ｈｔｔｐ： ／ ／ ｗｗｗ．ｉｃ－ｓｉ．ｏｒｇ ／ ·７０２· 智 能 系 统 学 报 第 １１ 卷