基于 AFK-MC²算法的 k-Means 聚类加速算法

Olivier Bachem 等人在其 NIPS 2016 （Neural Information Processing Systems，神经信息处理系统大会，机器学习领域的顶级会议之一）的文章“Fast and Probably Good Seedings for k-Means”中提出了AFK-MC²算法，该算法改进了 k-Means 算法中初始种子点的生成方式，使其聚类速度相较于目前最好的 k-Means++ 方式提高了好几个数量级。

k-Means 聚类算法可以对数据点或一些不知道标签但总类别数（比如总共有 K 个类别）比较明确的一些观测值进行聚类。其目的是使用一些相似性度量（比如欧式距离）来将数据聚集到 K 个类别。这种算法通常被称为 Lloyd 算法，该算法的核心包括需要找出每个类别的聚类中心，使得同一个类别中的数据点到聚类中心的距离最小。

与其他非凸优化算法一样，Lloyd 算法可能收敛到一个局部最小值。为了提高解的质量，该算法通过被称为种子点的初始聚类中心来启动。随机种子点可以很快得到，但是使用随机种子点算法很难得到最优解。

k-Means++ 通过对数据点做一个自适应采样来改进种子点的产生方式。首先选择一个随机的数据点作为初始种子点，然后计算所有的数据点到最近种子点的距离（第一次迭代中只有初始种子点），下一个种子点随机地在所有的数据点中选择，而每个数据点被选中的概率与前面计算的距离的平方相关。

k-Means++ 的缺点在于其很难推广到数据量比较大的数据集，因为在寻找种子点的过程中，Lloyd 算法的每一次迭代都需要计算相应的聚类中心和所有数据点之间的距离。

而本文介绍的 AFK-MC²算法被认为是一种简单但快速的 k-Means 选取种子点的替代算法，可以在不需要假定数据分布的情况下得到比较好的聚类结果。

这种方法的关键之处在于它使用马尔科夫链对k-Means++ 进行近似处理，也就是将数据点看做状态点。第一个状态是随机采样的数据点，通过一个随机过程来决定链的状态是否要转移到其他的随机数据点。状态是否转移与所有点的初始距离是相互独立的（马尔科夫链的稳定状态与初始状态无关），并且初始距离作为预处理的一部分只计算一次。与k-Means++ 不同的是，AFK-MC²算法只需要遍历一次数据集。

在足够的条件下，AFK-MC²和k-Means++ 可以达到相同的稳定状态。结果表明，对于大数据集，在0 到1% 的相对误差下，AFK-MC²算法要比k-Means++ 快200 到1000 倍。

目前 Github 上已经有基于 Cython 的 AFK-MC²算法的实现，还有一些与 scikit-learn 配合使用的示例。

查看英文原文： AFK-MC² Algorithm Speeds up k-Means Clustering Algorithm Seeding

感谢薛命灯对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作，请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博（ @InfoQ ， @丁晓昀），微信（微信号： InfoQChina ）关注我们。