稀疏子空间聚类算法

稀疏子空间聚类算法与模型建立稀疏子空间聚类是一种基于谱聚类的子空间聚类方法，基本思想：假设高位空间中的数据本质上属于低维子空间，能够在低维子空间中进行线性表示,能够揭示数据所在的本质子空间,有利于数据聚类.基本方法是,对给定的一组数据建立子空间表示模型,寻找数据在低维子空间中的表示系数,然后根据表示系数矩阵构造相似度矩阵,最后利用谱聚类方法如规范化割(Normalizedcut,Ncut)[22]获得数据的聚类结果。基本原理稀疏子空间聚类[32]的基本思想是:将数据Sxi表示为所有其他数据的线性组合,jijijixZx（1）并对表示系数施加一定的约束使得在一定条件下对所有的Sxj,对应的0ijZ。将所有数据及其表示系数按一定方式排成矩阵，则式（1）等价于XZX（2）且系数矩阵NNRZ满足:当ix和jx属于不同的子空间时,有0ijZ.不同于用一组基或字典表示数据,式（2）用数据集本身表示数据,称为数据的自表示.若已知数据的子空间结构,并将数据按类别逐列排放,则在一定条件下可使系数矩阵Z具有块对角结构,即kZZZZ00000021（3）这里),,1(kZ表示子空间S中数据的表示系数矩阵;反之,若Z具有块对角结构,这种结构揭示了数据的子空间结构.稀疏子空间聚类就是通过对系数矩阵Z采用不同的稀疏约束,使其尽可能具有理想结构,从而实现子空间聚类.Elhamifar等[32]基于一维稀疏性提出了稀疏子空间聚类(Sparsesubspaceclustering,SSC)方法,其子空间表示模型为1minZZ0,..iiZXZXts（4）该模型利用稀疏表示(SR)迫使每个数据仅用同一子空间中其他数据的线性组合来表示.在数据所属的子空间相互独立的情况下,模型(4)的解Z具有块对角结构,这种结构揭示了数据的子空间属性:块的个数代表子空间个数,每个块的大小代表对应子空间的维数,同一个块的数据属于同一子空间.注意,模型中的约束0iiZ是为了避免平凡解,即每个数据仅用它自己表示,从而Z为单位矩阵的情形.稀疏子空间聚类综述王卫卫1李小平1冯象初1王斯琪132ElhamifarE,VidalR.Sparsesubspaceclustering.In:Pro-ceedingsofthe2009IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition(CVPR).Miami,FL,USA:IEEE,2009.2790¡2797稀疏最优化模型位于线性或仿射子空间集合的高维数据可以稀疏地被同一个子空间的点线性或者仿射表示。通过文献［９］中稀疏表示技巧获得高维数据的稀疏表示。设有N个D维数据Niiy1，处于DR空间的n个线性子空间nllS1中，子空间的维数分别为nlld1，定义一个矩阵Y为：][][11nNYYyyY其中，lNMRY矩阵。对于每个数据点都可以被一些除它以外的数据点表示，即0,ciiciiYy，其中NNNiRcccC][21，该表示是任意的并存在一个最稀疏的形式。为了获得每个数据点的最稀疏的表示，选择最小化其0l范数对其进行凸松弛处理。稀疏最优化模型为：0)(,..min1CdiagYCYtsC将已获得的稀疏系数矩阵Ｃ应用到谱聚类算法中，从而对数据进行聚类，称为稀疏子空间聚类算法。谱聚类算法谱聚类［１１］是建立在图谱理论基础上的一种重要的数据聚类方法，首先根据给定的样本数据集建立数据间的相似度矩阵，然后构造加权图，通过寻找图的最优划分实现数据聚类的目的。非正则化LaplacianWDL正则化Laplacian2/12/12/12/1:WDDILDDLxymWDILDLrw11:其中，D度矩阵为对角矩阵，对角线上的元素为njijnwddd121,,,。L对应于划分准则RatioCut【12】，而正则化：Laplacian对应于划分准则Ncut［１２］。根据Laplacian矩阵的选择不同［１２］，衍生出三个谱聚类算法，一种非正则化谱聚类，两种正则化谱聚类［６，１３］。谱聚类算法寻求相似加权图的最优划分，要求类间切割权值最小而类内相似权值最大。然而非正则化谱聚类有时不能满足类内相似权值最大这个要求，而正则化谱聚类能够很好的满足这两个条件。因此，正则化谱聚类算法优于非正则化谱聚类算法。一种改进的稀疏子空间聚类算法欧阳佩佩，赵志刚，刘桂峰（青岛大学信息工程学院，青岛２６６０７１［６］ＮｇＡ，ＷｅｉｓｓＹ，Ｊｏｒｄａｎ．Ｏｎｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇ：ａｎａｌｙｓｉｓａｎｄａｎａｌｇｏｒｉｔｈｍ［Ｊ］．ＮｅｕｒａｌＩｎｆｏｒｍａｔｉｏｎＰｒｏｃｅｓｓｉｎｇＳｙｓｔｅｍｓ，２００１：８４９－８５６．［９］ＥｌｈａｍｉｆａｒＥ，ＶｉｄａｌＲ．Ｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇ：Ａｌｇｏｒｉｔｈｍ，ｔｈｅｏｒｙ，ａｎｄａｐｐｌｉｃａｔｉｏｎｓ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅＩｎｔｅｌｌｉｇｅｎｃｅ，２０１３，３５（１１）：２７６５－２７８１．［１１］ｖｏｎＬｕｘｂｕｒｇＵ，Ａｔｕｔｏｒｉａｌｏｎｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇ［Ｊ］．ＳｔａｔｉｓｔｉｃｓａｎｄＣｏｍｐｕｔｉｎｇ，２００７，１７（４）：３９５－４１６．［１２］ＢｏｙｄＳ，ＰａｒｉｋｈＮ，ＣｈｕＥ，ｅｔａｌ．Ｄｉｓｔｒｉｂｕｔｅｄｏｐｔｉｍｉｚａｔｉｏｎａｎｄｓｔａｔｉｓｔｉｃａｌｌｅａｒｎｉｎｇｖｉａｔｈｅａｌｔｅｒｎａｔｉｎｇｄｉｒｅｃｔｉｏｎｍｅｔｈｏｄｏｆｍｕｌｔｉｐｌｉｅｒｓ［Ｊ］．ＦｏｕｎｄａｔｉｏｎｓａｎｄＴｒｅｎｄｓｉｎＭａｃｈｉｎｅＬｅａｒｎｉｎｇ，２０１０，３（１）：１－１２２．［１３］ＳｈｉＪ，ＭａｌｉｋＪ．Ｎｏｒｍａｌｉｚｅｄｃｕｔｓａｎｄｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ［Ｊ］．ＩＥＥＥＴｒａｎｓ．ｏｎＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅＩｎｔｅｌｌｉｇｅｎｃｅ，２０００，２（８）：８８８－９０５．以上所述的稀疏子空间聚类模型通常采用交替方向法(Alternatingdirectionmethod,ADM)[74]来求解,需要大量的迭代,同时复杂度较高。我们选用ADM的改进算法，ADMM（交替方向乘子法）。交替方向乘子法是求解分散式优化问题的方法之一，它收敛性好，鲁棒性强，且不要求子优化模型目标函数严格凸和有限，近年来越来越受关注。其标准形式[17]如下：cBzAxtszgxf..)()(minpmpnpmnRcRBRARzRx;;;;；gf,为凸函数。当gf,函数在RRn上为凸函数时，算法能收敛到最优解[17]。需特别注意的是ADMM不要求gf,函数有限，因此gf,除了可以表示每个子系统的目标函数外，还可以表示每个子系统的等式或不等式约束，这时，当每个子系统约束不越限时，0,0gf，否则gf,。[11]ChenC．Non-convexeconomicdispatch：Adirectsearchapproach[J]．EnergyConversionandManagement，2007，48(1)：219-225．基于交替方向乘子法的动态经济调度分散式优化李佩杰，陆镛，白晓清，韦化求解：