鄭亞軍， 胡學(xué)鋼

（合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院，安徽 合肥 230009）

隨著Internet的快速發(fā)展，數(shù)據(jù)以指數(shù)級飛速增長。從海量的數(shù)據(jù)中挖掘出有效的、可理解的信息已經(jīng)成為數(shù)據(jù)挖掘的熱門課題。關(guān)聯(lián)規(guī)則作為海量數(shù)據(jù)挖掘的研究之一，更多的研究在于挖掘靜態(tài)數(shù)據(jù)。面對數(shù)據(jù)增長以及參數(shù)變化，通常是重新使用算法進(jìn)行挖掘，也因此使得數(shù)據(jù)頻繁計算，且隨著數(shù)據(jù)的高速增加，傳統(tǒng)算法存在眾多約束。為了節(jié)省資源減少計算量，并有效地維護(hù)已有關(guān)聯(lián)規(guī)則，研究者提出增量更新挖掘算法。

增量更新挖掘算法是指已知原數(shù)據(jù)集關(guān)聯(lián)規(guī)則的情況下，對更新的數(shù)據(jù)集或參數(shù)進(jìn)行維護(hù)［1－2］。目前，關(guān)聯(lián)規(guī)則增量式更新算法主要是基于Apriori算法進(jìn)行改進(jìn)與優(yōu)化，比如文獻(xiàn)［2］提出的FUP算法，其算法高效的關(guān)鍵在于盡可能利用已有的挖掘結(jié)果來生成較小的候選項集或避免頻繁掃描原始數(shù)據(jù)集，但是由于頻繁掃描新增數(shù)據(jù)導(dǎo)致其效率低下。為了避免生成候選項目集，文獻(xiàn)［3］提出了基于FP樹生成頻繁項目集的FPGrowth。該算法將發(fā)現(xiàn)大頻繁項目集的問題轉(zhuǎn)換成遞歸地挖掘一些小頻繁項目，為使用最不頻繁的項目后綴提供了好的選擇性，大大降低了搜索開銷，但是它沒有考慮挖掘關(guān)聯(lián)規(guī)則的高效增量更新問題。目前研究者已經(jīng)提出了一些基于FP樹的增量更新關(guān)聯(lián)規(guī)則的算法［4］，但是隨著數(shù)據(jù)規(guī)模的擴(kuò)大，F(xiàn)P樹的規(guī)模也越來越大致使其性能下降，效率低下。

隨著數(shù)據(jù)量增大所帶來的限制，基于FP樹的關(guān)聯(lián)規(guī)則增量更新算法的并行化研究逐漸展開［5－8］。一方面單一節(jié)點的并行化工作不能滿足現(xiàn)今海量數(shù)據(jù)存儲與計算，另一方面多節(jié)點的并行算法也存在數(shù)據(jù)分割不平衡的缺陷。針對現(xiàn)有單一節(jié)點計算能力遇到的瓶頸，使用云計算的分布式處理技術(shù)并行計算，是行之有效的解決方法。為此，本文提出關(guān)聯(lián)規(guī)則增量更新算法即 MRPFP，該算法通過將PFP算法并行挖掘頻繁模式樹的思想應(yīng)用到關(guān)聯(lián)規(guī)則增量更新之中，明顯減少對海量數(shù)據(jù)集的掃描次數(shù)，通過產(chǎn)生相互獨立的數(shù)據(jù)集約束FP樹規(guī)模。

1 關(guān)聯(lián)規(guī)則的更新

對于原有的事務(wù)數(shù)據(jù)庫D以及新增事務(wù)數(shù)據(jù)集d，生成融合事務(wù)數(shù)據(jù)庫的頻繁項目集可分解為以下2個子問題：①如何找出D中不再生效或仍然生效的頻繁項目集；② 如何找出D融合d后新的頻繁項目集。對于前者，由定理1可知，通過對比新舊數(shù)據(jù)的頻繁項集求出公共項集LD即可，這一步驟只需掃描d1次。由于D中的頻繁項目集和d均較小，因此其運算量也較小，故下面的工作主要集中在找出所有新的頻繁項目集。

定義1 對于項目集X，如果有X.supD≥s，且X.supd≥s成立，則稱X為D中的強(qiáng)頻繁項目集，同樣定義d中的強(qiáng)頻繁項目集［9］。

