一種基于本地分區(qū)的挖掘算法研究

韓天鵬　王峰

摘 要：在頻繁項集挖掘中減少數(shù)據(jù)庫掃描次數(shù)是核心工作之一.本文提出一種利用本地支持信息來計算頻繁項集的改進分區(qū)方法，在此基礎(chǔ)上只需對數(shù)據(jù)庫掃描一次.由于改進算法不進行第二次數(shù)據(jù)庫掃描，僅使用從分區(qū)獲得的本地支持的原因，使得頻繁項集的挖掘準(zhǔn)確率有一定的誤差，但實驗結(jié)果表明，誤差在可控范圍內(nèi).改進算法與Apriori、FP-growth和Partition算法相比，總體時間復(fù)雜度得到降低;內(nèi)存使用和數(shù)據(jù)庫訪問時間減少，有一定的優(yōu)越性.

關(guān)鍵詞：數(shù)據(jù)挖掘;頻繁項集;Partition算法;FP-Growth

中圖分類號：TP311? 文獻標(biāo)識碼：A? 文章編號：1673-260X（2019）11-0057-05

1 引言

頻繁項集挖掘技術(shù)是數(shù)據(jù)挖掘中重要的描述性技術(shù)，是分類，聚類，索引和關(guān)聯(lián)規(guī)則生成[1]等算法核心求解過程.而關(guān)聯(lián)規(guī)則生產(chǎn)的目的是使決策者能夠理解交易數(shù)據(jù)項之間的關(guān)系從而獲得決策的數(shù)據(jù)支持.關(guān)聯(lián)規(guī)則中頻繁項目集挖掘的應(yīng)用非常廣泛[2]，如無線自組織傳感器網(wǎng)絡(luò)（WASN）中的服務(wù)質(zhì)量改進[3]，實時心電信號分析和診斷[4]，印度夏季風(fēng)降雨預(yù)測[5]，庫存和利潤管理[6]，自動網(wǎng)絡(luò)監(jiān)控[7]等.

Apriori算法[8]是頻繁項集挖掘的經(jīng)典方法.盡管Apriori算法很受歡迎，但它具有以下缺點：（1）從二級存儲設(shè)備讀取/寫入數(shù)據(jù)時的I/O開銷，與最大頻繁項目集的大小成比例.（2）不可擴展具有大量項目的交易數(shù)據(jù)，因為它需要生成更多候選項集.（3）不能利用底層計算基礎(chǔ)結(jié)構(gòu)的并行處理能力.

為了克服Apriori算法的問題，許多研究提出了多樣化思想的方法.例如：動態(tài)項目集計數(shù)（DIC）算法[9]，嘗試通過同時計算不同長度項集的支持，對項目集的支持的訓(xùn)練模型來減少I/O操作的次數(shù).Pincersearch算法[10]自下而上和自上而下的方向上搜索頻繁項目集，在讀取數(shù)據(jù)庫時，除了計算對apriori等較小項集的支持外，它還計算候選最大頻繁項集的支持，以減少數(shù)據(jù)庫傳遞（I/O）的數(shù)量.如果最大的頻繁項集很長，它會顯著降低I/O開銷.雖然DIC和Pincersearch算法在一定程度減少了I/O操作的數(shù)次數(shù)，并顯著地提升了I/O的開銷效率，但由于其不可擴展性，它們對于大型數(shù)據(jù)庫來說是不適用的[11].

分區(qū)算法[12]基于一種新的思想，即創(chuàng)建適合主存儲器的水平數(shù)據(jù)分區(qū).在數(shù)據(jù)庫掃描方面，它比apriori和其他相關(guān)方法有了顯著的改進.但是，它會受到以下影響：（1）數(shù)據(jù)庫I/O開銷，因為它讀取數(shù)據(jù)庫兩次以計算頻繁項集.（2）時間復(fù)雜度更高，因為它從分區(qū)中計算更多的頻繁項集.分區(qū)算法所需的額外數(shù)據(jù)庫掃描是由于沒有利用分區(qū)中計算的本地支持來生成全局頻繁項集.此外，為了在不生成候選項集的情況下計算頻繁項集，提出了fp-growth算法[13]，它對數(shù)據(jù)庫進行兩次掃描，但其生成的樹不適合存儲較大的數(shù)據(jù)庫.eclat[14]在計算頻繁項集之前，將數(shù)據(jù)從水平格式轉(zhuǎn)換為垂直格式.盡管它只讀取一次數(shù)據(jù)庫，但它假定垂直數(shù)據(jù)庫適合內(nèi)存，該假設(shè)對于較大的數(shù)據(jù)庫是無效[15].

