有关基于Spark平台的K-means聚类算法改进并行化实现毕业论文写作资料-论文写作网

简介:关于本文可作为相关专业算法数据论文写作研究的大学硕士与本科毕业论文算法数据论文开题报告范文和职称论文参考文献资料。

算法数据论文范文

摘要：针对K-means算法在数据聚类过程中初始值选取的随机性问题,基于非均匀采样原则对该算法进行改进.同时,针对聚类算法并行化的需求,基于Spark平台对改进算法进行了并行化实现.单机串行处理和集群并行化实验证明了该改进算法在处理海量数据集时具有更高的准确性和稳定性,且在Spark平台上的并行化实现具有良好的加速比和可扩展性,从而表明该算法能在实际的海量数据处理中高效运行.

关键词：K-means；聚类；Spark；并行化

1. 引言

聚类是按照“物以类聚”的思想将数据集合分成若干类或簇,使得每个簇中的数据最大程度地相似,属于一种无监督的学习过程.聚类分析是数据挖掘中的一种常见技术,广泛地应用于市场营销、商品推荐、顾客分类、模式识别、过程优化、数据挖掘、信息安全、配方设计、空间分析、图像处理和Web文档分类等众多领域.常见的聚类算法主要包括K-means算法、K-medoids算法、Clara算法和Clarans算法等,其中,K-means算法因为简单、收敛速度快、易于实现等特点而被广泛使用.从K-means算法提出至今,已有半个多世纪,事实表明,K-means算法仍然是目前最流行的聚类算法之一.在K-means中,初始化选值是获取一个良好解决方案的关键,因此在面对未知数据集时,如何选取合适的初始聚类个数就成了K-means算法需要解决的问题.

Zhang Tian等提出了一种基于Canopy预处理的Canopy-Kmeans算法,其算法思想是针对一个数据集,将原始数据集合List按照一定的规则进行排序,初始阈值为T1、T2,且T1>,T2,在List中随机挑选一个数据向量A,计算A与List中其他样本数据向量之间的距离d,将数据点距离初始中心(d<,T1)的数据划入该聚类,这类数据聚类结束不再划分；将数据点距离初始中心d(Tl<,d<,T2)的点划入该聚类中心所属的Canopy.完成Canopy算法预处理,每个点都被划人其所属的Canopy,部分数据点存在属于多个Canopy的情况,再使用传统的聚类算法K-means对预处理后的数据进一步处理.然而Canopy中心点选取过密容易导致算法陷入局部最优,其区域半径大小直接影响算法的执行效率和分类准确率,具有较大的盲目性与随机性,并没有从根本上解决初始选值的问题.在互联网发展日新月异的当下,传统的K-means聚类算法不仅要面对初始选值的问题,还要面对单处理节点无法适应海量数据处理的问题,因此,有必要改善该算法并将其并行化运行在大数据处理平台上.

毛典辉提出了一种基于MapReduce的Canopy-Kmeans算法,将算法迁移到Hadoop大数据处理平台上,运用HDFS分布式海量存储和MapReduce分布式计算框架并行处理K-means程序.运用Hadoop平台能够充分利用集群并行化处理的优势,可以在很短的时间内高效地计算出聚类结果.然而,MapReduce是一种基于HDFS的计算框架,在每次的计算过程中需要反复对磁盘进行存储、读取等工作,因此在海量数据过程中,进行一次MapReduce运算往往需要耗费大量时间.

2009年,UC Berkeley AMP Lab提出了一种基于内存的大数据分布式处理框架Sparkc.在Spark程序中,数据在处理前被预先写入内存,由于内存的读取速度远快于磁盘,同时,Spark程序执行过程中使用有向无环图(DAG)的方式,并不计算程序的各个中间结果.基于以上两点优势,Spark在面对海量数据处理时具有运行快速、容错能力强等优势.本文正是采用了Spark平台以上的优势,并且将K-means算法加以改进,最后通过实验验证了改进算法在Spark平台上的高效性.

2.相关理论和技术

2.1 Spark大数据计算框架

Spark大数据处理并行框架基于MapReduce的思想实现分布式计算,不同于MapReduce基于磁盘的运行模式,Spark是一种基于内存的计算,且通过DAG的计算,在程序执行的过程中节省了大量的磁盘读取和存储时间.Spark能更好地运行数据挖掘、机器学习等需要反复迭代的MapReduce算法.Spark计算模型如图l所示.

在Spark计算模型中有两个重要的概念：弹性分布式数据集(RDD)和DAG.RDD是逻辑集中的实体,但在集群中的多台机器上进行了分区.通过对多台机器上不同RDD联合分区的控制,就能够减少机器之间的数据混合(Data Shuffling).图1所示的矩形框就是一个RDD,其中的小矩形框就是数据的不同分片.Spark提供了许多RDD算子,如map、reduce、union、filter、reduceByKey、partitionBy、join、count等,正是通过这些算子完成了RDD的转换过程,RDD可以随意在RAM中进行缓存,因此它提供了更快速的数据访问.在RDD转换过程中,从数据集读取到结果存储形成的每一个箭头构成了一个DAG,在数据处理过程中,数据流会随着DAG的方向流动,在流动过程中,集群并不会计算中间结果,而是要等待Action类型的算子触发后再计算,在计算过程中节省了大量对磁盘的操作.因此,Spark计算框架更加适用于实时处理等数据挖掘工作.

