基于格的快速频繁项集挖掘算法＊

刘彩苹，毛建频，毛建旭，屈卫兰，蔡玉武

（1.湖南大学 信息科学与工程学院，湖南 长沙 410082；2.抚州职业技术学院 信息工程系，江西 抚州 344000；3.湖南大学 电气与信息工程学院，湖南 长沙 410082）

频繁项集挖掘是数据挖掘中的一类重要挖掘问题，广泛应用于关联规则挖掘、相关性分析、入侵检测、序列挖掘、分类分析、聚类分析、Web挖掘、XML挖掘等诸多数据挖掘任务.长期以来，人们对频繁模式的挖掘进行了大量深入的研究工作.Han等人提出了一种比Apriori算法快一个数量级的FP－growth算法[1].随后，各国的研究者们提出了许多其他改进算法，如Koh等人提出的基于树的高效频繁项集挖掘算法[2]，李也白等人用一种辅助存储结构提高了查询的效率[3]，Nguyen利用矩阵提出的频繁项集挖掘算法[4]，郭宇红等人提出的反向频繁项集挖掘算法[5]，Zeng等人提出了加权关联规则挖掘算法[6].Jalan提出了一种非递归频繁项集挖掘算法[7].Adnan提出一种自适应的频繁项集挖掘算法[8].赵强利提出一种快速选择性集成算法[9].范明提出一种不生成条件FP－树的算法[10].谭军提出了一种单遍扫描频繁模式算法[11].

FP－growth算法开辟了有效挖掘频繁模式的新途径.然而，它的时间和空间效率还不足够高，仍需改进.FP－growth算法的主要问题是建树过程中必须将提供频繁项集的数据全部压缩到一棵频繁模式树（或FP－树），在挖掘时，由长度为1的频繁模式（初始后缀模式）开始，递归的构造条件FP－树进行挖掘，在建树和挖掘过程中都需要占用大量的内存.当数据库很大，或者数据库中的频繁1－项集的数目很大时，运行速度将大为降低；更有甚者，可能由于无法构造基于内存的FP－树，该算法将不能有效地工作.

本文结合大型数据库本身的特性，在分析FP－growth算法的基础上，提出了一种基于格的大型数据库频繁模式挖掘算法LFP－growth.实验和分析表明，在挖掘大型数据库时，LFP－growth算法具有较好的时间和空间效率.

1 基本概念和问题的描述

为方便讨论，以事务数据库为背景.设I＝｛i1，i2，…，im｝为所有项目的集合，D＝ ｛T1，T2，…，Tn｝为事务数据库，其中每个事务Ti（i∈[1，…，n]）有一个惟一的标识TID.表1中的事务数据库是本文的示例数据库.该数据库中事务已经按照各项的支持度计数递增地将各事务中的项重新排列.

在事务数据库中挖掘频繁项集的问题可以描述为：给定事务数据库D和最小支持度阈值minsup，挖掘所有的频繁项集.

定义1[12]设（A，≤）为一个偏序集，如果对任意的x，y∈A，都存在x，y的上确界和下确界，则称A关于偏序“≤”构成一个格，并称“≤”是A上的一个格序.

定义2[12]设P（k）是格P的子格，如果对任意的x，y⊆P（k），且x∪y∈P（k）且x∩y⊆P（k），则称P（k）是格P的一个子格.

表1 事务数据库Tab.1 Transaction databaseD

图1中利用等价关系将P（I）划分为互不相交的P（a），P（e），P（b），P（d），P（c）5个子网格（等价类），并且是有序的.LFP－growth算法采用的是基于前缀的分类，即P（k）子格表示所有前缀为k的项集构成的子网格.如，P（e）＝ ｛｛ebdc｝｛ed｝｛edc｝｝.

图中实线圈起的项集表示在样例数据库中有该事务，虚线圈起的项集表示没有该事务.

图1 格P（I）的划分Fig.1 Partition of latticeP（I）

定义3 令α表示I上的约束表达式，项集约束表达式α以合取范式（CN F）的形式，即k1∧k2∧…∧ki（ki∈I，即每一合取项要么是I中的一个项目，要么是I中一个项目的补项.α＝（a∧e∧⇁b），该约束表达式表示，该集合是包含了｛ae｝但不包含｛b｝的项集集合.

2 LFP－growth算法

2.1 算法基本思想

令L（P（k）｜α）（k∈I）表示在格P（k）上满足约束表达式α的频繁项集，令扩充格P（k）＾（k∈I）表示在P（I）中所有包含项目k的项集.

定理1α合取式（k1∧k2∧ …∧ki）（ki∈I）的首项ki是P（I）的第t个等价类，则满足约束表达式α的频繁集必在集中P（I）的前t个子格中.

证明 由等价类的性质，可推出P（I）＝P（a）∪P（e）∪…∪P（c），而且子格之间项集互不相交，则P（（I）｜α）＝L（P（a）｜α）∪L（P（e）｜α）∪…∪L（P（c）｜α），假设α合取项的首项ki1为b，b是P（I）的第3个等价类，由于位于第4和第5位的P（d）和P（c）中不含b项目，即L（P（d）｜α）＝Φ，L（P（d）｜α）＝Φ，满足α的频繁集必在该P（I）的前3个等价类中.同理可证，当α合取项的首项ki1为其他项时也是如此.

由定理1可推出以下公式，图2为扩展格P（e）＾.

LFP－growth算法按项集支持度由小到大依次处理每一个子网格，在对每一个子网格进行处理时采用了迭代分解的方法，即将一个较大的格分解成较小的子格，将分解后子格分别迭加到相应的子格中，依次进行约束项挖掘直到求出所有的频繁集.下面的定理给出了迭加项集数的大小，所谓迭加项集数是指完成对P（k）的挖掘后，从P（k）子格迭加到后续子格的项集总数.

图2 扩展格P（e）＾Fig.2 Extended latticeP（e）＾

定理2 按上述方法对子格空间进行迭加，P（k）的项集迭加总数为（n―t）×2n－t－1，n为I中子格的数，t为P（k）在P（I）中的排序.

证

设P（k）是P（I）中第t个子格，P（k）子格中参加迭加的项集总数为（n－t）×2n－t－1.

推论1 按k的支持度由小到大依次处理每一个子格P（k），可使参与“迭加”的事务最少.

证 由定理2可知，越早处理的子格迭加项集数越多，子格P（k）对应的k的支持度越小，其子搜索空间对应的事务越少，参加迭加的事务也越少.因此LFP－growth算法在将P（I）划分为若干个较小的子格后，按项集支持度由小到大依次处理每一个子格，目的是使参与“迭加”的事务最少.

由推理1可知，按k的支持度大小依次处理子格P（k）比随机选择P（k）进行处理效率更高，速度更快.

定理3L（P（I））＝L（P（a）＾｜a）∪L（P（e）＾｜e）∪…∪L（P（c）＾｜c）.

证P（k）＾（k∈I）表示在P（I）中包含项集k的项集，即P（k）＾⊆P（I），且P（k）＾中包含了P（I）中所有含项目k的项集，因此格P（k）上挖掘满足约束表达式α＝k的频繁项集等同于格P（I）上挖掘满足该表达式的频繁项集，即L（P（I）｜a）＝L（P（a）＾｜a），则有：

由定理3得到以下结论，对网格P（I）的频繁项集挖掘转化为对多个子网格的并集进行的约束频繁项集的挖掘，不会影响频繁项集完全集的正确输出.

2.2 算法步骤

实现LFP－growth算法的关键是子格（子搜索空间）所对应的事务的迭加，如果复制所有的子格对应的事务进行迭加，时间和空间的效率会非常低.为此，可以借鉴Christian Borgelt教授在研究Recursive elimination算法时提出的事务链表（transaction list array）来实现迭加.

事务链表是由一组单向数据链表组成，每一个单向数据链记录一个子格P（k）所对应的事务集（以下简称为P（k）事务集）的信息，每一个单向数据链都包括一个计数器（support counter）和一个指针.计数器的值表示P（k）事务集的总数，指针则用于保存P（k）事务集的关联信息.将所有单向数据链表按P（k）处理的顺序排列，便组成了事务链表.样例数据库的事务链表组如图3所示.

图3 事 务链表组Fig.3 Transaction list array

定理4L（P（a）＾′｜a）∪L（P（e）＾′｜e）∪…∪L（P（c）＾′｜c）＝L（P（I））.

证P（k）＾′是P（k）＾的过滤子集，它滤去了之前已挖掘过的冗余项.显然在过滤后的投影数据库上进行约束挖掘等同于在投影数据库上进行约束挖掘，即L（P（k）＾｜k）＝L（P（k）＾′｜k）.因此，L（P（a）＾′｜a）∪L（P（e）＾′｜e）∪…∪L（P（c）＾′｜c）＝L（P（a）＾｜a）∪L（P（e）＾｜e）∪…∪L（P（c）＾｜c）.由定理3可知，L（P（a）＾′｜a）∪L（P（e）＾′｜e）∪…∪L（P（c）＾′｜c）＝L（P（I））.证毕.

