一種基于Hadoop的動態樹增量更新方法

顏一鳴，郭 鑫

一種基于Hadoop的動態樹增量更新方法

顏一鳴，郭 鑫

(吉首大學軟件服務外包學院，湖南 張家界 427000)

為適應真實環境中數據量大、流程復雜、計算密集的數據挖掘需求，提高傳統樹增量更新挖掘效率，改變已有算法的串行執行方式，提出一種基于Hadoop的動態樹增量更新方法。介紹云計算、模型與執行流程等基本概念，針對現有Hadoop平臺中任務調度的隨機分配策略，設計一種動態云平臺中的資源調度與分配算法，以期達到成本消耗的最小化，給出樹增量更新挖掘算法以及2個并行算法(DeleteFreqTree和FindNewTree)，完成樹數據的增量挖掘工作。實驗結果表明，該并行算法有效可行，具有高效性與良好的擴展率，能夠對海量樹數據進行更新挖掘。

數據挖掘；數據庫；云計算；并發控制；頻繁子樹；增量更新

1 概述

樹結構是現實世界中最基本的數據類型之一，很多應用環境都需要樹結構，如數據庫設計、XML數據分析、生物工程等。雖然針對樹數據的處理技術與應用已發展很長時間，理論日趨完善，但隨著互聯網應用的普及與迅猛發展，許多企業機構都累積了大量不同結構形式的數據，其中大部分的數據都是以樹結構表現出來的，如何對這些海量樹數據進行高效管理，以及如何快速地更新與維護樹數據庫已經成為一個新的挑戰。顯然，傳統的樹數據挖掘算法與增量更新算法已無法滿足數據日益增長的需求，可以將云計算[1]技術應用到相關算法中，以提高更新挖掘海量數據的效率。

云計算是先進計算機技術的產物，利用云計算來解決大規模樹數據挖掘是一個具有發展潛力的方向。在云計算平臺下進行海量數據處理主要包括MapReduce[2]和整體同步并行計算模型(BSP)[3]2種模型。谷歌的Pregel[4]與雅虎的Giraph[5]就是基于BSP模型的，但存在著消息通信效率瓶頸。MapReduce模型主要包括Hadoop與HOP[6]系統，本文利用MapReduce模型來處理海量樹數據，主要包括輸入輸出文件、任務的分配、信息的改善、執行Reduce函數等過程。由于基于Hadoop平臺的MapReduce算法工作流程簡單可行，因此本文基于Hadoop平臺設計一種動態樹增量更新算法，以改善海量樹數據的更新挖掘效率。

2 動態云平臺

以往的云計算平臺采用空閑的計算結點列表來保存當前可用的計算資源，Master結點在對任務進行分配時，會查閱該資源列表并將分割的子任務隨機分配給當前閑置的計算結點，計算結點獲得數據并進行相應的計算工作，最后將計算結點反饋給主結點。

在這一過程中，計算結點會定時給主結點發送信息以證明是否處于空閑狀態，主結點收集空閑結點并進行隨機調度。隨機調度機制雖然可行，也很容易實現，但各個計算資源的實際情況不一，隨機分配并不能保證計算資源的最佳利用，如云平臺的整體反應時間最優、消耗成本最小、完成時間最少與計算性能最佳等。如何對計算資源進行合理調度才能達到最優化狀態是本文需要考慮的問題，但要想達到所有情況最優很難實現，因此，對現有Hadoop平臺的資源調度策略[7]進行改進，提出一種新的基于Hadoop的動態資源分配方法，該方法可以實現計算結點最小化資源消耗。

在設計動態云平臺時，將綜合考慮輸入大數據文件類型、集群中計算結點數量、分配的子任務數量、調度和使用文件的時間成本、回收文件成本等要素，下面將集中論述動態云資源分配模型相關概念。

其中：

目標函數的約束條件為：

基于CDA-HT算法的動態云模型框架如圖1所示。

圖1 動態云模型框架

3 基于Hadoop的樹數據增量更新算法

傳統的樹數據挖掘算法與相關應用已發展成熟，樹挖掘算法方面包括基于最右葉子結點擴展的有序樹挖掘算法[8]與基于XML樹結構特征的挖掘算法[9]等，樹應用方面包括基于樹的圖像特征提取[10]與樹層次聚類[11]等。本文考慮當樹數據庫與更新樹集較大時，改善增量挖掘效率，提出一種基于Hadoop平臺的動態樹增量更新方法。

Map操作：根據上述策略生成新的子樹集，分別用四元組表示，以子樹結點數為鍵，四元組為值形成鍵值對，作為中間數據傳遞給Reduce操作。

4 實驗設計與分析

表1 更新樹集的設置

設置不同的支持度閾值進行實驗，實驗結果如圖2 所示。

圖2 不同支持度下的運行結果

圖3 加速比性能測試結果

