李成嚴(yán) 辛雪 趙帥 馮世祥

摘 要：針對大數(shù)據(jù)環(huán)境下關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘效率不高的問題，采用Eclat算法使用垂直數(shù)據(jù)庫將事務(wù)的合并轉(zhuǎn)換成集合操作的方法。研究了一種大數(shù)據(jù)并行關(guān)聯(lián)規(guī)則挖掘算法-Sp-IEclat（Improved Eclat algorithm on Spark Framework），該算法基于內(nèi)存計算的Spark框架，減少磁盤輸入輸出降低I/O負載，使用位圖運算降低交集的時間代價并減少CPU占用，采用前綴劃分的剪枝技術(shù)減少求交集運算的數(shù)據(jù)量，降低運算時間。使用mushroom數(shù)據(jù)集和webdocs數(shù)據(jù)集在兩種大數(shù)據(jù)平臺下實驗，結(jié)果表明，Sp-IEclat算法的時間效率優(yōu)于MapReduce框架下的Eclat算法及Spark框架下的FP-Growth算法和Eclat算法。從對集群的性能監(jiān)控得到的數(shù)值表明，同Spark框架下的FP-Growth算法和Eclat算法相比，Sp-IEclat算法的CPU占用和I/O集群負載都較小。

關(guān)鍵詞：大數(shù)據(jù);關(guān)聯(lián)規(guī)則挖掘;頻繁項集;Spark彈性分布式數(shù)據(jù)集;MapReduce框架

DOI：10.15938/j.jhust.2021.04.015

中圖分類號：TP399

文獻標(biāo)志碼：A

文章編號：1007-2683（2021）04-0109-10

Abstract：Aiming at the problem of inefficient data mining of association rules in a big data environment， the Eclat algorithm is used to use a vertical database to convert the merging of transactions into collective operations. We researched a big data parallel association rule mining algorithm-Sp-IEclat（Improved Eclat algorithm on Spark Framework）. The algorithm is based on the Spark framework of memory computing， reduces disk input and output， reduces I/O load， and uses bitmap operations to reduce the time of intersection and CPU usage. The pruning technique of prefix division is used to reduce the amount of data in the intersection operation to reduce the operation time. The mushroom dataset and the webdocs dataset are used to test under two big data platforms.The experimental results show that the time efficiency of the Sp-IEclat algorithm is better than the Eclat algorithm under the MapReduce framework and the FP-Growth algorithm and the Eclat algorithm under the Spark framework. The value obtained from the performance monitoring of the cluster shows that， compared with the FP-Growth algorithm and the Eclat algorithm under the Spark framework， the CPU usage and I/O cluster load of Sp-IEclat are smaller.

Keywords：big data; association rule data mining; frequent itemset; Spark resilient distributed dataset（RDD）; MapReduce framework

0 引 言

關(guān)聯(lián)規(guī)則挖掘技術(shù)是數(shù)據(jù)挖掘中的重要組成部分，廣泛的應(yīng)用在金融行業(yè)[1]，零售業(yè)市場營銷[2]及醫(yī)療[3]等領(lǐng)域。

關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法有Apriori[4]算法，F(xiàn)P-Growth[5]算法及Eclat[6]算法。Apriori在其進行迭代的過程將會產(chǎn)生大量的候選集并且放在內(nèi)存中，當(dāng)處理大數(shù)據(jù)集時會導(dǎo)致內(nèi)存不足，而且Apriori需要重復(fù)的讀取數(shù)據(jù)庫，將會給系統(tǒng)I/O造成巨大壓力;FP-Growth算法將數(shù)據(jù)庫的掃描次數(shù)壓縮到了2次，但是在生成樹結(jié)構(gòu)的時候會有額外的開銷，當(dāng)數(shù)據(jù)集的支持度較低時，將會產(chǎn)生大量的節(jié)點，導(dǎo)致內(nèi)存不足;Eclat算法只讀取一次數(shù)據(jù)庫，但是取交集時會有大量的候選集存儲在內(nèi)存中，會耗費大量時間。

針對Eclat算法在數(shù)據(jù)集較大時求交集的時間代價會很大的問題，很多學(xué)者對Eclat算法進行了改進。文[7]提出了一種改進的Eclat算法-Eclat+算法。Eclat+算法在計算候選集的支持度之前，首先檢測支持度，當(dāng)候選集是潛在頻繁項集時，才執(zhí)行交集操作;文[8]提出了一種快速的Eclat算法，該算法可以通過使用Minwise散列和估計量來快速計算多個項目集的交集大小;文[9] 基于遞增的搜索策略提出了一種改進的Eclat算法，稱為Eclat_growth。以上算法都在一定程度上提高了Eclat算法的運行效率，但是在求交集時仍會占用很多時間以及整個算法的CPU占用仍很高。

