王嶸冰 徐紅艷 魏蓮蓮

（遼寧大學(xué)信息學(xué)院 沈陽 110036）

1 引言

隨著大數(shù)據(jù)時(shí)代的來臨，在科學(xué)計(jì)算、商業(yè)計(jì)算等諸多領(lǐng)域蘊(yùn)含著海量數(shù)據(jù)［1］。從這些海量數(shù)據(jù)中挖掘出其潛在價(jià)值已經(jīng)成為當(dāng)今學(xué)術(shù)界關(guān)注的熱點(diǎn)。在大數(shù)據(jù)處理方面，Google提出的Ma?pReduce框架［2］以其適用于大數(shù)據(jù)計(jì)算而成為大數(shù)據(jù)環(huán)境的關(guān)鍵計(jì)算模型。與常規(guī)分布式算法相比較，MapReduce的優(yōu)勢(shì)如下：

1）并行化程度高：在大數(shù)據(jù)處理過程中使用集群技術(shù)，以達(dá)到常規(guī)分布式算法無法實(shí)現(xiàn)的高效率。

2）經(jīng)濟(jì)性：普通的PC機(jī)可作為集群節(jié)點(diǎn)用于處理數(shù)據(jù)。

3）容錯(cuò)性好：MapReduce使用多副本冗余機(jī)制。

4）擴(kuò)展性強(qiáng)：可用于PB級(jí)數(shù)據(jù)的處理，而且可以根據(jù)實(shí)際需要來擴(kuò)展集群節(jié)點(diǎn)。

因此，將分布式數(shù)據(jù)挖掘技術(shù)與MapReduce模式相融合是大數(shù)據(jù)挖掘的主要研究方向［3］。

關(guān)聯(lián)規(guī)則挖掘算法FP-growth，其思想是分而治之［4］，相較于需多次掃描數(shù)據(jù)庫、產(chǎn)生大量候選集的Apriori算法［5］，在分布式環(huán)境中使用更廣泛，但弊端是局部站點(diǎn)通信量較大。Chen等［6］為解決此問題，采用垂直模式樹存儲(chǔ)數(shù)據(jù)，提出了高性能并行算法HPFP，克服了原FP-growth算法通信大的弊端。徐杰等［7］采用了數(shù)據(jù)并行和任務(wù)并行來提高挖掘效率，提出了基于垂直FP樹的并行頻繁項(xiàng)集挖掘算法。馮勇等［8］提出分布關(guān)聯(lián)規(guī)則挖掘算法VFP-LBDM，通過提高站點(diǎn)的負(fù)載均衡程度來縮小節(jié)點(diǎn)執(zhí)行時(shí)間差異，提高了整體的執(zhí)行效率。以上算法在分布式環(huán)境中一定程度上提高了算法效率，但在大數(shù)據(jù)環(huán)境中，并行化程度遠(yuǎn)不及MapRe?duce模式。

針對(duì)分布式垂直FP-growth算法在大數(shù)據(jù)環(huán)境下CPU、內(nèi)存、I/O開銷大和計(jì)算效率低的問題，本文提出基于MapReduce的垂直FP-growth挖掘算法（Vertical FP-growth Mining Algorithm Based on Ma?pReduce，MR-VFP），通過將分布式垂直FP-growth算法與MapReduce模式相融合，實(shí)現(xiàn)高度并行化計(jì)算以減少硬件資源的消耗。

2 MR-VFP算法框架

2.1 算法思想

垂直FP-growth算法是一個(gè)基于全局樹結(jié)構(gòu)的關(guān)聯(lián)規(guī)則算法［11］，它不僅繼承了FP-growth算法分而治之的優(yōu)點(diǎn)，同時(shí)又具有以垂直壓縮樹結(jié)構(gòu)減少局部合并過程通信消費(fèi)的優(yōu)勢(shì)［12］。在每次迭代過程中，需要對(duì)每個(gè)局部事務(wù)數(shù)據(jù)項(xiàng)做統(tǒng)計(jì)。在數(shù)據(jù)量較大的環(huán)境中，節(jié)點(diǎn)能力更是有限，無法承擔(dān)計(jì)算大規(guī)模數(shù)據(jù)的任務(wù)。MapReduce模型是典型的IPSS計(jì)算抽象［13］，具有高度并行化計(jì)算集群上大規(guī)模數(shù)據(jù)的特點(diǎn)，而垂直FP-growth算法挖掘的事務(wù)數(shù)據(jù)庫中的每條記錄都是相互獨(dú)立的，因此可以利用MapReduce模型將事務(wù)數(shù)據(jù)庫分割成若干塊，Map階段對(duì)每個(gè)事務(wù)塊進(jìn)行預(yù)處理，然后shuffle根據(jù)項(xiàng)的不同執(zhí)行分組，combine階段局部合并相同項(xiàng)的記錄，Reduce階段經(jīng)全局合并輸出最終結(jié)果，形成全局頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則。MapReduce模型通過并行化集群計(jì)算，使挖掘效率得到極大提高。綜上分析，本文提出了一種基于MapReduce的垂直FP-growth算法——MR-VFP算法。

