基于Hive的分布式K_means算法设计与研究

摘 要：针对大数据的处理效率问题，论文主要应用Hadoop技术，探讨了分布式技术应用于大数据挖掘的编程模式。论文以k_means算法作为研究对象，采用Hadoop的一个数据仓库工具——HIVE来实现该算法的并行化，并在结构化的UCI数据集上进行了实验，实验结果表明该方法具有优良的加速比和运行效率，适用于结构化海量数据的分析。

关键词：大数据；Hadoop；分布式；k-means

中图分类号：TP393.02

“大数据”时代已经降临，在商业、经济及其他领域中，决策将日益基于数据和分析而作出，而并非基于经验和直觉[1]。随着互联网和信息行业的发展，在日常运营中生成、累积的用户网络行为数据的规模是非常庞大的，以至于不能用G或T来衡量。我们希望从这些结构化或半结构化的数据中学习到有趣的知识，但这些数据在下载到关系型数据库用于分析时会花费过多时间和金钱。因此，并行化数据挖掘成为了当下的一个热门研究课题，其主要编程模式包括：数据并行模式，消息传递模式，共享内存模式以及后两种模式同时使用的混合模式[2][3]。

1 国内研究现状

当前中国的云计算的发展正进入成长期，国内很多研究者正进入分布式的数据挖掘领域，利用国外的成熟平台，例如Hadoop来实现大数据的聚类等算法。但是数据的多样性，文本多格式，造成对数据的操作有很大的难度，而如今大多数论文都利用了标准化的mapreduce方法来进行代码的编写，具有一定的通用性，但是Hadoop下还有许多的工具，能够简化m/r过程，同样对一定结构的数据具有很好的并行效果，但是这方面的研究比较少，因此本文引入了HIVE的运用，简化了数据的操作过程，利用类似标准的SQL语句对数据集进行运算，在一定程度上提高了并行化计算的效率。

2 Hadoop并行化基础

数据挖掘（Data Mining）是对海量数据进行分析和总结，得到有用信息的知识发现的过程[4]。其中的聚类是一个重要的研究课题，在面对如此的海量数据，现有的单机模式的挖掘算法在时间与空间上遇到了很大的限制，而并行化处理是一种比较好的解决模式。Hadoop是当下比较热门的一个分布式计算的平台，其中的一个数据仓库工具HIVE简单快捷地实现MapReduce方法，适用于结构化数据的存储模式。

Hadoop是一个分布式系统的基础架构，其平台由两部分组成，Hadoop分布式文件存储系统（HDFS）和MapReduce计算模型[5]。

HDFS的架构是基于一组特定的节点构建的（参见图1），这是由它自身的特点决定的。这些节点包括NameNode（仅一个），它在HDFS内部提供元数据服务；DataNode，它为HDFS提供存储块。由于仅存在一个NameNode，因此这是HDFS的一个缺点（单点失败）。存储在HDFS中的文件被分成块，然后将这些块复制到多个计算机中（DataNode）。这与传统的RAID架构大不相同。块的大小（通常为64MB）和复制的块数量在创建文件时由客户机决定。NameNode可以控制所有文件操作。HDFS内部的所有通信都基于标准的TCP/IP协议。

MapReduce是一种高效的分布式编程模型，用于海量数据（大于1TB）的并行运算[6]，它的主要思想就是映射（Map）和化简（Reduce）。一个任务（Job）需要实现基本的MapReduce过程主要包括三个部分：（1）输入数据；（2）实现Map函数与Reduce函数；（3）实现此任务的配置项（JobConf）[7]，图1描述了实现MapReduce的基本原理：

图1 MapReduce原理图

3 基于HIVE的并行k-means聚类算法设计

3.1 Hive简介

Hive是基于Hadoop的一个数据仓库工具，是建立在Hadoop上的数据仓库基础构架，可以将结构化的数据文件映射为一张数据库表，并提供完整的sql查询功能，可以将sql语句转换为MapReduce任务进行运行。其优点是可以通过类SQL语句快速实现简单的MapReduce统计，不必开发专门的MapReduce应用，十分适合数据仓库的统计分析。

3.2 Hive体系结构

图2 HIVE体系结构图

图2显示了HIVE的主要组件以及它和Hadoop的相互作用[8]，其主要组件说明如下：

外部接口，Hive同时提供了用户界面的命令行（CLI）和Web UI，以及应用程序编程接口（API），如JDBC和ODBC。

Hive Thrift服务器公开了一个简单的客户端API来执行HiveQL语句。Thrift[9]是一个用于跨语言服务的框架，框架内用一种语言（如Java）编写，服务器也可以支持其他的语言的客户端。Thrift Hive客户端用不同语言生成用于构建常用的驱动程序，如JDBC（java），ODBC（c++），以及用php，perl，python等编写的脚本驱动程序。

元数据存储（metastore）是系统目录。所有其他的Hive组件都和metastore有交互。

3.3 K-means算法介绍

k-means算法是最为经典的基于划分的聚类方法，它的基本思想是：以空间中k个点作为中心进行聚类，对最靠近它们的对象进行分类。通过迭代的方法，逐次更新各聚类中心的值，直到有良好的收敛[10]。假设要把样本集分为m个类别，算法描述如下：

（1）适当选择m个类的初始中心；

（2）在第k次迭代中，对任意一个样本，求其到m个中心的距离，将该样本归到距离最短的中心所在的类；

（3）利用欧式距离等方法更新每一个新类的中心值；

（4）对于所有的m个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变或者变化在可允许范围内，则迭代结束，否则重复（2）（3）步骤。

参考文献：

[1]杜鹃，沈铭思.大数据时代，让子弹飞[J].中国制衣，2013-02-05：12.

[2]胡善杰.数据挖掘算法并行化研究[J].电子世界，2012（12）：67-68.

[3]都志辉.高性能计算之并行编程技术——MPI并行程序设计[M].北京：清华大学出版社，2006.

[4]王超鹏.基于云计算分布式数据挖掘算法研究[J].技术研发，2012：92-104.

[5]Dean J，Ghemawat S.MapReduce：simplified data processing on large clusters[C].Proceedings of Operating Systems Design and Implementation. San Francisco，CA，2004：137-150.

[6]付东华.基于HDFS的海量分布式文件系统研究与优化[J].北京：北京邮电大学软件工程，2012-05.

[7]江小平，李成华，向文，张新访，颜海涛.k-means聚类算法的MapReduce并行化实现[J].华东科技大学学报，2011-06（39）：120-124.

[8]叶文宸.基于HIVE性能优化方法的研究与实践[J].南京：南京大学软件工程学院，2011.

[9]刘书楠.Thrift入门简介[J].YOUNG青年与社会，2013（1）：228.

[10]崔丹丹.K-means聚类算法研究及改进[M].安徽：安徽大学计算机学院，2012-04.

[11]Xu X W，Jager J， Kriegel H P. A fast parallel clustering algorithm for large spaial databases[J].Data Mining aand knowledeg Discovery，1999，3（3）：263-290.

作者简介：冯晓云（1988-），男，江苏常州人，在读研究生，硕士，主要研究方向：数据挖掘，分布式计算等；陆建峰，教授，研究方向：模式识别，图像处理，数据挖掘，智能机器人系统，生物医学工程。

作者单位：南京理工大学计算机科学工程学院，南京 210094