一种基于Hadoop云计算平台大数据聚类算法设计*1

司福明，卜天然（安徽机电职业技术学院信息工程系，安徽 芜湖 241000）

一种基于Hadoop云计算平台大数据聚类算法设计*1

司福明，卜天然
（安徽机电职业技术学院信息工程系，安徽 芜湖 241000）

传统的数据挖掘技术由于受到编程模型等的约束，产生了不同瓶颈，聚类算法的研究面临着海量的大数据处理与分析的挑战，新兴计算模型Hadoop作为一种可并行处理的云计算平台得到了广泛应用。文章对传统聚类挖掘算法进行改进和优化，在Hadoop云计算平台上进行K-means算法的并行化实现，降低算法的时间复杂度，提高了计算效率。实践证明，改进的K-means算法适合大规模数据集的聚类挖掘，具有高效、准确、稳定、安全等特性，适合于海量数据的分析和处理。

Hadoop；云计算平台；大数据；聚类挖掘算法；并行化

1　引言

大数据技术、物联网、云计算是当今IT产业具有颠覆性的技术革命。大数据时代的到来对人们的生活方式、商业模式都发生着重要影响。随着大数据的提出，给信息技术产业带来了新的发展机遇，尤其对数据挖掘技术影响更为明显。数据挖掘技术进入一个新的发展阶段，要提高大数据的准确性，大数据的挖掘算法对大数据处理结果的误差率必须在可接受的范围内，这就需要对传统数据挖掘算法进行改进。文章以提高大数据挖掘效率和准确度为目标，将面向大数据的聚类挖掘算法准确度和效率作为研究重点，对传统的聚类算法进行了必要的改进并利用云计算平台将改进后的聚类挖掘算法进行并行化实验。改进型的聚类算法具有较好的理论和实用价值，可在大数据集的应用平台进行广泛推广和应用［1］。

2　关键技术概述

2.1基于hadoop的云计算平台

2.1.1云计算技术

云计算作为一种基于互联网的服务交付和使用模式，是指通过网络以按需、易扩展的方式获得所需服务。它的核心思想是将大量用网络连接起来的计算资源统一管理和调度，构成一个资源池向用户提供按需服务。云计算为用户提供了最可靠、最安全的数据存储中心，用户可不再顾虑数据丢失、病毒入侵等问题。云计算的应用模式主要有：软件即服务 （SaaS）、平台即服务（PaaS）、基础实施即服务 （IaaS）三种。

2.1.2Hadoop

Hadoop是一个开源的、可以编写和运行分布式应用来处理大规模数据的框架 （平台）。其主要特点是用户可以在不了解分布式底层细节的情况下，开发分布式程序充分利用集群的威力进行高速运算和存储。

（1）HDFS（Hadoop Distributed File System）：分布式文件系统，可实现分布式存储；

（2）MapReduce：分布式程序框架，可实现分布式计算。MapReduce程序框架如下：

Map函数：键/值对映射

＜k1，v1＞→＜k2，v2＞

E.g.：＜k1，v1＞：＜1，“abcd”＞，＜2，“cde”＞，＜3，“acd”＞，…..

＜k2，v2＞：＜‘a’，2＞，＜‘b’，1＞，＜‘c’，3＞，……

Reduce函数：规约

＜k2，list（v2）＞→＜k3，v3＞

E.g.：＜k2，list（v2） ＞：＜‘a’，list（1，2，3） ＞＜k3，v3＞：＜‘a’，6＞

基于Hadoop云计算平台，建立HDFS分布式文件系统存储海量文本数据集，通过文本词频利用MapReduce原理建立分布式索引，以分布式数据库HBase存储关键词索引，并提供实时检索，从而可实现对海量数据进行的分布式并行处理。

2.2大数据技术

Big Data（大数据技术），因近年来互联网、云计算、移动和物联网的迅猛发展而成为广为关注的热点话题。大数据是一种规模大到在获取、存储、管理、分析方面大大超出了传统数据库软件工具能力范围的数据集合，具有海量的数据规模、快速的数据流转、多样的数据类型和价值密度低四大特征。从技术层面来看，大数据与云计算的关系是密不可分的。大数据在使用过程中必须采用分布式架构，其特点在于对海量数据进行分布式的数据挖掘。但它必须依托云计算的分布式处理、分布式数据库和云存储、虚拟化技术［2］。

2.3聚类挖掘技术

聚类分析是数据挖掘采用的核心技术，聚类分析基于“物以类聚”的朴素思想，根据事物的特征对其进行聚类或分类。从隐性层面来看，聚类分析的结果将会得到一组数据对象的集合，我们称其为簇。在簇中的对象是彼此相似的，而其他簇中的对象则是相异的。在许多应用中，可以将一个簇中的数据对象作为一个整体来对待。

聚类挖掘技术最早在统计学和人工智能等领域得到广泛的研究。近年来，随着数据挖掘的发展，聚类以其特有的优点，成为数据挖掘研究领域一个非常活跃的研究课题。在数据挖掘领域内，经常面临含有海量数据的数据库，因此，要不断改进面向大规模数据库的聚类方法，以适应新问题带来的挑战。