傳統(tǒng)的關(guān)聯(lián)規(guī)則算法無法處理大數(shù)據(jù)環(huán)境下的數(shù)據(jù)挖掘問題，所以有學(xué)者將算法在MapReduce框架下實現(xiàn)。文[10]將Apriori算法轉(zhuǎn)移到MapReduce框架上實現(xiàn);文[11]介紹了兩種算法，分別是基于MapReduce平臺的Dist-Eclat算法和BigFIM。Dist-Eclat通過使用基于k-fis的簡單負載平衡方案來關(guān)注速度。BigFIM重點是利用混合方法挖掘非常大的數(shù)據(jù)庫，優(yōu)化為在真正大的數(shù)據(jù)集上運行。文[12]將Eclat算法轉(zhuǎn)移到MapReduce框架上并進行了改進。文[13]提出了一種基于MapReduce的等長劃分數(shù)據(jù)庫，并使用位圖來計算的關(guān)聯(lián)規(guī)則挖掘算法。文[14]提出了一種按照等長切割數(shù)據(jù)集后在每一塊數(shù)據(jù)集上使用MapReduce的Apriori算法或者FP-Growth算法的組合方法。文[15]提出了一種基于前綴共享樹設(shè)計的關(guān)聯(lián)規(guī)則挖掘算法，這種方法通過將共有的前綴樹進行合并，從而達到減少內(nèi)存占用和節(jié)省運算時間。文[16]提出了一種并行的FP-Growth算法，將傳統(tǒng)的FP-Growth再加上前綴樹的生成模式，使用了消息傳遞機制將規(guī)則按照前綴分配到各個reduce中。以上算法選用了MapReduce框架來解決大數(shù)據(jù)挖掘的問題，但由于MapReduce是基于非循環(huán)的數(shù)據(jù)流模型，在計算過程中，不同計算節(jié)點之間保持高度并行，導(dǎo)致需要反復(fù)使用一個特定數(shù)據(jù)集的迭代算法無法高效地運行。在內(nèi)存占用方面，如果一個節(jié)點運行失敗，需要將這個節(jié)點的任務(wù)重復(fù)運行多次甚至交給其他運算能力更高的節(jié)點重新計算，從而導(dǎo)致巨大的內(nèi)存損耗。

Spark框架不僅克服了MapReduce框架的上述缺點，還具有迭代運算效率高，集群I/O負載低等優(yōu)勢。文[17]針對提出了一種基于Spark框架的并行Apriori算法FAFIM，并證明該算法的運行效率要遠遠高于文[10]提出的算法。文[18]針對Apriori算法在生成候選項集的大量開銷問題，提出了R-Apriori算法，通過消除候選生成步驟并避免了代價高昂的比較從而降低計算復(fù)雜性。文[19]提出了一種基于Apriori增量并行算法。該算法隨著數(shù)據(jù)集的增加，不需要從頭開始計算整個數(shù)據(jù)庫，而是根據(jù)以前的頻繁項集更新頻繁的項集。文[20] 提出了基于Spark的分布式FP-Growth算法叫做DFPS算法，該算法的運行效率遠遠高于FP-Growth算法在MapReduce框架下的運行效率。文[21] 提出了基于Spark實現(xiàn)的可擴展的并行FP-Growth。文[22]提出了一種改進的FP-Growth算法，該算法修改了支持計數(shù)并在Spark下實現(xiàn)。

以上算法都是基于Spark框架下對Apriori算法和FP-Growth算法的改進，由于都是基于水平數(shù)據(jù)庫的算法，在速度，I/O負載和CPU占用方面仍然存在問題，所以選擇在基于內(nèi)存的Spark框架下對基于垂直數(shù)據(jù)庫的Eclat算法進行改進，從而降低集群的I/O負載。根據(jù)文[7]中提到的對數(shù)據(jù)庫使用預(yù)處理技術(shù)進行數(shù)據(jù)壓縮，減少問題規(guī)模，并根據(jù)文[9]及文[13]中提出的使用位圖的方法來進行計算，減少求交集的運算時間并降低CPU占用。根據(jù)文[13]及文[14]提出的方法對頻繁項集進行劃分，根據(jù)文[15]及文[16]提出的方法以前綴為劃分條件對頻繁項集進行劃分，即對求得的頻繁項集使用前綴策略進行劃分并提交給不同的計算節(jié)點進行計算，這樣能夠減少需要求交集的數(shù)據(jù)量從而減少集群的運算量，從而提高了算法的運行速度。

本文的主要工作如下：

1）將Eclat算法使用基于位圖的計算策略并采用前綴劃分策略對其進行改進，提高了運行效率，減少了CPU占用。

2）將改進的Eclat算法在Spark框架下進行實現(xiàn)，降低了集群的I/O負載，提出了基于Spark框架的關(guān)聯(lián)規(guī)則挖掘算法—Sp-IEclat算法。

3）通過運行相關(guān)的實驗，與基于MapReduce下的Eclat算法和現(xiàn)有的一些基于Spark的關(guān)聯(lián)規(guī)則挖掘算法進行實驗比較。比較的內(nèi)容為公共數(shù)據(jù)集下，不同支持度的挖掘時間性能表現(xiàn)。

本文其余部分構(gòu)成如下：第2部分為介紹相關(guān)概念;第3部分介紹Sp-IEclat算法;第4部分描述本算法的具體實現(xiàn)，并做復(fù)雜度分析;第5部分進行數(shù)值實驗并對結(jié)果分析;最后給出結(jié)論。

1 相關(guān)概念

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

設(shè)D={T1，T2，T3，…，Tn}是一個事務(wù)數(shù)據(jù)集，該數(shù)據(jù)包含n個事務(wù)項集，其中每個事務(wù)項集包含m個不同的項，I={I1，I2，I3，…，Im}。包含K個事務(wù)項的項集被稱為K-項集，K為項集的長度。項集X在D中出現(xiàn)的次數(shù)叫做項集X的支持度。

