基于Fp―Tree频繁模式的挖掘算法

fp-tree算法在挖掘最大频繁模式和搜索关联规则中得到了广泛应用。本文阐述了Fp-Tree算法的一般过程，并对其效率瓶颈作了分析：传统的Fp-Tree算法在构建频繁树的过程中需要递归地插入频繁项，在频繁模式的挖掘过程中需要递归地产生条件Fp-Tree， 这些递归过程会增大算法开销，降低算法效率。本文使用非递归机制对Fp-Tree的构建过程做了一些改进，同时，在挖掘频繁项过程中使用了组合频繁前缀的方法，避免了条件Fp-Tree的产生。本文就改进算法与传统算法作了对比实验，可以看出，这些改进一定程度上提高了效率。

【关键词】频繁模式 关联规则Fp-Tree频繁 前缀

1 前言

随着信息社会的发展，关联规则挖掘在数据挖掘中的地位日益重要。关联规则是对事物之间相互依存和关联关系的一种描述。挖掘频繁模式是挖掘关联规则的基础，针对这种模式的挖掘有一系列优秀算法，比如Aprior算法和Fp-Tree算法。其中Aprior算法思路直观，更易实现，但需多次扫描数据集并产生大量候选频繁项集。相对的，Fp-Tree在挖掘过程中无需产生候选集，与Aprior 相比效率更高。

但是，传统的Fp-Tree算法建立Fp-Tree的过程是递归的，会频繁进出栈，这就增加了内存开销，提高算法的时间复杂性，特别是在数据集很大的情况下。同时，在频繁模式的挖掘过程中需递归地构建条件Fp树，这也会降低算法效率。本文从这两方面改进了Fp-Tree算法，使之更有效率。

2 魍车Fp-Tree算法

2.1 传统Fp-Tree算法的的基本步骤

每个待插入Fp-Tree数据集的项包含四个字段：项目名称、父结点指针、指向同名结点的指针（该指针构成同名指针的结点链）以及结点的支持度计数。

传统Fp-Tree算法的的基本步骤如下：

（1）将频繁项集按降序排序。扫描事务数据集D以生成频繁1项集，并计算它们的支持度，然后对满足不小于最小支持度要求的频繁1项集按支持度降序排序，排序后的结果形成了一个项列表，记为L。

（2）建立FP-Tree。创建一个以root标记的根结点T，对数据集中的每笔事务t。删除L中未包含的项目，对剩余项目按照L中的顺序进行排序，记作[i|P]，其中i表示排序后序列的第一项，P表示剩余项。调用insert_tree（T，[i|P]）方法将交易的频繁项插入到Fp-Tree中。若T有一个子结点N满足条件N.项名=i.项名，也即两个结点具有相同的项目名称，insert_tree方法将N的计数加1。否则，创建新的子结点N，并将其计数置为1，然后，将结点N链接到其父结点T，同时，再将N链接到到具有相同项名的结点上（这些相同item_name的结点最终形成结点链结构，该链的头结点为L中的同名项）。若P不为空，insert_tree（N，P）方法会递归地调用。扫描所有的交易后，一颗完整的Fp-Tree被构建出来。

（3）挖掘Fp-Tree以获得频繁项集合。挖掘过程需要在（2）中建立好的原始Fp-Tree结构中递归挖掘以得到频繁项集，在此过程中还需生成很多条件Fp-Tree，具体步骤如下：逆序遍历频繁项列表L，对每项找出其条件模式基，以条件模式基的集合作为新的交易集（每个条件基对应一条交易）建立条件Fp-Tree，条件Fp-Tree的构建方式与原始Fp-Tree构建方式相同。条件模式基是指从根节点出发到所有以该项为最后一项（不含该项）的前缀路径上结点的集合。条件模式基的计数为路径中结点的最小计数。

结束条件：条件Fp_Tree为空则退出；如果新的Fp-Tree只有一条单一的路径到叶子结点，则输出该路径上所有结点的组合，并上L中的频繁项即为频繁项集。

2.2 传统Fp-Tree算法存在的问题

首先，传统的Fp-Tree算法需要使用递归机制去插入频繁项以形成Fp-Tree。只要剩余项列表P仍是非空集，insert_tree（N，P）过程将会被递归调用。根据递归函数调用栈的原理可知，在递归结束前，变量和子函数占用的存储空间必须保留，当事务中有很多项目时，需要大量的递归，这时调用栈中的大量出栈入栈操作非常费时。此外，在建立好Fp-Tree之后，对频繁模式的挖掘也是递归的，此过程还会产生很多条件Fp-Tree，这也拉低了算法的效率，尤其是在数据集较大的情况下。

3 改进Fp-Tree算法

3.1 构建Fp-Tree

在这种改进的算法中，没有递归的函数调用，从而减少了内存使用，提高了效率。下面用表1中的交易数据为例，说明Fp-Tree的建立过程。本例中最小支持度阈值为2：

首先，根据交易数据集D，计算D中每项的支持度计数，若该计数不小于最小支持度阈值则为频繁项，将这些项（频繁1-项集）按支持度计数降序排列，得到频繁项列表L：{b：7， a：6， c：6， d：2， e：2}。

接着，我们再次扫描数据集D，将其中的每笔交易数据项插入到Fp-Tree中。每次添加一笔事务的频繁项之前，先对这些事务进行预处理：将其中的非频繁项删除，剩余项按照L中的顺序排列。然后，让辅助指针指向根结点，待新项添加到树中后，让辅助指针指向新添加的结点。每次结束一个数据集的插入之后，都让辅助指针指向根结点。图1显示了将t1和t2插入Fp-Tree的具体步骤：

将整个事务数据库的交易都处理完毕之后，得到如下Fp-Tree。

3.2 挖掘频繁模式

改进的算法使用频繁前缀以及频繁子孙集连接构成频繁项集，不必再去构建条件fp-tree，这就减小了内存开销，在一定程度上提高了算法效率。其中频繁前缀和频繁子孙集的定义如下：

定义一频繁前缀：Fp-Tree中若结点i的支持度计数大于等于最小支持度计数，则从根结点遍历到i所经过结点的集合称为i的频繁前缀。

定义二频繁子孙：若Fp-Tree中结点i的所有同名子孙结点j的支持度计数之和大于等于最小支持度计数，则称j为i的频繁子孙。所有i的频繁子孙的集合称为i的频繁子孙集。

以图2中数据为例，改进后挖掘频繁项的过程如下：

（1）自底向上后根遍历图中的Fp-Tree，获得非叶子结点c，计算出c的频繁子孙集为?。

（2）继续后根遍历Fp-Tree，获得非叶子结点a。其频繁子孙集为{c：2，e：2}，并找到a的频繁前缀{b}。将a和他的频繁子集连接生成频繁2项集{ac：2，ae：2}，再与其频繁前缀组合得到频繁项集FI={ac：2，ae：2，bac：2，bae：2}。

（3）继续后根遍历Fp-Tree，找到非叶子结点b， 其频繁子孙集{a：4，c：4，d：2，e：2}，频繁前缀为空。将b和他的频繁子集连接生成频繁2项集{ba：4，bc：4，bd：2，be：2}，与频繁前缀组合得到频繁项集FI={ba：4，bc：4，bd：2，be：2}。

（4）将（2）（3）步中得到的频繁项集组合并更新其支持度，得到新的频繁项集FI={ ba：4，bc：4，bd：2，be：2， ac：2，ae：2，bac：2，bae：2}。

（5）继续后根遍历Fp-Tree，得到非叶子结点a，其频繁子孙集{c：2}，频繁前缀为?。二者连接得到频繁二项集{ac：2}，与频繁前缀组合得到频繁集FI={ac：2}。

（6）合并（4）（5）得到的频繁集，得到新的频繁集FI，并更新其支持度，得到新的频繁集FI={ ba：4，bc：4，bd：2，be：2， ac：4，ae：2，bac：2，bae：2}。

（7）至此，Fp-Tree中所有非叶子结点被遍历一遍。将（6）中FI与L中频繁项做并集运算，得到最后的频繁集FI={ ba：4，bc：4，bd：2，be：2， ac：4，ae：2，bac：2，bae：2，b：7，a：6，c：6，d：2，e：2}。

4 实验及结论

使用三种数据量规模的样本做数据集，分别使用传统及改进过的Fp-Tree算法挖掘频繁集，记下其运行时间，如图3所示：

图3：算法运行时间

从图中可以看出，在数据量较小的情况下，两种算法花费的时间几乎相等。但是当处理较大数据量的时候，改进的算法所花费时间明显小于传统方法，效率有了一定的提高。

参考文献

[1]范明，孟小峰等译.数据挖掘概念与技术[M].北京：机械工业出版社，2006：3-29.

[2]AGRAWAL R，IMIELINSKI T，SWAMI A.Mining association rules between sets of items in large database[C]//Proceedings of 1993 ACM SIGMOD Conference on Management of Data.NewYork：ACM，1993：207-216.

[3]Han，J.，Kamber，M.Data Mining Concepts and Techniques[M]，Second Edition，translated by Ming Fan and Xiaofeng Meng.Machinery Industry Press（2007）.

[4]Hui，L.，Qian，X.Non Check Mining Algorithm of Maximum Frequent Patterns in Association Rules based on FP-tree[J].Journal of Computer Applications 7（30），1923-1924（2010）.

[5]范明，李川.在FP-渲型诰蚱捣蹦J蕉不产生条件FP-树[J].计算机研究与发展，2003，40（08）：1216-1222.

作者单位

长治学院计算机系 山西省长治市 046011