K均值算法（K-Means）

博客CSDN：深入浅出K-Means算法
博客：机器学习算法-K-means聚类
分布式：MapReduce实现
并行化：kmeans算法并行化的mpi程序

1. K-Means算法步骤

算法步骤

收敛性定义，畸变函数（distortion function）：

伪代码：

1) 创建k个点作为K个簇的起始质心（经常随机选择）
2) 当任意一个点的蔟分配结果发生变化时（初始化为True）
    对数据集中的每个数据点，重新分配质心
        对每个质心
            计算质心到数据点之间的距离
        将数据点分配到距其最近的蔟
    对每个蔟，计算蔟中所有点的均值并将均值作为新的质心

缺点：

1. 需要提前确定K值；
2. 对异常值敏感；
3. 对初始聚类中心敏感；

优点：

1. 易解释；
2. 运行速度快；
3. 一般效果不错；

2. K-Means改进

2.1 K-Mediods

每次选取中值作为聚类中心，排除异常值的影响；

2.2 K-Means++算法

K-Means主要有两个最重大的缺陷——都和初始值有关：

• K是事先给定的，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。（ISODATA算法通过类的自动合并和分裂，得到较为合理的类型数目K）

• K-Means算法需要用初始随机种子点来搞，这个随机种子点太重要，不同的随机种子点会有得到完全不同的结果。（K-Means++算法可以用来解决这个问题，其可以有效地选择初始点）

我在这里重点说一下K-Means++算法步骤：

1. 先从我们的数据库随机挑个随机点当“种子点”。
2. 对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
3. 然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。
4. 重复第（2）和第（3）步直到所有的K个种子点都被选出来。
5. 进行K-Means算法。

3. K-Means分布式实现

算法伪代码：
k-means的每一次迭代都可以分为以下3个步骤。

• 第一步：Map：对于每一个点，将其对应的最近的聚类中心

  
  

• 第二步：Combine：刚完成map的机器在本机上都分别完成同一个聚类的点的求和，减少reduce操作的通信量和计算量。

  
  

• 第三步：reduce：将同一聚类中心的中间数据再进行求和，得到新的聚类中心

  
  

4. K-Means并行化

并行化思路：使用主从模式。由一个节点充当主节点负责数据的划分与分配，其他节点完成本地数据的计算，并将结果返回给主节点。大致过程如下：

1. 进程0为主节点，先从文件中读取数据集，然后将数据集划分并传给其他进程；
2. 进程0选择每个聚类的中心点，并发送给其他进程；
3. 其他进程计算数据块中每个点到中心点的距离，然后标出每个点所属的聚类，并计算每个聚类所有点到其中心点的距离之和，最后将这些结果返回给进程0；
4. 进程0计算出新的中心点并发送给其他进程，并计算其他进程传来的聚类所有点到其中心点的距离总和；
5. 重复3和4直到，直到步骤4中的所有聚类的距离之和不变（即收敛）。