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

3.0 范春蓉 2024-09-25 12 4 48KB 5 页 15积分

侵权投诉

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

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

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

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

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

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

Research of Maximal frequent item FP-MFI arithmetic Based on FP-tree

ZHENG Hai-ming

Jili University Computer Science and Technology Institute 135000

Abstract: Because of generating the candidate ones in the maximal frequent item-sets and it will bring on a batch of the candidate

sets， this paper improved the traditional FP-tree structure and proposed the maximal frequent item-sets mining algorithm based on

the improved FP-tree. It needn't to generate the candidate maximal frequent item-sets. The improved FP-tree is unilateralist ， and

each point save the pointers of the parents'， which will economize memory. It is shown in our experimental results that the FP-MFI

algorithm is more effectively than the DMFIA also based on FP-tree in the mining maximal frequent item-sets when the frequent

items are very much in database and they are so few in each transaction.

Key words: Data mining； Association rules； Maximal frequent item； FP-tree

0 引言

传统的 Apriori 及其改进算法，要多遍扫描数据库并产生大量的候选项集。针对 Apriori 算法的缺陷，

Jiawei Han 提出 FP-growth 算法，该算法采用 FP-tree 数据结构，该结构在经过两次扫描数据集后，把

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

对 FP-tree 的挖掘，无须生成候选项目集，提高的频繁项目集的挖掘效率[1-2]。但如果大项集的数量很多，

并且如果由原数据库得到的 FP-tree 的分支很多且分支长度很长时，该算法需要构造出数量巨大的条件

FP-tree，不仅费时而且占用大量的空间，挖掘效率不高，而且递归算法本身效率也较低。所以在挖掘大

型数据库的时，占用内存大，运行速度慢。因此在利用 FP-tree 数据结构优势的基础上，研究出更加高效

的适合挖掘大规模数据库的挖掘算法是目前数据挖掘研究的重要内容之一。

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

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

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

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

构。

1.1 新 FP-tree 的改进思想

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

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

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

域，这样维护 FP 树和条件 FP 树就需要占用大量的内存空间。改进的 FP 一树是单向的，只有从树叶到树根

的路径，不存在从树根到树叶的路径，可节约树空间。

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

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

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

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

15 积分 4人已下载

立即下载

摘要：

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

展开>> 收起<<

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

共5页,预览1页

还剩页未读，继续阅读

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

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: