基于云計算的最大頻繁項集挖掘算法

孫鶴旭，孫澤賢，林　濤

(河北工業(yè)大學 控制科學與工程學院，天津 300130)

?

基于云計算的最大頻繁項集挖掘算法

孫鶴旭，孫澤賢*，林濤

(河北工業(yè)大學 控制科學與工程學院，天津 300130)

針對目前海量數據挖掘過程中存在著頻繁項集挖掘效率低、冗余項集繁多的問題，提出了改進的頻繁模式樹和遺傳算法(FPGA),該算法鑒于異構數據的差異性特征，采用改進的頻繁模式樹和基于MapReduce的并行遺傳算法搜索最大頻繁項集，縮小了搜索范圍，提高了挖掘效率.實驗結果表明：該算法在時間復雜度方面有了很大提高，與傳統(tǒng)的FP_Growth算法相比，具有更好的加速比以及更高的執(zhí)行效率.

遺傳算法；云計算；FP_Growth算法；最大頻繁項集

近年來，不同結構類型的數據呈現幾何、爆炸式的增長，海量異構數據在日常的應用中扮演著關鍵角色，傳統(tǒng)的數據管理系統(tǒng)已經很難適應目前的發(fā)展形勢.挖掘異構數據的研究主要分為分類挖掘、關聯規(guī)則挖掘、聚類挖掘等，其中關聯規(guī)則挖掘是重要問題之一.關聯規(guī)則挖掘和頻繁項集挖掘有著緊密的聯系，頻繁項集挖掘是關聯規(guī)則挖掘的先決條件.由于在頻繁項集挖掘的過程中，往往存在著結果項集數量十分龐大，挖掘效率較差的問題，影響了挖掘結果的應用與理解.為了解決上述問題，文獻[1]通過構造支持度函數、關鍵字篩選技術，減小了內存消耗，去除了用戶不關心的冗余信息，但仍然采用的是傳統(tǒng)的串行計算方法.文獻[2]、[5-7]、[9]利用了MapReduce的并行計算優(yōu)勢，但并沒有對挖掘算法進行改進，只是單純的提高了挖掘效率，依然存在挖掘結果數量龐大、冗余信息多的缺點.文獻[3]提出了UFPGA算法，利用縮小變異空間的遺傳算法搜索頻繁項集，但沒有考慮到算法的性能問題.文獻[4]結合模糊集理論和Apriori算法，提出了模糊加權關聯規(guī)則挖掘算法，提高了算法的挖掘效率，但卻依然存在冗余的規(guī)則.文獻[8]基于DCI-Closed-Index閉項集挖掘算法引入了全新的剪枝策略，設計了一個元項集的挖掘策略，挖掘效果得到了很大提高.

針對以上問題，本文提出了基于遺傳算法和FP_Growth挖掘算法的組合思想，有效地減少了檢測數據的數量，降低了搜索空間.而且，有效地減少了挖掘過程中的迭代次數，得到更加準確的條件模式基；另外，結合MapReduce并行計算模式，對遺傳算法、FP_Growth算法的各個步驟并行化，不僅提高了挖掘效率，消除了冗余結果，而且可減少內存消耗，解決了內存不足的問題.

1　最大頻繁項集挖掘方法

1.1構建原頻繁模式樹

在構建原頻繁模式樹時，針對FP-Growth算法掃描原始事務數據庫時，受制于單機計算能力、網絡帶寬能力的缺陷，在挖掘大數據集的過程中需要大量的I/O開銷；因此，本文結合MapReduce框架進行并行計算，提高計算效率，并將原始事務數據庫轉換為布爾矩陣，減少對事務數據庫的掃描次數.即FPMP算法(FP-Growth結合MapReduce)，給定一個原始事務數據庫TD(如表1所示)以及最小支持度min_sup,FPMP算法利用兩次MapReduce來構建原頻繁模式樹，FPMP算法具體流程如圖1所示.

圖1　構建原頻繁模式樹算法流程圖Fig.1　Flow chart of the FPMP

其算法步驟如下.

(1) 構建布爾矩陣：將原始事務數據庫TD(m個事務，n個項)轉換為布爾矩陣A=(aij)m×n，aij代表TD中的項，若項存在，則aij=1，否則為0.

(2) 分片：根據MapReduce中從節(jié)點的個數，將矩陣A垂直劃分為s個子矩陣(A1,A2，As),前s-1個分塊的數據大小相等，即子矩陣的列數均為

ceil(n/s)，最后一個子矩陣的列數為n-(s-1)×ceil(n/s).

(3) 并行計數：并行掃描原始事務數據庫，記錄每一項的支持度.

(4) 構造全局F-List：傳統(tǒng)算法在構建全局F-List的過程中，需要從第一項開始遍歷，查找對應的項名稱以及支持度，即只能進行順序查找，隨著項集數量的增加，遍歷時間也會增加，嚴重影響算法執(zhí)行效率.

本文通過設定一個地址函數f(In)，實現項名稱In與存儲地址f(In)的映射，并將支持度存入該地址中.在查找某項的支持度時，通過地址函數計算得出項地址，進而直接獲得支持度，而無需從第一項開始遍歷，時間復雜度由n提高到1.

例如，對表1的事務數據庫，其傳統(tǒng)的存儲結構如表2所示，本算法的存儲結構如表3所示.

表1　事務數據庫

表2　傳統(tǒng)算法存儲結構

表3　改進的存儲結構

對比頻繁項列表F-List的存儲結構表2、3可知，本算法效率的提高主要體現在：第2次掃描原始事務數據庫時，刪除非頻繁項，并按照F-List的順序降序排列.如果存在多個項的支持度計數相等時，改進算法只需比較地址函數的值，便可以判定項的順序.

(5) 并行FP-Growth：在Map階段，依據第(4)步得到的F-List，構造每個項的條件模式基.在Reduce階段，根據條件模式基構建原頻繁模式樹.

1.2構建有序頻繁模式樹

定義1在事務數據庫TD中，挖掘的結果項集X是頻繁項集，如果不存在頻繁項集Y，滿足X?Y，|Y|=|X|+1，則X為最大頻繁項集.

有序頻繁模式樹(OFPT)將TD中的項壓縮到原頻繁模式樹(FPT)中，利用支持度計算頻繁模式樹上的高支持度集，使得樹節(jié)點代表計算的項集，以此構建樹結構.

在構建OFPT時，首先構建FPT.對于表1的事務數據庫，設定其最小支持度閾值為3，1-項集集合為{(B：14)，(C：13)，(A：12)，(D：10)，(E：3)}，構建的FPT如圖2所示.

圖2　原頻繁模式樹Fig.2　Original frequent pattern tree

之后，復制FPT作為OFPT的樹干，遍歷FPT的第一層的項{(B：14)、(C：1)}，統(tǒng)計下層的分支鏈為{(C：12-A：9-D：6-E:2)，(A：2-D：1)，(C：0-D：2)，(C：0-A：0-E：1)，(A：1-D：1)}，將分支鏈看做對應的事務壓縮到OFPT中，同時，節(jié)點的支持度計數也要累加到投影點上.然后在下一層的項{(C：12)、(A：2)、(C：1)}繼續(xù)投影，直到最后一層{(E：2)}投影完成，最終OFPT如圖3所示.

圖3　最終的有序頻繁模式樹Fig.3　Ordered frequent pattern tree

根據定義1可知，在OFPT中如果存在一個節(jié)點r對應的項集為頻繁項集，而下一層節(jié)點r+1對應的項集不是頻繁項集，那么節(jié)點r即為所在分支鏈的最大頻繁項集.依據此規(guī)律，采用基于MapReduce的并行遺傳算法，利用其全局搜索性、隨機性、并行性計算的特點，搜索各分支鏈的最大頻繁項集.

1.3基于并行遺傳算法的最大頻繁項集挖掘

對于傳統(tǒng)的遺傳算法，在搜索最大頻繁項集的過程中，具有搜索不完全、迭代次數過多的缺陷.因此，本算法結合MapReduce并行計算模型，改進了變異運算，提高了搜索準確性.算法具體描述如下.

(1) 編碼：算法采用十進制編碼規(guī)則.首先，統(tǒng)計OFPT中分支鏈的數量作為染色體的長度，每條分支鏈對應一個基因位，每條分支鏈上的節(jié)點代表該基因位有幾種基因值，基因z取值范圍為[1,zmax]，zmax為OFPT中根節(jié)點到葉子節(jié)點的節(jié)點數(不包括根節(jié)點).

(2) 初始化種群：將整個種群分為n個子種群，每一個子種群由一個MapReduce任務負責.

(3) 適應度函數：為了保證基因值對應的是最大頻繁項集，采用如下的對應函數：

(1)

其中，c為比例參數，取值為10的倍數，取決于初始化種群大小，這樣能夠保證復制到下一代的個體為優(yōu)秀個體.l為OFPT分支鏈數量，即染色體長度.在Map階段計算子種群中個體的適應度值，在根據子種群數量以及Reduce數量，將各子群分配到Reduce任務中，首先暫存各子群，之后再在Reduce階段執(zhí)行選擇、交叉、變異操作.

(4) 選擇和交叉：本算法采用輪盤賭法，基于適用度比例選擇優(yōu)秀個體；交叉操作采用均勻交叉對種群個體進行隨機配對.

(2)

并行遺傳算法流程圖如圖4所示，由上述過程可知，這里僅需計算少量頻繁項集.然后按照定義1搜索最大頻繁項集，并且將MapReduce并行計算模式和遺傳算法一起應用到FP_Growth算法上，提高了算法的整體性能.

圖4　并行遺傳算法流程圖Fig.4　Flowchart of the Parallel genetic algorithm

1.4FPGA算法流程

FPGA算法描述如下.

輸入：原始事務數據庫TD，最小支持度，概率閾值.

輸出：最大頻繁項集.

a. 構建FPT：利用MapReduce的并行計算模式，結合地址函數有效地提高了算法的時間復雜度.

b. 構建OFPT：將FPT中每一層節(jié)點投影到OFPT中，直到最后一層結束.

c. 修減OFPT：將每條支鏈中支持度小于ω的節(jié)點去掉.

d. 編碼：遍歷OFPT，統(tǒng)計分支鏈條數L和最大節(jié)點個數，將染色體的每一個基因位賦值，并進行十進制編碼.

e. 隨機初始化子種群：每一個子種群由一個MapReduce任務負責，在Map階段進行適應度選擇，并將各子群分配到對應的Reduce任務中.

f. 按照公式(1)計算各適應度，并以此進行選擇、交叉、變異操作.

g. 重復f操作，直到流程結束，輸出挖掘的頻繁項集.

綜上所述，FPGA算法采用地址函數、MapReduce并行計算模型、遺傳算法優(yōu)化了FP_Growth算法，具有更好的加速比、更好的執(zhí)行效率，節(jié)省了內存資源.

2　實驗結果及分析

本文實驗平臺的基本配置如表4所示，1個NameNode，3個DataNode，操作系統(tǒng)為CentOS release 5.6，Mapper和Reducer的最大負載都配置為2，其他配置都采用Hadoop的默認配置.

表4　實驗平臺基本配置

設定最小支持度為10%、20%、30%、40%、50%，采用某公司貨物供應商數據集進行試驗，總計有12790431條事務，事務數據庫涉及3210個項.文獻[9]在分析了傳統(tǒng)的FP_Growth算法的基礎上，針對單路徑和多路徑的不同挖掘算法，提出了Pruned FP-tree算法，結合MapReduce計算模式，實現了算法流程的并行化，提高了對海量數據的處理能力；然而，它并沒有對FP_Growth算法進行改進，算法依舊需要對數據庫進行重復掃描.因此，在構建原頻繁模式樹時，FPGA算法借鑒文獻[9]的思想，利用MapReduce的并行計算的優(yōu)勢，結合地址函數的思想，有效地減小了時間開銷，FPGA算法與Pruned FP-tree算法的性能比較如圖5所示.

圖5　FPGA與FP_Growth性能比較Fig.5　The comparison between the FPGA and FP_Growth

定義2加速比即為在Hadoop框架下單節(jié)點算法執(zhí)行時間t1和多節(jié)點算法執(zhí)行時間tp之比.如公式(3)所示：

Sp=t1/tp.

(3)

本文通過加速比來評估FPGA算法在挖掘最大頻繁項集中的整體性能.在同義事務數據庫的前提下，通過對比不同最小支持度、不同工作節(jié)點數的加速比，證明了FPGA算法的優(yōu)越性.

如圖6 所示，不同最小支持度的加速比是不一致的，加速比在最初階段會隨著節(jié)點數的增加而變大，但由于節(jié)點數量增加會造成通信負載的增大，使得加速比的增長趨于穩(wěn)定.由圖6可知，在最小支持度變大時，頻繁項集的數量會減少，并行遺傳算法搜索的項集也就會減少，因此加速比的增長也就開始降低.

圖6　FPGA算法的加速比Fig.6 The speed-up raios of the FPGA

3　結束語

本文提出一種基于Hadoop的，將FP_Growth算法和遺傳算法相結合的最大頻繁項集挖掘算法.該算法主要由6步組成：構建原頻繁模式樹，構建有序頻繁模式樹，修減有序頻繁模式樹，編碼，隨機初始化子種群，選擇、交叉、變異，最終挖掘出最大頻繁項集.實驗表明該算法是十分有效的，本文的主要創(chuàng)新

點是：將FP_Growth算法并行化，結合地址函數，快速構建原頻繁模式樹；在挖掘最大頻繁項集的過程中，利用遺傳函數的全局搜索性、隨機性，再結合MapReduce的并行計算模型，提高了整體挖掘效率.但本文也有一定的不足之處，如果數據集較小，采用MapReduce則會降低算法執(zhí)行效率，則沒有并行化的必要，這是以后仍需改進的地方.

[1]李宏光,夏麗君. 改進的FP-growth算法及其在TE過程故障診斷中的應用[J]. 北京工業(yè)大學學報,2016(05):697-706.

[2]周國軍,龔榆桐. 基于MapReduce和矩陣的頻繁項集挖掘算法[J]. 微電子學與計算機,2016(5):119-123.

[3]唐向紅,楊全緯,鄭 陽. 挖掘不確定數據的最大頻繁項集[J]. 華中科技大學學報(自然科學版),2015(9):29-34.

[4]王佳,李宏光. 工業(yè)報警序列的模糊關聯規(guī)則挖掘方法[J]. 化工學報,2015(12):4922-4928.

[5]陳興蜀,張帥,童浩,等. 基于布爾矩陣和MapReduce的FP-Growth算法[J]. 華南理工大學學報(自然科學版),2014(1):135-141.

[6]何波. 基于頻繁模式樹的分布式關聯規(guī)則挖掘算法[J]. 控制與決策,2012(4):618-622.

[7]陳光鵬,楊育彬,高陽,等. 一種基于MapReduce的頻繁閉項集挖掘算法[J]. 模式識別與人工智能,2012,25(2):220-224.

[8]宋威,李晉宏,徐章艷,等. 一種新的頻繁項集精簡表示方法及其挖掘算法的研究[J]. 計算機研究與發(fā)展,2010,47(2):277-285.

[9]楊勇,王偉. 一種基于MapReduce的并行FP-growth算法[J]. 重慶郵電大學學報(自然科學版),2013,25(5):651-657+670.

Mining Maximal Frequent Itemsets Based on Cloud Computing

SunHexu,SunZexian,LinTao

(Institute of Control Science and Engineering , Hebei University of Technology , Tianjin 300130, China)

Since efficiency and accuracy of mining frequent itemsets is not very high in mass data,an improved FPGA algorithm was proposed for mining them.According to the feactures of the mass data,the improved FP_Growth mines frequent itemsets and the parallel genetic algorithm was employed to search for the largest frequent patterns.FPGA althorithm sharnk the scope to improve the efficiency of the mining results.Experiments show that the FPGA althorithm is superior to the original one due to the high efficiency and speedup.

genetic althorithm;cloud computing;FP_Growth althorithm;maximal frequent itemsets

2016-06-30*通訊作者孫澤賢，研究方向：數據挖掘、云計算， E-mail：1249226957@qq.com

孫鶴旭(1956-)，男，教授，博士生導師，研究方向：自動化,E-mail：shx13682168380@sina.com

天津市科技支撐資助項目(14ZCDZGX00818)

TP3

A

1672-4321(2016)03-0102-05