劉興建 原振文

摘要：隨著數(shù)據(jù)每天呈指數(shù)級增長，頻繁項集挖掘的效率和可伸縮性問題變得更加嚴重。因此，提出融合貝葉斯深度學習的計算機大數(shù)據(jù)頻繁項挖掘算法（Sequential growth），并在MapReduce框架上實現(xiàn)。為了測試算法的性能，在具有大型數(shù)據(jù)集的MapReduce框架上進行了不同方面的實驗。結(jié)果表明，Sequential growth算法具有良好的效率和可擴展性，尤其在處理大數(shù)據(jù)和長項目集時。

關(guān)鍵詞：頻繁模式挖掘;頻繁項集挖掘;MapReduce;貝葉斯深度學習;可擴展性

中圖分類號：TP301文獻標志碼：A

文章編號：2095-5383（2020）04-0038-05

Frequent Item Mining Algorithm of Computer Big Data

based on Bayesian Deep Learning

LIU Xingjian1， YUAN Zhenwen2

（1.Department of Computer Application Technology， Guangdong Business and Technology University， Zhaoqing 526040， China;2. Artillery Academy， National University of Defense Technology， Changsha 410111， China）

Abstract：

Frequent itemsets mining （FIM） is an important research topic because it is widely used in the real world to find frequent itemsets and mine human behavior patterns. As data grows exponentially every day， the efficiency and scalability issues of frequent itemset mining have become more serious. Therefore， a frequent item mining algorithm （Sequential growth） of computer big data that integrates Bayesian deep learning was porposed in this paper， and it was implemented on the MapReduce framework. In order to test the performance of the algorithm， experiments in different aspects were carried out on the MapReduce framework with large data sets. The results show that the Sequential growth algorithm has good efficiency and scalability， especially when processing large data and long itemsets.

Keywords：

frequent pattern mining; Frequent Itemset Mining（FIM）; MapReduce; Bayesian deep learning; scalability

頻繁模式挖掘（frequent pattern mining）是數(shù)據(jù)挖掘的最重要技術(shù)之一，它在各種領(lǐng)域中都有廣泛應用，例如市場籃分析、網(wǎng)頁點擊分析、患者路徑分析、DNA序列發(fā)現(xiàn)以及最近的無缺陷率改進等[1-4]。頻繁項集挖掘（Frequent Itemset Mining，F(xiàn)IM）問題首次出現(xiàn)在1995年，這是基于1994年的工作進行的擴展研究工作，Gupta等[5]介紹了2種基于Apriori的算法，分別稱為AprioriAll和AprioriSome，F(xiàn)IM問題逐漸引起了人們的廣泛關(guān)注，并成為數(shù)據(jù)挖掘的重要研究課題之一。Apriori算法也成為FIM最重要的概念之一，并以此為基礎(chǔ)拓展了許多算法[6-7]。FIM的另一種方法稱為Eclat。與Apriori使用自下而上的廣度優(yōu)先搜索策略不同，Eclat使用具有交集的廣度優(yōu)先方法來挖掘頻繁項集[8]。 Eclat將事務數(shù)據(jù)庫轉(zhuǎn)換為其垂直格式。 每個項目集與其封面（也稱為tid-list）一起存儲。垂直數(shù)據(jù)庫D′定義為：D′=ij，Cij=tidij∈X，tid，X∈D，其中Cij是ij的最新列表。在垂直數(shù)據(jù)庫中，項目集Y的支持可以通過與任意2個子集的tid-list相交來計算。它可被表示為supportY=∩tj∈YCij。

