MapReduce框架下改進(jìn)Apriori算法的研究

楊健兵

(南通科技職業(yè)學(xué)院 信息與智能工程學(xué)院，江蘇 南通 226007)

MapReduce框架下改進(jìn)Apriori算法的研究

楊健兵

(南通科技職業(yè)學(xué)院 信息與智能工程學(xué)院，江蘇 南通 226007)

MapReduce是一種編程模型，這種模型編程簡(jiǎn)單，可以用于大規(guī)模數(shù)據(jù)集的并行計(jì)算。Apriori算法是一種發(fā)現(xiàn)頻繁項(xiàng)集的基本算法，通過(guò)該算法，可以產(chǎn)生關(guān)聯(lián)規(guī)則。針對(duì)Apriori的特點(diǎn)，研究了在MapReduce編程模型下，Apriori的實(shí)現(xiàn)方法。實(shí)驗(yàn)結(jié)果表明：該方法在對(duì)大數(shù)據(jù)集進(jìn)行頻繁項(xiàng)集挖掘時(shí), 可充分利用云計(jì)算的優(yōu)勢(shì), 從而能獲得更好的時(shí)效性。

Apriori；數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；MapReduce

0 引言

隨著計(jì)算機(jī)和互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，海量的數(shù)據(jù)不斷地產(chǎn)生。數(shù)據(jù)挖掘技術(shù)是通過(guò)數(shù)據(jù)挖掘算法從海量數(shù)據(jù)中找到有意義的模式或知識(shí)，這些知識(shí)對(duì)于企業(yè)和政府決策起了很大的作用。傳統(tǒng)的數(shù)據(jù)挖掘算法往往在普通的計(jì)算機(jī)上運(yùn)行，面對(duì)大量的數(shù)據(jù)時(shí)，在計(jì)算能力、處理速度、存儲(chǔ)容量、帶寬速度等多個(gè)方面往往表現(xiàn)出力不從心。云計(jì)算在計(jì)算機(jī)網(wǎng)絡(luò)的基礎(chǔ)上，將計(jì)算機(jī)龐大的處理程序通過(guò)云計(jì)算機(jī)平臺(tái)分解成小子程序，采取分而治之的方式加以解決。

在大規(guī)模數(shù)據(jù)集的并行運(yùn)算方面，MapReduce[1]是一種用得比較多的編程模型，其主要思想是Map和Reduce，它可以在程序開(kāi)發(fā)人員不會(huì)分布式并行編程的情況下，將程序運(yùn)行在分布式系統(tǒng)上。

Hadoop[2-4]是一個(gè)由Apache基金會(huì)所開(kāi)發(fā)的分布式系統(tǒng)基礎(chǔ)架構(gòu)。用戶(hù)可以在不知曉分布式文件系統(tǒng)實(shí)現(xiàn)細(xì)節(jié)的環(huán)境下開(kāi)發(fā)分布式程序。HDFS和MapReduce是 Hadoop的框架最重要的設(shè)計(jì)，HDFS為海量的數(shù)據(jù)存儲(chǔ)提供了可能，而MapReduce則為海量的數(shù)據(jù)提供了計(jì)算。通過(guò)Apache開(kāi)源社區(qū)Hadoop項(xiàng)目[5]，程序設(shè)計(jì)人員實(shí)現(xiàn)了該模型，使的該模型進(jìn)行分布式并行計(jì)算成為可能。

多種Apriori算法已經(jīng)在云計(jì)算編程模型MapReduce上實(shí)現(xiàn)。本文結(jié)合各自算法的思想與MapReduce 的運(yùn)行機(jī)理，提出MapReduce框架下Apriori算法的研究。在MapReduce的框架下，Apriori算法的使用范圍由單機(jī)擴(kuò)展到云計(jì)算平臺(tái)，極大地減少了Apriori算法的運(yùn)行時(shí)間，顯著地提高了運(yùn)行的效率。

1 MapReduce編程模型

圖1 MapReduce 運(yùn)行流程圖

MapReduce在海量數(shù)據(jù)進(jìn)行并行計(jì)算中使用廣泛，美國(guó)的Google 公司首次開(kāi)發(fā)出了該技術(shù)框架。由Map和Reduce這兩個(gè)核心步驟組成。MapReduce 接受到一個(gè)作業(yè)時(shí)，將該作業(yè)拆分成一系列任務(wù)，然后把這些任務(wù)按照一定的原則分配到不同的機(jī)器節(jié)點(diǎn)上去執(zhí)行，當(dāng)Map 處理完任務(wù)以后，將會(huì)產(chǎn)生一些中間文件，這些中間文件就成了Reduce的輸入數(shù)據(jù)。Reduce把前面若干個(gè)Map 產(chǎn)生的中間結(jié)果進(jìn)行排序匯總后一并輸出。MapReduce的數(shù)據(jù)流圖如圖1 所示。

2 Apriori算法在MapReduce框架下的實(shí)現(xiàn)

2.1 Apriori算法

Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集算法。Apriori算法使用迭代方法，該迭代方法使用逐層搜索的技術(shù)，通過(guò)k項(xiàng)集產(chǎn)生(k+1)項(xiàng)集。首先，通過(guò)掃描整個(gè)數(shù)據(jù)庫(kù)，累計(jì)每個(gè)項(xiàng)的數(shù)量，計(jì)算滿(mǎn)足最小支持度的項(xiàng)，找到頻繁1項(xiàng)集，該集合記為L(zhǎng)1項(xiàng)集。然后通過(guò)L1項(xiàng)集找到頻繁2項(xiàng)集，該集合記為L(zhǎng)2。通過(guò)使用L2找到L3，迭代下去，直到不能再找到頻繁K項(xiàng)集。

定義1 頻繁項(xiàng)集的所有非空子集一定也是頻繁的。

證明：根據(jù)定義，如果項(xiàng)集I不能滿(mǎn)足最小支持度min_sup，則I不是頻繁的，即P(I)

Apriori的核心思想是連接步和剪枝步。連接步是自連接，原則是保證前k-2項(xiàng)相同，并按照字典順序連接。剪枝步是使任一頻繁項(xiàng)集的所有非空子集也必須是頻繁的。反之，如果某個(gè)候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。Apriori算法的串行計(jì)算流程如圖2所示。

圖2 Apriori算法的串行計(jì)算流程

(1)連接步

為了找出Lk，通過(guò)將Lk-1與自身連接產(chǎn)生候選k項(xiàng)集的集合。該候選項(xiàng)集的集合為Ck。設(shè)l1和l2是Lk-1項(xiàng)集。li[j]表示li的第j項(xiàng)。Apriori算法假定事務(wù)或者項(xiàng)集中的項(xiàng)按照字典序排列，對(duì)于(k-1)項(xiàng)集li，這意味著把項(xiàng)排序，使得li[1] < li[2]< …< li[k-1]。執(zhí)行連接lk-1和lk-1，如果它們前(k-2)個(gè)項(xiàng)相同。即lk-1的元素l1和l2是可連接的。連接l1和l2產(chǎn)生的結(jié)果項(xiàng)集是{l1[1], l1[2]]，…，l1[k-1]，l2[k-1]}。

(2)剪枝步

Ck是Lk的超集，也就是說(shuō)，Ck的成員可以是也可以不是頻繁的，但所有的頻繁k項(xiàng)集都包含在Ck中。掃描數(shù)據(jù)庫(kù)，確定Ck中每個(gè)候選的計(jì)數(shù)，從而確定Lk。然后Ck可能很大，因此所涉及的計(jì)算量很大。為了壓縮Ck，可以用以下辦法使用定義1。任何非頻繁的(k-1)項(xiàng)集都不在頻繁k項(xiàng)集的子集。因此，如果一個(gè)候選k項(xiàng)集的(k-1)項(xiàng)集不在Lk-1中，則該候選也不可能是頻繁的，從而可以從Ck中刪除。

2.2 Apriori算法分析

