BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

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

| 作者 Alexandre Rodrigues 关注 1 他的粉丝 ,译者 尚剑 关注 2 他的粉丝 发布于 2016年12月30日. 估计阅读时间: 3 分钟 | AICon 关注机器学习、计算机视觉、NLP、自动驾驶等20+AI热点技术和最新落地成功案例。

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)关注我们。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

深度内容

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT