Efficiently Mining Maximal Frequent Itemsets by Item Grouping and 3-Dimensional Indexing

Fan-Chen Tseng ； Guo-Sheng Fu

《Electronic Commerce Studies》 4卷1期 (2006/03) Pp. 37-55

https://doi.org/10.29767/ECS.200603.0003

並列摘要

The mining of frequent itemsets has wide applications in data mining, and many methods have been proposed for this problem. However, mining the complete set of frequent itemsets often leads to a huge solution space. Fortunately, this problem can be reduced to the mining of Frequent Closed Itemsets (FCIs), which results in a much smaller solution space. Nevertheless, in some applications the number of FCIs is still too large. In such cases, the alternative is to mine the Maximal Frequent Itemsets (MFIs). In this paper, we propose a compact data structure, the Transaction Pattern List (TPL), for representing the transaction database. Efficient pruning of the search space can be accomplished with TPL. Besides, we develop the technique of item grouping to shorten the search paths and speed up the mining process. For the superset checking before generating new MFIs, we take advantage of the basic properties of itemsets to derive the three-dimensional indexing for quickly locating the set of relevant MFIs to be checked. Experimental results show that our method is more efficient than previously existing methods.

並列關鍵字

Data Mining ； Maximum Frequent Itemset ； Transaction Pattern List TPL ； Item Grouping ； 3D-Indexing

參考文獻

Agrawal, R.,Srikant, R.(1994).Fast Algorithms for Mining Association Rules in Large Databases.Proc. 20th VLDB.(Proc. 20th VLDB).

Agarwal, R. C.,Aggarwal, C. C.,Prasad, V. V. V.(2000).Depth First Generation of Long Patterns.Proc. ACM SIGMOD.(Proc. ACM SIGMOD).

R. J. Bayardo(1998).Efficiently mining long patterns from databases.(Proc. ACM SIGMOD).

D. Burdick(2001).MAFIA: a maximal frequent itemsets algorithm for transactional databases.(Proc. ICDE).

Han, J.,Pei, J.,Yin, Y.(2000).Mining frequent patterns without candidate generation.(Proc. ACM SIGMOD).