傳統(tǒng)的Apriori算法首先通過(guò)生成頻繁1項(xiàng)集，通過(guò)頻繁1項(xiàng)集產(chǎn)生頻繁2項(xiàng)集，依次類(lèi)推。在產(chǎn)生頻繁項(xiàng)集的過(guò)程中，每產(chǎn)生一個(gè)頻繁項(xiàng)集，就需要掃描整個(gè)數(shù)據(jù)庫(kù)。但數(shù)據(jù)量比較大的時(shí)候，每次掃描數(shù)據(jù)庫(kù)需要耗費(fèi)大量的時(shí)間，這種掃描數(shù)據(jù)庫(kù)過(guò)程增加了系統(tǒng)運(yùn)行的時(shí)間，降低了系統(tǒng)效率。

2.3 改進(jìn)的Apriori算法在MapReduce模型下實(shí)現(xiàn)

輸入部分：在HDFS的文件系統(tǒng)中存儲(chǔ)事務(wù)數(shù)據(jù)庫(kù)D以及最小支持度閾值min_sup。輸出部分：L,D中的頻繁項(xiàng)集。

①L1=find_frequent_1_itemsets(D)。

②Map過(guò)程，通過(guò)L1把每條記錄轉(zhuǎn)換成行向量，行向量記住v。

③reduce過(guò)程，生成矩陣，計(jì)算候選項(xiàng)集的局部支持度。

④計(jì)算全局支持度。

⑤得到關(guān)聯(lián)規(guī)則。

該算法共分為兩個(gè)階段。在第一階段，執(zhí)行算法第①步查找候選項(xiàng)集，通過(guò)計(jì)算得到頻繁項(xiàng)集L1。然后把L1存放到數(shù)據(jù)庫(kù)中以備第二階段使用。在MapReduce第二階段，采用改進(jìn)的Apriori算法，該改進(jìn)的算法采用矩陣思想來(lái)計(jì)算候選項(xiàng)集的局部支持度。在reduce任務(wù)中，合并相同的key再生成矩陣，算出局部支持頻度。通過(guò)計(jì)算出來(lái)的局部支持頻度計(jì)算全局支持頻度，如果全局支持頻度大于最小支持頻度閾值，則把候選項(xiàng)集歸為頻繁項(xiàng)集。最后根據(jù)頻繁項(xiàng)集得到關(guān)聯(lián)規(guī)則。

2.4 算法實(shí)例分析

假定D 有9 條交易記錄，D={T100、T200、T300、T400、T500、T600、T700、T800、T900}，如表1所示，I 是項(xiàng)目的集合，且I={I1，I2，I3，I4，I5}。把D 上傳到HDFS 中，且其被分成兩個(gè)數(shù)據(jù)塊D1={ T100、T200、T300、T400、T500 }和D2={ T600、T700、T800、T900}。最小支持頻度閾值為3。

改進(jìn)的Apriori算法在執(zhí)行MapReduce第一階段任務(wù)的時(shí)候會(huì)生成頻繁1項(xiàng)集。以T100為例，它將產(chǎn)生鍵值對(duì)：、、，其他交易記錄也會(huì)產(chǎn)生相應(yīng)的鍵值對(duì)。所以我們得到I1的支持頻度為6，它大于最小支持頻度。通過(guò)類(lèi)似的方法，可以獲得L1{，，}。

表1 事務(wù)數(shù)據(jù)

改進(jìn)的Apriori算法在執(zhí)行MapReduce第二階段任務(wù)的時(shí)候，在Map階段，把表1的數(shù)據(jù)分成D1和D2兩個(gè)部分，將D1和D2分配給不通的Map任務(wù)進(jìn)行執(zhí)行。通過(guò)使用頻繁1項(xiàng)集L1把數(shù)據(jù)轉(zhuǎn)換成一個(gè)行向量v，向量中的元素為頻繁1項(xiàng)集中所對(duì)應(yīng)的元素，即I1，I2，I3。如果數(shù)據(jù)中存在該向量的元素，則對(duì)應(yīng)部分為‘1’，否則為‘0’。數(shù)據(jù)的行向量表示如表2和表3所示。

表2 數(shù)據(jù)塊D1向量表示

表3 數(shù)據(jù)塊D2向量表示

TIDI1I2I3T600011T700101T800111T900111

設(shè)表2數(shù)據(jù)塊D1向量用矩陣來(lái)表示，該矩陣為G1，表3數(shù)據(jù)塊D2向量用矩陣來(lái)表示為G2，設(shè)它們的轉(zhuǎn)置矩陣分別是G1’和G2’，則G1’和G2’分別如表4和表5所示。