定理1 設(shè)LD為D∪d中頻繁項目集的集合，則必有LD＝SLD∪SLd成立。記SLD、SLd分別為D、d中強(qiáng)頻繁項目集的集合［9］。

定理2 如果Ld是d中的強(qiáng)頻繁項目集，則Ld的任何子集都是d中的強(qiáng)頻繁項目集［10］。

目前已經(jīng)提出的可用于增量式更新關(guān)聯(lián)規(guī)則的算法有 FUP、FUP2［11］，以及在此基礎(chǔ)上有效改進(jìn)的并行更新算法 PFUP［9］、PPFUP［12］，為了更高效地解決I／O負(fù)載及并行計算，文獻(xiàn)［13］采用將FUP的并行計算與Map／Reduce融合后的MRFUP，這些算法都是建立在Apriori算法基礎(chǔ)上。然而基于FP樹的關(guān)聯(lián)規(guī)則更新算法顯著優(yōu)于Apriori，并已經(jīng)用于處理增量更新方面。文獻(xiàn)［14］提出的FIUA實現(xiàn)了將FP－Growth應(yīng)用到關(guān)聯(lián)規(guī)則增量更新中，在已知原數(shù)據(jù)集的頻繁項目集情況下，對于新增數(shù)據(jù)集使用FP－Growth算法挖掘頻繁項集，在將新舊數(shù)據(jù)的頻繁項目集融合的過程中，需要k次掃描數(shù)據(jù)以確定頻繁項目集的變化；文獻(xiàn)［15］通過制定新的支持度函數(shù)構(gòu)造IFP－Growth更新頻繁項集，但實際等同于對新舊數(shù)據(jù)融合后的整體直接進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，這很明顯增加了原數(shù)據(jù)的掃描次數(shù)，并且，當(dāng)項目集的維度很大時樹的空間消耗會超出內(nèi)存限制。

從上述可以看出，數(shù)據(jù)的不斷增加導(dǎo)致FP樹規(guī)模的擴(kuò)大，進(jìn)而限制了FP－Growth算法的應(yīng)用。對于FP－Growth算法的并行優(yōu)化避免了FP樹大量開銷。FP－Growth并行優(yōu)化的研究已經(jīng)取得不錯的效果［16－18］，從優(yōu)化效果和大數(shù)據(jù)計算的性能來看，算法PFP［18］具有最好以及最廣泛的應(yīng)用。

PFP算法將對FP－Growth的遞歸構(gòu)造條件FP樹這一過程并行，減小FP樹的規(guī)模。本文提出的基于PFP的增量式更新算法MRPFP，在增量更新時將新舊數(shù)據(jù)集挖掘結(jié)果融合的過程與Map／Reduce［19］結(jié)合，避免頻繁掃描新舊數(shù)據(jù)庫并加快計算。

2 MRPFP算法及實現(xiàn)

MRPFP算法是基于PFP的關(guān)聯(lián)規(guī)則增量更新算法，它將增量更新的過程與Hadoop的Map／Reduce相結(jié)合。

2.1 算法思想描述

設(shè)原數(shù)據(jù)集為D，新增數(shù)據(jù)集為d，原數(shù)據(jù)集的頻繁項目集合為SLD?？梢钥闯?，算法整體包括2個部分：PFP挖掘新增數(shù)據(jù)以及新舊數(shù)據(jù)頻繁項集的增量更新部分。

（1）挖掘新增數(shù)據(jù)。對新增數(shù)據(jù)集d，使用PFP算法挖掘關(guān)聯(lián)規(guī)則，得到d的所有頻繁項SLd，比較SLD和SLd，找出其公共部分放入更新后數(shù)據(jù)集的強(qiáng)頻繁項集中，記為L′。剩余項目集則為待確定項集，記為C。

（2）分割整體數(shù)據(jù)。將融合數(shù)據(jù)集分割成相互獨立的P個數(shù)據(jù)子集，把數(shù)據(jù)子集和C分別發(fā)送到P個站點。每個站點掃描它的數(shù)據(jù)子集，與C中的項集進(jìn)行匹配，得到C中各項集的支持度計數(shù)并標(biāo)記。

