基于最频繁项提取和候选集剪枝的THIMFUP算法

吉林大学学报(理学版) ›› 2021, Vol. 59 ›› Issue (3): 635-642.

基于最频繁项提取和候选集剪枝的THIMFUP算法

杨勇^1,2, 张磊¹, 曲福恒¹, 刘俊杰¹, 陈强¹

1. 长春理工大学计算机科学技术学院, 长春 130022； 2. 长春师范大学教育学院, 长春 130032

收稿日期:2020-09-15 出版日期:2021-05-26 发布日期:2021-05-23

THIMFUP Algorithm Based on the Most Frequent Item Extraction and Candidate Set Pruning

YANG Yong^1,2, ZHANG Lei¹, QU Fuheng¹, LIU Junjie¹, CHEN Qiang¹

1. School of Computer Science and Technology, Changchun University of Science and Technology, Changchun 130022, China；
2. Institute of Education, Changchun Normal University, Changchun 130032, China

Received:2020-09-15 Online:2021-05-26 Published:2021-05-23
Contact: 杨勇 E-mail:yy@cust.edu.cn

摘要/Abstract

摘要： 针对FBCM(基于矩阵压缩FUP(fast update algorithm))算法在项集挖掘过程中存在频繁扫描原频繁项集库, 并生成大量候选集的问题, 提出一种通过提取数据库中最频繁项的方法, 以降低对原频繁项集库的扫描次数；并通过候选集剪枝思想, 减少算法整体运行过程中的候选集生成, 以提高频繁项集的挖掘速度. 实验结果表明, 在相同实验条件下, 该算法的效率比FBCM算法效率提高15%以上, 最高达60%.

关键词: 关联规则, 增量挖掘, 候选集剪枝, 最频繁项

Abstract: Aiming at the problem that FBCM (FUP (fast update algorithm) based on matrix compression) algorithm frequently scanned the original frequent itemset library and generated a large number of candidate sets in the process of item set mining. We proposed a method to extract the most frequent items from the database to reduce the scanning times on the original frequent itemset library, and through a candidate set pruning idea, it reduced the generation of candidate sets in the whole running process of the algorithm, so as to improve the speed of frequent itemset mining. Experimental results show that the efficiency of the algorithm is 15% higher than that of FBCM algorithm, and the highest is 60% under the same experimental conditions.

Key words: association rule, incremental mining, candidate set pruning, most frequent item

中图分类号:

TP301.6

杨勇, 张磊, 曲福恒, 刘俊杰, 陈强. 基于最频繁项提取和候选集剪枝的THIMFUP算法[J]. 吉林大学学报(理学版), 2021, 59(3): 635-642.

YANG Yong, ZHANG Lei, QU Fuheng, LIU Junjie, CHEN Qiang. THIMFUP Algorithm Based on the Most Frequent Item Extraction and Candidate Set Pruning[J]. Journal of Jilin University Science Edition, 2021, 59(3): 635-642.

[1]	冯锋, 张珑耀, 张青. 基于软集上逻辑公式的极大关联规则描述与挖掘方法[J]. 吉林大学学报(理学版), 2018, 56(4): 901-908.
[2]	曹莹, 苗志刚. 基于向量矩阵优化频繁项的改进Apriori算法[J]. 吉林大学学报(理学版), 2016, 54(02): 349-353.
[3]	解男男, 胡亮, 努尔布力, 樊丽, 印晓天. 基于Web日志挖掘的网页推荐方法[J]. J4, 2013, 51(02): 267-272.
[4]	董立岩, 刘光远, 苑森淼, 李永丽, 吴志辉. 数据挖掘技术在交通事故分析中的应用[J]. J4, 2006, 44(06): 951-955.
[5]	王媛, 刘衍珩, 田大新. 分布式数据挖掘[J]. J4, 2006, 44(06): 80-84.
[6]	陆楠,, 周栩. 数值约束条件下的模糊关联规则挖掘方法[J]. J4, 2006, 44(06): 101-106.
[7]	陆楠,. 一种关联规则挖掘的裁剪及优化方法[J]. J4, 2006, 44(06): 107-115.
[8]	徐秀娟, 贾立峰, 周春光, 王喆, 徐笑昂. 商业销售中的利润挖掘及商品选择算法[J]. J4, 2006, 44(02): 201-206.
[9]	欧阳继红, 王仲佳, 刘大有. 具有动态加权特性的关联规则算法[J]. J4, 2005, 43(03): 314-319.
[10]	胡陈勇, 刘大有, 刘亚波. 一种扩展的关联规则挖掘算法[J]. J4, 2005, 43(02): 153-156.
[11]	刘大有, 刘亚波, 尹治东. 关联规则最大频繁项目集的快速发现算法[J]. J4, 2004, 42(02): 212-215.
[12]	陆楠, 王哲, 周春光. 基于FP-tree频集模式的FP-Growth算法对关联规则挖掘的影响[J]. J4, 2003, 41(02): 180-185.