基于随机分块的稀疏子空间聚类方法

Sparse subspace clustering method based on random blocking

针对稀疏子空间聚类(SSC)方法聚类误差大的问题,提出了基于随机分块的SSC方法。首先,将原问题数据集随机分成几个子集,构建几个子问题;然后,采用交替方向乘子法(ADMM)分别求得几个子问题的系数矩阵,之后将几个系数矩阵扩充成与原问题一样大小的系数矩阵,并整合成一个系数矩阵;最后,根据整合得到的系数矩阵计算得到一个相似矩阵,并采用谱聚类(SC)算法获得原问题的聚类结果。相较于稀疏子空间聚类(SSC)、随机稀疏子空间聚类(S3COMP-C)、基于正交匹配追踪的稀疏子空间聚类(SSCOMP)、谱聚类(SC)和K均值(K-Means)算法中的最优算法,基于随机分块的SSC方法将子空间聚类误差平均降低了3.12个百分点,且其互信息、兰德指数和熵3个性能指标都明显优于对比算法。实验结果表明基于随机分块的SSC方法能降低子空间聚类误差,改善聚类性能。

Aiming at the problem of big clustering error of the Sparse Subspace Clustering(SSC)methods,an SSC method based on random blocking was proposed.First,the original problem dataset was divided into several subsets randomly to construct several sub-problems.Then,after obtaining the coefficient matrices of several sub-problems by the sparse subspace Alternating Direction Method of Multipliers(ADMM)respectively,these coefficient matrices were expanded into coefficient matrices of the same size as the original problem and integrated into a coefficient matrix.Finally,a similarity matrix was calculated according to the coefficient matrix obtained by the integration,and the clustering result of the original problem was obtained by using the Spectral Clustering(SC)algorithm.The SSC method based on random blocking has the subspace clustering error reduced by 3.12 percentage points on average compared with the optional algorithm among SSC,Stochastic Sparse Subspace Clustering via Orthogonal Matching Pursuit with Consensus(S3COMP-C),scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit(SSCOMP),SC and K-Means algorithms,and has all the mutual information,Rand index and entropy significantly better than comparison algorithms.Experimental results show that the SSC method based on random blocking can significantly reduce subspace clustering error,and improve the clustering performance.