算法1 格P（I）的分解和迭加

输入：P（I）对应的事务数据库D；最小支持度阈值minisup

输出：D中频繁项集

方法

子格P（a）中事务的迭加如图4所示.

图4 将P（a）中事务分解到其他子格Fig.4 The transaction ofP（a）was decomposed to other sublattices

算法2 约束频繁项集挖掘算法

输入：扩展子格P（k）＾对应的数据库子集Dk＾；最小支持度阀值minisup；约束表达式k；

输出：满足约束表达式lk的频繁项集Li

定理5P（k）＾（k∈I）是格.

证P（k）＾＝（P（a）｜k）∪（P（e）｜k）…∪（P（c）｜k）.

（P（a）｜k）为格P（I）中包含项目｛ak｝的项集.设X，Y⊆ （P（a）｜k），则X∩Y，X∪Y⊆ （P（a）｜k）.用反证法，如果X∩Y，X∪Y⊄ （P（a）｜k），则X，Y中必有一项 ⊄ （P（a）｜k），与假设矛盾，因此，X∩Y，X∪Y⊆ （P（a）｜k）.由定义2可知（P（a）｜k）是一个格，同理可证（P（e）｜k），…，（P（c）｜k）都是格，而（P（a）｜k）∪（P（e）｜k）…∪（P（c）｜k）也是格.证毕.

性质1 LFP－growth算法具有良好的可扩展性.

当数据库为海量数据库时，可将它分解迭加成多个P（k）＾进行挖掘，而当某个P（k）＾对应的事务很多，依然无法在内存中构造Fp－树时，挖掘就难以顺利进行.根据定理5可知P（k）＾是格，因此我们可将P（k）＾再次进行迭加分解，如果分解后扩展子格依然无法在内存中构造Fp－树时，就再继续分解直到可以在内存中构造扩展子格的Fp－树为止.

3 实验结果和分析

3.1 实验结果

本节对LFP－growth算法和FP－growth算法进行比较，程序代码均用Visual C＋＋实现.实验在PetiumⅣ2.8G，内存512M，硬盘80G的PC机上运行.实验结果如图5～图7所示.

图5是采用accidents数据库进行实验，该数据库大小为33.6M，是比利时国家统计院提供的1991－2000年期间Flanders地区的交通事故数据库.由图5可知，当最小支持度大于等于0.5%时，FP－growth算法的运行速度比LFP－growth算法略快.但是，当最小支持度小于0.5%时，LFP－growth算法的运行速度比FP－growth算法快.而且随着支持度的减少，差别越明显.

图6是采用bio＿train数据库进行实验，该数据库是KDD Cup 2004所提供的关于蛋白质同源性的训练数据库.该数据库有145 751行，每行包含有1个块号、1个试验号和74个特征值.图6是在事务数据库大小为66.4M条件下，最小支持度从3%减少到0.05%的两种算法运行时间的比较，由图6可知，当最小支持度等于3%时，FP－growth算法的运行速度比LFP－growth算法快.但是，当最小支持度小于等于1%时，LFP－growth算法的运行速度比FP－growth算法快.而且随着支持度的减少，差别越大.

图5 在accidents上的运行时间Fig.5 Runtime on database accidents

图6 在bio＿train上的运行时间Fig.6 Runtime on database bio＿train

图7是在最小支持度固定在15%条件下，事务数据库从300M增加到600M时两种算法运行时间的比较，由图7可知：随着事务数据库规模的增加，两种算法的运行时间都在不断增加.但是FP－growth算法运行时间的增长要远大于LFP－growth算法，甚至当事务数据库规模大于等于450M时，FP－growth算法因为内存空间不够无法运行，而LFP－growth算法却能正常运行.

图7 在WebDocs（支持度15%）上的运行时间Fig.7 Runtime on database WebDocs（min－sup 15%）

3.2 实验结果分析

