Concise representations for association rules in multi-level datasets

Abstract

Association rule mining plays an important role in knowledge and information discovery. Often for a dataset, a huge number of rules can be extracted, but many of them are redundant, especially in the case of multi-level datasets. Mining non-redundant rules is a promising approach to solve this problem. However, existing work (Pasquier et al. 2005, Xu & Li 2007) is only focused on single level datasets. In this paper, we firstly present a definition for redundancy and a concise representation called Reliable basis for representing non-redundant association rules, then we propose an extension to the previous work that can remove hierarchically redundant rules from multi-level datasets. We also show that the resulting concise representation of non-redundant association rules is lossless since all association rules can be derived from the representation. Experiments show that our extension can effectively generate multilevel non-redundant rules.

Keywords

Association rule mining / redundant association rules / closed itemsets / multi-level datasets

References

[1] Bayardo R.J., Agrawal R., Gunopulos D.. Constraint-based rule mining in large, dense databases. Data Mining and Knowledge Discovery, 2000, 4: 217-240.

[2] Berry, M.J.A. & Linoff, G.S. (1997). Data Mining Techniques for Marketing Sales and Customer Support. John Wiley and Sons

[3] Brin, S., Motwani, R., Ullman, J.D. & Tsur, S. (1997). Dynamic itemset counting and implication rules for market basket data. In: Proceedings of the 1997 ACM SIGMOD Conference, 255–264

[4] Ganter, B. & Wille, R. (1999). Formal Concept Analysis: Mathematical Foundations. Springer-Verlag

[5] Han, J. & Fu, Y. (1995). Discovery of multiple-level association rules from large databases. In: Proceedings of the 21st International Conference on Very Large Databases, 420–431

[6] Han J., Fu Y.. Mining multiple-level association rules in large databases. IEEE Transactions on Knowledge and Data Engineering, 1999, 11(5): 798-805.

[7] Han J., Pei J.. Mining Frequent Patterns by Pattern-Growth: Methodology and Implications. ACM SIGKDD Explorations Newsletter., 2000, 2: 14-20.

[8] Hong T.P., Lin K.Y., Chien B.C.. Mining fuzzy multiple-level association rules from quantitative data. Applied Intelligence, 2003, 18(1): 79-90.

[9] Kaya, M. & Alhajj, R. (2004). Mining multi-cross-level fuzzy weighted association rules. In: the 2nd International IEEE Conference on Intelligent Systems, 225–230

[10] Kryszkiewicz M., Rybinski H., Gajek M.. Dataless transitions between concise representations of frequent patterns. Journal of Intelligent Information Systems, 2004, 22(1): 41-70.

[11] Ng, R.T., Lakshmanan, V., Han, J. & Pang, A. (1998). Exploratory mining and pruning otimizations of constrained association rules. In: Proceedings of the SIGMOD Conference, 13–24

[12] Pasquier N., Bastide Y., Taouil R., Lakhal L.. Efficient mining of association rultes using closed itemset lattices. Information Systems, 1999, 24(1): 25-46.

[13] Pasquier N., Taouil R., Bastide Y., Stumme G., Lakhal L.. Generating a condensed representation for association rules. Journal of Intelligent Information Systems, 2005, 24(1): 29-60.

[14] Srikant, R., Vu, Q. & Agrawal, R. (1997). Mining association rules with item constraints. In: Proceedings of the KDD Conference, 67–73

[15] Thakur, R.S., Jain, R.C. & Pardasani, K.P. (2006). Mining level-crossing association rules from large databases. Journal of Computer Science, 76–81

[16] Wille, R. (1982). Restructuring lattices theory: An approach based on hierarchies of concepts. In: Rival, I. (ed.), Ordered Sets. Dordrecht-Boston

[17] Xu, Y. & Li, Y. (2007). Generating concise association rules. In: Proceedings of the 16th ACM Conference on Information and Knowledge Management (CIKM07), 781–790

[18] Zaki, M.J. (2000). Generating nonredundent association rules. In: Proceedings of the KDD Conference, 34–43

[19] Zaki M.J.. Mining non-redundant association rules. Data Mining and Knowledge Discovery, 2004, 9: 223-248.

[20] Ziegler, C.N., McNee, S.M., Konstan, J.A. & Lausen, G. (2005). Improving recommendation lists through topic diversification. In: Proceedings of the 14th International World Wide Web Conference (WWW05), 22–32