基于核的低秩子空间聚类算法

马凯 王伟文 由从哲

摘    要：基于稀疏表示和低秩表示的子空间聚类算法是目前的研究热点，但大多数子空间聚类方法只适用于线性子空间或仿射子空间。针对这一问题，研究了一种能处理非线性模型的核子空间聚类方法。提出学习一种低秩核映射，通过这种映射，特征空间中的映射数据不仅具有低秩性，而且具有自表达性，从而使得低维子空间结构在高维特征空间中得以呈现。通过运动分割和人脸图像聚类问题的实验，验证了方法的有效性。

关键词：子空间聚类;低秩表示;核方法;运动分割;人脸聚类

中图分类号：TP391.4                文献标识码：A               文章编号：2095-7394（2021）04-0032-06

子空间聚类是指将位于一组低维线性子空间中的数据样本点划分到不同子空间中的算法。该算法在计算机视觉中有多种应用，如：运动分割、图像聚类。现有的子空间聚类方法大致可分为三类[1]：代数算法、统计方法以及基于谱聚类的方法。目前，对于子空间聚类的研究热点主要集中在基于表示的谱聚类算法[2-3]，算法主要步骤为：（1）构建亲和矩阵;（2）应用谱聚类对亲和图进行划分，得到聚类结果。然而，这些方法只能处理线性子空间问题，在实际应用中，数据点可能不完全适合线性子空间模型。例如，在运动分割问题中，相机通常具有某种程度的透视失真，因此，仿射相机假设不成立;在这种情况下，一个运动的轨迹就会位于非线性子空间中。

为了解决这一问题，也有一些方法通过核技巧将线性子空间聚类扩展到对应的非线性子空间。例如，核稀疏子空间聚类（KSSC）方法[4]采用多项式核或高斯RBF核将数据矩阵的内积替换为核矩阵。KSSC算法假设数据是从对称正定（SPD）矩阵中提取的，并将对Log-Euclidean核应用于SPD矩阵上，实现SSC算法的核化。但是，由于这些方法中使用了预先定义的核，特征空间映射后的数据不能保证低秩;因此，很难形成多个低维子空间结构。

在本文中，我们通过学习得到一个低秩核映射，这样，通过核映射得到的特征空间中的数据都具有低秩性和自表示特性。直观地说，本文方法强制核特征映射为低秩，从而使得数据在特征空间中形成线性子空间结构。

1    相关工作

子空间聚类算法的核心在于亲和矩阵的构造，来自同一子空间的数据点具有高亲和值，而来自不同子空间的数据点具有低亲和值（理想情况下为零）。基于表示的子空间聚类方法利用子空间自表示特性，即一个子空间中的数据样本点可以表示为同一子空间中其他数据样本点的线性组合，并利用自表示系数矩阵作为谱聚类的亲和矩阵。

给定数据矩阵[X∈RD×N]，子空间自表示特性可以表示为[X=XZ]，其中，[Z]为自表示系数矩阵。JI等人[5]在子空间独立的假设下，通过最小化[Z]的某些范数，得到[Z]的最优解具有块对角结构，该优化问题可以表示为如下形式：

在实际应用中，数据往往含有噪声，为了处理噪声污染的数据，LRR算法的目标函数可以表示为如下形式：

其中：[λ]为平衡参数;采用[E2，1]来强调噪声矩阵[E]的列稀疏性。

LRR的设计是为了处理原始输入空间中子空间并集的数据;因此，它不能有效地处理从非线性输入空间采样的数据。此外，我们不能直接对LRR的目标函数进行核化，这是因为当数据不以内积的形式出现时，核技巧无法直接使用（即[x′ixj]）。

2    基于核的低秩子空间聚类算法

核方法可以将数据点映射到高维特征空间，在该空间中可进行线性模式分析，并与输入数据空间中的非线性分析相对应[6]。核方法中的常见做法不是显式计算高维特征空间中的坐标，而是使用“核技巧”，其中，特征映射是隐式的，特征空间中一对数据点之间的内积作为核值计算。虽然，“核技巧”在计算上相对方便，但对于常用的核函数（如高斯RBF），我们并不清楚数据点是如何映射到特征空间的。具体地说，在子空间聚类的背景下，在隐式特征映射下，无法保证在特征空间中具有低维线性子空间结构。

本文目标是学习一个低秩核映射，它将数据投影到一个高维Hilbert空间，并具有线性子空间的结构。当Hilbert特征空间中存在线性子空间结构时，特征映射[ΦX]应该是低秩的。我们希望得到的Hilbert空间中的数据仍然位于多個线性子空间上，因此，也希望它具有自表示特性。优化目标函数可以表示为如下形式：

其中：[K=KX，X=ΦXTΦX]表示未知的核Gram矩阵;[λ]是一个平衡参数。在这里，最小化[ΦX?]使得[ΦX]是低秩的。在核方法中，通常不知道[ΦX]的显式形式，因此，需要应用“核技巧”。在实际应用中，数据点往往含有噪声，此时可以放宽（3）中的等式约束，使之成为目标中的正则化项，即[ΦX-ΦXZ2F]。该项可以展开为如下形式：

上述目标函数优化的主要障碍在于[ΦX?]，因为该项依赖于[ΦX]。LEE等人[10]通过使用重参数化可以绕过这一障碍，从而得到特征空间中鲁棒秩最小化的闭式解。由于核矩阵[K]是对称半正定的，可以把它分解为[K=BTB]，其中，[B]是一个方阵。得到：

利用[B?]来代替[ΦX?]，则目标函数表示如下：

其中：[ΦXTΦX=BTB];[KG]是给定的正定核矩阵。由于假设数据点离线性子空间不太远，因此，本文中仅利用简单的核函数来定义[KG]，例如多项式核。本算法的主要思想是学习一个核矩阵[K=BTB]，即：（1）学习得到的特征映射是低秩的;（2）学习得到的核矩阵不是任意的，而是接近于一个预定义的核矩阵（如多项式核或高斯RBF核）;（3）特征空间中的数据点仍然形成一个多重线性子空间结构，因此，其在特征空间中具有自表示特性。

3   目标函数优化

由于目标函数中双线性项的存在，上述优化问题是非凸的。近年来，ADMM算法[7]在求解非凸问题特别是双线性问题上得到了广泛的应用，本文采用ADMM算法来求解该优化问题。

为了求解目标函数，引入了一个辅助变量[A]，使得[A=Z]。将式（4）代入式（6），得到如下等价的优化目标函数：

为了利用ADMM算法求解优化问题（7），首先给出其增广拉格朗日方程，表示如下：

其中：[Y1∈RN×N]和[y2∈R1×N]分别是（7）中约束所对应的拉格朗日乘子;[ρ]是拉格朗日增广项的惩罚参数。

通过固定其他参数，ADMM算法利用迭代的方式来更新某一变量，更新规则如下：

（1）固定变量[A，B]，求解变量[Z]

通过求解如下子问题，可以得到[Z]的表达式：

该问题可以利用奇异阈值算子（SVT）进行求解。SVT 算子为[DηX=UηVT]，其中：[X=UVT]为SVD分解;[ηX=sgnx];[maxabsx-η，0]为压缩算子。

（2）固定变量[Z，B]，求解变量[A]

通过求解如下优化问题，得到[A]的表达式：

通过对[A]求导并令其值为零，可以得到[A]的闭式解，表示如下：

其中：[I]是一个单位矩阵。

（3）固定变量[Z，A]，求解变量[B]

[B]通过求解如下优化问题得到：

该优化问题有闭式解表示如下：

4    算法复杂度分析

文中，由于核矩阵[K]是对称半正定的，因此，可以把它分解为[K=BTB]，其中[，B]是一个方阵。我们可以基于矩阵[X]的SVD分解直接得到核矩阵[K]的SVD分解。以线性核[K=XTX]为例，计算[X]的SVD分解[X=UXSXVTX]，时间复杂度为[ONDL]，其中[L=minN，D]。由于[SX]是对角阵，[S2X]以单个元素的方式很容易进行求解，从而直接得到核矩阵[K]的SVD分解[K=UXS2XVTX]。

文中优化算法采用迭代方式进行求解，迭代算法的效率取决于迭代的总次数以及每次迭代的时间复杂度。优化方法每次迭代的计算复杂度，主要开销在于更新变量[Z]，[A]，[B]。对于更新[Z]，可通过SVD分解来进行奇异值收缩，时间复杂度为[OrN2]，其中，[r]是迭代中SVD分解的秩;对于更新[A]，可以预先计算[λ2BTB+ρI+11T-1]的Cholesky分解，复杂度为[O12N3]，则计算[A]的复杂度为[ON2];对于[B]的计算，主要开销在于对核矩阵的SVD分解，时间复杂度为[ONDL]。综上分析，算法每次迭代的复杂度为[ON3+NDL]。

5    实验