如果項集的支持度不小于規(guī)定的最小支持度，則為頻繁項集。反之，為非頻繁項集。

前綴共享樹：設(shè)兩個項集X={i1，i2，…，ik，…，im}，Y={i1，i2，…，ik，…，in}它們的前k項相同，則{i1，i2，…，ik}稱為項集X和Y的K-前綴。項集{A，B，C，D}和項集{A，B，E，F(xiàn)}具有相同前綴{A，B}。

1.2 SPARK框架

Spark是一種基于內(nèi)存的分布式計算框架，不僅包含MapReduce分布式設(shè)計的優(yōu)點，而且將中間處理數(shù)據(jù)放入內(nèi)存中以減少磁盤I/O從而提高性能。Spark是基于Spark RDD編程，提供轉(zhuǎn)換算子和行動算子2種算子。2種算子都將中間結(jié)果存放在內(nèi)存中，所以會有較快的運行效率。相比MapReduce框架，Spark具有更高效、充分利用內(nèi)存、更適合迭代計算和交互式處理的優(yōu)點。

2 Sp-IEclat算法

2.1 ECLAT算法

Eclat算法采用的數(shù)據(jù)結(jié)構(gòu)是垂直數(shù)型數(shù)據(jù)結(jié)構(gòu)，即數(shù)據(jù)形式為{item：TIDSet}的形式。如此轉(zhuǎn)換后，關(guān)聯(lián)規(guī)則的挖掘?qū)嶋H上轉(zhuǎn)換成了使用集合運算的方式。對于小數(shù)據(jù)集，集合運算的速度將會很快。但當(dāng)數(shù)據(jù)集變大的時候，取交集的運算的代價會變得比較大，也會產(chǎn)生比較大的中間數(shù)據(jù)量。Eclat算法對于大型數(shù)據(jù)集數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘時時間效率不是很理想，所以將Eclat算法進行優(yōu)化使其更加適用于挖掘大型數(shù)據(jù)集。

2.2 SP-IECLAT算法概述

針對Eclat算法求交集運算代價大的問題，采用位圖交集運算來代替集合交集運算使用前綴劃分策略將頻繁項集進行劃分。本文提出了Sp-Eclat算法，一種基于Spark框架的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法，在Spark框架下編程運行。Sp-Eclat算法共分成2個部分，分別是數(shù)據(jù)預(yù)處理和計算頻繁K-項集。

首先是數(shù)據(jù)預(yù)處理。第一步要讀取數(shù)據(jù)，Spark的讀取數(shù)據(jù)分為從本地文件系統(tǒng)中加載數(shù)據(jù)和從分布式文件系統(tǒng)（HDFS）中讀取數(shù)據(jù)，本文采用的是讀取HDFS中數(shù)據(jù)。然后將得到的數(shù)據(jù)進行數(shù)據(jù)庫格式的轉(zhuǎn)換及非頻繁項集的過濾。將水平數(shù)據(jù)庫轉(zhuǎn)換成垂直數(shù)據(jù)庫，轉(zhuǎn)換后將項集的支持度和給定的最小支持度進行比較，如果小于，則將該項集是非頻繁項集，將其過濾掉;如果大于，則得到了頻繁1-項集。最后位圖存放數(shù)據(jù)，將得到的頻繁1-項集采用位圖保存TID，位圖中1的個數(shù)就是該項集的支持度。

然后為計算頻繁K-項集。包含計算頻繁2-項集及根據(jù)頻繁2-項集求出頻繁K（K>2）-項集。在求頻繁2-項集時，對itemID求并集并對TID求交集，保留TID交集的長度大于等于最小支持度的作為頻繁2-項集。使用前綴劃分策略對頻繁2-項集進行劃分并分發(fā)給計算節(jié)點。計算得到的頻繁2-項集的大小是遠小于整個事務(wù)的大小，對頻繁K-項集使用前綴劃分策略進行劃分需要觸發(fā)到shuffle計算，而頻繁K-項集的大小同樣遠小于頻繁2-項集的大小，所以Sp-Eclat的網(wǎng)絡(luò)通信開銷會很小。Sp-IEclat算法流程圖如圖1所示。

2.3 數(shù)據(jù)預(yù)處理

Eclat算法在生成K-項集的時候總是需要使用到（K-1）-項集作為生成的前綴，但隨著數(shù)據(jù)量的增加或者最小支持度的減小，生成K-項集的前綴數(shù)量會很大，求交集時的時間代價和CPU占用會很大從而導(dǎo)致該方法不可用。這種趨勢在分布式框架上也變得非常明顯，即當(dāng)一臺機器的性能不足以完成分配到的任務(wù)時，往往是需要系統(tǒng)將這個任務(wù)分配到性能更強的機器上，而這個調(diào)度代價是非常巨大的。

為了降低調(diào)度代價，通過數(shù)據(jù)預(yù)處理將讀取的數(shù)據(jù)轉(zhuǎn)換成垂直數(shù)據(jù)庫并過濾掉支持度小于最小支持度的數(shù)據(jù)，從而減小了整個算法中生成的中間候選集。如圖2所示，給出了一個示例說明當(dāng)最小支持度為2時，水平數(shù)據(jù)庫轉(zhuǎn)換成垂直數(shù)據(jù)庫并得到頻繁1-項集的過程。

