基于FP-tree的支持度计数优化策略  

Support Count Optimization Method Based on FP-tree

作　　者：赵阳[1] 白凡 

机构地区：[1]江南计算技术研究所,江苏无锡214083

出　　处：《计算机技术与发展》2017年第10期30-33,38,共5页Computer Technology and Development

基　　金：国家科技重点专项"核高基"(2015ZX01040-201)

摘　　要：关联规则挖掘过程中,频繁项集的挖掘是最关键的步骤。最大频繁项集是最常用的频繁项集简化表示。基于FPtree的最大频繁项集挖掘算法多数都需要自底向上地搜索FP-tree来计算项集的支持度。而已有的支持度计算方法在计算当前项集的支持度时没有考虑已完成的支持度计算过程所获得的信息,因而造成了不必要的开销。针对该问题,提出了基于FP-tree的支持度计数优化策略(Support Count Optimization Method on FP-tree,SCOM),在付出很小的额外空间代价的条件下,充分利用已完成的支持度计数过程中获取的路径对项集的支持信息和项集之间的关系进行搜索剪枝,并设计实验将该策略应用到DMFIA算法上。实验结果表明,应用该策略的最大频繁项集挖掘算法DMFIA获得了较大的性能提升。SCOM对基于FP-tree的支持度计数进行优化,因此能够应用到所有利用FP-tree进行支持度计数的算法之中。In the association rules mining, mining frequent itemsets is the most critical step. Maximum frequent itemsets is the most com- mon simplified representation of frequent itemsets. Maximum frequent itemsets mining algorithms based on FP-tree are most needed to search the FP-tree bnttom-up to count the support of the itemsets ,but they have not considered the information obtained by completed support counting while counting the current itemset, resulting in unnecessary overhead. To solve it, Support Count Optimization Method on FP-tree, called SCOM for short,is proposed. With a small additional space cost,it can make full use of the information that whether a path supports a itemset and the relation between the itemsets to prune the search. Experimental results show that the maximum frequent itemsets mining algorithm applied obtains a performance boost with SCOM which optimizes the support count based on FP-tree, so it can be applied to all algorithms that use FP-tree to count support.

关 键 词：关联规则挖掘 FP-TREE 最大频繁项集 支持度计数 搜索剪枝 

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