Are Easy Data Easy (for K-Means)
Mieczysław A. Kłopotek
This paper investigates the capability of correctly recovering well-separated
clusters by various brands of the $k$-means algorithm. The concept of
well-separatedness used here is derived directly from the common definition of
clusters, which imposes an interplay between the requirements of
within-cluster-homogenicity and between-clusters-diversity. Conditions are
derived for a special case of well-separated clusters such that the global
minimum of $k$-means cost function coincides with the well-separatedness. An
experimental investigation is performed to find out whether or no various
brands of $k$-means are actually capable of discovering well separated
clusters. It turns out that they are not. A new algorithm is proposed that is a
variation of $k$-means++ via repeated {sub}sampling when choosing a seed. The
new algorithm outperforms four other algorithms from $k$-means family on the
task.