每一個事務(wù)TID都對應(yīng)了一個項集itemSet，表示為在該事務(wù)中分別出現(xiàn)的項。將每一個項拿出來并將該項出現(xiàn)的全部TID放入到TIDSet中就得到了垂直數(shù)據(jù)庫。如圖2所示，對于項A分別出現(xiàn)在TID為1，2，3的事務(wù)中，所以項A所對應(yīng)的TIDSet為{1，2，3}。其次，對得到的垂直數(shù)據(jù)庫中支持度小于最小支持度的數(shù)據(jù)進行刪除。如圖2所示，假設(shè)給定最小支持度為2，轉(zhuǎn)換成垂直數(shù)據(jù)庫形式后，項C對應(yīng)的TIDSet為{3}，該集合中只有一個元素，表明項C的支持度為1，小于給定的最小支持度，所以將項C從垂直數(shù)據(jù)庫中刪除，這個過程使用Spark對于RDD提供的轉(zhuǎn)換算子filter算子來完成，對于其他項A，B，C，E，支持度都大于最小支持度，所以都保留。上述過程結(jié)束后，就得到了頻繁1-項集。

對于得到的頻繁1-項集，為了降低后續(xù)計算頻繁K-項集的時間代價和CPU占用，在數(shù)據(jù)的導(dǎo)出中直接采用位圖的形式存放TID，位圖是位操作的對象，值只有0或1，TID的值對應(yīng)于位圖中的標(biāo)號設(shè)置為1。BitSet最小規(guī)模是64位，隨著存儲的元素越來越多，BitSet內(nèi)部會自動擴充，每次擴充64位，位圖的大小是TIDSet中最大的TID向上取整64位。當(dāng)數(shù)據(jù)集很大時，位圖求交集的時間效率遠遠高于集合求交集時間效率。對于圖2得到的頻繁1-項集，項集{A}和項集{D}的位圖內(nèi)部存放形式如圖3所示。

2.4 計算頻繁2-項集

預(yù)處理中將水平數(shù)據(jù)庫轉(zhuǎn)換成了垂直數(shù)據(jù)庫，并且得到了所有頻繁1-項集。在計算頻繁2-項集中，Sp-IEclat算法使用Eclat算法取交集的思想，進行頻繁2-項集的計算。當(dāng)數(shù)據(jù)量巨大的時候，Eclat算法取交集的成本將會變得非常的高。所以對保存TID的位圖求交集，位圖作為基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，即使對于很大的數(shù)據(jù)集，求交集的效率仍然很高。如圖4所示，給出了用圖2的頻繁1-項集來計算頻繁2-項集的過程。

圖4中，使用了圖2的頻繁1-項集得到的2-項集有{A，B}，{A，D}，{A，E}，{B，D}，{B，E}，{D，E}，但2-項集{D，E}對應(yīng)的TIDSet為{3}，支持度為1，小于給定的最小支持度，不滿足頻繁2-項集要求，因此不將{D，E}加入到頻繁2-項集中。

將獲得的頻繁2-項集使用前綴劃分策略進行劃分，具體前綴劃分策略工作在2.5中說明，Sp-IEclat算法是在Spark分布式框架下并行執(zhí)行的，首先要Dirver Program觸發(fā)集群開始作業(yè)，也就是在文件讀取時應(yīng)用已經(jīng)被提交，然后Cluster Manager作為主節(jié)點控制著整個集群，將獲得的頻繁2-項集分發(fā)到計算節(jié)點進行計算，每個結(jié)算節(jié)點接收到來自主節(jié)點的命令之后負責(zé)任務(wù)的執(zhí)行。

2.5 前綴劃分策略

根據(jù)文[14]提出的數(shù)據(jù)集劃分技術(shù)，提出了前綴劃分策略。根據(jù)文[14]中的引理1，可以得到以下推論：

引理1：將數(shù)據(jù)集D劃分為S個相等大小的數(shù)據(jù)塊，記為D = {D1，D2，...，DS}，將這些塊上的本地頻繁項目集分別表示為FI 1，F(xiàn)I2，...，F(xiàn)IS。并將數(shù)據(jù)集D上的頻繁項目集表示為FI。 FI是所有塊本地頻繁項集的并集的子集，即FIFI1∪FI2∪…FIS。

推論：將頻繁K-項集提取前（K-1）個項作為前綴，將頻繁K-項集按照具有相同前綴原則進行劃分，劃分的塊數(shù)為前綴的個數(shù)。將得到的頻繁K-項集（fre-k）進行劃分，假設(shè)不同前綴個數(shù)為s個，記為fre-k ={fre-k1，fre-k2，…，fre-ks}，在劃分后的每個塊中除前綴外計算頻繁2-項集，每個塊中得到的頻繁2-項集分別為fre-k1-2，fre-k2-2，…，fre-ks-2，將得到的每個頻繁2-項集加上該塊的前綴取并集就是所有的頻繁（K+1）-項集，并且該頻繁2-項集的支持度就是頻繁-（K+1）項集的支持度。

證明：每一個頻繁項集中的項都是順序存放的，所以前綴是唯一的，對于每個塊中的頻2-項集會存在重復(fù)的情況，但是加上前綴后的頻繁K-項集就是唯一的。在任何一個頻繁項集塊fre-ki中，其中1≤i≤s，如果存在頻繁2-項集，那么fre-ki-2的支持度一定大于最小支持度，所以加上前綴后一定是頻繁K-項集。因為每個塊得到的頻繁K-項集都是唯一的，所以對于非頻繁2-項集，他也不會對應(yīng)頻繁K-項集。

在Spark框架的具體實現(xiàn)為首先調(diào)用map（）將所有的前綴提取得到一個RDD，也就是將每個頻繁項中的第（K-1）個元素提取出來得到一個集合。該RDD是由兩部分組成，第一部分是提取出的前綴，第二部分是一個哈希表，包含剩余的前綴以及該頻繁2-項集對應(yīng)的項集ID。然后調(diào)用reduceByKey（）將相同的前綴進行合并，這里的前綴就是要合并的key值，合并時相同前綴的RDD被合并成一個RDD，合并后的RDD包含兩個部分，分別是相同的key值和所有value中的哈希表拼接成一個大的哈希表。

下面給出前綴劃分策略的具體示例，圖5為圖4中得到的頻繁2-項集使用前綴劃分策略進行劃分的過程示例。

對于圖4所示獲得的頻繁2-項集中前綴為A的2-項集{{A，B}：（1，2，3），{A，D}：（1，3），{A，E}：（2，3）}進行前綴提取得到{A，{B：（1，2，3）}}，{A，{D：（1，3）}}，{A，{E：（2，3}}，這個過程調(diào)用Spark提供的轉(zhuǎn)換算子map（）。然后進行規(guī)約得到{A，{B ：（1，2，3），D：（1，3） ，E：（2，3）}}，這個過程調(diào)用Spark提供的行動算子reduceByKey（）進行合并。

2.6 計算頻繁K（K>2）-項集

獲取頻繁K-項集首先要判斷獲得的頻繁項集是否為空，若為空，則結(jié)束運行。若不為空，繼續(xù)進行前綴劃分，將在各個計算節(jié)點中針對具有相同前綴的項集，并行地以自底向上的形式進行迭代，用頻繁K-項集產(chǎn)生頻繁（K+1）-項集。即在每個節(jié)點中，對分配到該節(jié)點的項集進行前綴劃分計算，產(chǎn)生不同前綴對應(yīng)的所有項集，之后對除前綴外的所有項集進行計算頻繁-2項集，將滿足條件的頻繁2-項集添加前綴得到頻繁K-項集，并將計算結(jié)果保存到內(nèi)存中。

獲取頻繁3-項集，首先對頻繁2-項集進行前綴劃分，劃分后提取前綴，將除前綴外剩余的部分稱為后綴，對后綴計算頻繁2-項集，將得到的頻繁2-項集加上前綴得到頻繁3-項集。對于圖5中得到的前綴劃分后的結(jié)果，將前綴為A的項集除去前綴的部分得到{B ：（1，2，3），D：（1，3） ，E：（2，3）}再次進行2-項集的計算分別得到{{B，D}：（1，3），{B，E}：（2，3），{D，E}：（3）}。然而對于獲得的2-項集中{D，E}的支持度小于給定的最小支持度2，所以將其過濾掉。所以得到的頻繁2-項集為{{B，D}：（1，3），{B，E}：（2，3）}，所以只要將前綴A分別加入到{B，D}，{B，E}中就可以得到頻繁3-項集{{A，B，D}：（1，3），{A，B，E}：（2，3）}。

同理，對于頻繁K-項集的計算，首先提取頻繁（K-1）-項集前綴，這時前綴的個數(shù)為（K-2）個，提取前綴后對剩余部分計算頻繁2-項集，將前綴添加到頻繁2-項集中得到頻繁K-項集。

3 算法實現(xiàn)

3.1 數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理將原始數(shù)據(jù)的儲存從水平型數(shù)據(jù)庫轉(zhuǎn)換成垂直型數(shù)據(jù)庫，并用位圖保存TIDSet。針對水平型數(shù)據(jù)庫的數(shù)據(jù)集，若數(shù)據(jù)集本身就是以垂直型數(shù)據(jù)進行儲存，計算每行中存在的TID即可。這個過程是將數(shù)據(jù)集進行存儲方式的轉(zhuǎn)換，同時過濾掉支持度小于最小支持度的數(shù)據(jù)，需要對整個數(shù)據(jù)庫進行讀取，所以該過程中網(wǎng)絡(luò)傳輸量會增大。數(shù)據(jù)預(yù)處理的偽代碼如算法1所示。

算法1 數(shù)據(jù)預(yù)處理算法

輸入：原始數(shù)據(jù)集路徑path

輸入：最小支持度minsup

輸出：滿足最小支持度并以位圖儲存的頻繁1-項集fre_1

1.javaRDD←sc.textFile（path）

2.map←new HashMap

3.for row∈javaRDD do

4.count←1 //設(shè)置行號

5.set1←row.split（“”）

6.for i∈set.length do

7.if set1[i]∈map.key then//item已存在

8.map.put（set1[i]，set1[i].values+count）

9.else //item不存在

10.map.put（set1[i]，count）

11.count++

12.for i∈map do

13.s←s+i.key+i.value+”＼＼n”

14.fre_1←new HashMap（）