2.2 算法工作機(jī)理

MR-VFP算法分為數(shù)據(jù)劃分、預(yù)剪枝、VFP-tree序列化、生成全局頻繁樹四個(gè)部分。

1）數(shù)據(jù)劃分，頻繁一項(xiàng)集生成。該步驟的主要任務(wù)是將事務(wù)數(shù)據(jù)劃分到各個(gè)處理機(jī)上。各站點(diǎn)并行MapReduce操作，計(jì)算出頻繁項(xiàng)，其過程如圖1。

圖1 MapReduce處理數(shù)據(jù)項(xiàng)過程

在數(shù)據(jù)劃分階段，局部站點(diǎn)執(zhí)行map操作并行挖掘局部數(shù)據(jù)庫，統(tǒng)計(jì)出局部頻繁項(xiàng)，以＜itemid，itemcount＞格式輸出，然后reduce操作合并具有相同itemid的項(xiàng)，得出全局頻繁項(xiàng)。

2）預(yù)剪枝。中心站點(diǎn)的預(yù)剪枝將根據(jù)各局部節(jié)點(diǎn)返回的頻繁項(xiàng)集進(jìn)行。各站點(diǎn)預(yù)先刪除父節(jié)點(diǎn)為非頻繁項(xiàng)的分支，不再收集該項(xiàng)的支持?jǐn)?shù)信息，然后構(gòu)造局部垂直模式樹，從而有效減少通信量。

3）VFP-tree序列化。對(duì)局部垂直模式樹使用深度優(yōu)先遍歷樹，每個(gè)節(jié)點(diǎn)的輸出格式為：項(xiàng)與該項(xiàng)所對(duì)應(yīng)的計(jì)數(shù)。節(jié)點(diǎn)的輸出分為以下三種情況：（1）該節(jié)點(diǎn)有子節(jié)點(diǎn)輸出“-”；（2）沒有子節(jié)點(diǎn)有兄弟節(jié)點(diǎn)輸出“|”；（3）沒有兄弟節(jié)點(diǎn)輸出“+”，并返回該節(jié)點(diǎn)的上一層繼續(xù)掃描。用符號(hào)“-”“|”“+”表示樹節(jié)點(diǎn)之間的關(guān)系，以減少站點(diǎn)間的通信開銷。

4）生成全局頻繁樹。本文選取的規(guī)則只由根節(jié)點(diǎn)項(xiàng)出發(fā)而生成以避免規(guī)則冗余。在各局部站點(diǎn)上執(zhí)行MapReduce操作，各站點(diǎn)按照任務(wù)分配表，將生成的規(guī)則發(fā)送給相應(yīng)站點(diǎn)，以＜itemid，itemseq＞格式將以Ii開頭的序列合并到指定的站點(diǎn)，生成全局頻繁模式樹，最終輸出全局頻繁森林，其過程如圖2。

圖2 MapReduce處理局部頻繁樹序列過程

3 MR-VFP算法描述與效率分析

3.1 算法描述

MR-VFP算法按照MapReduce框架的結(jié)構(gòu)，劃分為頻繁項(xiàng)集構(gòu)建算法、全局頻繁模式樹構(gòu)建算法兩部分。

算法1.MapReduce框架下頻繁項(xiàng)集構(gòu)建算法

輸入：數(shù)據(jù)集D

輸出：全局頻繁項(xiàng)集

Begin

Step1：m個(gè)mappers并行地讀取輸入的數(shù)據(jù)切片，對(duì)map函數(shù)讀取的某項(xiàng)itemid，依次進(jìn)行下述操作：

IF（項(xiàng)item不為空）

則累計(jì)項(xiàng)item出現(xiàn)的次數(shù)，輸出＜itemid，temcount＞鍵值對(duì)，其中，itemid 指不同的itemcount為常量；ELSE忽略此對(duì)象

Step2：所有key為相同itemid的值集將被一個(gè)reducer接收，并由reduce函數(shù)對(duì)itemcount值集進(jìn)行累加，形成一個(gè)關(guān)于某項(xiàng)的局部支持?jǐn)?shù)；

按照下面的步驟構(gòu)建全局項(xiàng)集：

