拉普拉斯秩约束的子空间聚类算法

第51卷第2期 V o l.51N o.2山东大学学报（工学版）J O U R N A L O F S H A N D O N G U N I V E R S I T Y(E N G I N E E R I N G S C I E N C E)2021年4月A p r.2021文章编号：1672-3961 (2021)02-0065-09D O I： 10.6040/j.issn. 1672-3961.0.2020.182块对角子空间聚类中成对约束的主动式学习解子奇，王立宏*，李谩(烟台大学计算机与控制工程学院，山东烟台264005)摘要:针对块对角表示（b l o c k d i a g o n a l r e p r e s e n t a t i o n，B D R)子空间聚类算法在对子空间重叠的高维数据聚类时效果较差的问题，提出成对约束的块对角子空间聚类（c o n s t r a i n e d s u b s p a c e c lustering w i t h b l o c k d i a g o n a l r e p r e s e n t a t i o n，C B D R)算法，设计主 动式学习策略，获取用户提供的少量数据点成对信息，以改进B D R算法的性能，给出C B D R算法的目标函数和求解过程。

在 测试集上的试验结果表明，C B D R算法的聚类错误率和归一化互信息指标比B D R和S B D R(s t r u c t u r e d b l o c k d i a g o n a l r e p r e s e n­tation) 算法好，而且主动式选取点对方法优于随机选取点对方法，使用少于的约束信息可降低B D R的聚类错误率达到5%以上。

关键词：子空间聚类；主动式学习；成对约束;块对角表示；约束聚类中图分类号:T P181文献标志码:A引用格式:解子奇，王立宏，李熳.块对角子空间聚类中成对约束的主动式学习[J].山东大学学报（工学版），2〇21，51(2):65-73.X I E Ziqi, W A N G L i h o n g,L I M a n.Active learning o f pairwise constraints in block diagonal s u b space clustering[J]. Journal o f S h a n d o n g University (E n g i n e e r i n g Science) ,2021,51(2)：65-73.Active learning of pairwise constraints in block diagonal subspace clusteringXIE Ziqi, WANG Lihong* , LI Man(S c h o o l o f C o m p u t e r a n d C o n t r o l E n g i n e e r i n g,Y a n t a i U n i v e r s i t y,Y a n t a i 264005,S h a n d o n g,C h i n a)A b s t r a c t：F o c u s i n g o n th e p o o r p e r f o r m a n c e o f s u b s p a c e c l ustering b y b l o c k d i a g o n a l r e p r e s e n t a t i o n(B D R)o n h i g h-d i m e n s i o n a l d a t a w i t h o v e r l a p p e d s u b s p a c e s,a n ac t i v e l e a r n i n g strategy w a s d e s i g n e d to o b t a i n partial p a i r w i s e i n f o r m a t i o n a m o n g a f e w d a t a points. A p a i r w i s e c o n s t r a i n e d b l o c k d i a g o n a l r e p r e s e n t a t i o n a l g o r i t h m(C BD R) w a s p r o p o s e d to i m p r o v e the p e r f o r m a n c e o f th eB D R a l g o r i t h m.T h e o b j e c t i v e f u n c t i o n a n d solut i o n p r o c e s s o f th eC BD R w e r e g i v e n.T h e e x p e r i m e n t a l results o n the test datasets s h o w e d that th e C B D R a l g o r i t h m r e d u c e d t h e c l ustering e rror b y m o r e t h a n5%w i t h less t h a n5%〇 cons t r a i n t i n f o r m a t i o n in t e r m s o f c l ustering e rror a n d n o r m a l i z e d m u t u a l i n f o r m a t i o n,w h i c h significantly o u t p e r f o r m e d t h e c o m p a r e d a l g o r i t h m s,i.e., B D R,S B D R (s t r u c t u r e d b l o c k d i a g o n a l r e p r e s e n t a t i o n)w i t h r a n d o m selection o f p a i r w i s e constraints.K e y w o r d s：s u b s p a c e c l ustering ；ac t i v e l e a r n i n g；p a i r w i s e constr a i n t s；b l o c k d i a g o n a l r e p r e s e n t a t i o n；c o n s t r a i n e d clustering〇引言聚类是一种基本的数据挖掘方法，通常应用于文本数据聚类、图像分割和人脸识别等实际问题中。

空间序列低秩稀疏子空间聚类算法作者：由从哲舒振球范洪辉来源：《江苏理工学院学报》2020年第04期摘要：研究序列数据的子空间聚类问题，具体来说，给定从一组序列子空间中提取的数据，任务是将这些数据划分为不同的不相交组。

基于表示的子空间聚类算法，如SSC和LRR 算法，很好地解决了高维数据的聚类问题，但是，这类算法是针对一般数据集进行开发的，并没有考虑序列数据的特性，即相邻帧序列的样本具有一定的相似性。

针对这一问题，提出了一种新的低秩稀疏空间子空间聚类方法（Low Rank and Sparse Spatial Subspace Clustering for Sequential Data，LRS3C）。

该算法寻找序列数据矩阵的稀疏低秩表示，并根据序列数据的特性，在目标函数中引入一个惩罚项来加强近邻数据样本的相似性。

提出的LRS3C算法充分利用空间序列数据的时空信息，提高了聚类的准确率。

在人工数据集、视频序列数据集和人脸图像数据集上的实验表明：提出的方法LRS3C与传统子空间聚类算法相比具有较好的性能。

关键词：低秩表示;稀疏表示;子空间聚类;序列数据中图分类号：TP391.4 文献标识码：A 文献标识码：2095-7394（2020）04-0078-08序列数据特别是视频数据往往具有高维属性，利用传统聚类算法进行分析处理时，往往会遇到“维数灾难”的问题，于是研究人员提出了一系列基于表示的子空间聚类算法，如稀疏表示子空间聚类算法（SSC）和低秩表示算法（LRR），较好地解决了高维数据聚类的问题，从而得到了广泛的关注，并在众多领域得到成功的应用。

但是，这类算法是针对一般数据集设计开发的，在许多实际场景中，数据通常具有顺序或有序的属性，例如视频、动画或其他类型的时间序列数据。

然而，传统的方法假设数据点独立于多个子空间，而忽略了时间序列数据中的连续关系。

如何充分利用空间序列数据这一特性提高聚类性能，是计算机视觉领域中一个重要但又具有挑战性的问题。

拉普拉斯特征映射降维拉普拉斯特征映射降维：从简到繁，由浅入深的探索一、介绍在当今大数据时代，高维数据的处理变得越来越重要。

然而，高维数据的特点是维度多、噪声大，而且存在着冗余信息，这给数据处理和分析带来了挑战。

为了克服这些问题，并发现数据中隐藏的本质特征，降维技术成为了一个热门研究领域。

降维技术旨在从高维空间中提取出最具代表性的低维子空间，并保留原始数据的关键结构信息。

在这个领域中，拉普拉斯特征映射是一种被广泛应用的方法，它在节点图中通过计算节点间的邻接关系，将高维数据映射到低维子空间中。

在本文中，我们将对拉普拉斯特征映射进行全面评估，并深入探讨其原理、优势和应用。

二、原理与方法1. 拉普拉斯矩阵拉普拉斯矩阵是拉普拉斯特征映射的核心工具之一。

它用于度量节点间的相似性，并构建邻接图。

拉普拉斯矩阵包含了两部分：度矩阵和邻接矩阵。

度矩阵反映了每个节点的连接数，而邻接矩阵则表示了节点之间的邻接关系。

通过计算度矩阵和邻接矩阵的差异，我们可以得到拉普拉斯矩阵。

2. 特征向量与特征值通过分解拉普拉斯矩阵，我们可以得到其特征向量和特征值。

特征向量代表了数据在低维子空间中的投影，而特征值则表示了每个特征向量的重要性。

通过选择最大的特征值对应的特征向量，我们可以得到最具代表性的低维子空间。

3. 降维过程降维过程主要包括以下几个步骤：- 构建邻接图：基于数据的相似性，构建邻接图来表示数据之间的关系。

- 计算拉普拉斯矩阵：通过度矩阵和邻接矩阵的差异，计算得到拉普拉斯矩阵。

- 特征值分解：对拉普拉斯矩阵进行特征值分解，得到特征向量和特征值。

- 选择特征向量：选择最大的特征值对应的特征向量，构建低维子空间。

- 数据映射：将原始数据映射到低维子空间，得到降维后的数据。

三、优势与应用拉普拉斯特征映射具有以下几个优势：1. 保持数据局部结构：拉普拉斯特征映射基于邻接关系，能够更好地保持数据的局部结构，减小降维过程中的信息损失。

2. 无监督学习：拉普拉斯特征映射是一种无监督学习方法，不需要事先标注的标签信息，使其适用于各种数据类型和场景。

基于核的低秩子空间聚类算法作者：马凯王伟文由从哲来源：《江苏理工学院学报》2021年第04期摘要：基于稀疏表示和低秩表示的子空间聚类算法是目前的研究热点，但大多数子空间聚类方法只适用于线性子空间或仿射子空间。

针对这一问题，研究了一种能处理非线性模型的核子空间聚类方法。

提出学习一种低秩核映射，通过这种映射，特征空间中的映射数据不仅具有低秩性，而且具有自表达性，从而使得低维子空间结构在高维特征空间中得以呈现。

通过运动分割和人脸图像聚类问题的实验，验证了方法的有效性。

关键词：子空间聚类;低秩表示;核方法;运动分割;人脸聚类中图分类号：TP391.4 文献标识码：A 文章编号：2095-7394（2021）04-0032-06子空间聚类是指将位于一组低维线性子空间中的数据样本点划分到不同子空间中的算法。

该算法在计算机视觉中有多种应用，如：运动分割、图像聚类。

现有的子空间聚类方法大致可分为三类[1]：代数算法、统计方法以及基于谱聚类的方法。

目前，对于子空间聚类的研究热点主要集中在基于表示的谱聚类算法[2-3]，算法主要步骤为：（1）构建亲和矩阵;（2）应用谱聚类对亲和图进行划分，得到聚类结果。

然而，这些方法只能处理线性子空间问题，在实际应用中，数据点可能不完全适合线性子空间模型。

例如，在运动分割问题中，相机通常具有某种程度的透视失真，因此，仿射相机假设不成立;在这种情况下，一个运动的轨迹就会位于非线性子空间中。

为了解决这一问题，也有一些方法通过核技巧将线性子空间聚类扩展到对应的非线性子空间。

例如，核稀疏子空间聚类（KSSC）方法[4]采用多项式核或高斯RBF核将数据矩阵的内积替换为核矩阵。

KSSC算法假设数据是从对称正定（SPD）矩阵中提取的，并将对Log-Euclidean核应用于SPD矩阵上，实现SSC算法的核化。

但是，由于这些方法中使用了预先定义的核，特征空间映射后的数据不能保证低秩;因此，很难形成多个低维子空间结构。

《谱聚类中拉普拉斯约束优化问题的等式证明》一、引言在谱聚类中，拉普拉斯约束优化问题一直是一个备受关注的议题。

本文将围绕这一主题展开深入探讨。

我们将简要介绍谱聚类和拉普拉斯约束优化问题的基本概念，然后逐步深入分析和证明其中的等式。

二、谱聚类和拉普拉斯约束优化问题谱聚类是一种基于图论的聚类方法，它通过对数据的相似性矩阵进行特征值分解来实现聚类。

而拉普拉斯约束优化问题则是谱聚类中的核心问题之一，它可以用数学公式表示为：\[ \min_{F} Tr(F^TLF) \]其中，\(F\) 是一个指示矩阵，\(L\) 表示拉普拉斯矩阵。

在实际应用中，我们常常需要证明：\[ Tr(F^TLF) = 2 \times \sum_{i,j} W_{ij} ||f_i - f_j||_2^2 \]其中，\(W_{ij}\) 是相似性矩阵，\(f_i\) 和 \(f_j\) 分别是样本 \(i\) 和\(j\) 对应的特征向量。

三、证明过程为了证明等式 \(Tr(F^TLF) = 2 \times \sum_{i,j} W_{ij} ||f_i -f_j||_2^2\)，我们需要从矩阵的特征值分解出发，逐步推导证明。

1. 我们对拉普拉斯矩阵 \(L\) 进行特征值分解，得到：\[ L = U \Lambda U^T \]其中，\(U\) 是特征向量矩阵，\(\Lambda\) 是特征值对角矩阵。

2. 将指示矩阵 \(F\) 展开成特征向量矩阵的形式，即：\[ F = U \tilde{F} \]其中，\(\tilde{F}\) 是一个辅助矩阵。

3. 将 \(F^T L F\) 展开成特征向量的形式，并进行化简，得到：\[ F^T L F = \tilde{F}^T U^T L U \tilde{F} \]4. 将拉普拉斯矩阵的特征值分解代入上式，得到：\[ F^T L F = \tilde{F}^T U^T U \Lambda U^T U \tilde{F} \]5. 根据正交特征向量矩阵的性质，可以化简得到：\[ F^T L F = \tilde{F}^T \Lambda \tilde{F} \]6. 根据特征值矩阵的性质，我们可以将 \( \tilde{F}^T \Lambda\tilde{F} \) 展开成求和的形式，并得到证明所需的等式：\[ Tr(F^T L F) = \sum_{i} \lambda_i \sum_{j} (\tilde{F}_{ij})^2 \]\[ = 2 \times \sum_{i,j} W_{ij} ||f_i - f_j||_2^2 \]四、总结与展望通过本文的证明过程，我们成功证明了在谱聚类中的拉普拉斯约束优化问题中的等式。

Sparse subspace clustering:Algorithm,theory,and Application稀疏子空间聚类（SSC）的算法，理论和应用参考文献：1、E. Elhamifar and R. Vidal. Sparse subspace clustering: Algorithm,theory,and Application. IEEE Transactions on Pattern Analysis and Machine Intelligence,20132、E. Elhamifar and R. Vidal. Sparse subspace clustering. In CVPR, 20092013年的这篇论文写得比09年那篇容易懂一些，讨论和实验也更详细。

2013年的这篇可以看成是09那篇会议的扩展版。

一、算法数据没有损坏，求解模型（5）获得矩阵C：数据有损坏（noise and sparse outlying entries)，求解模型（13）获得矩阵C：仿射子空间模型：二、理论1、independent子空间设rank(Yi)=di，Yi表示从第i个子空间Si抽取的Ni个样本构成的矩阵，di 表示Si的维数。

论文的定理1表明，模型（5）的解C*是一个块对角矩阵，属于同一个子空间的数据间的cij可能非零，不属于同一个子空间的数据间的cij=0.2、disjoint子空间对于disjoint子空间，除了满足条件rank(Yi)=di外，还需要满足公式（21）：则可获得与independent子空间下类似的结论：三、应用segmenting multiple motionsin videos: Hopkins 155 datasetclustering images of human faces: Extended Yale B dataset通过计算每对子空间的最小主角(principal angle）小于一给定值的比例，每对子空间中的数据的k近邻至少有一个在其他子空间的比例，可以帮助我们更好地知道两个数据库子空间聚类的挑战和各个算法的性能差别。

基于分布式低秩表示的子空间聚类算法许凯;吴小俊;尹贺峰【摘要】针对基于低秩表示的子空间分割算法运算时间较长、聚类的准确率也不够高，提出一种基于分布式低秩表示的稀疏子空间聚类算法（distributed low rank representation‐based sparse subspace clustering algorithm ，DLRRS），该算法采用分布式并行计算来得到低秩表示的系数矩阵，然后保留系数矩阵每列的前k个绝对值最大系数，其他系数置为0，用此系数矩阵构造一个稀疏的样本关系更突出的相似度矩阵，接着用谱聚类得到聚类结果。

但是其不具备增量学习功能，为此再提出一种基于分布式低秩表示的增量式稀疏子空间聚类算法（scalable distributed low rank representation based sparse subspace clustering algorithm ，SDLRRS），如果有新增样本，可以利用前面的聚类结果对新增样本进行分类得到最后的结果。

实验结果表明：所提2种子空间聚类算法不仅有效减少算法的运算时间，还提高了聚类的准确率，从而验证算法是有效可行的。

%Vision problem ranging from image clustering to motion segmentation can naturally be framed as subspace segmentation problem ,in which one aims to recover multiple low dimensional subspaces from noisy and corrupted input data .Low rank representation‐based subspace segmentation algorithm (LRR) formulates the problem as a convex optimization and achieves impressive results . However ,it needs to take a long time to solve the convex problem ,and the clustering accuracy is not high enough . Therefore , this paper proposes a distributed low rank representation‐based sparse subspace clustering algorithm (DLRRS) .DLRRS adopts the distributed parallel computing to get thecoefficient matrix ,then take the absolute value of each element of the coefficient matrix ,and retain the k largest coefficients per column and set the other elements to 0 to get a new coefficient matrix . Finally ,DLRRS performs spectral clustering over the new coefficient matrix .But it doesn't have incremental learning function ,so there is a scalable distributed low rank representation‐based sparse subspace clustering algorithm (SDLRRS) here .If new samples are brought in ,SDLRRS can use the former clustering result to classify the new samples to get the final result .Experimental results on AR and Extended Yale B datasets show that the improved algorithms can not only obviously reduce the running time , but also achieve higher accuracy , w hich verifies that the proposed algorithms are efficient and feasible .【期刊名称】《计算机研究与发展》【年(卷),期】2016(053)007【总页数】7页(P1605-1611)【关键词】低秩表示;子空间聚类;并行计算;增量学习;系数重建【作者】许凯;吴小俊;尹贺峰【作者单位】江南大学物联网工程学院江苏无锡 214122;江南大学物联网工程学院江苏无锡 214122;江南大学物联网工程学院江苏无锡 214122【正文语种】中文【中图分类】TP18;TP391.4(*****************)高维数据在信息技术高速发展的今天变得越来越普遍，它们通常分布在不同的子空间，这不仅增加了计算机内存的需求量和算法的执行时间，还会对算法[1]的性能产生不利影响，使得很多传统的聚类算法不再适用.最近几年，子空间聚类技术已经吸引了很多学者的关注，它基于高维数据固有的维数通常要比外围空间的维数低很多的思想，用多个子空间对高维数据进行聚类，并且发现适合每一组数据的低维子空间.这在计算机视觉、机器学习和模式识别等方面已经有很多的应用，尤其在图像表示[2]、聚类[3]、运动分割[4]这3个应用上的性能优异.可以将存在的子空间聚类算法分成主要的4类：代数方法[5]、迭代方法[6-7]、统计方法[8]和基于谱聚类的方法[9-10].在这些方法中，基于谱聚类的方法已经显示出其在计算机视觉等方面的优越性能[11-12].谱聚类算法[13]的核心是构建一个合适的相似度矩阵.通常用2种方法来构造相似度矩阵，即距离的倒数和重建系数.1)通过计算2个数据点间的距离倒数来得到相似度，例如欧氏距离.基于距离倒数的方法可以得到数据集的局部结构，但它的值仅仅取决于2个数据点之间的距离，所以对噪声和异常值很敏感.2)基于表示系数的方法，假设每个数据点可以被其他数据点的线性组合进行表示，并且表示系数可以被认为是一种度量.这种度量对噪声和异常值是鲁棒的，因为系数的值不仅取决于2个相连的数据点，还取决于其他的所有数据点.最近的几篇文章已经说明在子空间聚类中表示系数的性能是优于距离倒数的.例如基于低秩表示的子空间分割算法(low rank representation, LRR)[14]和基于稀疏表示的稀疏子空间聚类算法(sparse subspace clustering, SSC)[3].虽然LRR子空间聚类算法已经取得了不错的聚类效果，但是此算法仍有很大的改进空间.我们将文献[15]中的并行计算思想和文献[16]中的增量式学习框架相结合，这样不仅能充分利用当前的多核计算机资源，还能直接处理新增的样本，不需要重新聚类，达到充分利用资源节省运算时间的目的.最主要地，相似度矩阵中的元素衡量的是对应样本的相似程度，是谱聚类算法的核心，构造一个合适的相似度矩阵可以有效地提高算法的准确率.LRR子空间聚类算法直接用低秩表示所得的系数矩阵来构造相似度矩阵，这样会包含过多的冗余关系.本文通过保留系数矩阵每列的前k个绝对值最大系数、其他位置置0，得到一个新的系数矩阵，再用此系数矩阵构造一个稀疏的样本关系更突出的相似度矩阵.在AR数据集和Extended Yale B 人脸库上的实验结果表明本文所提DLRRS(distributed low rank representation-based sparse subspace clustering algorithm)和SDLRRS(scalable distributed low rank representation based sparse subspace clustering algorithm)这2种算法不仅有效减少运算时间，还提高了聚类的准确率.SDLRRS算法还具备增量式学习功能.研究数据空间的结构在很多领域都是一个非常具有挑战性的任务，这通常涉及到秩最小化问题.LRR算法通过求解式(1)来得到秩最小化问题的近似解:其中,*表示核范数，是奇异值的和;C∈n×n就是数据集矩阵Y∈m×n的低秩表示;E对应稀疏的干扰矩阵L可以表示L2,1范数、L1范数或者Frobenius范数，它们的选择取决于在数据集中假设存在哪种误差.具体就是，L2,1范数常被用来描述特定样本的污损和异常值，L1范数更适合用来描述随机的稀疏异常值，Frobenius范数通常用来描述小的高斯噪声.Liu等人[14]应用增广拉格朗日乘子法来解决核范数正规化优化问题可以得到式(1)的解.在算法1中，我们概述了LRR算法的具体实现.算法1. LRR算法[14].输入：数据集矩阵Y∈m×n和类别数u.① 解决核范数最小化式(1)得到C=[c1,c2,…,cn]；② 得到相似度矩阵W=|C|+|C|T；③ 对相似度矩阵W使用谱聚类；④ 输出数据集矩阵Y的类分配.2.1 基于分布式低秩表示的稀疏子空间聚类低秩子空间分割算法可以很精确地处理小规模的数据集，但不能有效处理大规模数据集.为此，文献[15]中提出了一种分布式低秩子空间分割算法，该算法将大规模数据集矩阵Y按列分割成t个小规模的数据矩阵{Z1,Z2,…,Zt}，然后再对这t个小规模数据矩阵进行并行处理.其中第i个LRR子问题的处理形式为运用此分而治之的思想，不仅保证了算法所得结果的准确率，还充分利用计算机的多核硬件资源，极大地降低算法的运算时间.在分别得到t个子系数矩阵后，本文不采用文献[15]中的投影方式来得到最后的系数矩阵，而是直接按列排成最后的系数矩阵.另外，基于低秩表示的子空间分割和分布式低秩子空间分割这2个算法中，都是在得到系数矩阵C后，直接用此系数矩阵来构造相似度矩阵，这样会产生大量冗余的关系，降低算法所得结果的准确率.为此，本文在得到系数矩阵后，先对系数矩阵中的每个元素取绝对值；然后保留每列的前k个最大值，其他位置的元素置为0；再次用新得到的系数矩阵来构造相似度矩阵；最后用谱聚类来得到聚类结果.具体实现过程如算法2所示.算法2. DLRRS算法.输入：数据集矩阵Y∈m×n、类别数u、每列保留的系数个数k和并行计算分割数t.① 将数据集矩阵Y按列分割成t个子数据矩阵{Z 1,Z 2,…,Zt}；② 进行并行计算③ 得到系数矩阵；④ 对系数矩阵C*中的每个元素取绝对值，然后保留每列最大的k个元素，其他元素置为0，得到一个新的系数矩阵；⑤ 得到相似度矩阵；⑥ 对相似度矩阵W使用谱聚类；⑦ 输出数据集矩阵Y的类分配.2.2 分布式低秩增量式稀疏子空间聚类在我们已经完成聚类得到聚类结果后，如果此时有新的样本加入，传统的聚类算法只有重新聚类所有样本，不具备增量学习的功能，会导致计算资源的浪费.在文献[16]中，提出了一种先聚类后分类的增量式聚类算法.本文参考此结构，先进行聚类，然后再用协同表示分类算法对新增的样本进行分类.协同表示分类需要求解的目标函数为其中，y是数据集矩阵Y∈m×n中的一个样本，c是经过数据集矩阵Y对样本y 进行协同表示的系数列向量.在得到最优的系数列向量后，通过计算式(4)得到属于所有类的标准化残差：其中，δj(c*)表示保留系数列向量c*中对应第j类的元素，其他元素置为0；rj(y)表示样本y属于第j类的标准化残差.最后通过式(5)得到最终的分类结果.基于分布式低秩表示的可拓展稀疏子空间聚类算法的实现过程如算法3所示.算法3. SDLRRS算法.输入：数据集矩阵Y∈m×n、类别数u、每列保留的系数个数k和并行计算分割数t.① 使用随机抽样或其他方法从数据集矩阵Y中选出p个数据点，表示为X=[x1,x2,…,xp]，没有被抽到的数据点组成数据矩阵；② 在数据矩阵X上运行DLRRS算法，得到聚类结果；③ 将已经具有类标签的数据矩阵X作为训练集，作为测试集，进行协同表示，可以得到系数矩阵：④ 通过下式计算到所有类的标准化残差：⑤ 通过下式将i归属于第j类：⑥ 输出数据矩阵Y的类分配.本节我们使用子空间聚类准确率(式(6))和归一化互信息(normalized mutual information, NMI)来评估本文基于分布式低秩表示的子空间聚类算法的性能.同时，为了验证本文算法的有效性，实验通过3方面来进行比较分析：1)通过实验将本文算法的参数调到最佳；2)讨论并行计算分割数t对DLRRS算法的影响；3)讨论SDLRRS算法增量学习功能的有效性.其中用到的参考算法有分布式低秩子空间分割算法(distributed low-rank subspace segmentation, DFC-LRR)[15]、基于低秩表示的子空间分割算法(low rank representation, LRR)[14]、稀疏子空间聚类算法(sparse subspace clustering, SSC)[3]、可拓展的基于低秩表示的子空间分割算法(scalable low rank representation, SLRR)[16]和可拓展的稀疏子空间聚类算法(scalable sparse subspace clustering, SSSC)[16].后2种算法分别用LRR和SSC算法先进行聚类，当有新样本加入时再用分类的方法得到结果.实验在同一台PC机(CPU：3.20 GHz，内存：8 GB)上进行，操作系统版本为64位Windows 8，实验工具为MATLAB R2013a.实验选用2个常用的人脸数据集：AR数据集和Extended Yale B数据集.其中AR 数据集包含超过4 000幅126个人(70个男性、56个女性)的人脸图片，这些图片是在不同的表情、不同光照和伪装(戴墨镜或围巾)下得到的.每个人有26幅图片，其中14幅“干净”图片、6幅戴墨镜、6幅戴围巾.这里我们参照文献[17]，从50个男性和50个女性的图片中随机选出1 400幅“干净”的人脸图片.ExtendedYale B人脸库中有38个人，每个人在不同光照条件下得到64张正面人脸图像,每个人脸图像经过裁剪后有192×168个像素.为了降低所有算法的计算复杂度和对内存的需求量，我们将AR数据集中的图片下采样到55×40，Extended Yale B人脸库中的图片都下采样到48×42个像素，并且对它们进行PCA保留98%的信息.各个数据集的详细信息如表1所示.3.1 参数对本文算法的影响本文所提的2种子空间聚类算法包含3个参数：平衡参数λ、每列保留的系数个数k和并行计算的分割数t.本节只讨论平衡参数λ和每列保留的系数个数k对DLRRS和SDLRRS这2种算法聚类质量的影响，先设置t=1，3.2节再详细讨论参数t对算法的影响.图1(a)(b)展示了在AR数据集上参数λ和k对DLRRS算法的影响.当λ逐渐增大的时候，对应的聚类准确率和NMI也逐渐升高，然后趋于稳定.当k从3变到8时，对应的聚类准确率从65.36%变到85.93%，NMI从81.78%变到93.66%;当k继续增大时，对应的聚类准确率和NMI呈现出缓慢下降的趋势.所以DLRRS算法在AR数据集上的参数选择为平衡参数λ=2.2和保留的系数个数k=8.图1(c)(d)展示了在Extended Yale B数据集上参数λ和k对本文算法的影响.当λ从0.05变到2时，对应的聚类准确率从29.41%变到86.45%，NMI从38.37%变到91.15%;当λ从2变到3.8时，对应的聚类准确率和NMI基本保持不变.当k 从3变到9时，对应的聚类准确率从71.58%变到86.62%，NMI从81.70%变到91.84%;在k=9时DLRRS算法取得最好的聚类质量;当k从9变到20时，对应的聚类准确率从86.62%一直下降到78.38%，NMI从91.84%下降到86.27%.所以DLRRS算法在Extended Yale B数据集上的参数选择为平衡参数λ=2和保留的系数个数k=9.由于篇幅所限，在此直接给出SDLRRS算法的参数设置，在AR数据集上为平衡参数λ=3.1和保留的系数个数k=6，在Extended Yale B数据集上为平衡参数λ=2.9和保留的系数个数k=5.3.2 分割数t对算法质量的影响由于实验室只有4核处理器，所以分割数t取1～4，然后在AR和Extended Yale B数据集上进行DLRRS和DFC-LRR这2个算法的对比实验.1) 横向比较.从表2可以看出，在AR数据集上，本文DLRRS算法的聚类准确率较DFC-LRR算法高出5%左右，两者的运算时间基本一致，DLRRS算法稍优一点;在Extended Yale B数据集上，DLRRS算法在聚类准确率方面高出DFC-LRR算法18%左右，在运算时间方面可以节省10 s左右.主要有2方面原因使得本文DLRRS算法完全优于DFC-LRR算法:①保留系数矩阵每列的前k个绝对值最大系数，其他位置置0，然后再构造稀疏的相似度矩阵是有效提高本文算法准确率的关键;②在并行计算时，不采用投影的方式，而是直接按列排成最后的系数矩阵，在保证聚类准确率的同时可以减少算法的运算时间.2) 纵向比较.表2所示为并行计算的分割数t对算法的影响.可以很直观地看出，随着t的增大，DLRRS和DFC-LRR这2个算法的聚类准确率在AR和Extended Yale B数据集上几乎不受影响，但却可以大幅降低算法的执行时间;t=4时较t=1时在AR数据集上可以节省28%左右的时间，在Extended Yale B数据集上可以节省13%左右的时间.由于实验室的计算机只有4核，当t从1变到2时，DLRRS 算法在2个数据集上的执行时间降幅最大，分别为18%和9.8%;当t从2变到3时，执行时间的降幅会变小;当t从3变到4时，执行时间的降幅变得不是很明显，在Extended Yale B数据集上相较t=3时还出现了小幅度的上升，这是由于实验室CPU只有4核，在t=4满负荷运算时不可能只执行并行计算的代码，还要执行其他指令，这并不影响本文算法的有效性.综上，我们可以预见如果计算机的核数变得更多、数据集的规模变大，本文DLRRS算法在牺牲有限准确率的同时，节省运算时间的优势会更加明显.3.3 增量学习功能对已经聚类好的样本，如果此时有新样本加入，DLRRS算法需要重新聚类.为此，本文在DLRRS算法的基础上提出SDLRRS算法使其具备增量学习功能.为了验证SDLRRS算法的性能，我们分别将AR和Extended Yale B数据集中的一半样本随机选出作为新加入的样本进行测试，并和同样具备增量学习功能的SLRR算法和SSSC算法进行对比.对于DLRRS，LRR和SSC这3种不具备增量学习功能的聚类算法直接使用全部样本进行聚类测试.表3给出了不同算法在AR和Extended Yale B数据集上的聚类结果，同时列出了各个算法使用的参数，其中λ是平衡参数，k指系数矩阵中每列保留的系数个数，t是并行计算的分割数，μ是进行交替方向乘子法计算时的惩罚参数. 3.2节我们已经知道并行计算分割数t对DLRRS算法的聚类准确率影响很小，为了方便讨论SDLRRS算法增量学习的效果，本节我们设置t=1.从表3可以看出，SDLRRS算法和DLRRS算法的聚类准确率分别较SLRR算法，LRR算法在AR数据集上有4%左右的提升，在Extended Yale B数据集上有17%的提升.当有新的样本加入时，DLRRS，LRR，SSC这3种算法不得不对所有样本重新聚类，导致大量资源浪费.而可拓展的3种聚类算法SDLRRS，SLRR，SSSC可以直接处理新加入的样本，不需要对所有样本重新聚类.在AR数据集上的准确率，SDLRRS算法比DLRRS算法低3.80%，SLRR算法比LRR算法低1.62%，SSSC算法比SSC算法低7.71%；在Extended Yale B数据集上的准确率，SDLRRS算法比DLRRS算法低2.19%，SLRR算法比LRR算法低1.31%，SSSC算法比SSC算法低11.41%，可以验证可拓展算法的有效性.尤其是本文的可拓展聚类算法SDLRRS，比进行了重新聚类的LRR算法在AR数据集上的准确率还高出1.52%，在Extended Yale B数据集上高出15.54%；比SSC算法在AR数据集上高出3.97%，在Extended Yale B数据集上高出17.73%.另外，SDLRRS算法的运算时间相较LRR算法和SSC算法至少节省一半以上，所以SDLRRS算法不仅可以用来处理新增加的样本，必要的时候还可以用来快速聚类整个数据集，足见本文算法是非常有效可行的.本文首先设计了一种基于分布式低秩表示的稀疏子空间聚类算法，此算法运用并行计算思想，并且通过保留系数矩阵每列的前k个绝对值最大系数、其他系数置为0，达到简化突出样本间相似程度的目的，此算法具有充分利用计算资源节省运算时间和提高聚类准确率的优点.但它不具备增量学习功能，为此，又提出一种基于分布式低秩表示的增量式稀疏子空间聚类算法，在AR数据集和Extended Yale B人脸库上的聚类效果优异.但是，本文的研究工作还有待进一步深入和扩展，如新增加的样本不属于前面聚类的类，这时就不可以简单地根据前面的聚类结果对新增样本进行分类.Xu Kai, born in 1989. Master. His main research interests include pattern recogni-tion and data mining.Wu Xiaojun, born in 1967. Professor and PhD supervisor. Senior member of China Computer Federation. His main research interests include pattern recognition, computer vision, fuzzy systems, neural networks, and intelligent systems.Yin Hefeng, born in 1989. PhD candidate. Student member of China Computer Federation. His main research interests include feature extraction, sparse repres-entation and low rank representation.【相关文献】[1]Ying Wenhao, Xu Min, Wang Shitong, et al. Fast adaptive clustering by synchronization on large scale datasets[J]. Journal of Computer Research and Development, 2014, 51(4): 707-720 (in Chinese)(应文豪, 许敏, 王士同, 等. 在大规模数据集上进行快速自适应同步聚类[J]. 计算机研究与发展, 2014, 51(4): 707-720)[2]Hong W, Wright J, Huang K, et al. Multiscale hybrid linear models for lossy image representation[J]. IEEE Trans on Image Processing, 2006, 15(12): 3655-3671[3]Elhamifar E, Vidal R. Sparse subspace clustering: Algorithm, theory, and applications[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2765-2781[4]Zhuang L, Gao H, Lin Z, et al. Non-negative low rank and sparse graph for semi-supervised learning[C] Proc of IEEE CVPR’12. Pisca taway, NJ: IEEE, 2012: 2328-2335 [5]Vidal R, Ma Y, Sastry S. Generalized principal component analysis (GPCA)[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2005, 27(12): 1945-1959[6]Zhang T, Szlam A, Lerman G. Median k-flats for hybrid linear modeling with many outliers[C] Proc of the 12th Int Conf on Computer Vision Workshops. Piscataway, NJ: IEEE, 2009: 234-241[7]Lu L, Vidal R. Combined central and subspace clustering for computer vision applications[C] Proc of the 23rd Int Conf on Machine learning. New York: ACM, 2006: 593-600[8]Rao S, Tron R, Vidal R, et al. Motion segmentation in the presence of outlying, incomplete, or corrupted trajectories[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2010, 32(10): 1832-1845[9]Favaro P, Vidal R, Ravichandran A. A closed form solution to robust subspace estimation and clustering[C] Proc of IEEE CVPR’11. Piscataway, NJ: IEEE, 2011: 1801-1807 [10]Elhamifar E, Vidal R. Clustering disjoint subspaces via sparse representation[C] Proc of IEEE ICASSP’10. Piscataway, NJ: IEEE, 2010: 1926-1929[11]Vidal R. A tutorial on subspace clustering[J]. IEEE Signal Processing Magazine, 2010, 28(2): 52-68[12]Li Qingyong, Liang Zhengping, Huang Yaping, et al. Sparseness representation model for defect detection and its application[J]. Journal of Computer Research and Development, 2014, 51(9): 1929-1935 (in Chinese)(李清勇, 梁正平, 黄雅平, 等. 缺陷检测的稀疏表示模型及应用[J]. 计算机研究与发展, 2014, 51(9): 1929-1935)[13]Von Luxburg U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4): 395-416[14]Liu G, Lin Z, Yan S, et al. Robust recovery of subspace structures by low-rank representation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2013, 35(1): 171-184[15]Talwalkar A, Mackey L, Mu Y, et al. Distributed low-rank subspace segmentation[C]Proc of IEEE ICCV’13. Piscataway, NJ: IEEE, 2013: 3543-3550[16]Peng X, Zhang L, Yi Z. Scalable sparse subspace clustering[C] Proc of IEEE CVPR’13. Piscataway, NJ: IEEE, 2013: 430-437[17]Wright J, Yang A Y, Ganesh A, et al. Robust face recognition via sparse representation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227。

基于ADMM的拉普拉斯约束表示型聚类算法王万良;朱文博;郑建炜【摘要】作为数据挖掘领域的关键技术,子空间分割对在联合子域内所分布的输入数据进行潜在的流型聚类.谱聚类因具备出色的性能被作为子空间分割算法中的首选,其性能主要依赖于由输入样本构造的关联矩阵.在平滑聚类算法的基础上结合拉普拉斯矩阵学习机制,提出一种用联合样本系数以及关联矩阵学习的新型聚类模型.同时,为快速获取清晰的对角块结构,对目标函数增加低秩正则项约束,并通过交替方向最小乘子法进行模型优化求解.所提方法称为基于ADMM(Alternating direction minimizing multiplier)的拉普拉斯约束表示型聚类算法(Laplacian regularizer cluste-ring,LRC).通过实证结果表明:所提方法具有更高的聚类效果和更快的运行效率,综合性能优于相关的聚类方法.%As a key technology in the field of data mining,subspace segmentation is used to segment a set of data drawn from the union of subspaces into its underlying subspace.Spectral clustering is preferred as a subspace segmentation method whose performance is heavily dependent on the affinity matrix that is usually constructed from the original data or its corresponding representation.Based on smooth representation clustering approach and the Laplacian matrix learning mechanism,a new clustering model based on representations of data and affinity matrices is proposed.Furthermore,in order to fast acquire a clear diagonal block structure,the objective function is constrained by the low-rank regularization,and the model is optimized by alternating the direction minimizing multiplier,the proposed method is named as Laplacian regularizer clustering via ADMMimplementation,LRC.The empirical results show that the proposed method has higher clustering effect and faster operation efficiency,overall performance is better than the relevant clustering method.【期刊名称】《浙江工业大学学报》【年(卷),期】2018(046)004【总页数】7页(P363-368,381)【关键词】子流形分簇;拉普拉斯矩阵;交替方向最小乘子法;秩约束【作者】王万良;朱文博;郑建炜【作者单位】浙江工业大学计算机科学与技术学院,浙江杭州 310023;浙江工业大学计算机科学与技术学院,浙江杭州 310023;浙江工业大学计算机科学与技术学院,浙江杭州 310023【正文语种】中文【中图分类】TP391.4伴随时代的进步，数据量达到百万条的大型数据库随处可见，伴有高维度性质的聚类需求使得传统聚类算法应对起来难以得心应手.聚类，又称为分簇，是指将具有复杂分布的输入数据根据不同的目标准则划分为多个类簇的物理过程.聚类结果为多簇数据对象子集，其中同一类的数据彼此具有特征相似性，而异类的数据则彼此无关[1].在数据挖掘领域，聚类算法应用十分广泛并扮演着越来越重要的角色.迄今为止，聚类算法研究已成为机器学习、人工智能领域的热点，新模型层出不穷，包括经典的k-means算法、较新的复角度多学习分簇算法等等[2]，常见的可分为代数型、概率型及谱分簇型三大类，其中谱分族型聚类模型具有更为宽泛的应用能力且理论证明完备，因此拥有更广阔的应用前景[3-4].谱聚类算法性能受制于最终所得的系数矩阵和构造的关联矩阵.为提升聚类性能，常见的系数矩阵约束条件包含低秩性、压缩性以及分块对角特性等等[5].Elhamifar等[6]对系数表示矩阵约束压缩性条件构建稀疏流型聚类模型(Sparse subspace clustering,SSC)，使得数据点由处于相同子空间中的其他点来线性表示，同时寻求最稀疏的线性组合，但是因需要对每个输入数据的回归表示进行独立求解，使得该方法欠缺对样本矩阵的整体性分布结构考虑.针对该问题，Liu等[7]将压缩性约束条件替换为低秩结构提出一种新的表示型聚类算法(Low-rank representation,LRR).为获得更好的全局整体性，通过输入数据矩阵的低秩约束和行稀疏范数抑噪挖掘分组结构.随着研究工作深入，为提高抗噪鲁棒性，在SSC和LRR基准模型上添加稀疏性、结构性等约束，如抗扰型SSC[8]和非负条件迭加的Laplacian型LRR(简称LRR)[9]等，都以完美的子流型结构挖掘和块对角关联矩阵构建为目标.在对角结构构建过程中，限制型对角条件由Lu等[10]分析提出了在数据子集互相之间独立分布的前提下，正则项约束对强制分块对角条件的满足与保证关联矩阵块对角结构的联系.Feng等[11]在SSC 和LRR算法中对由系数矩阵所得的Laplacian矩阵添加具有确定簇组数量的秩约束，使得关联矩阵具有更清晰的块对角性.但是，其算法模型求解过程中的约束正则项需要经历多个耗时步骤，因此其实施效率并不理想.在关联矩阵学习方面，组间低秩约束算法(Low rank structure,LRS) [12]直接对样本进行分组约束逼近，较传统方法中先构造关联矩阵后谱聚类的操作形式更优，然而抗噪性差及组间奇异值分解计算量高仍是亟待解决的问题.史骏等[13]结合图论和低秩表示聚类算法进行鉴别投影分析，对样本邻域结构起到较好的学习效果，然而其半监督的特性针对聚类分析任务并不能发挥所长.近些年的研究受到回归表示高鉴别力的启发，许多聚类模型以自表征系数为基础构造关联矩阵.李波等[14]通过诱导Laplacian矩阵中系数矩阵的局部联接特性，使得字典样本的类间关联性得到减弱.Lu等[10]提出关联自学习子域分簇条件，并将其添加至最小平方回归模型中，分簇稳定性较优，然而对于组效应的约束并不能拓展应用于其它聚类模型.为解决该问题，光滑簇模型(Smooth clustering,SMC)以限制组效应条件为出发点，同时结合光滑重构表示正则项，进而在效果和效率上都得到了优化.上述聚类算法都通过Laplacian正则约束项引导关联矩阵构建，而其Laplacian矩阵都由输入样本直接计算得到，导致算法性能因初始值和具体数据状态的差异导致结果上较为明显的优劣.Guo[15]通过Laplacian表示型和系数矩阵联合优化的形式获得关联矩阵，提出了稳健型子流型分簇模型(Robust subspace segmentation,RSS)，获得更强的抗噪能力，然而模型受限于三个人工待定参数，导致其应用扩展性不佳，具该模型受初表示系数的次优性影响较强.笔者在光滑簇算法的基础上结合Laplacian矩阵学习机制，提出一种用联合样本系数以及关联矩阵学习的新型分簇聚类模型.提出基于ADMM(Alternating direction minimizing multiplier)的Laplacian约束表示型聚类算法(Laplacian regularizer clustering,LRC).LRC联合光滑F范数以及Laplacian矩阵正则约束，通过样本空间结构建立具有局部结构引导性的Laplacian矩阵并添加组数内最小特征值相加和为零的约束条件，通过迭代形式依次更新模型系数矩阵和Laplacian矩阵，其优化结果包含关联矩阵和表示系数矩阵两种相似度计算手段.算法针对前文描述算法中存在的问题进行了改进，具有更好的灵活性和更广的数据应用分布状态.1 相关工作研究和实验结果已表明：自表示系数能够较好的体现高维数据集样本间的关联特性，而关联矩阵的构建则是谱分簇算法的关键步骤，其具体分布结构决定了模型应用效果.经过研究，Lu等[10]发现组效应作为基准条件保证表示型算法高聚类性能.当给定数据样本为X=[x1,x2,…,xn]∈Rm×n，其中xi∈Rm代表第i例输入数据，n指代完整训练样本量，相对应的系数矩阵Z=[z1,z2,…,zn]∈Rn×n，其中zi∈Rn代表xi的系数矢量.组效应的意义是对任意给定的数据xi,xj，其中i,j∈{1,2,…,n}，如存在‖xi-xj‖2距离较近，则对应的表示系数向量‖zi-zj‖2也是近邻状态，其中‖·‖2表示l2约束范数.组效应从样本欧氏距离的角度挖掘输入样本的空间邻域特性，解释了低秩表示聚类模型等其他算法性能保证的依据.但仅从客观上发现了组间低秩约束算法组效应在表示型聚类算法中的作用，并没有对其约束形式及进一步应用拓展进行深入分析.受到组效应的启发，Hu等[16]对稀疏子空间分簇算法、低秩表示聚类算法、最小平方回归模型和关联自适应子空间分割模型等模型进行深入研究，得出统一框架为s.t. Z∈C(1)式中：α>0为平衡参数；‖·‖l为重构误差约束范数；Ω(X,Z)为Z的正则化约束；C 为Z的数值范围约束.以式(1)的重构基础框架，限制组效应条件包含两个子约束: 1) 正则约束项Ω(X,Z)是Z的连续函数，并在Z∈C条件下使得式(1)具有唯一解Z*；2) 对于任意的置换矩阵P ,Z∈C当且仅当ZP∈C且Ω(X,Z)=Ω(XP,ZP)时成立.在此条件下，为提升空间近邻样本数据的关联程度，Hu等[16]将组间低秩约束算法模型中的正则约束项Ω(Z)=tr(ZZT)调整为(2)即添加了空间距离约束因子sij，作为衡量样本间的相似性标准，L=D-S为Laplacian矩阵，其中S由元素sij组成，对角矩阵D称为度矩阵，且对角元素当S中的元素都为1时，式(2)退化为组间低秩约束算法模型的系数正则项.光滑簇算法利用K近邻图计算样本相似度权值sij，结合表示特性及空间特性构建目标函数模式并对比现有聚类模型的不同‖·‖l的性能分析后，引入光滑的Frobenius范数作为模型重构表示误差约束项，其目标函数为(3)式中Lε=L+τI作用为避免数值计算的不稳定性，I为单位矩阵，τ≥0是一个趋近于0的值.在求解式(3)后得到平滑聚类算法模型的自表示系数矩阵Z*，用于构造关联矩阵，之后通过谱分解操作及k-means得到最终的聚类结果.鉴于原始Z*的非对称性，包括稀疏子空间分簇算法、低秩表示聚类算法和最小平方回归模型在内的常见算法都通过式(4)进行最终邻接矩阵W的构建，即W=(|Z*|+|Z*T|)/2(4)为凸显组效应条件，光滑簇算法提出一种新的相似度元素计算方法，即(5)式中κ>0用于控制关联度的波动，能够对初始特征震荡带来的影响进行有效的规避，从而使得平滑聚类算法模型具有更优异的聚类性能表现.从式(2)可得：平滑簇模型在组效应约束上添加数据相似度元素sij，联合空间距离特征和表示系数重构特性计算更为合理的关联矩阵W.但是，在式(3)中的Laplacian矩阵L是由KNN算法直接计算而成，欠缺合理的学习机制，尽管L可通过其它子空间分割算法优化而得的关联矩阵替代，但独立的更新求解策略无法保证整体目标函数的全局优化结果.2 LRC算法描述本节采用系数矩阵和Laplacian矩阵联合优化策略提出一种新的光滑簇模型，称为LRC，主要包含目标函数描述和模型更新求解两个内容.从概率性邻域和空间距离结构特性出发，为实现Laplacian矩阵的迭代更新，以近邻数据对应大相似度值、远邻数据对应小相似度值的思路构建关联矩阵，即(6)式中：第二项用于规避sij出现平凡解；γ为平衡参数；si作为zi系数向量所对应的关联向量；约束项是概率特性约束，1代表元素全是1的n×1维向量，以起到相似度的非负性和数值稳定性的作用.值得说明的是，式(6)采用表示系数向量zi,i=1,2,…,n进行邻域图构建，较输入样本xi具有相较突出的噪声点抑制和全局结构挖掘能力等特性.将式(6)进行代数变换后得(7)由式(7)中第1项与式(3)第2项等价，为减少模型复杂度，结合式(3，7)，LRC的初始模型描述为(8)与平滑聚类算法对比可知：式(8)目标函数通过添加邻接元素S，使其整体模型结构依旧保留了平滑聚类算法的光滑和重构等特性本质，保证在其优化结果Z*仍具备块对角特性.但是，在噪声环境下，算法块对角结构将难以保证，其中一种较为直观的解决思路是对Laplacian矩阵添加显式的块对角结构约束，促使引导Z的块对角特性.结合谱簇理论中的连通性原则，Feng等[11]采用矩阵秩最小化逼近Laplacian矩阵的c簇结构，即T={Z|rank(L)=n-c,S=(|Z|+|ZT|)/2}(9)式中c为目标聚类数，同时将条件T放入经典稀疏子空间分簇算法和低秩表示聚类算法模型，进而获得聚类效果的提升.但是，约束式T存在求解复杂的问题，一般通过向量投影[17]、亚微分计算等策略进行近似，其计算效率较差且不具备算法最优性.不失一般性，假设将Laplacian矩阵的特征值按从小到大的顺序排列，即0≤σ1(L)≤σ2(L)≤…≤σn(L)，由L的半正定性决定其非负性.基于rank(L)=n-c及谱分解原理可得再通过Ky Fan理论得知：可将秩约束rank(L)=n-c替换成谱分解迹约束，即并将其添加至式(8)得到模型的最终目标函数为β tr(FTLF)(10)由式(8)可知：目标函数式采用统一的优化框架综合了所有前述的先验条件和约束限制，用于表示系数学习以及联合矩阵构建.虽然式(8)中S和Z不具备联合凸性，但是当剩余变量固定时则存留变量都是凸函数.交替方向最小乘子法(Alternating direction minimizing multiplier,ADMM)[18-19]已被证明是一个有效且高效的解决式(8)的方案.为了在我们的问题上应用ADMM，需要使目标函数可分离.因此，笔者引入一个辅助变量Q来代替目标函数式(8)的表示项中的Z.因此，Q=Z作为附加约束.同时，每个Si的概率属性被强制为硬约束.式(8)的增广拉格朗日函数为α‖E‖+tr(QLQT)+γ‖S‖+β tr(FTLF)+Φ(μ1,X-XZ-E)+Φ(μ2,Q-Z)(11)式中：Φ(μ,C)≡ρ‖C‖/2+<μ,C>，ρ是正则项约束值；μ1，μ2为拉格朗日乘子系数.除拉格朗日乘数外，还有5 个变量：E，Z，Q，S，F.通过固定其他变量来迭代地求解某一个变量,各子问题的解决方案如下.2.1 E子问题显然E相关项均是二维的，为计算E(t+1)，对E进行求导得到(12)2.2 Z子问题与E问题类似，对Z求导，得到(13)式中I为单位矩阵.2.3 Q子问题与计算E和Z类似，通过封闭式求解可得(14)2.4 S子问题S(t+1)可以通过优化求解，即(15)为获得闭式求解效果，将式(15)变形为向量描述形式为(16)式中fi∈c×1为F矩阵的第i行向量.式(16)则是二次规划问题，可由经典迭代型凸规化技术进行求解优化.为得到其唯一解，进一步令则式(16)可转变为(17)式中vi作为vij构成的辅助变量.由式(17)可知：不同的相似度向量si之间具有独立性，便可通过优化求解，其拉格朗日扩展式为(18)式中：ζ,μi为拉格朗日乘子参数，μi≥0.根据KKT(Karush-Kuhn-Tucker)条件可得(19)式中：(·)+表示·非负，还包含2 个未知量ζ，γi.考虑到全连接特性的S矩阵只有1 个零特征值，缺乏块对角分布状态.因此，将列向量si 稀疏化，仅对样本zi中的k 个近邻进行连接，得到的稀疏矩阵S可以有效减轻后续计算量.假设si的前k个元素为相似样本，可得sik>0且si,k+1=0，则(20)再依据约束条件得到(21)将式(20，21)代入式(19)中可知si 最终表达式为(22)式(22)具有闭式解并且仅含明确待调参数k，实现便捷性高.2.5 F子问题在确定S后，F由Laplacian矩阵通过特征分解并由前c个特征向量组成.最后，乘子μ1，μ2迭代计算式为(23)算法 1 LRC算法输入：数据矩阵X∈Rm×n，聚类量c，近邻数k,α≥0,β≥0，γ≥0.Step 1 初始化E(0)=μ1(0)=0∈Rm×n,F(0)=0∈Rc×n,Z(0)=Q(0)=S(0)=μ2(0)=0∈Rn×n,ρ(0)= 1,t=0.Step 2 基于St构造L(t).Step 3 通过式(12)求解E(t+1).Step 4 通过式(13)求解Z(t+1).Step 5 通过式(14)求解Q(t+1).Step 6 迭代i从1到n通过式(22)求解Step 7 通过式(23)更新算子.Step 8 如达到收敛，则输出S与Z；反之转至Step 2.算法 1是LRC的整体构建流程，其中的迭代过程在‖X-XZt+1-Et+1‖F≤δ‖X‖F时或达到最大迭代次数时终止，其中δ=10-3.在获得关联矩阵S和表示矩阵Z之后，通过经典谱聚类技术，对其进行归一化分割，将输入数据分割成c个聚类.值得注意的是，至今为止仍未有ADMM算法在多变量情形下的收敛性理论证明，但相关算法都能收敛至一个稳定点[20].通过公开数据集的经验结果将表明：所提算法具有强而稳定的收敛性.3 实验分析本节以8 种公开数据集为分簇目标，以聚类精度(Acc)和规范化互信息(NMI)两个分簇性能指标对LRC模型的应用性能进行验证：包括2 个手写字体库USPS，MNIST；3 个人脸图像库JAFFE，ORL，AR；1 个生物采集库LUNG；1 个语音波形库ISOLET；1 个目标对象库COIL.表1是对各数据集预处理后的描述.对比聚类算法选用SSC[6]，LRR[7]，NLRR[9]，LRS[12]，RSS[15]，SMC[16]，基准模型k-means等算法，在实验中参数优选范围如表2所示，其中各待定参数的描述符号与各模型原作保持一致.近邻k为所有模型的共享参数，实验中统一在{3，5，7，9，11，13，15}范围内搜索确定其最优值.表1 各实验数据集特征描述Table 1 Feature description of each experimental data set数据集名称数据量/个样本数/维聚类数/个USPS3 0002563MNIST2 00080010JAFFE21367610ORL4001 22540AR700980100LUNG20333005ISOLET1 55961226COIL1 4401 02420表2 对比算法中人工待定参数的优选范围Table 2 The optimal range of artificial undetermined parameters in comparison algorithm算法参数范围SSCλ∈{10-3,10-2,10-1,10,102}LRRλ∈{10-3,10-2,10-1,10,102}NLRRλ,γ,β∈{10-3,10-2,10-1,10,102}LRSp∈{0.1,0.2,0.4,0.6,0.8,1.0}RSSλ1,λ2,λ3∈{10-3,10-2,10-1,10,102}SMCα,γ∈{10-3,10-2,10-1,10,102}LRCα∈{10-3,10-2,10-1,10,102}表3，4分别给出了所有对比算法在各公开样本集中的Acc和NMI两个关键性能指标，各数值结果都由15 次随机实验并取平均值得到，黑体代表性能排名最高，下划线代表次优的实验值.结合表3，4可知：LRC在综合聚类性能方面的表现明显优于其他，几乎囊括了所有数据集中最高的聚类性能指标，仅在USPS数据集的NMI结果弱于RSS.在COIL数据集中，LRC的聚类精度达到89.77%，较次优值76.32%领先17.62%；NLRR和SMC两者的聚类性能比较相近，分别得到6 个和7 个次优值；RSS即便在NMI指标中获得了一个最优值，但其次优值却只有3 个；而LRS的真实数据集应用表现不佳，部分实验数据显示其性能甚至不如模型k-means，仅在合成的纯净数据中适用于应用.在算法稳定性方面，由于各数据集在空间分布结构、分组数、训练量和维数等方面都存在不同，因此算法间性能也出现一定的起伏.综上实验结果：LRC算法虽在数据集见的横向比较中存在起伏，但于其他算法的纵向对中表现出较强的稳定性，说明LRC具有更强的适应性和泛化性. 表3 各聚类模型在公开数据集中的精度实验结果Table 3 Experimental results on the accuracy of clustering models in public data sets %算法USPSJAFFEISOLETMNISTLUNGCOILORLARk-means91.5571.6649.8753.2075.3756.0951.8123.90SSC91.3295.3652.9051.54 84.6854.5461.8052.56LRR92.2393.2054.1250.7682.3361.3561.9449.73NLRR 96.5497.2957.3357.7388.2967.1868.7455.38LRS79.4773.3239.6445.7677.785 2.8557.7247.65RSS97.9032.7745.6751.7581.5776.3239.4526.59SMC96.7497. 2954.3761.7086.5471.6571.8459.88LRC98.0397.6558.5364.3790.1289.7772. 8161.64表4 各算法模型在公开数据集的规范化互信息指标结果Table 4 The normalized mutual information index results of each algorithm model in public data sets %算法USPSJAFFEISOLETMNISTLUNGCOILORLARk-means82.2587.5070.2050.7666.4077.6074.7167.35SSC83.6895.5965.6651.88 72.2572.2675.3272.60LRR85.6494.4567.7651.2671.8969.7776.5672.34NLRR 86.8897.8670.3651.9073.8773.0680.4477.38LRS69.7574.3548.1234.6059.335 4.7775.4474.78RSS93.3429.7661.6156.9054.6191.8046.6555.24SMC88.6496. 9369.0460.6372.8382.1882.3878.65LRC93.1998.5572.0663.9774.6692.0786. 5580.044 结论基于ADMM求解算法，提出了一种新型数据聚类算法LRC，通过样本间概率性的邻接距离特性作为相似度矩阵的构造基础，建立关联矩阵和系数矩阵的联合优化目标函数；同时，通过对目标函数增加低秩正则约束条件，以获取清晰的对角块结构.其构造的目标模型具备了限制组效应条件、光滑表示特征和分块对角状态等.在模型求解方面，选取变量交替更新的方法，保证对于各个子目标的优化函数都具有最优解，其中为了使算法更加直观，减少在算法实施时人工参数设定的步骤，对相似矩阵S的计算进行了分解操作.通过真实公开数据集对现有各算法及笔者聚类算法进行了实验，由实验数据可知：LRC算法在提升稳定性的同时，在精度、归一化互信息等指标下相较于其他聚类算法均有优越的表现，并在多个数据集中表现出了更强的鲁棒性且具备很好的泛化性及可拓展性.参考文献：[1] 孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.[2] 陆亿红,翁纯佳.基于三角模糊数的不确定性数据聚类算法[J].浙江工业大学学报,2016,44(4):405-409.[3] 龙胜春,傅佳琪,尧丽君.改进型k-means算法在肠癌病理图像分割中的应用[J].浙江工业大学学报,2014,42(5):581-585.[4] 高雪,谢仪,侯红卫.基于多指标面板数据的改进的聚类方法及应用[J].浙江工业大学学报,2014,42(4):468-472.[5] VON L U. A tutorial on spectral clustering[J]. Statistics and computing,2007,17(4):395-416.[6] 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.[7] LIU G C,LIN Z C,YAN S C,et al.Robust recovery of subspace structure by low-rank representation [J].IEEE transactions on pattern analysis and machine intelligence,2013,35(1): 171-184.[8] WANG Y X,XU H.Noisy sparse subspace clustering[J].Journal of machinelearning research,2016,17(12): 1-41.[9] YIN M,GAO J B,LIN Z placian regularized low-rank representation and its applications[J].IEEE transaction pattern analysis and machine intelligence,2016,38(3): 504-517.[10] LU C Y,MIN H,ZHAO Z Q,et al.Robust and efficient subspace segmentation via least squares regression[C]//Proceedings of the european conference on computer vision.Berlin: Spreinger,2012: 347-360.[11] FENG J S,LIN ZC,XU H,et al.Robust subspace segmentation with block-diagonal prior[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Los alamitos: IEEE Computer Society Press,2014: 3818-3825.[12] NIE F P,HUANG H.Subspace clustering via new low-rank model with discrete group structure con-straint[C]//Proceedings of the 25th International Joint Conference on Artificial Intelligence.San Francisco: Morgan Kaufmann,2016: 1-7.[13] 史骏,姜志国,赵丹培,等.利用自适应近邻选择和低秩表示的半监督鉴别分析[J].计算机辅助设计与图形学学报,2015,27(2):238-248.[14] 李波,卢春园,冷成财,等.基于局部图拉普拉斯约束的鲁棒低秩表示聚类方法[J].自动化学报,2015,41(11):1971-1980.[15] GUO X J.Robust subspace segmentation by simultaneouslylearning data representations and their affinity matrix[C]//Proceedings of the 24th International Conference on Artificial Intelligence.San Francisco: Morgan Kaufmann,2015: 3547-3553.[16] HU H,LIN Z C,FENG J J,et al.Smooth representationclustering[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Los Alamitos: IEEE Computer Society Press,2014：3818-3825.[17] 郑建炜,黄琼芳,杨平,等.特征加权组稀疏鉴别投影分析算法[J].自动化学报,2016,42(5):746-759.[18] 高乾坤,王玉军,王惊晓.基于交替方向乘子法的非光滑损失坐标优化算法[J].计算机应用,2013,33(7):1912-1916.[19] 张峥嵘,孙玉宝,黄丽丽,等.全变差图像恢复的交替方向乘子法[J].计算机工程与应用,2010,46(14):8-11.[20] BOYD S,PARIKH N,CHU E,et al.Distributed optimization and statistical learning via the alternating direction method of multipliers[J].Foundations & trends in machine learning,2011,3(1):1-122.。