基于MapReduce的數據挖掘平臺設計與實現

黃 斌，許舒人，蒲 衛

(1.中國科學院軟件研究所軟件工程技術中心，北京100190;2.中國科學院研究生院，北京100190;3.解放軍衛生信息中心，北京100842)

0 引言

2009年全球存儲的信息總量達到為8000億Gbt。IDC預測到2020年，全球將會存儲35Zbt(1Zbt=240Gbt)的信息量。社交網絡、電子商務、微博、音視頻分享等互聯網領域以及研究機構科學實驗源源不斷地產生大量的數據，單一數據庫存儲服務已經無法滿足數據多元化與大規模數據挖掘的需求。

在商業領域，從商業決策、搜索引擎、社交網絡、推薦系統，到垃圾郵件檢測與廣告投放，對大規模數據進行及時、有效地分析已成為這些商業應用能在競爭中脫穎而出的重要因素;在科學研究領域，天文學的圖片數據、生物學中的人類基因組數據以及物理學中粒子加速器產生的實驗數據的數據量都非常大，大數據量給科學分析帶來困難。

面對增長迅速的數據量，如何從數據中發掘有用的信息成為當前大多數數據挖掘系統面臨的問題。對于此類大數據集的數據分析與挖掘系統，Cohen等人在文獻 ［1］中總結了這類系統需要具備的特性:

(1)數據適應性:系統可接受多種類型的數據，避免系統對存儲的數據的類型、結構和數據完整性的強要求，從而避免通常的數據倉庫對數據的強要求帶來的問題;

(2)敏捷性:系統能夠適應數據遞增且更新頻繁的應用場景;

(3)分析深度:提供對數據分析多角度、多切面的分析，可便捷得加入復雜的概率統計和機器學習算法，適應多類型數據分析需求。

迫于數據量的急劇增長，大量的數據存儲在數據庫與數據倉庫中，關系型數據庫通常提供進行數據分析與挖掘的數據分析工具，例如，SAP BusinessObjects Explorer［2］、Matlab Spider［3］、SQL Server Analysis Services［4］、weka［5］等都提供了此類工具。然而，以關系型數據庫為基礎的數據挖掘系統存在以下幾個弊端:

(1)在龐大數據量背景下，數據遷移所帶來的時間損失巨大，在此種情況下，把計算力移向數據是比數據遷移到計算系統更有效率的方法;

(2)大多數數據庫分析系統需要將所有的數據放入內存中，對于占多數的大數據集，一般只能通過抽樣的方式使得數據量縮小到內存可接受的范圍內，數據的抽樣通常會導致數據信息量丟失;

(3)在處理速度上，不斷增加的數據很容易造成數據庫索引的不斷增加，索引增加的滯后性容易導致數據庫的處理速度降低。

數據庫系統在數據處理效率和可處理的數據量無法滿足當前數據的爆炸式增長，效率與容量成為以數據庫為基礎的數據挖掘系統的最大瓶頸。

基于模型驅動的開發方法與組件開發技術，本文提出一種可擴展數據挖掘平臺，運用MapReduce框架的擴展性與并行能力，定義可重用的數據挖掘組件和Connector組件，提高了數據挖掘過程敏捷性。系統主要解決以下3個方面的問題:

(1)定義數據挖掘過程中的挖掘組件模型，用戶可復用系統提供的數據挖掘組件來快速定義數據挖掘過程;

(2)通過GMF技術實現對數據挖掘過程的可視化定義，并通過代碼生成引擎實現挖掘過程到可執行代碼的轉換;

(3)定義Connector可重用組件，實現對多種數據存儲系統的數據訪問。

1 研究背景

Google 提出的分布式文件系統 GFS［6］和 MapReduce［7］框架為大規模并行數據計算與分析提供了重要的參考。MapReduce框架將數據的運算抽象成“Map”和“Reduce”兩個階段，以分而治之的思想簡化了大規模數據集的并行計算過程。Hadoop是MapReduce框架與分布式文件系統GFS的開源實現，它實現的MapReduce框架和HDFS分布式文件系統使得在成本可控的情況下處理海量數據成為可能。業界圍繞著Hadoop發展起來了一系列工具，這些工具擴展了Hadoop的運用場景與應用領域。如圖1展示了Hadoop軟件棧 (Hadoop software stack)，以Hadoop為核心，出現了在數據存儲、處理、訪問、管理、數據連接等幾個層次的軟件。它們提升了Hadoop的易用性、可維護性以及對多種編程語言的支持能力。

圖1 Hadoop Software Stack

