Kmeans

参考：http://blog.csdn.net/sb19931201/article/details/53586468

http://blog.csdn.net/angelahhj/article/details/41038955

http://blog.csdn.net/loadstar_kun/article/details/39450615

http://blog.csdn.net/tianwaikai/article/details/40898683

EM算法用于寻找隐藏参数的最大似然估计。该算法首先在E step中计算隐藏参数的似然估计，然后再M step中进行最大化，然后进行EM step的迭代直至收敛。应用场景之一是聚类问题，但EM算法本身并不是一个聚类算法。EM算法往往给出的是局部最佳解而非全局最佳解，EM算法对参数初始值敏感，不同的初始值可能得到不同的结果。

EM的算法流程如下：

初始化分布参数

重复直到收敛：

E步骤：用分布参数计算每个实例的聚类概率。（即每个实例属于不同聚类的概率）

M步骤：重新估计分布参数，以使得数据的似然性最大

机器学习数据聚类领域k-means算法也是EM算法思想的一种体现，知道聚类的中心值后，就知道每个点属于哪个类；知道每个点属于哪个类后，又重新纠正聚类中心点的位置。不同的初始聚类中心可能导致完全不同的聚类结果。

数学模型：最终得到的分类结果

模型参数：隐变量--聚类的中心（值）以及每一个点和每一个类别的隶属关系。

目标函数：同一类中不同点到中心的平均距离d较近，不同类之间的平均距离D较远

因此每一次迭代都要最大化D和-d(即最小化d)，这个就是整个过程的最大化目标函数。

K-Means随机挑选K个点作为起始的中心。  （1）首先计算所有点到这K个聚类中心的距离，并将这些点归到最近的一个类中。  （2）根据归类结果重新计算每一类的中心（比如计算该类别所有样本点的均值）。  这样新的聚类中心与原先的相比就会有一个位移，重复上述步骤直到新的聚类中心与旧的聚类中心的偏移非常小，即过程收敛。

Kmeans算法的缺陷

聚类中心的个数K 需要事先给定，但在实际中这个 K 值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适Kmeans需要人为地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。（可以使用Kmeans++算法来解决） K值的确定： 给定一个合适的类簇指标，比如平均半径或直径，只要我们假设的类簇的数目等于或者高于真实的类簇的数目时，该指标上升会很缓慢，而一旦试图得到少于真实数目的类簇时，该指标会急剧上升。即找拐点。

下图是当K的取值从2到9时，聚类效果和类簇指标的效果图：

  左图是K取值从2到7时的聚类效果，右图是K取值从2到9时的类簇指标的变化曲线，此处我选择类簇指标是K个类簇的平均质心距离的加权平均值。从上图中可以明显看到，当K取值5时，类簇指标的下降趋势最快，所以K的正确取值应该是5.为以下是具体数据：

1 2 个聚类 2 所有类簇的半径的加权平均值 8.51916676443 3 所有类簇的平均质心距离的加权平均值 4.82716260322 4 3 个聚类 5 所有类簇的半径的加权平均值 7.58444829472 6 所有类簇的平均质心距离的加权平均值 3.37661824845 7 4 个聚类 8 所有类簇的半径的加权平均值 5.65489660064 9 所有类簇的平均质心距离的加权平均值 2.22135360453 10 5 个聚类 11 所有类簇的半径的加权平均值 3.67478798553 12 所有类簇的平均质心距离的加权平均值 1.25657641195 13 6 个聚类 14 所有类簇的半径的加权平均值 3.44686996398 15 所有类簇的平均质心距离的加权平均值 1.20944264145 16 7 个聚类 17 所有类簇的半径的加权平均值 3.3036641135 18 所有类簇的平均质心距离的加权平均值 1.16653919186 19 8 个聚类 20 所有类簇的半径的加权平均值 3.30268530308 21 所有类簇的平均质心距离的加权平均值 1.11361639906 22 9 个聚类 23 所有类簇的半径的加权平均值 3.17924400582 24 所有类簇的平均质心距离的加权平均值 1.07431888569 初始聚类中心的确定 针对上述第2个缺陷，可以使用Kmeans++算法来解决

K-Means ++ 算法

 k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。

从输入的数据点集合中随机选择一个点作为第一个聚类中心对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大重复2和3直到k个聚类中心被选出来利用这k个初始的聚类中心来运行标准的k-means算法  从上面的算法描述上可以看到，算法的关键是第3步，如何将D(x)反映到点被选择的概率上，一种算法如下： 先从我们的数据库随机挑个随机点当“种子点”对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。重复2和3直到k个聚类中心被选出来利用这k个初始的聚类中心来运行标准的k-means算法

可以看到算法的第三步选取新中心的方法，这样就能保证距离D(x)较大的点，会被选出来作为聚类中心了。至于为什么原因比较简单，如下图 所示：  

                                                

      假设A、B、C、D的D(x)如上图所示，当算法取值Sum(D(x))*random时，该值会以较大的概率落入D(x)较大的区间内，所以对应的点会以较大的概率被选中作为新的聚类中心。