An Algorithm Of Maximal Frequent Itemsets Mining Based On Dynamic Reordering

Frequent itemsets mining plays a crucial role in many data mining applications, which dominates the time complexity of the discovery algorithms, the algorithem of mining frequent itemsets will have a direct impact on the efficiency and the rang of application, especially mining the association rules.Althought the freuqent closed itemsets mining algorithm can avoid the problem that is the frequent itemsets mining algorithm generate too much frequent itmesets. when the dataset is more dense or the minimum support is much lower, the performance of the freuqent closed itemsets mining algorithm will drop sharply.The valuable information is often hidden in long pattern in dense data sets.The maximum frequent itemsets(MFI for short) are that the itemset is frequent and every proper superset is infrequent. The number of MFIs is much smaller than that of frequent closed itemsets and also far less than the complete frequent itemsets.Mining MFIs can effectively reduce the scale of the problem solving, which has important significane.MFIs mining is a time-consuming task, pruning strategies are widely used to improve the efficiency of search. Data structure, searching strategies and the classic pruning strategies are thoroughly studied. Based on the thorough analysis, we develop a new algorithm called MPDR for more efficient maximal frequent itemset mining, our method uses a novel probing and reordering search method, one of the MFIs found so far is choosed as key pattern to dynamicly schedule its future search so that many search subspaces can be pruned. All the children of node in search space can be divided by key pattern into two groups: the promising children, whose descendants may have new MFIs, and unpromising children, whose descendants do not have new MFIs. The unproming children will be pruned, only the promising children are searched in a recursive way. we use the FP-tree as the main data structure. Compared with the FPMax algorithm and GenMax algorithm, our new algorithm has some advantages.