其中，Hbase［8］是一個以 BigTable［9］為原型的高性能、面向列、強一致性存儲系統;Hive［10］是一個基于Hadoop實現的數據倉庫工具;Pig使用戶可以通過Pig-latin語言定義運行于Hadoop上的數據流程;Avro是一個面向Hadoop的數據序列化系統;Sqoop［11］是一個用于關系型數據庫與HDFS之間數據遷移的工具;Zookeeper用于分布式應用中的集群管理、狀態同步服務、同步鎖服務;Chukwa是一個用于進行集群運行日志收集、分析和展示的管理工具。

以上軟件與工具在一定程度上提升了Hadoop的易用性和數據分析的能力，然而Hadoop對數據分析、數據挖掘算法以及可視化支持的缺乏使用戶在運用Hadoop進行數據挖掘過程中暴露出效率低下、重復開發等問題。目前還沒有基于MapReduce實現的面向數據密集型的可視化數據挖掘框架。用戶在使用Hadoop提供的任務提交機制進行數據挖掘操作時，往往需要根據需求去設計特定的Hadoop任務代碼。例如，對于一個SNS網站，若需要對20－30歲的用戶花費在社交網絡上的時間進行統計，開發人員需要針對特定的需求編寫MapReduce代碼 (包括條件過濾、數據統計和數據展示等幾個任務)，然后交給Hadoop去進行計算。該開發過程花費時間長，大部分時間都花費在重復開發上。

2 基于MapReduce的數據挖掘平臺

基于MapReduce實現的數據挖掘平臺的系統架構主要包括數據挖掘過程模型、代碼生成引擎、數據挖掘組件模型、MapReduce執行框架4個模塊，如圖2所示。

數據挖掘過程模型:用戶通過可視化的界面來定義數據挖掘過程，并配置相關的組件信息，該部分通過基于E-clipse 的 EMF［12］、GEF［13］和 GMF［14］實現圖形化的數據流程處理模型。

代碼生成引擎:為了避免讓用戶重復編寫通用代碼，系統具備生成符合Hadoop規范代碼的功能，用戶通過系統提供的參數配置界面配置需用戶定義的參數，這些參數最后將會反映到最終生成的代碼中。從用戶定義的數據挖掘過程模型轉換成可在Hadoop上運行的代碼有一個過程分析與代碼生成過程，該過程由代碼生成引擎完成，主要包括了過程模型分析、依賴關系分析、代碼模板解析等工作。

圖2 基于MapReduce數據挖掘處理平臺架構

數據挖掘組件模型:數據挖掘過程是通過將組件連接起來構成的，組件為了實現不同的功能，將封裝不同的數據操作邏輯。數據挖掘組件主要分成數據挖掘算法 (datamining algorithm)組件、Connector組件、用戶自定義組件(user defined component)三大類。

MapReduce執行框架:系統以Hadoop提供的MapReduce框架作為數據挖掘過程執行平臺，通過向MapReduce框架提交代碼的形式，運用MapReduce的并行計算能力實現挖掘過程的并行化。

運用基于模型驅動的開發方法，系統將軟件過程中使用的算法提取出來形成抽象模型。該方法可使用戶無需關心特定算法實現細節，系統以面向組件的方式簡化數據挖掘流程定義和算法組件定義。面向模型驅動的開發方法提高了系統的抽象層次，系統以一種可擴展的方式實現了數據挖掘平臺的低耦合、高內聚。

2.1 數據挖掘過程模型

用戶通過系統提供的模型組件來定義數據挖掘過程，該過程是一個符合過程邏輯模型的挖掘過程。在邏輯模型中，挖掘過程中的每一步數據操作被抽象成一個數據操作節點，該節點可稱為邏輯節點。系統通過解析邏輯節點的輸入輸出信息、用戶配置參數、節點對應的系統組件元信息來構建物理過程模型。邏輯過程模型與具體實現技術無關。物理模型則是從計算機系統的角度來定義，該模型與系統的實現平臺、編程模型和MapReduce任務調度策略相關。邏輯模型經過系統的后臺解析轉換成物理模型后才能在系統中執行。

過程模型使用EMF技術實現邏輯模型到物理模型的轉換。同時，通過GEF技術，用戶可通過模型的圖形化方式來實現邏輯模型的定義。物理模型與具體實現相關，物理模型包含了數據挖掘組件模型、Jet模板代碼生成技術以及與MapReduce相關的Mapper與Reducer定義、Job類型等相關內容。這些內容將分別在2.3節代碼生成引擎和2.4節數據挖掘組件介紹。

數據挖掘過程包括數據準備、數據預處理、數據挖掘和結果展示幾個步驟。如圖3所示，數據準備主要是指定義一個或多個數據來源，并在執行過程中完成數據抽取工作，用戶可通過定義不同的Connector組件來實現對不同數據源的數據抽取。數據預處理包括了數據清理 (去噪和去除不一致數據)、數據集成 (多數據源的組合)和數據選擇 (定義數據過濾規則)。用戶通過定義過濾、正則匹配等組件來實現該步驟。數據挖掘運用數據挖掘算法對經過預處理的數據執行挖掘算法。最后，結果展示步驟將執行結果以數據或圖表的形式展示給用戶。

圖3 數據挖掘過程

2.2 代碼生成引擎

代碼生成引擎主要完成從邏輯模型到可被MapReduce框架執行的可執行代碼的轉換過程，如圖4所示，大致可分成模型解析與代碼生成兩步。

第一步是模型解析，模型解析的主要工作是解析邏輯模型，系統根據數據挖掘過程模型定義的節點信息來劃分操作子流程，以Reduce操作節點為劃分點，以mapper+/reducer/mapper* (通過 ChainMapper［15］和 ChainRedu-cer［15］實現多個mapper和reducer在一個任務中執行)為子流程形式構造MapReduce任務集，并根據流程的連接順序來定義子流程之間的依賴關系。

圖4 代碼生成引擎工作原理

第二步是代碼生成，如圖5所示，根據第一步模型解析得到的子流程以及依賴關系，系統通過jet［16］模板解析的方式來生成MapReduce代碼。數據挖掘組件接收與其相連組件的輸入輸出類信息。根據輸入輸出類型信息和組件代碼模板，使用jet代碼模板生成相應的代碼，并將處理后的輸出按照輸出模式存放。組件模型包含組件ID、jet代碼模板、用戶定義參數類與組件元信息。組件ID用于標識組件的唯一性;jet代碼模板包括了Job配置模板、Mapper類模板、Reduce類模板以及Key/Value類模板等與MapReduce執行平臺相關的模板信息;用戶自定義參數類是用戶輸入的參數;組件描述元信息包含了組件描述、可視化圖標、模板路徑等元數據。數據挖掘過程模型最終會轉換成Java可執行代碼。這些類包括數據操作節點的Mapper類和Reducer類、數據連接輸入輸出類。最后，系統會生成一個以用戶定義的數據挖掘過程名稱為類名的主類來控制整個數據挖掘過程，并通過Hadoop Job Configuration模板提供的信息在runJob方法中按照模型解析獲得的任務依賴關系構建挖掘代碼。

圖5 Jet代碼模板解析器工作方式

圖6 描述了代碼生成引擎的部分類的類圖，引擎主要包括了用于對代碼生成進行控制的MapReduceTransfer類;用于對過程模型進行實例化的物理模型類PhysicalProess、PhysicaNode、PhysicalConnection、ChainHadoopJob;用于對代碼生成過程進行管理的DataMiningCodeManager類。

圖6 代碼生成引擎部分類

2.3 數據挖掘組件

數據挖掘組件是系統實現挖掘、數據連接等功能的數據操作單位，組件封裝了特定的數據操作邏輯。系統基于Eclipse來開發，可通過用戶自定義組件來擴展功能。數據挖掘組件在 OSGi［17］標準框架 Equinox中以組件的形式存在，系統提供標準擴展點，數據挖掘組件在plugin.xml中定義符合擴展點schema規則的組件元信息。

系統通過定義組件模型來規范化組件在系統中的生命周期。如圖7所示，組件模型定義了該組件的輸入流與輸出流，并通過Configure Interface接受用戶參數。

圖7 數據挖掘組件模型

組件模型定義了組件的類型、輸入接口、輸出接口、組件MapReduce類型等元信息。表1展示了數據挖掘組件模型Schema規范。

組件主要包括了ConfigInterface，Description，Icon，Id，MapredType，oType，TemplatePath以及 Input和 Output幾項屬性。表1描述了各項屬性的含義。

通過定義符合規則的schema，組件作為數據挖掘過程中標準組件的形式存在于系統中，并由系統對其進行加載、調用、銷毀等生命周期管理。上述schema的定義沒有規定組件內部的算法邏輯的實現，算法的實現主要通過每個組件各自的TemplatePath中的代碼模板來定義。代碼模板可根據組件需要實現的特定功能來實現算法，這種松耦合的架構為系統的可擴展性提供了保障。用戶可通過實現自定義的代碼模板來添加自定義組件。同時，代碼模板也可以方便得用于調用現成的算法庫，例如基于Hadoop實現的Mahout［18］算法庫。

