基于云計(jì)算的大數(shù)據(jù)挖掘平臺(tái)
2013-04-29 00:00:00何清莊福振
中興通訊技術(shù) 2013年4期
摘要：開發(fā)了一個(gè)基于云計(jì)算的并行分布式大數(shù)據(jù)挖掘平臺(tái)——PDMiner。PDMiner實(shí)現(xiàn)了各種并行數(shù)據(jù)挖掘算法，如數(shù)據(jù)預(yù)處理、關(guān)聯(lián)規(guī)則分析以及分類、聚類等算法。實(shí)驗(yàn)結(jié)果表明，并行分布式數(shù)據(jù)挖掘平臺(tái)PDMiner中實(shí)現(xiàn)的并行算法，能夠處理大規(guī)模數(shù)據(jù)集，達(dá)到太字節(jié)級(jí)；具有很好的加速比性能；實(shí)現(xiàn)的并行算法可以在商用機(jī)器構(gòu)建的并行平臺(tái)上穩(wěn)定運(yùn)行，整合了已有的計(jì)算資源，提高了計(jì)算資源的利用效率；可以有效地應(yīng)用到實(shí)際海量數(shù)據(jù)挖掘中。在PDMiner中還開發(fā)了工作流子系統(tǒng)，提供友好統(tǒng)一的接口界面方便用戶定義數(shù)據(jù)挖掘任務(wù)。
關(guān)鍵詞： 云計(jì)算；分布式并行數(shù)據(jù)挖掘；海量數(shù)據(jù)
Abstract： In this paper， we develop a parallel and distributed data mining toolkit platform called PDMiner. This platform is based on cloud computing. PDMiner is used to preprocess data， analyze association rules， and parallel classification and clustering. Our experimental results show that the parallel algorithms in PDMiner can tackle data sets up to one terabyte. They are very efficient because they have good speedup， and they are easily extended so that they can be executed in a cluster of commodity machines. This means that full use is made of computing resources. The algorithms are also efficient for practical data mining. We also develop a knowledge flow subsystem that helps the user define a data mining task in PDMiner.
Key words： cloud computing； parallel and distributed data mining； big data
中圖分類號(hào)：TN915.03； TP393.03 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1009-6868 （2013） 04-0032-007
隨著物聯(lián)網(wǎng)、移動(dòng)通信、移動(dòng)互聯(lián)網(wǎng)和數(shù)據(jù)自動(dòng)采集技術(shù)的飛速發(fā)展以及在各行各業(yè)的廣泛應(yīng)用，人類社會(huì)所擁有的數(shù)據(jù)面臨著前所未有的爆炸式增長。美國互聯(lián)網(wǎng)數(shù)據(jù)中心指出，互聯(lián)網(wǎng)上的數(shù)據(jù)每年以50%的速度增長，每兩年翻一番，而目前世界上90%以上的數(shù)據(jù)是最近幾年才產(chǎn)生的，人類社會(huì)進(jìn)入了“大數(shù)據(jù)”時(shí)代。因此，信息的獲取非常重要，一定程度上，信息的擁有量已經(jīng)成為決定和制約社會(huì)發(fā)展的重要因素。
數(shù)據(jù)挖掘作為信息獲取的一門重要技術(shù)，得到了廣泛的研究。數(shù)據(jù)挖掘[1]從大量的數(shù)據(jù)中挖掘出有用的信息，提供給決策者做決策支持，有著廣闊的應(yīng)用前景。由于要挖掘的信息源中的數(shù)據(jù)都是海量的，而且以指數(shù)級(jí)增長，傳統(tǒng)的集中式串行數(shù)據(jù)挖掘方法不再是一種適當(dāng)?shù)男畔@取方式。因此擴(kuò)展數(shù)據(jù)挖掘算法處理大規(guī)模數(shù)據(jù)的能力，并提高運(yùn)行速度和執(zhí)行效率，已經(jīng)成了一個(gè)不可忽視的問題。
為了解決海量數(shù)據(jù)的挖掘問題，一種簡單的方式就是把所有的數(shù)據(jù)劃分成若干份，也就是切分成若干個(gè)子任務(wù)，然后分布到各個(gè)計(jì)算資源上去進(jìn)行計(jì)算，每個(gè)節(jié)點(diǎn)完成一個(gè)子任務(wù)，最后進(jìn)行集成。分布式計(jì)算就是把一個(gè)計(jì)算問題分解成多個(gè)子問題并同時(shí)處理的計(jì)算模型?；诜植际接?jì)算模型，Luo等人[2-4]集成了很多數(shù)據(jù)挖掘算法到多主體系統(tǒng)。另外一種提高計(jì)算效率的方式是并行計(jì)算，并行計(jì)算也是把一個(gè)大的計(jì)算問題分割成小任務(wù)的形式。近年來，并行計(jì)算的體系結(jié)構(gòu)和模型也引起了廣泛的興趣和研究[5-6]。
盡管分布式計(jì)算和并行計(jì)算有很相似的特點(diǎn)，但是它們之間各有側(cè)重，分布式計(jì)算強(qiáng)調(diào)在所有異構(gòu)計(jì)算資源上同時(shí)求解問題，而并行計(jì)算則更加強(qiáng)調(diào)同一臺(tái)計(jì)算資源內(nèi)部多線程并行。這兩種計(jì)算方式可以對應(yīng)到算法之間的并行以及算法內(nèi)部并行這兩種計(jì)算模式。文獻(xiàn)[2-4]提出基于主體技術(shù)的算法之間并行的計(jì)算模式，他們利用主體技術(shù)中主體本身的自主性、智能性等特點(diǎn)，實(shí)現(xiàn)不同算法主體之間的并行計(jì)算，以消息傳遞的方式實(shí)現(xiàn)同步，大大提高了算法的執(zhí)行效率，減少了運(yùn)行時(shí)間。第二種計(jì)算模式，是粒度比較小的并行方式，主要研究的是算法內(nèi)部的并行。通過把算法分解，盡可能地找出算法中可并行的部分進(jìn)行并行計(jì)算。這種計(jì)算模型的最終效率取決于算法本身的可并行程度，如果并行程度非常高，那么就可以大大提高算法的運(yùn)行效率。由于在很多應(yīng)用中，只需要執(zhí)行一種應(yīng)用（算法），所以研究算法內(nèi)部的并行實(shí)現(xiàn)非常重要。文獻(xiàn)[7]實(shí)現(xiàn)了多種機(jī)器學(xué)習(xí)算法在多核計(jì)算機(jī)上的并行，本文主要針對第二種并行計(jì)算模式進(jìn)行研究，而且可以在大規(guī)模計(jì)算機(jī)集群上運(yùn)行。
近年來，云計(jì)算得到了學(xué)術(shù)界和業(yè)界的廣泛關(guān)注，它是一種基于互聯(lián)網(wǎng)的、大眾參與的計(jì)算模式，其計(jì)算資源，包括計(jì)算能力、存儲(chǔ)能力、交互能力，是動(dòng)態(tài)、可伸縮、且被虛擬化的，以服務(wù)的方式提供給用戶。基于大規(guī)模數(shù)據(jù)處理平臺(tái)——Hadoop，我們研究開發(fā)了并行分布式數(shù)據(jù)挖掘平臺(tái)——PDMiner，其目的是設(shè)計(jì)實(shí)現(xiàn)并行數(shù)據(jù)挖掘算法處理大數(shù)據(jù)集，且提高執(zhí)行效率。在PDMiner中包含4個(gè)子系統(tǒng)，工作流子系統(tǒng)、用戶接口子系統(tǒng)、數(shù)據(jù)預(yù)處理子系統(tǒng)和數(shù)據(jù)挖掘子系統(tǒng)。整個(gè)數(shù)據(jù)挖掘平臺(tái)提供了一個(gè)從海量數(shù)據(jù)中挖掘有用知識(shí)的完整解決方案，而且提供了可擴(kuò)展的靈活接口。
1 大規(guī)模數(shù)據(jù)處理平臺(tái)
——Hadoop
Hadoop是一個(gè)軟件計(jì)算平臺(tái)，可以讓程序員很容易地開發(fā)和運(yùn)行處理海量數(shù)據(jù)的應(yīng)用程序。其核心部分包括HDFS[8]和基于MapReduce[9-10]機(jī)制的并行算法實(shí)現(xiàn)。
1.1 HDFS
Hadoop分布式文件系統(tǒng)HDFS是受Google文件系統(tǒng)啟發(fā)，建立在大型集群上可靠存儲(chǔ)大數(shù)據(jù)集的文件系統(tǒng)。它和現(xiàn)有的分布式文件系統(tǒng)有著很多的相似性，然而和其他的分布式文件系統(tǒng)的區(qū)別也是很明顯的。HDFS具有高容錯(cuò)性，可以部署在低成本的硬件之上。此外，HDFS提供高吞吐量地對應(yīng)用程序數(shù)據(jù)的訪問，適合大數(shù)據(jù)集的應(yīng)用程序。
HDFS結(jié)構(gòu)包含一個(gè)名字節(jié)點(diǎn)作為控制主節(jié)點(diǎn)，其他的服務(wù)器作為數(shù)據(jù)節(jié)點(diǎn)，存儲(chǔ)數(shù)據(jù)。具體地說，HDFS具有如下幾大特點(diǎn)：
（1）強(qiáng)容錯(cuò)性
HDFS通過在名字節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)之間維持心跳檢測、檢測文件塊的完整性、保持集群負(fù)載均衡等手段使得系統(tǒng)具有高容錯(cuò)性，集群里個(gè)別機(jī)器故障將不會(huì)影響到數(shù)據(jù)的使用。
（2）流式數(shù)據(jù)訪問與大數(shù)據(jù)集
運(yùn)行在HDFS之上的應(yīng)用程序必須流式地訪問它們的數(shù)據(jù)集。HDFS適合批量處理數(shù)據(jù)，典型的HDFS文件是吉字節(jié)到太字節(jié)的大小，典型的塊大小是64 MB。
（3）硬件和操作系統(tǒng)的異構(gòu)性
HDFS的跨平臺(tái)能力毋庸置疑，得益于Java平臺(tái)已經(jīng)封裝好的文件IO系統(tǒng)，HDFS可以在不同的操作系統(tǒng)和計(jì)算機(jī)上實(shí)現(xiàn)同樣的客戶端和服務(wù)端程序。
1.2 MapReduce
MapReduce是Google實(shí)驗(yàn)室提出的一種簡化的分布式程序設(shè)計(jì)模型，用于處理和生成大量數(shù)據(jù)集。通過該模型，程序自動(dòng)分布到一個(gè)由普通機(jī)器組成的超大機(jī)群上并發(fā)執(zhí)行。
Map和Reduce是該模型中的兩大基本操作。其中，Map是把一組數(shù)據(jù)一對一的映射為另外的一組數(shù)據(jù)，Reduce是對數(shù)據(jù)進(jìn)行規(guī)約，映射規(guī)則與規(guī)約規(guī)則可由用戶通過函數(shù)來分別指定?，F(xiàn)實(shí)生活中很多任務(wù)的實(shí)現(xiàn)都是可以基于類似這樣的映射規(guī)約模式。
MapReduce通過把對數(shù)據(jù)集的大規(guī)模操作分發(fā)給網(wǎng)絡(luò)上的每個(gè)節(jié)點(diǎn)來實(shí)現(xiàn)可靠性，每個(gè)節(jié)點(diǎn)會(huì)周期性地把完成的工作和狀態(tài)信息返回給主節(jié)點(diǎn)。如果一個(gè)節(jié)點(diǎn)保持沉默超過一個(gè)預(yù)設(shè)的時(shí)間間隔，主節(jié)點(diǎn)就認(rèn)為該節(jié)點(diǎn)失效了，并把分配給這個(gè)節(jié)點(diǎn)的數(shù)據(jù)發(fā)到別的節(jié)點(diǎn)，并且因此可以被其他節(jié)點(diǎn)所調(diào)度執(zhí)行。
由于MapReduce運(yùn)行系統(tǒng)已考慮到了輸入數(shù)據(jù)劃分、節(jié)點(diǎn)失效處理、節(jié)點(diǎn)之間所需通信等各個(gè)細(xì)節(jié)，使得程序員可以不需要有什么并發(fā)處理或者分布式系統(tǒng)的經(jīng)驗(yàn)，就可以處理超大規(guī)模的分布式系統(tǒng)資源。
2 并行分布式大數(shù)據(jù)挖掘
平臺(tái)體系架構(gòu)
Hadoop提供了讓程序員易于開發(fā)和運(yùn)行處理海量數(shù)據(jù)應(yīng)用程序的平臺(tái)，其分布式文件系統(tǒng)HDFS是建立在大型集群上可靠存儲(chǔ)大數(shù)據(jù)集的文件系統(tǒng)，具有可靠性，強(qiáng)容錯(cuò)性等特點(diǎn)；MapReduce提供了一種高效編寫并行程序的編程模式?；诖?，我們開發(fā)了并行數(shù)據(jù)挖掘平臺(tái)——PDMiner，大規(guī)模數(shù)據(jù)存儲(chǔ)在HDFS上，且通過MapReduce實(shí)現(xiàn)各種并行數(shù)據(jù)預(yù)處理和數(shù)據(jù)挖掘算法。
PDMiner是一個(gè)集成各種并行算法的數(shù)據(jù)挖掘平臺(tái)，其中的并行計(jì)算模式不僅包括算法之間的并行，而且包括算法內(nèi)部的并行。圖1給出了并行數(shù)據(jù)挖掘平臺(tái)PDMiner的總體系統(tǒng)架構(gòu)，其中主要包括4個(gè)子系統(tǒng)：工作流子系統(tǒng)、用戶接口子系統(tǒng)、并行抽取轉(zhuǎn)換裝載（ETL）子系統(tǒng)以及并行數(shù)據(jù)挖掘子系統(tǒng)。工作流子系統(tǒng)提供了友好的界面方便用戶定義各種數(shù)據(jù)挖掘任務(wù)；用戶接口可以對算法的參數(shù)進(jìn)行設(shè)置以及通過結(jié)果展示模塊分析挖掘結(jié)果并做出相應(yīng)的決策；并行ETL算法子系統(tǒng)和并行數(shù)據(jù)挖掘算法子系統(tǒng)是PDMiner的核心部分，它們可以直接對存儲(chǔ)在HDFS系統(tǒng)上的數(shù)據(jù)進(jìn)行處理，ETL算法處理后的結(jié)果也可以作為數(shù)據(jù)挖掘算法的輸入。
2.1 工作流子系統(tǒng)
工作流子系統(tǒng)提供了友好和統(tǒng)一的用戶接口（UI），使得用戶可以方便地建立數(shù)據(jù)挖掘任務(wù)。在創(chuàng)建挖掘任務(wù)過程中，可以選擇ETL數(shù)據(jù)預(yù)處理算法、分類算法、聚類算法、以及關(guān)聯(lián)規(guī)則算法等，右邊下拉框可以選擇服務(wù)單元的具體算法。工作流子系統(tǒng)通過圖形化UI界面為用戶提供服務(wù)，靈活建立符合業(yè)務(wù)應(yīng)用工作流程的自定制挖掘任務(wù)。通過工作流界面，可以建立多個(gè)工作流任務(wù)，不僅每個(gè)挖掘任務(wù)內(nèi)部并行，而且不同數(shù)據(jù)挖掘任務(wù)之間也并行。
2.2 用戶接口子系統(tǒng)
用戶接口子系統(tǒng)由2個(gè)模塊組成：用戶輸入模塊、結(jié)果展示模塊。用戶接口子系統(tǒng)負(fù)責(zé)與用戶交互，讀寫參數(shù)設(shè)置，接受用戶操作請求，根據(jù)接口實(shí)現(xiàn)結(jié)果展示。比如并行分類算法中并行樸素貝葉斯算法的參數(shù)設(shè)置界面如圖2所示，從圖中看到可以方便地設(shè)置算法的參數(shù)。這些參數(shù)包括訓(xùn)練數(shù)據(jù)、測試數(shù)據(jù)、輸出結(jié)果以及模型文件的存儲(chǔ)路徑，而且還包括Map和Reduce任務(wù)個(gè)數(shù)的設(shè)置。結(jié)果展示部分實(shí)現(xiàn)了結(jié)果可視化理解，比如生成直方圖、餅圖等。
2.3 并行ETL算法子系統(tǒng)
數(shù)據(jù)預(yù)處理算法在數(shù)據(jù)挖掘中起著非常重要的作用，其輸出通常是數(shù)據(jù)挖掘算法的輸入。由于數(shù)據(jù)量的劇增，串行數(shù)據(jù)預(yù)處理過程需要消耗大量的時(shí)間來完成操作過程，因此為了提高預(yù)處理算法的執(zhí)行效率，在并行ETL算法子系統(tǒng)中設(shè)計(jì)開發(fā)了19種預(yù)處理算法[11]，如圖3所示，包括并行采樣Sampling、并行數(shù)據(jù)預(yù)覽PDPreview、并行數(shù)據(jù)添加標(biāo)簽PDAddLabel、并行離散化Discretize、并行增加樣本ID、并行屬性交換AttributeExchange、并行布爾型數(shù)據(jù)到系列數(shù)據(jù)的轉(zhuǎn)換BoolToSerialNum、并行數(shù)據(jù)歸一化Normalize、并行屬性約簡PCA、并行數(shù)據(jù)集成DataIntegration、并行統(tǒng)計(jì)Statistic、并行屬性約簡AttributeReduction、并行數(shù)據(jù)區(qū)間化Intervalize、并行冗余數(shù)據(jù)刪除RedundancyRemove、并行屬性添加AttributeAdd、并行屬性修改AttributeModify、并行數(shù)據(jù)缺失值替換ReplaceMissingValues、并行屬性刪除AttributeDel，以及并行屬性選擇AttributeSelection等。
通常ETL操作都具有很高的并行化程度，比如屬性的刪除，可以把數(shù)據(jù)劃分成很多塊，算法對每個(gè)數(shù)據(jù)塊的處理都是相對獨(dú)立的，因此并行ETL子系統(tǒng)中實(shí)現(xiàn)的并行ETL算法具有很好的加速比，大大提高了算法的運(yùn)行速度和執(zhí)行效率。
2.4 并行數(shù)據(jù)挖掘子系統(tǒng)
并行數(shù)據(jù)挖掘子系統(tǒng)是并行數(shù)據(jù)挖掘平臺(tái)PDMiner的核心部分，主要包括了三大類算法：并行關(guān)聯(lián)規(guī)則算法、并行分類算法[12]以及并行聚類算法等。
目前該并行數(shù)據(jù)挖掘子系統(tǒng)中已經(jīng)開發(fā)了很多經(jīng)典的數(shù)據(jù)挖掘算法，各類并行算法模塊包含的算法如圖4、圖5、圖6所示，其中并行關(guān)聯(lián)規(guī)則算法包括并行Apriori算法[13]，并行FP樹FPgrowth以及并行Awfits算法；并行分類算法包括并行超曲面分類算法HSC、并行k近鄰算法Knn、并行樸素貝葉斯算法NaiveBayes，并行決策樹算法C4.5、并行基于范例推理算法CBR、并行基于類中心算法CBC以及并行極限向量機(jī)ESVM等；并行聚類算法包括并行DBScan算法，并行Clara算法[14]、并行k均值算法Kmeans[15-16]以及并行EM算法等。
執(zhí)行數(shù)據(jù)挖掘算法的一般流程如圖7所示。從算法流程來看，PDMiner是一個(gè)用戶友好的系統(tǒng)，用戶不用了解底層算法的設(shè)計(jì)和實(shí)現(xiàn)，就可以很容易使用系統(tǒng)。另外對于并行ETL子系統(tǒng)和并行數(shù)據(jù)挖掘子系統(tǒng)，還提供靈活的接口方便用戶集成新的算法。
2.5 基于MapReduce實(shí)現(xiàn)的算法實(shí)例
下面以決策樹為例描述基于MapReduce的并行算法的實(shí)現(xiàn)過程。決策樹算法是利用已標(biāo)記訓(xùn)練集建立決策樹模型，然后利用生成的決策樹對輸入測試數(shù)據(jù)進(jìn)行分類。在以前的很多工作，主要是把數(shù)據(jù)劃分到多個(gè)計(jì)算節(jié)點(diǎn)上，然后各自建立決策樹模型，最后采用集成的方式得到最終模型[17]。采用MapReduce機(jī)制可以很好地解決決策樹算法內(nèi)部的并行問題，提高算法的執(zhí)行效率以及處理數(shù)據(jù)的規(guī)模。
圖8給出了并行決策樹算法的流程圖。在該并行算法中，實(shí)現(xiàn)了同一層內(nèi)節(jié)點(diǎn)之間、節(jié)點(diǎn)內(nèi)的并行計(jì)算，提高算法的執(zhí)行效率。更重要的是，實(shí)現(xiàn)的并行決策樹算法以循環(huán)代替了遞歸，使得運(yùn)行完程序所需要的最大作業(yè)（Job）個(gè)數(shù)可預(yù)測（最大數(shù)目為樣本集中條件屬性的數(shù)目 ），從而有利于控制程序的執(zhí)行狀態(tài)。而在遞歸中，無法預(yù)測還有多少節(jié)點(diǎn)要運(yùn)算，這樣就無法預(yù)測程序何時(shí)結(jié)束。由于層與層之間的運(yùn)算是串行的，因此在基于MapReduce機(jī)制的并行決策樹實(shí)現(xiàn)中，上一層都會(huì)傳遞前綴信息給下一層節(jié)點(diǎn)，這些前綴包括從根節(jié)點(diǎn)到當(dāng)前分支的分裂屬性信息等。
從流程圖可以看到每一層只需要一個(gè)Job，而不關(guān)心有多少個(gè)節(jié)點(diǎn)。程序需要運(yùn)行的最大層數(shù)由條件屬性的個(gè)數(shù)決定，因此是可控制的。由于在并行的過程中主要是統(tǒng)計(jì)頻率，因此
當(dāng)還有前綴的情況下，需要?jiǎng)h除訓(xùn)練集中包含生成決策規(guī)則的樣本，該過程是一個(gè)讀寫的過程。對于包含新得到的決策規(guī)則的樣本，不再寫入訓(xùn)練集，這樣在下一次迭代中就只計(jì)算那些沒有包含生成決策規(guī)則的樣本。
測試過程則非常簡單，每個(gè)Map利用已生成的決策樹模型對樣本進(jìn)行預(yù)測，直接樣本的預(yù)測標(biāo)記，不需要Reduce過程。
3 PDMiner的特點(diǎn)
3.1 可擴(kuò)展性
PDMiner是一個(gè)可擴(kuò)展的并行分布式數(shù)據(jù)挖掘平臺(tái)，我們?yōu)橄到y(tǒng)提供了靈活的接口來擴(kuò)展集成新的并行算法。通過工作流子系統(tǒng)可以很方便地添加一個(gè)新的算法，比如在并行ETL子系統(tǒng)中添加新的算法PDAlgorithm1，則只要添加如下代碼：
通過加入最后一行代碼以后就可以在選項(xiàng)卡PD-Filters下面加入一項(xiàng)PDAlgorithm1。生成空類PDAlgorithm1的代碼如下：
其中在函數(shù)listOptions（ ）、getOptions（ ）、setOptions（ ）中編寫配置算法參數(shù)的代碼，在run（ ）函數(shù)中編寫調(diào)用Map函數(shù)和Reduce函數(shù)的代碼，用戶可以根據(jù)具體的算法編寫相應(yīng)的Map函數(shù)和Reduce函數(shù)。并行數(shù)據(jù)挖掘算法的添加與ETL算法的添加類似。
3.2 支持多挖掘任務(wù)
在PDMiner中，不僅支持單個(gè)任務(wù)的創(chuàng)建和執(zhí)行，而且支持同時(shí)創(chuàng)建和運(yùn)行多個(gè)數(shù)據(jù)挖掘任務(wù)。這些任務(wù)可以是不同類別的挖掘任務(wù)，比如并行關(guān)聯(lián)規(guī)則任務(wù)、并行分類和聚類任務(wù)等，當(dāng)配置完參數(shù)，這些任務(wù)可以同時(shí)在并行分布式系統(tǒng)PDMiner中執(zhí)行。
支持多挖掘任務(wù)功能，具有非常重要的作用。比如要對所有的分類算法進(jìn)行比較，從而選擇對已有數(shù)據(jù)集表現(xiàn)最佳的算法。一般的做法是串行測試完所有的算法，然后根據(jù)算法的效果進(jìn)行選擇。而在PDMiner中可以并行地解決該問題，所有的算法都面向同一個(gè)數(shù)據(jù)集（讀取同一個(gè)頭文件信息），最后結(jié)果通過系統(tǒng)進(jìn)行展示，從而選擇最合適的算法。從這個(gè)比較機(jī)制看到，所有的并行算法都是在并行系統(tǒng)中執(zhí)行，因此可以處理大規(guī)模數(shù)據(jù)；另外，這些算法的執(zhí)行過程是并行的，評(píng)價(jià)過程是自動(dòng)的，因此可以減少算法執(zhí)行時(shí)間和用戶的干預(yù)。
3.3 創(chuàng)建復(fù)雜挖掘過程
通過工作流子系統(tǒng)，系統(tǒng)還支持創(chuàng)建復(fù)雜挖掘任務(wù)，可以把并行數(shù)據(jù)預(yù)處理操作和并行數(shù)據(jù)挖掘算法串聯(lián)起來。系統(tǒng)提供并行屬性刪除操作、并行數(shù)據(jù)歸一化以及并行分類算法樸素貝葉斯的串聯(lián)。當(dāng)配置完所有算法參數(shù)后，其執(zhí)行過程如下：
·執(zhí)行屬性刪除操作，對數(shù)據(jù)集進(jìn)行屬性刪除操作，并且修改頭文件，生成新的頭文件信息。
·接收屬性刪除后更新后的頭文件，進(jìn)行數(shù)據(jù)歸一化操作。
·進(jìn)行分類算法任務(wù)。接收從第二步傳遞過來的頭文件信息，然后啟動(dòng)分類算法任務(wù)。當(dāng)任務(wù)執(zhí)行完后，對分類結(jié)果進(jìn)行展示。
4 實(shí)驗(yàn)分析
并行分布式數(shù)據(jù)挖掘平臺(tái)PDMiner是一個(gè)高效的數(shù)據(jù)處理與分析工具，主要面向海量數(shù)據(jù)集的處理。在保證算法正確性的情況下，構(gòu)造大數(shù)據(jù)集來考察算法的性能。系統(tǒng)中開發(fā)的并行算法已經(jīng)在通信領(lǐng)域的實(shí)際數(shù)據(jù)挖掘中應(yīng)用，以下給出了一些算法在構(gòu)造的大數(shù)據(jù)集上的性能測試結(jié)果。鑒于隱私性等原因，這里沒有給出具體的并行算法名稱。
圖9、圖10、圖11、圖12、圖13給出了2個(gè)并行ETL算法和3個(gè)并行數(shù)據(jù)挖掘算法的時(shí)間性能。ETL測試的數(shù)據(jù)規(guī)模達(dá)到太字節(jié)級(jí)，而關(guān)聯(lián)規(guī)則、分類算法、聚類算法的數(shù)據(jù)規(guī)模分別是30 GB級(jí)別、400 GB級(jí)別、12 GB級(jí)別。我們分別記錄了32個(gè)節(jié)點(diǎn)，64個(gè)節(jié)點(diǎn)，128個(gè)節(jié)點(diǎn)的運(yùn)行時(shí)間。若假設(shè)32節(jié)點(diǎn)執(zhí)行的時(shí)間是標(biāo)準(zhǔn)的理想狀態(tài)下的時(shí)間，圖中紅線部分給出了理想情況下64節(jié)點(diǎn)和128節(jié)點(diǎn)的時(shí)間性能。從這些圖中，可以看到：
·通過增加節(jié)點(diǎn)，都可以提高算法的運(yùn)算速度，較少執(zhí)行時(shí)間。
·算法本身越簡單，即并行成分也大，效果越明顯，ETL算法顯然具有較高的加速比，執(zhí)行效率也比較高；這說明算法的并行效率與自身可并行化的程度有關(guān)。
·如圖11所示，算法有時(shí)候可以得到線性加速比，說明該并行數(shù)據(jù)挖掘系統(tǒng)可以有效地利用計(jì)算資源。但我們也應(yīng)該看到這種并行計(jì)算模型也不是萬能的，增加節(jié)點(diǎn)并不能總是能很好地提高效果（如圖13所示），有時(shí)甚至?xí)捎诓⑿型ㄐ哦剐Ч儾睢?/p>
5 結(jié)束語
針對大數(shù)據(jù)的處理和挖掘，本文開發(fā)設(shè)計(jì)了并行分布式數(shù)據(jù)挖掘平臺(tái)——PDMiner?；贖adoop平臺(tái)和MapReduce的編程模式，開發(fā)實(shí)現(xiàn)了各種并行數(shù)據(jù)預(yù)處理操作以及并行數(shù)據(jù)挖掘算法，包括關(guān)聯(lián)規(guī)則算法，分類算法以及聚類算法等。另外，PDMiner還開放了靈活的接口，方便集成新的ETL算法和數(shù)據(jù)挖掘算法。實(shí)驗(yàn)測試表明，開發(fā)的并行算法可以處理海量數(shù)據(jù)，且具有很好的加速比性能。
參考文獻(xiàn)
[1] HAN J W， KAMBER M， PEI J. Data mining： Concepts and techniques [M]. 3rd ed. San Francisco， CA，USA： Morgan Kaufmann Publishers， 2011.
[2] LUO P， LU K， SHI Z Z， et al. Distributed data mining in grid computing environments [J]. Future Generation Computer Systems， 2007，23（1）：84-91.
[3] LUO P， LU K， HUANG R， et al. A heterogeneous computing system for data mining workflows in multi-agent environments [J]. Expert Systems， 2006，23（5）：258-272.
[4] ZHUANG F Z， HE Q， SHI Z Z. Multi-agent based on automatic evaluation system for classification algorithm [C]//Proceedings of the International Conference on Information and Automation（ICIA’08），Jun 20-23，2008， Zhangjiajie， China. Piscataway， NJ， USA：IEEE， 2008： 264-269.
[5] HAMEENANTTILA T， GUAN X L， CAROTHERS J D， et al. The flexible hypercube： A new fault-tolerant architecture for parallel computing [J]. Journal of Parallel and Distributed Computing， 1996，37（2）：213-220.
[6] GOUDREAU M W， LANG K， RAO S B， et al. Portable and efficient parallel computing using the BSP model [J]. IEEE Transactions on Computers， 1999，48（7）：670-689 .
[7] CHU C T， KIM S K， LIN Y A， et al. Map-reduce for machine learning on multicore [C]//Proceedings of the 21st Annual Conference on Neural Information Processing Systems （NIPS’07）， Dec 3-6，2007， Vancouver， Canada. Berlin， Germany： Springer-Verlag， 2007：281-288.
[8] BORTHAKUR D. The hadoop distributed file system： Architecture and design [R]. The Apache Software Foundation， 2007.
[9] DEAN J， GHEMAWAT S. MapReduce： Simplified data processing on large clusters [J]. Communications of the ACM， 2008，51（1）：107-113.
[10] 萬至臻. 基于MapReduce模型的并行計(jì)算平臺(tái)的設(shè)計(jì)與實(shí)現(xiàn) [D]. 杭州： 浙江大學(xué)， 2008.
[11] HE Q， TAN Q， MA X D， et al. The High-activity parallel implementation of data preprocessing based on MapReduce [C]//Proceedings of the 5th International Conference on Rough Set and Knowledge Technology（RSKT’10）， Oct 15-17， 2010，Beijing， China. LNCS 6401. Berlin， Germany： Springer-Verlag， 2010：646-654.
[12] HE Q， ZHUANG F Z， LI J C， et al. Parallel implementation of classification algorithms based on MapReduce [C]//Proceedings of the 5th International Conference on Rough Set and Knowledge Technology（RSKT’10）， Oct 15-17， 2010， Beijing， China. LNCS 6401. Berlin， Germany： Springer-Verlag， 2010：655-662.
[13] LI N， ZENG L， HE Q， et al. Parallel implementation of apriori algorithm based on MapReduce [C]//Proceedings of the 13th ACIS International Conference on Software Engineering， Artificial Intelligence， Networking and Parallel Distributed Computing （SNPD’12）， Aug 8-12，2012， Kyoto， Japan. Piscataway， NJ，USA： IEEE， 2012：236-241.
[14] ZHAO W Z， MA H F， HE Q. Parallel K-means clustering based on MapReduce [C]//Proceedings of the1st International Conference on Cloud Computing（CloudCom’09）， Dec 1-4， 2009， Beijing， China. LNCS 5931. Berlin， Germany： Springer-Verlag， 2009：674-679.
[15] HE Q， WANG Q， ZHUANG F Z， et al. Parallel CLARANS clustering based on MapReduce [C]//Proceedings of the 3rd International Conference on Machine Learning and Computing （ICMLC’11）：Vol 6， Feb 26-28，2011，Singapore. Piscataway， NJ，USA： IEEE，2011： 236-240.
[16] HALL M， FRANK E， HOLMES G， et al. The WEKA data mining software： An update [J]. ACM SIGKDD Explorations Newsletter，2009，11（1）：10-18.
[17] 宋曉云， 蘇宏升. 一種并行決策樹學(xué)習(xí)算法研究 [J]. 現(xiàn)代電子技術(shù)， 2007，30（2）： 141-144.
作者簡介
何清，中國科學(xué)院計(jì)算技術(shù)研究所研究員、博士生導(dǎo)師；主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、云計(jì)算、并行算法；已承擔(dān)完成基金項(xiàng)目2項(xiàng)；已發(fā)表學(xué)術(shù)論文近100篇（其中SCI收錄27篇，EI收錄66篇）。
莊福振，中國科學(xué)院計(jì)算技術(shù)研究所助理研究員；主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、遷移學(xué)習(xí)、并行算法；已承擔(dān)完成基金項(xiàng)目2項(xiàng)；已發(fā)表學(xué)術(shù)論文30余篇。