在本文中，通過提出一個有效的分區(qū)算法，該方法只讀取一次數(shù)據(jù)庫來降低總體時間復(fù)雜度和內(nèi)存使用率.利用分區(qū)中可用的局部支持信息，提高算法的效率.

2 頻繁項集挖掘的劃分算法綜述

分區(qū)算法的核心思想是從每個數(shù)據(jù)分區(qū)計算局部頻繁項集，然后通過第二次掃描數(shù)據(jù)庫計算局部頻繁項集的支持度來計算全局頻繁項集.算法如下：設(shè)事務(wù)數(shù)據(jù)庫D，其中包括N個事務(wù)，d個項.設(shè)I={i1，i2，…，id}為項集.

（1）創(chuàng)建m（≥2）個數(shù)據(jù)分區(qū)，d1，d2，…，dm來自一個包含n個事務(wù)的數(shù)據(jù)庫D，其中包含d個項，使得每一個分區(qū)數(shù)據(jù)庫Di，i=1，2，…，m都適合內(nèi)存.這里，Di是包含d個項，N/m個事務(wù)的一個分區(qū).

（2）計算本地頻繁項集.對于每個分區(qū)，Di（i=1，2，…，m）使用apriori算法計算本地頻繁項集.

（3）計算全局頻繁項集.

（a）結(jié)合在第二步中獲取的本地頻繁項集.

（b）通過讀取數(shù)據(jù)分區(qū)Di（i=1，2，…，m）計算每個本地頻繁項集的支持生成全局頻繁項集.

分區(qū)算法執(zhí)行兩次數(shù)據(jù)庫掃描并計算m組本地頻繁項集，并且各分區(qū)中生成一個本地頻繁項集.

3 基于局部支持的頻繁項集挖掘分區(qū)算法（LPFM）

在本節(jié)中，提出了一種有效的分區(qū)算法來計算頻繁項集，算法如下：

3.1 算法

輸入：

（1）事務(wù)數(shù)據(jù)庫D，具有N個事務(wù)和d個項目，（2）本地支持閾值，（3）全局支持閾值，輸出：頻繁項目集G.

算法如下：

算法1 創(chuàng)建分區(qū)數(shù)據(jù)庫.將事務(wù)數(shù)據(jù)庫D邏輯劃分為m（≥2）個數(shù)據(jù)分區(qū)，D1，D2，...，Dm，每個都有N/m個事務(wù)和d個項目，這樣每個分區(qū)都適合內(nèi)存.D=D1∪D2∪…∪Dm，并且Di∩Dj=？覫，？坌i，j都有i≠j.

算法2 對于每個分區(qū)，Di，i=1，2，...，m，計算本地頻繁項目集.

（1）將分區(qū)Di從輔助存儲設(shè)備讀取到內(nèi)存中.

（2）[Fi，Si]←計算本地頻繁集sets（Di，ε，θ）.

其中Fi是本地頻繁項集的集合，Si是Fi的支持度.使用FP-Growth算法從Di中計算

本地頻繁項目集.

算法3 計算全局頻繁項集G.初始化G←？覫

（1）計算本地頻繁項集：F=F1∪F2∪…∪Fm.每個本地頻繁項集f∈F，執(zhí)行以下操作：

（2）計算f的本地支持：S（f）←∑si（f）

（3）計算{F1，F(xiàn)2，…，F(xiàn)m}中f的出現(xiàn)頻率，r（f）←基數(shù){Fi|f∈Fi，i=1，2，…，m}.r（f）表示f頻繁出現(xiàn)的分區(qū)數(shù).

