如何用AI技术降噪? QCon 广州“音视频架构实践”专场给你答案! 了解详情
写点什么

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

  • 2016 年 12 月 29 日
  • 本文字数:1096 字

    阅读完需:约 4 分钟

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

2016 年 12 月 29 日 18:002199

评论

发布
暂无评论
发现更多内容

互联网架构演化

张荣召

架构师训练营—第四周学习总结

Geek_shu1988

微服务

qh12346

作业二:第四周学习总结

静海

架构师训练营第四周作业

睡觉表演者

极客大学架构师训练营

架构师训练营 - 作业 - 第四周

Max2012

第四周-系统架构-总结

刘希文

架构师训练营第四周作业

xs-geek

极客大学架构师训练营

架构师训练营第 1 期第 4 周学习总结

du tiezheng

极客大学架构师训练营

作业一:典型的大型互联网应用系统使用了哪些技术方案和手段,主要解决什么问题?请列举描述。

静海

第四周心得

睡觉表演者

极客大学架构师训练营

架构师训练营第 1 期第 4 周作业

郑凯元

极客大学架构师训练营

区块链行业发展的“忧与愁”

CECBC

区块链 互联网

“链”接技术与应用:区块链的新命题,大命题

CECBC

区块链 数字货币

深入理解JVM垃圾回收算法 - 复制算法

CHEN川

深入理解JVM GC复制算法 Cheney

架构师训练营—第四周作业

Geek_shu1988

第四周作业总结

Geek_ce484f

极客大学架构师训练营

架构师训练营第四周总结

xs-geek

极客大学架构师训练营

架构师训练营第4周课后练习

叶纪想

极客大学架构师训练营

周练习 4

何毅曦

维基百科技术架构

张荣召

架构师训练营第四周 -- 学习总结

张荣召

spring-boot笔记

solike

一个典型的大型互联网应用系统使用了哪些技术方案和手段,主要解决什么问题?

Jacky.Chen

架构师训练营第 1 期 -- 第四周作业

发酵的死神

极客大学架构师训练营

如何组织一场用户故事地图工作坊

Bruce Talk

敏捷 用户故事 Product Owner 用户故事地图

架构模式

张荣召

一个典型的大型互联网应用系统使用了哪些技术方案和手段,主要解决什么问题?

A p7+

一个典型的大型互联网应用系统使用了哪些技术方案和手段,主要解决什么问题?(总结)

orchid9

系统架构:系统技术挑战与方案

张荣召

第四周作业

Geek_ce484f

极客大学架构师训练营

「云智公开课」百度沧海·存储

「云智公开课」百度沧海·存储

基于AFK-MC²算法的k-Means聚类加速算法_语言 & 开发_Alexandre Rodrigues_InfoQ精选文章