基于FP-tree挖掘最大频繁项集的FP-MFI算法的研究

VIP免费

3.0 李佳 2024-09-26 10 4 149KB 6 页 15积分

侵权投诉

基于 FP-tree 最大频繁项集的 FP-MFI 算法的研究

摘要：由于基于 FP-tree 的 DMFIA 算法在生成最大频繁项目集时会产生大量的候选频繁项集，本文改进传统的 FP-tree 结

构，并提出了一种基于改进 FP-tree 的最大频繁模式挖掘算法 FP-MFI，该算法不需要生成最大频繁候选项目集，改进的

FP-tree 是单向的，每个节点只保留了指向父节点的指针，可节约树空间。实验结果表明 FP-MFI 算法在数据库中频繁项目

很多，而每一个事务中频繁项目很少的情况下，比同样基于 FP-tree 的 DMFIA 算法挖掘最大频繁项目集的效率更高。

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

0 引言

关联规则揭示项集间的相关联系，从海量数据中挖掘关联规则是数据挖掘的重要研究课题。但是没有

强有力的分析工具，理解这些海量的、类型各异的数据已经远远超出了人的能力。传统的 Apriori 及其改

进算法，要多遍扫描数据库并产生大量的候选项集。针对 Apriori 算法的缺陷，Jiawei Han 提出 FP-

growth 算法，该算法采用 FP-tree 数据结构，该结构在经过两次扫描数据集后，把数据集中的频繁信息

压缩存入 FP-tree 中，同时依然保留其中的关联信息。从而将对数据集的挖掘转化到对 FP-tree 的挖掘，

无须生成候选项目集，提高的频繁项目集的挖掘效率。，但如果大项集的数量很多，并且如果由原数据库

得到的 FP-tree 的分支很多且分支长度很长时，该算法需要构造出数量巨大的条件 FP-tree，不仅费时而

且占用大量的空间，挖掘效率不高，而且递归算法本身效率也较低。所以在挖掘大型数据库的时，占用内

存大，运行速度慢。挖掘关联规则的挑战性在于数量巨大，算法的效率是关键，因此在利用 FP-tree 数据

结构优势的基础上，研究出更加高效的适合挖掘大规模数据库的挖掘算法是目前数据挖掘研究的重要内

容之一。

1.新 FP-tree 的设计与构造

事务数据库中有用的频繁模式信息对于频繁模式挖掘来说才是最有用的，因此，如果能够从事务数

据库中提取所有的频繁模式将其构造为压缩的结构，并且精减节点的指针域，然后基于此结构进行挖掘

不需要重复遍历，那么在一定程度上将提高挖掘的效率。本文就是基于这一思想来设计 FP 一树的数据结

构。

1.1 新 FP-tree 的改进思想

新 FP 树的构造基于以下思想分析:

1、 FP-growth 算法中的 FP 树和条件 FP 树都需要自顶向下生成，而频繁模式的挖掘自底向上处理。由

于条件 FP 树是递归生成的，因此 FP 树和条件 FP 树都必须双向可遍历，这些树的节点就需要大量的指针

域，这样维护 FP 树和条件 FP 树就需要占用大量的内存空间。FP-MFI 算法对 FP 一树做了改进，改进的 FP

一树是单向的，只有从树叶到树根的路径，不存在从树根到树叶的路径，可节约树空间。

2、由于在频繁模式挖掘中，只需要那些满足最小支持度阀值的项目就可以，因此，有必要首先扫描

一次事务数据库 D 找出所有频繁的项目，同时可以得到项目的支持度计数。并将频繁出现的项目压缩存储

在一种数据结构里，那么有可能避免对原始事务的重复扫描，减小I/O 开销。

3、如果多个事务有相同的频繁项目，那么可以根据支持度相加的方式合并。如果所有事务的频繁项目

按顺序排序，那么很容易去检查两个项目集是否相同。

4、如果两个事务共享公共前缀，那么根据支持度大小对频繁项目进行排列，在树中相同前缀部分只

需要将支持度计数相加。

根据上面的分析并参考文献，本文可以定义如下的一种数据结构:

（1）改进的 FP 一树节点包含四个字段:项目名node name、支持度计数 node count、指向右兄弟节点

或节点链中下一节点的指针 node link及指向最左子女节点的指针 node-parent。

(2)频繁项目头表的每个项目包含两个域:项目名item name、节点链的头指针 item head(指向该项

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

基于FP-tree最大频繁项集的FP-MFI算法的研究摘要：由于基于FP-tree的DMFIA算法在生成最大频繁项目集时会产生大量的候选频繁项集，本文改进传统的FP-tree结构，并提出了一种基于改进FP-tree的最大频繁模式挖掘算法FP-MFI，该算法不需要生成最大频繁候选项目集，改进的FP-tree是单向的，每个节点只保留了指向父节点的指针，可节约树空间。实验结果表明FP-MFI算法在数据库中频繁项目很多，而每一个事务中频繁项目很少的情况下，比同样基于FP-tree的DMFIA算法挖掘最大频繁项目集的效率更高。关键词：数据挖掘；关联规则；最大频繁项集；频繁模式树0引言关联规则揭示项集间的...

展开>> 收起<<

基于FP-tree挖掘最大频繁项集的FP-MFI算法的研究.doc

共6页,预览1页

还剩页未读，继续阅读

基于FP-tree挖掘最大频繁项集的FP-MFI算法的研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: