顏一鳴，郭 鑫

一種基于Hadoop的動態(tài)樹增量更新方法

顏一鳴，郭 鑫

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

為適應(yīng)真實(shí)環(huán)境中數(shù)據(jù)量大、流程復(fù)雜、計算密集的數(shù)據(jù)挖掘需求，提高傳統(tǒng)樹增量更新挖掘效率，改變已有算法的串行執(zhí)行方式，提出一種基于Hadoop的動態(tài)樹增量更新方法。介紹云計算、模型與執(zhí)行流程等基本概念，針對現(xiàn)有Hadoop平臺中任務(wù)調(diào)度的隨機(jī)分配策略，設(shè)計一種動態(tài)云平臺中的資源調(diào)度與分配算法，以期達(dá)到成本消耗的最小化，給出樹增量更新挖掘算法以及2個并行算法(DeleteFreqTree和FindNewTree)，完成樹數(shù)據(jù)的增量挖掘工作。實(shí)驗(yàn)結(jié)果表明，該并行算法有效可行，具有高效性與良好的擴(kuò)展率，能夠?qū)Ａ繕鋽?shù)據(jù)進(jìn)行更新挖掘。

數(shù)據(jù)挖掘；數(shù)據(jù)庫；云計算；并發(fā)控制；頻繁子樹；增量更新

1 概述

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

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

2 動態(tài)云平臺

以往的云計算平臺采用空閑的計算結(jié)點(diǎn)列表來保存當(dāng)前可用的計算資源，Master結(jié)點(diǎn)在對任務(wù)進(jìn)行分配時，會查閱該資源列表并將分割的子任務(wù)隨機(jī)分配給當(dāng)前閑置的計算結(jié)點(diǎn)，計算結(jié)點(diǎn)獲得數(shù)據(jù)并進(jìn)行相應(yīng)的計算工作，最后將計算結(jié)點(diǎn)反饋給主結(jié)點(diǎn)。

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

在設(shè)計動態(tài)云平臺時，將綜合考慮輸入大數(shù)據(jù)文件類型、集群中計算結(jié)點(diǎn)數(shù)量、分配的子任務(wù)數(shù)量、調(diào)度和使用文件的時間成本、回收文件成本等要素，下面將集中論述動態(tài)云資源分配模型相關(guān)概念。

其中：

目標(biāo)函數(shù)的約束條件為：

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

圖1 動態(tài)云模型框架

3 基于Hadoop的樹數(shù)據(jù)增量更新算法

傳統(tǒng)的樹數(shù)據(jù)挖掘算法與相關(guān)應(yīng)用已發(fā)展成熟，樹挖掘算法方面包括基于最右葉子結(jié)點(diǎn)擴(kuò)展的有序樹挖掘算法[8]與基于XML樹結(jié)構(gòu)特征的挖掘算法[9]等，樹應(yīng)用方面包括基于樹的圖像特征提取[10]與樹層次聚類[11]等。本文考慮當(dāng)樹數(shù)據(jù)庫與更新樹集較大時，改善增量挖掘效率，提出一種基于Hadoop平臺的動態(tài)樹增量更新方法。

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

4 實(shí)驗(yàn)設(shè)計與分析

表1 更新樹集的設(shè)置

設(shè)置不同的支持度閾值進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2 所示。

圖2 不同支持度下的運(yùn)行結(jié)果

圖3 加速比性能測試結(jié)果

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

第3組實(shí)驗(yàn)驗(yàn)證并行算法的擴(kuò)展率，隨機(jī)選取4個計算結(jié)點(diǎn)，采用5組數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集設(shè)置見表2。

表2 參數(shù)設(shè)置

圖4 擴(kuò)展率測試結(jié)果

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

5 結(jié)束語

本文根據(jù)云計算中并行分布式處理的特點(diǎn)，設(shè)計一種基于Hadoop的動態(tài)樹增量更新挖掘算法。實(shí)驗(yàn)結(jié)果表明，本文算法具有可行性、高效性和擴(kuò)展率，能夠滿足海量數(shù)據(jù)更新的需要。今后將繼續(xù)改進(jìn)該算法以解決實(shí)驗(yàn)過程中碰到的問題，同時還可以考慮將動態(tài)云計算平臺應(yīng)用到數(shù)據(jù)挖掘的其他方面，甚至擴(kuò)展到圖挖掘與社交網(wǎng)絡(luò)等領(lǐng)域。

[1] 劉 鵬. 云計算[M]. 北京: 電子工業(yè)出版社, 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] 卓月明. 基于聚類技術(shù)的XML文件代表性結(jié)構(gòu)獲取[J]. 吉首大學(xué)學(xué)報: 自然科學(xué)版, 2011, 32(6): 55-58.

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

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

[12] 陳光鵬, 楊育彬, 高 陽, 等. 一種基于MapReduce的頻繁閉項(xiàng)集挖掘算法[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

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

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

2013-02-28

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

10.3969/j.issn.1000-3428.2014.03.014