基于FP—Tree的最大频繁项目集挖掘算法

陈向华++刘可昂

摘要：挖掘最大频繁项目集是关联规则挖掘中的关键问题，基于Apriori产生候选项目集需要付出很高的代价，尤其是在存在大量强模式或长模式的时候.提出一种基于频繁模式树（FP-Tree）的最大频繁项目集挖掘算MFIP-Miner（maximum frequent itemsets pattern mmer），其挖掘过程无需产生候选项集，从而提高挖掘效率。

关键词：数据挖掘；最大频繁项集；关联规则；频繁模式树

中图分类号：TP311

文献标识码：A

DOI：10.3969/j.issn.1003-6970.2015.12.023

本文著录格式：陈向华，刘可昂.基于FP-Tree的最大频繁项目集挖掘算法[J]软件，2015，36（12）：98-102

0 引言

关联规则数据挖掘（简称关联规则挖掘）就是从大量的数据中挖掘出有价值的描述数据项之间相互联系的有关知识。自1993年Agrawal等人首先提出关联规则概念以来，关联规则挖掘便迅速受到数据挖掘域专家的广泛关注。在迄今十几年中，关联规则挖掘技术得到了较为深入的发展。其中发现频繁项目集是关联规则挖据应用中的关键技术和步骤。对于频繁项集挖掘，已经开发了许多有效的、可伸缩的算法，由它们可以导出关联和相关规则。这些算法可以分成三类：（1）类Apriori算法；（2）基于频繁模式增长的算法，如FP-growth；（3）使用垂数据格式的算法。在如上所述的诸多算法中，计算项目集的支持数是发现频繁项目集中最耗时的工作，占据整个计算量的大部分，因此，降低候选项目集的数量是减小开销的最好手段。

由于最大频繁项目集中已经隐含了所有频繁项目集，所以可把发现频繁项目集的问题转化为发现最大频繁项目集的问题.另外，某些数据挖掘应用仅需发现最大频繁项目集，而不必发现所有的频繁项目集，因而发现最大频繁项目集对数据挖掘具有重大意义。

目前已经提出的可用于发现最大频繁项目集的算法主要有Gunopulos等人提出算法ALL-MFS，Bayardo等人提出的算法Max-Miner，Lin等人提出的算法Pincer-Search，以及Burdick等人提出的算法Mafia，路松峰等人提出的算法DMFI，宋余庆等人提出的算法DMFIA等。上文阐述的这些算法都能有效地挖掘出事务数据库D中的最大频繁项目集，然而它们也存在不足之处。比如：Max-Miner虽然突破了传统的白底向上的搜索策略，尽可能早地对项目集进行修剪，但其存在的缺陷是：1）未利用白顶向下的信息进行剪枝；2）未对MFCS进行适当的排序，产生了多余的候选项目集；Pincer-Search虽然采用了白底向上和白顶向下的双向搜索策略，但其在发现最大频繁项目集的过程中产生了过多的无用候选项目集，对海量数据库来讲，将陷入NP难度的陷阱；DMFIA算法通过对D的两次扫描，把其中的所有事务压缩存储到FP-Tree中，这样在以后发现最大频繁项目集的过程中仅需在FP-Tree中进行查找，无需再扫描D，所以该算法的效率相对于Max-Miner、Pincer-Search有显著的提高，但它没有充分利用FP-Tree的特点，且其第k次的最大频繁候选集是由k-l次的最大频繁候选集中的非频繁项目集去掉一个项目来生成，所以也产生了大量的无用候选项目集；Mafia算法虽然利用垂直位图来压缩存储数据库中的事务，并且在挖掘过程中也采用了有效的剪枝技术，但其仍然要维护一个数量较大的候选项目集的集合，这降低了算法的整体性能。本文提出一种基于频繁模式树（FP-Tree）的最大频繁项目集挖掘算法MFIP-Miner（maximum frequent itemsets pattemminer），其挖掘过程无需产生候选项集，从而提高挖掘效率。

1 问题描述

显然，任何频繁项目集都是某最大频繁项目集的子集，所以可以把发现所有频繁项目集的问题转化为发现所有最大频繁项目集的问题.

1.2 频繁模式树

在Han等人定义的频繁模式树FP-Tree中，每个节点由节点名称node-name、节点计数node-count、节点链 node-link及父节点指针node-parent四部分组成。另外，为了方便树的遍历，创建一个频繁项目头表Htable，它包含两个组成部分：项目名称item-name和项目链头item-head。FP-Tree的构造算法如下：

（1）扫描D一次，产生频繁项目集合F及其支持数，并按支持数降序排列F生成频繁项目列表IDF；

2 挖掘最大频繁项集的算法MFIP-Miner

2.1 基本性质

性质1.在FP-Tree中，若某节点计数不小于s（s见定义1），则该节点和其前缀路径中的节点组成的模式（项目集）必为频繁模式。

证明：设节点Ⅳ为路径P的后缀，且N.node-count≥s，由FP-Tree的构造过程可知，对于Ⅳ的前缀路径p中的任一个节点N，一定有：N'.node-count≥N.node-count≥s，由此可知N即为P中最小节点，所以由P中所有节点组成的模式的计数必大于或等于s，即为频繁模式。证毕。

性质2.若由某一频繁项目T_i的条件模式基生成的条件FP-Tree中只含有单个路径P时，则P中的所有项目与T_i的并集一定是频繁项目集，且P∪T_i的支持数等于T_i中叶节点的支持数。

