基于PFP的关联规则增量更新算法

郑亚军， 胡学钢

（合肥工业大学 计算机与信息学院，安徽 合肥 230009）

随着Internet的快速发展，数据以指数级飞速增长。从海量的数据中挖掘出有效的、可理解的信息已经成为数据挖掘的热门课题。关联规则作为海量数据挖掘的研究之一，更多的研究在于挖掘静态数据。面对数据增长以及参数变化，通常是重新使用算法进行挖掘，也因此使得数据频繁计算，且随着数据的高速增加，传统算法存在众多约束。为了节省资源减少计算量，并有效地维护已有关联规则，研究者提出增量更新挖掘算法。

增量更新挖掘算法是指已知原数据集关联规则的情况下，对更新的数据集或参数进行维护［1－2］。目前，关联规则增量式更新算法主要是基于Apriori算法进行改进与优化，比如文献［2］提出的FUP算法，其算法高效的关键在于尽可能利用已有的挖掘结果来生成较小的候选项集或避免频繁扫描原始数据集，但是由于频繁扫描新增数据导致其效率低下。为了避免生成候选项目集，文献［3］提出了基于FP树生成频繁项目集的FPGrowth。该算法将发现大频繁项目集的问题转换成递归地挖掘一些小频繁项目，为使用最不频繁的项目后缀提供了好的选择性，大大降低了搜索开销，但是它没有考虑挖掘关联规则的高效增量更新问题。目前研究者已经提出了一些基于FP树的增量更新关联规则的算法［4］，但是随着数据规模的扩大，FP树的规模也越来越大致使其性能下降，效率低下。

随着数据量增大所带来的限制，基于FP树的关联规则增量更新算法的并行化研究逐渐展开［5－8］。一方面单一节点的并行化工作不能满足现今海量数据存储与计算，另一方面多节点的并行算法也存在数据分割不平衡的缺陷。针对现有单一节点计算能力遇到的瓶颈，使用云计算的分布式处理技术并行计算，是行之有效的解决方法。为此，本文提出关联规则增量更新算法即 MRPFP，该算法通过将PFP算法并行挖掘频繁模式树的思想应用到关联规则增量更新之中，明显减少对海量数据集的扫描次数，通过产生相互独立的数据集约束FP树规模。

1 关联规则的更新

对于原有的事务数据库D以及新增事务数据集d，生成融合事务数据库的频繁项目集可分解为以下2个子问题：①如何找出D中不再生效或仍然生效的频繁项目集；② 如何找出D融合d后新的频繁项目集。对于前者，由定理1可知，通过对比新旧数据的频繁项集求出公共项集LD即可，这一步骤只需扫描d1次。由于D中的频繁项目集和d均较小，因此其运算量也较小，故下面的工作主要集中在找出所有新的频繁项目集。

定义1 对于项目集X，如果有X.supD≥s，且X.supd≥s成立，则称X为D中的强频繁项目集，同样定义d中的强频繁项目集［9］。

定理1 设LD为D∪d中频繁项目集的集合，则必有LD＝SLD∪SLd成立。记SLD、SLd分别为D、d中强频繁项目集的集合［9］。

定理2 如果Ld是d中的强频繁项目集，则Ld的任何子集都是d中的强频繁项目集［10］。

目前已经提出的可用于增量式更新关联规则的算法有 FUP、FUP2［11］，以及在此基础上有效改进的并行更新算法 PFUP［9］、PPFUP［12］，为了更高效地解决I／O负载及并行计算，文献［13］采用将FUP的并行计算与Map／Reduce融合后的MRFUP，这些算法都是建立在Apriori算法基础上。然而基于FP树的关联规则更新算法显著优于Apriori，并已经用于处理增量更新方面。文献［14］提出的FIUA实现了将FP－Growth应用到关联规则增量更新中，在已知原数据集的频繁项目集情况下，对于新增数据集使用FP－Growth算法挖掘频繁项集，在将新旧数据的频繁项目集融合的过程中，需要k次扫描数据以确定频繁项目集的变化；文献［15］通过制定新的支持度函数构造IFP－Growth更新频繁项集，但实际等同于对新旧数据融合后的整体直接进行关联规则的挖掘，这很明显增加了原数据的扫描次数，并且，当项目集的维度很大时树的空间消耗会超出内存限制。

从上述可以看出，数据的不断增加导致FP树规模的扩大，进而限制了FP－Growth算法的应用。对于FP－Growth算法的并行优化避免了FP树大量开销。FP－Growth并行优化的研究已经取得不错的效果［16－18］，从优化效果和大数据计算的性能来看，算法PFP［18］具有最好以及最广泛的应用。

PFP算法将对FP－Growth的递归构造条件FP树这一过程并行，减小FP树的规模。本文提出的基于PFP的增量式更新算法MRPFP，在增量更新时将新旧数据集挖掘结果融合的过程与Map／Reduce［19］结合，避免频繁扫描新旧数据库并加快计算。