（4）檢查f是否為全局頻繁項集.if（S（f）≥θ），then G←G∪f.

（5）檢查f是否為非全局頻繁項集.else if [S（f）+（m-r（f））*（ε-1）]<θ，否則，丟棄f.

（6）檢查f是否可能是全局頻繁項集.else if [S（f）+（m-r（f））*（ε-1）/2]≥θ， then G←G∪f.

（7）其他情況丟棄f.

使用FP-Growth算法的思想枚舉局部頻繁項集以降低計算時間復(fù)雜度[步驟2（2）].所提出的算法的主要改進在于，計算全局頻繁項集時，避免了數(shù)據(jù)庫的二次掃描（步驟3）.在步驟3（2）中，針對每個本地頻繁項集合，聚合所有來自m個分區(qū)的本地支持.基于這種本地支持，本地頻繁項集f可以分類如下：

（1）全局頻繁項集，如果滿足全局閾值θ[步驟3（4）].

（2）非全局頻繁項集[步驟3（5）]，如果不滿足全局閾值θ;對于f不頻繁的（m-r（f））個分區(qū)，考慮ε-1的最大可能支持關(guān).

（3）可能的全局頻繁項集[步驟3（6）]，如果它滿足全局閾值θ，則在計算f不是頻繁的（m-r（f））分區(qū)中（ε-1）/2的平均支持度后.由于在不頻繁的分區(qū)中f的支持信息不可用，因此它的支持近似為平均支持度（ε-1）/2，以確定它是否可能是全局頻繁項集.

本文所提算法的局限性在于它可以將一些頻繁項集分類為非頻繁項和子頻繁項集，反之亦然.但是，它通過步驟3（6）中的平均度可以最大程度減少這種錯誤分類.

3.2 舉例說明

用表1所示的數(shù)據(jù)庫作為例庫來說明所提出的算法.假設(shè)使用事務(wù)T1到T10、T11到T20和T21到T30創(chuàng)建了3個分區(qū).所提出的LPFM方法的逐步分析如表2所示.本地支持和全局支持閾值固定為30%.該方法得到的頻繁項集和分區(qū)算法分別見表2和表3.同時觀察到，從這兩種方法獲得的頻繁項集與表2和表3所示相同.

4 算法分析

在本節(jié)中，將比較Apriori，Partition和FP-Growth算法在數(shù)據(jù)庫I/O開銷（即數(shù)據(jù)庫掃描數(shù)量）和計算方面時間復(fù)雜性的性能.

4.1 數(shù)據(jù)庫掃描分析（I/O開銷）

由于大量的交易數(shù)據(jù)存儲在二級存儲設(shè)備上，如磁盤，所以頻繁項目挖掘中最耗時的活動之一是掃描存儲在輔助設(shè)備上的數(shù)據(jù)庫.因此，最小化數(shù)據(jù)庫掃描的數(shù)量是一項至關(guān)重要且具有挑戰(zhàn)性的任務(wù).

在Apriori算法中，數(shù)據(jù)庫掃描的次數(shù)s（s≥2）與最大頻繁項集的大小成比例.Apriori算法為頻繁項集的每個級別讀取數(shù)據(jù)庫，算法數(shù)據(jù)庫掃描數(shù)RA=s，數(shù)量極巨大.

分區(qū)算法Partition將數(shù)據(jù)庫掃描的數(shù)量減少到2.第一次讀取數(shù)據(jù)庫計算本地頻繁項集.第二次讀取數(shù)據(jù)庫時計算全局頻繁項集.因此，Partition算法數(shù)據(jù)庫掃描數(shù)RP=2.

FP-Growth算法執(zhí)行第一次數(shù)據(jù)庫掃描計算頻繁的1項集.隨后，第二次讀取數(shù)據(jù)庫構(gòu)建FP樹并生成頻繁項集.FP-Growth算法掃描次數(shù)RG=2.

此外，本文提出的LPFM方法僅掃描數(shù)據(jù)庫一次，使用FP-Growth算法計算本地頻繁項目集.然后，利用本地支持信息生成全局頻繁項集.LPFM算法數(shù)據(jù)庫掃描數(shù)RL=1.

