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

,一种基于Hadoop平台的聚类-K-means算法的并行实现,导师：黄萍姓名：陈涛范金兰班级：2008计算机科学与技术（3）班,目录,目录,目录,研究背景及意义,数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中未知的、有潜在应用价值的信息或模式的过程.计算机技术的迅猛发展以及网络的普及,使人们有更多机会使用便捷的方法与外界进行信息交流.可是,数据大量的涌入,增加了我们获取有用信息的难度.,研究背景及意义,数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中未知的、有潜在应用价值的信息或模式的过程.计算机技术的迅猛发展以及网络的普及,使人们有更多机会使用便捷的方法与外界进行信息交流.可是,数据大量的涌入,增加了我们获取有用信息的难度.,Hadoop平台简介,Hadoop的简介,Hadoop是一个分布式系统基础架构。由Apache基金会开发。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力高速运算和存储。也可以说Hadoop是以分散存储和并行计算为基础的云计算平台，利用低成本的PC设备组成大型集群，构建下一代高性能的海量数据分布式计算平台。hadoop的核心主要包含：HDFS和MapReduceHDFS是分布式文件系统，用于分布式存储海量数据。MapReduce是分布式数据处理模型，本质是并行处理。,Hadoop平台简介,Hadoop的简介,Hadoop是一个分布式系统基础架构。由Apache基金会开发。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力高速运算和存储。也可以说Hadoop是以分散存储和并行计算为基础的云计算平台，利用低成本的PC设备组成大型集群，构建下一代高性能的海量数据分布式计算平台。hadoop的核心主要包含：HDFS和MapReduceHDFS是分布式文件系统，用于分布式存储海量数据。MapReduce是分布式数据处理模型，本质是并行处理。,Hadoop平台简介,Hadoop的简介,Hadoop框架可在单一的Linux平台上使用（开发和调试时），但是使用存放在机架上的商业服务器才能发挥它的力量。这些机架组成一个Hadoop集群。它通过集群拓扑知识决定如何在整个集群中分配作业和文件。Hadoop假定节点可能失败，因此采用本机方法处理单个计算机甚至所有机架的失败。简单的hadoop集群简化视图如下图所示。,Hadoop平台简介,Hadoop的简介,Hadoop框架可在单一的Linux平台上使用（开发和调试时），但是使用存放在机架上的商业服务器才能发挥它的力量。这些机架组成一个Hadoop集群。它通过集群拓扑知识决定如何在整个集群中分配作业和文件。Hadoop假定节点可能失败，因此采用本机方法处理单个计算机甚至所有机架的失败。简单的hadoop集群简化视图如下图所示。,Hadoop平台简介,Hadoop的简介,Hadoop框架可在单一的Linux平台上使用（开发和调试时），但是使用存放在机架上的商业服务器才能发挥它的力量。这些机架组成一个Hadoop集群。它通过集群拓扑知识决定如何在整个集群中分配作业和文件。Hadoop假定节点可能失败，因此采用本机方法处理单个计算机甚至所有机架的失败。简单的hadoop集群简化视图如下图所示。,Hadoop平台简介,Hadoop的简介,Hadoop框架可在单一的Linux平台上使用（开发和调试时），但是使用存放在机架上的商业服务器才能发挥它的力量。这些机架组成一个Hadoop集群。它通过集群拓扑知识决定如何在整个集群中分配作业和文件。Hadoop假定节点可能失败，因此采用本机方法处理单个计算机甚至所有机架的失败。简单的hadoop集群简化视图如下图所示。,Hadoop平台简介,Hadoop的运行模式,1.单机模式2.伪分布式模式一个机器即当namenode又当datanode,或者说即是jobtracker,又是tasktracker。没有所谓的在多台机器上进行真正的分布式计算，故称为伪分布式。3.完全分布式模式本文的实验将会分别在单机模式和完全分布式模式进行操作。,Hadoop平台简介,Hadoop的运行模式,1.单机模式2.伪分布式模式一个机器即当namenode又当datanode,或者说即是jobtracker,又是tasktracker。没有所谓的在多台机器上进行真正的分布式计算，故称为伪分布式。3.完全分布式模式本文的实验将会分别在单机模式和完全分布式模式进行操作。,Hadoop平台简介,Hadoop的运行模式,1.单机模式2.伪分布式模式一个机器即当namenode又当datanode,或者说即是jobtracker,又是tasktracker。没有所谓的在多台机器上进行真正的分布式计算，故称为伪分布式。3.完全分布式模式本文的实验将会分别在单机模式和完全分布式模式进行操作。,Hadoop平台简介,Hadoop的运行模式,1.单机模式2.伪分布式模式一个机器即当namenode又当datanode,或者说即是jobtracker,又是tasktracker。没有所谓的在多台机器上进行真正的分布式计算，故称为伪分布式。3.完全分布式模式本文的实验将会分别在单机模式和完全分布式模式进行操作。,Hadoop平台搭建,准备工作,（1）下载vm虚拟机并进行安装；（2）RedhatLinux9.0的安装；新建虚拟机，加载RedhatLinux9.0系统的iso镜像文件，并在虚拟机下安装linux系统。（3）linux系统的简单设置；对linux系统进行简单的网络设置，使其接入Internet。（4）JDK的安装下载jdk安装文件jdk-6u30-linux-i586.bin，在终端下进入jdk-6u30-linux-i586.bin文件所在目录，执行命令./jdk-6u30-linux-i586.bin一直按回车。之后在该目录下生成jdk-1.6.0目录。（5）hadoop的安装在linux系统中，下载hadoop-0.21.0.tar.gz,j解压到/home文件夹下。,Hadoop平台搭建,准备工作,（1）下载vm虚拟机并进行安装；（2）RedhatLinux9.0的安装；新建虚拟机，加载RedhatLinux9.0系统的iso镜像文件，并在虚拟机下安装linux系统。（3）linux系统的简单设置；对linux系统进行简单的网络设置，使其接入Internet。（4）JDK的安装下载jdk安装文件jdk-6u30-linux-i586.bin，在终端下进入jdk-6u30-linux-i586.bin文件所在目录，执行命令./jdk-6u30-linux-i586.bin一直按回车。之后在该目录下生成jdk-1.6.0目录。（5）hadoop的安装在linux系统中，下载hadoop-0.21.0.tar.gz,j解压到/home文件夹下。,Hadoop平台简介与平台搭建,配置工作,（1）配置JDK环境变量PATH环境变量CLASSPATH环境变量JAVA_HOME环境变量（2）配置hadoop单机模式配置：修改hadoop-env.sh。本机器上解压路径是/home/hadoop-0.21.0，进入刚才所解压的文件夹，修改之(需要root权限)。cdhadoop-0.21.0geditconf/hadoop-env.sh设置xml文件，需要设置conf文件夹下的三个文件core-site.xml,hdfs-site.xml,mapred-site.xml,Hadoop平台简介与平台搭建,配置工作,（1）配置JDK环境变量PATH环境变量CLASSPATH环境变量JAVA_HOME环境变量（2）配置hadoop单机模式配置：修改hadoop-env.sh。本机器上解压路径是/home/hadoop-0.21.0，进入刚才所解压的文件夹，修改之(需要root权限)。cdhadoop-0.21.0geditconf/hadoop-env.sh设置xml文件，需要设置conf文件夹下的三个文件core-site.xml,hdfs-site.xml,mapred-site.xml,Hadoop平台简介与平台搭建,完全分布式模式的配置：首先，要两台机配置节点将master机密钥复制大slave机上3.运行hadoop（1）格式化分布式文件系统：$bin/hadoopnamenodeformat(2)启动hadoop：$bin/start-all.sh,配置工作,Hadoop平台简介与平台搭建,完全分布式模式的配置：首先，要两台机配置节点将master机密钥复制大slave机上3.运行hadoop（1）格式化分布式文件系统：$bin/hadoopnamenodeformat(2)启动hadoop：$bin/start-all.sh,配置工作,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聚类算法分析,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聚类算法分析,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聚类算法分析,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聚类算法分析,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的中心不需要知道关于其他数据点的任何信息所以，如果涉及到全局信息，只需要知道关于各个clustercenter的信息即可,基于Mapreduce的K-means并行算法的具体实现思想,在进行K-Means聚类中，在处理每一个数据点时只需要知道：各个cluster的中心不需要知道关于其他数据点的任何信息所以，如果涉及到全局信息，只需要知道关于各个clustercenter的信息即可,基于Mapreduce的K-means并行算法的具体实现思想,将所有的数据分布到不同的node上，每个node只对自己的数据进行计算每个node能够读取上一次迭代生成的clustercenters，并计算自己的各个数据点应该属于哪一个cluster每个node在一次迭代中根据自己的数据点计算新的clustercenters综合每个节点计算出的clustercenters，计算出最终的实际clustercenters,基于Mapreduce的K-means并行算法的具体实现思想,将所有的数据分布到不同的node上，每个node只对自己的数据进行计算每个node能够读取上一次迭代生成的clustercenters，并计算自己的各个数据点应该属于哪一个cluster每个node在一次迭代中根据自己的数据点计算新的clustercenters综合每个节点计算出的clustercenters，计算出最终的实际clustercenters,基于Mapreduce的K-means并行算法的具体实现思想,每一个节点需要访问如下的全局文件当前的迭代计数clusteridclustercenter属于该clustercenter的数据点的个数这是唯一的全局文件,基于Mapreduce的K-means并行算法的具体实现思想,每一个节点需要访问如下的全局文件当前的迭代计数clusteridclustercenter属于该clustercenter的数据点的个数这是唯一的全局文件,基于Mapreduce的K-means并行算法的具体实现思想,令k=3，欲生成cluster-0和cluster-1选取x1(1,2),x2(2,2),x3(2,5)作为中心点假定将所有数据分布到2个节点node-0和node-1上,即,Cluster-0,Cluster-1,基于Mapreduce的K-means并行算法的具体实现思想,令k=3，欲生成cluster-0和cluster-1选取x1(1,2),x2(2,2),x3(2,5)作为中心点假定将所有数据分布到2个节点node-0和node-1上,即,Cluster-0,Cluster-1,基于Mapreduce的K-means并行算法的具体实现思想,在开始之前，首先创建一个如前所述的全局文件,基于Mapreduce的K-means并行算法的具体实现思想,在开始之前，首先创建一个如前所述的全局文件,基于Mapreduce的K-means并行算法的具体实现思想,Map阶段,每个节点读取全局文件，以获得上一轮迭代生成的clustercenters等信息计算自己的每一个数据点到各个clustercenter的距离为每一个数据点，emit,基于Mapreduce的K-means并行算法的具体实现思想,Map阶段,每个节点读取全局文件，以获得上一轮迭代生成的clustercenters等信息计算自己的每一个数据点到各个clustercenter的距离为每一个数据点，emit,基于Mapreduce的K-means并行算法的具体实现思想,MapIteration1,计算各个数据点到各个cluster的距离，假定是如下的结果：,基于Mapreduce的K-means并行算法的具体实现思想,MapIteration1,计算各个数据点到各个cluster的距离，假定是如下的结果：,基于Mapreduce的K-means并行算法的具体实现思想,MapIteration1,计算各个数据点到各个cluster的距离，假定是如下的结果：,基于Mapreduce的K-means并行算法的具体实现思想,MapIteration1,计算各个数据点到各个cluster的距离，假定是如下的结果：,基于Mapreduce的K-means并行算法的具体实现思想,MapIteration1,计算各个数据点到各个cluster的距离，假定是如下的结果：,node-0输出：node-1输出：,基于Mapreduce的K-means并行算法的具体实现思想,MapIteration1,计算各个数据点到各个cluster的距离，假定是如下的结果：,node-0输出：node-1输出：,基于Mapreduce的K-means并行算法的具体实现思想,Combine阶段,利用combiner减少map阶段emit的大量数据Combiner计算每一个cluster的center，以及属于该cluster的数据点的个数然后，为每一个cluster发射key-valuepairkey-clusterid,value-【#ofdatapointsofthiscluster，averagevalue】,基于Mapreduce的K-means并行算法的具体实现思想,Combine阶段,利用combiner减少map阶段emit的大量数据Combiner计算每一个cluster的center，以及属于该cluster的数据点的个数然后，为每一个cluster发射key-valuepairkey-clusterid,value-【#ofdatapointsofthiscluster，averagevalue】,基于Mapreduce的K-means并行算法的具体实现思想,CombineIteration1,node-0发射：node-1发射：,基于Mapreduce的K-means并行算法的具体实现思想,CombineIteration1,node-0发射：node-1发射：,基于Mapreduce的K-means并行算法的具体实现思想,Reduce阶段,每个