表4 數(shù)據(jù)塊D1的轉(zhuǎn)置矩陣G1

表5 數(shù)據(jù)塊D2的轉(zhuǎn)置矩陣G2″

在Reduce階段，可以設(shè)置兩個(gè)Reduce任務(wù)，分別處理不同的key鍵值，具有相同key的都被送到同一Reduce任務(wù)進(jìn)行執(zhí)行。以表2為例，首先生成矩陣G1，然后再生成轉(zhuǎn)置矩陣G1′，另外一個(gè)任務(wù)也是相同的方法進(jìn)行處理。

數(shù)據(jù)塊D1的轉(zhuǎn)置矩陣G1′可以看做是由一系列行向量組成的，即I1={1,0,0,1,1}，I2={1,1,1,1,0} I3={0,0,1,0,0}，由于頻繁1項(xiàng)集為{I1，I2，I3}，所以可以計(jì)算出候選Lk(k>=2)項(xiàng)集肯定是{I1，I2，I3}這幾個(gè)頻繁1項(xiàng)集的組合。根據(jù)G1′的實(shí)際情況，它的候選項(xiàng)集分別是{I1，I2}，{I1，I3}，{I2，I3}，{I1，I2，I3}。以{I1，I2}為例，它的局部支持度為{1,0,0,1,1}&{1,1,1,1,0}=1&1+0&1+0&1+1&1+1&0=2。運(yùn)用相同的計(jì)算方法，{I1，I3}，{I2，I3}，{I1，I2，I3}的局部支持度分別是1，1，0。

對(duì)于轉(zhuǎn)置矩陣G2’可以同樣計(jì)算出{I1，I2}，{I1，I3}，{I2，I3}，{I1，I2，I3}的局部支持度為2，3，3，2。

在執(zhí)行完MapReduce第二階段任務(wù)后，把候選項(xiàng)集所對(duì)應(yīng)的局部支持度累加起來(lái)，就可以生成全局支持度計(jì)數(shù)，進(jìn)而可以生成頻繁項(xiàng)集。由于在本實(shí)例中設(shè)定的最小支持度閾值為3，根據(jù)規(guī)則可以生成頻繁項(xiàng)集為{I1}，{I2}，{I3}，{I1，I2}，{I1，I3}，{I2，I3}。

2.5 改進(jìn)的Apriori算法分析

改進(jìn)的Apriori算法在計(jì)算頻繁項(xiàng)集的過(guò)程中，對(duì)數(shù)據(jù)庫(kù)僅需要兩次掃描。同時(shí)利用MapReduce模型，可以在大量數(shù)據(jù)的情況下進(jìn)行平行計(jì)算。這種模型的使用降低了空間復(fù)雜度和時(shí)間復(fù)雜度，高效利用了平行的優(yōu)勢(shì)。特別是在數(shù)據(jù)量非常大的情況下，能夠提高系統(tǒng)效率，節(jié)省時(shí)間。

3 實(shí)驗(yàn)結(jié)果

通過(guò)實(shí)驗(yàn)，改進(jìn)的Apriori算法在MapReduce框架下實(shí)現(xiàn)效果進(jìn)行了展示和評(píng)估。

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

本實(shí)驗(yàn)在南京工業(yè)大學(xué)云平臺(tái)進(jìn)行實(shí)驗(yàn)。該平臺(tái)由一系列IBM服務(wù)器構(gòu)建。其中管理節(jié)點(diǎn)1個(gè)，計(jì)算機(jī)節(jié)點(diǎn)16個(gè)，網(wǎng)絡(luò)采用萬(wàn)兆網(wǎng)絡(luò)，操作系統(tǒng)采用RedHat Linux。在硬件配置上，每一個(gè)節(jié)點(diǎn)的CPU 采用Intel Xeon 2.0GCPU，8G內(nèi)存，100G硬盤(pán)，軟件配置Hadoop 。

