楊震宇

摘要：大規(guī)模數據處理分析工作，在單個處理節(jié)點上部署時往往會遇到機器性能局限所帶來的計算瓶頸。如今，技術更加先進且成本低廉的分布式計算平臺為這一問題帶來了改善的解決方案。文章運用MapReduce框架這一優(yōu)勢，研究了將數據挖掘的任務部署到分布式平臺上的方案以及提出了相關研究展望。

關鍵詞：MapReduce框架；Hadoop；數據挖掘方法；數據處理；聚類算法 文獻標識碼：A

中圖分類號：TP316 文章編號：1009-2374（2017）04-0008-03 DOI：10.13535/j.cnki.11-4406/n.2017.04.005

1 概述

隨著時代發(fā)展，各行各業(yè)的日常運營過程中都會產生海量的數據信息，甚至這些信息正呈幾何級數增長。無論是零售業(yè)、制造業(yè)還是政府機關和校園教育都可以從數據信息中發(fā)掘出有用的信息來幫助領導者做出決定，進一步優(yōu)化自身發(fā)展的各處細節(jié)。數據挖掘就是解決這類問題的重要方法，但隨之而來的便是如何快速有效地處理超大規(guī)模數據的疑問，提高計算核心的計算能力的確是重要的解決方案，而這確實不易實現(xiàn)。

鑒于半導體技術的不斷進步，科技工藝幾乎觸及其極限，當年的摩爾定律已經無法支撐著如今的制造廠商有效定期提升其產品的處理、計算能力。對于解決大數據信息的有效處理問題，時下流行的方案便是應用云計算，將分析處理任務交給分布式計算平臺，在節(jié)約計算的時間同時，巧妙地規(guī)避了硬件既定的制約。由當年Google公司提出的MapReduce計算模型已成為了分布式計算平臺中首選的數據計算框架，本文將對在該框架下部署大規(guī)模的數據挖掘進行研究，并探尋可行的解決

方案。

2 研究背景

20世紀60年代，IBM公司推出的CICS成為了最早研究中間件技術的嘗試，在80年代中期，貝爾實驗室提出了Tuxedo，成為第一代正式中間件產品，90年代發(fā)展出很多不同用途的產品。中間件技術幫助信息能夠在不同系統(tǒng)甚至網絡環(huán)境中進行傳輸，幫助分布式系統(tǒng)的計算方式取得了可喜的進步。在后期也出現(xiàn)了如網格技術、移動Agent技術、P2P技術等多方面的探索成果，但缺乏技術的統(tǒng)一標準也制約了它們廣泛應用的能力。在21世紀初的幾年，世界范圍內對于分布式計算平臺的研究方興未艾。當科技界正探討如何在集群計算平臺中處理大數據樣本時，美國科技公司Google的工程師團隊率先提出了MapReduce框架的概念，并給出了實施方案，其中除了該計算框架，還包括分布式文件系統(tǒng)、海量數據的分布式數據庫系統(tǒng)、分布式鎖等重要設計模型。由于提出了一整套的分布式計算的解決方案，該框架的提出引起了業(yè)界廣泛關注并迅速普及。

利用MapReduce框架進行數據處理的研究也取得了相當多的成果：參考文獻[3]提出了在該框架下運行機器學習算法程序來對文本信息進行處理的方案，將大規(guī)模的文本處理并行化提升了運算速率；參考文獻[4]在對MapReduce框架原理進行深度研究后，提出了利用樹構造算法與多路查詢算法對內存讀寫進行開銷評估，增強該框架的高并發(fā)情境中的讀寫速率；參考文獻[5]提出了將成熟算法部署到MapReduce框架中求解高復雜度問題的思路。

數據挖掘作為網絡時代最重要的信息處理技術，已經有了多種領域的應用。參考文獻[6]中針對目前網站訪問過程中用戶端加載速度不理想的現(xiàn)狀，提出對用戶瀏覽數據進行數據挖掘處理，獲得個人喜好以及訪問興趣，對網頁進行預讀取，可以有效提升網頁加載速度；參考文獻[7]用過綜合運用關聯(lián)算法以及聚類算法可以實現(xiàn)一自適應的檢測模型，可以有效實時檢測出DoS攻擊并分析查出異常的數據包的攻擊類別；參考文獻[8]創(chuàng)新地將數據挖掘技術應用于運營商客戶消費行為的趨勢分析中，提出了多維度事實物理分類聚類算法，有效獲取多維數據中的數據類型，能提高運營商提供服務的精確度；參考文獻[9]提出將數據挖掘方法應用到教育領域中的EDM新技術，通過發(fā)掘出收集的教育環(huán)境數據中的數據獨有的類型信息，進而發(fā)現(xiàn)受教育者的學習方式以及興趣，提升其學習效果。

由以上的研究成果可以發(fā)現(xiàn)，分布式系統(tǒng)中的MapReduce框架能夠幫助多種大數據運算高效完成多類型、高強度的計算任務并提供更簡潔易于管理的計算流程。數據挖掘算法也發(fā)展出了很多的應用方案，能夠解決很多復雜情景中的分類及趨勢分析問題。本文將繼續(xù)對MapReduce框架與數據挖掘算法進行合并研究，探究出將數據挖掘任務部署在MapReduce下的方案。

3 MapReduce并行化計算

作為分布式計算平臺中的計算框架，MapReduce主要完成了兩大任務：（1）“Map”（映射），將要進行處理或計算的數據樣本進行分割并分發(fā)至從工作節(jié)點；（2）“Reduce”（歸約），將各個從節(jié)點的數據計算結果統(tǒng)一進行收集進而獲取總的結果。程序設計者只需要將數據對象所需要進行并行計算的部分做設計，分發(fā)至各個從節(jié)點上，最后將需要進行的數據歸約處理的規(guī)則“告知”Reduce節(jié)點，而非需要詳細了解系統(tǒng)的底層設計。下面將對該框架進行詳細的研究說明：

3.1 Map與Reduce

如上文所介紹，Map、Reduce分別對應了MapReduce框架需要進行的兩大任務，映射與歸約。通過將數據處理任務的合理分配，對節(jié)點的計算結果進行規(guī)約匯總，能夠實現(xiàn)實時的并行化計算，由于可以將處于同一網絡中的普通計算機虛擬化為分布式計算節(jié)點，充分利用計算機內存來進行網絡數據交換與運算，能夠有效節(jié)省計算成本提高計算效率。

Map任務根據設計主要分為4大流程：record reader、mapper、combiner和partitioner：（1）record reader：負責解析分發(fā)的小的數據塊解析為形式，鍵是數據在reducer流程中處理時分組依據，值是reducer需要分析的數據。作為函數的參數，傳遞給mapper；（2）mapper：通過自定義的map函數接收上一步驟解析的鍵值對來計算并產生0個或多個新的鍵值對結果，例如的計算輸出作為中間結果可以記為List（）。List數據可以繼續(xù)傳遞到combiner；（3）combiner：MapReduce框架為了減少map到reduce過程中數據發(fā)送量，通過允許用戶自定義函數對指定的鍵名對做單一map范圍內的中間結果聚合，能夠充分壓縮無效的帶寬占用、節(jié)約網絡流量，通過該流程可以帶來可觀的性能提升；（4）partitioner：為了將Map任務不同的數據按不同的屬性來分類處理并對應唯一處理的reducer，可以定制partitioner的默認行為以保證不同的mapper計算的中間結果的相同鍵名能夠被同一reducer提取。

Reduce任務由框架的設計主要分為：shuffle and sort、reducer和輸出格式（output format）3大流程：（1）shuffle and sort：主要是將Map任務提交的輸出數據提取到reduce節(jié)點中，將中間結果進行數據大小分析，滿足條件則直接儲存到內存中，通過sort流程進而對數據建立頂堆的規(guī)則進行重組，可以幫助數據信息在reduce任務中進行迭代處理；（2）reducer：對上一階段的處理好的作為輸入參數，并利用已有的或自定義例如聚合、過濾等方式對數據進行歸約處理。reduce函數的輸入是鍵以及包含與該鍵對應的所有值的List記錄，例如：作為上一步驟的中間結果，其輸出可表示為；（3）output format：接收到reduce函數輸出最終結果的鍵值對，通過record writer將它們按照指定的格式寫入到輸出文件中。

