低秩稀疏亲和矩阵子空间聚类

Low-Rank and Sparse Affinity Matrix for Subspace Clustering

摘要: 子空间聚类在近年来受到了大量的关注，其主要是利用谱聚类的思想学习一个表示系数矩阵以构造亲和矩阵，使用亲和矩阵获得聚类结果。众多方法采用对表示系数矩阵加以限制以保证最终得到的亲和矩阵用于聚类后得到良好的聚类效果，但这种做法会降低亲和矩阵的表示能力。本文提出低秩稀疏亲和矩阵子空间聚类算法，直接对亲和矩阵进行约束以提高表示系数矩阵的表示能力。文章给出了算法的优化过程，验证了结果的块对角性质，在不同数据集上的实验证明了方法的有效性。

Abstract: Subspace clustering has received a lot of attention in recent years, which mainly uses the idea of spectral clustering to learn a representation coefficient matrix to construct an affinity matrix, and uses the affinity matrix to obtain clustering results. Many methods use the restriction of the representation coefficient matrix to ensure that the final affinity matrix is used for clustering to obtain good clustering results, but this practice will reduce the representation ability of the affinity matrix. In this paper, a low-rank sparse affinity matrix subspace clustering algorithm is proposed to directly constrain the affinity matrix to improve the representation ability of the representation coefficient matrix. The optimization process of the algorithm is presented, and the block diagonal property of the results is verified. Experiments on different data sets prove the effectiveness of the method.

1. 引言

在大数据时代，我们经常会接触到大量的数据信息，为了对所获的数据信息进行处理，人们对数据的结构进行了探索[1] [2]。高维数据样本可以看作取自多个低维线性子空间的集合，将一组高维数据样本分配到它们对应的子空间当中的这项工作被称为子空间聚类[3]。子空间聚类问题在机器学习和计算机视觉领域有着广泛的应用，像是人脸聚类[4]，图像分割[5]等等，因此激发了广大研究者的兴趣。在过去几十年，关于子空间聚类有大量的算法被提出，在这些算法中，基于谱聚类的思想[6]在聚类任务中展现出突出的表现，并在近几年引起了广泛关注。

在基于谱聚类的思想中，我们首先要获得一个亲和矩阵，然后通过使用谱聚类的方法，例如，归一化分割[7]，来获得最终的聚类结果。且如果所获得的亲和矩阵是块对角的，那么通过谱聚类得到的结果可能是正确的。经典的基于谱聚类的算法稀疏子空间聚类(SSC)，低秩表示子空间聚类(LRR)，非负低秩子空间聚类(NNLRS) [8]-[10]等都是利用矩阵的自我表示的特性来构建亲和矩阵，并采用了不同的正则化函数对表示系数矩阵进行约束。Lu等人指出[11]，如果选择的正则化函数满足强制块对角(EBD)条件，那么当数据所在的子空间是独立的情况下得到的解会具有块对角性质。这样构造的亲和矩阵也满足块对角性质，进而谱聚类后能够得到正确的聚类结果。

从进行子空间聚类的过程上来看，上述的这些方法都是基于自表示特性得到表示系数矩阵，使用正则化函数进行约束，以保证用于谱聚类的亲和矩阵(或者表示系数矩阵)的块对角性。但可以注意到的是，上述正则化函数中的变量都是表示系数矩阵，而非亲和矩阵。且在一些方法当中，例如块对角表示子空间聚类(BDR) [11]，虽然通过目标函数对表示系数矩阵加以对称、非负的限制，使得表示系数矩阵的引入是对称、非负的，但这些限制会降低表示系数矩阵的表示能力。

经过以上的观察，本文提出可以将亲和矩阵W直接作为自变量来建立目标函数求解，即建立以亲和矩阵W为自变量的正则化求解器，直接追求W的块对角性质。除此之外，本文没有对表示系数矩阵Z进行约束，而是利用高维数据的低秩性和稀疏性来直接构建亲和矩阵。这样可以直接获得一个低秩稀疏亲和矩阵。具体来说，对于给定的一组数据集，首先利用数据的自表示特性，将一个数据点表示为其他样本点的线性组合，得到表示系数矩阵Z。其次，利用得到的Z构建亲和矩阵$W=\left(\left|Z\right|+\left|Z^{\text{T}}\right|\right)/2$ 。最后，对W加以经典的低秩、稀疏限制以得到可能的块对角解，这可以在追求W块对角结构的同时使得表示系数矩阵Z刻画数据集的全局和局部结构。基于此，本文提出一个新的子空间聚类的算法，低秩稀疏亲和矩阵子空间聚类(LRSA)，并使用交替迭代算法(ADM) [12]求解。