Step3：m個(gè)mappers采用并行的方式將輸入的數(shù)據(jù)切片讀入，統(tǒng)計(jì)map函數(shù)讀取的每個(gè)項(xiàng)itemid，輸出鍵值對(duì)＜itemid，value＜itemid，itemcount＞＞；

Step4：r個(gè)reducers將所有劃分到該reducer分區(qū)的對(duì)象子集接收并執(zhí)行下面的操作步驟：1：將對(duì)象子集中每個(gè)元組itemid插入到列表L中；2：對(duì)列表L按itemcount值進(jìn)行排序，形成全局項(xiàng)集；END

算法2.MapReduce框架下全局頻繁模式樹構(gòu)建算法

輸入：局部樹的序列

輸出：全局頻繁模式森林

Begin

Step1：m個(gè)mappers并行地讀取輸入的局部樹序列，對(duì)map函數(shù)讀取的某項(xiàng)itemid，依次進(jìn)行下述操作：

IF（項(xiàng)item不為空）

則輸出＜itemid，itemseq＞鍵值對(duì)，其中，itemid指

同的項(xiàng)，itemseq為以itemid為根節(jié)點(diǎn)的局部樹；

ELSE忽略此對(duì)象

Step2：一個(gè)reducer接收所有key為相同itemid的序列。reduce函數(shù)對(duì)itemseq進(jìn)行合并，形成一個(gè)關(guān)于某項(xiàng)的頻繁模式樹；

按照下述操作步驟構(gòu)建全局頻繁模式森林：

Step3：m個(gè)mappers將輸入的數(shù)據(jù)切片并行讀取，統(tǒng)計(jì)map函數(shù)讀取的每個(gè)項(xiàng)itemid，輸出鍵值對(duì)＜itemid，value＜itemid，itemseq＞＞；

Step4：r個(gè)reducers接收所有劃分到該reducer分區(qū)的對(duì)象子集并執(zhí)行下屬操作步驟：

1：將對(duì)象子集中每個(gè)頻繁模式樹進(jìn)行合并，形成全局頻繁模式樹；

2：對(duì)頻繁樹按根節(jié)點(diǎn)itemcount進(jìn)行排序，形成全局頻繁模式森林；

END

3.2 算法時(shí)間復(fù)雜度分析

本算法開銷主要包括：統(tǒng)計(jì)項(xiàng)的支持?jǐn)?shù)從而得到每個(gè)項(xiàng)的全局支持?jǐn)?shù)，以及在局部樹合并成全局頻繁模式樹的兩個(gè)過程。如果總共有m1條事務(wù)記錄，平均每條記錄包含n1個(gè)數(shù)據(jù)項(xiàng)，參與計(jì)算的節(jié)點(diǎn)為k個(gè)，每個(gè)節(jié)點(diǎn)上可以同時(shí)處理 p個(gè)Map、Re?duce。整個(gè)計(jì)算頻繁項(xiàng)集的過程需要t1次迭代達(dá)到全局結(jié)果，則數(shù)據(jù)劃分階段，時(shí)間復(fù)雜度為同理，在全局頻繁森林生成階段，復(fù)，其中n2指數(shù)據(jù)項(xiàng)個(gè)數(shù)，每個(gè)數(shù)據(jù)項(xiàng)平均有m2個(gè)局部樹，迭代次數(shù)為t2。由此可知，當(dāng)整個(gè)集群越大，一次所能處理的Map和Reduce數(shù)越多，該算法的時(shí)間復(fù)雜度就越低、效率越高。

4 實(shí)驗(yàn)與對(duì)比分析

4.1 實(shí)驗(yàn)環(huán)境

Apache的Hadoop是MapReduce的開源實(shí)現(xiàn)。本文實(shí)驗(yàn)采用Hadoop平臺(tái)0.20.2，每個(gè)節(jié)點(diǎn)上可并行運(yùn)行的Mapper數(shù)和Reducer數(shù)設(shè)為5，其它采用默認(rèn)設(shè)置。

為了進(jìn)行對(duì)比實(shí)驗(yàn)，本文使用文獻(xiàn)13中使用的環(huán)境：Hadoop集群包括1臺(tái)主控節(jié)點(diǎn)和7個(gè)計(jì)算節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)配置為2quad-core 2.4GHZ CPU，16GB內(nèi)存和167GB的本地存儲(chǔ)磁盤，操作系統(tǒng)為Red Hat EnterpriseLinux 5.5，節(jié)點(diǎn)間通過 10-Giga?bit Infiniband網(wǎng)絡(luò)互聯(lián)。

4.2 算法的效率對(duì)比

