Sp-IEclat：一種大數(shù)據(jù)并行關(guān)聯(lián)規(guī)則挖掘算法

李成嚴(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)存計(jì)算的Spark框架，減少磁盤輸入輸出降低I/O負(fù)載，使用位圖運(yùn)算降低交集的時(shí)間代價(jià)并減少CPU占用，采用前綴劃分的剪枝技術(shù)減少求交集運(yùn)算的數(shù)據(jù)量，降低運(yùn)算時(shí)間。使用mushroom數(shù)據(jù)集和webdocs數(shù)據(jù)集在兩種大數(shù)據(jù)平臺下實(shí)驗(yàn)，結(jié)果表明，Sp-IEclat算法的時(shí)間效率優(yōu)于MapReduce框架下的Eclat算法及Spark框架下的FP-Growth算法和Eclat算法。從對集群的性能監(jiān)控得到的數(shù)值表明，同Spark框架下的FP-Growth算法和Eclat算法相比，Sp-IEclat算法的CPU占用和I/O集群負(fù)載都較小。

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

DOI：10.15938/j.jhust.2021.04.015

中圖分類號：TP399

文獻(xiàn)標(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在其進(jìn)行迭代的過程將會產(chǎn)生大量的候選集并且放在內(nèi)存中，當(dāng)處理大數(shù)據(jù)集時(shí)會導(dǎo)致內(nèi)存不足，而且Apriori需要重復(fù)的讀取數(shù)據(jù)庫，將會給系統(tǒng)I/O造成巨大壓力;FP-Growth算法將數(shù)據(jù)庫的掃描次數(shù)壓縮到了2次，但是在生成樹結(jié)構(gòu)的時(shí)候會有額外的開銷，當(dāng)數(shù)據(jù)集的支持度較低時(shí)，將會產(chǎn)生大量的節(jié)點(diǎn)，導(dǎo)致內(nèi)存不足;Eclat算法只讀取一次數(shù)據(jù)庫，但是取交集時(shí)會有大量的候選集存儲在內(nèi)存中，會耗費(fèi)大量時(shí)間。

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

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

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

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

本文的主要工作如下：

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

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

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

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

1 相關(guān)概念

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

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

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

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

1.2 SPARK框架

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

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)換成了使用集合運(yùn)算的方式。對于小數(shù)據(jù)集，集合運(yùn)算的速度將會很快。但當(dāng)數(shù)據(jù)集變大的時(shí)候，取交集的運(yùn)算的代價(jià)會變得比較大，也會產(chǎn)生比較大的中間數(shù)據(jù)量。Eclat算法對于大型數(shù)據(jù)集數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘時(shí)時(shí)間效率不是很理想，所以將Eclat算法進(jìn)行優(yōu)化使其更加適用于挖掘大型數(shù)據(jù)集。

2.2 SP-IECLAT算法概述

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

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

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

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

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

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

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

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

2.4 計(jì)算頻繁2-項(xiàng)集

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

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

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

2.5 前綴劃分策略

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

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

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

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

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

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

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

2.6 計(jì)算頻繁K（K>2）-項(xiàng)集

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

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

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

3 算法實(shí)現(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ù)進(jìn)行儲存，計(jì)算每行中存在的TID即可。這個(gè)過程是將數(shù)據(jù)集進(jìn)行存儲方式的轉(zhuǎn)換，同時(shí)過濾掉支持度小于最小支持度的數(shù)據(jù)，需要對整個(gè)數(shù)據(jù)庫進(jìn)行讀取，所以該過程中網(wǎng)絡(luò)傳輸量會增大。數(shù)據(jù)預(yù)處理的偽代碼如算法1所示。

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

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

輸入：最小支持度minsup

輸出：滿足最小支持度并以位圖儲存的頻繁1-項(xiàng)集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-項(xiàng)集

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

18.return fre_1

3.2 計(jì)算頻繁2-項(xiàng)集

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

算法2 計(jì)算頻繁2-項(xiàng)集算法

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

輸入：最小支持度minsup

輸出：滿足最小支持度并以位圖儲存的頻繁2-項(xiàng)集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-項(xiàng)集

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

9.return fre_2

3.3 計(jì)算頻繁K-項(xiàng)集（K>2）

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

算法3 計(jì)算頻繁K-項(xiàng)集（K>2）算法

輸入：計(jì)算得到的頻繁（K-1）-項(xiàng)集fre_k-1

輸入：最小支持度minsup

輸出：滿足最小支持度的頻繁K-項(xiàng)集fre_k

1.map=new HashMap（）

2.while fre_k-1.key hasNext

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

4.suf=new HashMap（）

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

6.map.put（pre，suf）

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

8.map1=new HashMap（）

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

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

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

3.4.2 時(shí)間開銷

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

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

時(shí)間代價(jià)如公式（1）所示。

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

I/O產(chǎn)生的最主要的開銷是前綴劃分中對前綴進(jì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ù)值實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(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）進(jìn)行開發(fā)、編譯和運(yùn)行，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ù)集

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

4.3 算法效率對比

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

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

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

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

4.4 集群性能分析

在這里使用webdocs.dat數(shù)據(jù)集，在支持度為250K的情況下對不同算法進(jìn)行測試，如圖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%。原因?yàn)镾p-IEclat算法和Eclat算法都采用垂直數(shù)據(jù)結(jié)構(gòu)，不需要多次掃描數(shù)據(jù)庫，并且Sp-IEclat算法中采用的位圖計(jì)算方法可以有效的減少CPU運(yùn)行壓力;而FP-Growth算法采用水平數(shù)據(jù)庫，并且需要構(gòu)建生成樹，在算法初始化的時(shí)候造成較大的CPU負(fù)載壓力。

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

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

5 結(jié) 論

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

參 考 文 獻(xià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]. 計(jì)算機(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.

（編輯：溫澤宇）