A robust decision tree algorithm for imbalanced data sets

Wei Liu, Sanjay Chawla, David A. Cieslak, Nitesh V. Chawla

Research output: Contribution to conferencePaperpeer-review

107 Scopus citations

Abstract

We propose a new decision tree algorithm, Class Confidence Proportion Decision Tree (CCPDT), which is robust and insensitive to size of classes and generates rules which are statistically significant. In order to make decision trees robust, we begin by expressing Information Gain, the metric used in C4.5, in terms of confidence of a rule. This allows us to immediately explain why Information Gain, like confidence, results in rules which are biased towards the majority class. To overcome this bias, we introduce a new measure, Class Confidence Proportion (CCP), which forms the basis of CCPDT. To generate rules which are statistically significant we design a novel and efficient top-down and bottom-up approach which uses Fisher's exact test to prune branches of the tree which are not statistically significant. Together these two changes yield a classifier that performs statistically better than not only traditional decision trees but also trees learned from data that has been balanced by well known sampling techniques. Our claims are confirmed through extensive experiments and comparisons against C4.5, CART, HDDT and SPARCCC.

Original languageEnglish
Pages766-777
Number of pages12
DOIs
StatePublished - 2010
Externally publishedYes
Event10th SIAM International Conference on Data Mining, SDM 2010 - Columbus, OH, United States
Duration: Apr 29 2010May 1 2010

Conference

Conference10th SIAM International Conference on Data Mining, SDM 2010
Country/TerritoryUnited States
CityColumbus, OH
Period04/29/1005/1/10

Fingerprint

Dive into the research topics of 'A robust decision tree algorithm for imbalanced data sets'. Together they form a unique fingerprint.

Cite this