基于大數(shù)據(jù)的數(shù)據(jù)挖掘引擎研究

王小燕，張麗敏

（1.陜西廣播電視大學(xué) 陜西 西安 710119；2.西安外事學(xué)院 信息與網(wǎng)絡(luò)學(xué)院，陜西 西安 710077）

基于大數(shù)據(jù)的數(shù)據(jù)挖掘引擎研究

王小燕1，張麗敏2

（1.陜西廣播電視大學(xué) 陜西 西安 710119；2.西安外事學(xué)院 信息與網(wǎng)絡(luò)學(xué)院，陜西 西安 710077）

為了解決數(shù)據(jù)挖掘在大數(shù)據(jù)中存在的問題，文中對大數(shù)據(jù)下的數(shù)據(jù)挖掘引擎進(jìn)行了研究，以Spark作為核心引擎，并在Spark的內(nèi)存計算算子的基礎(chǔ)上，實(shí)現(xiàn)了多個傳統(tǒng)數(shù)據(jù)挖掘算法的并行計算，使得傳統(tǒng)的數(shù)據(jù)挖掘算法能在集群環(huán)境中并行運(yùn)行，從而在大數(shù)據(jù)中得到較好的應(yīng)用。然后通過系統(tǒng)分層方法，將數(shù)據(jù)挖掘系統(tǒng)進(jìn)行分層設(shè)計，實(shí)現(xiàn)了一個完整的大數(shù)據(jù)挖掘平臺。實(shí)驗(yàn)表明，基于Spark實(shí)現(xiàn)的Apriori算法跟PageRank算法的并行計算能有效減少執(zhí)行時間，在大數(shù)據(jù)挖掘上具有較好的應(yīng)用。

大數(shù)據(jù)；數(shù)據(jù)挖掘；Spark；引擎

由于計算機(jī)的普及以及網(wǎng)絡(luò)的發(fā)展，互聯(lián)網(wǎng)在人們的日常生活與工作中應(yīng)用越來越廣泛，每天均有大量的人在使用互聯(lián)網(wǎng)，同時也產(chǎn)生了大量的數(shù)據(jù)。隨著時間的推移，人們積累的數(shù)據(jù)量越來越多，規(guī)模高達(dá)TB級甚至PB級。為了取得這些數(shù)據(jù)中的有用信息，人們利用各種數(shù)據(jù)挖掘算法來挖掘其中的潛在價值。雖然數(shù)據(jù)挖掘在小數(shù)據(jù)集上的應(yīng)用具有較好的效果，但對于大數(shù)據(jù)集而言，數(shù)據(jù)挖掘算法在執(zhí)行效率，算法并行化及平臺易用性等存在問題[1-5]。

為了解決上述問題，文中對大數(shù)據(jù)下的數(shù)據(jù)挖掘引擎進(jìn)行了研究，以Spark作為核心引擎，并在Spark的內(nèi)存計算算子的基礎(chǔ)上，實(shí)現(xiàn)了多個傳統(tǒng)數(shù)據(jù)挖掘算法的并行計算，使得傳統(tǒng)的數(shù)據(jù)挖掘算法能在集群環(huán)境中并行運(yùn)行，從而在大數(shù)據(jù)中得到較好的應(yīng)用。然后通過系統(tǒng)分層方法，將數(shù)據(jù)挖掘系統(tǒng)進(jìn)行分層設(shè)計，實(shí)現(xiàn)了一個完整的大數(shù)據(jù)挖掘平臺。

1 基于Spark的并行數(shù)據(jù)挖掘算法

Spark是一種開源集群計算環(huán)境，與Mahout相比，其擁有更快的計算速度，更適用于大數(shù)據(jù)的數(shù)據(jù)挖掘中，因此將其選為數(shù)據(jù)挖掘的核心引擎。由于Spark所提供的數(shù)據(jù)挖掘算法覆蓋量較少，例如缺少Apriori算法和PageRank算法。為了使Spark能成為核心引擎，本文在Spark的基礎(chǔ)上實(shí)現(xiàn)了Apriori算法和PageRank算法的并行執(zhí)行。

1.1 Spark編程模型

Spark[6-7]主要有兩個特點(diǎn)，首先是彈性分布式數(shù)據(jù)集（RDD），其將集群中的節(jié)點(diǎn)內(nèi)存全部組織起來，從而使所有節(jié)點(diǎn)內(nèi)存能并行使用。RDD的建立一方面可通過加載HDFS文件來實(shí)現(xiàn)，也可由轉(zhuǎn)換現(xiàn)有的RDD來得到。用戶可將指定的RDD緩存在內(nèi)存中，從而在再次使用時可免去創(chuàng)建過程，提升速度。

