CCCS: a top-down associative classifier for imbalanced class distribution

ABSTRACT

In this paper we propose CCCS, a new algorithm for classification based on association rule mining. The key innovation in CCCS is the use of a new measure, the "Complement Class Support (CCS)" whose application results in rules which are guaranteed to be positively correlated. Furthermore, the anti-monotonic property that CCS possesses has very different semantics vis-a-vis the traditional support measure. In particular, "good" rules have a low CCS value. This makes CCS an ideal measure to use in conjunction with a top-down algorithm. Finally, the nature of CCS allows the pruning of rules without the setting of any threshold parameter! To the best of our knowledge this is the first threshold-free algorithm in association rule mining for classification.

REFERENCES

• 1: 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
• 2: Maria-Luiza Antonie , Osmar R. Zaïane, An associative classifier based on positive and negative rules, Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13, 2004, Paris, France [doi>10.1145/1008694.1008705]
• 3: B. Arunasalam and S. Chawla. Cccs: A top-down associative classifier for imbalanced class distribution. Technical Report TR 584, University of Sydney, 2006.
• 4: C. Blake and C. Merz. UCI KDD Archive. http://kdd.ics.uci.edu/, 2000.
• 5: Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States
• 6: Gao Cong , Anthony K. H. Tung , Xin Xu , Feng Pan , Jiong Yang, FARMER: finding interesting rule groups in microarray datasets, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007587]
• 7: Gao Cong , Kian-Lee Tan , Anthony K. H. Tung , Feng Pan, Mining Frequent Closed Patterns in Microarray Data, Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04), p.363-366, November 01-04, 2004
• 8: Gao Cong , Kian-Lee Tan , Anthony K. H. Tung , Xin Xu, Mining top-K covering rule groups for gene expression data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066234]
• 9: M. Inc. Matlab Statistical Toolbox. Mathworks, 2005.
• 10: 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
• 11: C. X. Ling and C. Li. Data mining for direct marketing: problems and solutions. In International Conference on Knowledge Discovery and Data Mining(KDD'98) Proceedings, pages 73--79, 1998.
• 12: B. Liu, W. Hsu, and Y. Ma. Data Mining II. http://www.comp.nus.edu.sg/ dm2/index.html, 1998.
• 13: B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. In International Conference on Knowledge Discovery and Data Mining(KDD'98) Proceedings, pages 80--86, 1998.
• 14: Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 15: J. Wang and G. Karypis. Harmony: Efficiently mining the best rules for classification. In 2005 SIAM International Conference on Data Mining (SDM'05) Proceedings, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Experimentation

Keywords:
association rules mining, classification, imbalanced data sets, parameter-free mining