基于MapReduce的分布式云計算數(shù)據(jù)挖掘方法

薛慧敏

(山西財貿(mào)職業(yè)技術(shù)學(xué)院，山西 太原 030031)

0 引言

數(shù)據(jù)挖掘技術(shù)能夠有效解決目前社會各領(lǐng)域海量數(shù)據(jù)頻繁增長問題，幫助行業(yè)管理者從大數(shù)據(jù)中獲得有價值的趨勢信息[1]。大規(guī)模數(shù)據(jù)挖掘需要搭載高效數(shù)據(jù)處理平臺，才能在短時間內(nèi)完成相關(guān)領(lǐng)域的數(shù)據(jù)挖掘任務(wù)，滿足行業(yè)對數(shù)據(jù)挖掘的效率需求[2]。云計算以網(wǎng)絡(luò)“云”為介質(zhì)將宏觀的數(shù)據(jù)計算程序劃分成多個子計算程序，呈現(xiàn)顯著的分布式計算特征。云計算將數(shù)據(jù)挖掘壓力分散開來，以此降低運算時間，克服硬件設(shè)施對計算效率的負面干擾[3]。因而，本文以云計算環(huán)境為載體進行大數(shù)據(jù)挖掘，擬選用云計算技術(shù)中的MapReduce計算模型作為大規(guī)模數(shù)據(jù)并行運算的技術(shù)支撐，以獲取基于MapReduce的分布式云計算數(shù)據(jù)挖掘方案。

1 分布式云計算環(huán)境下基于MapReduce的數(shù)據(jù)挖掘技術(shù)

1.1 基于MapReduce分布式云計算框架

MapReduce是一個包含Map函數(shù)與 Reduce 函數(shù)的、能夠解決海量數(shù)據(jù)并行運算的編程模式，Map函數(shù)用于解決MapReduce計算框架的映射任務(wù)，Reduce 函數(shù)用于解決計算框架的歸約任務(wù)[4]。MapReduce計算模型下的數(shù)據(jù)挖掘效率提升的原理在于：MapReduce能夠基于實際運行狀態(tài)科學(xué)分配各程序的運算任務(wù)與運算量，通過Reduce 函數(shù)歸約節(jié)點運算結(jié)果并匯總，達到實時并行化運算狀態(tài)[5]；同時，運算過程中將計算機視為分布式運算的節(jié)點，網(wǎng)絡(luò)數(shù)據(jù)的交換、計算等任務(wù)均借助計算機的內(nèi)存空間來實現(xiàn)，如此一來，MapReduce無需投入過多的計算成本并且擴大了數(shù)據(jù)運算的空間場所，相同時間內(nèi)可以完成更多的計算任務(wù)。

圖1為 MapReduce計算模型的計算過程。MapReduce計算過程包括Map與Reduce兩大步驟，<鍵,值>為Map函數(shù)與Reduce函數(shù)輸入值、輸出值的表達形式。海量待挖掘數(shù)據(jù)的存儲、傳輸、讀取工作借助HDFS文件系統(tǒng)完成，HDFS是云計算環(huán)境下常用的分布式文件系統(tǒng)，可以高效解決分布式文件的存儲等工作[6]。首先，樣本數(shù)據(jù)在HDFS文件系統(tǒng)中進行分塊處理，得到n個數(shù)據(jù)塊；其次，數(shù)據(jù)塊被依次讀取至Map任務(wù)區(qū)域進行相應(yīng)運算處理，數(shù)個節(jié)點可以同時供Map函數(shù)運行，解決若干數(shù)據(jù)分片問題；接下來進入到Reduce函數(shù)處理環(huán)節(jié)，Reduce函數(shù)以并行化運行的方式處理Map函數(shù)輸出的中間結(jié)果。最后，得到被Map與Reduce處理完成的運算結(jié)果，作為最終結(jié)果輸出。

圖1 MapReduce計算過程

1.2 基于MapReduce的云計算K-means聚類算法實現(xiàn)

MapReduce計算模型在處理大規(guī)模數(shù)據(jù)問題上展現(xiàn)了并行、均衡負載等優(yōu)勢，行業(yè)技術(shù)人員愈發(fā)傾向于運用MapReduce模型解決數(shù)據(jù)挖掘問題[7]。在MapReduce計算模型的分布式云計算框架之下進行數(shù)據(jù)挖掘的方法較為豐富，K-means是一種經(jīng)典的數(shù)據(jù)聚類方法，其聚類原理是對比兩個樣本的歐氏距離從而判斷指標相似性大小，根據(jù)相似性進行數(shù)據(jù)歸類。海量數(shù)據(jù)樣本環(huán)境中，定義一個數(shù)據(jù)集M，任意獲得k個初始聚類中心，然后求取其他所有數(shù)據(jù)樣本與初始中心的歐氏距離[8]；接下來完成樣本與聚類中心的分類，分類遵循“最小距離”標準；最后統(tǒng)計各類中全部樣本的距離均值，同時將其作為此類別的聚類中心更新結(jié)果，當誤差平方和函數(shù)趨于最小值并且穩(wěn)定時終止運算。

K-means聚類算法的誤差平方和函數(shù)確定方式如下，定義數(shù)據(jù)集M的具體形式為M={x1,x2,……,xn}，樣本xi={xi1,xi2,……,xir}，樣本xj={xj1,xj2,……,xjr}，公式(1)為計算樣本xi、xj的歐式距離計算方法：

d(xi,xj)=

