Ch91-基于MapReduce的K-Means聚类并行算法.ppt

Ch MapReduce 算法设计——K-Means聚类算法
南京大学计算机科学与技术系
主讲人:黄宜华,肖韬
2011年春季学期
MapReduce海量数据并行处理
鸣谢:本课程得到Google公司(北京)
中国大学合作部精品课程计划资助
本节课程纲要

-Means聚类算法介绍
-Means算法为什么适合使用并行方法
-Means并行算法

数据挖掘
定义:数据挖掘是通过对大规模观测数据集的分析,寻找确信的关系,并将数据以一种可理解的、且利于使用的新颖方式概括数据的方法。
数据挖掘的特征之一:海量数据
—— Small data does not require data mining, large data causes problems
——以上摘自黎铭的《数据挖掘》课件
可见,数据挖掘是并行计算中值得研究的一个领域
聚类过程
定义:将给定的多个对象分成若干组,组内的各个对象是相似的,组间的对象是不相似的。进行划分的过程就是聚类过程,划分后的组称为簇(cluster)。
几种聚类方法:
基于划分的方法;
基于层次的方法;
基于密度的方法;
... ...
基于划分(partitioning)的聚类方法
给定N个对象,构造K个分组,每个分组就代表一个聚类。
这K个分组满足以下条件:
每个分组至少包含一个对象;
每个对象属于且仅属于一个分组;
K-Means算法是最常见和典型的基于划分的聚类方法
K-Means算法
输入:待聚类的N个数据点,期望生成的聚类的个数K
输出:K个聚类
----算法描述-------------------------
选出K个点作为初始的cluster center
Loop:
对输入中的每一个点p:{
计算p到各个cluster的距离;
将p归入最近的cluster;
}

重新计算各个cluster的中心

如果不满足停止条件,goto Loop; 否则,停止
过程示例 (1)
初始数据
K = 2
选择初始中心
------------------------------------------------------------------------
------------------------------------------------------------------------
第1次聚类:计算距离
+
+
过程示例 (2)
第1次聚类:归类各点
------------------------------------------------------------------------
重新计算聚类中心
+
+
过程示例 (3)
第2次聚类:计算距离
------------------------------------------------------------------------
第2次聚类:归类各点
+
+
+
+
聚类无变化,迭代终止
K-Means是个不断迭代的过程
第 i轮迭代:
生成新的clusters,并计算cluster centers
第 i+1轮迭代:
根据第i轮迭代中生成的clusters和计算出的cluster centers,进行新一轮的聚类
如此不断迭代直到满足终止条件