Probabilistic K-means Clustering via Nonlinear Programming

Abstract--K-means is a classical clustering algorithm with wide applications. However, soft K-means, or fuzzy c-means at m 1, remains unsolved since 1981. T o address this challenging open problem, we propose a novel clustering model, i.e. Probabilistic K-Means (PKM), which is also a nonlinear programming model constrained on linear equalities and linear inequalities. In theory, we can solve the model by active gradient projection, while inefficiently . Thus, we further propose maximum-step active gradient projection and fast maximum-step active gradient projection to solve it more efficiently . By experiments, we evaluate the performance of PKM and how well the proposed methods solve it in five aspects: initialization robustness, clustering performance, descending stability, iteration number, and convergence speed. It has been widely used in image and video processing [1] - [4], speech processing [5], biology [6], medicine [7], sociology [8], and so on.