陈笑[1]2016年在《基于Mahout的并行化k-means聚类算法优化研究》文中指出聚类分析是从大量数据中获取有效信息的重要手段,用于聚类分析的算法称为聚类算法。k-means聚类算法具备简单、快速、有效等诸多优点,是使用范围最广泛的经典聚类算法之一。如今,快速发展的互联网产业导致了数据量的剧增,传统k-means算法已无法满足海量数据的聚类需求,因此,k-means算法MapReduce并行化以及针对并行化k-means算法的优化研究尤为重要。本文将探讨并行化k-means算法的实现方式,并以此为基础采用适合海量数据处理需求的算法优化策略,目标是降低算法时间和空间复杂度的同时获取更优质的聚类结果。本文从k-means算法优化与并行化的研究现状出发,分析了目前k-means算法优化方法主要是针对串行k-means,与此同时k-means并行化研究主要围绕算法设计展开,由此可知现阶段国内外对并行化k-means算法的优化研究尚属薄弱环节,因此本文确立了采用时间复杂度较低的算法对并行化k-means进行优化的研究思路。作为铺垫,本文介绍了分布式开源框架Hadoop、编程模式MapReduce以及提供协同过滤、聚类、分类等大规模机器学习算法分布式实现的算法库Mahout;然后着重研究了k-means算法原理、算法缺陷以及它在Mahout中的并行化实现方式;最后,采用针对并行化k-means算法优化方法,即利用时间复杂度极低的“粗聚类”算法Canopy对并行化k-means进行优化。在算法性能测试阶段,本文利用Mahout算法库提供的算法驱动等接口将Canopy优化前后的k-means算法予以实现,并将优化前后的算法应用在Hadoop分布式测试平台上,采用控制变量法调整参数,将算法应用在呈高斯分布的数据集上进行聚类性能测试。分析实验数据可知,优化算法的聚类性能明显更优——在保证算法效率的前提下,以更少的迭代次数收敛于更准确的质心,并且在算法稳定性方面也有显着的提升。总体来看,基于Canopy的k-means算法优化效果明显。
刘建红[2]2017年在《基于Hadoop平台的聚类算法并行化研究》文中进行了进一步梳理随着信息技术的高速发展,大型商业数据库和互联网都积累了一定规模或者超大规模的数据,这些数据包含着丰富的信息内容。人们迫切希望从这些庞大的数据中发现对其生活、工作有益的潜在信息,如何快速准确地分析现有数据,最大程度地获取其蕴含的价值,已经成为许多公司和学者共同面对的问题。聚类算法在所有的数据挖掘方法中占有举足轻重的地位,是将待分类对象从未知过渡到已知的有效措施。Hadoop是一种开源的能够运行在大量节点之上的分布式系统,Map Reduce计算模型是其生态环境中的重要组成部分,与以前的并行计算模式相比,它能够极大地简化分布式并行化程序的开发过程。本文主要工作以及创新点如下:(1)针对串行化的Kmeans算法处理海量数据集效率低下的问题,本文设计了基于Hadoop的Kmeans并行化算法,并对其实现细节进行优化,从而进一步提升算法处理海量数据的性能。优化策略主要有:对输入数据进行min-max标准化处理;调整HDFS数据块大小;在Map阶段和Reduce阶段中间添加Combine过程,通过对Map阶段输出结果进行合并来减少数据节点间的通信。(2)针对Kmeans并行化算法指定初始聚类中心随机性的问题,本文采用Canopy算法快速聚类得到一组初始聚类中心,同时针对Canopy算法的区域半径盲目取值会造成canopy中心点不准确问题,本文提出了改进的Canopy-Kmeans并行化算法。主要改进有:提出区域半径的估值方法来改善canopy中心点的选取,从而减少算法迭代次数;优化Kmeans迭代过程来减少整体计算量,进一步提高迭代速度;删除数据集中的孤立点,得到更准确的初始聚类中心。(3)通过搭建Hadoop平台对基于Map Reduce的改进Canopy-Kmeans并行化算法进行了一系列的测试来验证其性能。实验结果表明:改进的Canopy-Kmeans并行化算法是有效的、收敛的,且可以进一步提升聚类准确率,减少算法迭代次数;该算法具有良好的可扩展性和加速比性能,进一步验证了本文设计的并行化算法适合处理海量数据集。
严正飞[3]2014年在《基于HADOOP云计算平台的聚类算法研究》文中研究指明随着移动互联网的迅速发展,数据量呈现爆炸式增长趋势,“大数据”时代已经到来。如何准确、有效地分析利用现有数据,最大限度地发掘其价值,已经成为学术界、企业界共同的难题。传统的数据分析方法显然无法有效地处理大数据,人们迫切需要新的数据处理方法。云计算技术应运而生。云计算是多种技术及商业模式的统称,其中,由Google公司最早提出的MapReduce技术是云计算技术的重要分支。MapReduce计算框架是一种并行的计算模型,相比于传统的并行计算思想,MapReduce能够大大地简化并行程序的开发,它对底层的数据分割、任务调度、并行处理、容错等问题都进行了封装。因此程序员不需要考虑复杂的底层机制,只需把焦点集中在问题本身上。聚类分析算法一直都是数据挖掘中的重要内容,能够有效地将数据归类,进而提取出有用信息。Kmeans算法是聚类分析中的常见算法,与其他算法相比有着天然的优势,比较容易实现并且常常能取得令人满意的效果。本文在云计算技术的背景下,尝试将MapReduce技术应用于聚类算法的分析。本文重点剖析了MapReduce计算的原理,并重点讨论了基于MapReduce技术的并行Kmeans算法及Canopy-Kmeans算法的实现。为了验证MapReduce的思想及所提出的并行Kmeans算法的有效性,本文搭建了开源的Hadoop云计算平台进行多组实验。最终结果表明,基于MapReduce技术并行的Kmeans算法及Canopy-Kmeans算法具有较好的加速比和可扩展性。而且,在hadoop云计算平台上实现的Canopy-kmeans算法相比于Kmeans算法,聚类效果更好,收敛速度更快。
梁彦[4]2014年在《基于分布式平台Spark和YARN的数据挖掘算法的并行化研究》文中提出现代互联网信息中含有极为丰富的商业价值，如何从这些海量数据中挖掘出有用的信息是一个重要的课题。而“信息爆炸”产生的海量数据在传统计算机上进行聚类分析处理需要耗费大量的时间，不能满足现今的商业需求，结合云计算平台的并行化改进能有效解决这一问题。由加州伯克利AMP实验室新开发的内存计算分布式框架Spark主要针对海量数据处理和机器学习。相较于传统并行计算框架，其内存计算的特性能很好的适应迭代计算，同时在数据切分、并行处理、容错健壮性方面进行了封装，能良好的适应于并行化计算开发。k-means算法是一种被广泛应用的聚类分析算法，一般采用误差平方和准则函数作为聚类准则，在处理数据集时效率较高且聚类效果良好。但面对海量数据规模时，计算海量数据对象间距离时遇到瓶颈，数据规模变大，迭代计算次数增加，计算耗时过长。同时算法本身存在k值不确定、初始聚类中心点随机性选取的问题，会影响聚类结果的准确性和算法效率。为了突破面对海量数据时的计算瓶颈，本文在Spark平台上实现k-means算法并行化。针对k-means算法的不足，本文使用canopy算法对k-means算法进行优化提高算法效率和聚类结果的准确性，并在Spark平台上实现canopy-kmeans算法的并行化。对基于Spark平台的k-means并行算法和canopy-kmeans并行算法在准确性、加速比、扩展性、与其他平台性能进行了比较。实验结果表明，算法并行化后得到较好的聚类结果，在面对海量数据时有较好的加速比和扩展性。与Hadoop平台比较，基于Spark平台算法并行化效率更高。而Spark平台执行需求资源不同的聚类任务时，在资源管理平台YARN调度任务相较于资源管理平台Mesos有更高的执行任务效率。研究表明，结合Spark+YARN平台实现并行化是可行高效且具有现实意义的。
付启沐[5]2016年在《基于可重构硬件架构的MapReduce计算方法研究与实现》文中研究说明随着互联网的飞速发展,信息量的爆炸式增长,需要高效的科学计算,以满足快速挖掘有价值信息的需求。在传统的计算机上处理海量的数据需要很长的时间消耗和能量代价,如何快速高效利用好海量的数据成为各行各业所面临的严峻考验。高效利用海量数据挖掘出有价值的信息成为工业界发展的必然选择。由Google实验室提出的MapReduce编程模型是一种快速、简洁、高效的大数据的处理方法。其通过对大数据块进行子任务划分、任务调配、并行化处理、容错处理等进行封装,很大程度上简化了并行程序的设计,目前已在Google、 Facebook、阿里巴巴等公司的许多项目中得到应用。相比较而言,传统的计算机其有限的运算单元和存储带宽,束缚其性能和功耗无法满足日益推成出新的应用需求。可重构计算架构的处理系统兼顾了专用集成电路的高效性和通用处理器的灵活性的优势,其可高效并行处理计算密集型应用的特点,成为解决并行计算多样性需求的有效途径。本文针对高效处理海量数据的场景下,对MapReduce编程模型和可重构计算技术进行了深入的研究；提出了将MapReduce编程模型与可重构计算技术相结合的研究方案；选取了Kmeans聚类算法和FIR滤波算法两种典型的算法作为目标算法；设计了Kmeas聚类算法和FIR滤波算法的MapReduce编程,完成了这两种算法在可重构硬件架构上的映射。完成了上述算法在可重构计算平台和通用计算平台ATOM230上的性能对比实验,实验结果表明：在可重构计算平台上实现基于MapReduce模型并行化的Kmeans聚类算法和FIR滤波算法在运行时间上较ATOM230通用计算平台分别提升3.2倍和2.6倍。
袁小艳[6]2016年在《ABC_Kmeans聚类算法的MapReduce并行化研究》文中研究指明随着数据的海量增长,数据聚类算法的研究面临着海量数据挖掘和处理的挑战;针对K-means聚类算法对初始聚类中心的依赖性太强、全局搜索能力也差等缺点,将一种改进的人工蜂群算法与K-means算法相结合,提出了ABC_Kmeans聚类算法,以提高聚类的性能;为了提高聚类算法处理海量数据的能力,采用MapReduce模型对ABC_Kmeans进行并行化处理,分别设计了Map、Combine和Reduce函数;通过在多个海量数据集上进行实验,表明ABC_Kmeans算法的并行化设计具有良好的加速比和扩展性,适用于当今海量数据的挖掘和处理。
闫萌[7]2018年在《电信运营商移动终端信息分析系统设计与实现》文中研究指明研究电信客户的分类问题,根据不同的客户类型采取不同的经营策略,是电信运营商目前的重点战略之一。根据终端的特性对客户进行细分,挖掘其中潜在信息也成为电信运营商的重要工作之一。目前,每日产生海量与终端相关的数据。仅河北联通一天新入网终端数据,就达几十万条,日新增数据数据超过1GB。而运营商现有架构较为传统,不足以支持日益增加的数据的存储与精准分析。因此,本课题从运营商所持有的由SIM卡记录的终端数据入手,针对日益增加的终端信息数据,在现有数据的基础上,根据用户的终端信息,用户订购套餐信息等设计维度表,并基于面向终端信息分析的主题进行集成,构建数据仓库,并对传统的挖掘算法进行改进并在Spark平台上进行了实现。本课题针对运营商现有的终端数据的数据存储方式进行改进,引入分布式集群,利用其可横向拓展的特性,构建数据仓库,使之可支撑对TB级数据的长期存储。同时,本课题重点根据电信终端数据无标签的特点,选取无监督学习方式对之进行了挖掘。一方面,提出基于Spark的K-means优化算法,引入前置算法canopy算法对数据进行预聚类,优化K-means算法初始中心的选取,并将优化后的K-means算法利用Spark的RDD编程模型予以实现;另一方面,针对K-means算法对非凸数据不敏感的特性,本课题选取另一种聚类算法DBSCAN算法,并提出了利用KD树对数据集进行划分,提高分布式集群处理效率的方法。将改进后的算法在Spark平台上进行了实现。对改进后的两种算法选取集成后的数据仓库中的部分数据进行了试验,并与单机版算法与未改进的算法分别进行了对比。针对电信数据集,相比串行算法及未经改进的算法,改进后的K-means算法准确率提升了 5%左右,且对于10^6级别以上的数据规模,聚类效率有所提升。对于DBSCAN算法,在10^6级别以上数据,聚类效率有所提升。通过本文方案建立的大数据终端信息分析系统,比传统的分析系统具有更高的效率和准确率,能够帮助电信运营商制定更好的经营策略。
程堃[8]2015年在《基于云平台的聚类算法并行化研究》文中研究指明聚类算法是数据挖掘中的重要内容,能够从数据中提取出隐藏的有用信息和知识来为人们服务,在工业、商业以及科研领域都得到了广泛应用。随着当今社会数据量急剧增加,单机聚类算法的计算能力渐渐无法满足需求,广大互联网公司为了从激烈的商业竞争中脱颖而出以获得商业成功和大量的经济利益,纷纷为大规模数据的处理寻求有效策略,于是多台计算机共同参与运算的分布式聚类算法成为当前研究热点。云计算平台是一个优秀的新型商业计算模型,通过虚拟化技术把互联网中的节点资源相融合来提供优越的计算能力,并且能够根据计算任务中任务量的实时变化情况来动态扩展集群中的节点。系统将待处理的计算任务合理分配到计算机集群中的节点上,根据实际需求得到所需的存储空间和计算能力等资源,用户在无需理解云内部的知识和细节的情况下也可以使用云平台中的基础设施。Hadoop作为Apache基金会开发的开源云计算平台,以一种高效可靠可伸缩的方式处理数据,此外还具有高容错性和低成本等优点,是一个能够分布式处理海量数据的软件框架。Hadoop核心设计是底部HDFS(分布式文件系统)和上层MapReduce(编程模式),分别为海量数据提供存储和计算。本文主要研究如何运用云平台中大量计算机节点的并行计算能力来解决大规模数据聚类的难题。针对Kmeans算法中一些不足之处提出改进:采用Canopy算法作为Kmeans聚类的初始步骤,并基于“最小最大原则”优化初始聚类中心的选取;对Kmeans迭代过程加以优化使整体计算量得到降低,进一步提高算法效率。详细分析DBSCAN算法在参数选择,内存使用、I/O开销等方面存在的问题,提出了一个基于层次的优化算法。既解除了因参数选择不当而对算法效率造成的影响,还在一定程度上降低了查询次数从而减小I/O开销。最后,通过搭建Hadoop平台分别对基于MapReduce的Kmeans和DBSCAN并行优化算法进行一系列的测试实验来验证性能。实验表明:Kmeans优化算法在迭代速度及聚类结果准确率上有所提升;DBSCAN优化算法在正确率和实效性方面均得到改善;并且通过加速比实验证明本文的并行算法更适合处理大规模数据集。
余相君[9]2017年在《布谷鸟搜索改进的K-means聚类算法及其并行化实现》文中提出随着计算机和互联网技术的迅速发展,数据量呈爆发式增长,海量数据的高效处理和利用成为当前社会面临的最艰巨任务之一;同时如何高效率、低成本、准确地从现有的海量数据中挖掘出潜在、有用的知识是数据挖掘领域研究面临的一大难题。以K-means算法为代表的聚类分析是数据挖掘领域最重要的研究方向之一,K-means是一种典型的基于划分方法的聚类算法,具有思路简单、收敛速度快、时间复杂度近似于线性等特点,较适合应用于海量数据的聚类;群体仿生优化算法能够利用群体优势、并行搜索,以全局寻优的方式快速获得优化问题最优解,被认为是目前处理K-means聚类优化问题最行之有效的方法。当前已有很多学者基于多种不同的群体仿生智能算法对K-means聚类算法进行优化,但现有的K-means聚类改进算法还存在以下两个问题需进一步完善:(1)聚类过程中的全局寻优能力不够突出,容易陷入局部最优;(2)在数据量较大时的聚类效率不高,没有充分利用服务器集群优势。作者所做的主要工作包括:(1)提出一种新型元启发式基于仿生行为的改进的布谷鸟搜索算法(Quantum-based Adaptive Cuckoo Search,QACS),解决了原始布谷鸟算法搜索步长的自适应性问题,并引入量子运算使该算法的搜索方向具有一定的倾向性。(2)针对K-means聚类算法易陷入局部最优的问题,将新算法QACS与K-means聚类算法相结合,提出了一种新的串行K-means聚类算法(K-means clustering algorithm based on QACS,QACS-KMeans),提高了K-means聚类算法的全局搜索能力;(3)针对K-means聚类算法在处理较大数据量时效率较低的问题,利用Hadoop分布式平台的MapReduce编程模型实现了对新算法QACS-KMeans的并行化处理。通过在虚拟机中搭建的Hadoop伪分布式集群对不同样本数据集分别进行10次准确性实验和效率实验,结果表明:(1)并行QACS-KMeans新算法聚类的平均准确率在实验所采用的6种UCI标准数据集上,相比原始K-means聚类算法、利用粒子群优化算法(Particle Swarm Optimization,PSO)改进的K-means聚类算法和自适应布谷鸟搜索(Adaptive Cuckoo Search,ACS)改进的K-means聚类算法都有所提高;(2)并行QACS-KMeans新算法聚类的平均运行效率在实验所采用的5种大小递增的随机数据集上,当数据量较大时,显着优于原始K-means串行算法,稍好于并行PSO-Kmeans算法和并行ACS-KMeans算法。实验结果表明,当数据量较大并且维数较低时,利用并行QACS-KMeans算法的聚类效果较好。
林超[10]2013年在《基于成对约束的半监督聚类算法研究及其并行化实现》文中指出作为数据挖掘领域中的一种重要方法,聚类分析能够发现数据对象自然的分布结构。它根据数据对象之间的相似性,把数据对象分割成簇,并保证同一簇内中数据的相似性尽可能大,而不同簇间数据的相似性尽可能小。从机器学习的角度来看,聚类分析是一种无监督的学习方法,它按照一定的优化准则对数据进行分割,对数据的分析不需要知道其相关的背景知识。但是,现实生活中我们对数据的信息并不是一无所知,并且我们发现通过这些少量的已知信息能够找到数据对象标识或相互之间的约束信息。半监督聚类就是在传统的无监督聚类算法中引入先验知识来指导聚类过程,提高聚类结果精度。本文选择引入成对约束作为先验知识来协助指导聚类过程,分别建立了Must-Link和Cannot-Link约束组,用以描述两个样本数据间的关系。其中,Must-Link代表两个样本数据必须被分配到同一划分,而Cannot-Link则代表两个样本数据必须被分配到不同的划分。详细介绍了基于成对约束的半监督聚类算法Cop-Kmeans,对算法比较常见的约束违反的问题,提出了全新的改进方法,在解决约束违反的同时,算法的运行时间效率也优于传统的改进方案。此外,针对成对约束自身特征可能给聚类性能带来的不良影响,进一步提出了相应的改进方案,能够最大限度的削弱这种不良影响,从而能够在一定程度上改善聚类结果精度。考虑到当聚类对象是一个大数据集或者高维数据类型时,传统的单机串行聚类算法无论是在内存或者运算能力都无法满足实际需求。本文选择运用“云计算”思想,采用并行处理方式处理大规模的数据集。我们利用MapReduce计算模型对改进的半监督聚类算法进行并行化实现,并在Hadoop搭建的并行处理平台上处理大数据集。实验结果表明,采用并行计算方式能够显着提高聚类效率。
参考文献：
[1]. 基于Mahout的并行化k-means聚类算法优化研究[D]. 陈笑. 华中科技大学. 2016
[2]. 基于Hadoop平台的聚类算法并行化研究[D]. 刘建红. 吉林大学. 2017
[3]. 基于HADOOP云计算平台的聚类算法研究[D]. 严正飞. 南京大学. 2014
[4]. 基于分布式平台Spark和YARN的数据挖掘算法的并行化研究[D]. 梁彦. 中山大学. 2014
[5]. 基于可重构硬件架构的MapReduce计算方法研究与实现[D]. 付启沐. 北京交通大学. 2016
[6]. ABC_Kmeans聚类算法的MapReduce并行化研究[J]. 袁小艳. 计算机测量与控制. 2016
[7]. 电信运营商移动终端信息分析系统设计与实现[D]. 闫萌. 北京邮电大学. 2018
[8]. 基于云平台的聚类算法并行化研究[D]. 程堃. 南京邮电大学. 2015
[9]. 布谷鸟搜索改进的K-means聚类算法及其并行化实现[D]. 余相君. 重庆大学. 2017
[10]. 基于成对约束的半监督聚类算法研究及其并行化实现[D]. 林超. 西南交通大学. 2013
标签：计算机软件及计算机应用论文; 大数据论文; 聚类论文; 云计算论文; k-means论文; mapreduce论文; 层次聚类方法论文; 分布式算法论文; 并行处理论文; 海量数据论文; 无监督学习论文; 分布式架构论文; 分布式技术论文; 分布式处理论文; 分布式开发论文; k-means算法论文; 算法论文; 数据处理论文; hadoop论文;