迭代加权的稀疏子空间聚类

付刚　吴观茂

摘要：文章提出了一种迭代加权的稀疏子空间的聚类算法。通过在数据集的实验，发现迭代加权稀疏子空间聚类算法极大降低了稀疏子空间的聚类算法的错误率，但并不增加算法的计算复杂度。

关键词：迭代；稀疏子空间；聚类

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2015）28-0030-02

1 子空间聚类

在这一节中，文章简要介绍下稀疏子空间聚类算法。在1.2节中文章介绍加权[?1] 最小化框架、所要解决的问题以及解决问题的算法。

1.1 稀疏子空间聚类

在这一节中，文章简要介绍SSC算法。该种算法采用稀疏表示方式，构建了相似图或多个子空间中数据点集聚类的亲和矩阵。

考虑一系列点[Y=[y1，y2，…，yn]]，其中[yi∈?m]，[yi]为原始空间的低维子空间中的第[i]个数据点。SSC算法在这些数据点中寻求自身相似性，这需要通过解决下面的最优化问题：

[minC1 s.t. Y=YC，diag（C）=0] （1）

其中，[C∈?n×n]是数据点集[Y]的稀疏表示矩阵。那么，该稀疏表示矩阵[C]用来把高维空间分割成多个低维子空间。

在SSC算法中，后置处理步骤就是子空间聚类。

SSC是通过解决下面[?1]最小化问题：

[min（C，E，Z） C1+λeE1+λz2Z2F s.t. Y=YC+E+Z，1TC=1T， diag（C）=0.] （2）

其中，变量矩阵[E]表示数据的稀疏外围，变量矩阵[Z]表示数据的噪声或误用。

参数[λe>0]和[λz>0]在目标函数中起着平衡作用。注意到最优目标函数（2）是凸优化变量，因此，可以使用凸程序工具（具体参考[1]）有效解决。

1.2 加权稀疏子空间

在理想情况下，在公式（1）中，对所有的[j∈S1]令[cij=0]。但是对于真实的数据SSC算法可能并不能确定理想的解决方案。我们可以用加权的[?1]最小框架代替[?1]最小框架，这将可能地改善子空间聚类的性能。正如所讨论的，加权矩阵的更新是建立在[PW1]解的前一次迭代上。

下面是我们的加权稀疏子空间框架：

[min（C，E，Z） W⊙C1+λeE1+λz2Z2F s.t. Y=YC+E+Z，1TC=1T， diag（C）=0.] （3）

在仿射的情况下，上面提出的框架可以用下面的描述：

[min（C，E，A） W⊙C1+λeE1+λz2Y-YZ-E2F s.t. AT1=1，A=C-diag（C）.] （4）

其中，[A]是通过在所要优化的变量的硬阈值得到更快的更新值的一个辅助矩阵。将所有的元素设置为一个加权矩阵。因此，上述框架是一个简单的[?1]最小化问题。它是凸的，可以通过凸程序算法（具体见参考文献[2][3]）有效的解决。

2 实验和讨论

对于所有的算法，我们使用它们作者所提供的代码。所有的参数的选择都是在最终平均聚类错误率最低时。使用的是Matlab2014b，Intel（R） Core（TM） i7-4770K CPU 3.50GHz 12GB RAM。

对于Hopkins 155数据集：在LRR算法中，我们使用[λ=4]。在LSR算法中，作者在LSR问题上应用了两种不同的方法，分别为LSR1和LSR2。最好的性能是在[λ=0.0048]（LSR1）和[λ=0.0046]（LSR2）取的。在SMR算法中，我们使用[α=20]。在SSC算法中，我们使用[α=800]。另外，为了数值稳定性，我们使用[ε1=0.001]，[ε2=0.02]。

在我们的试验中，表1显示的是使用原始2F维特征轨迹。表2显示的是通过PCA将2F维投影到4n维子空间，n代表移动物体的数目。在这里，我们使用相同的参数。有如下的结论：

（1） 在2F和4n情况下，所有的算法取得低的平均错误率（低于5%）。但是，相比于已经存在的算法，最近提出的SMR算法和本文中的RSSC算法取得低于1%的错误率。这些结果说明了RSSC算法在运动分割中有很强的稳定性。

（2） 在原始2F原始运动追踪的情况下，使用RSSC算法所得到的2个运动物体聚类错误率从1.53%降到0.64%，3个运动物体聚类错误率从4.4%降到2.01%。对于整个Hopkins 155数据集，SSC算法平均聚类错误率为2.28%，RSSC算法的为0.95%。对于投影到4n维数特征追踪，对两个物体和三个物体分别使用RSSC算法得到的聚类错误率从1.69%和4.38%分别降到0.83%和2.50%。对于整个Hopkins 155数据集平均聚类错误率：SSC算法的为2.29%，RSSC算法的为1.21%。结果表明RSSC算法通过加权迭代[?1]最小比SSC算法性能更优。

参考文献：

[1] Elhamifar E，Vidal R.Sparse subspace clustering： algorithm， theory， and applications[J].IEEE Trans，Pattern Anal. Mach. Intell. 2013，35 （11）：2765–2781.

[2] Boyd S P， Vandenberghe L.Convex Optimization[M].Cambridge University Press，2004.

[3] Boyd S， Parikh N， Chu E.Distributed optimization and statistical learning via the alternating direction method of multipliers， Found. Trends Mach. Learn. 2011，3 （1）：1–122.

[4] Liu G， Lin Z， Yu Y.Robust subspace segmentation by low-rank representation[C].ICML， 2010.