基于MapReduce的數(shù)據(jù)挖掘平臺(tái)設(shè)計(jì)與實(shí)現(xiàn)

黃 斌，許舒人，蒲 衛(wèi)

(1.中國(guó)科學(xué)院軟件研究所軟件工程技術(shù)中心，北京100190;2.中國(guó)科學(xué)院研究生院，北京100190;3.解放軍衛(wèi)生信息中心，北京100842)

0 引言

2009年全球存儲(chǔ)的信息總量達(dá)到為8000億Gbt。IDC預(yù)測(cè)到2020年，全球?qū)?huì)存儲(chǔ)35Zbt(1Zbt=240Gbt)的信息量。社交網(wǎng)絡(luò)、電子商務(wù)、微博、音視頻分享等互聯(lián)網(wǎng)領(lǐng)域以及研究機(jī)構(gòu)科學(xué)實(shí)驗(yàn)源源不斷地產(chǎn)生大量的數(shù)據(jù)，單一數(shù)據(jù)庫(kù)存儲(chǔ)服務(wù)已經(jīng)無(wú)法滿足數(shù)據(jù)多元化與大規(guī)模數(shù)據(jù)挖掘的需求。

在商業(yè)領(lǐng)域，從商業(yè)決策、搜索引擎、社交網(wǎng)絡(luò)、推薦系統(tǒng)，到垃圾郵件檢測(cè)與廣告投放，對(duì)大規(guī)模數(shù)據(jù)進(jìn)行及時(shí)、有效地分析已成為這些商業(yè)應(yīng)用能在競(jìng)爭(zhēng)中脫穎而出的重要因素;在科學(xué)研究領(lǐng)域，天文學(xué)的圖片數(shù)據(jù)、生物學(xué)中的人類(lèi)基因組數(shù)據(jù)以及物理學(xué)中粒子加速器產(chǎn)生的實(shí)驗(yàn)數(shù)據(jù)的數(shù)據(jù)量都非常大，大數(shù)據(jù)量給科學(xué)分析帶來(lái)困難。

面對(duì)增長(zhǎng)迅速的數(shù)據(jù)量，如何從數(shù)據(jù)中發(fā)掘有用的信息成為當(dāng)前大多數(shù)數(shù)據(jù)挖掘系統(tǒng)面臨的問(wèn)題。對(duì)于此類(lèi)大數(shù)據(jù)集的數(shù)據(jù)分析與挖掘系統(tǒng)，Cohen等人在文獻(xiàn) ［1］中總結(jié)了這類(lèi)系統(tǒng)需要具備的特性:

(1)數(shù)據(jù)適應(yīng)性:系統(tǒng)可接受多種類(lèi)型的數(shù)據(jù)，避免系統(tǒng)對(duì)存儲(chǔ)的數(shù)據(jù)的類(lèi)型、結(jié)構(gòu)和數(shù)據(jù)完整性的強(qiáng)要求，從而避免通常的數(shù)據(jù)倉(cāng)庫(kù)對(duì)數(shù)據(jù)的強(qiáng)要求帶來(lái)的問(wèn)題;

(2)敏捷性:系統(tǒng)能夠適應(yīng)數(shù)據(jù)遞增且更新頻繁的應(yīng)用場(chǎng)景;

(3)分析深度:提供對(duì)數(shù)據(jù)分析多角度、多切面的分析，可便捷得加入復(fù)雜的概率統(tǒng)計(jì)和機(jī)器學(xué)習(xí)算法，適應(yīng)多類(lèi)型數(shù)據(jù)分析需求。

迫于數(shù)據(jù)量的急劇增長(zhǎng)，大量的數(shù)據(jù)存儲(chǔ)在數(shù)據(jù)庫(kù)與數(shù)據(jù)倉(cāng)庫(kù)中，關(guān)系型數(shù)據(jù)庫(kù)通常提供進(jìn)行數(shù)據(jù)分析與挖掘的數(shù)據(jù)分析工具，例如，SAP BusinessObjects Explorer［2］、Matlab Spider［3］、SQL Server Analysis Services［4］、weka［5］等都提供了此類(lèi)工具。然而，以關(guān)系型數(shù)據(jù)庫(kù)為基礎(chǔ)的數(shù)據(jù)挖掘系統(tǒng)存在以下幾個(gè)弊端:

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

(2)大多數(shù)數(shù)據(jù)庫(kù)分析系統(tǒng)需要將所有的數(shù)據(jù)放入內(nèi)存中，對(duì)于占多數(shù)的大數(shù)據(jù)集，一般只能通過(guò)抽樣的方式使得數(shù)據(jù)量縮小到內(nèi)存可接受的范圍內(nèi)，數(shù)據(jù)的抽樣通常會(huì)導(dǎo)致數(shù)據(jù)信息量丟失;

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

數(shù)據(jù)庫(kù)系統(tǒng)在數(shù)據(jù)處理效率和可處理的數(shù)據(jù)量無(wú)法滿足當(dāng)前數(shù)據(jù)的爆炸式增長(zhǎng)，效率與容量成為以數(shù)據(jù)庫(kù)為基礎(chǔ)的數(shù)據(jù)挖掘系統(tǒng)的最大瓶頸。

基于模型驅(qū)動(dòng)的開(kāi)發(fā)方法與組件開(kāi)發(fā)技術(shù)，本文提出一種可擴(kuò)展數(shù)據(jù)挖掘平臺(tái)，運(yùn)用MapReduce框架的擴(kuò)展性與并行能力，定義可重用的數(shù)據(jù)挖掘組件和Connector組件，提高了數(shù)據(jù)挖掘過(guò)程敏捷性。系統(tǒng)主要解決以下3個(gè)方面的問(wèn)題:

(1)定義數(shù)據(jù)挖掘過(guò)程中的挖掘組件模型，用戶可復(fù)用系統(tǒng)提供的數(shù)據(jù)挖掘組件來(lái)快速定義數(shù)據(jù)挖掘過(guò)程;

(2)通過(guò)GMF技術(shù)實(shí)現(xiàn)對(duì)數(shù)據(jù)挖掘過(guò)程的可視化定義，并通過(guò)代碼生成引擎實(shí)現(xiàn)挖掘過(guò)程到可執(zhí)行代碼的轉(zhuǎn)換;

(3)定義Connector可重用組件，實(shí)現(xiàn)對(duì)多種數(shù)據(jù)存儲(chǔ)系統(tǒng)的數(shù)據(jù)訪問(wèn)。

1 研究背景

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

圖1 Hadoop Software Stack

其中，Hbase［8］是一個(gè)以 BigTable［9］為原型的高性能、面向列、強(qiáng)一致性存儲(chǔ)系統(tǒng);Hive［10］是一個(gè)基于Hadoop實(shí)現(xiàn)的數(shù)據(jù)倉(cāng)庫(kù)工具;Pig使用戶可以通過(guò)Pig-latin語(yǔ)言定義運(yùn)行于Hadoop上的數(shù)據(jù)流程;Avro是一個(gè)面向Hadoop的數(shù)據(jù)序列化系統(tǒng);Sqoop［11］是一個(gè)用于關(guān)系型數(shù)據(jù)庫(kù)與HDFS之間數(shù)據(jù)遷移的工具;Zookeeper用于分布式應(yīng)用中的集群管理、狀態(tài)同步服務(wù)、同步鎖服務(wù);Chukwa是一個(gè)用于進(jìn)行集群運(yùn)行日志收集、分析和展示的管理工具。

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

2 基于MapReduce的數(shù)據(jù)挖掘平臺(tái)

基于MapReduce實(shí)現(xiàn)的數(shù)據(jù)挖掘平臺(tái)的系統(tǒng)架構(gòu)主要包括數(shù)據(jù)挖掘過(guò)程模型、代碼生成引擎、數(shù)據(jù)挖掘組件模型、MapReduce執(zhí)行框架4個(gè)模塊，如圖2所示。

數(shù)據(jù)挖掘過(guò)程模型:用戶通過(guò)可視化的界面來(lái)定義數(shù)據(jù)挖掘過(guò)程，并配置相關(guān)的組件信息，該部分通過(guò)基于E-clipse 的 EMF［12］、GEF［13］和 GMF［14］實(shí)現(xiàn)圖形化的數(shù)據(jù)流程處理模型。

代碼生成引擎:為了避免讓用戶重復(fù)編寫(xiě)通用代碼，系統(tǒng)具備生成符合Hadoop規(guī)范代碼的功能，用戶通過(guò)系統(tǒng)提供的參數(shù)配置界面配置需用戶定義的參數(shù)，這些參數(shù)最后將會(huì)反映到最終生成的代碼中。從用戶定義的數(shù)據(jù)挖掘過(guò)程模型轉(zhuǎn)換成可在Hadoop上運(yùn)行的代碼有一個(gè)過(guò)程分析與代碼生成過(guò)程，該過(guò)程由代碼生成引擎完成，主要包括了過(guò)程模型分析、依賴(lài)關(guān)系分析、代碼模板解析等工作。

圖2 基于MapReduce數(shù)據(jù)挖掘處理平臺(tái)架構(gòu)

數(shù)據(jù)挖掘組件模型:數(shù)據(jù)挖掘過(guò)程是通過(guò)將組件連接起來(lái)構(gòu)成的，組件為了實(shí)現(xiàn)不同的功能，將封裝不同的數(shù)據(jù)操作邏輯。數(shù)據(jù)挖掘組件主要分成數(shù)據(jù)挖掘算法 (datamining algorithm)組件、Connector組件、用戶自定義組件(user defined component)三大類(lèi)。

MapReduce執(zhí)行框架:系統(tǒng)以Hadoop提供的MapReduce框架作為數(shù)據(jù)挖掘過(guò)程執(zhí)行平臺(tái)，通過(guò)向MapReduce框架提交代碼的形式，運(yùn)用MapReduce的并行計(jì)算能力實(shí)現(xiàn)挖掘過(guò)程的并行化。

運(yùn)用基于模型驅(qū)動(dòng)的開(kāi)發(fā)方法，系統(tǒng)將軟件過(guò)程中使用的算法提取出來(lái)形成抽象模型。該方法可使用戶無(wú)需關(guān)心特定算法實(shí)現(xiàn)細(xì)節(jié)，系統(tǒng)以面向組件的方式簡(jiǎn)化數(shù)據(jù)挖掘流程定義和算法組件定義。面向模型驅(qū)動(dòng)的開(kāi)發(fā)方法提高了系統(tǒng)的抽象層次，系統(tǒng)以一種可擴(kuò)展的方式實(shí)現(xiàn)了數(shù)據(jù)挖掘平臺(tái)的低耦合、高內(nèi)聚。

2.1 數(shù)據(jù)挖掘過(guò)程模型

用戶通過(guò)系統(tǒng)提供的模型組件來(lái)定義數(shù)據(jù)挖掘過(guò)程，該過(guò)程是一個(gè)符合過(guò)程邏輯模型的挖掘過(guò)程。在邏輯模型中，挖掘過(guò)程中的每一步數(shù)據(jù)操作被抽象成一個(gè)數(shù)據(jù)操作節(jié)點(diǎn)，該節(jié)點(diǎn)可稱(chēng)為邏輯節(jié)點(diǎn)。系統(tǒng)通過(guò)解析邏輯節(jié)點(diǎn)的輸入輸出信息、用戶配置參數(shù)、節(jié)點(diǎn)對(duì)應(yīng)的系統(tǒng)組件元信息來(lái)構(gòu)建物理過(guò)程模型。邏輯過(guò)程模型與具體實(shí)現(xiàn)技術(shù)無(wú)關(guān)。物理模型則是從計(jì)算機(jī)系統(tǒng)的角度來(lái)定義，該模型與系統(tǒng)的實(shí)現(xiàn)平臺(tái)、編程模型和MapReduce任務(wù)調(diào)度策略相關(guān)。邏輯模型經(jīng)過(guò)系統(tǒng)的后臺(tái)解析轉(zhuǎn)換成物理模型后才能在系統(tǒng)中執(zhí)行。

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

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