这篇文章的贡献可以总结如下：

1) 我们讨论了如何在子空间聚类模型中直接引入亲和矩阵的低秩和稀疏，提出了LRSA模型，这是首次。

2) 我们证明了对亲和矩阵引入的低秩、稀疏的策略也能够保证其块对角性质。

3) 与以往工作不同的是，我们可以在求解过程中可以同时得到表示系数矩阵和亲和矩阵，在现实数据集上的实验结果证明了方法的有效性。

2. 预备知识

给定一个数据集$X=\left[x_1,x_2,\cdots ,x_n\right]\in R^{d\times n}$ 包含来自k个独立子空间的n个数据样本，每个数据样本维数为d。首先通过数据样本的自表示特性，可以获得表示系数矩阵Z：

$X=XZ,Z\in R^{n\times n},$ (1)

满足公式(1)的矩阵Z并不是唯一的，为了得到满足聚类结果的Z，需要引入正则化函数$f\left(Z,X\right)$ ，对结果进行限制，问题转化为

$\min f\left(Z,X\right),s.t.X=XZ.$ $$ (2)

如果有一个满足k-块对角的Z，那么通过公式$W=\left(\left|Z\right|+\left|Z^{\text{T}}\right|\right)/2$ 得到的亲和矩阵用于谱聚类可能得到正确的聚类结果。

2.1. 块对角性质

k-块对角正则化器([11]，定义5)：对于任一亲和矩阵$W\in R^{n\times n}$ ，k-块对角正则化器定义为$L_W$ 的k个最小的特征值之和，也就是

${\Vert W\Vert }_{\boxed{k}}={{\displaystyle {\sum }_{n-k+1}^n\lambda }}_i\left(L_W\right),$ (3)

这里$L_W=Diag\left(W1\right)-W$ 是W的拉普拉斯矩阵，$1\in R^n$ 是全是1的向量，Diag能够将向量转化为块对角矩阵以及用矩阵对角线上的元素构成一个向量。

文章[11]的EBD条件对系数表示矩阵的块对角性质给出了理论证明，对于独立子空间中充足的样本数据，EBD条件能够判断由(2)式获得的数据是否是块对角的。具体来看，对于给定的任意一个函数$f\left(Z,X\right)$ ，定义在$\left(\Omega ,\Delta \right)$ 上，这里$\Omega$ 是一个包含许多方阵的集合且$\Delta$ 是一个包含许多非零向量的矩阵的

集合。对于任意一个$Z=\left(\begin{array}{cc}{Z}_1& Z_3\\ Z_4& Z_2\end{array}\right)\in \Omega ,Z\ne 0,Z_1,Z_2\in \Omega$ ，并且$X=\left[X_1,X_2\right]$ ，这里$X_1$ 和$X_2$ 分别与$Z_1$ 和$Z_2$ 对应。$Z=\left(\begin{array}{cc}{Z}_1& 0\\ 0& Z_2\end{array}\right)\in \Omega$ 。假设所有的矩阵都有合适的维度，EBD条件就是：

1) $f\left(Z,X\right)=f\left(P^{\text{T}}ZP,XP\right)$ ，对于任意的初等矩阵P，$P^{\text{T}}ZP\in \Omega$ 。

2) $f\left(Z,X\right)\ge f\left(Z^B,X\right)$ ，当且仅当$Z=Z^B$ (或者$Z_3=Z_4=0$ )时取得等号。

3) $f\left(Z^B,X\right)=f\left(Z_1,X_1\right)+f\left(Z_2,X_2\right)$ 。

2.2. 非负低秩稀疏图(NNLRS)

低秩子空间聚类(LRR)通过解决下面的优化问题来得到一个低秩的表示系数矩阵Z，使得到的解能够获得数据的全局结构

$\underset{Z}{\min }{\Vert Z\Vert }_{*},s.t.X=XZ.$ (4)

并且[11]证明得到的解能够满足块对角性质。

稀疏表示(SR)是通过对Z施加$l_0$ 范数的限制来得到一个稀疏的结果，以刻画局部低维数据的线性关系，这是一个NP难题，SSC将问题转换为

$\underset{\text{Z}}{\min }{\Vert Z\Vert }_1,s.t.X=XZ,diag\left(Z\right)=0.$ (5)

且在理论上能够证明得到解是块对角的。

非负低秩稀疏图(NNLRS)将上述二者结合，通过解决下面的问题同时施加低秩、稀疏及非负的限制，以同时得到全局和局部的信息

$\underset{Z}{\min }{\Vert Z\Vert }_{*}+\beta {\Vert Z\Vert }_1,s.t.X=XZ,Z\ge 0.$ (6)

可以证明上述正则化函数能够满足EBD条件，进而可得到块对角解。

3. LRSA思想

3.1. 目标函数

正如在第一部分的分析，大部分基于谱聚类的算法，都是通过对表示系数矩阵Z进行限制，以追求亲和矩阵$W=\left(\left|Z\right|+\left|Z^{\text{T}}\right|\right)/2$ 的块对角性质。因为最终用于谱聚类的是亲和矩阵W，我们提出，能否直接对亲和矩阵进行限制以追求块对角性质。为了解决这一问题，我们对亲和矩阵引入了经典的低秩、稀疏限制，即可以看作在NNLRS图的基础上将正则化函数的自变量由Z改成W，且不再对表示系数矩阵Z施加非负的限制。于是，我们可以通过解决下面的优化问题来寻找一个亲和矩阵W

$\underset{W}{\min }{\Vert W\Vert }_{*}+\beta {\Vert W\Vert }_1,s.t.X=XZ,W=\frac{|Z|+|Z^{\text{T}}|}{2},$ (7)

这里$\beta$ 是一个用来平衡低秩和稀疏的大于零的参数。

然而，解决问题(7)是一个NP难题。幸运的是，我们发现根据亲和矩阵W的定义方式，$\parallel W{\parallel }_1$ 即为${\Vert Z\Vert }_1$ ，但如何求解|${\Vert W\Vert }_{*}$ 没有前人的经验。注意到在${\Vert W\Vert }_{*}$ 中，W是一个非负、对称的矩阵，对应的拉普拉斯矩阵$L_W$ 定义为$L_W=Diag\left(W1\right)-W$ ，其中，$Diag\left(W1\right)$ 为对角矩阵。若想使得W为块对角的，只要$L_W$ 是块对角的即可。于是问题转化为

$\underset{W}{\min }{\Vert L_W\Vert }_{*}+\beta {\Vert W\Vert }_1,s.t.X=XZ,W=\frac{|Z|+|Z^{\text{T}}|}{2},$ (8)

注意到，$L_W$ 是一个对称、半正定的矩阵，其特征值等于奇异值，即${\Vert L_W\Vert }_{*}={\displaystyle \sum _{i=1}^n{\lambda }_i\left(L_W\right)}$ (${\lambda }_i,i=1,\cdots ,n,$ 代表$L_W$ 的特征值，降序排列)。这一项与${\Vert W\Vert }_{\boxed{k}}$ 密切相关，具体来说

${\Vert L_W\Vert }_{*}={\displaystyle \sum _{i=1}^n{\lambda }_i\left(L_W\right)={\displaystyle \sum _{i=1}^{n-k}{\lambda }_i\left(L_W\right)+}}{\displaystyle \sum _{i=n-k+1}^n{\lambda }_i\left(L_W\right)}={\displaystyle \sum _{i=1}^{n-k}{\lambda }_i\left(L_W\right)}+{\Vert W\Vert }_{\boxed{k}}.$ (9)

上述讨论可以看到，块对角也可以限制低秩，这不失为对块对角结构先验的另一种解释。于是问题可以转化为

$\underset{W}{\min }{\Vert W\Vert }_{\boxed{k}}+\beta {\Vert Z\Vert }_1,s.t.X=XZ,W=\frac{|Z|+|Z^{\text{T}}|}{2}.$ (10)

3.2. 优化

在这一部分，我们将讨论如何解决问题(10)。首先，问题(10)可以被转化为下面这个等价的问题：

$\min {\Vert W\Vert }_{\boxed{k}}+\beta {\Vert J\Vert }_1+{\Vert X-XZ\Vert }_F^2,s.t.Z=B,Z=J,W=\frac{|Z|+|Z^{\text{T}}|}{2},$ (11)

这里B和Z是两个辅助变量。这样，上述问题可以被交替迭代算法ADM [12]解决。问题(11)对应的增广拉格朗日函数定义如下：

$$ $\begin{array}{l}L={\Vert W\Vert }_k+\beta {\Vert J\Vert }_1+\lambda {\Vert X-XZ\Vert }_F^2+\langle Y_1,Z-J\rangle +\langle Y_2,Z-B\rangle \\ +\frac{\mu }{2}\left({\Vert Z-J\Vert }_F^2+{\Vert Z-B\Vert }_F^2\right),s.t.W=\frac{\left|B\right|+\left|B^{\text{T}}\right|}{2},\end{array}$ (12)