15.for i in map.size（） do

16.if s[1：].size>minsup do //頻繁1-項集

17.fre_1.add（s[0]，BitSet（s[1：]）.size） //轉(zhuǎn)換為位圖形式

18.return fre_1

3.2 計算頻繁2-項集

計算頻繁2-項集中求交集是采用基于位圖計算的方式，提高了算法的效率，并將中間結(jié)果保存在內(nèi)存中，方便后續(xù)頻繁K-項集的計算。計算頻繁2-項集的偽代碼如算法2所示。

算法2 計算頻繁2-項集算法

輸入：預(yù)處理得到的頻繁1-項集fre_1

輸入：最小支持度minsup

輸出：滿足最小支持度并以位圖儲存的頻繁2-項集fre_2

1.fre_2←new HashMap（）

2.while i∈fre_1 do

3.bitset2← i.values（）

4.while j∈fre_1 and i

5.bitset3←j.values（）

6.bitset4←bitset2&&bitset3

7.if bitset4.size（）≥minsup do //頻繁2-項集

8.fre_2.put（fre_1.get（i）+“，”+fre_1.get（j），bs4）

9.return fre_2

3.3 計算頻繁K-項集（K>2）

計算頻繁K-項集需要對頻繁（K-1）-項集進行前綴劃分操作，該操作會導(dǎo)致網(wǎng)絡(luò)開銷，因為在調(diào)用reduceByKey算子時會觸發(fā)shuffle，這個過程無法避免。但是因為求得的頻繁（K-1）-項集都是保存在內(nèi)存中的，所以后續(xù)劃分時不需要再次從數(shù)據(jù)庫或者HDFS中讀取，這樣減少很多網(wǎng)絡(luò)開銷。計算頻繁K-項集的偽代碼如算法3所示。

算法3 計算頻繁K-項集（K>2）算法

輸入：計算得到的頻繁（K-1）-項集fre_k-1

輸入：最小支持度minsup

輸出：滿足最小支持度的頻繁K-項集fre_k

1.map=new HashMap（）

2.while fre_k-1.key hasNext

3.pre=fre_k-1.key[0：K-2]//提取K-2個前綴

4.suf=new HashMap（）

5.suf.put（fre_k-1.key-pre，fre_k-1.get（fre_k-1.key）） //除前綴項外都作為后綴

6.map.put（pre，suf）

7.javaRDD=sc.parallelizePairs（（List）map）

8.map1=new HashMap（）

9.mappreadd←javaRDD.reduceByKey（i.suf+j.suf）//前綴相同時后綴合并

10.fre2←Getfre_2（mappreadd.value.key，minsup））

11.fre_k=mappreadd.key+fre_2

12.return fre_k

3.4 算法復(fù)雜度分析

3.4.1 I/O開銷

在Spark計算框架中，I/O消耗主要包含網(wǎng)絡(luò)I/O消耗和磁盤I/O消耗。在本算法中，主要的I/O和網(wǎng)絡(luò)消耗的步驟發(fā)生在計算頻繁K（K>2）-項集。

計算頻繁K-項集用到前綴劃分的剪枝技術(shù)，而前綴劃分階段會調(diào)用到reduceByKey算子觸發(fā)shuffle過程，從而產(chǎn)生磁盤I/O和網(wǎng)絡(luò)開銷。對于Spark的shuffle而言，map端需要把不同的key值及其對應(yīng)的value值發(fā)送到不同機器上，reduce端接收到map的數(shù)據(jù)后采用Aggregator機制將鍵值對保存到HashMap中，而Aggregator的操作是在磁盤上進行的，所以會產(chǎn)生大量的磁盤I/O。由于對數(shù)據(jù)進行了清洗并且得到的頻繁K-項集中隨著K值的增大，項集大小逐漸變小，磁盤寫入需要的I/O會逐漸變小，后面實驗得到證明。

3.4.2 時間開銷

為了描述可能的時間的開銷，定義符號及含義如表1所示。

時間開銷主要包含位運算消耗，Spark自身框架的維護消耗，I/O網(wǎng)絡(luò)消耗。由于位運算消耗的時間很短所以忽略不計，所以時間代價主要與當(dāng)前集群的網(wǎng)絡(luò)質(zhì)量和I/O所使用的存儲介質(zhì)有關(guān)。

時間代價如公式（1）所示。

數(shù)據(jù)預(yù)處理是整個算法最主要的CPU消耗。CPU的開銷如公式（2）所示，這個公式表示的是CPU平均的消耗情況。由于每個節(jié)點所分配到的數(shù)據(jù)量難以確定，但是在分發(fā)過后的數(shù)據(jù)規(guī)模都是確定的。

I/O產(chǎn)生的最主要的開銷是前綴劃分中對前綴進行合并觸發(fā)shuffle導(dǎo)致的，Spark的shuffle過程既會產(chǎn)生網(wǎng)絡(luò)開銷也會產(chǎn)生磁盤開銷。網(wǎng)絡(luò)I/O開銷如公式3所示，磁盤I/O開銷如公式4所示。

4 數(shù)值實驗與結(jié)果分析

4.1 實驗環(huán)境

