Skip to main content
Log in

Mining Non-Redundant Association Rules

  • Published:
Data Mining and Knowledge Discovery Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

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

    Google Scholar 

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

    Google Scholar 

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

    MathSciNet  Google Scholar 

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

    MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints 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

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:DAMI.0000040429.96086.c7

Navigation