›› 2014, Vol. 29 ›› Issue (3): 392-407.doi: 10.1007/s11390-014-1438-5

Special Issue: Artificial Intelligence and Pattern Recognition; Data Management and Data Mining

• Data Management and Data Mining • Previous Articles     Next Articles

ConfDTree:Statistical Methods for Improving Decision Trees

Gilad Katz, Asaf Shabtai, Lior Rokach, and Nir Ofek   

  1. Department of Information Systems Engineering, Ben-Gurion University of the Negev, Beer Sheva 8410501, Israel Telekom Innovation Laboratories, Ben-Gurion University of the Negev, Beer Sheva 8410501, Israel
  • Received:2013-09-08 Revised:2014-01-27 Online:2014-05-05 Published:2014-05-05
  • About author:Gilad Katz is a Ph.D. student at the Department of Information Systems Engineering at Ben-Gurion University of the Negev. He received both his B.Sc. and M.Sc. degrees from this department. His main areas of interest include text mining, machine learning and big data. For the past four years, Gilad has also worked as a researcher at Deutsche Telekom Labs at Ben-Gurion University.

Decision trees have three main disadvantages: reduced performance when the training set is small; rigid decision criteria; and the fact that a single "uncharacteristic" attribute might "derail" the classification process. In this paper we present ConfDTree (Confidence-Based Decision Tree)——a post-processing method that enables decision trees to better classify outlier instances. This method, which can be applied to any decision tree algorithm, uses easy-to-implement statistical methods (confidence intervals and two-proportion tests) in order to identify hard-to-classify instances and to propose alternative routes. The experimental study indicates that the proposed post-processing method consistently and significantly improves the predictive performance of decision trees, particularly for small, imbalanced or multi-class datasets in which an average improvement of 5%~9% in the AUC performance is reported.

[1] Rokach L, Maimon O. Data Mining with Decision Trees: Theory and Applications. World Scientific Publishing, 2008.

[2] Quinlan J R. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.

[3] Chawla N V, Japkowicz N, Kotcz A. Editorial: Special issue on learning from imbalanced data sets. SIGKDD Explor. Newsl., 2004, 6(1): 1-6.

[4] Provost F, Domingos P. Well-trained PETs: Improving probability estimation trees. Technical Report, CDER #00-04IS, Stern School of Business, New York University, 2001. http://pages.stern.nyu.edu/籪provost/Papers/pet-wp.pdf, Mar. 2014.

[5] Lin H Y. Effcient classifiers for multi-class classification problems. Decision Support Systems, 2012, 53(3): 473-481.

[6] Breiman L. Random forests. Machine Learning, 2001, 45(1): 5-32.

[7] Van Assche A, Blockeel H. Seeing the forest through the trees: Learning a comprehensible model from an ensemble. In Proc. the 18th European Conf. Machine Learning, Sept. 2007, pp.418-429.

[8] Katz G, Shabtai A, Rokach L, Ofek N. ConfDTree: Improving decision trees using confidence intervals. In Proc. the 12th Int. Conf. Data Mining (ICDM), Dec. 2012, pp.339-348.

[9] Quinlan J R. Induction of decision trees. Machine Learning, 1986, 1(1): 81-106.

[10] Quinlan J R. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.

[11] Breiman L, Friedman J, Stone C J, Olshen R A. Classification and Regression Trees. Chapman and Hall/CRC, 1984.

[12] Breiman L. Technical note: Some properties of splitting criteria. Machine Learning, 1996, 24(1): 41-47.

[13] Cieslak D A, Chawla N V. Learning decision trees for unbalanced data. In Proc. 2008 ECML PKDD, Sept. 2008, pp.241-256.

[14] Buntine W, Niblett T. A further comparison of splitting rules for decision-tree induction. Machine Learning, 1992, 8(1): 75-85.

[15] Rodr砱uez J J, Kuncheva L I, Alonso C J. Rotation forest: A new classifier ensemble method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(10): 16191630.

[16] Gehrke J, Ganti V, Ramakrishnan R, Loh W Y. BOAToptimistic decision tree construction. In Proc. SIGMOD, May 31-June 03, 1999, pp.169-180.

[17] John G H. Robust decision trees: Removing outliers from databases. In Proc. the 1st Int. Conf. Knowledge Discovery and Data Mining, Aug. 1995, pp.174-179.

[18] Last M, Maimon O, Minkov E. Improving stability of decision trees. International Journal of Pattern Recognition and Artificial Intelligence, 2002, 16(2): 145-159.

[19] Zadrozny B, Elkan C. Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers. In Proc. the 8th International Conference on Machine Learning, June 28-July 1, 2001, pp.609-616.

[20] Ling C X, Robert J Y. Decision tree with better ranking. In Proc. the 20th International Conference on Machine Learning, Aug. 2003, pp.480-487.

[21] Mccallum R A. Instance-based utile distinctions for reinforcement learning with hidden state. In Proc. the 12th Int. Conf. Machine Learning, July 1995, pp.387-395.

[22] Massey F J. The Kolmogorov-Smirnov test for goodness of fit. Journal of the American Statistical Association, 1951, 46(253): 68-78.

[23] Rzepakowski P, Jaroszewicz S. Decision trees for uplift modeling with single and multiple treatments. Knowledge and Information Systems, 2012, 32(2): 303-327.

[24] Bhattacharyya S. Confidence in predictions from random tree ensembles. Knowledge and Information Systems, 2013, 35(2): 391-410.

[25] Janikow C Z. Fuzzy decision trees: Issues and methods. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1998, 28(1): 1-14.

[26] Olaru C, Wehenkel L. A complete fuzzy decision tree technique. Fuzzy Sets and Systems, 2003, 138(2): 221-254.

[27] Zadorny B, Elkan C. Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers. In Proc. the 18th International Conference on Machine Learning, June 28-July 1, 2001, pp.609-616.

[28] Esposito F D, Malerba D, Semeraro G. A comparative analysis of methods for pruning decision trees. IEEE Trans. Pattern Analysis and Machine Intelligence, 1997, 19(5): 476-491.

[29] Chawla N V, Bowyer K W, Hall L O, Kegelmeyer W P. SMOTE: Synthetic minority over-sampling technique. Journal of Artificial Intelligence Research, 2002, 16(1): 321-357.

[30] Stanfill C, Waltz D. Toward memory-based reasoning. Communications of the ACM, 1986, 29(12): 1213-1228.

[31] Kohavi R, Becker B, Sommerfield D. Improving simple Bayes. In Proc. the 9th European Conf. Machine Learning, April 1997, pp.78-87.

[32] Ponte J M, Croft W B. A language modeling approach to information retrieval. In Proc. the 21st Annual Int. ACM SIGIR Conf. Research and Development in Information Retrieval, Aug. 1998, pp.275-281.

[33] Lafferty J, Zhai C. Document language models, query models, and risk minimization for information retrieval. In Proc. the 24th Annual Int. ACM SIGIR Conf. Research and Development in Information Retrieval, Sept. 2001, pp.111-119.

[34] Demšar J. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 2006, 7: 1-30.

[35] Hand D J, Till R J. A simple generalisation of the area under the ROC curve for multiple class classification problems. Machine Learning, 2001, 45(2): 171-186.

[36] Hall M, Frank E, Holmes G, Pfahringernd B, Reutemann P, Witten I H. The WEKA data mining software: An update. ACM SIGKDD Explorations Newsletter, 2009, 11(1): 10-18.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved