改进的基于谱聚类的子空间聚类模型

高 冉，陈花竹

（中原工学院理学院，郑州 451191）

（∗通信作者联系邮箱nygr@163.com）

0 引言

子空间聚类得到了广泛的关注和大量的研究，它的任务是将数据分割到其本质上所属的子空间。子空间聚类是对传统聚类方法的一种扩展，近20年来，人们提出了大量的子空间聚类方法，这些方法大致可以分为四类：迭代方法［1-2］、代数方法［3-4］、统计方法［5-6］和基于谱聚类的方法［7］。迭代方法将数据点分配到不同的子空间，并应用数据点拟合每个子空间。该方法通常需要预先设置每个子空间的维数，最终的结果取决于初始化。代数方法的一个典型代表是基于分解的方法，它通过阈值相似矩阵（由数据矩阵的分解构造）的元素来搜索初始分割。这些方法在子空间独立时具有严格的理论保证；然而，它们对数据噪声或异常值没有鲁棒性。统计方法通常假设每个子空间内的数据遵循某种分布，如高斯分布。在此基础上，采用期望最大化（Expectation Maximization，EM）算法交替进行数据聚类和子空间估计。这些方法的主要缺点是依赖于估计精确的子空间模型。基于谱聚类的方法由于其易于实现、对初始化和数据损坏不敏感等优点而越来越流行。这类方法通常将问题划分为两个独立的阶段：首先，通过自表示学习从数据中学习一个相似度矩阵，如稀疏子空间聚类（Sparse Subspace Clustering，SSC）［8-9］、低秩表示（Low-Rank Representation，LRR）［10-11］和一些基于SSC 或LRR 的扩展模型）如鲁棒子空间聚类的最小二乘回归（Least Square Regression，LSR）［12］、相关自适应子空间聚类（Correlation Adaptive Subspace Segmentation，CASS）［13］、隐低秩表示（Latent Low-Rank Representation，LatLLR）［14］、隐光滑表示子空间聚类（Latent SMooth Representation clustering，LSMR）［15］、块对角表示（Block Diagonal Representation，BDR）［16］等，它们主要研究如何从数据中学习一个好的相似度矩阵来提高聚类性能。其次，应用Normalized cuts（N-cut）［17］或稀疏谱聚类（Sparse Spectral Clustering，SSpeC）［18］等谱聚类方法，利用相似度矩阵推断数据的标签，得到数据最终的聚类结果。这些两阶段法中，SSpeC 模型是对传统谱聚类的改进，通过分析隐相似度矩阵的稀疏性引入稀疏正则项，以此来增强聚类判别能力；但该正则项对于隐相似度矩阵的稀疏性是模糊的，因为它没有显式地捕获数据的自表示矩阵和聚类指标矩阵之间的自然关系，没有考虑隐相似度矩阵中哪些元素为0。SSpeC 模型虽然优于传统的谱聚类方法，但也没有充分利用相似度矩阵与数据标签之间的关系，聚类性能并未达到最优。

结构稀疏子空间聚类（Structured Sparse Subspace Clustering，SSSC）［19-20］将两阶段合并，同时得到相似度矩阵和聚类结果。将相似度矩阵学习和标签学习集成到一个统一的优化框架中，并利用其中一个来引导另一个，使两者都具有优点：一方面，它利用标签将来自不同类的数据点对应的相似度强制为零；另一方面，它使用相似度矩阵来引导标签推断，使得同一类中的数据点具有相同的标签。SSSC的聚类性能优于上述两阶段法，但SSSC只强制来自相同子空间的数据具有相同的聚类标签，没有考虑来自不同子空间的数据具有不同的聚类标签。结构块对角表示（Structured Block Diagonal Representation，SBDR）［21］和判别相关子空间聚类（Discriminative and Coherent Subspace Clustering，DCSC）［22］都是两个阶段的统一优化模型，它们是对SSSC 方法的改进，但是它们主要集中在对自表示学习时的改进，使用相似度矩阵来引导标签推断时仍然应用的是传统的谱聚类算法（N-cut）。

本文在SSpeC 模型的稀疏性基础上，给出一个新的数据自适应稀疏正则项，并采用SSSC 的统一优化框架，以保持相似度矩阵学习和聚类指标推断的相互引导。一方面，利用数据对的相关性来指导隐相似度矩阵的稀疏性，克服了SSpeC中稀疏性惩罚的盲目性；另一方面，它倾向于强制来自不同子空间的数据具有不同的聚类指标，从而补充了SSSC 只强制来自相同子空间的数据具有相同的聚类指标的缺陷。