（3）統(tǒng)計局部項集。利用分區(qū)函數(shù)把P個站點在C中相同的項集和它的支持度計數(shù)發(fā)送到Q個站點。通過把相同的項集計數(shù)累加起來，并加上C中的初始支持度計數(shù)，產(chǎn)生最后的實際支持度計數(shù)，與最小支持度計數(shù)比較，確定局部頻繁項集的集合。

（4）合并結(jié)果。把各個站點的輸出結(jié)果合并為K′，并加上L′，即得到更新數(shù)據(jù)集后的全部頻繁項的集合。

MRPFP算法的優(yōu)勢在于掃描原數(shù)據(jù)集以及新增數(shù)據(jù)集的次數(shù)大大較少，且在和 Map／Reduce計算模型結(jié)合后充分利用云計算強(qiáng)大的存儲和計算能力，增加了該算法對于大數(shù)據(jù)的可擴(kuò)展性和實用性。

2.2 MRPFP算法實現(xiàn)

對新增數(shù)據(jù)調(diào)用PFP算法，含有遞歸的思想，對其并行的過程交由Map和Reduce實現(xiàn)。

（1）統(tǒng)計數(shù)據(jù)集的頻繁一項集F－List，將數(shù)據(jù)集分割成P份發(fā)送到節(jié)點上。由Map函數(shù)識別事務(wù)集中的每項作為輸出鍵值對的key，對應(yīng)的value為1。Reduce將具有相同key的value值累加得到每項出現(xiàn)的次數(shù)。合并所有Reduce的輸出結(jié)果并刪除計數(shù)小于最小支持度的項，排序后即得到F－List。具體程序如算法1所示。

算法1 頻繁一項集統(tǒng)計。

（2）根據(jù)F－List進(jìn)行劃分得到Q份局部FList。根據(jù)局部F－List對應(yīng)的ID（List－i），掃描數(shù)據(jù)集d并將其分為相互獨立的Q份，ID為d－i，由每一個節(jié)點根據(jù)List－i調(diào)用FP－Growth算法，并行地構(gòu)建條件FP樹來計算關(guān)聯(lián)規(guī)則。具體程序如算法2所示。

算法2 PFP算法。

（3）對于并行FP－Growth運行得到的結(jié)果SLd和原數(shù)據(jù)的頻繁項SL，比較后得到L′和C，

D然后將融合數(shù)據(jù)集發(fā)送到節(jié)點進(jìn)行計算，具體步驟及實現(xiàn)如算法3所示。

算法3 頻繁項集的增量更新算法。

綜上所述，MRPFP算法對新數(shù)據(jù)的掃描次數(shù)遠(yuǎn)遠(yuǎn)少于基于Apriori的增量更新算法，且在增量更新時對于關(guān)聯(lián)規(guī)則的并行融合更為高效，在新舊數(shù)據(jù)的增量更新理論上優(yōu)于其他算法。

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

本文提出的MRPFP算法是基于PFP并行化并結(jié)合 Map／Reduce進(jìn)行增量更新，因此將MRPFP算法和文獻(xiàn)［13］的MRFUP算法進(jìn)行實驗對比。盡管FIUA也是基于FP－Growth的算法，由于在數(shù)據(jù)稍大時內(nèi)存開銷過大無法運行，故不做比較。實驗使用4臺相同配置的PC機(jī)搭建集群，操作系統(tǒng)采用 Ubuntu12.04；Map／Reduce采用了 Hadoop1.0.4版本；實驗數(shù)據(jù)通過IBM數(shù)據(jù)生成器［20］生成，以及采集自合肥工業(yè)大學(xué)數(shù)據(jù)挖掘與智能計算DMiC網(wǎng)站的IIS日志記錄，通過預(yù)處理生成0.1G到4G的事務(wù)數(shù)據(jù)；數(shù)據(jù)集的記錄數(shù)量級為（1～5）×106；通過java（jdk1.6）實現(xiàn)MRPFP算法運行在上述環(huán)境中。

（1）實驗1（單機(jī)環(huán)境下算法比較）。在單機(jī)情況下，設(shè)置支持度閥值為1%，通過不斷增大數(shù)據(jù)集d運行MRPFP與MRFUP算法進(jìn)行實驗對比，結(jié)果如圖1所示。