表1 組件schema描述表

2.3.1 數據挖掘算法組件

數據挖掘算法組件封裝了挖掘算法邏輯。在數據挖掘算法組件中，數據以SequenceFile類型存儲。如圖8所示。SequenceFile存儲類型是Hadoop內置的一種數據存儲類型，用于存儲二進制形式的key/value。該存儲方式支持壓縮，可定制為基于Record或Block壓縮壓縮粒度。

基于hadoop的機器學習算法庫mahout實現了部分并行算法，用戶可通過參考系統定義的數據挖掘組件擴展點schema將mahout算法包裝成數據挖掘算法組件。

圖8 數據挖掘算法組件SequenceFile數據轉換

圖9 展示了基于MapReduce框架的K-means聚類算法，與傳統的K-means算法比，該算法實現了并行化。該算法分成三步:第一步實現文件的轉換，為后續步驟做數據準備;第二步對數據進行了分布式的Canopy算法，用于確定K-means算法初始的K個簇中心;第三步根據用戶配置的參數進行K-means迭代算法。該算法參考了mahout中的實現。

圖9 分布式K-means聚類算法

2.3.2 Connector組件

Connector組件用來實現系統與其它存儲系統的數據訪問功能。該類組件通過將定義系統與各類存儲系統的數據訪問接口與數據訪問格式來實現數據讀寫訪問。主要包括關系型數據庫Connector組件和key-value數據庫Connector組件兩大類。例如，MySQL Connector用于訪問存儲在MySQL數據庫中的數據。對于關系型數據庫的Connector組件，系統參考Cloudera Sqoop框架的實現。

3 實驗與分析

實驗與分析主要是通過數據挖掘平臺向量聚類挖掘過程的可視化開發過程來說明基于MapReduce數據挖掘平臺的易用性以及在面對多變需求時的敏捷性。

3.1 實驗設置

聚類算法能夠在沒有訓練樣本的條件下產生聚類模型。作為數據挖掘的一種重要手段，聚類在Web文檔的信息挖掘、信息分類中有著重要作用。對于需要聚類的文檔，傳統的做法是通過分詞與TF-IDF［19］統計等方式將文檔轉換成向量。然后通過Canopy、K-means等聚類算法對向量進行聚類分析。

用戶通過系統提供的可視化開發界面定義挖掘過程。如圖10所示，HDFS數據抽取組件定義輸入路徑;文件轉換組件將原始文件轉換成K-means聚類算法組件可接受的SequenceFile存儲類型;最后K－means聚類算法組件執行聚類分析。

圖10 K-means向量聚類流程

對于K-means聚類算法組件的需要配置的參數，用戶可通過系統提供的組件屬性配置界面進行參數配置。如圖11所示，通過配置界面，可定義用于K-means算法的特定的屬性值 T1，T2，向量距離測量方式，算法迭代次數等參數。

圖11 K-means聚類算法組件參數配置面板

在用戶配置完數據挖掘流程后，系統將自動生成代碼并上傳到Hadoop集群進行計算。圖12展示了8000個向量進行K-means聚類的結果。對于二維向量，系統提供聚類圖形化的選項 (如圖11所示)。通過系統的可視化工具，可將聚類結果以圖形化的方式展現給用戶。該聚類結果是在合理配置T1，T2，數值范圍、收斂指數等參數后的聚類結果。

圖12 K-means二維向量聚類

通過系統提供的挖掘過程定義界面與組件配置功能，用戶可在不關心K-means算法實現細節與算法并行化技術的基礎上，實現了對向量數據的聚類分析。同時，通過系統提供的可視化工具，實現對聚類結果的可視化展示。該過程簡化了在Hadoop平臺上的數據挖掘過程，提高了開發效率。

4 相關工作

Wegenner［20］等人針對數據挖掘算法的并行化問題，提出了針對MapReduce環境下通用數據挖掘工具。該研究表明MapReduce并行化計算大幅提高了挖掘算法對大數據集的挖掘效率。

Weka Parallel［21］將Weka擴展到多核環境下，通過實現Weka多核環境下并行化交叉驗證，縮短需進行交叉驗證的分類、聚類等挖掘算法的執行時間。

Lai［22］等人提出了在Hadoop上構建數據索引，該文運用決策樹算法建立索引的方式實現了比Hadoop提供的Map-File索引跟高效的訪問效率。同時，運用Java持久化API(JPA)與MySQL集群構建基于Hadoop的數據挖掘系統。

