Abstract
The traditional association rule mining framework produces many redundant rules. The extent of redundancy is a lot larger than previously suspected. We present a new framework for associations based on the concept of closed frequent itemsets. The number of non-redundant rules produced by the new approach is exponentially (in the length of the longest frequent itemset) smaller than the rule set from the traditional approach. Experiments using several “hard” as well as “easy” real and synthetic databases confirm the utility of our framework in terms of reduction in the number of rules presented to the user, and in terms of time.
Similar content being viewed by others
References
Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., and Inkeri Verkamo, A. 1996. Fast discovery of association rules. In Advances in Knowledge Discovery and Data Mining, U. Fayyad et al. (Eds.), Menlo Park, CA: AAAI Press, pp. 307–328
Bastide, Y., Pasquier, N., Taouil, R., Stumme, G., and Lakhal, L. 2000a. Mining minimal non-redundant association rules using frequent closed itemsets. In 1st International Conference on Computational Logic.
Bastide, Y., Taouil, R., Pasquier, N., Stumme, G., and Lakhal, L. 2000b. Mining frequent patterns with counting inference. SIGKDD Explorations, 2(2).
Bayardo, R.J. 1998. Efficiently mining long patterns from databases. In ACM SIGMOD Conf. Management of Data.
Bayardo, R.J. and Agrawal, R. 1999. Mining the most interesting rules. In 5th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining.
Brin, S., Motwani, R., Ullman, J., and Tsur, S. 1997. Dynamic itemset counting and implication rules for market basket data. In ACM SIGMOD Conf. Management of Data.
Burdick, D., Calimlim, M., and Gehrke, J. 2001. MAFIA: A maximal frequent itemset algorithm for transactional databases. In Intl. Conf. on Data Engineering.
Davey, B.A. and Priestley, H.A. 1990. Introduction to Lattices and Order. Cambridge University Press.
Ganter, B. and Wille, R. 1999. Formal Concept Analysis: Mathematical Foundations. Springer-Verlag.
Godin, R., Missaoui, R., and Alaoui, H. 1995. Incremental concept formation algorithms based on galois (concept) lattices. Computational Intelligence, 11(2):246–267.
Guigues, J.L. and Duquenne, V. 1986. Familles minimales d'implications informatives resultant d'un tableau de donnees binaires. Math. Sci. hum., 24(95):5–18.
Klemettinen, M., Mannila, H., Ronkainen, P., Toivonen, H., and Verkamo, A.I. 1994. Finding interesting rules from large sets of discovered association rules. In 3rd Intl. Conf. Information and Knowledge Management, pp. 401–407.
Lin, D.-I. and Kedem, Z.M. 1998. Pincer-search: A new algorithm for discovering the maximum frequent set. In 6th Intl. Conf. Extending Database Technology.
Liu, B., Hsu, W., and Ma, Y. 1999. Pruning and summarizing the discovered associations. In 5th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining.
Luxenburger, M. 1991. Implications partielles dans un contexte. Math. Inf. Sci. hum., 29(113):35–55.
Ng, R.T., Lakshmanan, L., Han, J., and Pang, A. 1998. Exploratory mining and pruning optimizations of constrained association rules. In ACM SIGMOD Intl. Conf. Management of Data.
Pasquier, N., Bastide, Y., Taouil, R., and Lakhal, L. 1999a. Discovering frequent closed itemsets for association rules. In 7th Intl. Conf. on Database Theory.
Pasquier, N., Bastide, Y., Taouil, R., and Lakhal, L. 1999b. Efficient mining of association rules using closed itemset lattices. Information Systems, 24(1):25–46.
Pei, J., Han, J., and Mao, R. 2000. Closet: An efficient algorithm for mining frequent closed itemsets. In SIGMOD Int'l Workshop on Data Mining and Knowledge Discovery.
Savasere, A., Omiecinski, E., and Navathe, S. 1995. An efficient algorithm for mining association rules in large databases. In 21st VLDB Conf.
Taouil, R., Bastide, Y., Pasquier, N., and Lakhal, L. 2000. Mining bases for association rules using closed sets. In 16th IEEE Intl. Conf. on Data Engineering.
Toivonen, H., Klemettinen, M., Ronkainen, P., Hätönen, K., and Mannila, H. 1995. Pruning and grouping discov-ered association rules. In MLnet Wkshp. on Statistics, Machine Learning, and Discovery in Databases.
Zaki, M.J. and Hsiao, C.-J. 2002. CHARM: An efficient algorithm for closed itemset mining. In 2nd SIAM International Conference on Data Mining.
Zaki, M.J. and Ogihara, M. 1998. Theoretical foundations of association rules. In 3rd ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.
Zaki, M.J., Parthasarathy, S., Ogihara, M., and Li, W. 1997. New algorithms for fast discovery of association rules. In 3rd Intl. Conf. on Knowledge Discovery and Data Mining.
Zaki, M.J. and Phoophakdee, B. 2003. MIRAGE: A framework for mining, exploring and visualizing minimal association rules. Technical Report 03–4, Computer Science Dept., Rensselaer Polytechnic Institute.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Zaki, M.J. Mining Non-Redundant Association Rules. Data Mining and Knowledge Discovery 9, 223–248 (2004). https://doi.org/10.1023/B:DAMI.0000040429.96086.c7
Issue Date:
DOI: https://doi.org/10.1023/B:DAMI.0000040429.96086.c7