基于Hive的分布式K_means算法設(shè)計(jì)與研究

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

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

中圖分類號(hào)：TP393.02

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

1 國(guó)內(nèi)研究現(xiàn)狀

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

2 Hadoop并行化基礎(chǔ)

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

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

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

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

圖1 MapReduce原理圖

3 基于HIVE的并行k-means聚類算法設(shè)計(jì)

3.1 Hive簡(jiǎn)介

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

3.2 Hive體系結(jié)構(gòu)

圖2 HIVE體系結(jié)構(gòu)圖

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

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

Hive Thrift服務(wù)器公開(kāi)了一個(gè)簡(jiǎn)單的客戶端API來(lái)執(zhí)行HiveQL語(yǔ)句。Thrift[9]是一個(gè)用于跨語(yǔ)言服務(wù)的框架，框架內(nèi)用一種語(yǔ)言（如Java）編寫，服務(wù)器也可以支持其他的語(yǔ)言的客戶端。Thrift Hive客戶端用不同語(yǔ)言生成用于構(gòu)建常用的驅(qū)動(dòng)程序，如JDBC（java），ODBC（c++），以及用php，perl，python等編寫的腳本驅(qū)動(dòng)程序。

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

3.3 K-means算法介紹

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

（1）適當(dāng)選擇m個(gè)類的初始中心；

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

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

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

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

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

由于k-means算法的要求，我們?cè)诿看斡?jì)算聚類中心的過(guò)程中，會(huì)對(duì)整個(gè)數(shù)據(jù)集進(jìn)行遍歷，于是我們利用Hadoop的一個(gè)數(shù)據(jù)倉(cāng)庫(kù)工具——HIVE來(lái)對(duì)文本數(shù)據(jù)進(jìn)行結(jié)構(gòu)化錄入。

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

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

partitioned by （name string）

row format delimited

fields terminated by ‘，’

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

select字段名from表名。

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

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

整個(gè)實(shí)驗(yàn)的偽代碼如下：

{

在HIVE中建立表結(jié)構(gòu)并導(dǎo)入txt數(shù)據(jù)結(jié)構(gòu)；

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

While（迭代結(jié)束標(biāo)志）{

res = HiveUtil.queryHive（hivesql）；

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

計(jì)算出最近的簇族中心并歸類；

}

重新計(jì)算新的簇族中心；

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

}

}

4 實(shí)驗(yàn)部署與實(shí)驗(yàn)結(jié)果分析

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

本實(shí)驗(yàn)環(huán)境的拓?fù)淙鐖D3所示：

圖3 實(shí)驗(yàn)環(huán)境拓?fù)鋱D

在master主機(jī)和兩臺(tái)slave機(jī)器上，分別部署hadoop1.1.1，并開(kāi)啟服務(wù)后，后臺(tái)駐留進(jìn)程有：NameNode，DataNode，JobTracker，TaskTracker，SecondaryNameNode。最后解壓hive-0.10.0.bin目錄，通過(guò)命令hive –service hiveserver開(kāi)啟服務(wù)。

4.2 實(shí)驗(yàn)環(huán)境與評(píng)價(jià)標(biāo)準(zhǔn)

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

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

對(duì)于實(shí)驗(yàn)結(jié)果的評(píng)測(cè)，本文采用運(yùn)行效率和加速比（speedup）[11]來(lái)作為評(píng)價(jià)標(biāo)準(zhǔn)。

4.3 實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)中，我們的初始質(zhì)心是隨機(jī)選取，因此，每項(xiàng)實(shí)驗(yàn)做十次，取平均值得出以下結(jié)果（實(shí)驗(yàn)結(jié)果已取整），如圖4：

圖4 運(yùn)行效率

由圖中可以看出，隨著數(shù)據(jù)量的加大，運(yùn)行時(shí)間并不是一個(gè)線性增長(zhǎng)，因?yàn)楸闅v整個(gè)數(shù)據(jù)集的次數(shù)和收斂的效果有關(guān)，數(shù)據(jù)量的遞增，會(huì)導(dǎo)致時(shí)間的更快的增量。但很明顯，實(shí)驗(yàn)機(jī)器數(shù)目的增多，能很好的提高并行效果，對(duì)聚類算法的性能也有較好的提升。

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

圖5 加速比

4.4 結(jié)果分析

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

5 結(jié)語(yǔ)

本文對(duì)基于Hadoop平臺(tái)的分布式k-means算法進(jìn)行了深入研究，利用HIVE技術(shù)對(duì)m/r過(guò)程進(jìn)行簡(jiǎn)化。文中對(duì)HIVE結(jié)構(gòu)體系和k-means算法進(jìn)行了介紹，利用m/r過(guò)程來(lái)提高大數(shù)據(jù)的分布式數(shù)據(jù)挖掘算法的性能，得到了良好的實(shí)驗(yàn)結(jié)果。在以后的工作中，我們會(huì)更加深入的細(xì)化這個(gè)領(lǐng)域的研究，完善本文的結(jié)果。

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

參考文獻(xiàn)：

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

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

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

[4]王超鵬.基于云計(jì)算分布式數(shù)據(jù)挖掘算法研究[J].技術(shù)研發(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].北京：北京郵電大學(xué)軟件工程，2012-05.

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

[8]葉文宸.基于HIVE性能優(yōu)化方法的研究與實(shí)踐[J].南京：南京大學(xué)軟件工程學(xué)院，2011.

[9]劉書(shū)楠.Thrift入門簡(jiǎn)介[J].YOUNG青年與社會(huì)，2013（1）：228.

[10]崔丹丹.K-means聚類算法研究及改進(jìn)[M].安徽：安徽大學(xué)計(jì)算機(jī)學(xué)院，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.

作者簡(jiǎn)介：馮曉云（1988-），男，江蘇常州人，在讀研究生，碩士，主要研究方向：數(shù)據(jù)挖掘，分布式計(jì)算等；陸建峰，教授，研究方向：模式識(shí)別，圖像處理，數(shù)據(jù)挖掘，智能機(jī)器人系統(tǒng)，生物醫(yī)學(xué)工程。

作者單位：南京理工大學(xué)計(jì)算機(jī)科學(xué)工程學(xué)院，南京 210094