本文提出的基于MapReduce的數據挖掘平臺從開發效率和擴展性出發，運用過程建模與組件復用技術，實現挖掘過程可視化與挖掘算法組件化，提高挖掘效率。

5 結束語

本文提出了一種基于MapReduce編程模型的數據挖掘平臺設計與實現，為Hadoop在構建數據挖掘、數據可視化以及商業智能應用提供參考。該平臺以OSGi為基礎，以一種可擴展、低耦合的構建方式，用戶可方便地利用現有的算法對平臺進行功能擴充。面對互聯網和科學計算產生的海量數據，該平臺充分利用了Hadoop對海量數據的處理能力和OSGi框架對組件完善的管理能力，構建一種可適應數據挖掘領域需求變動快、數據來源多樣等特點的海量數據挖掘平臺。

［1］Jeffrey Cohen B D，Mark Dunlap.MAD skills:New analysis practices for big data ［J］.Proceedings of the VLDB Endowment，2009，2(2):1481-1492.

［2］Business objects explorer home page on the sap community network［EB/OL］.http://www.sdn.sap.com/irj/boc/explorer，2012.

［3］The spider is intended to be a complete object orientated environment for machine learning in Matlab［EB/OL］.http://people.kyb.tuebingen.mpg.de/spider/，2012.

［4］Microsoft SQL server analysis services(SSAS)［EB/OL］.http://msdn.microsoft.com/en-us/library/ms175609(v=sql.90).aspx，2011.

［5］Mark Hall E F，Geoffrey Holmes，Bernhard Pfahringer，et al.The WEKA data mining software:An update［J］.ACM SIGKDD Explorations Newsletter，2009，11(1):10-18.

［6］McKusick K，Quinlan S.GFS:Evolution on fast-forward ［J］.Communications of the ACM，2010，53(3):42-49.

［7］Dean J，Gheawat S.MapReduce:Simplified data processing onlarge clusters［J］.Communications of the ACM-50th Anniversary Issue:1958-2008，2008，51(1):107-113.

［8］Khetrapal A，Ganesh V HBase.Hypertable for large scale distributed storage systems［EB/OL］.http://www.ankurkhetrapal.com/downloads/HypertableHBaseEval2.pdf，2008.

［9］Chang F，Dean J，Ghemawat S，et al.Bigtable:A distributed storage system for structured data［J］.ACM Transactions on Computer Systems，2008，26(2):205-218.

［10］Thusoo A，Sarma JS，Jain N，et al.Hive:A warehousing solution over a map-reduce framework［J］.Proceedings of the VLDB Endowment，2009，2(2):1626-1629.

［11］Hadoop Sqoop.SQL-to-Hadoop database import and export tool［EB/OL］.https://github.com/cloudera/sqoop/wiki，2010

［12］Eclipse modeling framework project(EMF)［EB/OL］.http://www.eclipse.org/modeling/emf/，2012.

［13］Eclipse consortium，eclipse graphical editing framework(GEF)［EB/OL］.http://www.eclipse.org/gef/，2012.

［14］Eclipse consortium，eclipse graphical modeling framework［EB/OL］.http://www.eclipse.org/modeling/gmp/，2010.

［15］White T.Hadoop:The definitive guide［M］.2nd ed.O'Reilly Media/Yahoo Press，2010:165.

［16］Eclipse consortium，Java emitter templates(jet)，eclipse modeling framework-version 2.6.1，2010［EB/OL］.http://www.eclipse.org/emf，2010.

［17］OSGi Alliance.OSGi-the dynamic module system for Java［EB/OL］.http://www.osgi.org，2009.

［18］Sean Owen R A.Mahout in action［M］.Manning Publications，2010.

［19］Wu H C，Luk R W P，Wong K F，et al.Interpreting TF-IDF term weights as making relevance decisions［J］.ACM Transactions on Information Systems，2008，26(3):2-36.

［20］Wegener D，Mock M，Adranale D，et al.Toolkit-based high-performance data mining of large data on MapReduce clusters［C］//Washington:IEEE Computer Society，2009:296-301.

［21］Celis S，Musicant D R.Weka-parallel:Machine learning in parallel［EB/OL］.http://sourceforge.net/projects/weka-parallel/，2009.

［22］Lai Y，ZhongZhi S.An efficient data mining framework on hadoop using java persistence API［C］//Bradford:IEEE Computer Society，2010:203-209.