聚类算法-kmeans

简介

k-means应该是最简单的一个聚类算法了，它的优化目标是使所有数据点到它们各自的最近类别中心的距离总和最小。其实k-means是基于质心的聚类，它假设类别的形状是球形的，并通过EM的方法进行求解。它的缺点是对噪声敏感，无法发现任意形状的类别，不稳定。

优化目标：

算法过程

1. 首先随机选出k个数据作为类别中心
2. 然后将其他数据分配到距离他们最近的类别中
3. 将类别中心更新为所有这个类别中的数据的均值
4. 迭代2和3，直至算法稳定

k-means++

由于k-means受初始中心的影响严重，而随机选择很可能使得中心分布不均匀。k-means++的想法就是通过控制生成初始中心的过程来使得中心分布均匀，具体为顺序选择初始中心，使得新选择的中心距离已有的中心尽可能地远。初始中心的过程如下：

1. 首先随机选择一个中心
2. 然后计算其他数据点到已有中心的最近距离记为D(x)

3. 按照按照概率从数据点中选取下一个中心，每个数据点被选取的概率＝

   
   
4. 迭代2和3直至选出k个中心

参考文献

1. k-means++: The Advantages of Careful Seeding