Hadoop數(shù)據(jù)挖掘并行算法框架

論文提出了hadoop云平臺(tái)實(shí)現(xiàn)數(shù)據(jù)挖掘并行算法的編程框架。首先對(duì)數(shù)據(jù)挖掘算法和應(yīng)用和原理進(jìn)行了分析，然后介紹了Map/Reduce并行編程流程，從input split，到map（）的（key，value），和reduce對(duì)（key，list{value}）的簡(jiǎn)答計(jì)算。詳細(xì)設(shè)計(jì)了數(shù)據(jù)挖掘算法的通用Map/Reduce編程框架，分析了算法關(guān)鍵技術(shù)。最后應(yīng)用在sprint和k-mean算法上，實(shí)驗(yàn)結(jié)果說(shuō)明hadoop云平臺(tái)能實(shí)現(xiàn)數(shù)據(jù)挖掘并行算法，提高加速比。

【關(guān)鍵詞】數(shù)據(jù)挖掘 Map/Reduce 并行計(jì)算

數(shù)據(jù)挖掘是知識(shí)發(fā)現(xiàn)KDD的關(guān)鍵環(huán)節(jié)，并且在連續(xù)數(shù)值、異構(gòu)數(shù)據(jù)、計(jì)算模型等方面有發(fā)展。知識(shí)挖掘是在大量數(shù)據(jù)中發(fā)現(xiàn)有效的、新穎的、有用的以及最終可理解知識(shí)的非平凡過(guò)程，所用到的技術(shù)包括統(tǒng)計(jì)學(xué)、數(shù)據(jù)庫(kù)、數(shù)值計(jì)算、機(jī)器學(xué)習(xí)和算法。數(shù)據(jù)挖掘技術(shù)包括關(guān)聯(lián)發(fā)現(xiàn)、分類(lèi)器、聚類(lèi)算法和序列模式等，它們的應(yīng)用分別是：分類(lèi)算法用在客戶(hù)分類(lèi)、目標(biāo)市場(chǎng)選擇、異常分析（信用卡欺詐等）；聚類(lèi)算法用在市場(chǎng)銷(xiāo)售、土地使用、金融領(lǐng)域，互聯(lián)網(wǎng)WWW，地震防災(zāi)、圖像處理；關(guān)聯(lián)規(guī)則用在購(gòu)物籃分析、交叉銷(xiāo)售、產(chǎn)品目錄設(shè)計(jì)；序列模式應(yīng)用在客戶(hù)購(gòu)買(mǎi)行為模式預(yù)測(cè)、自然災(zāi)害預(yù)測(cè)、DNA序列分析、工業(yè)控制。

分類(lèi)算法包括兩個(gè)步驟，首先對(duì)訓(xùn)練數(shù)據(jù)集建立分類(lèi)規(guī)則的訓(xùn)練模型，然后對(duì)未知樣本數(shù)據(jù)進(jìn)行分類(lèi)。聚類(lèi)算法則有兩個(gè)應(yīng)用：將數(shù)據(jù)庫(kù)分成差異明顯的不同群組，發(fā)現(xiàn)與其他簇差異較高的少量簇，例如發(fā)現(xiàn)較高賠償成本的保險(xiǎn)用戶(hù)。聚類(lèi)算法將樣本集分成簇，使簇中對(duì)象相似，而簇間對(duì)象距離差異大。關(guān)鍵過(guò)程是計(jì)算樣本數(shù)據(jù)與所有簇中心點(diǎn)的距離，根據(jù)最近距離選擇樣本所在簇；對(duì)新簇計(jì)算新的中心點(diǎn)。關(guān)聯(lián)規(guī)則算法則是在商業(yè)數(shù)據(jù)中，發(fā)現(xiàn)事務(wù)集合與對(duì)象集合之間的頻繁模式，生成關(guān)聯(lián)規(guī)則，而且具有支持度和可信度。頻繁模式設(shè)置min_sup，應(yīng)用建立樹(shù)和人工智能的剪枝技術(shù)，獲得頻繁閉項(xiàng)集。盡管數(shù)據(jù)挖掘在商業(yè)領(lǐng)域獲得了巨大的資金收益，然而新時(shí)期需要處理的是海量數(shù)據(jù)，使用單機(jī)的算法不能適應(yīng)互聯(lián)網(wǎng)環(huán)境的要求，因此數(shù)據(jù)挖掘并行算法的研究是勢(shì)在必行的。

1 Hadoop云平臺(tái)組成

Hadoop云計(jì)算平臺(tái)是Doug Cutting主導(dǎo)開(kāi)發(fā)的開(kāi)源項(xiàng)目，使用java語(yǔ)言，具有實(shí)用性，受到廣泛歡迎。Hadoop包括10個(gè)子項(xiàng)目。它的物理存儲(chǔ)是分布式文件系統(tǒng)HDFS。HDFS將數(shù)據(jù)文件分成64M數(shù)據(jù)塊，并且存儲(chǔ)在不同數(shù)據(jù)節(jié)點(diǎn)上。HDFS用備份方式防止出現(xiàn)讀寫(xiě)錯(cuò)誤，因此每個(gè)數(shù)據(jù)塊有三個(gè)副本，存儲(chǔ)在不同機(jī)柜。Hadoop可部署在廉價(jià)的微型機(jī)上，集群系統(tǒng)包括上千個(gè)服務(wù)器，因此Hadoop的應(yīng)用程序可處理海量數(shù)據(jù)，幾個(gè)GB甚至TB。