基于Apriori的算法以世代掃描方式挖掘頻繁項集。將串行Apriori算法應用于MapReduce框架的最便捷方法是MapReduce作業(yè)的多次迭代，以生成候選序列并掃描其在數(shù)據(jù)庫中的包含度。但是，MapReduce程序通常會從分布式文件系統(tǒng)（DFS）讀取輸入數(shù)據(jù)，并將輸出數(shù)據(jù)寫入DFS。基于MapReduce的Apriori FIM算法的開銷可能因為MapReduce作業(yè)的啟動和通信很昂貴。此外，與串行Apriori一樣，基于MapReduce的Apriori面臨的最關(guān)鍵挑戰(zhàn)之一就是昂貴的候選項目集生成和事務數(shù)據(jù)庫掃描。先前的研究表明，基于Apriori的算法在處理龐大的數(shù)據(jù)集或較長的事務長度時情況更為嚴峻[9]。為了減少MapReduce迭代，Eclat使用垂直數(shù)據(jù)庫格式為每個項目集構(gòu)造一個前綴樹。它以深度優(yōu)先的方式遍歷前綴樹，通過應用任意2個子集的交集來挖掘頻繁項集。但這種方式的垂直數(shù)據(jù)庫需要存儲在主存儲器中，這是處理大規(guī)模事務數(shù)據(jù)庫的另一個挑戰(zhàn)[10]。

本文提出融合貝葉斯深度學習的計算機大數(shù)據(jù)頻繁項挖掘算法（Sequential growth），算法采用字典順序的思想來構(gòu)造候選序列子集，以提高效率，節(jié)約成本。另外，Sequential growth以基于支持的廣度方法產(chǎn)生頻繁的項目集。在每個MapReduce迭代中，不常用的項目集都將被刪除。它顯著減少了每個MapReduce作業(yè)的內(nèi)存消耗和啟動時間。

1 頻繁項挖掘算法

1.1 基于MapReduce的Apriori算法

在MapReduce框架上采用串行Apriori算法的最自然的方法是將生成候選項目集和掃描內(nèi)容的過程轉(zhuǎn)換為map-reduce函數(shù)，然后迭代分配作業(yè)。以這種方式設(shè)計的算法歸為k相算法，因為一個長度為k的交易數(shù)據(jù)庫（k是最長的交易長度）最多需要k次迭代才能挖掘出完整的頻繁項目集。每個階段都包含2個MapReduce作業(yè)，1個用于生成候選項目集，另1個用于掃描數(shù)據(jù)庫以對它們的出現(xiàn)進行計數(shù)。這2個MapReduce作業(yè)將繼續(xù)交替運行，直到?jīng)]有生成任何候選項集為止[1-4]。由于MapReduce框架不適用于迭代過程，因此開發(fā)了基于MapReduce的Apriori算法的服務還原，以通過優(yōu)化挖掘完整頻繁項集所需的MapReduce階段數(shù)來降低啟動成本。Lin等[11]提出了2種算法，固定通行證聯(lián)合計數(shù)FPC和動態(tài)通行證計數(shù)DPC。以n和p為參數(shù)，F(xiàn)PC在p個相位后開始生成具有n個不同長度的候選對象，并在一個數(shù)據(jù)庫中對其頻率進行計數(shù)。DPC算法類似于FPC，不同之處在于n和p根據(jù)每個階段生成的候選數(shù)動態(tài)確定。

1.2 單相算法

一階段算法僅需要一項MapReduce作業(yè)即可挖掘所有頻繁項集。該算法在其map函數(shù)中逐行生成所有可能的交易子集（組合），并歸納reduce函數(shù)中的全局支持。像這樣的方法，候選項目集的增長率與交易的平均長度成指數(shù)比例。 例如，在平均長度為k且交易總數(shù)為T的情況下，單相需要生成平均C=T×2k-1個候選項目集。生成如此龐大的候選數(shù)據(jù)集，顯然無法滿足單相的可伸縮性，有學者提出的一項相關(guān)工作稱為單次通過計數(shù)SPC。SPC與FPC和DPC一起用于分析不同實現(xiàn)對性能的影響。

2 融合貝葉斯深度學習的順序增長

2.1 字典順序樹

根據(jù)已有算法，字典順序集定義為：設(shè)t=j1， j2，…， jk，t′=j′1， j′2，…， j′l。然后t

1）對于某些h，0≤h≤mink，l，對于r

2）k

另外，根據(jù)Apriori的定義，序列β=（b1，b2，…，bn）是α=（a1，a2，…，am）的子序列，而α是β的超序列，如果存在整數(shù)1≤j1

L=∩n-1l=0plαα∈ql（1）

其中：plα表示pl與α連接。

