基于FP树的最大频繁项集挖掘

陈凤娟

【摘要】频繁项集的挖掘是数据挖掘中的一个基础和核心问题，具有广泛的应用领域。而频繁项集挖掘可分为完全频繁项集挖掘、频繁闭项集挖掘和最大频繁项集挖掘三类，其中，最大频繁项集的数目最少。频繁项集的挖掘是一个搜索问题，剪枝优化技术是提高频繁项集挖掘效率的一个重要手段。对于最大频繁项集的挖掘可以从宽度优先和深度优先两个角度来考虑，而基于FP树的深度优先算法比宽度优先算法扫描数据集的次数要少很多，因此，具有较好的性能。本文主要分析宽度优先的最大频繁项集挖掘算法和基于FP树的深度优先最大频繁项集挖掘算法。

【关键词】关联规则;频繁项集;最大频繁项集;FP树

1.引言

数据挖掘技术能从数据库中智能地获取有价值的知识和信息，是人工智能和数据库等多个学科的重要研究内容。数据挖掘发展到现在，出现了许多技术分支和研究方向。应用不同的挖掘技术可以从数据库中挖掘出不同类型的知识，根据挖掘出的知识不同的形式，可以把数据挖掘分为通用关联规则挖掘、特征规则挖掘、分类挖掘、聚类挖掘、序列模式分析、时间序列分析、趋势分析和偏差分析等类别。其中关联规则挖掘及频繁项集的挖掘是数据挖掘研究的核心内容之一，频繁项集的挖掘效果对数据挖掘算法的性能和效率有重要的作用。

关联规则是数据中一种简单规则，这些规则能反映出实际的需求，是大量数据中项集之间相关联系。关联规则的挖掘算法是无监督学习的方法，其中，频繁项集挖掘是关联规则挖掘的第一步，也是关联规则挖掘的关键步骤，是影响数据挖掘效率的关键问题。

本文主要分析频繁项集与最大频繁项集的概念，然后分析关联规则中的最大频繁项集挖掘的常用算法，并探讨算法的优劣。

2.频繁项集和最大频繁项集

关联规则挖掘的主要目的是确定数据集中不同属性之间的联系，从这种联系中找出有价值的多个属性之间的依赖关系，通过这种依赖关系给出决策支持。关联规则的挖掘可以分成两步来完成。第一步是按照用户给定的最低阈值，识别出数据集中的所有频繁项目集，第二步是从频繁项目集中构造规则，要求构造的规则的可信度大于等于用户设定的最低值。

设U={U1，U2，…，Un}为n个不同字符的集合，其中的字符称为项或商品。任意一个集合XU称为一个项集，若|X|=k，则称X为k项集。事务（或交易）T是项的集合，且任意的TU，对应每一个事务有唯一的标识，记作TID。设A={T1，T2，…，Tn}，称A为U上的交易集或者数据集，简称交易集或者数据集。如果XT，称事务T包含X。对于一个项集X和一个交易集A，X在A中的支持度定义为X在A中的支持计数与A中总的交易个数之比，记作sup（X）。如果X的支持度大于某个给定的最小阈值，则称X是频繁的。

支持度是对关联规则代表的重要性进行度量的指标，它体现了关联规则的频度。如果某个项集的支持度的值太小，则表明相应的规则很可能只是偶然发生的。

给定数据集A、项集X和min_sup，且min_sup∈（0，l），sup＼（XY）= 为项集X在数据集A上的支持度，简记为sup（X）。当sup（X）≥min_sup时，项集X称为A上的完全频繁项集，简称为频繁项集。频繁项集挖掘就是要在事务数据库里找出所有大于给定的最小支持度的频繁项集。

数据集A上的频繁闭项集定义为：若项集X满足条件sup（X）≥min_sup且（YA∧XY→sup（Y）

项集X满足条件sup（X）≥min_sup且（YA∧XY→sup（Y）

最大频繁项集是指那些在所有的频繁项集中不存在超集的频繁项集。如果一个频繁项集不是其它任何频繁项集的真子项集，那么称此频繁项集为最大频繁项集。由于最大频繁项集的个数远远小于频繁闭项集，更远远小于完全频繁项集，所以挖掘最大频繁项集可以有效缩小问题解的规模，给稠密集中的长频繁模式挖掘提供了新的解决方案。

3.最大频繁项集挖掘

如果X是一个频繁项集，且X的任何一个超集都是非频繁的，则X是最大频繁项集。把所有的最大频繁项集放入一个集合中，称为最大频繁项集的集合，即MFS（Maximum Frequent Sets）。如果X是最大频繁项集，那么X的任何真子集都不是最大频繁项集。从这个特性可知，在挖掘最大频繁项集的过程中，最大频繁项集所有的子集都可以不去挖掘，只需要挖掘最大频繁项集就可以了，这样能有效地缩短算法的运行时间，提高算法的运行效率。按遍历搜索空间的策略，可以把最大频繁项集挖掘算法分为宽度优先搜索和深度优先搜索两类算法。

Pincer-search算法是典型的采用宽度优先搜索策略的算法，它使用传统的横向数据集的表示方法，通过多次遍历数据集来计算各个项集的支持度计数。该算法把自顶向下的搜索策略与由底向上的搜索策略结合起来，使用两种策略同时对数据空间进行搜索。其中，由底向上的搜索方法与Apriori算法的方法相似，先扫描数据集k次生成的k阶频繁项集，用k阶频繁项集来生成k+l阶侯选项集，再扫描数据集，计算候选项集的支持度计数，并将候选项集分为k+1项频繁项集和k+1项非频繁项集。Pincer-search算法利用两个不同方向搜索生成的非频繁项集和最大频繁项集相互剪枝，不断重复剪枝动作，直到两个不同方向的搜索过程发现的频繁项集一致时为止。通过互相剪枝，可以迅速降低搜索空间，提高挖掘效率，但算法需要多次遍历数据集，并计算项集的支持度，还会产生过多的无用的候选项集，对海量数据算法效率会急剧下降。

Max-Miner算法也是采用宽度优先搜索策略，它利用子集剪枝策略对候选项集进行剪枝，又利用超集剪枝策略对非最大频繁项集进行剪枝。Max-Miner提出的利用尾项集按项支持度从低到高的排序方法，不但提高了超集剪枝策略的效率，还被广泛地应用在其他的最大频繁项集挖掘算法中。Max-Miner算法根据提出的搜索空间树概念，尽可能早地对项目集进行剪枝，有效地缩小了搜索空间。但是，由于Max-Miner算法也是横向的宽度优先策略，所以它也需要多次扫描数据集，降低了算法的效率。

4.基于FP树的最大频繁项集挖掘

FP-Max算法是一种基于FP-Tree的最大频繁项集挖掘算法，它是一种使用深度优先搜索策略的有效算法。FP-Max算法在深度优先遍历搜索空间树时，对于数据集，建立其FP树，对于每个结点，还保存该结点到根结点搜索路径上的每一个结点对应的FP子树。这些FP子树表示与相关结点挖掘有关的频繁信息。在当前结点上，通过在相应项集之中添加对应的FP子树头表中的某个项，来生成搜索空间中的子结点。

在构建子结点的FP子树之前做，先对其进行超集是否存在的判断，如果在已有最大频繁项集的集合中，存在首尾项集并集的超集，则进行前瞻剪枝;否则，创建子结点FP子树，递归调用算法在该子结点上进行挖掘，直至某个子孙结点的FP子树是单路径树。当某个节点的子FP树为单一路径树时表明，该节点对应项集与子FP树的头表项集的并集，为最大频繁项集，将其加入最大频繁项集树中。最大频繁项集树是FP-Max算法用来压缩保存已经产生的最大频繁项集的存储结构。它的结构与FP树的结构一样，都包含头表和树结构，从某个叶节点到根节点的路径代表一个最大频繁项集。

FP-Max算法只需要在构建FP树时，对事务数据库进行两次扫描，在挖掘过程中，该算法不会产生候选项集，但会产生一些候选最大频繁项集。因此FP-Max算法在一定程度上减少了 I/O开销，提高了算法的挖掘效率。但是FP-Max算法也有一些不足之处，首先，为了有效的进行前瞻剪枝，该算法需要在最大频繁项集树中查询超集，就需要将给定项集集合中每一个项集与被检测项集做项匹配，使得超集存在判断的开销较大。其次，该算法会构建大量的条件模式树，在某些存在大量的长模式以及强模式的数据集中，构建FP树的工作量非常大，而节点链的复杂度将增加数据结构的复杂性。最后，FP-Max算法是基于双向FP树结构的，就导致存储FP树需要其他单向FP树的两倍的存储空间，因此，FP树的存储也会占用大量的内存空间。

5.结束语

在关联规则挖掘、序列模式挖掘、多层模式挖掘等数据挖掘问题中，挖掘频繁项集既是基本步骤，也是关键步骤。最大频繁项集比频繁项集的数量少，在某些挖掘中，挖掘最大频繁项集可以有更好的算法效率。最大频繁项集挖掘算法按对搜索空间树的遍历策略可以分为两种，分别是宽度优先算法和深度优先算法。Pincer-search算法和Max-Miner算法是宽度优先算法，而FP-Max算法是基于FP树的深度优先算法，对这几个算法的分析和研究对以后的最大频繁项集挖掘算法的改进有很大的帮助。

参考文献

[1]李庆华，王卉等.挖掘最大频繁项集的并行算法[J].计算机科学，2004，31（12）：132-134.

[2]吴振光.一个改进的关联规则的频繁项目集数据挖掘算法[J].科学，2007，34（9）：145-147.

[3]陈晨，鞠时光.基于改进FP-tree的最大频繁项集挖掘算法[J].计算机工程与设计，2008，29（24）：6236-6239.

[4]王丹阳，田卫东.一种有效的并行频繁项集挖掘算法[J].计算机应用研究，2008，25（11）：3332-3334.

[5]花红娟，张健，陈少华.基于频繁模式树的约束最大频繁项集挖掘算法[J].计算机工程，2011，37（9）：78-80.

[6]廖福荣，王成良.基于有序FP-tree的最大长度频繁项集挖掘算法[J].计算机工程与应用，2012，48（30）：147-150.

[7]刘芝怡，常睿.频繁项集高效挖掘算法研究[J].微计算机信息，2012，28（10）：491-493.