3.2 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)來(lái)自于某大型超市數(shù)據(jù)庫(kù)交易記錄信息，在進(jìn)行數(shù)據(jù)分析之前，我們對(duì)數(shù)據(jù)進(jìn)行了預(yù)處理，包括數(shù)據(jù)的清理、集成、變換等。為了便于實(shí)驗(yàn)，對(duì)這些文件進(jìn)行了多次備份并進(jìn)行了合并以得到不同大小的文件。數(shù)據(jù)集規(guī)模大小如圖表6所示。

表6 預(yù)處理后數(shù)據(jù)集

3.3 實(shí)驗(yàn)結(jié)果

圖3 兩種不同算法數(shù)據(jù)分析圖

在處理大數(shù)據(jù)的過(guò)程中，在MapReduce框架下改進(jìn)Apriori算法所使用的時(shí)間明顯要大于在MapReduce框架下改進(jìn)的Apriori算法。并且從圖3中可以看出，在數(shù)據(jù)量由10百萬(wàn)條增加到40百萬(wàn)條的時(shí)候，傳統(tǒng)的Apriori算法用時(shí)明顯增加，而MapReduce框架下改進(jìn)的Apriori算法所消耗的時(shí)間增加不是太多，這說(shuō)明MapReduce框架下改進(jìn)的Apriori算法在處理大規(guī)模數(shù)據(jù)集的時(shí)候擁有更大的加速比，更適合處理大量的數(shù)據(jù)。

4 結(jié)語(yǔ)

隨著互聯(lián)網(wǎng)業(yè)務(wù)的不斷發(fā)展，每天都有大量的數(shù)據(jù)產(chǎn)生，對(duì)于產(chǎn)生的數(shù)據(jù)用數(shù)據(jù)挖掘的方法對(duì)它進(jìn)行分析并提取有益的信息已經(jīng)成為大家關(guān)注的對(duì)象。在源源不斷的數(shù)據(jù)產(chǎn)生以后，我們可以通過(guò)在MapReduce框架下改進(jìn)的Apriori算法進(jìn)行關(guān)聯(lián)規(guī)則分析，從而產(chǎn)生對(duì)現(xiàn)實(shí)有意義的知識(shí)。

本文提出了一個(gè)思路，在面對(duì)大量數(shù)據(jù)的時(shí)候如何使用MapReduce框架去處理這些數(shù)據(jù)。實(shí)驗(yàn)表明，該解決方法在面對(duì)大量數(shù)據(jù)的時(shí)候可以極大地提高運(yùn)行速度、縮短運(yùn)行時(shí)間、提高運(yùn)行效率。

[1] Dean j,Ghemawat S. MapReduce simplified data processing on large cluster[J].Communication of the ACM,2006,51(1):107-113.

[2] Dean Jeffrey,Ghemawat Sanjay.Mapreduce:simplified data processing on large clusters[J]．Communications of the ACM,2005,51(1):107-113.

[3] 劉騫，陳明．基于改進(jìn)的Map/Reduce及模式空間劃分的數(shù)據(jù)挖掘[J]．微電子學(xué)與計(jì)算機(jī)，2011(08)：140-142.

[4] 李建江，崔健，王聃，等.Mapreduce并行編程模型研究綜述[J].電子學(xué)報(bào)，2011(11)：2635-2642.

[5] Apache Hadoop. Hadoop[EB/OL].[2011-02-15].http://hadoop.apache.org.

責(zé)任編輯：程艷艷

Research of Improved Apriori Algorithm under MapReduce Framework

YANG Jianbing

(Department of Information and Intelligence Engineering,Nantong Vocational College of Science and Technology, Nantong 226007, China)

MapReduce is a programming model, which is simple, can be used for parallel computing of large-scale data sets. Apriori algorithm is a basic algorithm to discover frequent item sets, and association rules are generated from it. In view of the characteristics of Apriori, this paper analyzes the realization method of Apriori under MapReduce programming model. Experimental results show that the proposed method can make full use of the advantages of cloud computing in the frequent item sets mining on large data sets, having better effectiveness.

Apriori; data mining; association rule; MapReduce

2016-09-02

楊健兵(1976-)，江蘇海門(mén)人，講師，碩士，主要從事數(shù)據(jù)挖掘和人工神經(jīng)網(wǎng)絡(luò)方面研究。

TP301

A

1009-3907(2016)08-0040-04