基于Flag-Prefix-Tree的频繁模式挖掘改进算法  

An Improved Algorithm for Mining Frequent Patterns Based on Flag-Prefix-Tree

作　　者：蒋跃军 郑文[1] JIANG Yuejun;ZHENG Wen(Zhejiang Wanli University,Ningbo Zhejiang 315100)

机构地区：[1]浙江万里学院,浙江宁波315100

出　　处：《浙江万里学院学报》2024年第3期76-81,共6页Journal of Zhejiang Wanli University

摘　　要：稀疏数据集上,条件FP-Tree无法有效压缩且频繁构造开销大,使用伪构造的问题是数据项目未经压缩和过滤导致额外的遍历代价。文章提出了一种简单而新颖的标志前缀树(Flag-Prefix-Tree)和一种新的挖掘稀疏数据集上频繁模式的算法FPT-Mine。通过Flag-Prefix-Tree中的flag,伪构造条件树可以巧妙地过滤不频繁项目。而且flag可以在挖掘过程中递归地重用,只有非常小的开销,但节省了遍历不频繁项目的大量开销。FPT-Mine以自上向下的顺序遍历Flag-Prefix-Tree,并为每个频繁模式创建一个临时根表(Root table)来伪构造条件树,这样就不需要在每个节点上维护父节点和兄弟节点的链接。此外,FPT-Mine在树上应用了合并技术,这使得FlagPrefix-Tree越来越小。研究表明,FPT-Mine在各种稀疏数据集中具有高性能和可扩展性。FPT-Mine在所有测试数据集中的性能都优于FP-growth,当最小支持度阈值降低时,算法之间的差距增大。The current research has a limitation of using conditional FP-Tree on the sparse dataset,which results in ineffective compression and expensive frequent construction.The negative impact of using pseudo-construction is that the database is not compressed and filtered,resulting in additional traversal costs.To address these limitations,this paper proposes a simple and innovative Flag-Prefix-Tree and a new algorithm FPT-Mine that can effectively mine frequent patterns on sparse datasets.By using FlagPrefix-Tree,the pseudo-constructed conditional tree can cleverly filter infrequent items,which saves significant overhead while mining.In addition,FPT-Mine searches Flag-Prefix-Tree in top-down order and creates a temporary Root table(pseudo-constructed conditional tree) for each frequent pattern so that there is no need to maintain the parent and brother node links on each node.Furthermore,the merging technique applied to the tree further reduces the size of the Flag-Prefix-Tree.The study shows that FPTMine has high performance and scalability,outperformed FP-growth in all the tested datasets,and the gap between the algorithms increases when the minimum support threshold is lowered.

关 键 词：数据挖掘 关联规则 频繁模式 频繁项目集 

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]