使用2臺服務(wù)器，配置均為3T硬盤，128G物理內(nèi)存，第六代Intel處理器。操作系統(tǒng)是 Ubuntu16.04，集群參數(shù)中Hadoop的堆大小設(shè)置為25G。Spark的executor內(nèi)存設(shè)置為25G。開發(fā)語言采用Java語言。開發(fā)工具采用IntelliJ IDEA（COMMUNITY 2018.2）進行開發(fā)、編譯和運行，Hadoop采用hadoop-2.5.1 版本，JDK采用jdk1.7.0_71，Scala采用scala-2.11.8，Spark采用spark-2.1.0-bin-hadoop2.7版本。

4.2 數(shù)據(jù)集

在本實驗中，使用了FIMI倉庫的Mushroom[21]和Webdocs[9]數(shù)據(jù)集，是兩個被廣泛用于關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)集。數(shù)據(jù)集的參數(shù)如表2所示，常用于比較算法的性能。

4.3 算法效率對比

這里進行了2種比較，為了保證挖掘出的所有頻繁項集都不為空，2種比較都選擇最大關(guān)聯(lián)規(guī)則長度為5的情況。首先是本文提出的Sp-IEclat算法和MapReduce框架下的Eclat算法之間的比較，選擇比較的數(shù)據(jù)集為Mushroom，比較結(jié)果如圖6所示。

由圖6可以看出，在數(shù)據(jù)集較大時，本文提出的算法運行的效率要遠高于Eclat算法在MapReduce框架下的運行效率。當(dāng)支持度越來越小時，挖掘出的頻繁項集越來越多，Sp-IEclat算法會將中間結(jié)果存放在內(nèi)存中，而且位圖求交運算代替集合求交集運算，會節(jié)省大量時間。

其次，在Spark框架下將本文提出的Sp-IEclat算法和FP-Growth算法及Eclat算法進行比較。選擇比較的數(shù)據(jù)集是Webdocs數(shù)據(jù)集。Spark中包含了一個可以提供機器學(xué)習(xí)的功能的程序庫，其中算法FP-Growth就是調(diào)用了Spark MLlib中的FP-Growth算法的接口。實驗結(jié)果如圖7所示。

在數(shù)據(jù)集較大的環(huán)境下，可以看到本文提出的Sp-IEclat算法的運行速度遠大于FP-Growth算法和Eclat算法。隨著支持度越來越小，產(chǎn)生的頻繁項集越來越多時，Sp-IEclat算法效率要更明顯一點。對于FP-Growth算法來說，Sp-IEclat算法不需要產(chǎn)生中間的樹型數(shù)據(jù)結(jié)構(gòu)，可節(jié)省大量時間。對于Eclat算法來說，Sp-IEclat算法求交集時采用位圖計算，并且使用前綴劃分使求頻繁K-項集時遍歷項集數(shù)目變少，提高了算法效率。

4.4 集群性能分析

在這里使用webdocs.dat數(shù)據(jù)集，在支持度為250K的情況下對不同算法進行測試，如圖8～10為使用集群監(jiān)控軟件Ganglia監(jiān)測集群CPU占用率情況。

以上3幅圖片給出了不同算法的CPU占用率情況。對于CPU占用率，此集群環(huán)境下，Sp-IEclat算法和Eclat算法的CPU占用率比較低，相對于FP-Growth算法來說，F(xiàn)P-Growth算法CPU的占用率最大將近80%，而Sp-IEclat算法和Eclat算法的CPU占用量最大不到15%。原因為Sp-IEclat算法和Eclat算法都采用垂直數(shù)據(jù)結(jié)構(gòu)，不需要多次掃描數(shù)據(jù)庫，并且Sp-IEclat算法中采用的位圖計算方法可以有效的減少CPU運行壓力;而FP-Growth算法采用水平數(shù)據(jù)庫，并且需要構(gòu)建生成樹，在算法初始化的時候造成較大的CPU負載壓力。

如圖11～13為使用集群監(jiān)控軟件Ganglia監(jiān)測集群I/O占用情況。

以上3幅圖片給出了不同算法的I/O占用情況。對于集群的I/O負載，F(xiàn)P-Growth算法I/O負載壓力主要出現(xiàn)在生成規(guī)則樹中，最大達到9000kB，當(dāng)支持度低的時候生成樹可能會非常大，此時需要大量的進行磁盤交換，從而導(dǎo)致I/O負載增大。Eclat算法有兩次負載峰值，達到250kB，因為頻繁4-項集和頻繁5-項集的傳輸過程TIDSet長度比較長，傳輸數(shù)據(jù)大，I/O負載增大。Sp-IEclat算法在整個算法中有一次負載峰值，僅僅不到20kB，因為要進行頻繁2-項集的前綴劃分，即使后面也要進行前綴劃分操作，但是占用量肯定要小于頻繁2-項集的前綴劃分的I/O負載，因此集合的I/O負載也顯著的降低。

5 結(jié) 論

本文提出了一種基于Spark框架的關(guān)聯(lián)規(guī)則挖掘算法。本算法只需進行一次數(shù)據(jù)庫遍歷，并基于位圖進行計算以及采用了前綴劃分的剪枝方法，從而提高了運行效率，減少了集群的CPU占用率和I/O負載壓力。通過實驗可得出在大數(shù)據(jù)下，較低支持度中也能保持算法以較快的速度和較低的CPU占用量及集群I/O負載來執(zhí)行關(guān)聯(lián)規(guī)則。而在較高的支持度下也能保持算法的高效。此算法使用范圍比較廣，可以用于大數(shù)據(jù)挖掘環(huán)境中。下一步考慮將該算法推廣到不確定數(shù)據(jù)挖掘環(huán)境下。