圖3 數(shù)據(jù)挖掘過(guò)程

2.2 代碼生成引擎

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

第一步是模型解析，模型解析的主要工作是解析邏輯模型，系統(tǒng)根據(jù)數(shù)據(jù)挖掘過(guò)程模型定義的節(jié)點(diǎn)信息來(lái)劃分操作子流程，以Reduce操作節(jié)點(diǎn)為劃分點(diǎn)，以mapper+/reducer/mapper* (通過(guò) ChainMapper［15］和 ChainRedu-cer［15］實(shí)現(xiàn)多個(gè)mapper和reducer在一個(gè)任務(wù)中執(zhí)行)為子流程形式構(gòu)造MapReduce任務(wù)集，并根據(jù)流程的連接順序來(lái)定義子流程之間的依賴(lài)關(guān)系。

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

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

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

圖6 描述了代碼生成引擎的部分類(lèi)的類(lèi)圖，引擎主要包括了用于對(duì)代碼生成進(jìn)行控制的MapReduceTransfer類(lèi);用于對(duì)過(guò)程模型進(jìn)行實(shí)例化的物理模型類(lèi)PhysicalProess、PhysicaNode、PhysicalConnection、ChainHadoopJob;用于對(duì)代碼生成過(guò)程進(jìn)行管理的DataMiningCodeManager類(lèi)。

圖6 代碼生成引擎部分類(lèi)

2.3 數(shù)據(jù)挖掘組件

數(shù)據(jù)挖掘組件是系統(tǒng)實(shí)現(xiàn)挖掘、數(shù)據(jù)連接等功能的數(shù)據(jù)操作單位，組件封裝了特定的數(shù)據(jù)操作邏輯。系統(tǒng)基于Eclipse來(lái)開(kāi)發(fā)，可通過(guò)用戶自定義組件來(lái)擴(kuò)展功能。數(shù)據(jù)挖掘組件在 OSGi［17］標(biāo)準(zhǔn)框架 Equinox中以組件的形式存在，系統(tǒng)提供標(biāo)準(zhǔn)擴(kuò)展點(diǎn)，數(shù)據(jù)挖掘組件在plugin.xml中定義符合擴(kuò)展點(diǎn)schema規(guī)則的組件元信息。

系統(tǒng)通過(guò)定義組件模型來(lái)規(guī)范化組件在系統(tǒng)中的生命周期。如圖7所示，組件模型定義了該組件的輸入流與輸出流，并通過(guò)Configure Interface接受用戶參數(shù)。

圖7 數(shù)據(jù)挖掘組件模型

組件模型定義了組件的類(lèi)型、輸入接口、輸出接口、組件MapReduce類(lèi)型等元信息。表1展示了數(shù)據(jù)挖掘組件模型Schema規(guī)范。

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

通過(guò)定義符合規(guī)則的schema，組件作為數(shù)據(jù)挖掘過(guò)程中標(biāo)準(zhǔn)組件的形式存在于系統(tǒng)中，并由系統(tǒng)對(duì)其進(jìn)行加載、調(diào)用、銷(xiāo)毀等生命周期管理。上述schema的定義沒(méi)有規(guī)定組件內(nèi)部的算法邏輯的實(shí)現(xiàn)，算法的實(shí)現(xiàn)主要通過(guò)每個(gè)組件各自的TemplatePath中的代碼模板來(lái)定義。代碼模板可根據(jù)組件需要實(shí)現(xiàn)的特定功能來(lái)實(shí)現(xiàn)算法，這種松耦合的架構(gòu)為系統(tǒng)的可擴(kuò)展性提供了保障。用戶可通過(guò)實(shí)現(xiàn)自定義的代碼模板來(lái)添加自定義組件。同時(shí)，代碼模板也可以方便得用于調(diào)用現(xiàn)成的算法庫(kù)，例如基于Hadoop實(shí)現(xiàn)的Mahout［18］算法庫(kù)。