2 MRPFP算法及实现

MRPFP算法是基于PFP的关联规则增量更新算法，它将增量更新的过程与Hadoop的Map／Reduce相结合。

2.1 算法思想描述

设原数据集为D，新增数据集为d，原数据集的频繁项目集合为SLD。可以看出，算法整体包括2个部分：PFP挖掘新增数据以及新旧数据频繁项集的增量更新部分。

（1）挖掘新增数据。对新增数据集d，使用PFP算法挖掘关联规则，得到d的所有频繁项SLd，比较SLD和SLd，找出其公共部分放入更新后数据集的强频繁项集中，记为L′。剩余项目集则为待确定项集，记为C。

（2）分割整体数据。将融合数据集分割成相互独立的P个数据子集，把数据子集和C分别发送到P个站点。每个站点扫描它的数据子集，与C中的项集进行匹配，得到C中各项集的支持度计数并标记。

（3）统计局部项集。利用分区函数把P个站点在C中相同的项集和它的支持度计数发送到Q个站点。通过把相同的项集计数累加起来，并加上C中的初始支持度计数，产生最后的实际支持度计数，与最小支持度计数比较，确定局部频繁项集的集合。

（4）合并结果。把各个站点的输出结果合并为K′，并加上L′，即得到更新数据集后的全部频繁项的集合。

MRPFP算法的优势在于扫描原数据集以及新增数据集的次数大大较少，且在和 Map／Reduce计算模型结合后充分利用云计算强大的存储和计算能力，增加了该算法对于大数据的可扩展性和实用性。

2.2 MRPFP算法实现

对新增数据调用PFP算法，含有递归的思想，对其并行的过程交由Map和Reduce实现。

（1）统计数据集的频繁一项集F－List，将数据集分割成P份发送到节点上。由Map函数识别事务集中的每项作为输出键值对的key，对应的value为1。Reduce将具有相同key的value值累加得到每项出现的次数。合并所有Reduce的输出结果并删除计数小于最小支持度的项，排序后即得到F－List。具体程序如算法1所示。

算法1 频繁一项集统计。

（2）根据F－List进行划分得到Q份局部FList。根据局部F－List对应的ID（List－i），扫描数据集d并将其分为相互独立的Q份，ID为d－i，由每一个节点根据List－i调用FP－Growth算法，并行地构建条件FP树来计算关联规则。具体程序如算法2所示。

算法2 PFP算法。

（3）对于并行FP－Growth运行得到的结果SLd和原数据的频繁项SL，比较后得到L′和C，

D然后将融合数据集发送到节点进行计算，具体步骤及实现如算法3所示。

算法3 频繁项集的增量更新算法。

综上所述，MRPFP算法对新数据的扫描次数远远少于基于Apriori的增量更新算法，且在增量更新时对于关联规则的并行融合更为高效，在新旧数据的增量更新理论上优于其他算法。

3 实验与结果分析

本文提出的MRPFP算法是基于PFP并行化并结合 Map／Reduce进行增量更新，因此将MRPFP算法和文献［13］的MRFUP算法进行实验对比。尽管FIUA也是基于FP－Growth的算法，由于在数据稍大时内存开销过大无法运行，故不做比较。实验使用4台相同配置的PC机搭建集群，操作系统采用 Ubuntu12.04；Map／Reduce采用了 Hadoop1.0.4版本；实验数据通过IBM数据生成器［20］生成，以及采集自合肥工业大学数据挖掘与智能计算DMiC网站的IIS日志记录，通过预处理生成0.1G到4G的事务数据；数据集的记录数量级为（1～5）×106；通过java（jdk1.6）实现MRPFP算法运行在上述环境中。

（1）实验1（单机环境下算法比较）。在单机情况下，设置支持度阀值为1%，通过不断增大数据集d运行MRPFP与MRFUP算法进行实验对比，结果如图1所示。

图1 单机环境下数据实验对比

（2）实验2（多节点环境下算法比较）。在多节点环境下，设置支持度为1%，通过在1～4个节点下运行MRPFP与MRFUP算法进行实验对比，对比实验结果如图2所示。

从上述实验可以看出，MRPFP明显比MRFUP更为高效。单节点时，随着数据的不断增大，MRPFP的优势也逐渐明显。MRFUP由于融合新旧规则的同时频繁地扫描新增数据，导致其运行时间越来越高于MRPFP算法。而在多节点环境下，MRFP也能带来比MRFUP更为稳定的加速，使得该算法具有较好的扩展性。

图2 多节点环境下数据实验对比

4 结束语

本文通过将FP－Growth分而治之的思想与云计算的Map／Reduce模型结合，提出关联规则增量更新算法MRPFP。该算法能做到一次扫描即可实现新增数据集后的关联规则更新。且通过实验结果证明：MRPFP算法随着数据量增大，能充分利用Map／Reduce的并行计算能力，性能优势明显，提高了对海量数据的挖掘能力和效率。

［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］.计 算 机 学 报，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.