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

　　OlivierBachem等人在其NIPS2016（NeuralInformationProcessingSystems，神经信息处理系统大会，机器学习领域的顶级会议之一）的文章“FastandProbablyGoodSeedingsfork-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配合使用的示例。

　　Python培训，就选光环大数据Python培训机构！python学习地址：http://hadoop.aura.cn/python/

大数据培训、人工智能培训、Python培训、大数据培训机构、大数据培训班、数据分析培训、大数据可视化培训，就选光环大数据！光环大数据，聘请专业的大数据领域知名讲师，确保教学的整体质量与教学水准。讲师团及时掌握时代潮流技术，将前沿技能融入教学中，确保学生所学知识顺应时代所需。通过深入浅出、通俗易懂的教学方式，指导学生更快的掌握技能知识，成就上万个高薪就业学子。 更多问题咨询，欢迎点击------>>>>在线客服！