其中，$Y_1,Y_2$ 是两个拉格朗日乘子，$\mu >0$ 是一个参数。然后通过关于变量$Z,J,B$ 每次最小化L，同时将其他变量固定在最新值，可以交替优化变量。假设k代表目前的迭代步数，对于变量和拉格朗日乘子的更新步骤描述如下：

1) 固定其它更新Z：将(12)中与Z无关的项去除，我们得到：

$\underset{Z^{k+1}}{\min }\lambda {\Vert X-X{Z}^{k+1}\Vert }_F^2+\langle Y_1^k,Z^{k+1}-J^k\rangle +\langle Y_2^k,Z^{k+1}-B^k\rangle +\frac{{\mu }^k}{2}\left({\Vert Z^{k+1}-J^k\Vert }_F^2+{\Vert Z^{k+1}-B^k\Vert }_F^2\right).$ (13)

这里$J^k,B^k,Y_1^k,Y_2^k$ 和${\mu }^k$ 是$J,B,Y_1,Y_2$ 和$\mu$ 分别在第$k-1$ 次迭代中得到的，$Z^{k+1}$ 是更新需要得到的。通过(13)式对$Z^{k+1}$ 求偏导并令其偏导等于零，可以得到：

$Z^{k+1}={\left(2\lambda X^{\text{T}}X+2{\mu }^{k}I\right)}^{-1}\left(2\lambda X^{\text{T}}X-Y_1^k-Y_2^k+{\mu }^k{J}^k+{\mu }^k{B}^k\right).$ (14)

2) 固定其它更新J：当$Z^{k+1}$ 获得之后，同前面的处理过程一样，我们找到(12)中与J有关的项，得到：

$\underset{J^{k+1}}{\min }\beta {\Vert J^{k+1}\Vert }_1+\langle Y_1^k,Z^{k+1}-J^{k+1}\rangle +\frac{{\mu }^k}{2}{\Vert Z^{k+1}-J^{k+1}\Vert }_F^2.$ (15)

满足(15)的最优解$J^{k+1}$ 满足${\left[J^{k+1}\right]}_{ij}=S_{{\epsilon }_{ij}}\left(Z^{k+1}+Y_1^k/{\mu }^k\right)$ ，这里$S_{{\epsilon }_{ij}}\left(x\right)=\max \left(x-{\epsilon }_{ij},0\right)+\min \left(x+{\epsilon }_{ij},0\right)$ ，且${\epsilon }_{ij}=\beta /{\mu }^k$ 。

3) 固定其它更新B：注意到W是由B计算得到的，因此对于更新B，优化问题转换为：

$\underset{B}{\min }{\Vert W\Vert }_{\boxed{k}}+\langle Y_2,Z-B\rangle +\frac{\mu }{2}{\Vert Z-B\Vert }_F^2,s.t.W=\frac{\left|B\right|+\left|B^{\text{T}}\right|}{2},$ (16)

这里对k块对角正则化器${\Vert W\Vert }_{\boxed{k}}$ 的求解是一个非凸问题，将其转化为凸问题[13]求解：

$\underset{B}{\min }tr\langle Diag\left(W1\right)-W,A\rangle +\langle Y_2,Z-B\rangle +\frac{\mu }{2}{\Vert Z-B\Vert }_F^2,s.t.W=\frac{\left|B\right|+\left|B^{\text{T}}\right|}{2},0\le A\le I,tr\left(A\right)=n.$ (17)

问题(17)可以由更新$\left\{A,B\right\}$ 解决，在前面已经求得$Z^{k+1}$ 的情况下，等价于经过下面的(18) (19)依次更新$B^{k+1},A^{k+1}$ ：

$B^{k+1}=\underset{B}{\arg \min }\langle Diag(W1)-W,A\rangle +\langle Y_2,Z-B\rangle +\frac{\mu }{2}{\Vert Z-B\Vert }_F^2,s.t.W=\frac{\left|B\right|+\left|B^{\text{T}}\right|}{2}.$ (18)

$A^{k+1}=\underset{A}{\arg \min }\langle Diag\left(W1\right)-W,A\rangle ,0\le A\le I,tr\left(A\right)=n.$ (19)

对于(18)，问题等价于

$B^{k+1}=\underset{B}{\text{argmin}}<W,diag\left(A\right)1^{\text{T}}-A>+\frac{\mu }{2}{\Vert Z+\frac{Y_2}{\mu }-B\Vert }_F^2,s.t.W=\frac{\left|B\right|+\left|B^{\text{T}}\right|}{2},$ (20)

将W代入，令$N=Z+\frac{Y_2}{\mu },P=diag\left(A\right)1^{\text{T}}-A$ ，问题等价于

$B^{k+1}=\underset{B}{\arg \min }\frac{1}{2}\langle \left|B\right|+\left|B^{\text{T}}\right|,P\rangle +\frac{\mu }{2}{\Vert N-B\Vert }_F^2,$ (21)

等价于

$B^{k+1}=\underset{B}{\arg \min }tr\left(\left|B\right|\left(P+P^{\text{T}}\right)\right)+\mu {\Vert N-B\Vert }_F^2,$ (22)

令$V=\frac{P+P^{\text{T}}}{2}$ ，问题等价于

$B^{k+1}=\underset{B}{\arg \min {\displaystyle \sum \left|B\right|\circ V}}+\mu {\Vert N-B\Vert }_F^2.$ (23)

经求解，上述优化问题的最优解$B^{k+1}$ 满足：

当${\left[V^{k+1}\right]}_{ij}\ge 0$ 时，

${\left[B^{k+1}\right]}_{ij}=\max \left({\left[N^{k+1}\right]}_{ij}-\frac{1}{2}{\left[V^{k+1}\right]}_{ij},0\right)+\min \left({\left[N^{k+1}\right]}_{ij}+\frac{1}{2}{\left[V^{k+1}\right]}_{ij},0\right),$ (24)

当${\left[V^{k+1}\right]}_{ij}<0$ 时，

${\left[B^{k+1}\right]}_{ij}=\{\begin{array}{c}{\left[N^{k+1}\right]}_{ij}-\frac{1}{2}{\left[V^{k+1}\right]}_{ij}\begin{array}{cc}& \end{array}{\left[N^{k+1}\right]}_{ij}\ge 0\\ {\left[N^{k+1}\right]}_{ij}+\frac{1}{2}{\left[V^{k+1}\right]}_{ij}\begin{array}{cc}& \end{array}{\left[N^{k+1}\right]}_{ij}<0\end{array},$ (25)

其中${\left[N^{k+1}\right]}_{ij}={\left[Z^{k+1}\right]}_{ij}+\frac{{\left[Y_2^k\right]}_{ij}}{{\mu }^k},{\left[P^{k+1}\right]}_{ij}={\left[diag\left(A^k\right)1^T-A^k\right]}_{ij},{\left[V^{k+1}\right]}_{ij}=\frac{{\left[P^{k+1}\right]}_{ij}+{\left[{\left(P^T\right)}^{k+1}\right]}_{ij}}{2}.$ 对于(19)，$A^{k+1}=U{U}^{\text{T}},U\in R^{n\times k}$ 包括$Diag\left(W1\right)-W$ 的n个最小特征值对应的特征向量。

4) 固定其它更新参数、乘子：具体的更新步骤总结如下：

$Y_1^{k+1}=Y_1^k+{\mu }^k\left(Z^{k+1}-J^{k+1}\right),Y_2^{k+1}=Y_2^k+{\mu }^k\left(Z^{k+1}-B^{k+1}\right),{\mu }^{k+1}=\min \left(\rho {\mu }^k,{\mu }_{\max }\right).$ (26)

这里$\rho$ 和${\mu }_{\max }$ 是两个给定的正参数。

3.3. 算法

我们在算法1中总结了LRSA的算法步骤，如表1所示。对于一个数据集，一旦得到了LRSA的解，在W上使用N-cut获得最终的聚类结果。

算法1的计算复杂度主要取决于更新四个变量$Z,J,B,A$ 。第一，更新Z需要计算一个$n\times n$ 的伪逆矩阵，故复杂度为$O\left(n^3\right)$ 。第二，更新J和B都需要计算一个$n\times n$ 矩阵的每一个元素，因此它们的计算复杂度是$O\left(n^2\right)$ 。第三，更新A时进行了特征值计算，计算复杂度为$O\left(n^3\right)$ 。综上，我们可以看到算法1在每次迭代时的时间复杂度为$O\left(n^3\right)$ 。

4. 块对角性

命题1：满足$\Phi \left(W\right)={\Vert L_W\Vert }_{*}+\beta {\Vert W\Vert }_1$ 的亲和矩阵将是块对角的。

为了证明这一命题，我们将问题(8)整理如下：

Table 1. The algorithm steps of LRSA

表1. LRSA的算法步骤

算法1 LRSA

输入：矩阵$X=\left[x_1,x_2,\cdots ,x_n\right]\in R^{d\times n}$ ，参数$\beta ,\lambda ,k$ 。

初始化：$B=J=Z=A=Y_1=Y_2=0,$

$\mu ={10}^{-6},\rho =1.1,{\mu }_{\max }={10}^6,\epsilon ={10}^{-4}.$

while未收敛do

1. 固定其它更新Z。按照公式(14)更新Z。

2. 固定其它更新J。按照公式(15)更新J。