為驗(yàn)證本文所提算法的性能，選取目前在垂直頻繁樹挖掘算法中應(yīng)用較為廣泛的兩種算法作為對(duì)比：并行頻繁項(xiàng)集挖掘算法DVFP算法采用垂直頻繁樹結(jié)構(gòu)，通過計(jì)算并行和通信并行，在分布式環(huán)境中挖掘效率較高；基于垂直頻繁模式樹帶有負(fù)載均衡的挖掘算法VFP-LBDM算法是改進(jìn)的垂直挖掘算法，根據(jù)節(jié)點(diǎn)的CPU、內(nèi)存、帶寬資源進(jìn)行挖掘任務(wù)劃分，從負(fù)載均衡的角度提高運(yùn)行效率。本文對(duì)此兩種算法重新進(jìn)行了實(shí)現(xiàn)，在本文實(shí)驗(yàn)環(huán)境下與本文所提算法進(jìn)行實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)數(shù)據(jù)集為UCI的 Poker Hand［14］。

1）不同支持度下執(zhí)行時(shí)間的對(duì)比。

三個(gè)算法分別計(jì)算4000000條記錄。支持度小時(shí)，例如支持度為5%時(shí)，預(yù)剪去的非頻繁樹少，全局頻繁項(xiàng)集較大，因此每個(gè)算法的執(zhí)行時(shí)間比較多；隨著支持度變大，頻繁項(xiàng)集變小，挖掘速率會(huì)加快。MR-VFP算法由于并行化程度高，因此整體執(zhí)行效率比較高，三種算法執(zhí)行時(shí)間的對(duì)比如圖3所示。

圖3 三種算法在不同支持度下執(zhí)行時(shí)間的對(duì)比

2）不同數(shù)據(jù)量下執(zhí)行時(shí)間的對(duì)比。

采用數(shù)據(jù)復(fù)制的方法，將數(shù)據(jù)集擴(kuò)大至200MB、400MB、600MB、800MB、1000MB，在節(jié)點(diǎn)數(shù)為16的條件下進(jìn)行實(shí)驗(yàn)。隨著數(shù)據(jù)規(guī)模增大，MR-VFP算法的MapReduce模式優(yōu)勢(shì)越明顯。三種算法執(zhí)行時(shí)間的對(duì)比如圖4所示。

圖4 三種算法在不同數(shù)據(jù)量下執(zhí)行時(shí)間的對(duì)比

3）并行化水平對(duì)比

本文使用加速比作為體現(xiàn)算法并行化水平的指標(biāo)。隨著節(jié)點(diǎn)數(shù)的增加，MR-VFP算法在時(shí)間的減少上具有很好的優(yōu)勢(shì)，從而說明本算法具有高效并行性。三種算法并行化水平的對(duì)比如圖5所示。

4）可擴(kuò)展性對(duì)比

總數(shù)據(jù)量固定的情況下，隨著節(jié)點(diǎn)數(shù)的增加，局部節(jié)點(diǎn)的任務(wù)量減少，局部節(jié)點(diǎn)的有效功率會(huì)減少（但因節(jié)點(diǎn)數(shù)增多，整體的效率是升高的），所以節(jié)點(diǎn)平均效率曲線呈下降趨勢(shì)。MR-VFP算法是基于MapReduce模式，節(jié)點(diǎn)間呈串行和并行協(xié)同有序運(yùn)行，因此節(jié)點(diǎn)平均效率要比另兩種算法的節(jié)點(diǎn)無序運(yùn)行效率高。在較大數(shù)據(jù)集上，MR-VFP算法的節(jié)點(diǎn)平均效率曲線較為平滑，不會(huì)因節(jié)點(diǎn)增加而使性能降低得過快。因此，本文所提算法對(duì)于集群計(jì)算具有良好的可擴(kuò)展性，三種算法可擴(kuò)展性的對(duì)比如圖6所示。

圖6 三種算法節(jié)點(diǎn)平均效率對(duì)比

5 結(jié)語

大數(shù)據(jù)環(huán)境下，為使傳統(tǒng)數(shù)據(jù)挖掘算法發(fā)揮功效，本文提出一種基于MapReduce的垂直FP-growth挖掘算法。該算法先用Map函數(shù)對(duì)事務(wù)數(shù)據(jù)庫數(shù)據(jù)項(xiàng)進(jìn)行解析分塊；然后用Reduce函數(shù)計(jì)算頻繁項(xiàng)的支持度和合并全局頻繁樹，從而并行化垂直FP-growth算法中間迭代過程；最后通過計(jì)算全局頻繁項(xiàng)，得到準(zhǔn)確的頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則。經(jīng)實(shí)驗(yàn)證明，所提算法在大數(shù)據(jù)處理方面不僅保持原有垂直FP-growth算法挖掘準(zhǔn)確性，而且具有較高的運(yùn)行效率和較好的集群性能。