摘 要：針對大數(shù)據(jù)的處理效率問題，論文主要應用Hadoop技術，探討了分布式技術應用于大數(shù)據(jù)挖掘的編程模式。論文以k_means算法作為研究對象，采用Hadoop的一個數(shù)據(jù)倉庫工具——HIVE來實現(xiàn)該算法的并行化，并在結構化的UCI數(shù)據(jù)集上進行了實驗，實驗結果表明該方法具有優(yōu)良的加速比和運行效率，適用于結構化海量數(shù)據(jù)的分析。

關鍵詞：大數(shù)據(jù)；Hadoop；分布式；k-means

中圖分類號：TP393.02

“大數(shù)據(jù)”時代已經(jīng)降臨，在商業(yè)、經(jīng)濟及其他領域中，決策將日益基于數(shù)據(jù)和分析而作出，而并非基于經(jīng)驗和直覺[1]。隨著互聯(lián)網(wǎng)和信息行業(yè)的發(fā)展，在日常運營中生成、累積的用戶網(wǎng)絡行為數(shù)據(jù)的規(guī)模是非常龐大的，以至于不能用G或T來衡量。我們希望從這些結構化或半結構化的數(shù)據(jù)中學習到有趣的知識，但這些數(shù)據(jù)在下載到關系型數(shù)據(jù)庫用于分析時會花費過多時間和金錢。因此，并行化數(shù)據(jù)挖掘成為了當下的一個熱門研究課題，其主要編程模式包括：數(shù)據(jù)并行模式，消息傳遞模式，共享內存模式以及后兩種模式同時使用的混合模式[2][3]。

1 國內研究現(xiàn)狀

當前中國的云計算的發(fā)展正進入成長期，國內很多研究者正進入分布式的數(shù)據(jù)挖掘領域，利用國外的成熟平臺，例如Hadoop來實現(xiàn)大數(shù)據(jù)的聚類等算法。但是數(shù)據(jù)的多樣性，文本多格式，造成對數(shù)據(jù)的操作有很大的難度，而如今大多數(shù)論文都利用了標準化的mapreduce方法來進行代碼的編寫，具有一定的通用性，但是Hadoop下還有許多的工具，能夠簡化m/r過程，同樣對一定結構的數(shù)據(jù)具有很好的并行效果，但是這方面的研究比較少，因此本文引入了HIVE的運用，簡化了數(shù)據(jù)的操作過程，利用類似標準的SQL語句對數(shù)據(jù)集進行運算，在一定程度上提高了并行化計算的效率。

2 Hadoop并行化基礎

數(shù)據(jù)挖掘（Data Mining）是對海量數(shù)據(jù)進行分析和總結，得到有用信息的知識發(fā)現(xiàn)的過程[4]。其中的聚類是一個重要的研究課題，在面對如此的海量數(shù)據(jù)，現(xiàn)有的單機模式的挖掘算法在時間與空間上遇到了很大的限制，而并行化處理是一種比較好的解決模式。Hadoop是當下比較熱門的一個分布式計算的平臺，其中的一個數(shù)據(jù)倉庫工具HIVE簡單快捷地實現(xiàn)MapReduce方法，適用于結構化數(shù)據(jù)的存儲模式。

Hadoop是一個分布式系統(tǒng)的基礎架構，其平臺由兩部分組成，Hadoop分布式文件存儲系統(tǒng)（HDFS）和MapReduce計算模型[5]。

HDFS的架構是基于一組特定的節(jié)點構建的（參見圖1），這是由它自身的特點決定的。這些節(jié)點包括NameNode（僅一個），它在HDFS內部提供元數(shù)據(jù)服務；DataNode，它為HDFS提供存儲塊。由于僅存在一個NameNode，因此這是HDFS的一個缺點（單點失?。?。存儲在HDFS中的文件被分成塊，然后將這些塊復制到多個計算機中（DataNode）。這與傳統(tǒng)的RAID架構大不相同。塊的大小（通常為64MB）和復制的塊數(shù)量在創(chuàng)建文件時由客戶機決定。NameNode可以控制所有文件操作。HDFS內部的所有通信都基于標準的TCP/IP協(xié)議。

MapReduce是一種高效的分布式編程模型，用于海量數(shù)據(jù)（大于1TB）的并行運算[6]，它的主要思想就是映射（Map）和化簡（Reduce）。一個任務（Job）需要實現(xiàn)基本的MapReduce過程主要包括三個部分：（1）輸入數(shù)據(jù)；（2）實現(xiàn)Map函數(shù)與Reduce函數(shù)；（3）實現(xiàn)此任務的配置項（JobConf）[7]，圖1描述了實現(xiàn)MapReduce的基本原理：

圖1 MapReduce原理圖

3 基于HIVE的并行k-means聚類算法設計

3.1 Hive簡介

Hive是基于Hadoop的一個數(shù)據(jù)倉庫工具，是建立在Hadoop上的數(shù)據(jù)倉庫基礎構架，可以將結構化的數(shù)據(jù)文件映射為一張數(shù)據(jù)庫表，并提供完整的sql查詢功能，可以將sql語句轉換為MapReduce任務進行運行。其優(yōu)點是可以通過類SQL語句快速實現(xiàn)簡單的MapReduce統(tǒng)計，不必開發(fā)專門的MapReduce應用，十分適合數(shù)據(jù)倉庫的統(tǒng)計分析。

3.2 Hive體系結構

圖2 HIVE體系結構圖

圖2顯示了HIVE的主要組件以及它和Hadoop的相互作用[8]，其主要組件說明如下：

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

Hive Thrift服務器公開了一個簡單的客戶端API來執(zhí)行HiveQL語句。Thrift[9]是一個用于跨語言服務的框架，框架內用一種語言（如Java）編寫，服務器也可以支持其他的語言的客戶端。Thrift Hive客戶端用不同語言生成用于構建常用的驅動程序，如JDBC（java），ODBC（c++），以及用php，perl，python等編寫的腳本驅動程序。

元數(shù)據(jù)存儲（metastore）是系統(tǒng)目錄。所有其他的Hive組件都和metastore有交互。

3.3 K-means算法介紹

k-means算法是最為經(jīng)典的基于劃分的聚類方法，它的基本思想是：以空間中k個點作為中心進行聚類，對最靠近它們的對象進行分類。通過迭代的方法，逐次更新各聚類中心的值，直到有良好的收斂[10]。假設要把樣本集分為m個類別，算法描述如下：

（1）適當選擇m個類的初始中心；

（2）在第k次迭代中，對任意一個樣本，求其到m個中心的距離，將該樣本歸到距離最短的中心所在的類；

（3）利用歐式距離等方法更新每一個新類的中心值；

（4）對于所有的m個聚類中心，如果利用（2）（3）的迭代法更新后，值保持不變或者變化在可允許范圍內，則迭代結束，否則重復（2）（3）步驟。

該算法的最大優(yōu)勢在于簡潔和快速，但每次迭代中需要遍歷數(shù)據(jù)需要消耗大量空間與時間，是算法的性能的瓶頸所在。

3.4 基于HIVE的k-means算法的分布式實現(xiàn)

由于k-means算法的要求，我們在每次計算聚類中心的過程中，會對整個數(shù)據(jù)集進行遍歷，于是我們利用Hadoop的一個數(shù)據(jù)倉庫工具——HIVE來對文本數(shù)據(jù)進行結構化錄入。

在錄入過程中，我們建表時采用了分區(qū)（partition）的操作，按文本數(shù)據(jù)結構分割成n個分區(qū)，因為對于大數(shù)據(jù)集的HIVE SELECT查詢中一般會掃描整個數(shù)據(jù)表，會消耗很多時間和不必要的工作。本文在建表sql語句如下：

create table IF NOT EXISTS ……（建表的字段）

partitioned by （name string）

row format delimited

fields terminated by ‘，’

至此，對于數(shù)據(jù)的操作可以按照數(shù)據(jù)庫形式讀取。對于HIVE的操作，如果單單只是“select *”的sql語句是沒有m/r過程的，只有當我們對數(shù)據(jù)選取特定的字段才會產(chǎn)生m/r過程，提升數(shù)據(jù)選取的效率。所以在整個程序中，我們的select語句都是如下的：

select字段名from表名。

而不選擇：select * from 表名，這種形式；

K-means算法需要多次遍歷數(shù)據(jù)集，并且迭代選出距離每個節(jié)點最近的中心，直至收斂，因此，在整個算法過程中，我們可以將select過程和計算距離的過程并行化，在master機器中計算每次分類之后的聚類中心，并傳遞給兩臺slave機器，并且通過master主機向slave分發(fā)任務，而m/r過程即在hive中完成。相對的，我們可以認為，每一次聚類過程中，由三臺機器并行完成整個數(shù)據(jù)集的計算，通過硬件的分布式來達到性能的優(yōu)化。

整個實驗的偽代碼如下：

{

在HIVE中建立表結構并導入txt數(shù)據(jù)結構；

初始化k = 簇族數(shù)和初始質心；

While（迭代結束標志）{

res = HiveUtil.queryHive（hivesql）；

while（res.next（））{ //遍歷數(shù)據(jù)集

計算出最近的簇族中心并歸類；

}

重新計算新的簇族中心；

如果中心改變，則繼續(xù)，否則結束；

}

}

4 實驗部署與實驗結果分析

4.1 部署Hadoop分布式環(huán)境