3. 固定其它更新B。按照公式(25)更新B。

4. 固定其它更新A。按照公式(19)更新A。

5. 更新乘子和参数μ。按照公式(26)进行更新。

6. 验证收敛条件：${\Vert Z-J\Vert }_{\infty }<\epsilon ,{\Vert Z-B\Vert }_{\infty }<\epsilon$ 。

end while

$\min {\Vert L_W\Vert }_{*}+\beta {\Vert W\Vert }_1,s.t.X=XZ,W=\frac{\left|Z\right|+\left|Z^{\text{T}}\right|}{2},L_w=D-W,D=Diag\left(W1\right).$ (27)

问题(27)可被改写为[11]中的统一形式

$\min f\left(Z,X\right),s.t.X=XZ.$ (28)

其中$f\left(Z,X\right)={\Vert L_W\Vert }_{*}+\beta {\Vert Z\Vert }_1$ ，可以看到$f\left(Z,X\right)$ 可写为$f_1\left(Z,X\right)+\beta f_2\left(Z,X\right)$ ，其中$f_1\left(Z,X\right)={\Vert L_W\Vert }_{*},f_2\left(Z,X\right)={\Vert Z\Vert }_1$ 。对于$f_2\left(Z,X\right)$ ，在[11]中已经说明能够满足EBD条件的(1)~(3)。下面我们重点讨论$f_1\left(Z,X\right)$ 。

容易证明对于任意一个初等矩阵P，问题(27)满足$f\left(Z,X\right)=f\left(PX,P^{\text{T}}XP\right)$ ，即EBD条件(1)。同样容易验证问题(27)满足EBD条件(3)。因此，下面对是否满足EBD条件(2)进行讨论。

命题2：函数$f_1\left(Z,X\right)={\Vert L_W\Vert }_{*}$ ，定义在$\left(\Omega ,\Delta \right)$ 上，$\Omega$ 是一个包含许多方阵的集合，$\Delta$ 是一个包含许多非零向量的矩阵的集合。对于任意一个$Z=\left[\begin{array}{cc}{Z}_1& Z_3\\ Z_4& Z_2\end{array}\right]\in \Omega ,Z\ne 0,Z_1,Z_2\in \Omega$ 并且$X=\left[X_1,X_2\right]$ 这里$X_1$ 和$X_2$ 分别与$Z_1$ 和$Z_2$ 对应，$Z^B=\left[\begin{array}{cc}{Z}_1& 0\\ 0& Z_2\end{array}\right]\in \Omega$ 。假设所有的矩阵都有合适的维度，记$W=\frac{\left|Z\right|+\left|Z^{\text{T}}\right|}{2},W^B=\frac{\left|Z^B\right|+\left|{\left(Z^B\right)}^{\text{T}}\right|}{2}$ ，有$f_1\left(Z,X\right)\ge f_1\left(Z^B,X\right)$ 。

证明：由$W=\frac{\left|Z\right|+\left|Z^{\text{T}}\right|}{2},W^B=\frac{\left|Z^B\right|+\left|{\left(Z^B\right)}^{\text{T}}\right|}{2}$ ，可知$L_W=D-W,L_{W^B}=D^B-W^B$ ，其中$D=Diag\left(W1\right),D^B=Diag\left(W^{B}1\right)$ ，$L_W$ 与$L_{W^B}$ 均为对称半正定矩阵。于是考虑$L_{W^A}=D-W^B=\left(D-D^B\right)+L_{W^B}$ ，$L_{W^A}$ 与$L_{W^B}$ 的区别在于$L_{W^A}$ 的对角元更大，且对角元均$\ge 0$ ，故$tr\left(L_{W^A}\right)\ge tr\left(L_{W^B}\right)，\forall x\ne 0,x^{\text{T}}{L}_{W^A}x=x^{\text{T}}\left(D-D^B\right)x+x^{\text{T}}{L}_{W^B}x=d_1{x}_1^2+d_2{x}_2^2+\cdots +d_n{x}_n^2+x^{\text{T}}{L}_{W^B}x,$ $x_1,x_2,\cdots x_n$ 为x的各个分量，因此$x^{\text{T}}{L}_{W^A}x\ge 0,$ $x^{\text{T}}{L}_{W^A}x$ 半正定。又由$L_{W^A}$ 对称，可知$L_{W^A}$ 特征值等于奇异值，${\Vert L_{W^A}\Vert }_{*}$ 等于$L_{W^A}$ 特征值之和，且由矩阵的特征值之和等于矩阵的迹[14]，可以得到${\Vert L_{W^A}\Vert }_{*}=tr\left(L_{W^A}\right)\ge tr\left(L_{W^B}\right)={\Vert L_{W^B}\Vert }_{*}$ 。而$L_W$ 与$L_{W^A}$ 区别在于$L_{W^A}$ 非对角块位置为0，所以有${\Vert L_W\Vert }_{*}\ge {\Vert L_{W^A}\Vert }_{*}$ ，综上，${\Vert L_W\Vert }_{*}\ge {\Vert L_{W^B}\Vert }_{*}$ ，即$f_1\left(Z,X\right)\ge f_1\left(Z^B,X\right)$ 。