证明：由条件频繁模式树的构造过程可知，对于某一频繁项目T_i，在其条件频繁模式树中的节点必为频繁项目节点。由于此时树中只含有单个路径，而且路径中的每个节点又都是频繁项目节点，则由性质l可知，此路径中的节点和项目T_i组成的模式必为频繁模式。根据频繁模式树的构造方法可知，FP-Tree中的叶节点的节点计数是整个路径中最小的，因此P∪T_i的支持数不可能大于或小于叶节点的节点计数，所以P∪T_i的支持数等于叶节点的支持数，证毕。

由上述性质可知，最大频繁项目集一定存在于由条件FP-Tree产生的频繁模式中。因此MFIP-Miner算法的基本思想是：依次从Htable中取出所有的频繁项目，对每个项目构造其条件模式基和条件FP-Tree，对构造的条件FP-Tree进行如下处理：

（l）如果构造的条件FP-Tree中只含有单个路径，则取出该路径中所有项目，将它们与生成该条件FP-Tree的项目合并，组成一个频繁模式，然后判断此频繁模式是否是MFIP中某项目集的子集，若不是，则此频繁模式就为最大频繁模式，并将其放入MFIP中，同时删除MFIP中是该最大频繁模式子集的项目集，若是则舍去。

（2）如果构造的条件中含有多个路径，则依次从该条件FP-Tree所对应的Htable中取出所有项目，构造每个项目的条件FP-Tree，找出其包含的最大频繁模式。可见整个发现过程是递归进行的，直到找出所有最大频繁模式为止

（3）在挖掘过程中，若发现树中的某个节点Ⅳ的计数不小于s，则从Htable中取出所有排列在N.node-name前面的项目组成集合X；然后，通过Ⅳ的同名节点链，找出节点链中所有计数不小于s的同名节点；最后，遍历每条以同名节点为后缀的路径P，检查X是否存在于P中，一旦发现了这样的路径，则可将在当前频繁模式（或条件频繁模式）树中的挖掘过程终止。

2.2 算法MFIP-Miner

输入：最小支持度X._{sup D}，在此X._{sup D}下构造的FP-Tree T；

输出：事务数据库D中满足X._{sup D}要求的最大频繁项目集的集合MFIP。

（1）MFIP=NULL：

3 算法实现与比较

3.1 测试机配置

本文所用的测试机为Lenovo台式机，其配置是：CPU为Pentium3.2GHz，操作系统为win7旗舰版，内存为4G，并选用R语言，在Eclipse+StatET编程环境中实现了算法MFIP-Miner算法和Mafia算法。

3.2 测试数据库的选择

为了能综合测试MFIP-Miner算法的性能，本文选用了两种类型的数据库：Chess和Mushroom（它们可以从UCI Machine Leaming Repository上免费获得）

3.3 对比算法选择

本文通过对比MFIP-Miner算与Mafia算法在Chess和Mushroom数据库运行效率，来分析和验证MFIP-Miner算法的性能，之所以选择Mafia算法作为比较的对象，主要是因为该算法是目前公认挖掘最大频繁项目集最有效的算法。

3.4 在Chess数据库上的测试分析

Chess数据库的特点是最大频繁项目集的分布比较对称，而且大多数最大频繁项目集的维数相对较低，平均长度约为37。从图l中可以看出，算法MFIP-Miner在最小支持度大于20%时的执行效率要好于算法Mafia两到三倍。然而，当最小支持度小于50%时算法MFIP-Miner的性能开始下降，而在最小支持度小于30%时性能下降的速度更大。产生这种现象的原因是：MFIP-Miner算法采用FP-Tree来压缩存储数据库中的事务，并在该基础上进行挖掘，由于充分利用了FP-Tree的特点，在挖掘过程中不需要产生候选项目集，这使其在挖掘过程中具有较高的效率。然而，MFIP-Miner算法在挖掘过程中需要产生条件频繁模式基，当这种模式基数量巨大时会占用较多内存，以致复杂的内存管理花费了一些额外的开销，使算法的性能趋于下降。而对于Mafia算法来说，由于其是基于Apriori算法的挖掘思想，需要生成大量的候选项目集，并对其进行支持度计算和频繁性检验，因此Mafia算法需要花费大量的计算开销。但是，Mafia算法采用了一种垂直位图结构来表示事务，并且采用了一些有效的剪枝技术，因此，总的来说其在挖掘最大频繁项目集方面也是很有效的。

3.5 在Mushroom数据库上的测试分析

Mushroom数据库的特点是最大频繁项目集的分布比较密集，其中每个事务的长度为23，而绝大多数最大频繁项目集的长度为20，因此，每个最大频繁项目集中都有一些项目存在于每个事务中。从图2中可以看出，MFIP-Miner算法在这种数据库中的执行效率要好于在上面两个数据库中的执行效率，总的执行时间较少，这说明MFIP-Minerr算法对最大频繁项目集较长且分布密集的数据库有较大优势。和Mafia算法相比，MFIP-Miner算法略优于前者，这也说明Mafia算法对最大频繁项目集较长的挖掘也很有效。

4 结论

本文提出的MFIP-Miner算法能高效地挖掘出事务数据库中的最大频繁项目集，其在挖掘过程中不需要产生最大频繁候选项目集，而且由于挖掘过程只需扫描事务数据库D一次，从而提高了算法的执行效率。