表1 組件schema描述表

2.3.1 數(shù)據(jù)挖掘算法組件

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

基于hadoop的機(jī)器學(xué)習(xí)算法庫(kù)mahout實(shí)現(xiàn)了部分并行算法，用戶可通過(guò)參考系統(tǒng)定義的數(shù)據(jù)挖掘組件擴(kuò)展點(diǎn)schema將mahout算法包裝成數(shù)據(jù)挖掘算法組件。

圖8 數(shù)據(jù)挖掘算法組件SequenceFile數(shù)據(jù)轉(zhuǎn)換

圖9 展示了基于MapReduce框架的K-means聚類(lèi)算法，與傳統(tǒng)的K-means算法比，該算法實(shí)現(xiàn)了并行化。該算法分成三步:第一步實(shí)現(xiàn)文件的轉(zhuǎn)換，為后續(xù)步驟做數(shù)據(jù)準(zhǔn)備;第二步對(duì)數(shù)據(jù)進(jìn)行了分布式的Canopy算法，用于確定K-means算法初始的K個(gè)簇中心;第三步根據(jù)用戶配置的參數(shù)進(jìn)行K-means迭代算法。該算法參考了mahout中的實(shí)現(xiàn)。

圖9 分布式K-means聚類(lèi)算法

2.3.2 Connector組件

Connector組件用來(lái)實(shí)現(xiàn)系統(tǒng)與其它存儲(chǔ)系統(tǒng)的數(shù)據(jù)訪問(wèn)功能。該類(lèi)組件通過(guò)將定義系統(tǒng)與各類(lèi)存儲(chǔ)系統(tǒng)的數(shù)據(jù)訪問(wèn)接口與數(shù)據(jù)訪問(wèn)格式來(lái)實(shí)現(xiàn)數(shù)據(jù)讀寫(xiě)訪問(wèn)。主要包括關(guān)系型數(shù)據(jù)庫(kù)Connector組件和key-value數(shù)據(jù)庫(kù)Connector組件兩大類(lèi)。例如，MySQL Connector用于訪問(wèn)存儲(chǔ)在MySQL數(shù)據(jù)庫(kù)中的數(shù)據(jù)。對(duì)于關(guān)系型數(shù)據(jù)庫(kù)的Connector組件，系統(tǒng)參考Cloudera Sqoop框架的實(shí)現(xiàn)。

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

實(shí)驗(yàn)與分析主要是通過(guò)數(shù)據(jù)挖掘平臺(tái)向量聚類(lèi)挖掘過(guò)程的可視化開(kāi)發(fā)過(guò)程來(lái)說(shuō)明基于MapReduce數(shù)據(jù)挖掘平臺(tái)的易用性以及在面對(duì)多變需求時(shí)的敏捷性。

3.1 實(shí)驗(yàn)設(shè)置

聚類(lèi)算法能夠在沒(méi)有訓(xùn)練樣本的條件下產(chǎn)生聚類(lèi)模型。作為數(shù)據(jù)挖掘的一種重要手段，聚類(lèi)在Web文檔的信息挖掘、信息分類(lèi)中有著重要作用。對(duì)于需要聚類(lèi)的文檔，傳統(tǒng)的做法是通過(guò)分詞與TF-IDF［19］統(tǒng)計(jì)等方式將文檔轉(zhuǎn)換成向量。然后通過(guò)Canopy、K-means等聚類(lèi)算法對(duì)向量進(jìn)行聚類(lèi)分析。