參 考 文 獻：

[1] MASUM， HOSEYNI Z. Mining Stock Category Association on Tehran Stock Market [J]. Soft Computing， 2019， 23（4）：1165.

[2] LEUNG K H， LUK C C， CHOY K L， et al. A B2B Flexible Pricing Decision Support System for Managing the Request for Quotation Process under Ecommerce Business Environment [J]. International Journal of Production Research， 2019， 57（20）：6528.

[3] GUAN V X， PROBST Y C， NEALE E P， et al. Identifying Usual Food Choices at Meals in Overweight and Obese Study Volunteers：Implications for Dietary Advice[J]. British Journal of Nutrition， 2018， 120（4）：472.

[4] HAN J， PEI J. Mining Frequent Patterns without Candidate Generation[C]// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data， May 16-18， 2000， Dallas， Texas， USA. ACM， 2000：1.

[5] ZAKI M J， PARTHASARATHY S， OGIHARA M， et al. New Algorithms for Fast Discovery of Association rules[C]// International Conference on Knowledge Discovery and Data Mining. AAAI Press， 1997：283.

[6] PHILIPPE F V， JERRY C L， BAY V， et al. A Survey of Itemset Mining[J]. Wiley Interdisciplinary Reviews Data Mining & Knowledge Discovery， 2017， 7（4）：1.

[7] LI Z F， LIU X F， CAO X. A Study on Improved Eclat Data Mining Algorithm[C]//Advanced Materials Research. Trans Tech Publications Ltd， 2011， 328：1896.

[8] ZHABG C K， TIAN P， ZHANG X D， et al. Fast Eclat Algorithms Based on Minwise Hashing for Large Scale Transactions[J].IEEE Internet Of Things Journal，2019，6（2）：3948.

[9] MA Z Y， YANG J C， ZHANG T X， et al. An Improved Eclat Algorithm for Mining Association Rules Based on Increased Search Strategy[J]. International Journal of Database Theory and Application， 2016， 9（5）：251.

[10]VERMA N， SINGH J. An Intelligent Approach to Big Data Analytics for Sustainable Retail Environment using Apriori–map Reduce Framework [J]. Industrial Management & Data Systems， 2017， 117（7）：1503.

[11]CHAVAN K， KULKARNI P， GHODEKAR P， et al. Frequent Itemset Mining for Big Data[C]// International Conference on Green Computing and Internet of Things（ICGCIoT）， Noida， IEEE， 2015：1365.

[12]SUVALKA B， KHANDELWAL S， PATEL C. Revised ECLAT Algorithm for Frequent Itemset Mining[M]// Information Systems Design and Intelligent Applications. Springer India.2016：219.

[13]CHON K W， KIM M S. BIGMiner：A Fast and Scalable Distributed Frequent Pattern Miner for Big Data[J]. Cluster Computing， 2018， 21（3）：1507.

[14]WANG L. An Efficient Algorithm of Frequent Itemsets Mining Based on Map Reduce [J]. Journal of Information & Computational Science， 2014， 11（8）：2809.

[15]丁勇， 朱長水， 武玉艷. 一種基于Hadoop的關(guān)聯(lián)規(guī)則挖掘算法[J]. 計算機科學(xué)， 2018， 45（S2）：419.

DING Yong， ZHU Changshui，WU Yuyan. Association Rule Mining Algorithm Based on Hadoop[J]. Computer Science. 2018，45（S2）：409.

[16]LI H， WANG Y， ZHANG D ， et al. Pfp：Parallel Fp-growth for Query Recommendation[C]// Acm Conference on Recommender Systems. ACM， 2008 ：107.

[17]QIU H， GU R， YUAN C， et al. YAFIM：A Parallel Frequent Itemset Mining Algorithm with Spark[C]// Parallel & Distributed Processing Symposium Workshops. IEEE， 2014：1664.

[18]RATHEE S， KASHYAP A， KAUL M. R-Apriori：An Efficient Apriori based Algorithm on Spark[C]// Proceedings of the 8th Workshop on Ph.D. Workshop in Information and Knowledge Management. ACM， 2015：27.

[19]WEN H， KOU M， HE H， et al. A Spark-based Incremental Algorithm for Frequent Itemset Mining[C]// Proceedings of the 2018 2nd International Conference on Big Data and Internet of Things October 2018：53.

[20]SHI X， CHEN S， YANG H. DFPS：Distributed FP-growth Algorithm Based on Spark[C]// 2017 IEEE 2nd Advanced Information Technology， Electronic and Automation Control Conference（IAEAC）. IEEE， 2017：1725.

[21]GASSAMA A D D ， CAMARA F ， NDIAYE S. S-FPG：A Parallel Version of FP-Growth Algorithm Under Apache SparkTM[C]// IEEE International Conference on Cloud Computing & Big Data Analysis. IEEE， 2017：98.

[22]LI C， HUANG X. Research on FP-Growth Algorithm for Massive Telecommunication Network Alarm Data Based on Spark[C]// IEEE International Conference on Software Engineering & Service Science. IEEE， 2017：857.

（編輯：溫澤宇）