Learning the $k$ in $k$-means via the Camp-Meidell Inequality

摘要

Determining $k$, the number clusters, is a key challenge in $k$-means clustering. We propose an approach, named Automatic $k$-means ($k$-means-auto), which judges a $k$ value to be right, if at least 88.89% of $pmb{D}$ is less than twice its standard deviation, where $pmb{D}$ is a vector of length $pmb{N}$ (number of points) comprising the distance of each point to its cluster centroid. The bound is derived from Camp-Meidell's inequality for unimodal and symmetrical distributions. First in this paper, we show that $k$-means' equal-variance Gaussian cluster assumption induces Gaussian fit for $pmb{D}$. Thus, if $pmb{D}$ is Gaussian, then all clusters are Gaussian, and the underlying $k$ value is appropriate. We chose to test $pmb{D}$ for unimodality and symmetry instead of Gaussian fit, as a means of relaxation, since clusters in real data are hardly perfectly Gaussian. The proposed approach is fast since $pmb{D}$ does not have to be computed afresh: it is already available as a by-product of the clustering process. On 10 well-known datasets, $k$-means-auto finds the true $pmb{k}$ in 6 cases and comes very close ($pm 1$ cluster) in 3 other cases. Compared with two well-known methods, gap statistics and silhouette, it outperforms the former and competes closely (statistically insignificant difference at 95% confidence) with the latter. Over all the cases, the running time range for $k$-means-auto, gap and silhouette are 0.02s-0.44s (factor of 22), 0.31s-13.63s (factor of 108) and 0.02s-70.78s (factor of 3539) respectively. Thus, $k$-means-auto surpasses the other two methods in efficiency.