Learning the $k$ in $k$-means via the Camp-Meidell Inequality
Peter Olukanmi, Fulufhelo Vincent Nelwamondo, Tshilidzi Marwala · 2019
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 \pmbD is less than twice its standard deviation, where \pmbD is a vector of length \pmbN (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 \pmbD. Thus, if \pmbD is Gaussian, then all clusters are Gaussian, and the underlying k value is appropriate. We chose to test \pmbD 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 \pmbD 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 \pmbk in 6 cases and comes very close ( ±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.