算法:数据结构与算法01 浙江大学全60讲零基础自学

2.2 K-means聚类算法

本实验使用了3个不同类型的数据集,数据集皆为UCI实验室提供的分类、聚类数据.通过查准率、误差平方和来评价聚类算法的聚类效果并进行对比试验；通过测试加速比来测试改进算法的并行性能.

5.2聚类效果实验

本实验主要通过4个不同类型的已分类数据集进行测试,通过统计聚类结果与标签计算出本算法的聚类准确率,4个数据集详情见表2.

统计结果见表3.横向比较实验结果可以看出,改进算法无论是通过串行实现还是并行实现,在查准率方面都有所提高,平均提高了4%,这说明改进算法通过采样得到的聚类中心能够很好地代表它所在的聚类；纵向比较可以看出,通过在分布式集群上运行相同的算法,查准率并不会因为分布式数据分散的原因而影响最终的聚类结果,这表明分布式处理具有良好的准确性和稳定性.

聚类结果误差平方和SSE如图6所示.根据式(3)的定义,SSE越小表明聚类数据之间的关系越紧密,聚类效果越好,图6中改进算法无论对于哪个数据集都有比K-means更好的聚类效果.

5.3并行性能试验

加速比是指在数据集规模固定的条件下,通过计算任务执行串行时间与并行时间的比率来判断并行效果,加速比越大则表明集群并行化效果越好,本实验加速比测试结果如图7所示.

从实验结果可以看出,不同数据集在实际测试中并行加速的效果并不相同,主要原因在于数据集的大小,根据HDFS对于数据的分片原理,以64 MB为单位,当数据集小于64 MB时,集群只会将该任务分发到集群中的某一个节点执行,因此节点数的增加并不会提高任务的执行效率,相反,由于任务分发过程也需要消耗时间,因此节点增加反而会提高运行时间,Wine数据集的加速比结果很好地体现了这种状况.但对于更大规模的数据集来说,随着节点数量增加,加速比呈线性增长的趋势,直到节点数增加到一定量之后,加速比就不再增加.如Car Evaluation数据集的测试结果,加速比在3个节点后就不再增加.因此在实际测试中,只需要根据数据集的大小选择合适的节点个数,就可以快速地得出实验结果,避免资源浪费.

3D Road Network数据集分别采用K-means算法与改进算法的任务运行时间如图8所示,由图可知,改进算法所需的执行时间小于K-means算法,这是因为通过采样,数据集的规模比原始规模缩小了许多,在时间上有14%～1970的优势.

5.4 系数K与a的选择实验

在改进算法中,引入了采样参数a,正是通过过采样的方法,数据集预处理后的l+a logφ数据点才能更好地体现集群聚类的真实情况.本节设置不同的a/k比值,通过观察误差平方和大小SSE来判断最优的a/k比值,实验结果如图9所示.

随着a/k比值的逐渐增大,聚类结果误差平方和逐渐降低,这样的结果是可以预见的,这是因为比值越大,数据采样阶段采样的结果越多,采样结果更能全面地反映原数据的真实情况.极限情况是：采样过程把原数据集的全部数据都进行采样,那么采样结果就和原数据一模一样,误差平方和也就达到了极限,不再降低.在本实验中,选取a/k的值就能得到较好的聚类结果.

6.结束语

本文对于K-means聚类算法进行了改进,并且基于Spark平台并行化实现了该算法.本算法基于概率值采用过采样的方法对原始数据集进行采样,采样结果能够很好地体现原数据集的聚类情况,且通过测试准确率、误差平方和验证了改进算法在聚类效果上的确具有一定的提升.通过将算法并行化运行在集群上,测试并行加速比、任务执行时间,验证了并行化计算具有高效性.本实验表明：在海量数据挖掘的应用场景中,串行计算已经不能很好地适应时论文范文展的需要,在未来的研究中,并行化平台、并行化计算将扮演越来越重要的角色.

吴哲夫(1971-),男,博士,浙江工业大学信息工程学院副教授,主要研究方向为数据通信网络、大数据分析和应用、云计算架构和服务等.

张彤（1990-）,男,浙江工业大学信息工程学院硕士研究生,主要研究方向为云计算、数据并行处理算法等.

肖鹰(1990-),男,浙江工业大学信息工程学院硕士研究生,主要研究方向为机器学习与数据挖掘、自然语言处理等.

总结：本论文可用于算法数据论文范文参考下载，算法数据相关论文写作参考研究。

算法引用文献: