戴偉敏

(陽(yáng)光學(xué)院信息工程學(xué)院)

0 引言

關(guān)聯(lián)規(guī)則的挖掘可以發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系，其核心是通過(guò)統(tǒng)計(jì)數(shù)據(jù)項(xiàng)獲得頻繁項(xiàng)集，用于發(fā)現(xiàn)交易數(shù)據(jù)庫(kù)中不同項(xiàng)目集之間的關(guān)系[1].傳統(tǒng)的關(guān)聯(lián)規(guī)則主要有Apriori算法、FP-Growth算法、抽樣算法等，它們可實(shí)現(xiàn)可靠準(zhǔn)確的處理小規(guī)模數(shù)據(jù)，但隨著社會(huì)互聯(lián)網(wǎng)技術(shù)、計(jì)算機(jī)技術(shù)和數(shù)據(jù)庫(kù)技術(shù)的迅速發(fā)展，數(shù)據(jù)呈爆炸式上升，傳統(tǒng)的關(guān)聯(lián)規(guī)則算法在面對(duì)大數(shù)據(jù)時(shí)候，無(wú)論在運(yùn)算能力還是并行化效率方面都難以滿足人們的要求.云計(jì)算平臺(tái)Hadoop[2-3]是一個(gè)開源的、可以更容易開發(fā)和并行處理大規(guī)模數(shù)據(jù)的分布式計(jì)算平臺(tái)，主要用于海量數(shù)據(jù)的存儲(chǔ)和分布式計(jì)算，其對(duì)海量數(shù)據(jù)的存儲(chǔ)能力和并行計(jì)算能力提供了有利條件，為解決海量數(shù)據(jù)挖掘問(wèn)題提供了一種新的解決方案.Hadoop平臺(tái)是以HDFS和MapReduce為核心，HDFS是分布式文件系統(tǒng)，MapReduce是一種簡(jiǎn)單的編程模式，采用分布式的并行方式處理海量數(shù)據(jù)，無(wú)需考慮數(shù)據(jù)的劃分、分配以及調(diào)度等問(wèn)題，同時(shí)還能處理集群中節(jié)點(diǎn)失效，具有適用性強(qiáng)、資源消耗小、方便連接和可擴(kuò)展性好等優(yōu)點(diǎn).

該文基于FP-Growth算法結(jié)合MapReduce編程模型進(jìn)行改進(jìn)，使其能高效運(yùn)行于Hadoop平臺(tái)，以解決Apriori算法在單機(jī)環(huán)境下運(yùn)行效率低下的問(wèn)題.

1 算法描述

1.1 關(guān)聯(lián)規(guī)則描述

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的一個(gè)重要分支.根據(jù)韓家煒等觀點(diǎn)，關(guān)聯(lián)規(guī)則定義為：假設(shè)I= {I1,I2,…,Im}是項(xiàng)的集合.給定一個(gè)事務(wù)數(shù)據(jù)庫(kù)D，其中每個(gè)事務(wù)t是I的非空集合，即每一個(gè)交易都與一個(gè)唯一的標(biāo)識(shí)符TID對(duì)應(yīng).關(guān)聯(lián)規(guī)則在D中的支持度定義為：

支持度support (A=>B)=P：表示D中同時(shí)包含A和B的百分比，即概率.

關(guān)聯(lián)規(guī)則在D中的置信度定義為：

