一種基于云計算的大數(shù)據(jù)關(guān)聯(lián)規(guī)律挖掘分析方法

陳 勇

(中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

一種基于云計算的大數(shù)據(jù)關(guān)聯(lián)規(guī)律挖掘分析方法

陳 勇

(中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

隨著云計算時代的到來，云計算為海量數(shù)據(jù)的挖掘分析提供了一種新的技術(shù)途徑，能夠有效地解決傳統(tǒng)數(shù)據(jù)挖掘方法不能適應(yīng)海量數(shù)據(jù)挖掘的問題。介紹了云計算的含義和特點(diǎn)，分析了運(yùn)用云計算技術(shù)實(shí)現(xiàn)數(shù)據(jù)挖掘的優(yōu)勢，設(shè)計了基于MapReduce并行處理架構(gòu)的關(guān)聯(lián)規(guī)律挖掘算法，并開展了試驗(yàn)驗(yàn)證。試驗(yàn)結(jié)果表明，基于云計算平臺的并行關(guān)聯(lián)規(guī)律挖掘算法能夠極大地提高數(shù)據(jù)挖掘的執(zhí)行速度。

云計算；數(shù)據(jù)挖掘；大數(shù)據(jù)處理

0 引言

數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的應(yīng)用數(shù)據(jù)中提取隱藏在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程[1]。云計算采用分布式計算模式，將計算任務(wù)分配到不同的計算節(jié)點(diǎn)上，根據(jù)用戶的業(yè)務(wù)需求動態(tài)組成相適應(yīng)的計算和存儲服務(wù)能力，云計算為存儲和分析海量數(shù)據(jù)提供了高效的存儲和計算平臺[2-3]。云計算平臺下的并行數(shù)據(jù)挖掘算法設(shè)計是解決大數(shù)據(jù)挖掘分析的關(guān)鍵技術(shù)，具有重要的理論意義和應(yīng)用價值。

本文利用Hadoop中的MapReduce分布式并行計算框架設(shè)計了并行化的FP-Growth算法，實(shí)現(xiàn)了大規(guī)模數(shù)據(jù)的快速深度分析。

1 大數(shù)據(jù)關(guān)聯(lián)規(guī)律挖掘的理論分析

1.1 關(guān)聯(lián)規(guī)律挖掘理論

關(guān)聯(lián)規(guī)律挖掘分析是一種重要的數(shù)據(jù)分析方法，主要用于發(fā)現(xiàn)存在于大量數(shù)據(jù)集中的數(shù)據(jù)屬性取值之間的關(guān)聯(lián)規(guī)律，關(guān)聯(lián)規(guī)律挖掘的問題描述如下：

假定：I={i1，i2……，im}是所有數(shù)據(jù)屬性可能取值的集合，D是所有交易記錄的集合(即數(shù)據(jù)庫)，每條交易記錄T是一些項(xiàng)目的集合，T包含在I中，即每條交易記錄由若干個屬性及其取值的鍵值對組成，每條交易記錄可以用唯一的標(biāo)識符TID來標(biāo)識。設(shè)X為某些數(shù)據(jù)屬性取值的集合，如果X包含在T中，則稱交易記錄T包含X，關(guān)聯(lián)規(guī)律可表示為如下形式(X包含在T)=>(Y包含在T)的蘊(yùn)涵式，這里X包含在I中，Y包含在I中，并且X∧Y=?。其意義在于一個事務(wù)中某些數(shù)據(jù)屬性取值的出現(xiàn)，可推導(dǎo)出另一些數(shù)據(jù)屬性取值在同一事務(wù)中也出現(xiàn)，可將(X包含在T)=>(Y包含在T)表示為X=>Y，此處，‘=>’稱為‘關(guān)聯(lián)’操作，X稱為關(guān)聯(lián)規(guī)律的先決條件，Y稱為關(guān)聯(lián)規(guī)律的結(jié)果[4]。

所有交易記錄的集合D中的規(guī)律X=>Y有2個指標(biāo)：支持度s(support)和置信度c(confidence)，c表示規(guī)律的可信強(qiáng)度，c越高說明此規(guī)律的因果關(guān)系越強(qiáng)；s表示以整個數(shù)據(jù)庫中的數(shù)據(jù)為背景，一項(xiàng)規(guī)律出現(xiàn)的頻度，s越高說明此規(guī)律越具有應(yīng)用價值。數(shù)據(jù)屬性取值集合X的支持度s(X)是D中包含X的交易記錄數(shù)量與D中所有交易記錄數(shù)量之比。

規(guī)律X=>Y的支持度s定義為：在D中包含X∪Y的交易記錄所占比例為s%，表示同時包含X和Y的交易記錄數(shù)量與D中所有交易記錄數(shù)量之比；規(guī)律X=>Y的置信度c定義為：在D中，c%的交易記錄包含X的同時也包含Y，表示D中包含X的交易記錄中有多大可能性包含Y。

最小支持度閾值minsupport表示數(shù)據(jù)屬性取值集合在統(tǒng)計意義上的最低應(yīng)用價值。最小置信度閾值minconfidence表示規(guī)律的最低可信度。一般由用戶給定minconfidence和minsupport。置信度和支持度大于相應(yīng)閾值的規(guī)律稱為強(qiáng)關(guān)聯(lián)規(guī)律，反之稱為弱關(guān)聯(lián)規(guī)律。發(fā)現(xiàn)關(guān)聯(lián)規(guī)律的任務(wù)就是從數(shù)據(jù)庫中發(fā)現(xiàn)那些置信度、支持度大小等于給定值的有效規(guī)律。

找出數(shù)據(jù)庫D中所有大于等于用戶指定最小支持度的數(shù)據(jù)屬性取值集合(itemset)，具有最小支持度的數(shù)據(jù)屬性取值集合稱為頻繁項(xiàng)目集，項(xiàng)目集的支持度是指包含該項(xiàng)目集的交易記錄數(shù)量。

利用頻繁項(xiàng)目集生成所需要的關(guān)聯(lián)規(guī)律，對每一頻繁項(xiàng)目集A，找到A的所有非空子集a，如果比率滿足support(A)/support(a)>=minconfidence，那么就可以生成關(guān)聯(lián)規(guī)律a=>(A-a)。而support(A)/support(a)是規(guī)則a=>(A-a)的置信度。

1.2 關(guān)聯(lián)規(guī)律挖掘算法

事實(shí)上，在挖掘關(guān)聯(lián)規(guī)律的過程中找到所有的頻繁項(xiàng)目集是核心問題。當(dāng)找到所有的頻繁項(xiàng)目集后，相應(yīng)的關(guān)聯(lián)規(guī)律將很容易產(chǎn)生。

Apriori算法是進(jìn)行關(guān)聯(lián)規(guī)律挖掘的常用方法，Apriori算法包括兩步[5]：第1步，統(tǒng)計所有含一個屬性-取值鍵值對出現(xiàn)的頻率，并找出那些不小于最小支持度的屬性-取值鍵值對集，即一維頻繁項(xiàng)目集；從第2步開始進(jìn)入一個循環(huán)處理過程直到找出所有頻繁鍵值對集。這一循環(huán)過程可以描述如下：第k步中，根據(jù)第k-1步生成的(k-1)維頻繁屬性-取值鍵值對集產(chǎn)生k維候選屬性-取值鍵值對集，然后對數(shù)據(jù)庫進(jìn)行搜索，得到候選屬性-取值鍵值對集的支持度，與最小支持度比較，從而找到k維頻繁屬性-取值鍵值對集。Apriori算法對候選屬性-取值鍵值對集進(jìn)行甄別，刪除那些不可能成為頻繁屬性-取值鍵值對集的候選屬性-取值鍵值對集。這樣就節(jié)省了花費(fèi)在這些不合格候選屬性-取值鍵值對集上的數(shù)據(jù)庫搜索時間，但Apriori算法仍有以下缺點(diǎn)[6-7]：

每次計算屬性-取值鍵值對集的支持度時，都需要對D中的全部記錄進(jìn)行一遍遍歷比較。如果數(shù)據(jù)庫規(guī)模很大，這種逐條比較的運(yùn)算時間就會很長。

為了解決Apriori算法的上述缺點(diǎn)，F(xiàn)P-Growth算法采用以下策略：首先，將數(shù)據(jù)庫中的內(nèi)容映射到一棵頻繁模式樹(FP-Tree)，但仍保留屬性-取值鍵值對集的關(guān)聯(lián)信息；然后，將FP樹按照頻繁模式投影，分為若干條件數(shù)據(jù)庫，并分別挖掘每個數(shù)據(jù)庫。

FP-Growth算法將一個大型數(shù)據(jù)庫映射成比原數(shù)據(jù)庫規(guī)模小很多的高密度的數(shù)據(jù)結(jié)構(gòu)，避免了重復(fù)遍歷數(shù)據(jù)庫[8]。該算法基于FP樹采取模式增長的遞歸策略，是一種無候選項(xiàng)集的挖掘方法，在進(jìn)行頻繁項(xiàng)集的挖掘時效率很高。FP-Growth算法的執(zhí)行步驟如下：

① 遍歷一次D得到所有頻繁屬性-取值鍵值對及其支持度數(shù)值，并對頻繁屬性-取值鍵值對按其支持度計數(shù)從高到低進(jìn)行排序，并構(gòu)建頭表；

② 再次遍歷D，將讀取的每條記錄按照第①步的頻繁屬性-取值鍵值對順序進(jìn)行排序，排序后以null為根結(jié)點(diǎn)構(gòu)建一條FP樹的路徑，對路徑上項(xiàng)的計數(shù)+1，在插入FP樹過程中查找頭表里對應(yīng)的屬性-取值鍵值對，建立鏈表索引；

③ 從頭表尾部向上遍歷頻繁屬性-取值鍵值對集，每次循環(huán)過程中從頭表的鏈表里訪問FP樹得到條件模式，根據(jù)條件模式構(gòu)建每個頻繁屬性-取值鍵值對的條件FP樹；

④ 從條件FP樹分單分支和多分支2種情況遞歸挖掘頻繁屬性-取值鍵值對集。

但是，對于海量數(shù)據(jù)而言，F(xiàn)P-Growth算法的時空復(fù)雜度仍然很高，因此，對于大數(shù)據(jù)挖掘應(yīng)用而言，F(xiàn)P-Growth算法仍有進(jìn)一步改進(jìn)的必要[9]。在本項(xiàng)研究中，利用云計算平臺Hadoop中的MapReduce分布式并行處理模型設(shè)計并行版的FP-Growth算法，通過充分發(fā)揮多機(jī)并行處理的優(yōu)勢，提高挖掘分析計算的效率，。

2 基于云計算的關(guān)聯(lián)規(guī)律算法設(shè)計

2.1 Hadoop平臺

Hadoop是Apache機(jī)構(gòu)的一個開源產(chǎn)品，能夠以分布式存儲和并行計算方式處理海量數(shù)據(jù)。其分布式存儲Hadoop Distributed File System(HDFS)能夠在多個節(jié)點(diǎn)上存儲數(shù)據(jù)，數(shù)據(jù)被分割成更小的數(shù)據(jù)塊分別存儲在不同節(jié)點(diǎn)上，因此，可以同時向多個節(jié)點(diǎn)上存儲數(shù)據(jù)，也可以同時從多個節(jié)點(diǎn)上讀取數(shù)據(jù)，除了HDFS文件系統(tǒng)外，Hadoop產(chǎn)品還包括并行處理模型MapReduce[10]，將各類運(yùn)算都抽象為Map運(yùn)算[11]和Reduce運(yùn)算[12]，使得用戶不必關(guān)心并行處理過程中的作業(yè)調(diào)度和節(jié)點(diǎn)間的數(shù)據(jù)交換等繁瑣細(xì)節(jié)，只需專注業(yè)務(wù)處理邏輯，并充分利用計算機(jī)集群的協(xié)作能力實(shí)現(xiàn)高速業(yè)務(wù)運(yùn)算[13-14]。

由于FP-Growth算法將數(shù)據(jù)庫記錄數(shù)據(jù)中的頻繁部分在內(nèi)存中映射成FP樹，當(dāng)數(shù)據(jù)規(guī)模很大時，F(xiàn)P樹會很龐大，因此，算法中FP樹的構(gòu)建屬于計算密集型業(yè)務(wù)。在本文中，基于MapReduce的并行處理模型來提高FP樹的構(gòu)建效率。

MapReduce并行處理模型的原理就是利用一個輸入的鍵值對集合來產(chǎn)生一個輸出的鍵值對集合[15-16]。MapReduce任務(wù)過程被分為Map環(huán)節(jié)和Reduce環(huán)節(jié)。Map環(huán)節(jié)負(fù)責(zé)把計算任務(wù)分解為多個作業(yè)，Reduce環(huán)節(jié)負(fù)責(zé)把分解后的多個作業(yè)的處理結(jié)果匯集起來，用戶需要定義2個函數(shù)：Map和Reduce，Map函數(shù)接收輸入數(shù)據(jù)，并分割成固定大小的片段，隨后將每個片段進(jìn)一步分解成一批鍵-值對，為每一個數(shù)據(jù)片段創(chuàng)建一個Map任務(wù)，用于執(zhí)行業(yè)務(wù)處理所需的Map函數(shù)，并將對應(yīng)片段中的對作為輸入，得到計算的中間結(jié)果，接著將中間結(jié)果按照K2進(jìn)行排序，并將鍵相同的值放在一起，形成列表，最后再根據(jù)鍵的范圍將這些組進(jìn)行分組，對應(yīng)不同的Reduce任務(wù)[17]。在Reduce環(huán)節(jié)，把接收到的數(shù)據(jù)匯集在一起并進(jìn)行排序，然后調(diào)用業(yè)務(wù)處理所需的Reduce函數(shù)，對輸入的對進(jìn)行相應(yīng)的處理，得到鍵-值對并輸出到HDFS文件存儲系統(tǒng)上[18]。

2.2 基于MapReduce的挖掘算法設(shè)計

基于MapReduce的并行FP-Growth算法設(shè)計如下：

第1步： 通過一次MapReduce任務(wù)統(tǒng)計屬性-取值鍵值對的頻繁度。FP-Growth算法在構(gòu)造FP樹之前需掃描一遍數(shù)據(jù)庫統(tǒng)計屬性-取值鍵值對的頻繁度并排序，這實(shí)際上是FP-Growth算法的第①步。

第2步： 通過一次MR任務(wù)執(zhí)行MR-FP算法計算頻繁項(xiàng)集。在MR-FP算法中利用MapReduce并行處理模型對傳統(tǒng)FP-Growth算法的第②、③、④步進(jìn)行并行設(shè)計，這是算法的核心任務(wù)，通過此次MapReduce任務(wù)將FP-Growth算法中對各頻繁屬性-取值鍵值對的條件FP樹的挖掘運(yùn)算分發(fā)到各個節(jié)點(diǎn)，進(jìn)行本地計算，再匯集各個節(jié)點(diǎn)的局部計算結(jié)果，形成最終結(jié)果。

基于Hadoop集群的MapReduce框架實(shí)現(xiàn)上述步驟的具體方法描述如下：

第1步：對所有的輸入進(jìn)行統(tǒng)計，統(tǒng)計出每一項(xiàng)的出現(xiàn)頻率，這一點(diǎn)可以通過Hadoop下一個詞頻統(tǒng)計任務(wù)(wordcount任務(wù))完成，對輸出結(jié)果按照頻率進(jìn)行降序排列，得到詞表F-list。

第2步：對所有F-list中的詞進(jìn)行分組，生成組表G-list，組號為id，將對應(yīng)的輸入分別在Map中進(jìn)行輸出。

第3步：當(dāng)Reduce接收到Map端的輸入后，對數(shù)據(jù)進(jìn)行本地化的FP-Growth算法計算，將超過支持度閾值的項(xiàng)進(jìn)行輸出。

第4步：對結(jié)果進(jìn)行聚合、排序以及相關(guān)的統(tǒng)計。

Map階段算法的核心偽代碼如下：

LoadG-List;

Generate Hash TableHfromG-List;

a[]←Split(Ti);

forj=|Ti|-1 to 0 do

HashNum←getHashNum(H,a[j]);

ifHashNum≠Nullthen

Delete all pairs which hash value isHashNuminH;

Call Output();

end

end

Reduce階段算法的核心偽代碼如下：

Procedure:Reducer(key=gid,value=DBgid)

LoadG-List

nowGroup←G-Listgid

LocalFPtree←clear;

foreachTiinDBgiddo

Define and clear a size K max heap:HP;

Call TopKFPGrowth(LocalFPtree,ai,HP);

foreachviinHPdo

Call Output();

end

end

3 實(shí)驗(yàn)計算與結(jié)果分析

為了驗(yàn)證所設(shè)計并行FP-Growth算法的正確性以及效率，搭建了一個Hadoop平臺開展了相關(guān)實(shí)驗(yàn)，Hadoop平臺計算機(jī)集群有28個計算節(jié)點(diǎn)，每個節(jié)點(diǎn)有1T的硬盤容量，6G的內(nèi)存空間。實(shí)驗(yàn)使用的數(shù)據(jù)集共含有1百萬行數(shù)據(jù)，每行包含的事物項(xiàng)個數(shù)約100個。

首先使用單機(jī)版的FP-Growth算法進(jìn)行測試，將支持度閾值設(shè)為1%，單機(jī)版的FP-Growth算法會發(fā)生outofmemory錯誤，可見FP-Growth算法本身存在巨大的內(nèi)存需求。

然后，使用并行版的FP-Growth算法進(jìn)行測試，測試過程中設(shè)置不同的支持度閾值，進(jìn)行了對比試驗(yàn)，對執(zhí)行時間、挖掘出的規(guī)則數(shù)量進(jìn)行測試，具體測試結(jié)果如表1所示。

表1 支持度閾值、運(yùn)行時間、輸出數(shù)目的關(guān)系

支持度與執(zhí)行時間關(guān)系如圖1所示。

圖1 支持度與執(zhí)行時間關(guān)系

通過對實(shí)驗(yàn)數(shù)據(jù)的分析發(fā)現(xiàn)，隨著支持度閾值的不斷降低，無論是執(zhí)行時間還是輸出規(guī)則數(shù)目都會以指數(shù)級的速度增長，尤其是當(dāng)閾值從0.2%降為0.1%時，輸出的數(shù)目出現(xiàn)了快速增長，在單機(jī)條件下甚至出現(xiàn)運(yùn)行失敗的情況，這是由于閾值過小，剪枝之后的FP樹依舊巨大，內(nèi)存資源無法滿足導(dǎo)致的。

并行版的FP-Growth算法非常適合于基于計算機(jī)集群的海量數(shù)據(jù)關(guān)聯(lián)規(guī)律挖掘，當(dāng)集群新增計算節(jié)點(diǎn)時，無需對算法進(jìn)行任何修改就可以繼續(xù)使用，算法效率與計算節(jié)點(diǎn)數(shù)量成正比。

4 結(jié)束語

關(guān)聯(lián)規(guī)律挖掘是大數(shù)據(jù)分析常用的算法和基礎(chǔ)性工具，本文針對海量的結(jié)構(gòu)化數(shù)據(jù)，基于云計算平臺開展了大數(shù)據(jù)關(guān)聯(lián)規(guī)律挖掘算法研究，以發(fā)現(xiàn)數(shù)據(jù)中潛在關(guān)聯(lián)模式和規(guī)律，研究成果解決了傳統(tǒng)串行數(shù)據(jù)挖掘算法計算效率低的問題，在保證結(jié)果正確的前提下，能夠快速地完成數(shù)據(jù)挖掘分析任務(wù)。

[1] 毛國君，段立娟，王 實(shí)，等.數(shù)據(jù)挖掘原理與算法[M].北京：清華大學(xué)出版社，2005：64-205.

[2] 王 軼，達(dá)新宇.分布式并行數(shù)據(jù)挖掘計算框架及其算法研究[J].微電子學(xué)與計算機(jī)，2006，23(9)：223-225.

[3] 楊武軍，郝 凱.基于貪心改進(jìn)算法的云計算任務(wù)調(diào)度[J].傳感器與微系統(tǒng)，2016，35(12):143-145.

[4] 李曉毅，徐兆棣.關(guān)聯(lián)規(guī)則挖掘的算法分析[J]．遼寧工程技術(shù)大學(xué)學(xué)報，2006，24(2)：319-320.

[5] 朱小琴.Apriori算法的分析與改進(jìn)[J]．廣西民族大學(xué)學(xué)報(自然科學(xué)版)，2013，19(4)：68-71.

[6] 陳麗芳.基于Apriori算法的購物籃分析[J]．重慶工商大學(xué)學(xué)報(自然科學(xué)版)，2014，31(5)：84-89.

[7] 亓文娟，晏 杰.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則Apriori算法[J]．計算機(jī)系統(tǒng)應(yīng)用，2013，22(4)：121-124.

[8] 石云平.FP-Growth關(guān)聯(lián)算法應(yīng)用研究[J]．計算機(jī)與信息技術(shù)，2008，10(6)：12-14.

[9] 呂萍麗.淺談Apriori算法[J]．電腦知識與技術(shù)，2011，7(4)：715-716.

[10] 郭景瞻，張文逵.Hadoop平臺下的數(shù)據(jù)遷移設(shè)計與實(shí)現(xiàn)[J].信息技術(shù)與標(biāo)準(zhǔn)化，2014，38(9)：39-41.

[11] 張 遙，蔣春娟.基于Hadoop集群的海量數(shù)據(jù)處理系統(tǒng)[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2014，38(10)：8-9.

[12] 宛 婉，周國祥.Hadoop平臺的海量數(shù)據(jù)并行隨機(jī)抽樣[J].計算機(jī)工程與應(yīng)用，2014，50(20)：115-118.

[13] 劉師語，周淵平，杜 江.基于HADOOP分布式系統(tǒng)的數(shù)據(jù)處理分析[J].通信技術(shù)，2013，46(9)：99-102.

[14] 陳吉榮，樂嘉錦.于Hadoop生態(tài)系統(tǒng)的大數(shù)據(jù)解決方案綜述[J].計算機(jī)工程與科學(xué)，2013，35(10)：27-35.

[15] 陳 娜，張金娟，劉智瓊，等.基于Hadoop平臺的電信大數(shù)據(jù)入庫及查詢性能優(yōu)化研究[J].移動通信,2014,38(7):58-63.

[16] 蔡斌雷，任家東，朱世偉，等.基于Hadoop MapReduce的分布式數(shù)據(jù)流聚類算法研究[J].信息工程大學(xué)學(xué)報，2014，15(4)：472-478.

[17] 楊 勇，高松松.基于MapReduce的關(guān)聯(lián)規(guī)則并行增量更新算法[J].重慶郵電大學(xué)學(xué)報(自然科學(xué)版)，2014，26(5)：670-678.

[18] 張 帥，趙卓峰，丁維龍，等.基于MapReduce的城市道路旅行時間實(shí)測計算[J].計算機(jī)與數(shù)字工程，2014，299(9)：1 542-1 546.

陳 勇 男，(1968—)，高級工程師。主要研究方向：數(shù)據(jù)挖掘。

A Method of Mining Association Rules of Big Data Based on Cloud Computing

CHEN Yong

(The54thResearchInstituteofCETC,ShijiazhuangHebei050081,China)

With the cloud computing era coming,data mining methods based on cloud computing appear to be reliable and efficiency,compared to traditional centralized data mining approaches.In this paper,concepts,strengths and characteristics of cloud computing are introduced.A data mining algorithm based on MapReduce framework is presented.And experiments based on the algorithm are conducted.Experimental results show that the algorithm significantly improves data mining speed.

cloud computing;data mining;big data processing

10.3969/j.issn.1003-3106.2017.03.02

陳 勇.一種基于云計算的大數(shù)據(jù)關(guān)聯(lián)規(guī)律挖掘分析方法[J].無線電工程,2017,47(3):8-11.

2016-12-23

中國博士后科學(xué)基金資助項(xiàng)目(2015M580217)。

TP311

A

1003-3106(2017)03-0008-04