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.

该论文研究了 $k$-means 算法的能力，正确地恢复互相分离的簇群。基于常见的簇群定义，考虑了簇内同质性和簇间多样性的要求，并找到了一种特殊情况的互相分离簇群，使得 $k$-means 的代价函数全局最小值与互相分离性一致。通过实验发现各种 $k$-means 品牌实际上无法发现互相分离的簇群，因此提出了一种新的算法，通过重复子抽样选择种子的方式，对 $k$-means++ 进行变体改进，并在任务中胜过 $k$-means 系列中的其他四种算法。