Penalized K-Means Clustering: Another Look at Its Statistical Properties

Unsupervised learning is a major class of machine learning techniques where response information is missing or unavailable. Among these techniques, clustering plays a central role by grouping objects based on a chosen similarity measure. K-Means is one of the most established and widely used clustering methods, known for its simplicity and computational efficiency. For continuous data, K-Means performs well when the number of clusters <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>K</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> is known and correctly specified. However, it faces convergence and overfitting challenges when <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>K</mml:mi> </mml:math> is unknown. These issues stem from K-Means’ objective function, which monotonically decreases as the number of clusters increases—leading to a tendency to overfit. In this article, we propose an augmented K-Means algorithm that introduces a penalized version of the standard K-Means objective, designed to guard against overfitting and promote model parsimony when <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>K</mml:mi> </mml:math> is unknown. We establish key optimality properties of both the traditional K-Means loss function and the proposed penalty term. Extensive simulation studies on benchmark datasets demonstrate the improved performance of the proposed method, including accurate identification of the true number of clusters. Extensive simulation studies on benchmark datasets demonstrate the improved performance of the proposed method, including accurate identification of the true number of clusters. Additionally, we apply our approach to the clustering of globular galaxy datasets—an example of truly large-scale (“Big”) data—to further illustrate its effectiveness.