從圖3中可以看出，并行算法加速性能良好，在不同的支持度下加速性能不一樣，但總體趨勢一致，隨著計算結點的增多，加速效果明顯，但增長放緩，對于單一結點，其數據處理效率還是具有很大優勢的。

第3組實驗驗證并行算法的擴展率，隨機選取4個計算結點，采用5組數據集進行實驗，數據集設置見表2。

表2 參數設置

圖4 擴展率測試結果

從圖4中可以看出，當計算結點數增多時，算法的擴展率(百分比)是逐漸減小的，原因在于結點數越多，算法所需的通信代價也就越高，算法的執行時間也會隨之增加。通過大量實驗表明，本文提出的基于Hadoop的動態樹增量更新算法具有可行性、高效性和擴展率。

5 結束語

本文根據云計算中并行分布式處理的特點，設計一種基于Hadoop的動態樹增量更新挖掘算法。實驗結果表明，本文算法具有可行性、高效性和擴展率，能夠滿足海量數據更新的需要。今后將繼續改進該算法以解決實驗過程中碰到的問題，同時還可以考慮將動態云計算平臺應用到數據挖掘的其他方面，甚至擴展到圖挖掘與社交網絡等領域。

[1] 劉 鵬. 云計算[M]. 北京: 電子工業出版社, 2010.

[2] Jeffrey D, Sanjay G. MapReduce: Simplified Data Processing on Large Clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[3] Valiant L G. A Bridging Model for Parallel Computation[J]. Communications of the ACM, 1990, 33(3): 103-111.

[4] Grzegorz M, Austern M H, Bik A J C, et al. Pregel: A System for Large-scale Graph Processing[C]//Proc. of SIGMOD’10. Indianapolis, Indiana: [s. n.], 2010: 135-145.

[5] Ching A. Giraph: Large-scale Graph Processing Infrastruction on Hadoop[C]//Proc. of the Hadoop Summit. Santa Clara, USA: [s. n.], 2011.

[6] Condie T, Conway N, Alvaro P, et al. MapReduce Online[C]// Proc. of NSDI’10. San Jose, USA: [s. n.], 2010: 33-48.

[7] Lublin U, Feitelson D G. The Workload on Parallel Super- computers: Modeling the Characteristics of Rigid Jobs[J]. Journal of Parallel and Distributed Computing, 2003, 63(20): 1105-1122.

[8] Zaki M J. Efficiently Mining Frequent Trees in a Forest: Algorithms and Applications[J]. IEEE Transactions on Knowledge and Data Engineering: Special Issue on Mining Biological Data, 2005, 17(8): 1021-1035.

[9] 卓月明. 基于聚類技術的XML文件代表性結構獲取[J]. 吉首大學學報: 自然科學版, 2011, 32(6): 55-58.

[10] 王志瑞, 閆彩良. 圖像特征提取方法的綜述[J]. 吉首大學學報: 自然科學版, 2011, 32(5): 43-47.

[11] 劉文軍, 游興中. 一種改進的凝聚層次聚類法[J]. 吉首大學學報: 自然科學版, 2011, 32(4): 11-14.

[12] 陳光鵬, 楊育彬, 高 陽, 等. 一種基于MapReduce的頻繁閉項集挖掘算法[J]. 模式識別與人工智能, 2012, 25(2): 220-224.

編輯 任吉慧

A Dynamic Tree Incremental Updating Method Based on Hadoop

YAN Yi-ming, GUO Xin

(School of Software and Service Outsourcing, Jishou University, Zhangjiajie 427000, China)

In order to deal with problems in true environment caused by data mining tasks with larger amount of data, complex processing and intensive computing, improve the traditional tree incremental updating mining efficiency, and change the existing algorithm of serial implementation methods, this paper proposes a dynamic tree incremental updating method on the basis of Hadoop. It introduces concepts concerning cloud computing, the cloud model, operating process and so on. Then, according to the Hadoop platform task scheduling random distribution strategy, a new dynamic cloud platform resource allocation algorithm is put forward in order to minimize the consumption cost. It designs a new tree incremental updating algorithm on the basis of cloud platform, and two parallel algorithms (DeleteFreqTree, FindNewTree) are proposed. Large number of experiments show that the paralleled algorithm is feasible, highly efficient, expandable, and the algorithm can mine mass tree data effectively.

data mining; database; cloud computing; concurrency control; frequent subtree; incremental updating

1000-3428(2014)03-0067-04

A

TP311.12

湖南省工業支撐計劃基金資助項目(2012GK2006)；湖南省教育廳科學研究基金資助項目(12C0291)。

顏一鳴(1976－)，男，講師，主研方向：數據挖掘；郭 鑫，講師、碩士。

2013-02-28

2013-04-02 E-mail：yymboy@126.com

10.3969/j.issn.1000-3428.2014.03.014