稀疏子空间聚类算法

1、稀疏子空间聚类算法与模型建立稀疏子空间聚类是一种基于谱聚类的子空间聚类方法，基本思想：假设高位空间中的数据本质上属于低维子空间，能够在低维子空间中进行线性表示,能够揭示数据所在的本质子空间, 有利于数据聚类.基本方法是, 对给定的一组数据建立子空间表示模型,寻找数据在低维子空间中的表示系数, 然后根据表示系数矩阵构造相似度矩阵, 最后利用谱聚类方法如规范化割(Normalized cut, Ncut)22 获得数据的聚类结果。基本原理稀疏子空间聚类32 的基本思想是: 将数据 表示为所有其他数据的线性组合, （1） 并对表示系数施加一定的约束使得在一定条件下对所有的, 对应的。将所有数据及其表

2、示系数按一定方式排成矩阵 ，则式（1）等价于 （2）且系数矩阵 满足: 当 和属于不同的子空间时, 有. 不同于用一组基或字典表示数据, 式（2）用数据集本身表示数据, 称为数据的自表示. 若已知数据的子空间结构, 并将数据按类别逐列排放, 则在一定条件下可使系数矩阵具有块对角结构, 即 （3）这里 表示子空间中数据的表示系数矩阵; 反之, 若Z 具有块对角结构, 这种结构揭示了数据的子空间结构. 稀疏子空间聚类就是通过对系数矩阵采用不同的稀疏约束, 使其尽可能具有理想结构, 从而实现子空间聚类.Elhamifar 等32 基于一维稀疏性提出了稀疏子空间聚类(Sparse subspace c

3、lustering,SSC) 方法, 其子空间表示模型为 （4）该模型利用稀疏表示(SR) 迫使每个数据仅用同一子空间中其他数据的线性组合来表示. 在数据所属的子空间相互独立的情况下, 模型(4) 的解具有块对角结构, 这种结构揭示了数据的子空间属性: 块的个数代表子空间个数, 每个块的大小代表对应子空间的维数, 同一个块的数据属于同一子空间. 注意, 模型中的约束 是为了避免平凡解, 即每个数据仅用它自己表示, 从而Z 为单位矩阵的情形.稀疏子空间聚类综述 王卫卫1 李小平1 冯象初1 王斯琪132 Elhamifar E, Vidal R. Sparse subspace clusteri

4、ng. In: Pro-ceedings of the 2009 IEEE Computer Society Conferenceon Computer Vision and Pattern Recognition (CVPR).Miami, FL, USA: IEEE, 2009. 27902797稀疏最优化模型位于线性或仿射子空间集合的高维数据可以稀疏地被同一个子空间的点线性或者仿射表示。通过文献中稀疏表示技巧获得高维数据的稀疏表示。设有个D维数据，处于 空间的n个线性子空间中，子空间的维数分别为，定义一个矩阵Y为： 其中，矩阵。对于每个数据点都可以被一些除它以外的数据点表示，即，其中，该

5、表示是任意的并存在一个最稀疏的形式。为了获得每个数据点的最稀疏的表示，选择最小化其范数对其进行凸松弛处理。稀疏最优化模型为：将已获得的稀疏系数矩阵应用到谱聚类算法中，从而对数据进行聚类，称为稀疏子空间聚类算法。谱聚类算法谱聚类是建立在图谱理论基础上的一种重要的数据聚类方法，首先根据给定的样本数据集建立数据间的相似度矩阵，然后构造加权图，通过寻找图的最优划分实现数据聚类的目的。非正则化Laplacian 正则化Laplacian 其中，D度矩阵为对角矩阵，对角线上的元素为。L对应于划分准则RatioCut【12】，而正则化：Laplacian对应于划分准则Ncut。根据Laplacian矩阵的选

6、择不同，衍生出三个谱聚类算法，一种非正则化谱聚类，两种正则化谱聚类，。谱聚类算法寻求相似加权图的最优划分，要求类间切割权值最小而类内相似权值最大。然而非正则化谱聚类有时不能满足类内相似权值最大这个要求，而正则化谱聚类能够很好的满足这两个条件。因此，正则化谱聚类算法优于非正则化谱聚类算法。一种改进的稀疏子空间聚类算法 欧阳佩佩，赵志刚，刘桂峰（青岛大学信息工程学院，青岛 ，： ，： ，：，（）：，（）：，（）：，（）：以上所述的稀疏子空间聚类模型通常采用交替方向法(Alternating direction method, ADM)74来求解, 需要大量的迭代, 同时复杂度较高。我们选用ADM的改进算法，ADMM（交替方向乘子法）。交替方向乘子法是求解分散式优化问题的方法之一，它收敛性好，鲁棒性强，且不要求子优化模型目标函数严格凸和有限，近年来越来越受关注。其标准形式17如下： ；为凸函数。当 函数在上为凸函数时，算法能收敛到最优解17。需特别注意的是ADMM 不要求函数有限，因此除了可以表示每个子系统的目标函数外，还可以表示每个子系统的等式或不等式约束，这时，当每个子系统约束不越限时， ，否则 。11 Chen CNon-convex economic dispatch：A direc