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

Pruning strategy for mining maximal frequent itemsets

最大频繁项集挖掘可以广泛应用在多种重要的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...