基于Hadoop的数据聚类算法研究

徐正巧　赵德伟

摘要：聚类算法一直备受研究者青睐。随着信息技术和数据技术的发展，数据的种类和数量急剧增长，云计算平台Hadoop成为这些数据存储和处理的新平台，基于云计算平台Hadoop的聚类算法逐渐成为热门。针对数据挖掘中的聚类问题，依托云计算模式及Hadoop平台，研究了Kmeans算法，有效改变了现有算法的局限性。

关键词关键词：云计算；Hadoop；聚类分析；MapReduce

DOIDOI：10.11907/rjdk.143858

中图分类号：TP301.6

文献标识码：A文章编号文章编号：16727800（2015）002000402

基金项目基金项目：四川省教育厅科研项目（12ZB144）；西华师范大学校基金项目（12A038）

作者简介作者简介：徐正巧（1982-），女，宁夏盐池人，硕士，西华师范大学实验中心讲师，研究方向为数据挖掘与智能计算。

0引言

随着信息技术和电子商务的飞速发展，数据正以惊人的速度剧增，无论是数据量还是数据种类都越来越丰富。这些海量的数据中隐藏着大量有价值的信息，如何存储、处理这些海量数据，从这些海量数据中挖掘出有用信息，利用已有数据进行预测是目前的研究热点。

海量数据分布在不同的计算机中，分布式计算和大规模异构系统资源共享是实现海量数据挖掘的关键技术，云计算技术为这一问题提供了理想的技术解决方案，云计算平台满足了用户“按需使用，按量付费，即需即用”的服务需求，有效解决了计算机中海量数据的存储与处理问题。

1云计算

1.1云计算概念

云计算（Cloud Computing）是将存储于电脑、移动电话和智能通讯设备上的大量信息和处理器资源集中在一起进行工作的超级计算机模式。它将要完成的任务分布在大量计算机构成的资源池上，各种应用系统能够根据需要从资源池中获取计算力、存储空间和各种软件服务＼[1＼]。

云计算是集群计算（Cluster Computing）、分布式处理 （Distributed Computing）、并行计算（Parallel Computing）和网格计算（Grid Computing）的发展＼[2＼]。云计算采用计算机集群构成数据中心和资源池，使用户能够利用互联网随时随地、按实际需要共享云资源。

1.2云计算特点

云计算以其超大规模、高可扩展性、高可靠性、虚拟化、按需分配、廉价性和通用性等优势，使普通用户在普通计算机上都能享受到高性能计算机的存储、计算能力，给人类生活和工作带来了极大便利。目前Google、IBM、Microsoft等大型互联网企业都部署有云计算平台，供用户分享云技术带来的好处。

1.3云计算平台

云计算系统主要由云平台、云终端、云存储和云安全4部分组成，其中云平台是云计算系统的核心，它整合了多个数据中心的资源，统一分配和调度计算机资源、存储资源和网络资源，为用户提供了良好的计算环境、开发平台和应用软件等多种服务＼[3＼]。

云计算平台可以划分为存储型云平台、计算型云平台以及综合云计算平台。其中，存储型云平台主要以数据存储为主，计算型云平台主要进行数据处理，综合云计算平台则兼顾计算和数据存储。

Hadoop是一个易开发及并行处理海量数据的云计算平台，主要由两部分组成：分布式文件系统HDFS（Hadoop Distributed File System）和MapReduce计算模型＼[45＼]，HDFS为海量数据提供存储，是分布式计算的基石，采用了M/S架构，主要执行的操作有创建、删除、移动或重命名等，架构类似于传统的分级文件系统；而MapReduce则为海量数据提供计算。

2数据聚类分析

聚类分析（Clastering Analysis）以对象的相似性为基础，在聚类模式之间具有更多的相似性，是数据挖掘的重要技术之一。聚类是将物理或抽象对象的集合分成由类似的对象组成多个类的过程，是现实世界中普遍存在的现象，作为统计学的一个分支，其应用非常广泛。

在数据挖掘之前，对象类划分的数据量与类型均是未知的，因此在数据挖掘后一般需要对数据挖掘结果进行合理的分析与解释。聚类算法可分为划分法、层次法、基于网格方法、基于密度方法、图论聚类法等。数据聚类分析主要有4个步骤，如图1所示。