3　改进K-means聚类算法研究

3.1K-means聚类算法基本思想与方法

K-means算法是很典型的基于距离的聚类分析算法，它采用距离作为相似性评价的指标，即：如果两个对象的距离越近，则它的相似度就越大。这种算法是认为簇是由距离靠近的对象而组成的，因此它把能够得到紧凑并且独立的簇作为最终的目标［3］。

算法过程如下：

（1）从N个文档中随机地选取K个文档作为质心

（2）测量剩余的每一个文档到每个质心的距离，同时将它归到最近质心的类

（3）再进行重新计算已经获得的每个类的质心

（4）迭代第二和第三步直到新质心和原质心相等或小于指定阈值

（5）算法完成

具体算法描述如下：

输入：k，data［n］；

（1）选择k个初始中心点，例如c［0］ =data［0］，…c［k-1］ =data［k-1］；

（2）对于data［0］….data［n］，分别与c［0］…c［k-1］比较，假定与c［i］差值最少，就标记为i；

（3）对于所有标记为i点，重新计算c［i］ =｛所有标记为i的data［j］之和｝/标记为i的个数；

（4）重复 （2）（3），直到所有c［i］值的变化小于给定阈值。

3.2基于密度的增量的DBIK-means改进方法

k-means算法缺点：在K-means算法中，K往往是给定的，因此，K值的选定是很难估计的。在运算之前，不清楚给定的数据集应该分成多少种类别才最恰当。在K-means算法中，需要根据初始聚类中心来确定初始划分，然后进行优化。这种选择对聚类分析的结果会产生比较大的影响，如果初始值选择不好，则有可能无法获取有效的聚类结果。此外，在K-means算法框架中可以发现，当运算的数据量较大时，算法的时间开销则非常之大。所以需要对算法的时间复杂度进行一定程度的改进［4］。

综合k-means聚类算法的缺点，结合密度增量的基本思想，文章提出基于密度的增量kmeans聚类算法。

改进的k-means算法以基于密度的k-means聚类结果为依据，对X-Y数据集合聚类。作为相异度的计算公式，DBIK-means聚类算法的伪代码如下：

输入：数据集合X，密度阈值minPts

输出：若干任意形状的簇

步骤：

从集合X中随机取小部分数据集Y，YX，同时计算Eps的大小

List centerPoint=null，clusters=null；//初始中心点集合，簇的集合都为空

for i=1 to|Y|//|Y|表示数据集合Y的大小，for循环用于计算数据点的密度

将集合Y中没有划分到任意簇的点划分到与其相异度最近的簇中；

计算簇的中心点之间的距离的均值Dave；

for i=1 to|X-Y|//将集合X-Y中的点划分到与其相异度最小的簇中

DBIK-means聚类算法可以发现若干任意形状的簇，在准确率和时间复杂度方面，算法对数据的输入顺序和minPts参数不敏感，DBIK-means算法可以有效处理高维混合属性的数据集。

4　DBIK-means在云计算hadoop平台设计

4.1DBIK-means聚类算法基于hadoop的并行优化设计

聚类算法在Hadoop平台上的实现过程比较复杂，需要实现map和reduce函数。DBIK-means聚类算法在Hadoop上的具体实现分为两个阶段。其设计最主要的内容就是设计和实现map和Reduce函数，包括输入和输出 ＜key，value＞键值对的类型以及 map和 Reduce函数的具体逻辑等［5］。

（1）map函数设计

map函数的输入包括一组＜key，value＞键值对的集合和密度阈值minPts，其中＜key，value＞是MapReduce框架默认的格式，key表示当前数据集合相对于输入数据文件起始点的偏移量，value为对应的数据；函数的输出是一组＜key1，value1＞键值对的集合，其中key1表示簇的编号，value1表示属于第key1个簇的相关属性，包括簇的中心点、簇中点的个数Num、簇中所有点的和Sum以及簇中与中心点最远的点与中心点的相异度，i的取值范围为1到k，k表示簇的个数。函数的伪代码如下：

（2）combine函数设计

combine函数的输入为一组＜key1，value1＞键值对的集合，key1和value1的含义同map函数中的＜key1，value1＞键值对中的key1和value1一样。combine的伪代码如下：

（3）reduce函数设计

reduce函数的功能是将同一个DataNode中的多个map函数生成的＜key，value＞键值对集合进行合并，同时以JSON的格式持久化到分布式数据库中，其伪代码如下：

4.2hadoop平台搭建与完全分布式实现

4.2.1hadoop平台配置

采用完全分布模式才能真正体现Hadoop框架的优势所在。在综合考虑资源使用效率和实验中PC数量有限的情况下，采用将U0作为JobTracker和NameNode，U1至U4作为TaskTracker和DataNode的方式来实现完全分布模式的配置。从分布式存储的层面考虑，Hadoop集群由三个部分组成，包括两个必选部分即一个NameNode和若干个DataNode，和一个可选部分即Secondary NameNode；为了确保Hadoop集群的可靠性，Secondary NameNode作为NameNode的备份，当且仅当NameNode出现异常时，采用Secondary NameNode重新启动整个Hadoop集群。从分布式应用的层面考虑，Hadoop集群由一个JobTracker和若干个TaskTracker两个必选部分组成，前者负责任务的调度管理，后者负责任务的并行执行。为了便于进行数据的读取和本地的计算，JobTracker最好运行在DataNode上，JobTracker和NameNode可以不在同一台机器上［6］。

文章采用开源的分布式软件Hadoop来搭建实验用的云计算平台，用于测试DBIK-means聚类算法的性能。使用四台机器，都安装fedora 9一个master三个slave这么做是为了测试hdfs分布式存储时备份成三份，关掉某一台slave看是否影响整体的文件系统。

虚拟机：VMware-workstation-6.0.5-109488；

操作系统：操作系统fedora 9

系统配置：

四台机器的具体网络配置为：

Hostname　IP　Use master　192.168.213.170　NameNode，JobTracker slave1　192.168.213.172　DataNode，TaskTracker slave2　192.168.213.173　DataNode，TaskTracker slave3　192.168.213.175　DataNode，TaskTracker

（1）进入到hadoop目录下，配置conf目录下的hadoop-env.sh中的JAVA_HOME的jdk路径，例如："export JAVA_HOME=/usr/Java/jdk1.6.0_23"。

（2）配置conf目录下的core-site.xm l，在标签＜configuration＞＜/configuration＞中添加如下配置：

Xm l代码如下：

（3）配置conf目录下的mapred-site.xm l在标签＜configuration＞＜/configuration＞中添加如下配置：

Xm l代码如下：

4.2.2实验分析及小结

Hadoop配置好之后，在NameNode即U0机器的终端中执行start-all.sh，启动Hadoop进程。当第一次启动Hadoop时，需要运行Hadoop namenode-format命令对系统进行格式化。Hadoop启动之后，会自动启动浏览器，显示NameNode的管理页面，集群中各个DadaNode节点的状态、已用存储空间、剩余存储空间和blocks数目等［7］。在完全分布式环境下对DBIK-means聚类算法进行仿真实验，通过实验验证了DBIK-means聚类算法在处理大数据时，能够得到更好的聚类结果和更短的运行时间，数据量越大，时间性能优势越明显，借助云平台能够获得更好的加速比。但改进算法对于具有密集噪声点等方面的数据处理仍然存在局限性，需要进一步加以完善。

［1］周爱武，崔丹丹，潘勇.一种优化初始聚类中心的K-means聚类算法 ［J］.微型机与应用，2011，30（13）：1—3，9.

［2］江小平，李成华，等.K-means聚类算法的MapReduce并行化实现［J］.华中科技大学学报，2011，39（S1）：120—124.

［3］孙吉贵，刘杰，赵连宇.聚类算法研究［J］.软件学报，2008，19（1）：48—61.

［4］Dean J，Ghemawat S.MapReduce：simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）：107—113.

［5］赵卫中，马慧芳，傅燕翔，等.基于云计算平台Hadoop的并行k-means聚类算法设计研究［J］.计算机科学，2011，38（10）：166—168.

［6］张琳，陈燕，汲业，等.一种基于密度的K-means算法研究［J］.计算机应用研究，2011，28（11）：71-73.

［7］Chang F，Dean J，Ghemawat S，et al.Bigtable：A distributed storage system for structured data ［J］.ACM Transactions on Computer Systems（TOCS），2008，26（2）：1—4.

（责任编辑刘洪基）

Design of a Large Data Clustering Algorithm Based on Hadoop Cloud Computing Platform

SIFuming&BU Tianran
（Dept.，of Information Engineering，Anhui Technical College of Mechanical and Electrical Engineering，Wuhu，241000，Anhui Province）

The traditional datamining technology due to the constraint programmingmodel，resulting in a bottleneck，clustering algorithm research faces the challenge ofmass of data processing and analysis，the emerging computingmodel Hadoop as a parallel processing of cloud computing platform has been widely used in many fields.In this paper，the traditional clusteringmining algorithm is improved and optimized. The K-means algorithm is implemented on Hadoop cloud computing platform，which can reduce the time complexity and improve the computational efficiency.Practice has proved that the improved K-means algorithm is suitable for large-scale data sets clustering mining，with high efficiency，accuracy，stability，security and other haracteristics，suitable for the analysis and processing ofmassive data.

Hadoop；cloud computing platform；big data；Clustering Mining Algorithm；Parallel

TP301.6

A

1671-7406（2016）03-0049-07

安徽省教育厅2016年度高校自然科学研究项目，项目编号：KJ2016A134。

2015-12-10

司福明 （1983—），男，讲师，硕士研究生，研究方向：数据挖掘技术，网络化应用系统。