圖1 單機(jī)環(huán)境下數(shù)據(jù)實驗對比

（2）實驗2（多節(jié)點環(huán)境下算法比較）。在多節(jié)點環(huán)境下，設(shè)置支持度為1%，通過在1～4個節(jié)點下運行MRPFP與MRFUP算法進(jìn)行實驗對比，對比實驗結(jié)果如圖2所示。

從上述實驗可以看出，MRPFP明顯比MRFUP更為高效。單節(jié)點時，隨著數(shù)據(jù)的不斷增大，MRPFP的優(yōu)勢也逐漸明顯。MRFUP由于融合新舊規(guī)則的同時頻繁地掃描新增數(shù)據(jù)，導(dǎo)致其運行時間越來越高于MRPFP算法。而在多節(jié)點環(huán)境下，MRFP也能帶來比MRFUP更為穩(wěn)定的加速，使得該算法具有較好的擴(kuò)展性。

圖2 多節(jié)點環(huán)境下數(shù)據(jù)實驗對比

4 結(jié)束語

本文通過將FP－Growth分而治之的思想與云計算的Map／Reduce模型結(jié)合，提出關(guān)聯(lián)規(guī)則增量更新算法MRPFP。該算法能做到一次掃描即可實現(xiàn)新增數(shù)據(jù)集后的關(guān)聯(lián)規(guī)則更新。且通過實驗結(jié)果證明：MRPFP算法隨著數(shù)據(jù)量增大，能充分利用Map／Reduce的并行計算能力，性能優(yōu)勢明顯，提高了對海量數(shù)據(jù)的挖掘能力和效率。

［1］ Shah S，Chauhan N C，Bhanderi S D.Incremental mining of association rules：a survey ［J］.International Journal of Computer Science and Information Technologies，，2012，3（3）：4071－4074.

［2］ Cheung D W.Maintenance of discovered association rules in large database：an incremental updating technique［C］／／Proc of 1996Int Conf on Data Engineering.IEEE Computer Soc Press，1996：106－114.

［3］ Han Jiawei，Kamber M.Data mining concepts and techniques ［M ］. MorganKaufmann Publishers， 2002：151－159.

［4］ Leung C K S，Khan Q I，Hoque T.CanTree：a tree structure for efficient incremental mining of frequent patterns［C］／／Proceedings of the Fifth IEEE International Conference on Data Mining，2005：274－281.

［5］ Pramudiono I，Kitsuregawa M.Parallel fp－growth on pc cluster［M］／／Advances in knowedge Discovery and Data Mining.Berlin：Springer，2003：467－473.

［6］ Aouad L M，Le－Khac N A，Kechadi T M.Distributed frequent itemsets mining in heterogeneous platforms［J］.Journal of Engineering，Computing and Archtecture，2007，1（2）：1－12.的增 量 更 新 算 法 ［J］.計 算 機(jī) 學(xué) 報，2004，27（5）：703－710.

［16］ El－Hajj M，Zaiane O R.Parallel leap：Large scale maximal pattern mining in a distributed environment［C］／／Paralld and Distrbxted Systems，12th Intornatonal Confereance on IEEE，2006：135－142.

［17］ Buehrer G，Parthasarathy S，Tatikonda S，et al.Toward terabyte pattern mining：an architecture－conscious solution［C］／／Procedings of the 12th ACM SIGPLAN Syrnposium on Principles and Practhce of Parallcl Programming ACM，2007：2－12.

［18］ Li Haoyuan，Wang Yi，Zhang Dong，et al.Pfp：parallel fp－growth for query recommendation［C］／／Proceedings of 2008ACM Comferce on Recomendation Systems.ACM，2008：107－114.

［19］ Dean J，Ghemawat S.Mapreduce：simplified data processing on large clusters［C］／／Proceedings of the 6th Symposium on Opcrating System Design and Implementation，San Francisco，California，USA，2004：137－150.

［20］ Rajaraman A，Ullman J D.Mining of massive data［M］.Stanford：［S.n.］，2010.

［21］ Ghemawat S，Gobiof H，Leung S.The google filesystem［C］／／Proc.of ACM Symposium on Operating Systems Principles.Lake George，NY：［S.n.］，2003：29－43.