另一個特點(diǎn)是變量共享功能。Spark能在不同節(jié)點(diǎn)執(zhí)行的任務(wù)中對共享向量進(jìn)行拷貝，其能夠在并行計算中使用。Spark的共享變量主要有廣播變量及累加器變量，廣播變量用于將一個值緩存到所有節(jié)點(diǎn)內(nèi)存中，累加器變量執(zhí)行累加功能。

1.2 Apriori算法

Apriori算法[8-9]是一種關(guān)聯(lián)規(guī)則算法，其功能為挖掘大數(shù)據(jù)中事件的關(guān)聯(lián)性，篩選出關(guān)聯(lián)性大于預(yù)設(shè)閾值的事件，主要用于分析用戶的消費(fèi)行以及為商業(yè)政策的制定提供可行性分析等。設(shè)定事件A與B同時發(fā)生的概率為支持度，事件項(xiàng)集支持度大于預(yù)設(shè)值稱為頻繁項(xiàng)集，Apriori算法的工作步驟為：

1）掃描數(shù)據(jù)庫，計算每個事件集的支持度，并將支持度小于預(yù)設(shè)值的事件集篩選掉，得到頻繁項(xiàng)集L1。

2）將頻繁項(xiàng)集的元素兩兩結(jié)合為一個事件項(xiàng)，形成新的事件項(xiàng)集。

3）將支持度小于預(yù)設(shè)值的事件集篩選掉，得到頻繁項(xiàng)集Lk。

4）重復(fù)執(zhí)行步驟 2）、3），直到不能形成新的事件項(xiàng)集。

1.3 PageRank算法

PageRank算法[10-11]是一種對網(wǎng)頁搜索結(jié)果進(jìn)行排序的算法，其工作原理為，以所有鏈接到某一網(wǎng)頁的鏈接數(shù)作為該網(wǎng)頁的支持度，對于一次搜索行為后，計算每一個搜索結(jié)果網(wǎng)頁的支持度，并按照支持度從大到小的順序?qū)λ阉鹘Y(jié)果進(jìn)行排序。

2 系統(tǒng)設(shè)計

2.1 系統(tǒng)架構(gòu)設(shè)計

本文的數(shù)據(jù)挖掘系統(tǒng)架構(gòu)[12-15]如圖1所示，從底往上分別分為引擎層、中間層以及用戶層。引擎層為系統(tǒng)的最低層，其作為系統(tǒng)的數(shù)據(jù)處理引擎，以Spark集群為主體，并通過Zookeeper實(shí)現(xiàn)集群配置管理，以及使用Mesos對資源進(jìn)行調(diào)度，封裝常見的數(shù)據(jù)接入接口。中間層包括對（RPC）接口的遠(yuǎn)程調(diào)用以及多用戶并發(fā)的控制請求。用戶層主要包含開發(fā)套件和可視化控件等。

圖1 系統(tǒng)整體架構(gòu)圖

2.2 引擎層

引擎層是整個數(shù)據(jù)挖掘系統(tǒng)的核心部分，其擔(dān)負(fù)著系統(tǒng)的數(shù)據(jù)處理引擎。引擎層運(yùn)行在Linux集群環(huán)境下，文中使用的是Ubuntu 16.04 64位系統(tǒng)。引擎層以spark集群為核心，通過Zookeeper實(shí)現(xiàn)集群配置管理，并使用Mesos對資源進(jìn)行調(diào)度，封裝常見的數(shù)據(jù)接入接口，包括Kafka，F(xiàn)lume等。此外，引擎層還具有3個組件，包括Spark SQL、數(shù)據(jù)挖掘算法包及Spark Streaming。Spark SQL用于處理結(jié)構(gòu)化大數(shù)據(jù)；數(shù)據(jù)挖掘算法包用于提供數(shù)據(jù)挖掘算法，包括前文介紹的Apriori算法和PageRank算法；Spark Streaming用于處理流式數(shù)據(jù)。

圖2 引擎層設(shè)計圖

2.3 中間層

中間層負(fù)責(zé)對（RPC）接口的遠(yuǎn)程調(diào)用以及多用戶并發(fā)的控制請求。RPC（Remote Procedure CallProtocol），即遠(yuǎn)程過程調(diào)用協(xié)議，其是一種通過網(wǎng)絡(luò)從遠(yuǎn)程計算機(jī)程序上請求服務(wù)，而無需要了解底層網(wǎng)絡(luò)技術(shù)的協(xié)議。RPC能夠使用戶免去登錄到集群環(huán)境中進(jìn)行操作的環(huán)節(jié)而直接在本地進(jìn)行調(diào)用，減去了提交大數(shù)據(jù)計算任務(wù)的環(huán)節(jié)。由于RPC由Python語言編寫，因而選用Python的xml-rpc，其工作過程如圖3所示。

首先是用戶發(fā)起調(diào)用請求后，數(shù)據(jù)將被封裝為xml的格式，然后通過HTTP的post方法，將xml格式的數(shù)據(jù)傳播給rpc服務(wù)端，服務(wù)端解析xml數(shù)據(jù)，執(zhí)行相關(guān)指令后，將結(jié)果以xml格式返回給調(diào)用端。

圖3 xml-rpc處理過程

為了滿足同一時間不同用戶的需求，引入隊(duì)列作為請求的存儲結(jié)構(gòu)，對任務(wù)進(jìn)行優(yōu)先級排序。用戶請求調(diào)度過程如圖4所示，中間層在接收到一個RPC調(diào)用時，先判斷是否為getModel調(diào)用，若是將調(diào)用從Memcached取出執(zhí)行，并將結(jié)果返回給用戶層。若不是getModel調(diào)用，判斷是否為Schedule調(diào)用，若為Schedule調(diào)用，則將調(diào)用標(biāo)記為KEY鎖定并放入到候選隊(duì)列中等候執(zhí)行；若不是Schedule調(diào)用，則不執(zhí)行調(diào)用。

圖4 中間層流程圖

3 實(shí)驗(yàn)測試

文中在惠普Precision T5810工作站上搭建實(shí)驗(yàn)平臺，處理器為Intel E5-1620處理器，主頻3.5GHz，內(nèi)存16G，硬盤1TB。在工作站上建立虛擬機(jī)，系統(tǒng)環(huán)境為Ubuntu 16.04 64位系統(tǒng)，完成Spark分布式環(huán)境的搭建。本文通過實(shí)驗(yàn)來比較以MapReduce及以Spark為基礎(chǔ)的Apriori算法和PageRank的并行化執(zhí)行效率，其中數(shù)據(jù)集采用大小分別為20MB，30MB，70MB，100MB 的 Note Dame，Stanford，Google以及Berkeley-Stanford數(shù)據(jù)集，對于頻繁項(xiàng)分析，本文采用T10I4D100K.數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果如圖5～8所示。

由圖5，圖7可看出，不管是Apriori算法還是PageRank算法，本文提出的基于Spark的內(nèi)存計算算子實(shí)現(xiàn)的數(shù)據(jù)挖掘算法的并行計算，其平均執(zhí)行時間遠(yuǎn)小于MapReduce的平均執(zhí)行時間。隨著數(shù)據(jù)量的增加，基于MapReduce的數(shù)據(jù)挖據(jù)算法執(zhí)行時間成線性增長，且斜率較大。而基于Spark的數(shù)據(jù)挖掘算法執(zhí)行時間增長緩慢，并未發(fā)生較大變化。這是由于Spark基于內(nèi)存進(jìn)行計算的，其將每次迭代結(jié)果均緩存在內(nèi)存中，因而能直接讀取，減少了從硬盤讀取數(shù)據(jù)的時間。

其次，隨著Slave節(jié)點(diǎn)的增加，基于Spark的數(shù)據(jù)挖掘算法Apriori和PageRank算法的執(zhí)行時間呈線性下降，說明這兩種算法均能較好地進(jìn)行算法的并行計算。

4 結(jié)束語

基于大數(shù)據(jù)的數(shù)據(jù)挖掘算法其在執(zhí)行效率，算法并行化以及平臺易用性等存在問題。為了解決這些問題，本文對大數(shù)據(jù)下的數(shù)據(jù)挖掘引擎進(jìn)行了研究，以Spark作為核心引擎，并在Spark的內(nèi)存計算算子的基礎(chǔ)上，實(shí)現(xiàn)了多個傳統(tǒng)數(shù)據(jù)挖掘算法的并行計算，使得傳統(tǒng)的數(shù)據(jù)挖掘算法能在集群環(huán)境中并行運(yùn)行，從而在大數(shù)據(jù)中得到較好的應(yīng)用。然后通過系統(tǒng)分層方法，將數(shù)據(jù)挖掘系統(tǒng)進(jìn)行分層設(shè)計，實(shí)現(xiàn)了一個完整的大數(shù)據(jù)挖掘平臺。實(shí)驗(yàn)表明，基于Spark實(shí)現(xiàn)的Apriori算法跟PageRank算法的并行計算能有效減少執(zhí)行時間，在大數(shù)據(jù)挖掘上具有較好的應(yīng)用。

圖5 并行化Apriori算法的數(shù)據(jù)規(guī)模實(shí)驗(yàn)結(jié)果