字典順序樹的功能是構(gòu)建候選生成空間。字典順序樹中的每個節(jié)點表示1個子序列，其高度與該級別上子序列的長度相對應。字典順序樹可以通過以序列增長方式迭代地將每個節(jié)點及其后綴串聯(lián)在一起來擴展。length-（k+1）序列是其父節(jié)點（length-k）和父級后綴項的串聯(lián)。例如，V=（s1，s2，s3）是S的長度3子序列。長度4子集V′={（s1，s2，s3，s4），（s1，s2，s3，s5），（s1，s2，s3，s6），…，（s1，s2，s3，in）}是通過將S中跟在s3之后的每個項目附加到V的末尾而獲得的。從長度1開始，到n可以從字典順序樹中檢索S的子序列。2020年第4期

劉興建

，等：

融合貝葉斯深度學習的計算機大數(shù)據(jù)頻繁項挖掘算法

成都工業(yè)學院學報http：//paper.cdtu.edu.cn/第23卷

2.2 貝葉斯深度學習

貝葉斯深度學習中的修剪策略也是設(shè)計高效FIM算法的重要因素。與單階段算法在一次迭代中生成交易數(shù)據(jù)庫的所有可能子集的方法不同，Sequential growth以1～k的基數(shù)迭代執(zhí)行以生成候選項目集。將候選項集生成的延遲稱為“惰性挖掘”，這是提出的算法的有效修剪策略。將Apriori屬性應用于字典順序樹，如果不經(jīng)常使用某個節(jié)點，則可以刪除所有子節(jié)點。Sequential growth減少了每次迭代的候選項目集的大小，并顯著減少了內(nèi)存消耗。因此，執(zhí)行可使數(shù)據(jù)適合主存儲器，以防止昂貴的上下文交換過程。 Sequential growth算法是根據(jù)字典順序樹的概念和惰性挖掘修剪策略設(shè)計的，并在MapReduce框架上實現(xiàn)以實現(xiàn)分布式執(zhí)行。

2.3 擴展序列增長方法用于軌跡模式挖掘

通常事務中的每個項目都可以分為2個項目集，1個前綴和1個后綴。因此，Sequential growth算法中建立字典順序樹的方法也可以應用于其他關(guān)聯(lián)規(guī)則挖掘算法來構(gòu)造其候選空間。本節(jié)提供了一種用于軌跡模式挖掘TPM的示例算法，該算法是Sequential growth的較小微調(diào)。由于TPM的研究問題不在本文討論范圍之內(nèi)，因此本文中的TPM問題得以簡化，以易于理解。軌跡記錄可以表示為Euclid Math TwoTA@=Euclid Math TwoSA@，Euclid Math TwoAA@，其中Euclid Math TwoSA@=ρ0，ρ1，…，ρn是n+1個移動位置的序列，而Euclid Math TwoAA@=μ1，μ2，…，μn是一組過渡時間，因此μi=Δti=ti-ti-1。軌跡數(shù)據(jù)庫

t=t1，t2，…，tm是一組軌跡。suppDEuclid Math TwoSA@是軌跡數(shù)據(jù)庫

t中Euclid Math TwoSA@的頻率。給定最小支持閾值smin和時間公差τ，如果suppDEuclid Math TwoSA@≥smin且每個μi∈Euclid Math TwoAA@的μi≤τ，則

Euclid Math TwoTA@=Euclid Math TwoSA@，Euclid Math TwoAA@頻繁，稱為T型。TPM是找到所有T-軌跡數(shù)據(jù)庫t中的模式Euclid Math TwoSA@，Euclid Math TwoAA@。采礦程序從發(fā)現(xiàn)所有“熱點”開始。該步驟類似于在Sequential growth算法中挖掘length-1項集，不同之處在于，如果后綴位置（當前點之后的移動位置）的過渡時間大于時間公差，則不會輸出這些位置。算法1包含該步驟的偽代碼。在算法1中，通過遍歷位置序列以截斷那些過渡時間大于時間容限的軌跡（第7至9行）。下一步包括通過反復應用字典順序樹的方法來挖掘所有T模式，以在每個mapreduce作業(yè)中將序列長度擴展一個。

算法1：GenHotSpot//生成熱點