Apriori，Partition，F(xiàn)P-Growth和LPFM方法所需的數(shù)據(jù)庫讀取/掃描次數(shù)如表4.

4.2 時間復(fù)雜度分析

就計算時間而言，很明顯LPFM算法與Apriori和Partition算法相比顯示效率提高了，與FP-Growth算法在一個數(shù)量級上.

5 實驗結(jié)果與分析

5.1 使用的數(shù)據(jù)庫和實驗設(shè)置

實驗使用來自頻繁項目集挖掘數(shù)據(jù)集存儲庫的兩個數(shù)據(jù)集.這兩個數(shù)據(jù)庫每個包含100，000條事務(wù).每個事物是集合項目的子集{1，2，3，...，1000}.這兩個數(shù)據(jù)庫的主要區(qū)別在于交易長度.第一個數(shù)據(jù)庫具有較少數(shù)量的項目，平均值為10，第二個數(shù)據(jù)庫顯示具有更多項目的交易，平均值為39.6.這兩個數(shù)據(jù)庫是具有較大的數(shù)據(jù)庫和不同的項目分布.

實驗配備Intel i3處理器，8GBRAM，1TBHDD和Ubuntu16.04的計算機系統(tǒng)上運行.實驗使用Python腳本來實現(xiàn)FP-Growth算法.LPFM分區(qū)算法，創(chuàng)建了5個分區(qū)，每個分區(qū)具有相同數(shù)量的事務(wù).

生成頻繁項目集的支持閾值對于第一個數(shù)據(jù)集固定為1%，第二個數(shù)據(jù)集固定為5%.由于第一個數(shù)據(jù)庫中的事務(wù)長度較小，將支持閾值設(shè)置為1%以獲得頻繁項目集的合理數(shù)量.第二個數(shù)據(jù)庫將支持閾值設(shè)置稍高為5%，這樣可獲得高密度交易具有較低閾值的更頻繁的項目集.

5.2 實驗分析

實驗表明，LPFM與Apriori算法就數(shù)據(jù)庫開銷方面，LPFM算法優(yōu)于Apriori.與Apriori方法（圖1）相比，LPFM的計算時間更短.另外，與Apriori方法相比，LPFM需要更低的數(shù)據(jù)庫訪問時間（圖3）.因此，LPFM方法在計算時間和數(shù)據(jù)庫開銷方面顯示出優(yōu)于Apriori的優(yōu)勢.

由于LPFM算法僅掃描數(shù)據(jù)庫一次，而Partition算法掃描兩次，LPFM算法應(yīng)更優(yōu).實驗分析證實了這一點（圖3）.實證結(jié)果表明，兩個數(shù)據(jù)集中LPFM算法比Partition算法的性能更優(yōu)（圖2）.因此，與分區(qū)算法相比，所提出的LPFM在數(shù)據(jù)庫開銷和計算時間復(fù)雜度方面更優(yōu).

LPFM與FP-Growth算法相比，LPFM將數(shù)據(jù)庫掃描的數(shù)量減少到1，而FP-Growth算法需執(zhí)行兩次數(shù)據(jù)庫掃描.因此，LPFM的數(shù)據(jù)庫訪問時間比FP-Growth方法低（圖3）.LPFM利用FP-Growth方法的思想來計算局部頻繁項集，所以它在計算時間方面與FP-Growth算法相比具有競爭力（圖2）.FP-Growth算法用FP-tree來壓縮整個數(shù)據(jù)庫，所以消耗內(nèi)存更多.而LPFM使用了分區(qū)本地的較小FP-tree，所以消耗更少.實驗結(jié)果表明LPFM方法相對于FP-Growth在內(nèi)存使用方面提高了很多（圖4）.

計算與Apriori，F(xiàn)P-Growth和Partition算法幾乎相同數(shù)量的頻繁項目集.LPFM分別找到370和299個頻繁項集，而其他三個算法分別獲得386和316個頻繁項集.頻繁項目集數(shù)量的不同是由于LPFM不進行第二次數(shù)據(jù)庫掃描，僅使用從分區(qū)獲得的本地支持的原因.LPFM方法需要一次數(shù)據(jù)庫掃描，而其他3種算法至少需要2次數(shù)據(jù)庫掃描.

