Hadoop數據挖掘并行算法框架

論文提出了hadoop云平臺實現數據挖掘并行算法的編程框架。首先對數據挖掘算法和應用和原理進行了分析，然后介紹了Map/Reduce并行編程流程，從input split，到map（）的（key，value），和reduce對（key，list{value}）的簡答計算。詳細設計了數據挖掘算法的通用Map/Reduce編程框架，分析了算法關鍵技術。最后應用在sprint和k-mean算法上，實驗結果說明hadoop云平臺能實現數據挖掘并行算法，提高加速比。

【關鍵詞】數據挖掘 Map/Reduce 并行計算

數據挖掘是知識發現KDD的關鍵環節，并且在連續數值、異構數據、計算模型等方面有發展。知識挖掘是在大量數據中發現有效的、新穎的、有用的以及最終可理解知識的非平凡過程，所用到的技術包括統計學、數據庫、數值計算、機器學習和算法。數據挖掘技術包括關聯發現、分類器、聚類算法和序列模式等，它們的應用分別是：分類算法用在客戶分類、目標市場選擇、異常分析（信用卡欺詐等）；聚類算法用在市場銷售、土地使用、金融領域，互聯網WWW，地震防災、圖像處理；關聯規則用在購物籃分析、交叉銷售、產品目錄設計；序列模式應用在客戶購買行為模式預測、自然災害預測、DNA序列分析、工業控制。

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

1 Hadoop云平臺組成

Hadoop云計算平臺是Doug Cutting主導開發的開源項目，使用java語言，具有實用性，受到廣泛歡迎。Hadoop包括10個子項目。它的物理存儲是分布式文件系統HDFS。HDFS將數據文件分成64M數據塊，并且存儲在不同數據節點上。HDFS用備份方式防止出現讀寫錯誤，因此每個數據塊有三個副本，存儲在不同機柜。Hadoop可部署在廉價的微型機上，集群系統包括上千個服務器，因此Hadoop的應用程序可處理海量數據，幾個GB甚至TB。

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

2 數據挖掘算法Map/Reduce并行框架

Hadoop云平臺設計數據挖掘并行算法包括4層，底層是分布式計算層，用戶構建Hadoop系統；第二層是數據挖掘并行算法層，包括數據預處理模塊、主算法程序、模式評估模塊等；第三層是業務應用層，包括用戶業務響應模塊和工作流程。最上層是用戶界面，包括界面程序、用戶管理模塊等。數據挖掘算法包括三個階段：數據預處理、數據挖掘、數據樣本類型、簇或者關聯規則輸出。對每一個階段都使用Map/Reduce并行框架。

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

3 實驗分析

將數據挖掘的map/reduce框架應用在sprint算法和k-means算法上，hadoop云平臺有4個節點，則加速比分別增加了2.1倍和1.3倍。因此，hadoop云平臺的數據挖掘并行算法是可行的。只是實驗設置相對簡單，今后應予以改進。

4 總結

Hadoop云平臺為海量數據的分布式處理提供了開發環境。數據挖掘算法的各種類型能應用map/reduce編程框架進行并行計算，實現了分布式數據和大量數據實時計算，在當今大數據和物聯網迅捷發展的形勢下將有良好的應用前景。

參考文獻

[1]胡昕.基于Hadoop海量數據挖掘技術分析[J].企業導刊，2014（11）：154，158.

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

作者簡介

徐嘯（1993-），男，河南省漯河市人。現為香港浸會大學碩士在讀學生。

作者單位

香港浸會大學 中華人民共和國香港特別行政區 999077