最大频繁项集挖掘中搜索空间的剪枝策略  

Pruning strategy for mining maximal frequent itemsets

作　　者：马志新[1] 陈晓云[1] 王雪[1] 李龙杰[1] 

机构地区：[1]兰州大学信息科学与工程学院,兰州730000

出　　处：《清华大学学报（自然科学版）》2005年第S1期1748-1752,共5页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金资助项目(60473095)

摘　　要：最大频繁项集挖掘可以广泛应用在多种重要的Web挖掘工作中.为了有效地削减搜索空间,提出了一种新的最大频繁项集挖掘中的搜索空间剪枝策略.这种策略基于深度优先遍历词典序子集枚举树,利用树中子节点与父节点扩展集中相同项的扩展支持度相等的特性,对搜索空间进行剪枝.应用该策略,对MAFIA算法进行改进优化.实验结果表明,该剪枝策略可以有效削减搜索空间,尤其在稀疏但包含长频繁项集的数据集上,搜索空间削减掉2/3,算法的时间效率比原MAFIA算法提高3～5倍.Mining maximal frequent itemsets is a fundamental problem in many practical web mining applications. This paper presents ESEquivPS extension support equivalency pruning strategy, a new search space pruning strategy for mining maximal frequent itemsets to effectively reduce the search space. ESEquivPS was based on a depthfirst traversal of lexicographic subset enumeration tree and uses equivalency of item s extension supports to prune search space. Furthermore, the MAFIA maximal frequent itemset algorithm wa...

关 键 词：WEB挖掘 最大频繁项集 剪枝策略 搜索空间 

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