A Patricia-Tree Approach for Frequent Closed Itemsets

Authors: Moez Ben Hadj Hamida, Yahya SlimaniI

Abstract:

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.

Keywords: Datamining, Frequent itemsets, Frequent closeditemsets, Sparse datasets.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077795

References:

[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.