Abstract:

Spectral relaxation is widely used in traditional subspace clustering and spectral clustering.First,the eigenvector of the Laplacian matrix is calculated.The eigenvector contains negative numbers,and the result of the 2-way clustering can be obtained directly according to the positive and negative of the elements.For multi-way clustering problems,2-way graph partition is applied recursively or the k-means is used in eigenvector space.The assignment of the cluster label is indirect.The instability of clustering results will increase by this post-processing clustering method.For the limitation of spectral relaxation,a subspace clustering algorithm optimized by non-negative Lagrangian relaxation is proposed,which integrates self-representation learning and rank constraints in the objective function.The similarity matrix and membership matrix are solved by non-negative Lagrangian relaxation and the nonnegativity of the membership matrix is maintained.In this way,the membership matrix becomes the cluster posterior probability.When the algorithm converges,the clustering results can be obtained directly by assigning the data object to the cluster with the largest posterior probability.Compared with the existing subspace clustering and spectral clustering methods,the proposed algorithm designs a new optimization rule,which can realize the direct allocation of cluster labels without additional clustering steps.Finally,the convergence of the proposed algorithm is analyzed theoretically.Generous experiments on five benchmark clustering datasets show that the clustering performance of the proposed method is better than that of the recent subspace clustering methods.

Key words: clustering algorithms, self-expression, optimization, non-negative Lagrangian relaxation, subspace clustering