圖6 并行化Apriori算法的集群規(guī)模實(shí)驗(yàn)結(jié)果

圖7 并行化PageRank算法的數(shù)據(jù)規(guī)模實(shí)驗(yàn)結(jié)果

圖8 并行化PageRank算法的集群規(guī)模實(shí)驗(yàn)結(jié)果

[1]Gheraawat S，Gobioff H，Leung ST.The Google file system [C].ACM SIGOPS Operating Systems Review.ACM， 2003，37（5）:29-43.

[2]Dean J，Ghemawat S.MapReduce:simplified data processing on large chisters[J].Communications of the ACM，2008，51（1）:107-113.

[3]Chang F，Dean J，Ghemawat S，et al.Bigtable:A distributed storage system for structured data[J].ACM Transactions on Computer Systems（TOCS），2008，26（2）:4.

[4]Taylor R C.An overview of the Hadoop/Map Reduce/HBase framework and its current applications in bioinformatics[J].BMC bbinformatics，2010，ll（Suppl 12）:S1.

[5]McKenna A， Hanna M， Banks E，et al.The Genome Analysis Toolkit:aMapReduce framework for analyzing next-generation DNA sequencing data[J].Genome research^2010，20（9）:1297-1303.

[6]胡俊，胡賢德，程家興.基于Spark的大數(shù)據(jù)混合計算模型[J].計算機(jī)系統(tǒng)應(yīng)用，2015（4）:214-218.HU Jun，HU Xiande，CHENG Jiaxing.Spark Big Data hybrid computing model[J].Computer Systems&Applications，2015（4）:214-218.

[7]王虹旭，吳斌，劉旸.基于Spark的并行圖數(shù)據(jù)分析系統(tǒng)[J].計算機(jī)科學(xué)與探索，2015，9（9）:1066-1074.

[8]崔貫勛，李梁，王柯柯，等.關(guān)聯(lián)規(guī)則挖掘中Apriori算法的研究與改進(jìn)[J].計算機(jī)應(yīng)用，2010，30（11）:2952-2955.

[9]栗青霞，王換換，傅喆.改進(jìn)的Apriori算法在試題關(guān)聯(lián)分析中的應(yīng)用[J].電子科技，2014，27（2）:35-38.

[10]李稚楹，楊武，謝治軍.PageRank算法研究綜述[J].計算機(jī)科學(xué)，2011（s1）:185-188.

[11]錢功偉，倪林，MIAO，等.基于網(wǎng)頁鏈接和內(nèi)容分析的改進(jìn)PageRank算法[J].計算機(jī)工程與應(yīng)用，2007，43（21）:160-164.

[12]余永紅，向曉軍，高陽，等.面向服務(wù)的云數(shù)據(jù)挖掘引擎的研究[J].計算機(jī)科學(xué)與探索，2012，6（1）:46-57.

[13]張英朝，鄧蘇，張維明，等.智能數(shù)據(jù)挖掘引擎的設(shè)計與實(shí)現(xiàn)[J].計算機(jī)科學(xué)，2002，29（10）:11-13.

[14]姚全珠，張杰.基于數(shù)據(jù)挖掘的搜索引擎技術(shù)[J].計算機(jī)應(yīng)用研究，2006，23（11）:29-30.

[15]陳勇，張佳驥，吳立德，等.基于數(shù)據(jù)挖掘的面向話題搜索引擎研究[J].無線電通信技術(shù)，2011，37（5）:38-40.

Research on data mining engine based on big data

WANG Xiao-yan1，ZHANG Li-min2
（1.Shaanxi Radio and TV University， Xi'an 710119，China； 2.Xi'an Institute of Foreign Affairs and Network Information Institute， Xi'an 710077， China）

In order to solve the problem of data mining in large data，the data of the large-scale data mining engine is studied， using Spark as the core engine， and in the memory of Spark operator on the basis of the implementation of a number of traditional data mining algorithms of parallel computing，the traditional data mining algorithm can run in parallel in a cluster environment，so as to obtain the very good application in big data.Then through the system layering method，the data mining system is designed，and a complete big data mining platform is realized.Experimental results show that the Apriori algorithm based on Spark algorithm and PageRank algorithm can effectively reduce the execution time，and it has a good application in large data mining.

big data； data mining； Spark；engine

TN99

：A

：1674－6236（2017）15-0031-04

2016-09-17稿件編號：201609153

陜西省教育廳科研項(xiàng)目（16JK2176）；陜西工商職業(yè)學(xué)院2015年度教學(xué)改革研究項(xiàng)目（GJ1510）

王小燕（1982—），女，陜西西安人，碩士，工程師。研究方向：軟件工程。