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)步骤,算法流程如下:输入: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)。

此条目发表在编程开发分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。