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

来源：计算机应用杂志2017年第8期北京时间：

作者：李校林, 杜托, 刘彪

单位：1. 重庆邮电大学 通信新技术应用研究中心, 重庆 400065;2. 重庆信科设计有限公司, 重庆 400065

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

关键词：数据挖掘,模式挖掘,频繁项集,遍历构造树,构造链表

基金资助：重庆市研究生科研创新基金资助项目（CYS15166）。