K-means、K-medoide中心算法

                                                                                         个人博客：www.xiaobeigua.icu

(1)K值均步骤：

1. 从N个数据文档随机选取K个数据文档作为质心。
2. 对剩余的每个数据文档测量其到每个质心的距离，并把它归到最近的质心的类.
3. 重新计算已经得到的各个类的质心。
4. 迭代二、三步直至新的质心与原质心相等或小于指定阈值，算法结束。

     优点：（1）KMeans算法擅长处理球状分布的数据

1. 简单，容易掌握

     缺点：（1）k的取值需要根据经验，没有可借鉴性

1. 对异常偏离的数据非常敏感

例题：

我搞了6个点，从图上看应该分成两推儿，前三个点一堆儿，后三个点是另一堆儿。

现在手工执行K-Means，体会一下过程，同时看看结果是不是和预期一致。

1.选择初始大哥： 我们就选P1和P2

2.计算小弟和大哥的距离： P3到P1的距离从图上也能看出来（勾股定理），是√10 = 3.16；P3到P2的距离√((3-1)^2+(1-2)^2 = √5 = 2.24，所以P3离P2更近，P3就跟P2混。同理，P4、P5、P6也这么算，如下：

 P3到P6都跟P2更近，所以第一次站队的结果是：

组A：P1

组B：P2、P3、P4、P5、P6

3.人民代表大会： 组A没啥可选的，大哥还是P1自己 组B有五个人，需要选新大哥，这里要注意选大哥的方法是每个人X坐标的平均值和Y坐标的平均值组成的新的点，为新大哥，也就是说这个大哥是“虚拟的”。

因此，B组选出新大哥的坐标为：P哥（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）。 综合两组，新大哥为P1（0，0），P哥（6.2，5.6），而P2-P6重新成为小弟

4.再次计算小弟到大哥的距离：

 这时可以看到P2、P3离P1更近，P4、P5、P6离P哥更近，所以第二次站队的结果是：

组A：P1、P2、P3

组B：P4、P5、P6（虚拟大哥这时候消失）

5.第二届人民代表大会： 按照上一届大会的方法选出两个新的虚拟大哥：P哥1（1.33，1） P哥2（9，8.33），P1-P6都成为小弟

6.第三次计算小弟到大哥的距离：

这时可以看到P1、P2、P3离P哥1更近，P4、P5、P6离P哥2更近，所以第二次站队的结果是：

组A：P1、P2、P3

组B：P4、P5、P6

我们发现，这次站队的结果和上次没有任何变化了，说明已经收敛，聚类结束，聚类结果和我们最开始设想的结果完全一致。

(2)K中心点算法：

K-中心点算法也是一种常用的聚类算法，K-中心点聚类的基本思想和K-Means的思想相同，实质上是对K-means算法的优化和改进。在K-means中，异常数据对其的算法过程会有较大的影响。在K-means算法执行过程中，可以通过随机的方式选择初始质心，也只有初始时通过随机方式产生的质心才是实际需要聚簇集合的中心点，而后面通过不断迭代产生的新的质心很可能并不是在聚簇中的点。如果某些异常点距离质心相对较大时，很可能导致重新计算得到的质心偏离了聚簇的真实中心。

算法步骤：

（1）确定聚类的个数K。

（2）在所有数据集合中选择K个点作为各个聚簇的中心点。

（3）计算其余所有点到K个中心点的距离，并把每个点到K个中心点最短的聚簇作为自己所属的聚簇。

（4）在每个聚簇中按照顺序依次选取点，计算该点到当前聚簇中所有点距离之和，最终距离之后最小的点，则视为新的中心点。

（5）重复（2），（3）步骤，直到各个聚簇的中心点不再改变。

如果以样本数据{A,B,C,D,E,F}为例，期望聚类的K值为2，则步骤如下：

（1）在样本数据中随机选择B、E作为中心点。

（2）如果通过计算得到D,F到B的距离最近，A,C到E的距离最近，则B,D,F为聚簇C1，A,C,E为聚簇C2。

（3）在C1和C2两个聚类集合中，计算一个点到其他店的距离之和的最小值作为新的中心点，假如分别计算出D到C1中其他所有点的距离之和最小，E到C2中其他所有点的距离之和最小。

（4）再以D,E作为聚簇的中心点，重复上述步骤，知道中心点不再改变。

优缺点：

  K-中心聚类算法计算的是某点到其它所有点的距离之后最小的点，通过距离之和最短的计算方式可以减少某些孤立数据对聚类过程的影响。从而使得最终效果更接近真实划分，但是由于上述过程的计算量会相对杜宇K-means，大约增加O（n）的计算量，因此一般情况下K-中心算法更加适合小规模数据运算。