通过实验验证本文算法的有效性。对比算法采用LRR[3]、SSC[2]、LRSC[8]和KSSC[4]算法。实验数据集分别采用Hopkins155[9]数据集和扩展的YaleB数据集。

5.1  运动分割实验

Hopkins155是一个标准的运动分割数据集，它由155个具有2个或3个运动的序列组成，如图1所示。这些序列可分为三类：室内棋盘序列（104个序列）、室外交通序列（38个序列）和铰接/非刚性序列（13个序列）。在仿射摄像机模型下，一个运动的轨迹位于一个高达3维的仿射子空间上;因此，可以采用子空間聚类方法来进行运动分割。

实验中，本文提出的KLRR算法参数设置为：[λ1=1];[λ2=10];[λ3=1×105]。另外，使用多项式核[kx1，x2=xT1x2+2.23]来定义[KG]。所有算法独立运行10次，实验结果如表1所示。根据表1，所有算法都取得了很好的结果，但本文提出的算法取得了最低的聚类错误率。需要指出的是：对比SSC算法和KSSC算法，KSSC算法的聚类错误率要更高，这也表示并不是单纯利用核方法就可以提高算法性能。本文提出的基于核的低秩表示KLRR算法，其性能要优于传统LRR算法。

5.2  人脸聚类实验

如图2所示扩展的Yale B数据集[10]由38个人的人脸图像组成，每个人有64张正面人脸图像。这些图像在不同光照条件以及固定姿势下获取，为了方便进行计算，首先对图像进行采样，大小为48×42;然后进行矢量化处理，将每一张图像变为2 016维向量。

为了充分验证算法的有效性，选择不同数目的样本类别（[K]=10、15、20、25、30、35或38）。将样本类别从1到38进行编号，先学习前[K]个类别，再学习后[K]个类别，直到考虑所有样本类别。以[K]=10为例，每次实验选取1-10，2-11，[…]，或者29-38的样本类别，来组成测试数据集[X∈R2  016×640]。

实验中，本文提出的KLRR算法参数设置为：[λ1=1.1×103];[λ2=2×10-2];[λ3=1×105];多项式核[kx1，x2=xT1x2+122]。实验中，将数据标准化为[-1，1]，实验结果如表2所示。从表2可以看出，本文提出的KLRR算法聚类错误率最低，取得了很好的聚类效果。

6    结语

为了更好地处理非线性子空间的聚类问题，本文提出了一种新的低秩核子空间聚类算法。主要思路为：在聚类过程中通过学习得到一个低秩特征映射，以便在特征空间中获得所需要的线性子空间结构。对于目标函数的优化问题，本文给出了有效的基于ADMM算法的求解方案。在运动分割和人脸识别数据集上的实验，也验证了本文算法明显优于基于预定义核子空间聚类方法和线性子空间聚类方法，显示了算法的有效性。在未来的研究中，将进一步探讨算法对于缺失数据的处理，以及在多视图子空间聚类问题中的拓展应用。

参考文献：

[1] VIDAL R. Subspace clustering[J]. Signal Processing Magazine IEEE，2011，28（2）：52-68.

[2] ELHAMIFAR E，VIDAL R. Sparse subspace clustering： algorithm， theory， and applications[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，2012，35（11）：2765-2781.

[3] LIU G，LIN Z，YAN S，et al. Robust recovery of subspace structures by low-rank representation[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，2013，35（1）：171-184.

[4] PATEL V M，VIDAL R. Kernel sparse subspace clustering[C]// IEEE International Conference on Image Processing，2014：2849-2853.

[5] JI P，SALZMANN M，LI H. Shape interaction matrix revisited and robustified： efficient subspace clustering with corrupted and incomplete data[C]// IEEE International Conference on Computer Vision，2015：4687-4695.

[6] SHAWETAYLOR J. Kernel methods for pattern analysis[M]. Cambridge：Cambridge University Press，2004.

[7] LIN Z，CHEN M，MA Y. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[J]. Eprint Arxiv，2010：9.DOI：10.1016/j.jsb.2012.10.010.

[8] VIDAL R，FAVARO P. Low rank subspace clustering （LRSC）[J]. Pattern Recognition Letters，2014，43（1）：47-61.

[9] TRON R，VIDAL R. A benchmark for the comparison of 3-D motion segmentation algorithms[C]// IEEE Conference on Computer Vision & Pattern Recognition，2007：1-8.

[10] LEE K，HO J，KRIEGMAN D J. Acquiring linear subspaces for face recognition under variable lighting[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（5）：684-698.

責任编辑    盛    艳