Sp-IEclat：一種大數據并行關聯規則挖掘算法

李成嚴 辛雪 趙帥 馮世祥

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

關鍵詞：大數據;關聯規則挖掘;頻繁項集;Spark彈性分布式數據集;MapReduce框架

DOI：10.15938/j.jhust.2021.04.015

中圖分類號：TP399

文獻標志碼：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 引 言

關聯規則挖掘技術是數據挖掘中的重要組成部分，廣泛的應用在金融行業[1]，零售業市場營銷[2]及醫療[3]等領域。

關聯規則挖掘的經典算法有Apriori[4]算法，FP-Growth[5]算法及Eclat[6]算法。Apriori在其進行迭代的過程將會產生大量的候選集并且放在內存中，當處理大數據集時會導致內存不足，而且Apriori需要重復的讀取數據庫，將會給系統I/O造成巨大壓力;FP-Growth算法將數據庫的掃描次數壓縮到了2次，但是在生成樹結構的時候會有額外的開銷，當數據集的支持度較低時，將會產生大量的節點，導致內存不足;Eclat算法只讀取一次數據庫，但是取交集時會有大量的候選集存儲在內存中，會耗費大量時間。

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

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

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

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

本文的主要工作如下：

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

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

3）通過運行相關的實驗，與基于MapReduce下的Eclat算法和現有的一些基于Spark的關聯規則挖掘算法進行實驗比較。比較的內容為公共數據集下，不同支持度的挖掘時間性能表現。

本文其余部分構成如下：第2部分為介紹相關概念;第3部分介紹Sp-IEclat算法;第4部分描述本算法的具體實現，并做復雜度分析;第5部分進行數值實驗并對結果分析;最后給出結論。

1 相關概念

1.1 關聯規則

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

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

前綴共享樹：設兩個項集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}具有相同前綴{A，B}。

1.2 SPARK框架

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

2 Sp-IEclat算法

2.1 ECLAT算法

Eclat算法采用的數據結構是垂直數型數據結構，即數據形式為{item：TIDSet}的形式。如此轉換后，關聯規則的挖掘實際上轉換成了使用集合運算的方式。對于小數據集，集合運算的速度將會很快。但當數據集變大的時候，取交集的運算的代價會變得比較大，也會產生比較大的中間數據量。Eclat算法對于大型數據集數據的關聯規則挖掘時時間效率不是很理想，所以將Eclat算法進行優化使其更加適用于挖掘大型數據集。

2.2 SP-IECLAT算法概述

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

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

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

2.3 數據預處理

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

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

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

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

2.4 計算頻繁2-項集

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

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

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

2.5 前綴劃分策略

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

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

推論：將頻繁K-項集提取前（K-1）個項作為前綴，將頻繁K-項集按照具有相同前綴原則進行劃分，劃分的塊數為前綴的個數。將得到的頻繁K-項集（fre-k）進行劃分，假設不同前綴個數為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-項集會存在重復的情況，但是加上前綴后的頻繁K-項集就是唯一的。在任何一個頻繁項集塊fre-ki中，其中1≤i≤s，如果存在頻繁2-項集，那么fre-ki-2的支持度一定大于最小支持度，所以加上前綴后一定是頻繁K-項集。因為每個塊得到的頻繁K-項集都是唯一的，所以對于非頻繁2-項集，他也不會對應頻繁K-項集。

在Spark框架的具體實現為首先調用map（）將所有的前綴提取得到一個RDD，也就是將每個頻繁項中的第（K-1）個元素提取出來得到一個集合。該RDD是由兩部分組成，第一部分是提取出的前綴，第二部分是一個哈希表，包含剩余的前綴以及該頻繁2-項集對應的項集ID。然后調用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}}，這個過程調用Spark提供的轉換算子map（）。然后進行規約得到{A，{B ：（1，2，3），D：（1，3） ，E：（2，3）}}，這個過程調用Spark提供的行動算子reduceByKey（）進行合并。

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

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

獲取頻繁3-項集，首先對頻繁2-項集進行前綴劃分，劃分后提取前綴，將除前綴外剩余的部分稱為后綴，對后綴計算頻繁2-項集，將得到的頻繁2-項集加上前綴得到頻繁3-項集。對于圖5中得到的前綴劃分后的結果，將前綴為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）-項集前綴，這時前綴的個數為（K-2）個，提取前綴后對剩余部分計算頻繁2-項集，將前綴添加到頻繁2-項集中得到頻繁K-項集。

3 算法實現

3.1 數據預處理

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

算法1 數據預處理算法

輸入：原始數據集路徑path

輸入：最小支持度minsup

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

1.javaRDD←sc.textFile（path）

2.map←new HashMap

3.for row∈javaRDD do

4.count←1 //設置行號

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） //轉換為位圖形式

18.return fre_1

3.2 計算頻繁2-項集

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

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

輸入：預處理得到的頻繁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）-項集進行前綴劃分操作，該操作會導致網絡開銷，因為在調用reduceByKey算子時會觸發shuffle，這個過程無法避免。但是因為求得的頻繁（K-1）-項集都是保存在內存中的，所以后續劃分時不需要再次從數據庫或者HDFS中讀取，這樣減少很多網絡開銷。計算頻繁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 算法復雜度分析

3.4.1 I/O開銷

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

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

3.4.2 時間開銷

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

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

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

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

I/O產生的最主要的開銷是前綴劃分中對前綴進行合并觸發shuffle導致的，Spark的shuffle過程既會產生網絡開銷也會產生磁盤開銷。網絡I/O開銷如公式3所示，磁盤I/O開銷如公式4所示。

4 數值實驗與結果分析

4.1 實驗環境

使用2臺服務器，配置均為3T硬盤，128G物理內存，第六代Intel處理器。操作系統是 Ubuntu16.04，集群參數中Hadoop的堆大小設置為25G。Spark的executor內存設置為25G。開發語言采用Java語言。開發工具采用IntelliJ IDEA（COMMUNITY 2018.2）進行開發、編譯和運行，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 數據集

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

4.3 算法效率對比

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

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

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

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

4.4 集群性能分析

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

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

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

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

5 結 論

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

參 考 文 獻：

[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的關聯規則挖掘算法[J]. 計算機科學， 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.

（編輯：溫澤宇）