1 相关工作

为方便起见，在回顾相关理论之前，由表1 给出了本文中使用的符号的定义。

表1 符号说明Tab.1 Symbol description

令X=(x1，x2，…，xN)∈Rn×N是N个数据的集合，每一列xi都是一个n维特征向量。假设数据分别来自维数未知的的K个相互独立的子空间的并集。子空间聚类的目的是通过聚类来揭示每个数据的子空间属性，一类对应一个子空间。基于谱聚类方法取得了很好的效果，它假设子空间中的任何数据都可以表示为其他数据的线性组合的前提下，利用自表示矩阵Z构造相似度矩阵。这些方法通过求解以下优化问题得到自表示矩阵Z：

其中：Ω(Z)和C 是对Z的约束；E表示误差值、损坏值或异常值；Φ(E)是E的约束函数，一般来说用于高斯噪声，‖E‖1用于异常值；λ是一个权衡参数。不同聚类方法之间的主要区别在于Ω(Z)的选择，设计合适的Ω(Z)使得模型得到的矩阵Z满足类间稀疏、类内一致的性质。例如，SSC 使用‖Z‖1来增强Z的稀疏性，LRR 使用核范数‖Z‖∗来寻求对所有数据的低秩表示。得到问题（1）的最优解Z*后，就构造出相似度矩阵。然后，通过谱聚类算法得到聚类结果。具体地，通过优化以下问题得到最终聚类结果：

其中：L=D-A是Laplace 矩阵；D是一个对角元素为Djj=的对角矩阵。约束Γ是聚类指标矩阵的集合，定义为：

其中F为聚类指标矩阵。具体地，定义为：

第i行的非零元所在的列表示数据xi的所在的类，F的第j列表示哪些数据属于第j类。F1=1 表示每个数据点只在一个子空间中。约束rank(F)=K是为了确保F只有K行不同，因为子空间的类的个数是K。问题（2）通常由F∈Γ松弛为FTF=I，其中I是单位矩阵。所以谱聚类问题松弛为以下优化问题：

问题（4）的最优解F的列是L的K个最小特征值的对应的特征向量。将K-均值（K-means）聚类算法作用于F的每一行，得到最终聚类结果。

FFT在某种程度上是稀疏的，SSpeC 模型通过‖FFT‖1来考虑稀疏性，所以SSpeC模型表示为：

SSpeC 表明FFT矩阵隐含了相似度矩阵A的可判别性或|FFT|可视为一个新的相似度矩阵，称为隐相似度矩阵。但它是盲目的，因为它没有考虑两个数据点是否来自不同的子空间。只有数据点xi与xj来自不同的子空间，才有(FFT)ij=0。此外，SSpeC 是一个两阶段的方法，没有充分利用相似度矩阵和数据标签之间的关系。

SSSC 通过以下模型将子空间聚类问题表述为一个统一的框架：

α＞0和λ＞0权衡参数，SSSC中，自表示矩阵Z和聚类指标矩阵F彼此交互，使得它们有一些有利于聚类的特性。

SSSC 模型虽然将相似度矩阵和聚类指标矩阵结合成一个统一的框架，是统一优化模型，优于两阶段聚类方法，但是它没有考虑来自不同子空间的数据具有不同的聚类指标，本文旨在针对聚类指标矩阵的学习对SSSC方法进行改进。

2 本文提出的模型

2.1 本文模型

根据前面对SSpeC模型的分析，当xi和xj不在同一个子空间时，隐相似度矩阵的元素|(FFT)ij为零。直观地说，如果数据点xi和xj之间的距离很远，那么很可能xi和xj|来自不同的子空间。在此基础上，利用下面的加权稀疏性来惩罚隐相似度矩阵的稀疏性：

将式（7）代入SSSC 模型，且将F∈Γ松弛为FTF=I，可得：

2.2 模型求解

通过交替求解以下两个子问题，设计了模型（8）的有效算法：

1）固定X和Z，求解F；

2）固定F，通过求解表示问题找到Z和E。

2.2.1 求聚类指标矩阵F

当Z和E固定时，式（8）转化为下式：

又因为

所以式（9）可写为下式：

为了式（10）的目标函数能变量分离，引入辅助变量J，然后将其改写为如下等价公式：

该问题可以用交替方向乘子法（Alternating Direction Method of Multipliers，ADMM））［23-24］来解决。式（11）的增广Lagrange函数为：

其中：Y是Lagrange乘子，μ＞0是惩罚算子。当别的变量固定时，依次更新F、J和Y。

