一种基于Hadoop平台下的K-means算法.ppt

导师：黄萍 姓名：陈涛 范金兰 班级：2008计算机科学与技术（3）班 打开目录 K-means聚类算法分析 K-means算法的核心思想是把n个数据对象划分为k个聚类,使每个聚类中的数据点到该聚类中心的平方和最小,算法处理过程： 输入：聚类个数k,包含n个数据对象的数据集. 输出：k个聚类. (1)从n个数据对象中任意选取k个对象作为初始的聚类中心. (2)分别计算每个对象到各个聚类中心的距离,把对象分配到距离最近的聚类中. (3)所有对象分配完成后,重新计算k个聚类的中心. (4)与前一次计算得到的k个聚类中心比较,如果聚类中心发生变化,转(2),否则转(5). (5)输出聚类结果. 打开目录 K-means聚类算法分析 K-means算法的核心思想是把n个数据对象划分为k个聚类,使每个聚类中的数据点到该聚类中心的平方和最小,算法处理过程： 输入：聚类个数k,包含n个数据对象的数据集. 输出：k个聚类. (1)从n个数据对象中任意选取k个对象作为初始的聚类中心. (2)分别计算每个对象到各个聚类中心的距离,把对象分配到距离最近的聚类中. (3)所有对象分配完成后,重新计算k个聚类的中心. (4)与前一次计算得到的k个聚类中心比较,如果聚类中心发生变化,转(2),否则转(5). (5)输出聚类结果. 流程图 数据分布 最终结果 第一次迭代 打开目录 K-means聚类并行原理分析 设分布式系统中有p个站点,从中任意选定一个站点Sm为主站点,其余p-1个站点为从站点.首先在主站点随机产生k个聚簇中心作为全局初始聚簇中心,并将其广播给所有从站点；各站点根据这些中心确认本站数据对象所属聚簇,并通过公式得到局部聚簇中心,同时,从站点将本站点的局部聚簇中心点及相应簇的数据对象总数传送给主站点；主站点根据这些聚簇信息计算全局聚簇中心.迭代上述过程,直到全局判别函数E值稳定,也即全局聚簇中心稳定 打开目录 K-means聚类并行原理分析 设分布式系统中有p个站点,从中任意选定一个站点Sm为主站点,其余p-1个站点为从站点.首先在主站点随机产生k个聚簇中心作为全局初始聚簇中心,并将其广播给所有从站点；各站点根据这些中心确认本站数据对象所属聚簇,并通过公式得到局部聚簇中心,同时,从站点将本站点的局部聚簇中心点及相应簇的数据对象总数传送给主站点；主站点根据这些聚簇信息计算全局聚簇中心.迭代上述过程,直到全局判别函数E值稳定,也即全局聚簇中心稳定 打开目录 K-means聚类并行原理分析 设分布式系统中有p个站点,从中任意选定一个站点Sm为主站点,其余p-1个站点为从站点.首先在主站点随机产生k个聚簇中心作为全局初始聚簇中心,并将其广播给所有从站点；各站点根据这些中心确认本站数据对象所属聚簇,并通过公式得到局部聚簇中心,同时,从站点将本站点的局部聚簇中心点及相应簇的数据对象总数传送给主站点；主站点根据这些聚簇信息计算全局聚簇中心.迭代上述过程,直到全局判别函数E值稳定,也即全局聚簇中心稳定 打开目录 K-means聚类并行原理分析 设分布式系统中有p个站点,从中任意选定一个站点Sm为主站点,其余p-1个站点为从站点.首先在主站点随机产生k个聚簇中心作为全局初始聚簇中心,并将其广播给所有从站点；各站点根据这些中心确认本站数据对象所属聚簇,并通过公式得到局部聚簇中心,同时,从站点将本站点的局部聚簇中心点及相应簇的数据对象总数传送给主站点；主站点根据这些聚簇信息计算全局聚簇中心.迭代上述过程,直到全局判别函数E值稳定,也即全局聚簇中心稳定 打开目录 基于Mapreduce的K-means并行算法的具体实现思想 在进行K-Means聚类中，在处理每一个数据点时 只需要知道： 各个cluster 的中心 不需要知道 关于其他数据点的任何信息 所以，如果涉及到全局信息，只需要知道关于各个cluster center的信息即可 打开目录 基于Mapreduce的K-means并行算法的具体实现思想 在进行K-Means聚类中，在处理每一个数据点时 只需要知道： 各个cluster 的中心 不需要知道 关于其他数据点的任何信息 所以，如果涉及到全局信息，只需要知道关于各个cluster center的信息即可 打开目录 基于Mapreduce的K-means并行算法的具体实现思想 将所有的数据分布到不同的node 上，每个node只对自己的数据进行计算 每个node能够读取上一次迭代生成的cluster centers，并计算自己的各个数据点应该属于哪一个cluster 每个node在一次迭代中根据自己的数据点计算新的cluster cen