由命题2可知$f_1\left(Z,X\right)$ 满足EBD条件的前半部分，结合$f_2\left(Z,X\right)$ 满足EBD条件(1)~(3)，$f_1\left(Z,X\right)$ 满足EBD条件(1)，(3)。由[11]命题6，$f\left(Z,X\right)$ 满足EBD条件(1)~(3)，得到的结果满足块对角性质，即$\Phi \left(W\right)={\Vert L_W\Vert }_{*}+\beta {\Vert W\Vert }_1$ 的解满足块对角，命题1得证。

5. 实验

在这一部分，我们进行了子空间聚类的实验来证明LRSA思想用于子空间聚类的有效性。

5.1. 实验设定

5.1.1. 数据集

我们在4个真实世界的数据集进行实验来检验LRSA的有效性，真实数据集包括nMNIST_P200手写体数据集，PIE_32和AR20这两个人脸数据集以及USC_SIPI纹理数据集。

nMNIST_P200手写体数据集包含“0”~“9”十个类别的共2000张图片，每张图片大小是28 × 28像素。实验中我们在每个类别中选取20张图像构成具有200张图片的数据集，因此可以得到大小为784 × 200的数据矩阵。

PIE_32数据集包括68个人在不同姿势、光照和表情下的共11,554张图像，每张图像是32 × 32维的。我们选择前20个人的每人20张图片进行实验，得到大小为1024 × 400的数据矩阵。

AR20数据集包括120个人的3120张人脸图像，对于每个人的26张图片分两个阶段拍摄，每次拍摄13张图片，涵盖了在不同表情、照明和遮挡下的正脸图片，每张图片大小为50 × 40像素。实验中选取前20人的每人全部26张照片，组成大小为2000 × 520的数据矩阵。

USC_SIPI纹理数据集根据图片的基本特征分卷，包括了树皮、砖块、泡沫、草地、皮革、猪皮、纤维、沙子、稻草、水滴、织物、木材和羊毛13种纹理，共包括1456张图片。实验中选择13个类别的每类80张图片，组成大小为16,384 × 1040的数据矩阵。对于USC_SIPI数据集的纹理图像，我们通过LBP_riu2提取其特征，以获得图像的纹理信息，经提取特征后得到大小为10 × 1040的矩阵。

5.1.2. 比较方法

我们在实验中选择了具有代表性并且与我们的方法密切相关的算法进行对比，包括SSC，LRR，LSR，NNLRS，SMR，BDR和AGCSC。由于参数的设定会影响参与评估的算法的表现，为了进行公平的比较，对于每个比较的方法，我们按照相应文章中的建议进行了参数设定，对于不同的实验，分别保留每个算法最好的表现。

5.1.3. 评价标准

实验采用了七种评价标准来对结果进行评价。分别是准确性(ACC)、归一化互信息(NMI)、纯度(Purity)、调整兰德指数(ARI)、F-score、精确率和召回率。上述所有标准，计算出的数值越高表明聚类效果越好。

5.2. 实验结果

在真实数据集上的实验

表2~5展示了LRSA在四个数据集上具体的聚类表现，在每个表中，在每个指标下最好的结果用黑体字标出。可以看到LRSA在除USC_SIPI数据集外的其它数据集上相较于其他算法表现的都很好。这能体现出1) 通过自表示获取数据子空间结构后，直接对构建的亲和矩阵进行低秩稀疏约束用于聚类，同样可以得到优秀的聚类结果。2) 与基于自表示的子空间聚类的相关算法相比，LRSA在四个比较的数据集上表现的最好，体现出在真实数据集中，对亲和矩阵进行约束可以有效提高表示系数矩阵的表示能力。

Table 2. Clustering performance of different algorithms on nMNIST_P200 dataset

表2. 不同算法在nMNIST_P200数据集上的聚类表现

	ACC	NMI	Purity	ARI	F-score	Precision	Recall