3.2 框架工作流程

根據MapReduce框架的map與reduce任務的設計，其框架的計算流程如圖1所示：

圖1 MapReduce計算流程示意圖

通過圖1所示，運用Google公司提出的Hadoop分布式計算平臺的文件系統(tǒng)HDFS來實現(xiàn)樣本數據的存儲、傳輸以及讀取，預處理的數據由HDFS中的待處理數據分塊得出，框架將分塊后的數據塊讀入到Map任務中，通過數據解析模塊的處理，將鍵值對數據作為參數傳遞給map函數計算結果以鍵名存儲到list中，中間結果隨機傳輸到下一階段Reduce任務中，通過打亂并排序操作對中間結果進行處理傳輸到reduce流程中，經過歸約計算輸出格式化輸出存儲到HDFS中。該框架的主從模式的并行化計算的架構由圖2展示：

圖2 MapReduce并行計算示意圖

通過圖2所示，主節(jié)點通過HDFS分發(fā)數據處理作業(yè)亦稱作Job-Tracker作為分發(fā)工作的追蹤者，HDFS能夠進一步與其余從節(jié)點通過接收分塊數據并進一步map計算，上傳中間結果傳輸給reduce計算節(jié)點進行歸約運算，將計算結果上傳到HDFS供主節(jié)點讀取。

4 MapReduce下的數據挖掘綜述

在數據挖掘現(xiàn)有的常用算法中，主要分三類，分別為分類與預測、聚類分析和頻繁項挖掘。數據挖掘過程主要體現(xiàn)在數據的預處理、樣本的統(tǒng)計數據的計算以及概率學計算的使用，這些都可以簡化為map函數的相關程序進行并行化計算。

通過前文的相關描述，將數據挖掘任務部署到MapReduce框架下是可行的。在不對數據挖掘的應用領域做要求的情況下，對于分類與預測和聚類的數據挖掘進行MapReduce并行化運算的方案進行研究。

4.1 分類與預測的并行化研究

該類算法的思路是：（1）對預先獲取的大量樣本對象進行學習運算，獲得對數據分類的分類器；（2）運用構建的分類器對目標數據進行分類的判斷。在MapReduce框架中主要以離散方式對大數據對象進行運算操作的，運算規(guī)模是具有很大彈性的。而針對像樸素貝葉斯分類器的MapReduce實現(xiàn)，需要做出相關的改進。

訓練階段：對于樣本的離散取值的統(tǒng)計工作可以并行化處理，包括對屬性的均值、標準差計算，都可以交給map函數來處理。進而需要將統(tǒng)計結果（中間結果）進行規(guī)約化處理，該項流程也能夠寫入reduce函數來實現(xiàn)。整合的結果并不能直接用作分類器，因為受到并行化處理的影響，其表現(xiàn)仍是離散的，無法滿足貝葉斯分類算法的連續(xù)性要求。此時需要將結果放到主處理函數中來進行進一步的連續(xù)性轉換，才可得出最終的分類器。

預測階段：將數據樣本提取到Map任務中，完成對數據的計算及分類處理，輸出的分類中間結果交由Reduce任務來進行最終分類概率的統(tǒng)計。

圖3 訓練階段流程示意圖

在預測過程處理時，應對數據樣本進行規(guī)模判斷，如果較小，可以單一機器完成，則不需要其他操作；如果較大，便將分類器模型分配到各個map節(jié)點中，按照主從模式來進行分布式運算來減少計算時間。

4.2 聚類算法的并行化研究

聚類算法目的是運用分析方法對數據樣本進行處理，將對象整體劃分為簇的單位，應做到被分類到同簇的數據對象應是相似的，不同則不相似。重點是需要對數據樣本進行維度特征的相似度計算（例如k-means的簇中對象的平均值，k-modes算法中需要求出不同維度下的眾數），并不斷進行迭代直至結果穩(wěn)定。將聚類算法在MapReduce框架下進行并行化運算的實現(xiàn)思路是：（1）Map任務階段，選取初輪的簇中心，分配到Map節(jié)點上，通過map函數計算每個數據樣本的聚類中心距，通過目標函數累加，獲取的每個簇的中心數據傳遞到Reduce節(jié)點；（2）Reduce任務階段，接收Map節(jié)點的分類數據進行規(guī)約化計算，匯總計算目標函數中的值，獲取并更新每個聚類中心的數據，并繼續(xù)傳遞給主函數進行判斷；（3）主函數處理階段，判斷計算結果是否與上一輪沖突，如果兩輪結果不同則返回Map、Reduce任務繼續(xù)運算，否則停止并輸出結果。

該類算法的性能主要由需要進行迭代運算次數決定，通過將任務分配到分布式平臺上，可以顯著減少不必要的迭代操作，從而提升算法效率。如能獲得快速收斂的相似度計算函數方法，該算法計算速率仍能取得較大的增強。

5 研究展望

通過云計算方式去處理日益增長的巨大規(guī)模的數據已經成為時下的發(fā)展趨勢，數據挖掘也同時獲得了數據分析業(yè)界的重點關注，通過前文描述的相關算法，可以看出該領域日趨成熟的特點，多學科技術的應用也使得其適用面愈加寬廣。

作為分布式系統(tǒng)的重要組成部分，MapReduce框架有著不可替代的地位，尤其在大數據處理需求逐年增長，并行化計算體現(xiàn)著顯著重要性的業(yè)界環(huán)境中，與其余并發(fā)模型相比較，該框架能夠提供較高的編程效率，并且能充分且高效地利用分布式系統(tǒng)各個計算節(jié)點的資源，都使得它能夠占據領先地位。同時提供了較完善的故障處理的解決機制，也是其成為容錯性強的并行化模型的重要優(yōu)勢。

利用MapReduce框架來實現(xiàn)龐大計算的數據挖掘，能夠在如今對計算資源較為普遍但難以應付巨型數據處理任務的現(xiàn)實中，取得空間、時間成本與計算開銷較為理想的平衡。但在研究過程中，也發(fā)現(xiàn)仍有一些問題需要在今后的工作中進行改善：（1）MapReduce框架中的大量中間計算產生的臨時讀寫文件可能承載了數據挖掘運算中的重要數據，如何能夠在進一步的迭代過程中加以利用和回溯仍是需要思考的問題；（2）許多數據挖掘算法涉及到機器學習方法，某些監(jiān)督型算法如何有效地在map過程中進行仍將需要投入精力去研究。

參考文獻

[1] 周曉峰，王志堅.分布式計算技術綜述[J].計算機時代，2004，（12）.

[2] Dean J，Ghemawat S.MapReduce：Simplified Data Processing on Large Clusters[A].Conference on Symposium on Opearting Systems Design&Implementation[C].2004.

[3] 李銳，王斌.文本處理中的MapReduce技術[J].中文信息學報，2012，26（4）.

[4] 亓開元，韓燕波，趙卓峰，等.支持高并發(fā)數據流處理的MapReduce中間結果緩存[J].計算機研究與發(fā)展，2013，50（1）.

[5] 吳昊，倪志偉，王會穎.基于MapReduce的蟻群算法[J].計算機集成制造系統(tǒng)，2012，18（7）.

[6] 徐寶文，張衛(wèi)豐.數據挖掘技術在Web預取中的應用研究[J].計算機學報，2001，24（4）.

[7] 高能，馮登國，向繼.一種基于數據挖掘的拒絕服務攻擊檢測技術[J].計算機學報，2006，29（6）.

[8] 劉蓉，陳曉紅.基于數據挖掘的移動通信客戶消費行為分析[J].計算機應用與軟件，2006，23（2）.

[9] Romero C，Ventura S.Data mining in education[J].Wiley Interdisciplinary Reviews Data Mining&Knowledge Discovery，2013，3（1）.

[10] 李成華，張新訪，金海，等.MapReduce：新型的分布式并行計算編程模型[J].計算機工程與科學，2011，33（3）.

[11] 李建江，崔健，王聃，等.MapReduce并行編程模型研究綜述[J].電子學報，2011，39（11）.

[12] 蔣良孝.樸素貝葉斯分類器及其改進算法研究[D].中國地質大學，2009.

[13] Han J，Kamber M.Data Mining：Concepts and Techniques，Morgan Kaufmann[J].Machine Press，2006，5（4）.

（責任編輯：黃銀芳）