Non‐alternating stochastic K ‐means based on probabilistic representation of solution space

A non‐alternating (NA) form of K ‐means is proposed to improve the performance for the most fundamental, yet highly non‐convex clustering problem. The motivation of this Letter is that the non‐convex nature of K ‐means can be better handled by stochastic optimisation. However, the alternating update of the Lloyd's algorithm prohibits an effective stochastic optimisation. In order to fully realise the idea, a probabilistic representation is provided for the solution space of K ‐means, which leads to a simple yet efficient NA update. Experiments show that the proposed method outperforms the existing variants, especially for large numbers of clusters, with reasonable time complexity.