Scalable KMeans++论文解析

KMeans最大的优点是简单，随机初始化一些类中心，重复的将数据划分到最近的中心点中，然后更新中心点。这种局部搜索的方式称为Lloyd's algorithm[[1]][1] [1]: https://en.wikipedia.org/wiki/Lloyd%27s_algorithm 。即使在大规模数据下，K-Means也很受欢迎，如mahout中的KMeans方法。从理论上来看，K-Means在效率和质量上并不是一个好的聚类方法：在最坏的情况下，其运行时间是指数级的；即便最终的方案是局部最优的，它也未必是全局最优的。但是在实际中，由于简洁性和速度无可比拟，K-Means方法很受欢迎。因此，很多工作都关注选择初始类中心点来提高算法的优点。

这个领域里面一个重要的工作是Ostrovsky等人证明一个简单的程序就可以从理论上保证结果的质量，借助于好的初始类中心点可以提高Lloyd局部搜索的质量。K-Means++只在最初的时候随机公平的选择初始点。接下来的中心点则根据它们对错误的贡献程度来选择。直觉上来说，初始化算法发现一个好的聚类应该是相对扩散的，因此选择一个新的聚类中心应该是与之前选择的类中心相对较远。正式地，我们可以发现K-Means++大约与最优的O(log k)接近，或者是当我们知道数据是具有很好的簇特征的时候，它接近一个常量。

但是K-Means++初始化的缺点是它的序列特征。尽管在$R^d$空间中，寻找n个点的k个类别，其总的运行时间是O(nkd)，它与一次Lloyd迭代一样。哪一个点被选中为第i次迭代的中心点主要依赖于上次迭代的中心点。一个简单实现K-Means++的方式为了实现初始的中心点，需要在数据中传递k次。

这个情况在大规模数据场景下更为严重。首先随着数据的增长，每个类别下的数据增长很快。例如将数百万个点分到100个或者1000个类下是很常见的情况，但是K-Means++在这种情况下初始化会非常慢。在并行化处理（如MapReduce）这种数据的时候其缺点会更加明显。