基于FPMAX的最大频繁项目集挖掘改进算法  

Mining Maximal Frequent Item Sets with Improved Algorithm of FPMAX

作　　者：牛新征[1] 佘堃[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731

出　　处：《计算机科学》2013年第12期223-228,共6页Computer Science

基　　金：国家自然科学基金(61300192);四川省科技厅科技支撑计划项目(2012GZ0061);中央高校基本科研业务费电子科技大学项目(ZYGX2010J075)资助

摘　　要：挖掘事务数据库中的最大频繁项目集是数据挖掘领域一个重要的研究方向。基于FP-tree的FPMAX算法是目前较为高效与稳定的最大频繁项目集挖掘算法之一。然而对于稠密数据库中的挖掘,FPMAX会产生大量的冗余递归过程,导致额外的条件FP-tree构造开销。而且在支持度较低时,FPMAX则会因用于超集检测的全局MFItree较为庞大而导致超集检测的性能下降。为此提出FPMAX的改进算法FPMAX-reduce,其通过采用基于事务共同后缀的前瞻剪枝策略来减少挖掘过程中的冗余递归过程。当递归过程中产生的新条件FP-tree规模较小时,FPMAX-reduce通过构造条件MFI-tree来减小后续超集检测遍历的开销。性能试验表明,FPMAX-reduce算法通过有效的前瞻剪枝,在稠密事务数据库以及低支持度的情况下至多可将递归过程减少至原算法的一半以下,进而有效地提高了FPMAX算法的效率。Finding maximal frequent itemsets is an important issue in data mining research field. The FPMAX algo- rithm, which is based on the FP-tree structure, has been proved to be one of the high-performance algorithms on maxi- mal frequent itemsets mining. But for data mining task in dense datasets, FPMAX algorithm will construct a large num- ber of redundant conditional FP-tree. What＇s more, if the quantity of frequent itemsets is large, the MFI-tree structure used for subset testing in FPMAX will become quite big, decreasing the efficiency of subset testing in the algorithm. Therefore, this paper proposed the FPMAX-reduce algorithm to overcome those drawbacks of FPMAX. This novel al- gorithm uses a pruning technique based on the common suffix of transactions and greatly reduces the construction of re- dundant conditional FP-tree. Besides,when the scale of the newly constructed conditional FP-tree is small, FPMAX-re- duce constructs a corresponding conditional MFI-tree, which deletes the redundant information, to improves the efficien- cy of subset testing in the following recursive calls. Experimental results show that FPMAX-reduce algorithm effective- ly improves the efficiency of FPMAX and outperforms many existing available algorithms in dense datasets.

关 键 词：频繁项目集 最大频繁项目集 FP-TREE FPMAX FP-GROWTH 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]