K均值算法（K-Means）
2017-12-13 本文已影响0人
闫阿佳
博客CSDN：深入浅出K-Means算法
博客：机器学习算法-K-means聚类
分布式：MapReduce实现
并行化：kmeans算法并行化的mpi程序
1. K-Means算法步骤
算法步骤
收敛性定义，畸变函数（distortion function）：
伪代码：
1) 创建k个点作为K个簇的起始质心（经常随机选择）
2) 当任意一个点的蔟分配结果发生变化时（初始化为True）
对数据集中的每个数据点，重新分配质心
对每个质心
计算质心到数据点之间的距离
将数据点分配到距其最近的蔟
对每个蔟，计算蔟中所有点的均值并将均值作为新的质心
缺点：
- 需要提前确定K值；
- 对异常值敏感；
- 对初始聚类中心敏感；
优点：
- 易解释；
- 运行速度快；
- 一般效果不错；
2. K-Means改进
2.1 K-Mediods
每次选取中值作为聚类中心，排除异常值的影响；
2.2 K-Means++算法
K-Means主要有两个最重大的缺陷——都和初始值有关：
-
K是事先给定的，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。（ISODATA算法通过类的自动合并和分裂，得到较为合理的类型数目K）
-
K-Means算法需要用初始随机种子点来搞，这个随机种子点太重要，不同的随机种子点会有得到完全不同的结果。（K-Means++算法可以用来解决这个问题，其可以有效地选择初始点）
我在这里重点说一下K-Means++算法步骤：
- 先从我们的数据库随机挑个随机点当“种子点”。
- 对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
- 然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。
- 重复第（2）和第（3）步直到所有的K个种子点都被选出来。
- 进行K-Means算法。
3. K-Means分布式实现
算法伪代码：
k-means的每一次迭代都可以分为以下3个步骤。
-
第一步：Map：对于每一个点，将其对应的最近的聚类中心
-
第二步：Combine：刚完成map的机器在本机上都分别完成同一个聚类的点的求和，减少reduce操作的通信量和计算量。
-
第三步：reduce：将同一聚类中心的中间数据再进行求和，得到新的聚类中心
4. K-Means并行化
并行化思路：使用主从模式。由一个节点充当主节点负责数据的划分与分配，其他节点完成本地数据的计算，并将结果返回给主节点。大致过程如下：
- 进程0为主节点，先从文件中读取数据集，然后将数据集划分并传给其他进程；
- 进程0选择每个聚类的中心点，并发送给其他进程；
- 其他进程计算数据块中每个点到中心点的距离，然后标出每个点所属的聚类，并计算每个聚类所有点到其中心点的距离之和，最后将这些结果返回给进程0；
- 进程0计算出新的中心点并发送给其他进程，并计算其他进程传来的聚类所有点到其中心点的距离总和；
- 重复3和4直到，直到步骤4中的所有聚类的距离之和不变（即收敛）。