1）F子问题：固定J和Y，通过下式更新F。

其中：F为最大的K（K为类别个数）个特征值对应的特征向量组成的矩阵。

2）J子问题：固定F和Y，通过下式更新J。

式（14）的解为：

其中：S为软阈值算子，||W是对矩阵的每个元素求绝对值。

3）Y子问题：乘子的更新是标准的梯度上升过程：

将问题（11）的整个求解方法总结在算法1中，其中k是迭代次数。

2.2.2 求自表示矩阵Z和误差矩阵E

这是SSSC模型。具体求解参考文献［11］。

3 实验结果

本章分别在Extended Yale B 数据库［25］、Hopkins 155 数据库［26］及USPS 数据库［27］进行实验，以评估本文模型的聚类性能，并与当前较好的聚类模型进行聚类误差率比较，如SSC［8-9］、LRR［10-11］、LSR（包含LSR1和LSR2两个模型）［12］、CASS［13］、LatLRR［14］、LSMR［15］、BDR［16］、SSC+SSpeC（Sparse Subspace Clustering+Spare Spectral Clustering）［18］、N-cut［17］、BDSSC（Block Diagonal Sparse Subspace Clustering）［28］、SSSC［19-20］、LRSC［29-30］、BDLRR（Block Diagonal Low-rank Representation）［28］、TSC（Thresholding-based Subspace Clustering）［31］、NSN（Nearest Subspace Neighbor）［31］、正交匹配追踪（Orthogonal Matching Pursuit，OMP）［32］和K-means。为了在所有实验中进行公平的比较，使用作者源代码中默认或建议参数设置的实验结果，或者直接从其原始论文中引用最佳实验结果，从而获得所有比较模型的最佳性能。

采用上述参考文献中使用的子空间聚类误差率error=Nerror/Ntotal作为聚类性能度量，其中：Nerror表示错误聚类的数据点的个数，Ntotal表示数据点总数。

3.1 Extended Yale B 数据库实验

Extended Yale B 人脸数据库包含38 个人的2 414 张人脸图像，每一个人在不同可控光实验室条件下大约有64 张人脸图像，部分图像如图1所示。

图1 Extended Yale B人脸数据库的样本图像Fig.1 Sample images of Extended Yale B face data base

为了减少算法的计算时间和降低存储空间，参考SSSC［19-20］，先将所有图像的大小压缩为48×42，然后向量化为2 016 维数据点。和SSSC 一样，将38 类数据分为4 组，而不是对整个数据集进行聚类，以评估本文模型在平均意义上的聚类性能。具体而言，四组分别对应1～10 类、11～20 类、21～30类、31～38 类。对于前三组中的每一组，考虑K={2，3，5，8，10}类的所有选择；对于最后一组，考虑K={2，3，5，8}类的所有选择。实验中Φ(E)=‖E‖1。该实验结果与SSC、LRR、LSR、CASS、LatLRR、LSMR、BDR、SSC+SSpeC、N-cut、BDSSC、SSSC、LRSC、BDLRR、TSC、NSN、OMP 和K-means进行比较。

实验表明，当K=2 时，本文模型在参数α=0.1，β=0.001，λ=0.5 时通常会得到“最佳”平均聚类精度，另外在该数据集上所有实验的参数都选择这个设置。

为了展示本文模型的性能，从每个组中任选所有K类进行实验，例如，当K=2 时，共有种情况。然后每类的所有情况的聚类错误率的均值（Ave.）、标准差（“±”符号后的数据）和中值（Med.）如表2 所示，其中“—”表示未报告数据，最好的结果用粗体表示。为了更加直观，还绘制了不同模型的平均聚类错误率与类的个数的关系曲线如图2所示。

表2 Extended Yale B人脸数据库上的聚类错误率 单位：%Tab.2 Clustering error rate on Extended Yale B face data base unit：%

通过表2 和图2 可以看到，在所有模型中，后两种模型的聚类误差率的平均值、中值明显低于前几种模型，说明同时得到相似度矩阵和聚类结果的统一模型优于两步法模型；本文模型的平均聚类误差率最低，且对应的标准差明显较小，表明本文模型较其他方法更加稳定。当K=2，3，5，8，10 时，平均聚类误差率分别为0.18%、0.25%、0.309%、0.302% 和0.26%。由此可见，本文模型的平均聚类误差率对类别个数的增加具有较强的鲁棒性。

图2 Extended Yale B数据库上的聚类错误率与类的个数的关系Fig.2 Relationship between clustering error rate and the number of classes on Extended Yale B data dase

