《南开大学 并行程序设计 基于Hadoop MapReduce编程工具的K-means算法并行化》由会员分享，可在线阅读，更多相关《南开大学 并行程序设计 基于Hadoop MapReduce编程工具的K-means算法并行化（10页珍藏版）》请在金锄头文库上搜索。
1、一 、请同学们在下列题目中任选一题，写成期末论文。（一）并行算法研究类对某一问题，研究其并行算法的设计、实现，分析其性能，进行实验验证，撰写研究论文。例如：1、对矩阵相乘问题，设计pthread多线程结合SSE/AVX的两层并行算法，实现并行程序。讨论算法层面不同策略对性能的影响，例如多个线程间不同的任务分配方式、不同的线程同步策略等，讨论不同并行编程方法对性能的影响，例如SSE/AVX的对齐和不对齐内存访问等等。对不同的矩阵规模、不同的线程数测试程序性能，撰写研究论文。2、对高斯消去法问题（其串行算法伪代码示意如下面算法1所示），设计pthread多线程结合SSE/AVX的两层并行算法，实现
2、并行程序。讨论算法层面不同策略对性能的影响，例如多个线程间不同的任务分配方式、不同的线程同步策略等，讨论不同并行编程方法对性能的影响，例如SSE/AVX的对齐和不对齐内存访问等等。对不同的矩阵规模、不同的线程数测试程序性能，撰写研究论文。3、其他类似难度的问题。（二）并行编程工具调研类对某种并行编程工具进行调研，选取某个问题（例如矩阵相乘问题），用这种编程工具编写并行程序求解这个问题，进行实验验证，撰写研究论文介绍这种并行编程工具的特色、基本编程（使用）方法、如何用它解决实际问题（以你选定的问题为例）。例如：1、C+、Java等语言本身对并行编程提供的支持。2、Hadoop MapReduce
3、编程工具。3、其它并行编程工具。二、论文写作要求（一）并行算法研究类1、论文应详细描述清楚所研究的问题，并行算法的设计。2、鼓励大家选择课堂教学之外的问题，通过文献调研，研究其并行求解方法，甚至有自己提出新的方法。3、最好能有求解一个问题的多种并行算法之间的对比分析。（二）并行编程工具调研类1、应调研较新的工具，避免调研太“古老”的工具。2、不能只是工具相关资料的调研和文字的汇总、整理，重点仍是并行编程用调研的工具编程解决一个具体问题。3、鼓励大家进行不同并行编程工具间的对比，例如调研的工具与课堂讲授的工具之间的对比。基于Hadoop MapReduce编程工具的K-means算法并行化摘要在
4、许多应用上，数据聚类已经受到了广泛的关注，比如数据挖掘、文本检索、图像分割和模式识别等。随着科技进步而逐渐扩大的信息量使大数据的聚类变成了一个具有挑战性的任务。为了解决这个问题，许多调查研究者尝试去设计一种高效的并行聚类算法。在这篇文章中，我们提出一种基于MapReduce的并行k-means聚类算法，这是一种简单又强大的并行编程技术。实验结果表明所提出的算法可以大规模而且高效地在廉价的硬件上处理大型数据集。关键字：Hadoop、MapReduce、编程工具、K-means算法、并行化一、引言随着信息技术的发展，许多应用处理的数据规模会达到千兆级别，而这会自然而然地对计算提出更高的要求。高效的
5、并行聚类算法和运行技术是满足科学数据分析的可扩展性以及性能要求的关键。到目前为止，一些研究者已经提出了一些并行聚类算法。所有的这些并行聚类算法都有下述的缺点：a）他们假设所有对象都能在主存中同时存放；b）这些并行系统提供了有限的编程模型，并使用这种限制去自动并行计算。以上两者在面对拥有成千上万对象的大规模数据集时会望而却步。因此，以并行聚类算法为方向的数据集需要得到发展。 MapReduce是一种编程模型，用于处理和生成适用于各种现实世界任务的大型数据集的关联实施。用户指定map和reduce函数的计算过程，底层的运行系统便可以自动地在大规模集群上并行计算，可以自动地处理机器的错误，可以协调好
6、中间机器的交互以至于高效地利用网络和磁盘资源。Google和Hadoop都提供了MapReduce运行时容错和动态灵活性的支持。 在这篇文章中，我们把k-means算法改编到MapReduce框架下，该框架是在Hadoop下执行的，目的是为了使聚类方法变得可行。二、Hadoop概述Hadoop 是由Apache基金会开发的分布式基础框架,用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力高速运算和存储。Hadoop实现了一个分布式文件系统（Hadoop Distributed File System）,简称HDFS。HDFS有着高容错性的特点,并且设计用来部署在低廉的（
7、low-cost）硬件上。而且它提供高传输率（high throughput）来访问应用程序的数据,适合那些有着超大数据集（large data set）的应用程序。HDFS放宽了（relax）POSIX的要求（requirements）这样可以流的形式访问（streaming access）文件系统中的数据。Hadoop 有许多元素构成。其最底部是 Hadoop Distributed File System（HDFS）,它存储 Hadoop 集群中所有存储节点上的文件。HDFS的上一层MapReduce 引擎,该引擎由 JobTrackers 和 TaskTrackers 组成。MapRe
8、duce 是一种高效的分布式编程模型 也是一种用于处理和生成大规模数据集的实现方式MapReduce计算。模型各个阶段的工作流程如下：(1)Input：一个基于 Hadoop平台MapReduce框架的应用通常需要一对通过实现合适的接口或抽象类提供的Map和Reduce函数 还应该指明输入、输出的位置和其他一些运行参数 此阶段还会把输入目录下的大数据文件划分为若干独立的数据块。(2)Map: MapReduce框架把应用的输入看作一组键值对,在 Map这个阶段,框架会调用用户自定义的Map函数,处理每个键值对,同时生成一批新的中间键值对,这两组键值对的类型可能不同。(3)Shuffle：为了保
9、证Reduce的输入是Map排好序的输出,在Shuffle阶段,框架通过HTTP为每个Reduce获得所有Map输出中与之相关的键值对, MapRedus框架按照Key值对Reduce阶段的输入进行分组,因为不同Map的输出中可能会有相同的Key。(4)Reduce：此阶段会遍历中间数据 对每一个唯一的Key执行用户自定义的Reduce函数 输入参数是,输出是新的 键值对。(5)Output：此阶段会把Reduce输出的结果写入到输出目录指定的位置 这样 一个典型的MapReduce过程就完成了。hadoop擅长日志分析，facebook就用Hive来进行日志分析，2009年时facebook
10、就有非编程人员的30%的人使用HiveQL进行数据分析；淘宝搜索中 的 自定义筛选也使用的Hive；利用Pig还可以做高级的数据处理，包括Twitter、LinkedIn 上用于发现您可能认识的人，可以实现类似A的协同过滤的推荐效果。淘宝的商品推荐也是！在Yahoo！的40%的Hadoop作业是用pig运行的，包括垃圾邮件的识别和过滤，还有用户特征建模。三、K-means聚类算法MacQue既在1967年提出的K-means算法,是一种被广泛应用于科学研究和工业应用中的经典聚类算法。K-means算法的核心思想是把n个数据对象划分为k个聚类,使每个聚类中的数据点到该聚类中心的平方和最小,算法处
11、理过程：输入：聚类个数k,包含n个数据对象的数据集。输出：k个聚类。(1)从n个数据对象中任意选取k个对象作为初始的聚类中心。(2)分别计算每个对象到各个聚类中心的距离,把对象分配到距离最近的聚类中。(3)所有对象分配完成后,重新计算k个聚类的中心。(4)与前一次计算得到的k个聚类中心比较,如果聚类中心发生变化,转(2),否则转(5)。(5)输出聚类结果。开始结束输入聚类个数k,n初始化k个聚类中心分配各个数据对象到距离最近的类中重新计算各个聚类的中心输入聚类的结果是否收敛否是K-means算法的工作流程如下图。首先从n个数据对象中任意选择k个对象作为初始聚类中心;而对于所剩下的其它对象,则根
12、据他们与这些聚类中心的相似度(距离),分别将他们分配给与其最相似的(聚类中心所代表的)聚类。然后再计算每个所新聚类的聚类中心(该聚类中所有对象的均值)。不断重复这一过程直到标准测度函数开始收敛为止。一般都采用计算欧氏距离的方式进行计算。具体计算公式如下：K-means算法优点是可以处理大数据集,K-means算法是相对可伸缩的和高效率的,因为它的计算复杂度为O(nkt),其中n为对象个数,k为聚类个数,t为迭代次数,通常有tn,kn,因此它的复杂度通常也用O(n)表示。下面以一组二维数据为例,简要说明K-means的聚类过程。 x1x2x3x4x5x6x7x8x9x10x11x12239101
13、011151616y225314131516658空间分布图如下图所示输入k=3,kl=x1,k2=x2,k3=x3。算法初始分别选定前三个数据作为初始聚类中心,进行一次迭代后的聚类如下图所示。经过反复迭代后,最后的最佳聚类结果如下图所示。此外K-means算法不依赖于顺序,给定一个初始类分布,无论样本点的顺序如何,生成的数据分类都一样。基于大规模的数据运算,显然单个计算机上面的K-means已经远远不能满足数据聚类的处理,不断的迭代对运算时间造成考验,本文就K-means进行并行化,使得运算时间大大降低,下面就K-means进行做出论述。四、K-means聚类算法的并行化根据K-means聚
14、类算法并行原理分析将所有的数据分布到不同的node 上,每个node只对自己的数据进行计算。每个node能够读取上一次迭代生成的cluster centers,并计算自己的各个数据点应该属于哪一个cluster。每个node在一次迭代中根据自己的数据点计算新的cluster centers。综合每个节点计算出的cluster centers,计算出最终的实际cluster centers。每一个节点需要访问如下的全局文件,这是唯一的全局文件。当前的迭代计数。cluster id。cluster center。属于该cluster center的数据点的个数。本文以下里数据为例,将数据分别上传都
15、两个DataNode上,数据分配如下。 node-0数据节点数据分配x1x2x3x4x5x6x1223910y22531413node-1数据节点数据分配x7x8x9x10x11x1011151616y1516658若k=3；在开始之前,首先创建一个如前所述的全局文件,选取x1(1,2),x2(2,2),x3(2,5)作为中心点。全局文件如下表：初始化后的全局文件迭代次数0Cluster idcluster中心# of data points assignedcluster-0x1(1,2)0cluster-1x2(2,2)0cluster-2x3(2,5)0Map阶段：每个节点读取全局文件,以获得上一轮迭代生成的cluster centers等信息,计算自己的每一个数据点到各
