没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取ScienceDirectFutureComputing and Informatics Journal 3(2018)247e261http://www.journals.elsevier.com/future-computing-and-informatics-journal/使用MapReduce框架对大型数据集进行基于分区的聚类:对最近主题和方向的分析Tanvir Habib Sardar,Zahid Ansari*计算机科学与工程,PA工程学院,印度芒格洛尔接收日期2017年10月28日;修订日期2018年4月17日;接受日期2018年6月12日在线提供2018年摘要数据聚类是科学分析和数据挖掘的基本技术之一,它根据对象之间的相似性来描述数据集基于划分的聚类算法是最流行和最广泛使用的聚类技术。在这个信息时代,由于各个领域的数字化,数据分析人员可以获得大量的数据。这些数据集的快速增长使得十年前的计算平台、编程范式和聚类算法变得不足以从这些数据集中获取知识为了对这样的大数据集进行聚类,Hadoop分布式平台、MapReduce编程范式和改进的聚类算法被用来通过将聚类作业分布在多个计算节点上来缩短计算时间。本文全面回顾了Hadoop和MapReduce及其组件。本文的目的是调查最近的研究工作,分区为基础的聚类算法,使用MapReduce作为他们的编程范式。在最近的许多工作中,传统的基于分区的聚类算法,如K-means,K-prototypes,K-medoids,K-modes和模糊C-均值被修改为MapReduce范式,以获得不同的聚类目标,在不同的数据集,以减少计算时间。本文的贡献是(1)提供了一个概述在现实世界中的大数据集聚类的挑战和MapReduce编程范式及其支持平台的作用,在处理不同的数据集的几个任务的挑战和(2)审查最近的工作在基于分区的聚类使用MapReduce范式为不同的聚类目标,不同的数据集采用不同的策略。Copyright© 2018埃及未来大学计算机与信息技术学院由爱思唯尔公司制作和主持这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。关键词:数据挖掘;分区聚类; MapReduce; Hadoop1. 介绍1.1. 聚类分析数据聚类技术被认为是流行的数据挖掘技术之一。数据挖掘技术被广泛用于从不同的数据集中提取知识[1]。数据挖掘方法提供了有趣和有意义的* 通讯作者。电子邮件地址:tanvir. pace.edu.in(T.H.Sardar),zahid_cs@pace.edu.in(Z. Ansari)。同行审查,由埃及未来大学计算机和信息技术系负责。通过分析大型数据库的模式[2]。聚类或聚类分析是科学数据分析中使用的基本数据挖掘技术之一[3]。聚类也被称为无监督学习,它产生不同的输入数据集聚类,并能够将任何新的输入放入合适的聚类中[4]。聚类的结果导致通过确定数据集的数据点的相似性来确定许多聚类或组[5]。这是这样执行的,使得相同聚类/组中的数据点是相似的,而属于其他聚类/组的数据点是不同的[6]。聚类过程的目标由用户提供的特定需求确定[7]。聚类算法被广泛地应用于不同领域的数据分析和生物数据集,https://doi.org/10.1016/j.fcij.2018.06.0022314-7288/Copyright© 2018埃及未来大学计算机与信息技术学院。Elsevier B. V.制作和托管这是CC BY-NC-ND许可证下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。248T.H. Sardar,Z.Ansari/Future Computing and Informatics Journal 3(2018)247e261数据[8,9]、网络日志数据[10]、图像数据[11]、文本数据、市场数据、电信数据、医疗数据等。聚类技术仍然是数据挖掘过程中的重要研究课题,它基本上是数据挖掘中寻找最佳聚类的持续关注[12]。聚类技术有一些典型的要求,如下所述[13]:聚类算法需要有效地处理大数据量。聚类算法应该从包含二进制、数值和分类数据属性的不同输入数据集提供高质量的聚类。从聚类算法得到的簇的形状应该是任意形状。例如,根据输入数据集聚类结果需要生成椭圆形、聚类算法应该从包含低维或高维数据的数据集大量数据集通常包含缺失、不准确或错误数据方面的噪声。聚类算法被认为是鲁棒的,因为它可以用有噪声的输入数据集产生高质量的聚类由此产生的聚类应该易于理解和明确。然而,所有上述要求实际上是不可能在任何特定的聚类算法.聚类算法根据其用于聚类中数据分类的固有方法可以分为五大类。这些是i)分区算法ii)分层算法iv)基于网格的算法,以及v)基于模型的算法[14]。每个组下的各种算法已经在文献中可用,并有效地应用于现实生活中的数据挖掘问题[15]。最流行和广泛使用的算法可以说是基于分区的,因为与其他技术相比,它易于理解,易于实现并且时间复杂度最小[4]。基于分区的聚类算法创建给定数据集的k个分区,每个分区表示一个聚类。典型的数据聚类过程从一组数据对象开始,并将它们划分为基于相似性距离度量(如欧几里得距离)的k个聚类。由基于分区的聚类实现的一些要求是:i)每个聚类必须由其中至少一个数据对象组成,以及ii)在非模糊聚类算法中,每个对象应该仅存在于一个聚类中[14]。K-means,K-medoids,K-modes和FCM是基于分区的算法的示例[14]。聚类算法也可以分为软聚类和硬聚类[16]。传统的聚类方法本质上是困难的。这里,在聚类过程收敛之后,一个对象必须是单个聚类的一部分。传统的聚类算法被修改与软计算技术,以满足现实世界的聚类要求。这种修改导致它成为一种软聚类技术。因此,硬聚类表示分离数据对象将每个特定的数据对象准确地放在一个组中。在软聚类中,特定的数据对象可以关联到多个组中,并且通过成员关系计算连接到其他数据对象。数据对象的成员值显示了该数据对象相对于特定聚类的方向[17]。模糊集被广泛地与聚类算法结合用于软聚类。它使聚类结果能够展示特定对象与聚类的接近程度。软聚类为每个数据对象分配一个隶属度,其值在0和 1的范围内,具有不同的聚类。模糊聚类是隐式的,比非模糊聚类更能代表聚类的本质[16,18]。如果一个数据对象对于一个特定的集群拥有接近1的成员资格值,那么它表明这个对象适合于那个特定的集群。在聚类质量方面,模糊聚类比非模糊聚类提供更好的聚类。模糊聚类提供了关于数据对象与不同聚类的接近度的更多洞察力和知识。在模糊聚类[19]的情况下,重叠的聚类也可以很容易地通过隶属度值识别。在模糊聚类领域有许多最近的研究工作,以获得不同的聚类目标,如Web日志分析,图像分割和生物信息学等[20]。最流行和广泛使 用 的 硬 和 模 糊 划 分 算 法 分 别 是 K-means 和 模 糊 C-means[21]。1.2. 由于数据规模和并行技术不断增长而带来的挑战多年来,由于业务和制造流程自动化以及更便宜的存储设备可用性,数据集卷正在快速发展。这些由企业生成的大量数据集有时分布在其分支机构中。数据量不断增长的原因之一是Web服务器日志文件维护,它记录用户在特定网站中的活动。分析这些海量的Web服务器日志文件为企业提供了任何特定用户的行为[17]。数据分析师的工作变得难以从几乎所有工作领域[22]产生的大量数据中有效地分析和检索知识,例如生物信息学[23,24],生物医学[25,26],化学信息学[27],网络[28]等等。对这些大型数据集进行有效聚类成为传统聚类算法的一个问题[3]。传统的聚类算法在对如此庞大的数据集进行聚类时需要花费大量时间[14]。现有的数据分析工具在对大量数据集进行聚类时也存在类似的低效率问题[29]。因此,需要可扩展的和并行的聚类算法来有效地对这样大量的数据进行聚类。此外,需要一个并行计算模型来并行聚类如此大量的数据[30]。同时,当数据集大小增加时,计算机处理范例也改变为多核和众核系统。有一个越来越大的转变●●●●●●T.H. Sardar,Z.Ansari/Future Computing and Informatics Journal 3(2018)247e261249JJ并行和分布式机制。MapReduce是Google于2004年提出的一种在一系列连接的节点之间并行处理大型数据集的编程范式。MapReduce通过将任务划分为两个功能块map和reduce来执行任务。MapReduce自动处理map和reduce函数执行所需的输入和输出相关机制[31]。Hadoop是一个框架,它通过基于MapReduce范式编写的应用程序实现高效的大型数据集处理[32]。Hadoop采用主从架构,其中一个主节点协调多个从节点。Hadoop有两个主要部分:存储和处理。存储部分被管理采用Hadoop分布式文件系统(HDFS),处理部分基于MapReduce编程参数进行设计。使用这两个部分,Hadoop可以通过管理节点中数据分布的过程,处理节点中的数据并累积从节点的结果来有效地处理非常大的数据集[33,34]。本文总结了一个文献综述的努力,并行划分为基础的聚类算法使用MapReduce框架。以下是处理大型数据集时面临的挑战如何从现实世界的海量数据中有效地分析和检索知识是数据分析师面临的挑战。在MapReduce范式下,对传统聚类算法进行并行化是一个挑战.1.3. MapReduce框架的不同使用:概述真实世界的数据集,如Web日志数据,图像数据和生物医学数据需要大量的存储空间。有时它包含TB的存储空间。MapReduce[35,36]是在分布式集群和多核系统中对这些海量数据集进行集群的最佳选择[37,38]。许多研究人 员 已 经 进 行 了 使 MapReduce 为 用 户 所 熟 悉 , 并 使MapReduce 最 适 合 处 理 大 型 数 据 集 [31] 。 为 了 通 过MapReduce处理数据密集型[35]真实世界数据集来提高效率,许多最近的项目工作都改进了API,并使用不同的配置参数试验MapReduce[39e45]。MapReduce成功地实现了在不同平台上处理不同应用程序的大型数据集[39,46e49]。虽然MapReduce被设计为在计算节点集群上处理大型数据集,但它也用于为多核计算机开发应用程序[47,50,51]。MapReduce的名字是因为它的执行在很大程度上依赖于两个名为map和reduce的函数。reduce函数的输入是map函数的输出首先将输入数据集划分为多个部分,然后为映射函数分配特 定 的数 据 块 。然 后 将 该 数据 集 的 处理 结 果 馈送 到reducer , 以 进 行 进 一 步 处 理 和 结 果 的 累 积 [52] 。MapReduce模型之所以如此受欢迎,是因为以下原因:最大的优点是它提供了自动的等位基因化和分配。它能容忍错误。可以重试单个任务。为开发人员提供了一个干净的抽象。MapReduce程序通常是用Java编写的,Java是开发人员最流行和最广泛使用的程序之一。● Hadoop提供了标准的状态和监控工具。1.4. MapReduce设计在MapReduce中,数据集的各个部分由映射函数(也称为映射器)单独处理。reduce函数(也称为reducer)提供了来自映射器的结果。通过这种方式,MapReduce通过在映射器和归约器之间划分作业来处理大型数据集[51]。输入到MapReduce的数据集必须首先转换为键和值对,因为映射器和归约器只能以这种格式工作。映射器:(k1,v1)/[(k2,v2)]减速器:(k2,jv2j)/[(k3,v3)]其中,k1,k2分别是输入键和输出键,v1和v2分别是输入值和输出值。k3和v3分别是最终密钥和最终值v2是输出值列表。映射器在输入数据集的不同数据分割上并行执行,并输出键和值的中间对。归约器从映射器获得这些值,并计算每个键的最终值。图1提供了MapReduce的工作方式,包括映射器和归约器。1.5. MapReduce程序执行策略输入数据集被自动划分为原始数据集的子集,并分配给映射器函数,以便在集群的不同节点中进行并行处理。映射器输出的中间值和键然后被分配给归约器。分区数(p)和分区函数由用户指定[53]。当用户的应用程序在MapReduce范式上运行时,会发生以下顺序:(1)应用程序为主节点和从节点创建单独的进程,(2.1)主节点为映射作业分配节点,(2.2)还为Reduce作业分配节点,(3)对输入数据集进行分区,并将每个分区分配给特定的映射器节点,(4)映射器作业的输出相应地存储在本地节点上的文件中,(5)存储在●●●●●●250T.H. Sardar,Z.Ansari/Future Computing and Informatics Journal 3(2018)247e261键1Barrier:按输出键..............最终键1最终键2最终键3价值观价值观Fig. 1. MapReduce概述。本地文件被发送到分配用于归约作业的节点,(6)归约后的最终结果被存储在主节点中。MapReduce执行策略在图中提供。 二、1.6. MapReduce应用程序2008年,Google在100,000个MapReduce进程的帮助下每天处理20 PB的数据[54]。这些数据反过来在短时间内有效地分析其大容量所需的框架。对于这样的问题,最聪明的解决方案之一显然是MapReduce编程范式,它通过将作业分配到多个节点集群中来帮助它并行执行。如1.4节所述,MapReduce被广泛用于在几个问题领域中获得大数据处理的优势[55]。有许多针对MapReduce范式定制的应用程序,图二、MapReduce数据处理策略数据分割1键1键2关键字m映射器1数据分割n键2关键字m制图者键1,中间值减速器键2,中间值减速器键2,中间值减速器T.H. Sardar,Z.Ansari/Future Computing and Informatics Journal 3(2018)247e261251达到一定的目标。其中一些示例包括分析不同类型的日志文件[56]、确定农业规划和使用农药和化肥的作物[57]、从Web服务器日志文件中预处理和提取用户会话[58]、向农民提供作物价格的当前和年度趋势[59]、医学图像分析中的分割和分类[60]等。它也被发现在应用程序中很有用,例如网络图反转[61],SMS消息挖掘[62],编码和解码大型twister代码[63],并行化粒子群优化算法[64],使用广义随机Petri网计算响应时间以分析通信系统的效率[55]和优化空间查询[65]。在表1中,我们提供了一些使用MapReduce并行化的任务的细节:2. MapReduce编程范式2.1. HadoopHadoop[32]是一个开源的分布式计算框架,用于使用MapReduce[51]处理大型数据集。Hadoop在遵循主从架构的连接节点集群中执行程序。主节点对数据集进行分区,将数据集传输到从节点,并在处理后合并从节点的结果。它可以通过由商品硬件组成的节点集群有效地处理PB数据 [51]。 Hadoop由几 个部 分和 子项 目组成 [32,70]。Hadoop的两个重要部分如下所示:HDFS:Hadoop分布式文件系统是Hadoop的存储部分。MapReduce:这是Hadoop用于处理数据的计算范式。HDFS是Hadoop设计的一种高效、容错的分布式文件系统。主节点的HDFS隐式地划分输入数据集,分布在从节点之间,并将最终结果从从节点重新收集到主节点。主节点中的HDFS包含存储所有这些信息的元数据。图3提供了HDFS文件系统的概述。客户端:客户端[71]允许用户访问HDFS文件系统。HDFS主节点:重要的任务,如分割输入数据集,监视和跟踪特定数据分割的从节点扩展,跨从节点均匀分割的数据的复制和传输,管理文件列表以及文件中的块,存储文件的属性和管理其他元数据,由主节点的HDFS执行[51]。HDFS数据节点(从节点):从节点从主节点接收数据分割并存储在其本地HDFS文件系统中。它还维护一个元数据,从HDFS通过发送周期性信号与主HDFS合作,这意味着从HDFS工作正常。从节点也可以根据主节点的指令将块传输到其他从节点。Hadoop可以通过三种方式实现:[72]。独立:在Hadoop的独立安装中,只有一个Java进程执行以提供功能。伪分布式:顾名思义,这种Hadoop安装提供了一种Hadoop执行方式,其中包含主HDFS和从HDFS以及单个机器中的进程。这种实现只能用于开发和测试基于Hadoop的项目,而不能用于实际执行。完全分布式:这是一个真正的Hadoop安装,它在主从架构上提供了一个完整的分布式存储和处理。在完全分布式模式下处理大数据的作业肯定会提供效率,因为所有节点都可以根据各自的存储和处理能力做出贡献。2.2. MapReduce的其他实现以下段落描述了用于实现MapReduce编程范式的不同非Hadoop平台的工作机制:GridGain:GridGain[73]也是MapReduce的开源执行平台。与Hadoop不同,GridGain能够以分布式方式处理实时和非事务性数据。即使是低延迟的应用程序也可以有效地处理网格增益。GridGain提供了一种有效的机制,使得从设备从不等待数据。网格增益是适当的记录和吸引初学者[53]。Phoenix:Phoenix[47]是一个高效的共享内存系统,它隐式地提供容错和资源管理,并使用MapReduce模型工作。它非常适合多处理器和多核[53]。映射器和归约器由Phoenix通过线程制作。除了映射器和归约器之外,Phoenix还使用两个特殊函数,其中一个用于在数据处理作业的每个步骤之前分割数据,另一个用于比较键。Phoenix还使用一个名为scheduler的函数来启动Map- Reduce任务,分配I/O缓冲区位置并运行映射器和reducer线程。Mars:Mars[48]为图形处理单元实现了MapReduce。Mars实际上是通过隐藏GPU的内部复杂性来为其扩展并行计算系统提供标准化编程平台的GPUs[53]。映射器是由火星上的线程设计的还原器。线程分配过程是在MapReduce启动映射器和归约器之前在Mars上完成的,因为GPU不提供线程调度。输入数据集到键,值>对的转换是通过Mars的处理器完成的,因为GPU不直接从磁盘获取数据[48]。一●●●●●●●●●●●表1使用MapReduce并行化的任务。使用MapReduce数据集参考实现的目标向农民数据存储在HDFS中的格式包括商品,市场和地图操作后的日期的唯一ID。用户使用转换后的数据查询不同区域的当前价格。一种特定作物的市场。收集了各种来源的农业数据集在网页抓取工具的帮助下[59]农业规划中的作物确定支持向量机,规则化贪婪森林,决策树。农业数据集[66]改变土壤和作物传感,以确定农药和化肥包括土壤温度、含水率等数据的数字化农场记录农业数据集[57]农作物综合质量的判定农业信息回归。程度指数。它使用矢量回归模型和其他分类器。农业数据集[67]分析Web服务器日志文件,检查成功的客户端请求和Web爬虫请求。所提及带有空值的URL也会被删除。从日志文件中浏览用户会话当页面请求之间的时间超过30分钟时,基于唯一标识和超时拆分IP地址访问的所有页面。分析不同类型的日志文件,实现数据可视化和统计分析通过作业调度算法从美国宇航局肯尼迪航天中心从美国宇航局肯尼迪航天中心电子邮件、Web服务器;防火墙日志、呼叫中心日志[58个][58个][56个]医学图像分析支持向量机:寻找最佳SVM参数。首先,包含所有可能参数的文件产生了组合。后者用作Hadoop作业的输入,其中包含值对的每一行表示一个独立的map任务。ImageCLEF 2011医学数据集[60]基于内容的图像检索高斯密度函数和黄希尔伯特变换。DDSM图像数据库[68]生物医学图像中隐藏有用模式的检测使用聚类潜在语义索引,凝聚层次聚类,球形K均值算法来自PubMed的大量生物医学数据库。[69]第六十九届252T.H. Sardar,Z.Ansari/Future Computing and Informatics Journal 3(2018)247e261T.H. Sardar,Z.Ansari/Future Computing and Informatics Journal 3(2018)247e261253(file名称、区块编号)(区块编号、区块位置)数据集命名空间从指令(块号,字节范围)从状态块数据UNIX文件系统HDFS从节点UNIX文件系统HDFS从节点HDFS主节点客户端应用Block3df2图三. HDFS文件系统。Mars中的线程提供了一个数据集块,使得块的数量等于线程的数量。Map-Reduce-Merge:Map-Reduce-Merge[74]更适合指定为 MapReduce 的修 改, 而不是MapReduce 实现 框架。与MapReduce不同,Map-Reduce-Merge可以同时处理混合类型的数据集[53,74]。Map-Reduce- Merge可以有效地执行关系代数和连接操作。在该模型中,通过专门设计的合并阶段,可以将从归约器获得的结果连接起来。这个合并阶段使Map-Reduce-Merge具有比MapReduce更好的大型数据集处理能力。3. 基于MapReduce的分区聚类研究综述Surve和Paddune(2014)[75]使用MapReduce对遥感图像进行聚类。首先,利用CIELAB颜色空间对遥感图像中的彩色图像进行变换。 因此,首先,原始图像数据集的转换会产生一个文本文件,该文件在每行中表示一个像素及其红色,绿色和蓝色比例。两个颜色比例的差异是用欧几里德距离测量的。有两个MapReduce作业用于建议的K-means中使用的计算,一个作业将像素分配到特定的质心,另一个作业用于像素的误差方差检查。该方法在遥感数据集聚类中的有效性得到了验证。Zhenhua Lv等人(2010)[76]也对包含类似输入数据的数据集进行了类似的实验。一从这项工作的实验中发现的一个重要观察是,将图像转换为文本文件会创建一个大的数据文件,执行时间。为了提高大型数据集聚类的效率,采用MapReduceLi等人(2011年)[52]。这项工作在从UCI机器学习数据集存储库获得的不同图像数据集上进行了实验所提出的算法在图4中提供,并且细节总结如下:1) 从输入数据集空间中随机选择K个点。这些被认为是初始质心值。2) 将数据点子集分配给映射器,以计算数据点和质心的距离3) 在每个数据点被分配到一个质心之后,归约器重新计算质心位置。重复执行步骤2和3,直到新的质心值与旧的质心值相比变得相同。实验结果表明,该方法能有效地生成高质量的聚类.Kumar和Kavavarkar(2015)使用MapReduce范式实现了对文档数据集的有效聚类[77]。由于MapReduce编程模型需要提交给Map-Reduce作业的键和值对,因此选择键作为聚类中心,值是文档数据集的向量空间值Map函数将这两个文件作为输入,HDFS中的初始聚类中心文件形成关键字段,另一个文件由数据集的相应向量值表示组成。从聚类中心到数据集中每个点的距离计算在Map函数中执行,同时记录给定向量最近的聚类。在处理完所有向量后,将向量值分配给相邻的集群。在映射器执行之后,立即重新计算计算,直到它到达收敛点。这个重新计算部分进入Reduce例程,它还重新构造聚类以避免具有极端大小的聚类,即具有太少数据向量或太多数据向量的聚类这些新创建的集群被写回磁盘,磁盘将作为下一次迭代的输入加载。作者声称,所提出的工作有效地聚类了数据集。●254T.H. Sardar,Z.Ansari/Future Computing and Informatics Journal 3(2018)247e261减速器减速器映射器映射器对象质心版本i对象查找最近质心.......................关键词:质心,值:点重新计算质心.......................关键字:oldCentroids,值:质心版本i+1图四、使用MapReduce的并行K-means算法,如Ref.[52]第52段。在文档数据集[33]上的类似工作中,作者在10节点Hadoop集群上设计,实验和评估了基于MapReduce的并行K- Means,称为PK-Means。聚类结果提供了良好的质量集群在减少计算时间相比,传统的K-均值,同时聚类大型数据集。表2提供了PK均值与传统K均值相比所花费的执行时间的汇总。所提出的算法在几个阶段中执行,如下所述阶段1:这个阶段预处理文本数据集,并使用向量空间模型将其转换为规范化的数值数据集。这个任务是通过两个MapReduce进程来完成的。首先,MapReduce过程计算向量空间模型的参数值,如词频-逆文档频率。第二个MapReduce过程从规范化的数据集中提取项,并生成数据集的向量空间。此阶段还指定算法的迭代次数并随机选择质心。阶段2:此步骤使用映射器函数,以便计算质心和数据点之间的距离。由于它产生的数据量很大,因此分配了一个组合器函数,该函数分别计算每个质心的数据点的平均值。合并器的输出被发送到reducer函数。阶段3:此步骤接收阶段2的输出,并使用reducer函数重新计算质心值。阶段2和阶段3的该过程迭代,直到新的质心值变得相同。表2文中给出了传统算法和文献[1]中的PK-means算法的结果[33]第33段。算法采用传统K-means并行K均值使用的计算机110(Hadoop集群)需时间30分钟10分钟虽然上述评论的作品使用了文档数据集,但文献中有许多作品没有使用任何特定的数据集。相反,这些工作是在点的数据集上进行的。在其中一项工作中,作者[78]用MapReduce修改了K-means,以聚类1500万个2-D和3-D数据对象。K-means算法在商用硬件上实现了并行化和集群化。这项研究提供了一个洞察到的事实,作为数据的大小聚类是小的,MapReduce为基础的聚类算法变得无效,在利用数据聚类作业的效率。这是因为MapReduce模型由网络和进程开销组成,这与小数据集的效率有关。然而,这项工作的一个优点是,它使用了一个组合器功能,以提高聚类效率。一个类似的技术在Ref. [79].与之前的研究一样,Matalalia等人也使用组合器。(2014)用于基于MapReduce的K-means聚类[80]。这个组合器函数显著缩小了reducer函数的任务,这反过来又使聚类消耗更少的时间。与基于非合并器的MapReduce实现相比,该算法在1000万个数据点上的执行是高效的。作为一个实验观察,作者发现,在Map-Reduce中,5万个点的洗牌时间接近4 s,50万个点的洗牌时间变为30 s,500万个数据点的洗牌时间为207 s。因此,为了减少MapReduce中洗牌和排序的执行时间消耗,在映射器和归约器之间设计了一个组合器。这个组合器功能演示了一个很好的集群工作的速度Gowru和Potnuri(2015)[81]使用MapReduce修改了K-means:map步骤从序列输入文件中随机找到聚类中心值。迭代发生在输入文件中所有键/值对的每个聚类中心。然后计算距离,并将距离最小的最近中心保留到定义的向量中。然后,将集群中心连同其计算向量一起写入文件系统。约简器接收每个聚类中心的所有相关向量,然后将相关向量值相加,并计算新的聚类均值在这一点上,该算法比较旧的和新的聚类中心之间的值如果质心值不相同,则算法迭代,否则它收敛。Li等人。(2015)[82]在云计算模型中为大型数据集实现了基于MapReduce的K-均值算法。该算法提供了一种有效的初始质心选择方法,以获得高质量的聚类。该算法由两个主要部分组成。第一部分是选择初始聚类中心,并将样本数据集划分为多个分区进行并行处理。第二部分在这些数据分区上分配映射器和归约器。所提出的算法执行如图5所示。在某煤炭集团企业的数据集上进行了实验。实验结果表明,该算法提供了高质量的聚类,而消耗更少的计算时间比传统的K-均值。[83]Quanalia et al. ( 2013 ) [84] 提 出 了 一 种 使 用MapReduce模型进行文本数据聚类的并行K-means。文本T.H. Sardar,Z.Ansari/Future Computing and Informatics Journal 3(2018)247e261255计算每个点到中心的距离,然后比较并选择各自的聚类中心统计每个聚类中心的点数,更新聚类中心数据1分类数据1会聚读取群集中心文件数据片段类数据k阅读cluste环中心文件端用改进的方法初始化聚类中心减少k图n..................结合地图2减少2类数据2数据2减少1地图1地图合并归约图五、建议的K-均值方法如参考文献[82].首先将数据转换为向量空间模型。然后将这个转换后的数据集输入到Hadoop主节点。主节点创建两个文件:一个由从数据集中随机选择的质心值组成,第二个由文本数据集的矢量空间表示组成。这两个文件由主节点发送到从节点。从节点中的映射器计算质心和向量之间的距离,并根据其计算的较小距离将向量分配给质心。然后,通过归约器重新计算质心值来执行这些聚类的重构。这项工作没有实现映射器和归约器之间的任何组合器。本文也没有给出聚类的实验结果,如按比例放大、聚类放大等。Zhao等人。(2009)[84]提供了一种使用MapReduce的K-means修改,称为PK-Means。本研究的工作流程设计与[83]的先前综述相似,不同之处在于本工作设计有映射器和归约器之间的组合器功能。由于合并器的有效使用,减少了网络通信开销。作者使用加速,放大和放大的比较,以评估所提出的算法的效率。这项工作被发现有效地聚类大型数据集使用Hadoop集群的商品硬件。据观察,聚类的结果在加速方面不提供线性相对于数据大小的增加。作者指出,这种非线性的主要原因是Hadoop集群节点之间的通信开销。作者没有指定用于实验的数据集的类型。为了有效地聚类大型混合类型数据集,HajKacem et al.(2016)[85]建议修改使用MapReduce的K-prototype算法。在映射器中采用了一种修剪技术,称为三角不等式方法[86],在这项工作中使用该方法来减少K原型的距离计算。在映射器中计算聚类中心与数据对象之间的距离,在约简器接收到映射器的输出后重新计算聚类中心。聚类提供了相对于数据集大小的增加的线性加速。实验结果还表明,该算法仅在输入数据对象大于200万时才有效。Srinivasulu等人。(2015)[87]使用MapReduce并行化K-medoids。映射器提供了一个全局数组,其中包含随机选择的medoids对象。基于这些中心点,映射器计算与其他数据对象的距离。使用组合器函数,从映射器收集中间结果。由于组合器在同一节点上工作,因此减少了归约器的通信开销。然后将中位数和质心提取到归约器,在那里执行中位数的重新计算K-medoids算法解决了K-means算法在噪声数据聚类中的不足,但K-medoids算法执行时间长,对大数据集的聚类效率不高。为了解决K-中心点的不足,作者在文献[88]中提出了一种并行K-中心点算法,称为HK-中心点算法。这项工作中使用的技术类似于参考文献[87]中的综述。本文聚类的数据集是经典的虹膜特征数据集。算法HK-medoids是有效的,并获得了线性加速比。HBase使用HDFS的分布式模型提供稀疏信息的有效存储。作者Yue et al. (2016年)[89]已经使用MapReduce修改了K-medoids,命名为K-medoidsMapReduce,并在空间数据集上进行了实验输入256T.H. Sardar,Z.Ansari/Future Computing and Informatics Journal 3(2018)247e261分布式缓存....洗牌和排序图n地图2地图1空间数据集以有序的坐标文件的形式保存在HBase上。map函数的键是HBase数据集中的行号,值是对应坐标的字符串。空间点被分割并发送到映射器。 因此,中心点和数据对象之间的距离是并行计算的。所有初始medoids都存储在medoids文件中,并作为输入提供给映射器。映射器使用质心和数据对象之间的距离计算来计算中位数。在从映射器接收质心和相应的数据对象坐标之后,归约器重新计算质心值。聚类结果表明,K中心对大数据集的聚类是有效的。为了使用基于MapReduce的并行K模式对数据集进行聚类,Tao等人。[90]首先从数据集中随机选择K个初始分类对象。这些模式被输入到映射器函数,该映射器函数计算数据对象和模式之间的距离,然后基于它们之间的最高相似性将对象分配到集群。本文给出了从m个映射器到n个归约器的结果。Reducer进程将生成X个HDFS文件,其中包含X个分类集群,其中每个X都是从集群的模式中获得的。该研究是在美国人口普查数据集上进行的,并证明了大型数据集聚类的计算时间加快。该研究还表明,所提出的技术是等效的计算时间为小数据集的聚类。Garg等人使用MapReduce并行化模糊C均值。(2015)[91]。在本工作中用于生成数据点的Canopy方法也使用Map-Reduce进行了并行化。冠层生成的数据对象被认为是质心和矢量的数据对象。在这项工作中的映射器计算从质心和冠层生成的数据对象的距离,并分配的成员资格值相对于质心的每个数据对象。映射器将具有最高隶属度值的数据对象分配到聚类中,并将结果传递给归约器。reducer重新计算质心值并再次迭代地馈送到映射器,直到达到partic。在MapReduce中实现的算法如下:Map- pers计算距离和溢出出 来一K-means 的 key-value pair centroid_id ,datapoint>。这标识了数据点与聚类的关联性。另一方面,Reducer使用特定的cluster_id和与之关联的数据点列表。新的均值是在Reducer的帮助下计算的,Reducer也会写入新的质心文件。现在,用户可以选择要使用的迭代次数、算法终止方法或与前一次迭代中的质心进行比较图6中显示了本工作中使用的MapReduce上的K-均值的单个迭代方法。然而,这项工作需要许多MapReduce作业来进行聚类,这需要大量的计算需求[94]。Ghadiri等人(2016)[94]通过名为BigFCM的经典FCM的增强解决了使用Map- Reduce的并行FCM的上述缺点。数据对象与质心的关联性由权重指定。映射器从数据集中随机选择聚类中心,并将预处理的记录传输到另一个MapReduce进程:combiner。如果有多个组合器,则使用键定义它们。Combiner通过从缓存中获取质心并从映射器中获取数据对象来执行FCM。大FCM组合器为每个质心的对象提供权重还原器重新计算并发现新的质心。reducer输出由单个reducer收集,该reducer组合结果并发现最终的质心。实验结果表明,该算法在计算时间方面更快,并生成高质量的聚类。该算法的整体过程如下图所示。第七章在表3中,我们提供了最近使用MapReduce进行基于分区的集群的一些工作的细节。输入数据集一般迭代 这项技术的结果表明,加速大型数据集。FCM的停止准则是它将继续执行,直到质心不改变其值超出收敛阈值,并且分配给质心的数据对象也不改变。对于重叠集群的大型数据集而言,这种迭代次数的增加对于内存中的数据管理来说是有问题为了解决这个问题,Mathew和Materran(
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功