A Patricia-Tree Approach for Frequent Closed Itemsets

In this paper, we propose an adaptation of the Patricia-Tree for sparse datasets to generate non redundant rule associations. Using this adaptation, we can generate frequent closed itemsets that are more compact than frequent itemsets used in Apriori approach. This adaptation has been experimented on a set of datasets benchmarks.

• Moez Ben Hadj Hamida
• Yahya SlimaniI

• Datamining
• Frequent itemsets
• Frequent closeditemsets
• Sparse datasets.

[1] J.S. Park, M.S. Chen and P.S. Yu, "An Effective Hash Based Algorithm for Mining Association Rules," in Proc. 5th SIGMOD Intl. W orkshop. Management of Data, California, 1995, pp. 175-186.
[2] R. Agrawal and R. Srikant, "Fast Algorithms for Mining Association
Rules. 20th Intl. Conf. Very Large Data Bases, Santiago, 1994, pp. 487-
499.
[3] A. Savasere, E. Omiecinski and S. Navathe, "An Efficient Algorithm for
Mining Association Rules in Large Databases," in Proc. 21th Intl. Conf.
Very Large Data Bases, Santiago, 1995, pp. 487-499.
[4] S. Brin, R. Motwani, J. Ullman and S. Tsur, "Dynamic itemset counting
and implication rules for market basket data," in Proc. 7th SIGMOD Intl.
W orkshop. Management of Data, Arizona, 1997, pp. 255-264.
[5] K. Wang, L. Tang, J. Han and J. Liu, "Top Down FP-Growth for
Association Rule Mining," in Proc. 6 th Pacific-Asia Conf. Advances in
Knowledge Discovery and Data Miningy, Taipei, 2002, pp. 334-370.
[6] J. Pei, J. Han, H. Lu, S. Nishio, S. Tang and D. Yang, "H-Mine: Hyper-
Structure Mining of Frequent Patterns in Large Databases," in Proc. 1st
IEEE Intl. Conf. Data Mining, California, 2001, pp. 441-448.
[7] A. Pietracaprina and D. Zandolin, "Mining Frequent Itemsets using
Patricia Tries," in Proc. 1st FIMI Workshop. Frequent Itemset Mining
Implementations, Florida, 2003.
[8] N. Pasquier, Y. Bastide, R. Taouil and L. Lakhal, "Discovering Frequent
Closed Itemsets for Association Rules," in Proc. 7th Intl. Conf. Database
Theory, Jerusalem, 1999, pp. 398-416.
[9] M.J. Zaki and C. Hsiao, "CHARM: An Efficient Algorithm for Closed
Itemset Mining," in Proc. 2nd SIAM Intl. Con. Data Mining, Virginia,
2002, pp. 398-416.
[10] J. Pei, J. Han, R. Mao, "CLOSET: An Efficient Algorithm for Mining
Frequent Closed Itemsets," in Proc. 9th SIGMOD Intl. Workshop. Data
Mining and Knowledge Discovery, Dallas, 2000, pp. 11-20.
[11] J. Wang, J. Han and J. Pei, "CLOSET+: Searching for the Best
Strategies for Mining Frequent Closed Itemsets," in Proc. 12th Intl. Conf.
Knowledge Discovery and Data Mining, Washington, 2003, pp. 236-
245.
[12] G. Grahne and J. Zhu, "Efficiently using prefix-trees in mining frequent
itemsets," in Proc. 1st FIMI Workshop. Frequent Itemset Mining
Implementations, Florida, 2003.
[13] M. Ben Hadj Hamida, "Patricia-Tree based algorithm to find frequent
closed itemsets," Master. dissertation, Dept. Comp. Sci., Faculty of
Sciences of Tunis., Tunis, Tunisia, 2005.