與Apriori和Partition算法相比，LPFM方法可擴展，數(shù)據(jù)庫可動態(tài)變化增加，同時總體時間復(fù)雜度隨著數(shù)據(jù)庫的變化而變化.此外，LPFM方法比FP-Growth算法顯示出有競爭力的計算時間，減少內(nèi)存的使用和數(shù)據(jù)庫訪問時間.

6 結(jié)論

本文提出了一種新的頻繁項挖掘分區(qū)方法，利用本地支持信息生成全局頻繁項集.方法僅掃描數(shù)據(jù)庫一次，并且與Apriori，Partition和FP-Growth算法相比，實驗結(jié)果表明，挖掘算法的性能有了顯著的提高.由于所提出的分區(qū)思想方法，可以在諸如Hadoop的并行計算環(huán)境中容易實現(xiàn)，所以算法所產(chǎn)生的頻繁項集，更接近于分區(qū)算法.

參考文獻：

〔1〕Han J， Cheng H， Xin D， et al. Fequent pattern mining：current status and future directions[J]. Data Mining Knowledge Discover，2007， 15（1）：55–86.

〔2〕Zaki M J. Parallel and distributed association mining： a survey[J]. IEEE Concur，1999 7（4）：14–25.

〔3〕Boukerche A， Samarah S. A novel algorithm for mining association rules in wireless ad hoc sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems，2008， 19（7）：865–877.

〔4〕Gu X， Zhu Y， Zhou S， et al.? A real-time fpga-based accelerator for ecg analysis and diagnosis using association-rule mining[C]// ACM Transactions on Embedded Computing Systems， 2016 15（2）：25：1–25：23.

〔5〕Vathsala H， Koolagudi S G. （2017） Prediction model for peninsular indian summer monsoon rainfall using data mining and statistical approaches[J]. computer geosciences，2017， 98：55–63.

〔6〕Kim J S. Emotion prediction of paragraph using big data analysis[J]. Journal of Digital Con-vergence，2016， 14（11）： 267–273.

〔7〕Qu Z， Keeney J， Robitzsch S， et al. （2016） Multilevel pattern mining architecture for automatic network monitoring in heterogeneous wireless communication networks[J]. China Communication[J] ，2016，13（7）：108–116.

〔8〕Agrawal R， Srikant R. Fast algorithms for mining association rules in large databases[C]// Proceedings of the 20th international conference on very large data bases， VLDB， Santiago，Chile， 1994， 487–499.

〔9〕Bhandari A， Gupta A， Das D.Improvised Apriori Algorithm using frequent pattern tree for real time applications in data mining[J]. Procedia Computer Science， 2015，46：644–651.

〔10〕Lin Di， Kedem Z M. Pincer-search： an efficient algorithm for discovering the maximum frequent set[J]. IEEE Transaction Knowledge Data Engineering，2002， 14（3）：553–566.

〔11〕Han J， Pei J， Yin Y. Mining frequent patterns without candidate generation[C]// Proceedings of the 2000 ACM SIGMOD international conference on management of data， ser. SIGMOD’00. ACM， New York， NY， 2002， 1–12.

〔12〕Jung H， Chung K. Life style improvement mobile service for high risk chronic disease based on PHR platform[J]. Cluster Computing， 2016，19（2）：967–977.

〔13〕韓天鵬，白玲玲，王浩.基于候選項集剪枝的Apriori算法的研究[J].阜陽師范學(xué)院（自然科學(xué)版），2014，31.

〔14〕曹瑩，苗志剛.基于向量矩陣優(yōu)化頻繁項的改進Apriori算法[J].吉林大學(xué)學(xué)報（理學(xué)版），2016，54（2）：349-353.

〔15〕劉云，向禪.基于虛構(gòu)理論對不平衡數(shù)據(jù)集中少數(shù)類關(guān)聯(lián)規(guī)則挖掘的研究[J].云南大學(xué)學(xué)報（自然科學(xué)版），2017，39（4）：33-38.