置信度confidence(A=>B)=( support/support(A)：表示D中已經(jīng)包含A的情況下，包含B的百分比，即條件概率.

對(duì)于給定的一個(gè)事務(wù)數(shù)據(jù)庫(kù)D，關(guān)聯(lián)規(guī)則挖掘問(wèn)題是根據(jù)事務(wù)設(shè)定好的最小支持度和最小置信度來(lái)發(fā)現(xiàn)強(qiáng)關(guān)聯(lián)規(guī)則的過(guò)程.即對(duì)給定的支持度閾值min_sup、置信度閾值min_con，找到所有滿足下列條件的關(guān)聯(lián)規(guī)則：支持度>=min_sup 和置信度>=min_con，因而，對(duì)關(guān)聯(lián)規(guī)則挖掘需經(jīng)過(guò)以下兩個(gè)步驟：

(1)頻繁項(xiàng)集產(chǎn)生：從事務(wù)數(shù)據(jù)庫(kù)D中發(fā)現(xiàn)滿足最小支持度閾值的所有項(xiàng)集.

(2)規(guī)則的產(chǎn)生：從上一步發(fā)現(xiàn)的頻繁項(xiàng)集中提取出所有高于置信度的規(guī)則，這些規(guī)則稱作強(qiáng)規(guī)則.

1.2 傳統(tǒng)的Apriori算法

Apriori算法是挖掘產(chǎn)生布爾關(guān)聯(lián)規(guī)則所需的頻繁項(xiàng)集的基本算法，也是最著名的關(guān)聯(lián)規(guī)則挖掘算法之一.Apriori算法是采用逐層搜索的迭代方法，利用K-1項(xiàng)集來(lái)探索K項(xiàng)集，在挖掘過(guò)程中采用了2條重要性質(zhì)：

性質(zhì)1：若項(xiàng)目集I是事務(wù)數(shù)據(jù)庫(kù)D中的頻繁項(xiàng)目集，則其所有的非空子集在D中一定是頻繁項(xiàng)集.

性質(zhì)2：若項(xiàng)目集I是非頻繁項(xiàng)集，則其所有超集都是非頻繁項(xiàng)目集.

Apriori算法主要挖掘頻繁項(xiàng)集過(guò)程如下：

(1)連接步：頻繁K項(xiàng)集的集合是由所有的頻繁K-1項(xiàng)集的集合Lk-1與自身連接產(chǎn)生候選K項(xiàng)集的集合Ck.

(2)剪枝步：掃描事務(wù)數(shù)據(jù)庫(kù)D，確定Ck中每個(gè)候選的計(jì)數(shù)，再判斷是否小于最小支持度min_sup，如果是，則將其從Ck中刪除，否則，認(rèn)為該候選集合是頻繁的.

1.3 MapReduce簡(jiǎn)介

MapReduce[6-7]是面向大數(shù)據(jù)并行處理的計(jì)算模型、框架和平臺(tái)，采用分布式的并行計(jì)算的簡(jiǎn)單編程模式， 在運(yùn)行一個(gè)mapreduce計(jì)算任務(wù)時(shí)候，任務(wù)過(guò)程被分為兩個(gè)階段：map階段和reduce階段，每個(gè)階段都是用鍵值對(duì)(key/value)作為輸入(input)和輸出(output).因此程序員只需編寫map()函數(shù)和reduce()函數(shù).MapReduce執(zhí)行過(guò)程如圖1所示.

圖 1 MapReduce執(zhí)行過(guò)程

1.4 D_Apriori算法并行化設(shè)計(jì)

1.4.1 D_Apriori算法的壓縮布爾矩陣表示

Apriori算法在進(jìn)行關(guān)聯(lián)規(guī)則挖掘中，需要多趟掃描數(shù)據(jù)庫(kù)，并在迭代過(guò)程中產(chǎn)生大量的候選項(xiàng)集，耗費(fèi)大量的I/O時(shí)間，當(dāng)數(shù)據(jù)量稍大時(shí)，Apriori算法的執(zhí)行效率很低.因而本文提出一種基于矩陣[8]的關(guān)聯(lián)規(guī)則算法D_Apriori，再結(jié)合MapReduce對(duì)該算法進(jìn)行并行化改進(jìn).

改進(jìn)后的D_Apriori算法在挖掘頻繁項(xiàng)集時(shí)只需掃描一次事務(wù)數(shù)據(jù)庫(kù)D，能將事務(wù)數(shù)據(jù)庫(kù)轉(zhuǎn)換為矩陣，矩陣中每一行的向量表示事務(wù)數(shù)據(jù)庫(kù)D中的一個(gè)事務(wù)，每列對(duì)應(yīng)事務(wù)中的項(xiàng)，矩陣中每個(gè)元素用“0”或“1”表示，下次就可以直接利用矩陣中的信息進(jìn)行挖掘，不需要掃描數(shù)據(jù)事務(wù)庫(kù).矩陣中每一行表示一個(gè)事務(wù)，每一行中“1”的個(gè)數(shù)表示事務(wù)的長(zhǎng)度，在事務(wù)矩陣中增加一列記錄各事務(wù)的長(zhǎng)度，可將不滿足升序要求的行刪除，降低矩陣的行維度，矩陣中的每列中“1”個(gè)數(shù)為項(xiàng)目在事務(wù)數(shù)據(jù)庫(kù)中的支持度計(jì)數(shù)，通過(guò)給定的最小支持度，保留頻繁的項(xiàng)目即頻繁1項(xiàng)集，將非頻繁的項(xiàng)目所對(duì)應(yīng)的列刪除，降低矩陣的列維度.

D_Apriori算法中計(jì)算支持度和刪除非頻繁項(xiàng)目所在的列算法描述如下：

輸入：事務(wù)數(shù)據(jù)庫(kù)D，最小支持度min_sup

輸出：事務(wù)數(shù)據(jù)庫(kù)D中頻繁項(xiàng)目集的集合L

For(q=1;q

{

for(p=0;p

{ /*每項(xiàng)的支持度計(jì)數(shù)*/

sum=sum+M[p][q];

}

If sum<|D|.min_sup

Remove the q colume; /*刪除非頻繁項(xiàng)目所在的列*/

}

D_Apriori算法中刪除長(zhǎng)度小于k+1的事務(wù)所在的行的算法描述如下：

For(k=1;|Lk|p>=k+1;k++)

{

For(p=0;p

{

If M[p][0]

Remove the p row;/*刪除長(zhǎng)度小于k+1的事務(wù)所在的行*/

}

For each X Lk do

L1中項(xiàng)目標(biāo)識(shí)號(hào)大于X中的最大標(biāo)識(shí)號(hào)的項(xiàng)目與X進(jìn)行連接，得到C

For each k-subset sc of C

If sc Lk {delete C;}

Else Ck+1=Ck+1 {C}

For each X C k+1 do

列向量間進(jìn)行與運(yùn)算計(jì)算得到支持度計(jì)數(shù)X.count

{ if X.count |D|.min_sup

Lk+1={X Ck+1|X.count}

}

|Lk+1|=0;

For each X Lk+1 do

|Lk+1|=|Lk+1|+1;/*統(tǒng)計(jì)Lk+1中項(xiàng)目集的個(gè)數(shù)*/

L= Lk

}

1.4.2 D_Apriori算法的并行化設(shè)計(jì)

并行化的主要思想，將要處理的數(shù)據(jù)集均勻地劃分成n塊，每個(gè)節(jié)點(diǎn)采用D_Apriori算法發(fā)現(xiàn)各自的數(shù)據(jù)塊的局部頻繁項(xiàng)集，再合并各局部頻繁項(xiàng)集，就得到全局頻繁項(xiàng)集.

D_Apriori算法并行化改進(jìn)過(guò)程如下：

(1)將事務(wù)數(shù)據(jù)庫(kù)D轉(zhuǎn)化為事務(wù)矩陣；

(2)將事務(wù)矩陣劃分成n塊，將n個(gè)數(shù)據(jù)塊分配給m個(gè)節(jié)點(diǎn)；

(3)每個(gè)節(jié)點(diǎn)使用串行的D_Apriori算法掃描數(shù)據(jù)塊，得到各個(gè)數(shù)據(jù)塊上所有頻繁項(xiàng)集的集合，再合并各局部頻繁項(xiàng)集，就得到全局候選項(xiàng)集；

(4)將事務(wù)矩陣劃分成n’個(gè)數(shù)據(jù)塊，并分配到m’個(gè)節(jié)點(diǎn)，同時(shí)將全局候選項(xiàng)目集發(fā)送到各個(gè)節(jié)點(diǎn)中；

(5)各個(gè)節(jié)點(diǎn)掃描所分配到的數(shù)據(jù)，并在數(shù)據(jù)塊上計(jì)算候選項(xiàng)集的支持度計(jì)數(shù).用分區(qū)函數(shù)將m’個(gè)節(jié)點(diǎn)輸出的結(jié)果分配到m”個(gè)節(jié)點(diǎn)上；

(6)m”個(gè)節(jié)點(diǎn)將相同項(xiàng)目集的支持度進(jìn)行計(jì)數(shù)累加，并將得到的各個(gè)項(xiàng)目集的支持度與最小支持度s進(jìn)行比較，得到局部頻繁項(xiàng)集的集合，最后將m”個(gè)節(jié)點(diǎn)的結(jié)果合并，從而得到所有頻繁項(xiàng)集的集合.

D_Apriori算法并行化后只需要掃描一次事務(wù)數(shù)據(jù)庫(kù)，利用MapReduce將數(shù)據(jù)分配到各個(gè)節(jié)點(diǎn)上并行計(jì)算，實(shí)現(xiàn)了將原本由單機(jī)處理的計(jì)算任務(wù)分配到多個(gè)節(jié)點(diǎn)上并行處理，簡(jiǎn)化了生成候選項(xiàng)的連接步驟，同時(shí)在計(jì)算的過(guò)程中對(duì)事務(wù)進(jìn)行壓縮，提高了運(yùn)算速度，改善了算法的性能，D_Apriori算法未并行化前，時(shí)間復(fù)雜度為O(m1k.n)，假設(shè)每個(gè)節(jié)點(diǎn)可以處理w個(gè)計(jì)算任務(wù)，則并行化改進(jìn)后的D_Apriori算法的時(shí)間復(fù)雜度為O(m1k.n/w).

2 仿真實(shí)驗(yàn)及分析

2.1 Hadoop平臺(tái)實(shí)驗(yàn)環(huán)境搭建

實(shí)驗(yàn)環(huán)境采用9個(gè)Hadoop集群節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)，采用主從式架構(gòu)，其中一臺(tái)作為NameNode主節(jié)點(diǎn)和JobTracker主節(jié)點(diǎn)，其余的8臺(tái)作為DataNode從節(jié)點(diǎn)和TaskTracker從節(jié)點(diǎn)，操作系統(tǒng)采用Ubuntu12.04，JDK版本為1.7，Hadoop版本采用Hadoop-1.2.1.

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

該實(shí)驗(yàn)采用的數(shù)據(jù)源為來(lái)自某超算中心某大型超市購(gòu)物的數(shù)據(jù)，大小約為3GB，Map節(jié)點(diǎn)數(shù)分別為2、3、4、5、6、7、8個(gè)節(jié)點(diǎn)的Hadoop集群模式，為了進(jìn)一步比較串行并行算法的優(yōu)勢(shì)，選取結(jié)點(diǎn)數(shù)為4的實(shí)驗(yàn)數(shù)據(jù)作為并行算法的代表，其中CS1含有較小的數(shù)據(jù)量，所耗的資源相對(duì)小，并行化的效果不明顯，因而該實(shí)驗(yàn)采用CS2～CS5作為并行算法的實(shí)驗(yàn)數(shù)據(jù)，數(shù)據(jù)見表1.

表1 并行D_Apriori算法實(shí)驗(yàn)數(shù)據(jù)

(1)串行并行算法的比較分析

實(shí)驗(yàn)過(guò)程中分別記錄下單機(jī)模式和集群模式下運(yùn)行大小不同數(shù)據(jù)集所需要的時(shí)間(單位為秒)，見表2.

表2 單機(jī)模式和集群模式數(shù)據(jù)集運(yùn)行時(shí)間

為了分析該并行算法的可行性，只對(duì)CS2～CS5數(shù)據(jù)集的運(yùn)行時(shí)間進(jìn)行對(duì)比，其對(duì)比結(jié)果如圖2所示。

圖2 串行Apriori算法與并行D_Apriori算法的運(yùn)行時(shí)間對(duì)比

(2)加速比分析

加速比是用于衡量本次實(shí)驗(yàn)中并行算法的并行效率的標(biāo)準(zhǔn)，根據(jù)加速比公式，得到并行Apriori算法的加速比，并將結(jié)果記錄于表3.

表3 并行D_Apriori算法的加速比

其加速比的比較圖如圖3所示.

圖3 并行D_Apriori算法的加速比比較圖

從以上分析可以看出，在處理小規(guī)模數(shù)據(jù)集時(shí)，串行算法的處理時(shí)間小于并行算法的處理時(shí)間，但隨著數(shù)據(jù)集規(guī)模的增大，任務(wù)所需的資源的比例也隨之增大，并行算法的加速比性能越來(lái)越好，體現(xiàn)出了并行算法的優(yōu)勢(shì)，并行化的D_Apriori算法更適合應(yīng)用于大規(guī)模數(shù)據(jù)的處理.

3 結(jié)束語(yǔ)

在數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則是重要的數(shù)據(jù)挖掘算法，是通過(guò)多次掃描數(shù)據(jù)庫(kù)來(lái)產(chǎn)生頻繁項(xiàng)集，但面對(duì)海量數(shù)據(jù)時(shí)，需要花費(fèi)大量的時(shí)間和空間，因而利用Hadoop平臺(tái)實(shí)現(xiàn)Apriori算法的并行化，從而解決海量數(shù)據(jù)問(wèn)題，實(shí)驗(yàn)表時(shí)，并行化后的D_Apriori算法具有良好的加速比，適用于對(duì)海量數(shù)據(jù)的處理，下一步將會(huì)繼續(xù)研究將其他數(shù)據(jù)挖掘算法也移值到Hadoop平臺(tái)上實(shí)現(xiàn)算法并行化，增強(qiáng)云挖掘系統(tǒng)的能力.

參 考 文 獻(xiàn)

[1] 晏杰,元文娟.基于Apriori&FP-Growth算法的研究[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2013,22(5):122-125.

[2] 潘婷.基于物聯(lián)網(wǎng)服務(wù)平臺(tái)的海量傳感信息Hadoop處理方法和系統(tǒng)設(shè)計(jì)[D].南京郵電大學(xué),2013.

[3] 何建佳,葉春明,王祥兵,等.面向云計(jì)算的數(shù)據(jù)挖掘系統(tǒng)架構(gòu)研究[J].計(jì)算機(jī)應(yīng)用研究,2011,28(4):1372-1374.

[4] Han Jiawei,Pei Jian,Yin Yiwen.Mining Frequent Patterns Without Candidate Genneration[C]//Proceedings of ACM SIGMOD International Conference on Management of Date.New York,USA:ACM Press,2000.1-12.

[5] Agrawal R and Srikant R.Fsat algorithms for mining association rules in large databases[C].In Proceedings of 20th International Conference on Very Large Data Bases,1994.478-499.

[6] 董西成.Hadoop技術(shù)內(nèi)幕-深入解析MapReduce架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)原理[M]..北京:機(jī)械工業(yè)出版社,2013.

[7] 林長(zhǎng)方,吳揚(yáng)揚(yáng),黃仲開,等.基于MapReduce的Apriori算法并行化[J].江南大學(xué)學(xué)報(bào):自然科學(xué)版,2014,13(4):411-415.

[8] 戴新喜,白似雪.一種高效的基于布爾矩陣的Apriori改進(jìn)算法[J].廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2007,25(4):176-179.