(1)

進而得到如公式(2)所示的誤差平方和函數(shù)：

(2)

公式中，K-means聚類算法的類別數(shù)量用K表示，第i類樣本數(shù)量以及樣本均值分別用ri、ni表示。

為更加高效、精準地實現(xiàn)K-means算法在分布式云計算環(huán)境下的數(shù)據(jù)挖掘任務(wù)，在經(jīng)典的 MapReduce計算模型基礎(chǔ)上引入Combiner函數(shù)，具體而言，為進行Map函數(shù)操作的機器布設(shè)Combiner函數(shù)解決一次性合并Map函數(shù)輸出結(jié)果的問題，無須多次反復(fù)合并操作[9]。利用優(yōu)化后的MapReduce計算模型完成K-means聚類的步驟如下：

Step 1：Map函數(shù)執(zhí)行運算。還原K-means聚類算法中k 個中心點，以并行方法求取中心點與數(shù)據(jù)對象間的距離，數(shù)據(jù)對象分類工作也依據(jù)該距離完成。求取云計算環(huán)境下服務(wù)器數(shù)據(jù)對象與聚類中心點的距離，以此更新此刻數(shù)據(jù)對象的聚類類型，各個樣本數(shù)據(jù)對象的聚類中心點即為當前Map函數(shù)的輸入項。

Step 2：Combiner函數(shù)優(yōu)化。對完成Map函數(shù)操作的數(shù)據(jù)實施Combiner處理，以差異性數(shù)據(jù)節(jié)點為介質(zhì)完成Map函數(shù)內(nèi)存寫入操作，以此節(jié)約內(nèi)存開銷及其成本投入，同時減少中間數(shù)據(jù)傳輸量。

Step 3：Reduce函數(shù)執(zhí)行運算。初始階段Combiner過程的中間結(jié)果獲取可通過Reduce函數(shù)過程實現(xiàn)，各簇的樣本數(shù)量、差異性維度坐標值統(tǒng)計情況均可一并獲得，由此得到更新后的中心坐標值，在硬盤主函數(shù)部分進行安全存儲。分布式云計算 MapReduce計算模型框架下，各服務(wù)器的數(shù)據(jù)初始中心點均由主函數(shù)負責(zé)采集與存儲，將中心點信息傳遞至Map函數(shù)部分，從宏觀上向K-means聚類算法數(shù)據(jù)挖掘過程發(fā)號施令。

2 實驗分析

搭建云計算數(shù)據(jù)挖掘?qū)嶒炂脚_進行數(shù)據(jù)挖掘測試，系統(tǒng)環(huán)境為Ubuntul2.04，以驗證基于MapReduce的分布式云計算數(shù)據(jù)挖掘方法的可行性與性能。本次分布式云計算測試平臺包括6臺計算機，構(gòu)成集群式數(shù)據(jù)測試集群。其中，云計算環(huán)境的各個節(jié)點配備Inter Corel 7處理器，2.5GHz主頻，擁有8G內(nèi)存。本次測試從權(quán)威數(shù)據(jù)平臺獲得5個有效數(shù)據(jù)集作為數(shù)據(jù)挖掘的測試樣本，數(shù)據(jù)樣本總規(guī)模為1.02GB。為突出本文算法在云計算環(huán)境下的數(shù)據(jù)挖掘優(yōu)勢，同時選取未增加Combiner函數(shù)處理的傳統(tǒng)云計算K-means聚類算法以及G-means聚類算法作為對比測試方法，詳細的實驗結(jié)果如下。

整個數(shù)據(jù)挖掘測試過程中，隨著分布式計算節(jié)點的增加，三種數(shù)據(jù)聚類算法的時間開銷情況如表1所示。

表1 不同數(shù)據(jù)聚類算法的時間開銷情況/s

表1數(shù)據(jù)顯示，當分布式計算節(jié)點由1個增加至6個時，三種算法的時間開銷均呈下降趨勢。同時，可以明顯看出，本文算法的初始時間開銷便是三者中最低，直到節(jié)點增加至6個時，聚類時間開銷僅為4121s，為三種算法中效率最高者。這是因為本文算法在云計算環(huán)境下采用了 MapReduce計算模型，并且在Map函數(shù)操作的機器上布設(shè)Combiner函數(shù)解決一次性合并Map函數(shù)輸出結(jié)果的問題，無需多次合并操作，大大節(jié)省了算法運行的時間。

此外，還可以看出，隨著節(jié)點數(shù)量增加，本文算法聚類時間減少的數(shù)據(jù)量存在一定規(guī)律性，前期時間減少幅度約為2000s，后期時間減少幅度約為1000s，沒有大幅度波動情況，說明此算法在云計算環(huán)境下進行數(shù)據(jù)挖掘的穩(wěn)定性較優(yōu)。

3 結(jié)論

云計算的分布式計算特征使其成為大數(shù)據(jù)處理的必然發(fā)展趨勢，以“任務(wù)分發(fā)—合并”的形式解決大規(guī)模數(shù)據(jù)分析與處理問題，MapReduce模型則是突出的云計算工具。本文對云計算環(huán)境下的MapReduce計算模型進行優(yōu)化，獲得一種可以高效輔助K-means聚類算法完成數(shù)據(jù)挖掘的方案。經(jīng)過測試得出，該算法在聚類效率方面優(yōu)勢顯著，同時獲得了較優(yōu)的數(shù)據(jù)挖掘穩(wěn)定性。