基于B-list的快速频繁模式挖掘算法

李校林，杜 托，刘 彪

(1.重庆邮电大学 通信新技术应用研究中心，重庆 400065； 2.重庆信科设计有限公司，重庆 400065)

(*通信作者电子邮箱dutuotuo@yeah.net)

基于B-list的快速频繁模式挖掘算法

李校林1,2，杜 托1*，刘 彪1

(1.重庆邮电大学 通信新技术应用研究中心，重庆 400065； 2.重庆信科设计有限公司，重庆 400065)

(*通信作者电子邮箱dutuotuo@yeah.net)

针对现有的频繁模式挖掘算法存在建树复杂、挖掘效率低等问题，提出一种基于构造链表(B-list)的频繁模式挖掘(BLFPM)算法。BLFPM使用一种新的数据结构B-list表示频繁项集，通过连接两个k-1-频繁项集的B-list可以快速得到k-项集的支持度，避免了多次扫描数据库；针对连接两个B-list时间复杂度高的问题，给出了一种线性时间复杂度的连接方法，提高了BLFPM的时间效率；同时，BLFPM采用集合枚举树代表搜索空间，并使用子集非频繁剪枝策略，减小了频繁模式挖掘的搜索空间，提高了算法的执行速度。实验结果表明，与NSFI算法和prepost算法相比，BLFPM的时间效率提高约12%到29%，空间效率提高约10%到24%，对稀疏数据库或稠密数据库进行频繁模式挖掘均可以得到良好的效果。

数据挖掘；模式挖掘；频繁项集；遍历构造树；构造链表

0 引言

数据挖掘是从大量的数据中挖掘出隐含的、未知的、用户可能感兴趣的知识和规则的过程。关联规则是数据挖掘中非常重要的一个研究方向，能够找到事务之间隐含的人们可能感兴趣的规则，从而为人们带来巨大的价值。在当今大数据时代，如何在海量的数据中挖掘出有价值的关联规则显得尤为重要。……