一种改进的基于FP-Tree的高效挖掘最大频繁项目集算法  

Improved Algorithm for Efficiently Mining Maximum Frequent Itemsets Based on Frequent Pattern Tree

作　　者：尹治华[1] 张大鹏[1,2] 谭明[1] 王新生[1] YIN Zhihua ZHANG Dapeng TAN Ming WANG Xinsheng(School of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004 ,China)

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004 [2]桂林电子科技大学广西可信软件重点实验室,广西桂林541004

出　　处：《济南大学学报（自然科学版）》2017年第2期111-117,共7页Journal of University of Jinan(Science and Technology)

基　　金：国家自然科学基金项目(61303129);广西可信软件重点实验室开放基金项目(KX201212)

摘　　要：为了解决最大频繁项目集算法DMFIA(discover maximum frequent itemsets algorithm)在挖掘候选项目集维数较大而最大频繁项目集维数较小的情况下产生大量候选项目集的问题,提出一种改进的基于FP-Tree(frequent pattern tree)的最大频繁项目集挖掘的FP-EMFIA算法;该算法在挖掘过程中根据项目头表,采用自上而下和自下而上的双向搜索策略,并通过条件模式基中的频繁项目和较小维数的非频繁项目集对候选项目集进行降维和剪枝,以减少候选项目集的数量,加速对候选集计数的操作。在经典数据集mushroom、chess和connect上的实验结果表明,FP-EMFIA算法在支持度较小时的时间效率优于DMFIA、IDMFIA(improved algorithm of DMFIA)和BDRFI(algorithm for mining frequent itemsets based on decreasing dimensionality reduction of frequent itemsets)算法的,说明FP-EMFIA算法在候选项目集维数较大时有相对优势。In order to solve the problem with a large number of candidate itemsets, caused by DMFIA （ discover maximum frequent itemsets algorithm） mining the candidate itemsets with large dimension, whereas maximal frequent itemsets being small dimension, an improved algorithm for efficiently mining maximum frequent itemsets based on FP-Tree （frequent pat- tern tree） named FP-EMFIA was put forward. In the process of mining, according to the program header table, FP-EMFIA adopted the bidirectional search strategy of up-down and down-up, and did the reduction dimension and pruning for the candidate itemsets through the frequent itemsets in the conditional pattern base and the infrequent itemsets with small di- mension to sharply reduce the number of candidate itemsets and speed up the counting operation of the candidate item- sets. The experimental results of the classical mushroom dataset, chess dataset and connect dataset show that, when the support is small, the time-efficiency of the FP-EMFIA significantly outperforms the time-efficiency of DMFIA, IDMFIA （the improved algorithm of DMFIA）and BDRFI（ algorithm for mining frequent itemsets based on decreasing dimensionality reduction of frequent itemsets）. FP-EMFIA has relatively obvious advantage when the dimension of processing candidate itemsets is large.

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

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