Input：S：{t|t∈Si，t=<ρ0，…，ρn@μ1，…，μn>};

smin：integer;

τ：integer;

Output：L1：{ρ|ρ∈L1，ρ=};

C1：{c|c∈C1，c=};

Map Task（key，value）

1：for each t in Si do

2： loclist=t.split（“@”）[0].split（“，”）;

3： timelist=t.split（“@”）[1].split（“，”）;

4： for（k=0;k

5：tranTime=0;

6：len=k;

7：while（tranTime+=timelist[len]≤τ）do

8： len++;

9：end while

10：key=loclist[k];

11：if（len≥k）then

12： value=loclist.SubArray（k+1，len）;

13： value+=“@”;

14： value+=timelist.SubArray（k，len-1）;

15：end if

16：Output（key，value）;

17： end for

18：end for

3 實驗與分析

實驗是在由7臺機器組成的完全分布式集群環(huán)境中的Hadoop 1.2.1和jdk-7u6上執(zhí)行的。每個內(nèi)核包含6個內(nèi)核，分別為Intel（R）I7-4930 3.4 GHz CPU和64 G RAM。所有機器都在Ubuntu 12.04操作系統(tǒng)上運行。一臺機器作為主機和從機，其他機器僅作為從機。實驗中使用了由IBM Quest綜合數(shù)據(jù)生成器生成的綜合數(shù)據(jù)集，合成數(shù)據(jù)集的參數(shù)分別是：平均交易長度T，平均最大頻繁項集長度I和交易總數(shù)D。

首先，使用不同大小的事務數(shù)據(jù)庫來測試Sequential growth算法的可伸縮性。綜合事務數(shù)據(jù)集的大小從50 KB到8 000 KB。對于所有數(shù)據(jù)集，T=10，I=4，最小支持δ=0.1%。結(jié)果表明Sequential growth提供了良好的可伸縮性。斜率（處理時間的Δ/事務大小的Δ）表示增加1 KB事務所需的處理時間。當事務大小從4 000 KB增長到6 000 KB時，處理時間就開始大量增加。即使這樣，Sequential growth算法仍具有在合理時間內(nèi)處理此類大型數(shù)據(jù)集的能力。為了進一步驗證算法處理大數(shù)據(jù)的能力，使用1 000萬到2 000萬筆交易的數(shù)據(jù)集執(zhí)行Sequential growth，其中T=6，最小支持δ=1%。結(jié)果如圖1所示，它再次確認了Sequential growth的良好可伸縮性。

除了大量的事務外，廣泛的事務長度是FIM處理大數(shù)據(jù)的另一個挑戰(zhàn)。接下來，繼續(xù)驗證Sequential growth可以通過在第2次MapReduce迭代后均勻劃分分區(qū)并通過其有效的修剪策略來解決此問題，使用2%、4%和8%的最低支持來執(zhí)行具有不同平均交易時間的Sequential growth。圖2顯示的結(jié)果是，Sequential growth在處理從最短的3 B到最長的107 B處理過程中都是高效且可擴展的。Sequential growth被設(shè)計為能夠與輸入文件平均分區(qū)。在MapReduce作業(yè)的第2次迭代之后，Sequential growth將1條很長的線分成幾條較短的線。因此，輸入數(shù)據(jù)集能夠被分區(qū)并平均分配給每個映射器。這樣可以防止進程等待繁瑣的映射程序。該部分的代碼在算法2的第21～25行中進行了說明。另一個觀察結(jié)果是，當平均交易時長從35 s增加到40 s時，用于2%最小支持的處理時間增加了3.4倍。但是，對于最低支持8%。這是因為Sequential growth的“惰性挖掘”修剪策略生效。每

次MapReduce迭代期間使用的最小支持閾值越高，

修剪掉的項目集越多。實驗結(jié)果證明，基于廣度支持的修剪策略是提高序列增長性能的重要因素，尤其是在處理長事務時。

