鄭亞軍， 胡學(xué)鋼

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

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

增量更新挖掘算法是指已知原數(shù)據(jù)集關(guān)聯(lián)規(guī)則的情況下，對(duì)更新的數(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é)果來生成較小的候選項(xiàng)集或避免頻繁掃描原始數(shù)據(jù)集，但是由于頻繁掃描新增數(shù)據(jù)導(dǎo)致其效率低下。為了避免生成候選項(xiàng)目集，文獻(xiàn)［3］提出了基于FP樹生成頻繁項(xiàng)目集的FPGrowth。該算法將發(fā)現(xiàn)大頻繁項(xiàng)目集的問題轉(zhuǎn)換成遞歸地挖掘一些小頻繁項(xiàng)目，為使用最不頻繁的項(xiàng)目后綴提供了好的選擇性，大大降低了搜索開銷，但是它沒有考慮挖掘關(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é)點(diǎn)的并行化工作不能滿足現(xiàn)今海量數(shù)據(jù)存儲(chǔ)與計(jì)算，另一方面多節(jié)點(diǎn)的并行算法也存在數(shù)據(jù)分割不平衡的缺陷。針對(duì)現(xiàn)有單一節(jié)點(diǎn)計(jì)算能力遇到的瓶頸，使用云計(jì)算的分布式處理技術(shù)并行計(jì)算，是行之有效的解決方法。為此，本文提出關(guān)聯(lián)規(guī)則增量更新算法即 MRPFP，該算法通過將PFP算法并行挖掘頻繁模式樹的思想應(yīng)用到關(guān)聯(lián)規(guī)則增量更新之中，明顯減少對(duì)海量數(shù)據(jù)集的掃描次數(shù)，通過產(chǎn)生相互獨(dú)立的數(shù)據(jù)集約束FP樹規(guī)模。

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

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

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

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

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

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

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

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

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

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

2.1 算法思想描述

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

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

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

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

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

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

2.2 MRPFP算法實(shí)現(xiàn)

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

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

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

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

算法2 PFP算法。

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

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

算法3 頻繁項(xiàng)集的增量更新算法。

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

圖2 多節(jié)點(diǎn)環(huán)境下數(shù)據(jù)實(shí)驗(yàn)對(duì)比

4 結(jié)束語

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