Essential classification rule sets

ABSTRACT

Given a class model built from a dataset including labeled data, classification assigns a new data object to the appropriate class. In associative classification the class model (i.e., the classifier) is a set of association rules. Associative classification is a promising technique for the generation of highly accurate classifiers. In this article, we present a compact form which encodes without information loss the classification knowledge available in a classification rule set. This form includes the rules that are essential for classification purposes, and thus it can replace the complete rule set. The proposed form is particularly effective in dense datasets, where traditional extraction techniques may generate huge rule sets. The reduction in size of the rule set allows decreasing the complexity of both the rule generation step and the rule pruning step. Hence, classification rule extraction can be performed also with low support, in order to extract more, possibly useful, rules.

REFERENCES

• 1: Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, A tree projection algorithm for generation of frequent item sets, Journal of Parallel and Distributed Computing, v.61 n.3, p.350-371, March 1, 2001 [doi>10.1006/jpdc.2000.1693]
• 2: R. Agrawal , T. Imielinski , A. Swami, Database Mining: A Performance Perspective, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.914-925, December 1993 [doi>10.1109/69.250074]
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: Baralis, E. and Chiusano, S. 2002. Minimal non redundant classification rule sets. In Proceedings of the IEEE ICDM Workshop on The Foundation of Data Mining and Discovery. 143--149.
• 5: Elena Baralis , Paolo Garza, A Lazy Approach to Pruning Classification Rules, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.35, December 09-12, 2002
• 6: Yves Bastide , Rafik Taouil , Nicolas Pasquier , Gerd Stumme , Lotfi Lakhal, Mining frequent patterns with counting inference, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.66-75, Dec. 2000 [doi>10.1145/380995.381017]
• 7: Yves Bastide , Nicolas Pasquier , Rafik Taouil , Gerd Stumme , Lotfi Lakhal, Mining Minimal Non-redundant Association Rules Using Frequent Closed Itemsets, Proceedings of the First International Conference on Computational Logic, p.972-986, July 01, 2000
• 8: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, ACM SIGMOD Record, v.27 n.2, p.85-93, June 1998
• 9: Roberto J. Bayardo, Jr. , Rakesh Agrawal, Mining the most interesting rules, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.145-154, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312219]
• 10: Blake, C. and Merz, C. 1998. UCI repository of machine learning databases. Department of Information and Computer Science, University of California, Irvine, Irvine, CA. Available online at http://www.ics.uci.edu/~mlearn/mlrepository.html.
• 11: Jean-François Boulicaut , Artur Bykowski , Christophe Rigotti, Free-Sets: A Condensed Representation of Boolean Data for the Approximation of Frequency Queries, Data Mining and Knowledge Discovery, v.7 n.1, p.5-22, January 2003 [doi>10.1023/A:1021571501451]
• 12: Craig Silverstein , Sergey Brin , Rajeev Motwani, Beyond Market Baskets: Generalizing Association Rules to Dependence Rules, Data Mining and Knowledge Discovery, v.2 n.1, p.39-68, January 1998 [doi>10.1023/A:1009713703947]
• 13: Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, ACM SIGMOD Record, v.26 n.2, p.255-264, June 1997
• 14: Douglas Burdick , Manuel Calimlim , Johannes Gehrke, MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases, Proceedings of the 17th International Conference on Data Engineering, p.443-452, April 02-06, 2001
• 15: Artur Bykowski , Christophe Rigotti, A condensed representation to find frequent patterns, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.267-273, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375604]
• 16: Toon Calders , Bart Goethals, Mining All Non-derivable Frequent Itemsets, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.74-85, August 19-23, 2002
• 17: Cremilleux, B. and Boulicaut, J.-F. 2002. Simplest rules characterizing classes generated by delta-free sets. In Proceedings of the Twenty-Second Annual International Conference Knowledge Based Systems and Applied Artificial Intelligence (ES'02). Springer, New York, NY, 33--46.
• 18: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 19: Guozhu Dong , Xiuzhen Zhang , Limsoon Wong , Jinyan Li, CAEP: Classification by Aggregating Emerging Patterns, Proceedings of the Second International Conference on Discovery Science, p.30-42, December 01, 1999
• 20: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 21: Fayyad, U. and Irani, K. 1993. Multi-interval discretization of continuous-valued attributes for classification learning. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI'93). Morgan Kaufmann, San Francisco, CA, 1022--1029.
• 22: Takeshi Fukuda , Yasukiko Morimoto , Shinichi Morishita , Takeshi Tokuyama, Data mining using two-dimensional optimized association rules: scheme, algorithms, and visualization, ACM SIGMOD Record, v.25 n.2, p.13-23, June 1996
• 23: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, ACM SIGMOD Record, v.29 n.2, p.1-12, June 2000
• 24: Hettich, S. and Bay, S. D. 1999. UCI KDD archive. Department of Information and Computer Science, University of California, Irvine, Irvine, CA. Available online at http://kdd.ics.uci.edu.
• 25: KDDCUP2002. 2002. KDDCup 2002---Task 2. Available online at http://www.biostat.wisc. edu/~craven/kddcup/.
• 26: Marzena Kryszkiewicz, Concise Representation of Frequent Patterns Based on Disjunction-Free Generators, Proceedings of the 2001 IEEE International Conference on Data Mining, p.305-312, November 29-December 02, 2001
• 27: Marzena Kryszkiewicz , Marcin Gajek, Concise Representation of Frequent Patterns Based on Generalized Disjunction-Free Generators, Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, p.159-171, May 06-08, 2002
• 28: Wenmin Li , Jiawei Han , Jian Pei, CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules, Proceedings of the 2001 IEEE International Conference on Data Mining, p.369-376, November 29-December 02, 2001
• 29: Tjen-Sien Lim , Wei-Yin Loh , Yu-Shan Shih, A Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-Three Old and New Classification Algorithms, Machine Learning, v.40 n.3, p.203-228, Sept. 2000 [doi>10.1023/A:1007608224229]
• 30: Liu, B., Hsu, W., and Ma, Y. 1998. Integrating classification and association rule mining. In Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining (KDD'98). AAAI Press, Menlo Park, CA, 80--86.
• 31: Bing Liu , Wynne Hsu , Yiming Ma, Pruning and summarizing the discovered associations, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.125-134, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312216]
• 32: Mannila, H. and Toivonen, H. 1996. Multiple uses of frequent sets and condensed representations. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD'96). AAAI Press, Menlo Park, CA, 189--194.
• 33: Rosa Meo, Theory of dependence values, ACM Transactions on Database Systems (TODS), v.25 n.3, p.380-406, Sept. 2000 [doi>10.1145/363951.363956]
• 34: Michalski, R. 1980. Pattern recognition as rule-guided induction inference. IEEE Trans. Patt. Anal. Mach. Learn. 2, 349--361.
• 35: Mills, F. 1995. Statistical methods. Pitman, London, U.K.
• 36: Pasquier, N., Bastide, Y., Taouil, R., and Lakhal, L. 1999a. Closed itemsets discovery of small covers for association rules. In Proceedings of 15mes Journes Bases des Donnes Avances (BDA'99). 361--381.
• 37: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceeding of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
• 38: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Efficient mining of association rules using closed itemset lattices, Information Systems, v.24 n.1, p.25-46, March 1999 [doi>10.1016/S0306-4379(99)00003-4]
• 39: Jian Pei , Runying Mao , Kan Hu , Hua Zhu, Towards data mining benchmarking: a test bed for performance study of frequent pattern mining, ACM SIGMOD Record, v.29 n.2, p.592, June 2000
• 40: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 41: D. E. Rumelhart , G. E. Hinton , R. J. Williams, Learning internal representations by error propagation, Parallel distributed processing: explorations in the microstructure of cognition, vol. 1: foundations, MIT Press, Cambridge, MA, 1986
• 42: Gerd Stumme , Rafik Taouil , Yves Bastide , Nicolas Pasquier , Lotfi Lakhal, Intelligent Structuring and Reducing of Association Rules with Formal Concept Analysis, Proceedings of the Joint German/Austrian Conference on AI: Advances in Artificial Intelligence, p.335-350, September 19-21, 2001
• 43: Pang-Ning Tan , Vipin Kumar , Jaideep Srivastava, Selecting the right interestingness measure for association patterns, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775053]
• 44: Toivonen, H., Klemettinen, M., Ronkainen, P., Hatonen, K., and Manilla, H. 1995. Pruning and grouping discovered association rules. In Workshop on Statistics, Machine Learning, and Knowledge Discovery in Databases (ECML'95). 47--52.
• 45: Jianyong Wang , Jiawei Han , Jian Pei, CLOSET+: searching for the best strategies for mining frequent closed itemsets, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956779]
• 46: Ke Wang , Senqiang Zhou , Yu He, Growing decision trees on support-less association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.265-269, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347147]
• 47: Yin, X. and Han, J. 2003. CPAR: Classification based on predictive association rules. In Proceedings of the 3rd SIAM International Conference on Data Mining (SDM'03). SIAM, Philadelphia, PA.
• 48: Mohammed J. Zaki, Generating non-redundant association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.34-43, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347101]
• 49: Zaki, M. and Hsiao, C.-J. 1999. CHARM: An efficient algorithm for closed itemset mining. In Tech. rep. 99-10. Rensselaer Polytechnic Institute,
• 50: Zaki, M. and Hsiao, C.-J. 2002. CHARM: An efficient algorithm for closed itemset mining. In Proceedings of the Second SIAM International Conference on Data Mining (SIAM'02). SIAM, Philadelphia, PA.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Association rules, associative classification, concise representations