We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Gilad Katz, Asaf Shabtai, Lior Rokach, Nir Ofek. ConfDTree:Statistical Methods for Improving Decision Trees[J]. Journal of Computer Science and Technology, 2014, 29(3): 392-407. DOI: 10.1007/s11390-014-1438-5
Citation: Gilad Katz, Asaf Shabtai, Lior Rokach, Nir Ofek. ConfDTree:Statistical Methods for Improving Decision Trees[J]. Journal of Computer Science and Technology, 2014, 29(3): 392-407. DOI: 10.1007/s11390-014-1438-5

ConfDTree:Statistical Methods for Improving Decision Trees

More Information
  • Author Bio:

    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.

  • Received Date: September 07, 2013
  • Revised Date: January 26, 2014
  • Published Date: May 04, 2014
  • 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.
  • Related Articles

    [1]Ling-Xing Kong, You-Gang Chu, Zheng Ma, Jian-Bing Zhang, Jia-Jun Chen. Mix-Lingual Relation Extraction: Dataset and a Training Approach[J]. Journal of Computer Science and Technology, 2025, 40(1): 42-59. DOI: 10.1007/s11390-024-4314-y
    [2]Fei Du, Xin-Jian Ma, Jing-Ru Yang, Yi Liu, Chao-Ran Luo, Xue-Bin Wang, Hai-Ou Jiang, Xiang Jing. A Survey of LLM Datasets: From Autoregressive Model to AI Chatbot[J]. Journal of Computer Science and Technology, 2024, 39(3): 542-566. DOI: 10.1007/s11390-024-3767-3
    [3]Tai-Ling Yuan, Zhe Zhu, Kun Xu, Cheng-Jun Li, Tai-Jiang Mu, Shi-Min Hu. A Large Chinese Text Dataset in the Wild[J]. Journal of Computer Science and Technology, 2019, 34(3): 509-521. DOI: 10.1007/s11390-019-1923-y
    [4]Xin-Li Yang, David Lo, Xin Xia, Qiao Huang, Jian-Ling Sun. High-Impact Bug Report Identification with Imbalanced Learning Strategies[J]. Journal of Computer Science and Technology, 2017, 32(1): 181-198. DOI: 10.1007/s11390-017-1713-3
    [5]Yong-Nan Liu, Jian-Zhong Li, Zhao-Nian Zou. Determining the Real Data Completeness of a Relational Dataset[J]. Journal of Computer Science and Technology, 2016, 31(4): 720-740. DOI: 10.1007/s11390-016-1659-x
    [6]Xi-Te Wang, De-Rong Shen, Mei Bai, Tie-Zheng Nie, Yue Kou, Ge Yu. An Efficient Algorithm for Distributed Outlier Detection in Large Multi-Dimensional Datasets[J]. Journal of Computer Science and Technology, 2015, 30(6): 1233-1248. DOI: 10.1007/s11390-015-1596-0
    [7]Xue-Gang Hu, Pei-Pei Li, Xin-Dong Wu, Gong-Qing Wu. A semi-random multiple decision-tree algorithm for mining data streams[J]. Journal of Computer Science and Technology, 2007, 22(5): 711-724.
    [8]GAO Suixiang, LIN Guohui. Decision Tree Complexity of Graph Properties with Dimension at Most5[J]. Journal of Computer Science and Technology, 2000, 15(5): 416-422.
    [9]GAO Suixiang, LIN Guohui. Decision Tree Complexity of Graph Properties with Dimension at Most 5[J]. Journal of Computer Science and Technology, 2000, 15(5).
    [10]SHI Weisong, TANG Zhimin, SHI Jinsong. Using Confidence interval to Summarize the Evaluating Results of DSM Systems[J]. Journal of Computer Science and Technology, 2000, 15(1): 73-83.

Catalog

    Article views (979) PDF downloads (2485) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return