Asymptotics for The k-means

The k-means is one of the most important unsupervised learning techniques in statistics and computer science. The goal is to partition a data set into many clusters, such that observations within clusters are the most homogeneous and observations between clusters are the most heterogeneous. Although it is well known, the investigation of the asymptotic properties is far behind, leading to difficulties in developing more precise k-means methods in practice. To address this issue, a new concept called clustering consistency is proposed. Fundamentally, the proposed clustering consistency is more appropriate than the previous criterion consistency for the clustering methods. Using this concept, a new k-means method is proposed. It is found that the proposed k-means method has lower clustering error rates and is more robust to small clusters and outliers than existing k-means methods. When k is unknown, using the Gap statistics, the proposed method can also identify the number of clusters. This is rarely achieved by existing k-means methods adopted by many software packages.