Hadoop的編程模型是Map/Reduce。Map/Reduce框架是集中管理，只有一個(gè)管理器稱(chēng)為命名節(jié)點(diǎn)namenode，有多個(gè)工作節(jié)點(diǎn)稱(chēng)為數(shù)據(jù)節(jié)點(diǎn)datanode。Namenode接收用戶(hù)提交的作業(yè)，并且用JobDriver初始化一個(gè)job。Namenode將并且將用戶(hù)作業(yè)的輸入數(shù)據(jù)劃分成split，并且將用戶(hù)作業(yè)劃分成不同的map任務(wù)，分配給空閑數(shù)據(jù)節(jié)點(diǎn)，稱(chēng)為map節(jié)點(diǎn)。Mapper接受split，在setup階段建立鍵值對(duì)。在map函數(shù)運(yùn)行結(jié)束后，產(chǎn)生中間鍵值對(duì)結(jié)果，并且向namenode發(fā)出中間結(jié)果存儲(chǔ)信息。Namenode接收到位置信息后，發(fā)送到reduce節(jié)點(diǎn)。Reducer通過(guò)http將所有相關(guān)map函數(shù)的輸出結(jié)果復(fù)制到本地存儲(chǔ)器，進(jìn)行歸并和簡(jiǎn)單運(yùn)算，將結(jié)果按規(guī)格存儲(chǔ)在HDFS中。在reduce函數(shù)執(zhí)行前，應(yīng)產(chǎn)生列表。

2 數(shù)據(jù)挖掘算法Map/Reduce并行框架

Hadoop云平臺(tái)設(shè)計(jì)數(shù)據(jù)挖掘并行算法包括4層，底層是分布式計(jì)算層，用戶(hù)構(gòu)建Hadoop系統(tǒng)；第二層是數(shù)據(jù)挖掘并行算法層，包括數(shù)據(jù)預(yù)處理模塊、主算法程序、模式評(píng)估模塊等；第三層是業(yè)務(wù)應(yīng)用層，包括用戶(hù)業(yè)務(wù)響應(yīng)模塊和工作流程。最上層是用戶(hù)界面，包括界面程序、用戶(hù)管理模塊等。數(shù)據(jù)挖掘算法包括三個(gè)階段：數(shù)據(jù)預(yù)處理、數(shù)據(jù)挖掘、數(shù)據(jù)樣本類(lèi)型、簇或者關(guān)聯(lián)規(guī)則輸出。對(duì)每一個(gè)階段都使用Map/Reduce并行框架。

如果對(duì)分類(lèi)算法進(jìn)行Map/Reduce編程，則在第二階段map將根據(jù)屬性表的條件產(chǎn)生新的節(jié)點(diǎn)，因此reduce節(jié)點(diǎn)增加；而在聚類(lèi)算法中，reduce節(jié)點(diǎn)將計(jì)算所有簇的新中心點(diǎn)，因此reduce的數(shù)量少。input split在經(jīng)過(guò)數(shù)據(jù)挖掘程序的執(zhí)行后，輸出樣本數(shù)據(jù)的分類(lèi)、所有簇、數(shù)據(jù)庫(kù)規(guī)則。在數(shù)據(jù)挖掘并行算法中，概率計(jì)算、屬性表劃分、距離計(jì)算，和節(jié)點(diǎn)的并行分配是關(guān)鍵技術(shù)。例如：決策樹(shù)算法劃分?jǐn)?shù)據(jù)集使用屬性選擇度量，有信息增益等三種條件。k-means算法的距離計(jì)算有歐式距離等三種數(shù)學(xué)公式，用以選擇樣本所在簇；聚類(lèi)準(zhǔn)則函數(shù)是迭代停止的條件，有全局誤差函數(shù)和簇類(lèi)中心誤差值函數(shù)兩種公式。

3 實(shí)驗(yàn)分析

將數(shù)據(jù)挖掘的map/reduce框架應(yīng)用在sprint算法和k-means算法上，hadoop云平臺(tái)有4個(gè)節(jié)點(diǎn)，則加速比分別增加了2.1倍和1.3倍。因此，hadoop云平臺(tái)的數(shù)據(jù)挖掘并行算法是可行的。只是實(shí)驗(yàn)設(shè)置相對(duì)簡(jiǎn)單，今后應(yīng)予以改進(jìn)。

4 總結(jié)

Hadoop云平臺(tái)為海量數(shù)據(jù)的分布式處理提供了開(kāi)發(fā)環(huán)境。數(shù)據(jù)挖掘算法的各種類(lèi)型能應(yīng)用map/reduce編程框架進(jìn)行并行計(jì)算，實(shí)現(xiàn)了分布式數(shù)據(jù)和大量數(shù)據(jù)實(shí)時(shí)計(jì)算，在當(dāng)今大數(shù)據(jù)和物聯(lián)網(wǎng)迅捷發(fā)展的形勢(shì)下將有良好的應(yīng)用前景。

參考文獻(xiàn)

[1]胡昕.基于Hadoop海量數(shù)據(jù)挖掘技術(shù)分析[J].企業(yè)導(dǎo)刊，2014（11）：154，158.

[2]趙偉.基于Hadoop的數(shù)據(jù)挖掘算法并行化研究[碩士學(xué)位論文][D].西南交通大學(xué)，2015.

作者簡(jiǎn)介

徐嘯（1993-），男，河南省漯河市人?，F(xiàn)為香港浸會(huì)大學(xué)碩士在讀學(xué)生。

作者單位

香港浸會(huì)大學(xué) 中華人民共和國(guó)香港特別行政區(qū) 999077