基于频繁模式树的最大频繁模式挖掘算法

为减少高昂的计算代价 ,用挖掘最大频繁模式集代替挖掘频繁模式集是近年来提出的一个重要研究策略。由最大频繁模式集可求出所有频繁模式 ,但数量上却可以小几个数量级 ,从而可大大减少计算代价。通过对最大频繁模式挖掘的问题描述 ,以及关键问题的分析 ,针对频繁模式树 (FP- tree)和最大频繁模式的特点 ,给出了基于频繁模式树的最大频繁模式挖掘算法 (MMFP) ,采取先挖掘候选最大频繁模式再判断子集的方法 ,经示例分析表明该算法是有效的。提出的单路径修剪和项目修剪等修剪方法大大减少了侯选最大频繁模式的个数 ,对算法的性能提高起到了关键作用。

An Efficient FP-tree Based Algorithm for Mining the Maximal Frequent Patterns

The mining of frequent patterns has been studied extensively in data mining research.Because of the huge number of frequent patterns to be found,an interesting alternative has been proposed recently.Instead of mining the complete set of frequent patterns,the new model only finds out the maximal frequent patterns,which can generate all frequent patterns.The orders of the magnitude are smaller than the complete set of frequent patterns.This paper proposes an efficient FP-tree based algorithm,MMFP(Mining Maximal Frequent patterns),with the development of two techniques:(1)single FP-tree path pruning,(2)itemset pruning.These techniques prune the search space enormously.Our performance study shows the advantage of these techniques and that the MMFP may have a good performance in terms of runtime and memory usage.