本實驗環(huán)境的拓撲如圖3所示：

圖3 實驗環(huán)境拓撲圖

在master主機和兩臺slave機器上，分別部署hadoop1.1.1，并開啟服務后，后臺駐留進程有：NameNode，DataNode，JobTracker，TaskTracker，SecondaryNameNode。最后解壓hive-0.10.0.bin目錄，通過命令hive –service hiveserver開啟服務。

4.2 實驗環(huán)境與評價標準

本文中所有實驗均在本人搭建的hadoop平臺上完成，四臺機器均為雙核2.4G，內存4GB。Hadoop版本為1.1.1，HIVE版本為0.10.0，eclipse版本為galileo，java版本為jdk-1_5_0_15，每臺機器之間用5類網(wǎng)線（100M）通過路由連接。

實驗數(shù)據(jù)來源為UCI的數(shù)據(jù)集——Individual household electric power consumption，是一座房屋內近四年（共48個月份）的時間中每一分鐘的電能消耗的統(tǒng)計數(shù)據(jù)集，采用的是文本txt格式記錄，每一行有九個屬性值，由逗號分隔，但有可能包含缺失數(shù)據(jù)，用“？”代替，整個數(shù)據(jù)集大約有200多萬條記錄。因此，在本實驗中，上文分區(qū)中的n值我們取為48。

對于實驗結果的評測，本文采用運行效率和加速比（speedup）[11]來作為評價標準。

4.3 實驗結果

在實驗中，我們的初始質心是隨機選取，因此，每項實驗做十次，取平均值得出以下結果（實驗結果已取整），如圖4：

圖4 運行效率

由圖中可以看出，隨著數(shù)據(jù)量的加大，運行時間并不是一個線性增長，因為遍歷整個數(shù)據(jù)集的次數(shù)和收斂的效果有關，數(shù)據(jù)量的遞增，會導致時間的更快的增量。但很明顯，實驗機器數(shù)目的增多，能很好的提高并行效果，對聚類算法的性能也有較好的提升。

圖5是進行了三組實驗得出的不通數(shù)據(jù)集的加速比的圖表結果，我們分別對10M，50M，100M，200M的數(shù)據(jù)集進行了測試，發(fā)現(xiàn)數(shù)據(jù)集越大，加速比的性能越好，越接近線性函數(shù)。

圖5 加速比

4.4 結果分析

由于數(shù)據(jù)集大小的限制，我們對兆級的數(shù)據(jù)進行了不同大小的實驗，通過以上兩個圖表，發(fā)現(xiàn)數(shù)據(jù)集的大小對算法性能有一定的影響。在基于HIVE的分布式系統(tǒng)中，隨著節(jié)點機器的增加，我們的算法性能有比較明顯的加強，空間的消耗換取了時間的消耗，因此對算法的加速比有很好的改進。

5 結語

本文對基于Hadoop平臺的分布式k-means算法進行了深入研究，利用HIVE技術對m/r過程進行簡化。文中對HIVE結構體系和k-means算法進行了介紹，利用m/r過程來提高大數(shù)據(jù)的分布式數(shù)據(jù)挖掘算法的性能，得到了良好的實驗結果。在以后的工作中，我們會更加深入的細化這個領域的研究，完善本文的結果。

本文的研究主要解決了聚類算法在分布式平臺中運行的問題，對聚類過程的優(yōu)化，較好地提高了大數(shù)據(jù)集的運行效率，為分布式數(shù)據(jù)挖掘提供了廣闊的前景。

參考文獻：

[1]杜鵑，沈銘思.大數(shù)據(jù)時代，讓子彈飛[J].中國制衣，2013-02-05：12.

[2]胡善杰.數(shù)據(jù)挖掘算法并行化研究[J].電子世界，2012（12）：67-68.

[3]都志輝.高性能計算之并行編程技術——MPI并行程序設計[M].北京：清華大學出版社，2006.

[4]王超鵬.基于云計算分布式數(shù)據(jù)挖掘算法研究[J].技術研發(fā)，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的海量分布式文件系統(tǒng)研究與優(yōu)化[J].北京：北京郵電大學軟件工程，2012-05.

[7]江小平，李成華，向文，張新訪，顏海濤.k-means聚類算法的MapReduce并行化實現(xiàn)[J].華東科技大學學報，2011-06（39）：120-124.

[8]葉文宸.基于HIVE性能優(yōu)化方法的研究與實踐[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-），男，江蘇常州人，在讀研究生，碩士，主要研究方向：數(shù)據(jù)挖掘，分布式計算等；陸建峰，教授，研究方向：模式識別，圖像處理，數(shù)據(jù)挖掘，智能機器人系統(tǒng)，生物醫(yī)學工程。

作者單位：南京理工大學計算機科學工程學院，南京 210094