基于云計算的大數據挖掘平臺
2013-04-29 00:00:00何清莊福振
中興通訊技術 2013年4期
摘要：開發了一個基于云計算的并行分布式大數據挖掘平臺——PDMiner。PDMiner實現了各種并行數據挖掘算法，如數據預處理、關聯規則分析以及分類、聚類等算法。實驗結果表明，并行分布式數據挖掘平臺PDMiner中實現的并行算法，能夠處理大規模數據集，達到太字節級；具有很好的加速比性能；實現的并行算法可以在商用機器構建的并行平臺上穩定運行，整合了已有的計算資源，提高了計算資源的利用效率；可以有效地應用到實際海量數據挖掘中。在PDMiner中還開發了工作流子系統，提供友好統一的接口界面方便用戶定義數據挖掘任務。
關鍵詞： 云計算；分布式并行數據挖掘；海量數據
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
中圖分類號：TN915.03； TP393.03 文獻標志碼：A 文章編號：1009-6868 （2013） 04-0032-007
隨著物聯網、移動通信、移動互聯網和數據自動采集技術的飛速發展以及在各行各業的廣泛應用，人類社會所擁有的數據面臨著前所未有的爆炸式增長。美國互聯網數據中心指出，互聯網上的數據每年以50%的速度增長，每兩年翻一番，而目前世界上90%以上的數據是最近幾年才產生的，人類社會進入了“大數據”時代。因此，信息的獲取非常重要，一定程度上，信息的擁有量已經成為決定和制約社會發展的重要因素。
數據挖掘作為信息獲取的一門重要技術，得到了廣泛的研究。數據挖掘[1]從大量的數據中挖掘出有用的信息，提供給決策者做決策支持，有著廣闊的應用前景。由于要挖掘的信息源中的數據都是海量的，而且以指數級增長，傳統的集中式串行數據挖掘方法不再是一種適當的信息獲取方式。因此擴展數據挖掘算法處理大規模數據的能力，并提高運行速度和執行效率，已經成了一個不可忽視的問題。
為了解決海量數據的挖掘問題，一種簡單的方式就是把所有的數據劃分成若干份，也就是切分成若干個子任務，然后分布到各個計算資源上去進行計算，每個節點完成一個子任務，最后進行集成。分布式計算就是把一個計算問題分解成多個子問題并同時處理的計算模型。基于分布式計算模型，Luo等人[2-4]集成了很多數據挖掘算法到多主體系統。另外一種提高計算效率的方式是并行計算，并行計算也是把一個大的計算問題分割成小任務的形式。近年來，并行計算的體系結構和模型也引起了廣泛的興趣和研究[5-6]。
盡管分布式計算和并行計算有很相似的特點，但是它們之間各有側重，分布式計算強調在所有異構計算資源上同時求解問題，而并行計算則更加強調同一臺計算資源內部多線程并行。這兩種計算方式可以對應到算法之間的并行以及算法內部并行這兩種計算模式。文獻[2-4]提出基于主體技術的算法之間并行的計算模式，他們利用主體技術中主體本身的自主性、智能性等特點，實現不同算法主體之間的并行計算，以消息傳遞的方式實現同步，大大提高了算法的執行效率，減少了運行時間。第二種計算模式，是粒度比較小的并行方式，主要研究的是算法內部的并行。通過把算法分解，盡可能地找出算法中可并行的部分進行并行計算。這種計算模型的最終效率取決于算法本身的可并行程度，如果并行程度非常高，那么就可以大大提高算法的運行效率。由于在很多應用中，只需要執行一種應用（算法），所以研究算法內部的并行實現非常重要。文獻[7]實現了多種機器學習算法在多核計算機上的并行，本文主要針對第二種并行計算模式進行研究，而且可以在大規模計算機集群上運行。
近年來，云計算得到了學術界和業界的廣泛關注，它是一種基于互聯網的、大眾參與的計算模式，其計算資源，包括計算能力、存儲能力、交互能力，是動態、可伸縮、且被虛擬化的，以服務的方式提供給用戶。基于大規模數據處理平臺——Hadoop，我們研究開發了并行分布式數據挖掘平臺——PDMiner，其目的是設計實現并行數據挖掘算法處理大數據集，且提高執行效率。在PDMiner中包含4個子系統，工作流子系統、用戶接口子系統、數據預處理子系統和數據挖掘子系統。整個數據挖掘平臺提供了一個從海量數據中挖掘有用知識的完整解決方案，而且提供了可擴展的靈活接口。
1 大規模數據處理平臺
——Hadoop
Hadoop是一個軟件計算平臺，可以讓程序員很容易地開發和運行處理海量數據的應用程序。其核心部分包括HDFS[8]和基于MapReduce[9-10]機制的并行算法實現。
1.1 HDFS
Hadoop分布式文件系統HDFS是受Google文件系統啟發，建立在大型集群上可靠存儲大數據集的文件系統。它和現有的分布式文件系統有著很多的相似性，然而和其他的分布式文件系統的區別也是很明顯的。HDFS具有高容錯性，可以部署在低成本的硬件之上。此外，HDFS提供高吞吐量地對應用程序數據的訪問，適合大數據集的應用程序。
HDFS結構包含一個名字節點作為控制主節點，其他的服務器作為數據節點，存儲數據。具體地說，HDFS具有如下幾大特點：
（1）強容錯性
HDFS通過在名字節點和數據節點之間維持心跳檢測、檢測文件塊的完整性、保持集群負載均衡等手段使得系統具有高容錯性，集群里個別機器故障將不會影響到數據的使用。
（2）流式數據訪問與大數據集
運行在HDFS之上的應用程序必須流式地訪問它們的數據集。HDFS適合批量處理數據，典型的HDFS文件是吉字節到太字節的大小，典型的塊大小是64 MB。
（3）硬件和操作系統的異構性
HDFS的跨平臺能力毋庸置疑，得益于Java平臺已經封裝好的文件IO系統，HDFS可以在不同的操作系統和計算機上實現同樣的客戶端和服務端程序。
1.2 MapReduce
MapReduce是Google實驗室提出的一種簡化的分布式程序設計模型，用于處理和生成大量數據集。通過該模型，程序自動分布到一個由普通機器組成的超大機群上并發執行。
Map和Reduce是該模型中的兩大基本操作。其中，Map是把一組數據一對一的映射為另外的一組數據，Reduce是對數據進行規約，映射規則與規約規則可由用戶通過函數來分別指定。現實生活中很多任務的實現都是可以基于類似這樣的映射規約模式。
MapReduce通過把對數據集的大規模操作分發給網絡上的每個節點來實現可靠性，每個節點會周期性地把完成的工作和狀態信息返回給主節點。如果一個節點保持沉默超過一個預設的時間間隔，主節點就認為該節點失效了，并把分配給這個節點的數據發到別的節點，并且因此可以被其他節點所調度執行。
由于MapReduce運行系統已考慮到了輸入數據劃分、節點失效處理、節點之間所需通信等各個細節，使得程序員可以不需要有什么并發處理或者分布式系統的經驗，就可以處理超大規模的分布式系統資源。
2 并行分布式大數據挖掘
平臺體系架構
Hadoop提供了讓程序員易于開發和運行處理海量數據應用程序的平臺，其分布式文件系統HDFS是建立在大型集群上可靠存儲大數據集的文件系統，具有可靠性，強容錯性等特點；MapReduce提供了一種高效編寫并行程序的編程模式。基于此，我們開發了并行數據挖掘平臺——PDMiner，大規模數據存儲在HDFS上，且通過MapReduce實現各種并行數據預處理和數據挖掘算法。
PDMiner是一個集成各種并行算法的數據挖掘平臺，其中的并行計算模式不僅包括算法之間的并行，而且包括算法內部的并行。圖1給出了并行數據挖掘平臺PDMiner的總體系統架構，其中主要包括4個子系統：工作流子系統、用戶接口子系統、并行抽取轉換裝載（ETL）子系統以及并行數據挖掘子系統。工作流子系統提供了友好的界面方便用戶定義各種數據挖掘任務；用戶接口可以對算法的參數進行設置以及通過結果展示模塊分析挖掘結果并做出相應的決策；并行ETL算法子系統和并行數據挖掘算法子系統是PDMiner的核心部分，它們可以直接對存儲在HDFS系統上的數據進行處理，ETL算法處理后的結果也可以作為數據挖掘算法的輸入。
2.1 工作流子系統
工作流子系統提供了友好和統一的用戶接口（UI），使得用戶可以方便地建立數據挖掘任務。在創建挖掘任務過程中，可以選擇ETL數據預處理算法、分類算法、聚類算法、以及關聯規則算法等，右邊下拉框可以選擇服務單元的具體算法。工作流子系統通過圖形化UI界面為用戶提供服務，靈活建立符合業務應用工作流程的自定制挖掘任務。通過工作流界面，可以建立多個工作流任務，不僅每個挖掘任務內部并行，而且不同數據挖掘任務之間也并行。
2.2 用戶接口子系統
用戶接口子系統由2個模塊組成：用戶輸入模塊、結果展示模塊。用戶接口子系統負責與用戶交互，讀寫參數設置，接受用戶操作請求，根據接口實現結果展示。比如并行分類算法中并行樸素貝葉斯算法的參數設置界面如圖2所示，從圖中看到可以方便地設置算法的參數。這些參數包括訓練數據、測試數據、輸出結果以及模型文件的存儲路徑，而且還包括Map和Reduce任務個數的設置。結果展示部分實現了結果可視化理解，比如生成直方圖、餅圖等。
2.3 并行ETL算法子系統
數據預處理算法在數據挖掘中起著非常重要的作用，其輸出通常是數據挖掘算法的輸入。由于數據量的劇增，串行數據預處理過程需要消耗大量的時間來完成操作過程，因此為了提高預處理算法的執行效率，在并行ETL算法子系統中設計開發了19種預處理算法[11]，如圖3所示，包括并行采樣Sampling、并行數據預覽PDPreview、并行數據添加標簽PDAddLabel、并行離散化Discretize、并行增加樣本ID、并行屬性交換AttributeExchange、并行布爾型數據到系列數據的轉換BoolToSerialNum、并行數據歸一化Normalize、并行屬性約簡PCA、并行數據集成DataIntegration、并行統計Statistic、并行屬性約簡AttributeReduction、并行數據區間化Intervalize、并行冗余數據刪除RedundancyRemove、并行屬性添加AttributeAdd、并行屬性修改AttributeModify、并行數據缺失值替換ReplaceMissingValues、并行屬性刪除AttributeDel，以及并行屬性選擇AttributeSelection等。
通常ETL操作都具有很高的并行化程度，比如屬性的刪除，可以把數據劃分成很多塊，算法對每個數據塊的處理都是相對獨立的，因此并行ETL子系統中實現的并行ETL算法具有很好的加速比，大大提高了算法的運行速度和執行效率。
2.4 并行數據挖掘子系統
并行數據挖掘子系統是并行數據挖掘平臺PDMiner的核心部分，主要包括了三大類算法：并行關聯規則算法、并行分類算法[12]以及并行聚類算法等。
目前該并行數據挖掘子系統中已經開發了很多經典的數據挖掘算法，各類并行算法模塊包含的算法如圖4、圖5、圖6所示，其中并行關聯規則算法包括并行Apriori算法[13]，并行FP樹FPgrowth以及并行Awfits算法；并行分類算法包括并行超曲面分類算法HSC、并行k近鄰算法Knn、并行樸素貝葉斯算法NaiveBayes，并行決策樹算法C4.5、并行基于范例推理算法CBR、并行基于類中心算法CBC以及并行極限向量機ESVM等；并行聚類算法包括并行DBScan算法，并行Clara算法[14]、并行k均值算法Kmeans[15-16]以及并行EM算法等。
執行數據挖掘算法的一般流程如圖7所示。從算法流程來看，PDMiner是一個用戶友好的系統，用戶不用了解底層算法的設計和實現，就可以很容易使用系統。另外對于并行ETL子系統和并行數據挖掘子系統，還提供靈活的接口方便用戶集成新的算法。
2.5 基于MapReduce實現的算法實例
下面以決策樹為例描述基于MapReduce的并行算法的實現過程。決策樹算法是利用已標記訓練集建立決策樹模型，然后利用生成的決策樹對輸入測試數據進行分類。在以前的很多工作，主要是把數據劃分到多個計算節點上，然后各自建立決策樹模型，最后采用集成的方式得到最終模型[17]。采用MapReduce機制可以很好地解決決策樹算法內部的并行問題，提高算法的執行效率以及處理數據的規模。
圖8給出了并行決策樹算法的流程圖。在該并行算法中，實現了同一層內節點之間、節點內的并行計算，提高算法的執行效率。更重要的是，實現的并行決策樹算法以循環代替了遞歸，使得運行完程序所需要的最大作業（Job）個數可預測（最大數目為樣本集中條件屬性的數目 ），從而有利于控制程序的執行狀態。而在遞歸中，無法預測還有多少節點要運算，這樣就無法預測程序何時結束。由于層與層之間的運算是串行的，因此在基于MapReduce機制的并行決策樹實現中，上一層都會傳遞前綴信息給下一層節點，這些前綴包括從根節點到當前分支的分裂屬性信息等。
從流程圖可以看到每一層只需要一個Job，而不關心有多少個節點。程序需要運行的最大層數由條件屬性的個數決定，因此是可控制的。由于在并行的過程中主要是統計頻率，因此
當還有前綴的情況下，需要刪除訓練集中包含生成決策規則的樣本，該過程是一個讀寫的過程。對于包含新得到的決策規則的樣本，不再寫入訓練集，這樣在下一次迭代中就只計算那些沒有包含生成決策規則的樣本。
測試過程則非常簡單，每個Map利用已生成的決策樹模型對樣本進行預測，直接樣本的預測標記，不需要Reduce過程。
3 PDMiner的特點
3.1 可擴展性
PDMiner是一個可擴展的并行分布式數據挖掘平臺，我們為系統提供了靈活的接口來擴展集成新的并行算法。通過工作流子系統可以很方便地添加一個新的算法，比如在并行ETL子系統中添加新的算法PDAlgorithm1，則只要添加如下代碼：
通過加入最后一行代碼以后就可以在選項卡PD-Filters下面加入一項PDAlgorithm1。生成空類PDAlgorithm1的代碼如下：
其中在函數listOptions（ ）、getOptions（ ）、setOptions（ ）中編寫配置算法參數的代碼，在run（ ）函數中編寫調用Map函數和Reduce函數的代碼，用戶可以根據具體的算法編寫相應的Map函數和Reduce函數。并行數據挖掘算法的添加與ETL算法的添加類似。
3.2 支持多挖掘任務
在PDMiner中，不僅支持單個任務的創建和執行，而且支持同時創建和運行多個數據挖掘任務。這些任務可以是不同類別的挖掘任務，比如并行關聯規則任務、并行分類和聚類任務等，當配置完參數，這些任務可以同時在并行分布式系統PDMiner中執行。
支持多挖掘任務功能，具有非常重要的作用。比如要對所有的分類算法進行比較，從而選擇對已有數據集表現最佳的算法。一般的做法是串行測試完所有的算法，然后根據算法的效果進行選擇。而在PDMiner中可以并行地解決該問題，所有的算法都面向同一個數據集（讀取同一個頭文件信息），最后結果通過系統進行展示，從而選擇最合適的算法。從這個比較機制看到，所有的并行算法都是在并行系統中執行，因此可以處理大規模數據；另外，這些算法的執行過程是并行的，評價過程是自動的，因此可以減少算法執行時間和用戶的干預。
3.3 創建復雜挖掘過程
通過工作流子系統，系統還支持創建復雜挖掘任務，可以把并行數據預處理操作和并行數據挖掘算法串聯起來。系統提供并行屬性刪除操作、并行數據歸一化以及并行分類算法樸素貝葉斯的串聯。當配置完所有算法參數后，其執行過程如下：
·執行屬性刪除操作，對數據集進行屬性刪除操作，并且修改頭文件，生成新的頭文件信息。
·接收屬性刪除后更新后的頭文件，進行數據歸一化操作。
·進行分類算法任務。接收從第二步傳遞過來的頭文件信息，然后啟動分類算法任務。當任務執行完后，對分類結果進行展示。
4 實驗分析
并行分布式數據挖掘平臺PDMiner是一個高效的數據處理與分析工具，主要面向海量數據集的處理。在保證算法正確性的情況下，構造大數據集來考察算法的性能。系統中開發的并行算法已經在通信領域的實際數據挖掘中應用，以下給出了一些算法在構造的大數據集上的性能測試結果。鑒于隱私性等原因，這里沒有給出具體的并行算法名稱。
圖9、圖10、圖11、圖12、圖13給出了2個并行ETL算法和3個并行數據挖掘算法的時間性能。ETL測試的數據規模達到太字節級，而關聯規則、分類算法、聚類算法的數據規模分別是30 GB級別、400 GB級別、12 GB級別。我們分別記錄了32個節點，64個節點，128個節點的運行時間。若假設32節點執行的時間是標準的理想狀態下的時間，圖中紅線部分給出了理想情況下64節點和128節點的時間性能。從這些圖中，可以看到：
·通過增加節點，都可以提高算法的運算速度，較少執行時間。
·算法本身越簡單，即并行成分也大，效果越明顯，ETL算法顯然具有較高的加速比，執行效率也比較高；這說明算法的并行效率與自身可并行化的程度有關。
·如圖11所示，算法有時候可以得到線性加速比，說明該并行數據挖掘系統可以有效地利用計算資源。但我們也應該看到這種并行計算模型也不是萬能的，增加節點并不能總是能很好地提高效果（如圖13所示），有時甚至會由于并行通信而使效果變差。
5 結束語
針對大數據的處理和挖掘，本文開發設計了并行分布式數據挖掘平臺——PDMiner。基于Hadoop平臺和MapReduce的編程模式，開發實現了各種并行數據預處理操作以及并行數據挖掘算法，包括關聯規則算法，分類算法以及聚類算法等。另外，PDMiner還開放了靈活的接口，方便集成新的ETL算法和數據挖掘算法。實驗測試表明，開發的并行算法可以處理海量數據，且具有很好的加速比性能。
參考文獻
[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模型的并行計算平臺的設計與實現 [D]. 杭州： 浙江大學， 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] 宋曉云， 蘇宏升. 一種并行決策樹學習算法研究 [J]. 現代電子技術， 2007，30（2）： 141-144.
作者簡介
何清，中國科學院計算技術研究所研究員、博士生導師；主要研究領域為機器學習、數據挖掘、云計算、并行算法；已承擔完成基金項目2項；已發表學術論文近100篇（其中SCI收錄27篇，EI收錄66篇）。
莊福振，中國科學院計算技術研究所助理研究員；主要研究領域為機器學習、數據挖掘、遷移學習、并行算法；已承擔完成基金項目2項；已發表學術論文30余篇。
