基于fp―tree频繁模式的挖掘算法

《基于fp―tree频繁模式的挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、过程是递归的，会频繁进出栈，这就增加了内存开销，提高算法的时间复杂性，特别是在数据集很大的情况下。同时，在频繁模式的挖掘过程中需递归地构建条件Fp树，这也会降低算法效率。本文从这两方面改进了Fp-Tree算法，使之更有效率。2?魍车？Fp-Tree算法2.1传统Fp-Tree算法的的基本步骤每个待插入Fp-Tree数据集的项包含四个字段:项目名称、父结点指针、指向同名结点的指针(该指针构成同名指针的结点链)以及结点的支持度计数。传统Fp-Tree算法的的基本步骤如下：(1)将频繁项集按降序排序。扫描事务数据集D以

4、生成频繁1项集，并计算它们的支持度，然后对满足不小于最小支持度要求的频繁1项集按支持度降序排序，排序后的结果形成了一个项列表，记为L。(2)建立FP-Tree。创建一个以root标记的根结点T，对数据集中的每笔事务t。删除L中未包含的项目，对剩余项目按照L中的顺序进行排序，记作［i

5、P］，其中i表示排序后序列的第一项，P表示剩余项。调用insert_tree（T，［i

6、P］）方法将交易的频繁项插入到Fp-Tree中。若T有一个子结点N满足条件N.项名=i.项名，也即两个结点具有相同的项目名称，insert_tre

7、e方法将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,具体步骤如下：逆序遍

8、历频繁项列表L，对每项找出其条件模式基，以条件模式基的集合作为新的交易集（每个条件基对应一条交易）建立条件Fp-Tree,条件Fp-Tree的构建方式与原始Fp-Tree构建方式相同。条件模式基是指从根节点出发到所有以该项为最后一项（不含该项）的前缀路径上结点的集合。条件模式基的计数为路径中结点的最小计数。结束条件：条件Fp_Tree为空则退出；如果新的Fp-Tree只有一条单一的路径到叶子结点，则输出该路径上所有结点的组合，并上L中的频繁项即为频繁项集。2.2传统Fp-Tree算法存在的问题首先，传统的Fp-T

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

10、有递归的函数调用，从而减少了内存使用，提高了效率。下面用表1中的交易数据为例，说明Fp-Tree的建立过程。本例中最小支持度阈值为2:首先，根据交易数据集D，计算D中每项的支持度计数，若该计数不小于最小支持度阈值则为频繁项，将这些项（频繁1-项集）按支持度计数降序排列，得到频繁项列表L:{b:7，a:6，c:6，d:2，e：2}。接着，我们再次扫描数据集D，将其中的每笔交