当K=2，3，5，8，10 时，与次优的LSMR 相比，本文模型将聚类误差率从0.53%、0.98%、1.44%、1.80%和1.67%降到0.18%、0.25%、0.309%、0.302%和0.26%；与SSC+SSpeC 相比，本文模型将聚类误差率从1.92%、3.33%、4.49%、3.67%和2.71% 降到0.18%、0.25%、0.309%、0.302% 和0.26%。与SSSC 相比，随着类别的个数的增加，本文模型的平均误差率增大较为缓慢，说明该模型更适合大数据。本模型优于另两种的两个原因：一方面使用数据间的距离来指导隐相似度矩阵的稀疏性，克服了SSpeC 稀疏惩罚的盲目性；另一方面，它建立了相似度矩阵和聚类指标矩阵之间的关系，是统一的优化模型。

此外，为了更好地比较SSC+SSpeC、SSSC 以及本文模型，将这些模型应用于Extended Yale B 人脸数据库（K=5时），并将所得到的相似度矩阵A、隐相似度矩阵FFT和聚类指标矩阵F可视化。可视化结果如图3所示。理想情况下，来自不同聚类的数据点的相似度矩阵和隐相似度矩阵（对角块之外的元素）应为零，从而表现出区分性。与图3（a）、（b）所示的SSC+SSpeC 和SSSC 的相似度矩阵相比，本文模型产生了一个更好的相似矩阵，其对角块外的非零项非常少，如图3（f）所示，本文模型所得隐相似性矩阵基本上是对角块，具有更好的辨别性。

图3 三种模型在Extended Yale B人脸数据库上所得到的相似度矩阵、隐相似度矩阵和聚类指标矩阵的可视化（K=5）Fig.3 Visualization of affinity matrix，latent affinity matrix and clustering indicator matrix obtained by three models on Extended Yale B face data base（K=5）

3.2 Hopkins 155数据库实验

Hopkins 155 数据库是一个运动分割数据库，包括155 个视频序列，每个视频中有2个或3个类，对应于2个或3个低维子空间。图4 是来自Hopkins 155 数据库的样本图像。使用来约束E。本实验将本文模型与SSC、LRR、LSMR、N-cut、SSSC、K-means、SSC+SSpeC、LSR1、LSR2、BDLRR、BDSSC、LSA（Local Subspace Affinity）［33］和DCSC［22］作比较。

图4 Hopkins 155数据库的样本图像Fig.4 Sample images of Hopkins 155 data base

表3 Hopkins 155数据库上的聚类错误率对比 单位：%Tab.3 Clustering error rates on Hopkins 155 data base unit：%

图5 Hopkins 155数据库上聚类错误率与类的个数的关系Fig.5 Relationship between clustering error rate and the number of classes on Hopkins 155 data base

3.3 USPS数据库实验

USPS 数据集是一个手写数字数据集［27］，由10 类共9 298幅图像组成，每个类的手写数字为0～9。每幅图像的像素为16×16，部分样本如图6所示。

图6 USPS数据集的样本图像Fig.6 Sample images of USPS data base

本文实验中使用标准的主分量分析（Principal Component Analysis，PCA）将256维数据降至40维，并且只使用每类图像中的前100 幅图像，。该实验结果与SSC、LRR、LSMR、N-cut、SSSC、K-means、SSC+SSpeC、LSR、CASS 和光滑表示聚类（SMR）［34］进行比较。

实验结果表明，当α=0.1，β=0.000 01，λ=2.5 时得到“好”的聚类结果。聚类误差率如表4 所示，其中最好的结果用粗体表示。从表4 可以看出，与SSSC 相比，本文模型对USPS 数据集的聚类误差率从8.20%降到7.70%，聚类效果良好。

表4 USPS数据库上的聚类错误率 单位：%Tab.4 Clustering error rates on USPS database unit：%

4 结语

本文提出了一种新的子空间聚类模型，在SSSC 模型中加入了一个数据自适应稀疏正则项。一方面，新的正则项利用数据对之间的距离来强化潜在相似度矩阵的聚类判别性质，从而克服了SSpeC 中稀疏性惩罚的盲目性；另一方面，它建立了相似度矩阵和聚类指标矩阵之间的关系，克服了SSSC 只强制来自相同子空间的数据具有相同的聚类标签的缺陷，且是统一的优化模型。在三个常用数据集上的实验表明，本文提出的方法优于现有的两阶段方法和统一的SSSC优化模型。