LRSA	0.640	0.559	0.640	0.420	0.478	0.459	0.498
BDR-B	0.400	0.314	0.415	0.160	0.244	0.232	0.257
BDR-Z	0.230	0.132	0.235	0.015	0.110	0.110	0.111
NNLRS	0.545	0.535	0.575	0.347	0.410	0.402	0.419
AGCSC	0.555	0.590	0.600	0.404	0.464	0.438	0.494
LRR	0.265	0.153	0.275	0.047	0.170	0.126	0.261
SSC	0.265	0.146	0.275	0.045	0.167	0.125	0.255
SMR	0.255	0.140	0.270	0.031	0.168	0.113	0.329
LSR1	0.305	0.210	0.320	0.067	0.158	0.155	0.161
LSR2	0.255	0.140	0.270	0.0230	0.165	0.113	0.306

Table 3. Clustering performance of different algorithms on PIE_32 dataset

表3. 不同算法在PIE_32数据集上的聚类表现

	ACC	NMI	Purity	ARI	F-score	Precision	Recall
LRSA	1	1	1	1	1	1	1
BDR-B	0.533	0.628	0.553	0.335	0.371	0.326	0.431
BDR-Z	0.740	0.829	0.753	0.633	0.652	0.620	0.686
NNLRS	1	1	1	1	1	1	1
AGCSC	1	1	1	1	1	1	1
LRR	0.148	0.211	0.185	0.043	0.116	0.072	0.308
SSC	0.435	0.562	0.450	0.263	0.300	0.287	0.314
SMR	0.135	0.187	0.178	0.022	0.106	0.059	0.591
LSR1	0.553	0.659	0.573	0.394	0.424	0.409	0.441
LSR2	0.150	0.190	0.188	0.031	0.108	0.065	0.310

Table 4. Clustering performance of different algorithms on AR20 dataset

表4. 不同方法在AR20数据库上的聚类表现

	ACC	NMI	Purity	ARI	F-score	Precision	Recall
LRSA	0.796	0.841	0.802	0.712	0.726	0.711	0.741
BDR-B	0.654	0.695	0.673	0.485	0.511	0.483	0.543
BDR-Z	0.739	0.805	0.752	0.641	0.659	0.642	0.676
NNLRS	0.758	0.804	0.758	0.678	0.655	0.644	0.668
AGCSC	0.740	0.790	0.740	0.601	0.621	0.594	0.649
LRR	0.164	0.203	0.190	0.058	0.135	0.079	0.467
SSC	0.187	0.205	0.225	0.036	0.104	0.071	0.197
SMR	0.198	0.230	0.206	0.055	0.112	0.090	0.147
LSR1	0.610	0.655	0.621	0.429	0.457	0.440	0.476
LSR2	0.168	0.173	0.200	0.027	0.098	0.065	0.204

Table 5. Clustering performance of different algorithms on USC_SIPI dataset

表5. 不同方法在USC_SIPI数据库上的聚类表现

	ACC	NMI	Purity	ARI	F-score	Precision	Recall
LRSA	0.888	0.863	0.888	0.788	0.805	0.783	0.827
BDR-B	0.872	0.843	0.872	0.756	0.775	0.754	0.796
BDR-Z	0.873	0.842	0.873	0.757	0.776	0.755	0.798
NNLRS	0.758	0.790	0.773	0.659	0.686	0.652	0.724
AGCSC	0.892	0.867	0.892	0.790	0.806	0.791	0.821
LRR	0.742	0.762	0.771	0.640	0.669	0.640	0.701
SSC	0.864	0.833	0.864	0.745	0.765	0.742	0.789
SMR	0.803	0.827	0.822	0.716	0.739	0.703	0.778
LSR1	0.797	0.811	0.816	0.707	0.730	0.698	0.765
LSR2	0.800	0.802	0.819	0.706	0.729	0.707	0.754

6. 总结及未来工作

这篇文章提出了一个新的子空间聚类的方式——低秩稀疏亲和矩阵(LRSA)子空间聚类。LRSA在学习得到表示系数矩阵的同时定义亲和矩阵，直接对亲和矩阵进行低秩、稀疏约束，以在不影响表示系数矩阵表示能力的情况下，更好的获得数据的全局、局部结构信息。通过求解整个数据的低秩稀疏亲和矩阵，我们还能同时获得系数表示矩阵，得到数据的结构信息。在真实数据上的实验可以证明LRSA能够极大的利用通过表示系数矩阵得到的数据结构信息，因此相比于其他算法更加具有信息性且更适合聚类任务。

对于未来的工作有如下展望：按照本文思路，如果对亲和矩阵加以${\Vert \cdot \Vert }_F$ 限制是否进行求解，得到的结果能否满足EBD条件。

基金项目

国家自然科学基金(62076115)，大连青年科技之星项目(2023RQ088)。