Finding the Number of Clusters in a Dataset

One of the most difficult problems in cluster analysis is identifying the number of groups in a dataset. Most previously suggested approaches to this problem are either somewhat ad hoc or require parametric assumptions and complicated calculations. In this article we develop a simple, yet powerful nonparametric method for choosing the number of clusters based on distortion, a quantity that measures the average distance, per dimension, between each observation and its closest cluster center. Our technique is computationally efficient and straightforward to implement. We demonstrate empirically its effectiveness, not only for choosing the number of clusters, but also for identifying underlying structure, on a wide range of simulated and real world datasets. In addition, we give a rigorous theoretical justification for the method based on information-theoretic ideas. Specifically, results from the subfield of electrical engineering known as rate distortion theory allow us to describe the behavior of the distortion in both the presence and absence of clustering. Finally, we note that these ideas potentially can be extended to a wide range of other statistical model selection problems.