k-means的分布式实现

??? 网上逛论坛的时候无意中看到，mahout实现了基于mapreduce的k-means。我自己想了想其中的原理，发现不是很复杂。

?

??? 先从百科抄一段k-means的流程：

　输入：k, data[n]; 　

? （1） 选择k个初始中心点，例如c[0]=data[0],…c[k-1]=data[k-1];

? （2） 对于data[0]….data[n], 分别与c[0]…c[n-1]比较，假定与c[i]差值最少，就标记为i类; 　

? （3） 对于所有标记为i点，重新计算c[i]={ 所有标记为i类的data[j]之和}/标记为i类的个数；??

? （4） 重复(2)(3),直到所有c[i]值的变化小于给定阈值。

?

?? 在一次迭代，第二步是最耗时，比如一亿个样本要聚成一万类，需要一万亿次基本操作。而这一步也是容易进行并行处理的。data[0]与c[0]…c[n-1]比较的同时，data[1]可以与c[0]…c[n-1]比较。这种最耗时的步骤容易并行处理的特性决定了，k-means分布式实现有效。

?

?? 基于mapreduce的k-means，一次迭代需要启动一次mapreduce过程。每次mapreduce过程，执行(2)(3)步骤。

?? 基于mapreduce的k-means的算法流程如下：

?? 输入：k, data[n]（data应存在dfs里）;?

? （1）本地选择k个初始中心点。c[]存入文件clusterlist；

? （2）启动mapreduce过程，将文件clusterlist分发到各个节点。输入为存在dfs上的data,输出为dfs的dfs_clusterlist；

? （3）map过程：输入data[k1,..,k2]。对于data[k], 与c[0]…c[n-1]比较，假定与c[i]差值最少，就标记为i类。输出i,data[k]。i为key,data[k]为value；

? （4）reduce过程：由于类别为key，则同一类别的所有data会输入同reduce并且紧邻。这样我们可以重新计算c[i]={ 所有标记为i类的data[j]之和}/标记为i类的个数。将结果输出到res。

? （5）本地抓取dfs_clusterlist。dfs_clusterlist与原有的clusterlist比较。若变化小于给定阈值，则算法结束；反之，则用dfs_clusterlist替换clusterlist,跳转到(2)。

?

?? 后面想了想，发现朴素bayes也可以分布式实现。关键是朴素bayes实现过程，每一个样本的处理以及每一个概率密度估计器的训练可以并行。不过想想用海量数据训练分类器，是一件比较蛋疼的事，就不细说了。

?

原文地址：http://blog.163.com/rustle_go_go/blog/static/2029450142012233195419/

?