Sparse K-Means with the l_q(0leq q< 1) Constraint for High-Dimensional Data Clustering

Sparse clustering, which aims at finding a proper partition of extremely high dimensional data set with fewest relevant features, has been attracted more and more attention. Most researches model the problem through minimizing weighted feature contributions subject to a l₁ constraint. However, the l₀ constraint is the essential constraint for sparse modeling while the l₁ constraint is only a convex relaxation of it. In this article, we bridge the gap between the l₀ constraint and the l₁ constraint through development of two new sparse clustering models, which are the sparse k-means with the l_q(0 <; q <; 1) constraint and the sparse k-means with the l₀ constraint. By proving the certain forms of the optimal solution of particular l_q(0 = q <; 1) non-convex optimizations, two efficient iterative algorithms are proposed. We conclude with experiments on both synthetic data and the Allen Developing on both synthetic data and the l_q(0 = q <; 1) models exhibit the advantages compared with the standard k-mans and sparse k-means with the l₁ constraint.