用mapreduce实现10亿级以上数据的kmeans

用mapreduce实现10亿级以上数据的kmeans

参考回答：

算法1.map(key,value)

输入：全局变量centers，偏移量key，样本value

输出：<key’,value>对，其中key’是最近中心的索引，value’是样本信息的字符串

从value构造样本的instance；

minDis=Double.MAX_VALUE；Index=-1；For i=0 to centers.length dodis=ComputeDist(instance,centers[i]);If dis<minDis{minDis=dis;index=i;}End For

把index作为key’；

把不同维度的values构造成value’；

输出<key’,value’>对；

End

注意这里的Step 2和Step 3初始化了辅助变量minDis和index；Step 4通过计算找出了与样本最近的中心点，函数ComputeDist(instance,centers[i])返回样本和中心点centers[i]的距离；Step 8输出了用来进行下一个过程（combiner）的中间数据。

Combine函数. 每个map任务完成之后，我们用combiner去合并同一个map任务的中间结果。因为中间结果是存储在结点的本地磁盘上，所以这个过程不会耗费网络传输的代价。在combine函数中，我们把属于相同簇的values求和。为了计算每个簇的对象的平均值，我们需要记录每个map的每个簇中样本的总数。Combine函数的伪代码见算法2.

算法2.combine(key,V)

输入：key为簇的索引，V为属于该簇的样本列表

输出：<key’,value’>对，key’为簇的索引，value’是由属于同一类的所有样本总和以及样本数所组成的字符串。

初始化一个数组，用来记录同一类的所有样本的每个维度的总和，样本是V中的元素；

初始化一个计数器num为0来记录属于同一类的样本总数；

While(V.hasNext()){

从V.next()构造样本实例instance；

把instance的不同维度值相加到数组

num++;

}

把key作为key’；

构造value’：不同维度的求和结果+num；

输出<key’,value’>对；

End

Reduce函数. Reduce函数的输入数据由每个结点的combine函数获得。如combine函数所描述，输入数据包括部分样本（同一类）的求和以及对应样本数。在reduce函数中，我们可以把同一类的所有样本求和并且计算出对应的样本数。因此，我们可以得到用于下一轮迭代的新中心。Reduce函数的伪代码见算法3。

算法3.Reduce(key,V)

输入：key为簇的索引，V为来自不同结点的部分总和的样本列表

输出：<key’,value’>对，key’为簇的索引，value’是代表新的聚类中心的字符串

初始化一个数组，用来记录同一类的所有样本的每个维度的总和，样本是V中的元素；

初始化一个计数器NUM为0来记录属于同一类的样本总数；

While(V.hasNext()){

从V.next()构造样本实例instance；

把instance的不同维度值相加到数组

NUM+=num;

}

数组的每个元素除以NUM来获得新的中心坐标；

把key作为key’；

构造value’为所有中心坐标的字符串；

输出<key’,value’>对；

End