用戶通過(guò)系統(tǒng)提供的可視化開(kāi)發(fā)界面定義挖掘過(guò)程。如圖10所示，HDFS數(shù)據(jù)抽取組件定義輸入路徑;文件轉(zhuǎn)換組件將原始文件轉(zhuǎn)換成K-means聚類(lèi)算法組件可接受的SequenceFile存儲(chǔ)類(lèi)型;最后K－means聚類(lèi)算法組件執(zhí)行聚類(lèi)分析。

圖10 K-means向量聚類(lèi)流程

對(duì)于K-means聚類(lèi)算法組件的需要配置的參數(shù)，用戶可通過(guò)系統(tǒng)提供的組件屬性配置界面進(jìn)行參數(shù)配置。如圖11所示，通過(guò)配置界面，可定義用于K-means算法的特定的屬性值 T1，T2，向量距離測(cè)量方式，算法迭代次數(shù)等參數(shù)。

圖11 K-means聚類(lèi)算法組件參數(shù)配置面板

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

圖12 K-means二維向量聚類(lèi)

通過(guò)系統(tǒng)提供的挖掘過(guò)程定義界面與組件配置功能，用戶可在不關(guān)心K-means算法實(shí)現(xiàn)細(xì)節(jié)與算法并行化技術(shù)的基礎(chǔ)上，實(shí)現(xiàn)了對(duì)向量數(shù)據(jù)的聚類(lèi)分析。同時(shí)，通過(guò)系統(tǒng)提供的可視化工具，實(shí)現(xiàn)對(duì)聚類(lèi)結(jié)果的可視化展示。該過(guò)程簡(jiǎn)化了在Hadoop平臺(tái)上的數(shù)據(jù)挖掘過(guò)程，提高了開(kāi)發(fā)效率。

4 相關(guān)工作

Wegenner［20］等人針對(duì)數(shù)據(jù)挖掘算法的并行化問(wèn)題，提出了針對(duì)MapReduce環(huán)境下通用數(shù)據(jù)挖掘工具。該研究表明MapReduce并行化計(jì)算大幅提高了挖掘算法對(duì)大數(shù)據(jù)集的挖掘效率。

Weka Parallel［21］將Weka擴(kuò)展到多核環(huán)境下，通過(guò)實(shí)現(xiàn)Weka多核環(huán)境下并行化交叉驗(yàn)證，縮短需進(jìn)行交叉驗(yàn)證的分類(lèi)、聚類(lèi)等挖掘算法的執(zhí)行時(shí)間。

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

本文提出的基于MapReduce的數(shù)據(jù)挖掘平臺(tái)從開(kāi)發(fā)效率和擴(kuò)展性出發(fā)，運(yùn)用過(guò)程建模與組件復(fù)用技術(shù)，實(shí)現(xiàn)挖掘過(guò)程可視化與挖掘算法組件化，提高挖掘效率。

5 結(jié)束語(yǔ)

本文提出了一種基于MapReduce編程模型的數(shù)據(jù)挖掘平臺(tái)設(shè)計(jì)與實(shí)現(xiàn)，為Hadoop在構(gòu)建數(shù)據(jù)挖掘、數(shù)據(jù)可視化以及商業(yè)智能應(yīng)用提供參考。該平臺(tái)以O(shè)SGi為基礎(chǔ)，以一種可擴(kuò)展、低耦合的構(gòu)建方式，用戶可方便地利用現(xiàn)有的算法對(duì)平臺(tái)進(jìn)行功能擴(kuò)充。面對(duì)互聯(lián)網(wǎng)和科學(xué)計(jì)算產(chǎn)生的海量數(shù)據(jù)，該平臺(tái)充分利用了Hadoop對(duì)海量數(shù)據(jù)的處理能力和OSGi框架對(duì)組件完善的管理能力，構(gòu)建一種可適應(yīng)數(shù)據(jù)挖掘領(lǐng)域需求變動(dòng)快、數(shù)據(jù)來(lái)源多樣等特點(diǎn)的海量數(shù)據(jù)挖掘平臺(tái)。

［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.