Construct robust rule sets for classification

ABSTRACT

We study the problem of computing classification rule sets from relational databases so that accurate predictions can be made on test data with missing attribute values. Traditional classifiers perform badly when test data are not as complete as the training data because they tailor a training database too much. We introduce the concept of one rule set being more robust than another, that is, able to make more accurate predictions on test data with missing attribute values. We show that the optimal class association rule set is as robust as the complete class association rule set. We then introduce the k-optimal rule set, which provides predictions exactly the same as the optimal class association rule set on test data with up to k missing attribute values. This leads to a hierarchy of k-optimal rule sets in which decreasing size corresponds to decreasing robustness, and they all more robust than a traditional classification rule set. We introduce two methods to find k-optimal rule sets, i.e. an optimal association rule mining approach and a heuristic approximate approach. We show experimentally that a k-optimal rule set generated by the optimal association rule mining approach performs better than that by the heuristic approximate approach and both rule sets perform significantly better than a typical classification rule set (C4.5Rules) on incomplete test data.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: 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
• 3: Edward A. Bender, Mathematical methods in artificial intelligence, IEEE Computer Society Press, Los Alamitos, CA, 1996
• 4: E. K. C. Blake and C. J. Merz. UCI repository of machine learning databases, http://www.ics.uci.edu/~mlearn/MLRepository.html, 1998.
• 5: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 6: Peter Clark , Robin Boswell, Rule induction with CN2: some recent improvements, Proceedings of the European working session on learning on Machine learning, p.151-163, March 1991, Porto, Portugal
• 7: 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
• 8: Y. Freund and R. E. Schapire. Experiments with a new boosting algorithm. In International Conference on Machine Learning, pages 148--156, 1996.
• 9: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 10: Jiuyong Li , Hong Shen , Rodney W. Topor, Mining Optimal Class Association Rule Set, Proceedings of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining, p.364-375, April 16-18, 2001
• 11: 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
• 12: B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. In Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD-98), pages 27--31, 1998.
• 13: Bing Liu , Wynne Hsu , Yiming Ma, Mining association rules with multiple minimum supports, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.337-341, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312274]
• 14: Dimitris Meretakis , Beat Wüthrich, Extending naïve Bayes classifiers using long itemsets, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.165-174, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312222]
• 15: R. Michalski, I. Mozetic, J. Hong, and N. Lavrac. The AQ15 inductive learning system: an overview and experiments. In Proceedings of IMAL 1986, Orsay, 1986. Université de Paxis-Sud.
• 16: John Mingers, An Empirical Comparison of Selection Measures for Decision-Tree Induction, Machine Learning, v.3 n.4, p.319-342, March 1989 [doi>10.1023/A:1022645801436]
• 17: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 18: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Deduction (e.g., natural, rule-based)
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Relation systems

General Terms:
Algorithms, Measurement, Performance

Keywords:
association rule, classification rule, data mining