FP－growth算法要将事务数据库中所有产生频繁项集的数据压缩到一棵FP－树中，该树中存储的关联信息从建树开始到挖掘完毕都完整地保存在内存里，挖掘时又通过递归创建条件FP－tree生成频繁模式，条件FP－tree个数等于频繁模式数，所以建树挖掘的时间和空间开销都很大，尤其是随着数据库规模的增加或支持度阈值的减少而导致频繁模式的数量以指数形式增长时，FP－growth算法无法构造基于内存的FP－树，从而导致挖掘失败.而LFP－growth算法虽然多次迭加子格，但它是在扩展格中构造FP－tree，规模比原始的FP－tree要小，而且挖掘过程比FP－growth算法简单，时间消耗远小于FP－growth算法.

本文算法不仅时间效率明显优于FP－growth算法，而且空间效率也明显优于FP－growth算法.因为，LFP－growth算法构建的是基于扩展格的FP－树，其规模远远小于在整体事务数据库上构建的FP－树，而且由以上运行时间效率实验和分析已表明，LFP－growth可以在更小的支持度阀度水平上运行，而FP－growth算法常因耗尽物理内存而无法运行.

4 结 论

提出了一种基于格的快速频繁项集挖掘算法LFP－growth.这种算法不仅减少了对内存的需求，也较大地提高了挖掘效率，尤其适合挖掘大型数据库的频繁项集.本文的实验结果很好地证明了这一点.

今后的工作在于进一步的研究如何精简事务数据链表组的结构，进一步提高现有算法的效率，减少对内存的需求.同时考虑可将本文格迭加分解的策略和已有的各种分布式频繁模式挖掘算法结合起来，设计新的基于分布式数据库的频繁模式挖掘算法.

[1] HAN J，PEI J，YIN Y.Mining frequent patterns without candidate generation[C]／／Proceedings of the ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2000：1－12.

[2] KOH J L，TU Y L.A tree－based approach for efficiently min－ing approximate frequent itemsets[C]／／Proceedings of the Fourth International Conference on Research Challenges in Information Science（RCIS）.Nice，France：2010：1349－1357.

[3] 李也白，唐辉，张淳，等.基于改进的FP－tree的频繁模式挖掘算法[J].计算机应用，2011，31（1）：101－103.LI Ye－bai，TANG Hui，ZHANG Chun，etal.Frequent pattern mining algorithm based on improved FP－tree[J].Journal of Computer Applications，2011，31（1）：101－103.（In Chinese）

[4] NGUYEN T T.An improved algorithm for frequent patterns mining problem[C]／／Proceedings of the International Symposium on Computer Communication Control and Atomation.Tainan，2010：503－507.

[5] 郭宇红，童云海，唐世渭.基于FP－Tree的反向频繁项集挖掘[J].软件学报，2008，19（2）：338－350.GUO Yu－hong，TONG Yun－hai，TANG Shi－wei.Inverse frequent itemset mining based on FP－tree[J].Journal of Software，2008，19（2）：338－350.（In Chinese）

[6] ZENG B，JIANG X L，ZHAO W.The improvement of weighted association rules arithmetic based on FP－tree[C]／／Proceedings of the 3rd International Conference on Advanced Computer Theory and Engineering.Chengdu，2010：549－552.

[7] JALAN S，SRIVASTAVA A，SHARMA G K.A non－recursive approach for FP－tree based frequent pattern generation[C]／／2009IEEE Student Conference on Research and Development（SCOReD）.UPM Serdang，2009：160－163.

[8] ADNAN M，ALHAJJ R.A bounded and adaptive memorybased approach to mine frequent patterns from very large databases[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2011，41（1）：154－172.

[9] 赵强利，蒋艳凰，徐明.基于FP－Tree的快速选择性集成算法[J].软件学报，2011，22（4）：709－720.ZHAO Qiang－li，JIANG Yan－huang，XU Ming.Fast ensemble pruning algorithm based on FP－tree[J].Journal of Software，2011，22（4）：709－720.（In Chinese）

[10] 范明，李川.在FP－树中挖掘频繁模式而不生成条件FP－树[J].计算机研究与发展，2003，40（8）：1216－1222.FAN Ming，LI Chuan.Mining frequent patterns in an FP－tree without conditional FP－tree generation[J].Journal of Computer Research and Development，2003，40（8）：1216－1222.（In Chinese）

[11] 谭军，卜英勇，杨勃.一种单遍扫描频繁模式树结构[J].计算机工程，2010，36（14）：32－33.TAN Jun，BU Ying－yong，YANG Bo.Single－pass frequent pattern tree structure[J].Computer Engineering，2010，36（14）：32－33.（In Chinese）

[12] 郭耀煌，刘家诚，刘常青，等.格序决策[M].上海：上海科学技术出版社，2003.