為了進一步評估本文算法，進行了幾次實驗，以與其他2種基于Apriori的算法MR-Apriori和One-Phase進行比較。首先研究從10 KB到2 000 KB不同大小的事務數(shù)據(jù)集的3種算法的性能。對于所有數(shù)據(jù)集，T均為10，最小支持δ為0.1%。結(jié)果如圖3所示，當數(shù)據(jù)集的大小>50 KB時，MR-Apriori的執(zhí)行失敗。像串行Apriori一樣，MR-Apriori仍需要重復運行1個MapReduce作業(yè)以生成候選項目集，而另1個運行以掃描數(shù)據(jù)庫。即使在MapReduce框架上實現(xiàn)算法以進行分布式執(zhí)行，當數(shù)據(jù)集的大小變得巨大時，內(nèi)存使用和計算成本仍然可能非常昂貴。此外，在250 KB之后，單相處理時間顯著增加。在事務大小為250 KB時，“單階段”的執(zhí)行時間大約是“序列增長”的執(zhí)行時間的2倍，而在2 000 KB時，它的執(zhí)行時間要高出3倍以上?；诮Y(jié)果，本文算法在處理比較MR-Apriori和One-Phase的大型數(shù)據(jù)集時效率更高。

圖4顯示了使用10 KB合成數(shù)據(jù)集和不同級別的平均交易長度的三種算法之間的性能比較。即使在相對較短的數(shù)據(jù)集中處理時，單相的性能更好，但

當事務長度>14時，單相的運行時間會大大增加。原因是映射函數(shù)生成的中間數(shù)據(jù)的大小一階段算法的數(shù)量與交易時間成指數(shù)比例。執(zhí)行無法容納到主存儲器中，因此，當事務長度變長時，單階段的性能效率低下，甚至不可行。

單相和序列增長算法都挖掘頻繁項集，而無需重復掃描整個交易數(shù)據(jù)庫。2種算法之間的關(guān)鍵區(qū)別在于，“一階段”可在單個MapReduce作業(yè)中生成事務數(shù)據(jù)庫的所有可能子集。相反，Sequential growth以基于支持的廣度方法（惰性挖掘）產(chǎn)生頻繁的項集。在以上實驗的基礎(chǔ)上，進一步比較了Sequential growth和One-Phase算法生成的子集的處理時間和總數(shù)。對于“單階段”，執(zhí)行時間和子集的大小都顯著增長，同時平均交易時間也增加了。當平均交易長度=6時，“單階段”生成的項目集的總數(shù)是“序列增長”生成的總數(shù)的2倍。但是，當平均交易時長增加到18時，它大約大了172倍。結(jié)果證實了先前的觀察，“惰性挖掘”提供了一種有效的Sequential growth修剪策略，尤其是在處理平均交易時長較長的數(shù)據(jù)集時。

除了MapReduce-Apriori和One-Phase，還比較了分布式FIM算法BigFIM的最新成果。為了建立實驗，從BigFIM項目下載源代碼并進行相應的構(gòu)建。首先，嘗試比較BigFIM和Sequential growth在不同規(guī)模的數(shù)據(jù)集（從50 KB到4 000 KB）下的執(zhí)行性能。對于所有數(shù)據(jù)集，T均為10，最小支持δ為0.1%，2種算法的映射器數(shù)量均為42。對于BigFIM，前綴樹的深度為3。

圖5顯示Sequential growth優(yōu)于BigFIM。請注意，由于BigFIM無法完成生成k-FI的過程，因此即使提出的算法能夠處理更大的數(shù)據(jù)集，結(jié)果中顯示的最大事務大小仍為6 000 KB。根據(jù)觀察，BigFIM的較長執(zhí)行時間主要來自生成k-FI的步驟。 BigFIM改用類似于One-Phase的Apriori算法，以生成k長的前綴項集（在本實驗中為3），然后切換到Dist-Eclat算法以繼續(xù)挖掘階段。因此，在生成前綴步驟期間，BigFIM會面臨相同的單相問題。通過使用真實數(shù)據(jù)集BMSWebView1（Gazelle）比較兩種算法的執(zhí)行時間以及最低支持水平的變化，進行了第二項實驗以測試修剪策略的影響。 BMSWebView1包含來自電子商務的點擊流數(shù)據(jù)的59 601筆交易。序列的平均長度為2.42個項目，標準差為3.22。圖6顯示了最小支持δ從0.1%到1%的執(zhí)行時間。以0.1%的最低支持執(zhí)行，BigFIM比Sequential growth更快。盡管如此，與BigFIM相比，Sequential growth的處理時間從26%減少到47%，最小支持大于0.1%。那是因為貝葉斯深度學習的“惰性挖礦”修剪策略生效。因此，較大的δ值將通過在每次MapReduce迭代期間減少更多的不頻繁項集而從Sequential growth的修剪策略中獲得更多收益。