图1聚类分析步骤

3基于Hadoop的数据聚类算法

数据挖掘的特点就是从海量数据中提取有价值的规则和信息。随着数据量和种类的急剧增加，传统的数据挖掘技术已经很难满足数据挖掘的需求。在云计算时代，海量的数据分布在不同地理位置的计算机上，现有聚类算法在时间复杂性和空间复杂性上都无法很好地解决此问题。研究思路就是将并行处理技术应用到现有的聚类算法中，降低聚类算法的时间复杂度和空间复杂度，节约聚类时间。

并行聚类算法能够在多台计算机上同时运行，满足云计算需求，节约了大量计算机资源。目前，并行聚类算法有：并行聚类算法PWIDE、并行KMeans算法、基于密度和密度可达并行聚类算法PCADD等＼[6＼]。

KMeans算法是最著名和最常用的聚类算法。Kmeans算法以k为输入参数，把n个对象分为k个簇，使得簇内具有较高的相似度，簇间具有较低的相似度。相似度的计算根据一个簇中对象的平均值（被称为簇的重心或簇心）进行。本文聚类算法采用均方差作为标准测度函数：

E=∑ki=1∑Pcip-mi2（1）

其中，E为所有数据对象的均方差之和；P代表对象空间中的一个点；mi为聚类均值。

并行Kmeans算法采用数据并行的设计思想，首先把整个空间数据按照计算机的节点数量对海量的数据集X进行划分，形成N个子数据样本集X1，X2，X3……XN（N为计算机节点个数），每个节点上分别对应自己的数据集，然后对每个子数据集进行独立的数据聚类，形成数据集的簇{C11，C12，……，C1M}，{C21，C22，……，C2O}，……，{Cn1，Cn2，……，CnQ}（其中M，O，Q为聚类簇的个数，N为数据集的个数），最后把聚类结果发送到主节点上，主节点再把各个聚类结果汇总，输出最终的聚类结果。

Hadoop平台主要有HDFS和MapReduce两部分，并行Kmeans聚类算法，在每次迭代过程中分别执行Map和Reduce操作。

在Hadoop平台中，HDFS负责存储海量数据，并管理数据文件，记录数据文件分布在哪个节点上，从哪个数据节点上获得，并记录数据的初始中心。 Map函数的任务是完成每个记录员到中心点距离的计算并重新标记其新的类别，其输入为待聚类所有数据和上一轮聚类中心，输入数据聚类<行，记录>。Reduce函数的任务是根据Map函数得到的中间计算结果，计算出新类的聚类中心并发送给各节点，更新HDFS到文件然后进行下一次迭代直到收敛。

并行Kmeans聚类算法步骤如下：①任意选择K个样本作为初始的中心点；②迭代并执行Map和Reduce操作；③直到收敛。

4结语

利用云计算技术和Hadoop平台，获得强大的计算能力、存储能力以及基础设施服务能力，有效解决了分析与处理海量数据面临的问题，降低了终端设备要求，提高了数据处理能力。本文基于云计算平台Hadoop，对海量数据聚类的并行算法Kmeans进行了深入的研究和探讨，以期对聚类发展起到推动作用。

参考文献参考文献：

＼[1＼]黄成云，左明章，荣先海. 基于云计算的移动学习系统设计＼[J＼]. 现代教育技术，2010，20 （8）：102105.

＼[2＼]侯建， 帅仁俊， 侯文. 基于云计算的海量数据存储模型＼[J＼].通信技术，2011，44（5）：163165.

＼[3＼]吴功，吴英.物联网导论＼[M＼].北京：机械工业出版社，2012.

＼[4＼]赵卫中，马慧芳，傅燕翔，等. 基于云计算平台Hadoop的并行kmeans聚类算法设计研究＼[J＼].计算科学，2011， 38 （10）：166176.

＼[5＼]GHEMAWAT S，GOBIOFF H，LEUNG S. The google file system ＼[J＼]. SACM SIGOPS Operating Systems Review， 2003，37（5）：2943.

＼[6＼]张强，赵郑.WIDE：海量数据的聚类算法＼[J＼]. 天津大学学报， 2006（7）：3339.

责任编辑（责任编辑：杜能钢）