1、基于Hadoop数据挖掘算法研究,导师：王静宇 学生：卢胜宇,Cloud Computing,1,2,3,课题的背景,基于Hadoop平台的Canopy-Kmeans并行算法,课题总结,Cloud Computing,4,实验与结果分析,相关概念,Cloud Computing,课题背景,聚类算法及其分类Kmeans算法Canopy算法HadoopMapReduce,Cloud Computing,聚类算法及其分类,聚类是对点进行考察并按照某种距离测度将它们聚成多个“簇”的过程。聚类的目标是使得同一簇内的点之间距离比较短，而不同簇中点之间距离较大。,课题背景,Cloud Computing,课
2、题背景,聚类主要包括以下几个过程：数据准备、特征选择、提出、特征提取、聚类、聚类结果验证。动态的聚类过程步骤如下所示：,Cloud Computing,课题背景,Canopy 算法是 McCallum提出的一种简单、快速、但不太准确的聚类方法，是专门应对高维海量数据源的一种新型聚类算法。算法的思路是：首先在计算数据样本距离时采用算法复杂度低的距离度量(metric distance)，把样本数据集划分为一些部分重叠的子集，这种子集称之为华盖(canopies)。然后，在传统聚类中，比如 k 均值，应用复杂度高的度量距离，进一步计算，从而使得高维海量数据源聚类难题易于实现。,K-Means算法是
3、由 MacQueen 提出来的，该算法思想简单，实现相对容易，在多个学科里面都有广泛应用。它是聚类算法中最常见的划分方法，所谓的划分方法就是给定一个包含 n 个数据对象的数据集，将数据集划分为 k 个子集，其中每个子集均代表一个聚类，同一聚类中的对象相似度较高，而不同聚类中的对象相似度较小。,Cloud Computing,Hadoop平台,Hadoop是Apache旗下开源的分布式计算框架,可编写以及可运行分布式应用来处理大规模数据。Hadoop框架最核心组成部分就是HDFS(Hadoop Distributed File System)和MapReduce。,课题背景,Cloud Comp
4、uting,课题背景,MapReduce是一种编程模型，用于大规模数据集（大于1TB）的并行运算。概念Map（映射）和Reduce（归约），是它们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。它极大地方便了编程人员在不会分布式并行编程的情况下，将自己的程序运行在分布式系统上。 当前的软件实现是指定一个Map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce（归约）函数，用来保证所有映射的键值对中的每一个共享相同的键组。,MapReduce,为什么选择基于Hadoop平台的Canopy-Kmeans并行算法？,Cloud Computing,课
5、题背景,Cloud Computing,1.随着大数据时代的到来,同时硬件的提升也越来越困难,导致现在我们在单机下处理大规模数据遇到了前所未有的阻力和难度。2.传统的K-means算法在处理海量数据时效率低下、聚类质量差等弊端日益显露出来，其时间复杂度较高且处理数据的能力存在局限性也尤为突出。3.基于Hadoop平台的CK-means并行算法，该算法采用canopy算法改善K-means算法在确定初始聚类中心的盲目性，采用并行计算框架对算法并行扩展，使之能够适应对海量数据处理。,课题背景,1,2,3,课题的背景,基于Hadoop平台的Canopy-Kmeans并行算法,课题总结,Cloud C
6、omputing,4,实验与结果分析,Cloud Computing,算法的基本思想,CK-means算法是对K-means算法的一种优化，算法的思想为：采用基于余弦距离度量方式的canopy聚类算法对数据集初始中心点进行优化，canopy聚类算法利用MapReduce计算模式实现并行计算运行，经过Map和Reduce阶段得到全局的canopy中心集合，在对数据集进行精确聚类之前，还需要利用上面获取的全局canopy中心集合对数据集进行粗糙聚类，生成多个互相重叠的canopy聚类集合，这一系列的工作为下一步K-means精确聚类奠定基础。,算法流程,Canopy中心点生成,得到稳定的聚类,结束
7、,Canopy粗糙聚类生成,中心点标注,新中心点生成,聚类结果生成,开始,Cloud Computing,Cloud Computing,CanopyKmeans算法并行实现,根据前面的Canopy_Kmeans算法并行流程图，我们将整个过程设计成了两个MapReduce阶段，第一阶段执行Canopy算法,第二阶段执行Kmeans算法。,第一阶段Canopy算法的MapReduce实现,实现Canopy算法包括三个MR，即三个Job，可以描述为下面2个步骤：（1）Job1：将输入数据处理为Canopy算法可以使用的输入格式。（2）Job2：每个Mapper针对自己的输入执行Canopy聚类，输
8、出每个Canopy的中心向量。（3）Job2:每个Reducer接收Mapper的中心向量，并加以整合以计算最后的Canopy的中心向量。（4）Job3：根据Job2的中心向量来对原始数据进行分类。,Cloud Computing,第二阶段Kmeans算法的MapReduce实现,Kmeans算法利用上一阶段的生成的簇中心向量列表，对数据对象集合进行划分其主要的MapReduce编程模型包括了Map、Combine和Reduce三个阶段。,Map阶段,输入依然是各个数据块集合，输入格式为,Combine阶段,Combine函数用于合并Map结果中相同的key2的键值对，输入是Map的输出m，k
9、ey3依然还是簇类向量标识符，value3为相同key3的所有向量组合和这些向量的数目。,Reduce阶段,处理属于同一簇的所有数据对象向量，并重新生成新的簇类中心向量，其输入输出均是键值对形式，输入信息是各个子节点的combine结果，输出信息是簇类标识符和新的簇类中,1,2,3,课题的背景,基于Hadoop平台的Canopy-Kmeans并行算法,课题总结,Cloud Computing,4,实验与结果分析,Cloud Computing,实验平台的搭建,由于实验条件有限，本实验平台集群共4台计算机，搭建4个节点，服务器的配置如下表所示：,服务器的网络配置如下,操作系统：CentOS 6J
10、DK 版本：1.7Hadoop版本：2.5.2Mahout版本：0.10.1,Cloud Computing,软件环境,搭建Hadoop集群，Hadoop部署情况：,Cloud Computing,启动集群和Mahout,Web UI查看集群是否启动成功，在Master节点上启动Firefox浏览器，在浏览器地址栏输入http:/master:50070/，检查namenode和datanode是否启动正常。启动正常的UI页面如图2.10所示：,当Hadoop平台正常启动后，然后启动Mahout,Cloud Computing,实验过程,首先要准备数据，本实验运用的数据是在网站：http:/a
11、rchive.ics.uci.edu/ml/databases/synthetic_control/synthetic_control.data中下载相应数据synthetic_control.data。测试数据是由Dr Robert Alcock在1999年利用程序合成的600个样本的控制图数据。每个样本包括60个属性列，一共可以分为6类，分别为：正常（C）、循环（B）、上升趋势（E）、下降趋势（A）、向上移位（D）、向下移位（F）。首先上传该文本数据到HDFS。上传后在文件系统监控界面查看此文件。,Cloud Computing,分别执行Canopy算法和Kmeans算法,Cloud Co
12、mputing,实验结果分析,并行算法收敛曲线图,算法加速比分析,Cloud Computing,算法可扩展性分析,1,2,3,课题的背景,基于Hadoop平台的Canopy-Kmeans并行算法,课题总结,Cloud Computing,4,实验与结果分析,课题总结已完成的工作,针对传统的串行K-means聚类算法在处理海量数据时出现性能及初始聚类中心敏感等问题，提出了一种基于Hadoop平台的并行CK-means聚类算法，该算法采用Canopy算法和余弦相似度度量来改善K-means算法在确定初始聚类中心的盲目性，采用并行计算框架对算法并行扩展，使之能够适应海量数据处理。实验结果表明提出的
13、基于Hadoop 平台的CK-means并行算法具有更好的聚类质量，在处理海量数据时具有良好的加速比和扩展性。,课题总结已完成的工作,本文的主要工作有：,（1）针对传统的串行K-means聚类算法在处理海量数据时出现性能及初始聚类中心敏感等问题，提出了一种基于Hadoop平台的并行CK-means聚类算法。（2）通过利用代价低的余弦相似性度量方式的Canopy算法快速获取聚类中心作为K-means并行算法的初始聚类中心，加快K-means算法的收敛速度。（3）该算法对原始数据使用基于余弦相似度度量方式的Canopy算法进行聚类和覆盖划分，使得并行K-means算法进行精确聚类时不需要计算不处于
14、同一个Canopy的点之间的距离，这在很大程度上减少计算量。（4）实验验证所提出的CK-means算法的聚类质量、加速比和扩展性。,研究进度存在的问题,虽然在搭建好的Hadoop平台上对本文提出的一种基于Hadoop平台的CKmeans算法进行了实验验证，但实验数据单一，并且由于条件有限，adoop平台下处理数据的结点较少，这也造成了该算法在不同量的结点上得出的结论，且本实验没有在单机模式下也就是看kmeans串行算法进行对比实验，这也将是论文下一步的工作重点。,课题总结下一步改进计划,（1）继续对Hadoop平台的相关技术进行研究，对Hadoop中的HDFS分布式存储系统与MapReduce编程模式做进一步研究。（2）继续完善实验平台，由于实验室结点有限，以后要尽量选择多的节点对本文提出的算法进行并行实验，并选择不同数据集对本文提出的算法验证。,期刊论文发表情况（已见刊）,卢胜宇，王静宇，张晓琳，高俊峰基于Hadoop平台的K-means聚类算法优化研究J内蒙古科技大学校报，2016，35：264-268.,谢 谢,