4 結(jié)論

云計算提供了一種在大數(shù)據(jù)上挖掘頻繁項目集的解決方案。效率和可伸縮性對于設(shè)計用于處理此類大型數(shù)據(jù)集的FIM算法至關(guān)重要。但是，當前的分布式FIM算法通常會遇到產(chǎn)生大量中間數(shù)據(jù)或掃描整個交易數(shù)據(jù)庫以識別頻繁項集的問題。本文提出了融合貝葉斯深度學習的計算機大數(shù)據(jù)頻繁項挖掘算法，展示了Sequential growth算法運用字典順序的思想來構(gòu)造候選序列子集，而無需

在事務數(shù)據(jù)庫上進行詳盡搜索，說明廣度的“惰性挖掘”修剪策略可有效消除大量中間數(shù)據(jù)的生成，因此，算法的執(zhí)行可以更好地適合主內(nèi)存。實驗結(jié)果證明，Sequential growth在挖掘大數(shù)據(jù)集頻繁項集的效率和可伸縮性方面優(yōu)于現(xiàn)有算法。此外，本文還提供了一個示例算法，以演示可以輕松修改Sequential growth，以使其他關(guān)聯(lián)規(guī)則挖掘算法適應MapReduce框架。

參考文獻：

[1] 高騰飛，劉勇琰，湯云波. 面向時間序列大數(shù)據(jù)海量并行貝葉斯因子化分析方法[J]. 計算機研究與發(fā)展，2019，56（7）：1567-1577.

[2] 王來兵. 基于貝葉斯與生成式對抗網(wǎng)絡的手寫字文本識別算法[J]. 黑龍江工業(yè)學院學報（綜合版），2019（8）：31-35.

[3]姜斌，趙梓良，黃灝. 基于反貝葉斯學習的WDMS光譜自動識別研究[J]. 光譜學與光譜分析，2019，39（6）：12-20.

[4] 來純曉，武振國，金松林. 基于BP神經(jīng)網(wǎng)絡的小麥抗寒性模型構(gòu)建[J]. 河南科技學院學報（自然科學版），2019（3）：43-49.

[5]GUPTA R K，AGRAWAL D P. Improving the performance of association rule mining algorithms by filtering insignificantTransactions Dynamically [J]. Asian Journal of Information Management，1994，3（1）：7-17.

[6]ARYABARZAN N， MINAEI-BIDGOLI B， TESHNEHLAB?M. negFIN： an efficient?algorithm for fast mining frequent itemsets[J]. Expert Systems with Applications，2018，105（6）：11-22.

[7] WU S，WANG M，ZOU Y. Research on internet information mining based on agent algorithm[J]. Future Generation Computer Systems，2018，86（3）：56-62.

[8] NJAH H，JAMOUSSI S，MAHDI W. Deep bayesian network architecture for big data mining[J]. Concurrency and Computation： Practice and Experience，2019（1）：4418-4423.

[9] ALJOBOURI H K，JABER H A，KOAK O M，et al. Clustering fMRI data with a robust unsupervised learning algorithm for neuroscience data mining[J]. Journal of Neuroence Methods，2018，299（8）：421-432.

[10] WANG T，ZHANG D，ZHOU X，et al. Mining personal frequent routes via road corner detection[J]. IEEE Transactions on Systems Man & Cybernetics Systems，2017，46（4）：445-458.

[11] LIN T，BORZABADI-FARAHANI A，LANE C J，et al. Apriori feasibility testing of randomized clinical trial design in patients with cleft deformities and class Ⅲ malocclusion[J]. International Journal of Pediatric Otorhinolaryngology，2014，78（5）：725-730.