Skip to main content

Advertisement

SpringerLink
Log in

Decision trees: a recent overview

  • Published:
Artificial Intelligence Review Aims and scope Submit manuscript

Abstract

Decision tree techniques have been widely used to build classification models as such models closely resemble human reasoning and are easy to understand. This paper describes basic decision tree issues and current research points. Of course, a single article cannot be a complete review of all algorithms (also known induction classification trees), yet we hope that the references cited will cover the major theoretical issues, guiding the researcher in interesting research directions and suggesting possible bias combinations that have yet to be explored.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aitkenhead MJ (2008) A co-evolving decision tree classification method. Exp Syst Appl 34: 18–25

    Article  Google Scholar 

  • Altınçay H (2007) Decision trees using model ensemble-based nodes. Pattern Recogn 40: 3540–3551

    Article  MATH  Google Scholar 

  • Appavu Alias Balamurugan Subramanian, Pramala S, Rajalakshmi B, Rajaram R (2010) Improving decision tree performance by exception handling. Int J Automat Comput 7(3):372–380

    Google Scholar 

  • Banfield RE, Hall LO, Bowyer KW (2007) A comparison of decision tree ensemble creation techniques. IEEE Trans Pattern Anal Mach Intell 29: 173–180

    Article  Google Scholar 

  • Bar-Or, Wolff ASR, Keren D (2005) Decision tree induction in high dimensional, hierarchically distributed databases. In: Proceedings of 2005 SIAM international conference on data mining SDM’05, Newport Beach, CA

  • Blockeel H, Page D, Srinivasan A (2005) Multi-instance tree learning. In: Proceedings of the 22nd international conference on Machine learning, Bonn, Germany, pp 57–64

  • Breiman L (1996) Bagging predictors. Mach Learn 24: 123–140

    MathSciNet  MATH  Google Scholar 

  • Breiman L (2001) Random forests. Mach Learn 45(1): 5–32

    Article  MATH  Google Scholar 

  • Breiman L, Friedman JH, Olshen RA, Sotne CJ (1984) Classification and regression trees. Wadsworth, Belmont

    MATH  Google Scholar 

  • Caragea D, Silvescu A, Honavar V (2004) A framework for learning from distributed data using sufficient statistics and its application to learning decision trees. Int J Hybrid Intell Syst 1(2): 80–89

    MATH  Google Scholar 

  • Carvalho DR, Freitas AA (2004) A hybrid decision tree/genetic algorithm method for data mining. Inf Sci 163: 13–35

    Article  Google Scholar 

  • Chandra B, Varghese PP (2009a) Fuzzifying Gini index based decision trees. Exp Syst Appl 36: 8549–8559

    Article  Google Scholar 

  • Chandra B, Varghese PP (2009b) Moving towards efficient decision tree construction. Inf Sci 179: 1059–1069

    Article  MATH  Google Scholar 

  • Chandra B, Kothari R, Paul P (2010) A new node splitting measure for decision tree construction. Pattern Recogn 43: 2725–2731

    Article  MATH  Google Scholar 

  • Chang P-C, Fan C-Y, Dzan W-Y (2010) A CBR-based fuzzy decision tree approach for database classification. Exp Syst Appl 37: 214–225

    Article  Google Scholar 

  • Chen Y, Hsu C, Chou S (2003) Constructing a multi-valued and multi-labeled decision tree. Exp Syst Appl 25(2): 199–209

    Article  Google Scholar 

  • Chen RY, Sheu DD, Liu CM (2007) Vague knowledge search in the design for outsourcing using fuzzy decision tree. Comput Oper Res 34: 3628–3637

    Article  MATH  Google Scholar 

  • Chen Y-l, Wang T, Wang B-s, Li Z-j (2009a) A survey of fuzzy decision tree classifier. Fuzzy Inf Eng 2: 149–159

    Article  Google Scholar 

  • Chen Y-L, Wu C-C, Tang K (2009b) Building a cost-constrained decision tree with multiple condition attributes. Inf Sci 179: 967–979

    Article  Google Scholar 

  • Chengming Q (2007) A new partition criterion for fuzzy decision tree algorithm. In: Intelligent information technology application, workshop on 2–3 December 2007, pp 43–46

  • Chou S, Hsu C (2005) MMDT: a multi-valued and multi-labeled decision tree classifier for data mining. Exp Syst Appl 28(2): 799–812

    Article  Google Scholar 

  • Dietterich T (2000) An experimental comparison of three methods for constructing ensembles of decision trees: bagging, boosting, and randomization. Mach Learn 40: 139–157

    Article  Google Scholar 

  • Djukova EV, Peskov NV (2007) A classification algorithm based on the complete decision tree. Pattern Recogn Image Anal 17(3): 363–367

    Article  Google Scholar 

  • Esmeir S, Markovitch S (2010) Anytime learning of anycost classifiers. Mach Learn, doi:10.1007/s10994-010-5228-1

  • Esposito F, Malerba D, Semeraro G (1997) A comparative analysis of methods for pruning decision trees. EEE Trans Pattern Anal Mach Intell 19(5): 476–492

    Article  Google Scholar 

  • Ferri U, Flach PA, Hernandez-Orallo J (2003) Improving the AUC of probabilistic estimation trees. Lect Notes Artif Intell 2837: 121–132

    Google Scholar 

  • Fournier D, Crémilleux B (2002) A quality index for decision tree pruning. Knowl Based Syst 15(1-2): 37–43

    Article  Google Scholar 

  • Frank E, Hall M (2001) A simple approach to ordinal prediction. In: De Raedt L, Flach P (eds) ECML 2001, LNAI. Springer, Berlin, vol 2167, pp 145–156

  • Freitas A, Pereira A, Brazdil P (2007) Cost-sensitive decision trees applied to medical data. Lect Notes Comput Sci 4654: 303–312

    Article  Google Scholar 

  • Freund Y, Mason L (1999) The alternating decision tree learning algorithm. In: Proceedings of the sixteenth international conference on machine learning, Bled, Slovenia, pp 124–133

  • Freund Y, Schapire RE (1997) A decision-theoretic generalization of on-line learning and an application to boosting. J Comput Syst Sci 55(1): 119–139

    Article  MathSciNet  MATH  Google Scholar 

  • Fu L (2006) Construction of decision trees using data cube. In: Chen CS et al (eds) Enterprise information systems, vol VII, pp 87–94

  • Gama J (2004) Functional trees. Mach Learn 55(3): 219–250

    Article  MATH  Google Scholar 

  • Gama J, Rocha R, Medas P (2003) Accurate decision trees for mining high-speed data streams. In: Proceedings of 9th ACM SIGKDD international conference on knowledge discovery and data mining, pp 523–528

  • Gama J, Fernandes R, Rocha R (2006) Decision trees for mining data streams. Intell Data Anal 1: 23–45

    Google Scholar 

  • Gehrke J, Ramakrishnan R, Ganti V (2000) RainForest—a framework for fast decision tree construction of large datasets. Data Mining Knowl Discovery 4(2–3): 127–162

    Article  Google Scholar 

  • Gill Abdul A, Smith George D, Bagnall Anthony J (2004) Improving decision tree performance through induction- and cluster-based stratified sampling. LNCS 3177: 339–344

    Google Scholar 

  • Ho TK (1998) The random subspace method for constructing decision forests. IEEE Trans Pattern Anal Mach Intell 20(8): 832–844

    Article  Google Scholar 

  • Hulse J, Khoshgoftaar T (2009) Knowledge discovery from imbalanced and noisy data. Data Knowl Eng 68(12): 1513–1542

    Article  Google Scholar 

  • Hüllermeier E, Beringer J (2005) Learning from ambiguously labeled examples. Intell Data Anal 168–179

  • Hulten G, Spencer L, Domingos P (2001) Mining time-changing data streams. In: Proceedings of 7th ACM SIGKDD international conference on knowledge discovery and data mining, pp 97–106

  • Ittner, Schlosser M (1996) Discovery of relevant new features by generating non-linear decision trees. In: Proceedings of second international conference on knowledge discovery and data mining. AAAI Press, Menlo Park, pp 108–113

  • Jenhani I, Amor Nahla B, Elouedi Z (2008) Decision trees as possibilistic classifiers. Int J Approx Reason 48: 784–807

    Article  Google Scholar 

  • Jenhani I, Benferhat S, Elouedi Z (2009) On the Use of clustering in possibilistic decision tree induction. LNAI 5590: 505–517

    MathSciNet  Google Scholar 

  • Jin R, Agrawal G (2003) Communication and memory efficient parallel decision tree construction. In: Proceedings of third SIAM conference on data mining

  • Kotsiantis S, Kanellopoulos D (2010) Cascade generalization of ordinal problems. Int J Artif Intell Soft Comput (IJAISC) 2(1/2): 46–57

    Article  Google Scholar 

  • Kumar MA, Gopal M (2010) A hybrid SVM based decision tree. Pattern Recogn 43: 3977–3987

    Article  MATH  Google Scholar 

  • Landwehr N, Hall M, Frank E (2005) Logistic model trees. Mach Learn 59(1–2): 161–205

    Article  MATH  Google Scholar 

  • Lee JWT, Liu D-Z (2002) Induction of ordinal decision trees. In: International conference on machine learning and cybernetics, pp 2220–2224

  • Li X-B (2005) A scalable decision tree system and its application in pattern recognition and intrusion detection. Decis Support Syst 41: 112–130

    Article  MATH  Google Scholar 

  • Li RH, Belford GG (2002) Instability of decision tree classification algorithms. In: Proceedings of the 8th ACM SIGKDD international conference on knowledge discovery and data mining, Edmonton, pp 570–575

  • Li H, Zhao R, Chen J, Xiang Y (2006) Research on multi-valued and multi-labeled decision trees. LNAI 4093: 247–254

    Google Scholar 

  • Li C-G, Wang M, Sun Z-G, Wang X-R, Zhang Z-F (2009) Decision tree algorithm using attribute frequency splitting and information entropy discretization. Comput Eng Appl 45(12): 153–156

    Google Scholar 

  • Liang C, Zhang Y, Song Q (2010) Decision tree for dynamic and uncertain data streams. In: JMLR: workshop and conference proceedings, vol 13, pp 209–224, 2nd Asian conference on machine learning (ACML2010), Tokyo, Japan

  • LiMin W, SenMiao Y, Ling L, HaiJun L (2004) Improving the performance of decision tree: a hybrid approach. Lect Notes Comput Sci 3288: 327–335

    Article  Google Scholar 

  • Ling CX, Yang Q, Wang J, Zhang S (2004) Decision trees with minimal costs. In: Proceedings of the 21st international conference on machine learning (ICML-2004), Banff, pp 69–77

  • Liu J, Li X, Zhong W (2009) Ambiguous decision trees for mining concept-drifting data streams. Pattern Recogn Lett 30: 1347–1355

    Article  Google Scholar 

  • Lo S-H, Ou J-C, Chen M-S (2003) Inference based classifier: efficient construction of decision trees for sparse categorical attributes. LNCS 2737: 182–191

    Google Scholar 

  • Loh WY, Shih X (1999) Families of splitting criteria for classification trees. Stat Comput 9: 309–315

    Article  Google Scholar 

  • Mehta M, Agrawal R, Riassnen J (1996) SLIQ: a fast scalable classifier for data mining. Extending database technology. Springer, Avignon, pp 18–32

    Google Scholar 

  • Melville P, Mooney R (2005) Creating diversity in ensembles using artificial data. Inf Fus 6: 99–111

    Article  Google Scholar 

  • Muata K, Bryson O (2004) Evaluation of decision trees: a multi-criteria approach. Comput Oper Res 31: 1933–1945

    Article  MATH  Google Scholar 

  • Muata K, Bryson O (2007) Post-pruning in decision tree induction using multiple performance measures. Comput Oper Res 34: 3331–3345

    Article  MATH  Google Scholar 

  • Mugambi EM, Hunter A, Oatley G, Kennedy L (2004) Polynomial-fuzzy decision tree structures for classifying medical data. Knowl Based Syst 17: 81–87

    Article  Google Scholar 

  • Murthy SK (1998) Automatic construction of decision trees from data: a multi-disciplinary survey. Data Mining Knowl Discovery 2(4): 345–389

    Article  Google Scholar 

  • Niculescu-Mizil A, Caruana R (2005) Predicting good probabilities with supervised learning. Association for Computing Machinery Inc., New York

    Google Scholar 

  • Nijssen S, Fromont E (2007) Mining optimal decision trees from itemset lattices. In: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining (KDD-2007), San Jose, pp 530–539

  • Olaru C, Wehenkel L (2003) A complete fuzzy decision tree technique. Fuzzy Sets Syst 138(2): 221–254

    Article  MathSciNet  Google Scholar 

  • Ouyang J, Patel N, Sethi I (2009) Induction ofmulticlassmultifeature split decision trees fromdistributed data. Pattern Recogn 42: 1786–1794

    Article  MATH  Google Scholar 

  • Pfahringer B, Holmes G, Kirkby R (2001) Optimizing the induction of alternating decision trees. In: Proceedings of the fifth Pacific-Asia conference on advances in knowledge discovery and data mining, pp 477–487

  • Piramuthu S (2008) Input data for decision trees. Exp Syst Appl 34: 1220–1226

    Article  Google Scholar 

  • Poulet F (2002) Cooperation between automatic algorithms, interactive algorithms and visualization tools for visual data mining. In: Proceedings of VDM@ECML/PKDD 2002, international workshop on visual data mining, Helsinki, pp 67–80

  • Poulet F, Do TN (2008) Interactive decision tree construction for interval and taxonomical data. LNCS 4404: 123–135

    Google Scholar 

  • Provost F, Domingos P (2003) Tree induction for probability-based ranking. Mach Learn 52: 199–215

    Article  MATH  Google Scholar 

  • Provost F, Fawcett T (2001) Robust classification for imprecise environments. Mach Learn 42: 203–231

    Article  MATH  Google Scholar 

  • Qin Z, Lawry J (2005) Decision tree learning with fuzzy labels. Inf Sci 172: 91–129

    Article  MathSciNet  MATH  Google Scholar 

  • Quinlan JR (1993) C4.5: programs for machine learning. Morgan Kaufmann, San Francisco

    Google Scholar 

  • Rodríguez JJ, Kuncheva LI, Alonso CJ (2006) Rotation forest: a new classifier ensemble method. IEEE Trans Pattern Anal Mach Intell 28(10): 1619–1630

    Article  Google Scholar 

  • Ruggieri S (2002) Efficient C4.5 [classification algorithm]. IEEE Trans Knowl Data Eng 14(2): 438–444

    Article  Google Scholar 

  • Saffavian SR, Landgrebe D (1991) A survey of decision tree classifier methodology. IEEE Trans Syst Man Cybern 21(3): 660–674

    Article  Google Scholar 

  • Shafer J, Agrawal R, Mehta M (1996) SPRINT: a scalable parallel classifier for data mining. In Proceedings of the VLDB conference, Bombay

  • Sheng S, Ling CX, Yang Q (2005) Simple test strategies for cost-sensitive decision trees. In: Proceedings of the 9th European conference on machine learning (ECML-2005), Porto, pp 365–376

  • Shyi-Ming C, Fu-Ming T (2007) Generating fuzzy rules from training instances for fuzzy classification systems. Exp Syst Appl, doi:10.1016/j.eswa.2007.07.013

  • Sieling D (2008) Minimization of decision trees is hard to approximate. J Comput Syst Sci 74: 394–403

    Article  MathSciNet  MATH  Google Scholar 

  • Srivastava A, Han E-H, Kumar V, Singh V (1999) Parallel formulations of decision-tree classification algorithms. Data Mining Knowl Discovery 3: 237–261

    Article  Google Scholar 

  • Sug H (2005) A comprehensively sized decision tree generation method for interactive data mining of very large databases. LNAI 3584: 141–148

    Google Scholar 

  • Tjen-Sien L, Wei-Yin L, Yu-Shan S (2000) A comparison of prediction accuracy, complexity, and training time of thirty-three old and new classification algorithms. Mach Learn 40: 203–228

    Article  MATH  Google Scholar 

  • Twala BETH, Jones MC, Hand DJ (2008) Good methods for coping with missing data in decision trees. Pattern Recogn Lett 29: 950–956

    Article  Google Scholar 

  • Wang X, Chen B, Qian G, Ye F (2000) On the optimization of fuzzy decision trees. Fuzzy Sets Syst 112: 117–125

    Article  MathSciNet  Google Scholar 

  • Wang S, Wei J, You J, Liu D (2006) ComEnVprs: a novel approach for inducing decision tree classifiers. LNAI 4093: 126–134

    Google Scholar 

  • Wang X-Z, Zhai J-H, Lu S-X (2008) Induction of multiple fuzzy decision trees based on rough set technique. Inf Sci 178: 3188–3202

    Article  MathSciNet  MATH  Google Scholar 

  • Wang T, Qin Z, Jin Z, Zhang S (2010) Handling over-fitting in test cost-sensitive decision tree learning by feature selection, smoothing and pruning. J Syst Softw 83: 1137–1147

    Article  Google Scholar 

  • Ware M, Franck E, Holmes G, Hall M, Witten I (2001) Interactive machine learning: letting users build classifiers. Int J Hum Comput Stud 55: 281–292

    Article  MATH  Google Scholar 

  • Webb GI (2000) MultiBoosting: a technique for combining boosting and wagging. Mach Learn 40: 159–196

    Article  Google Scholar 

  • Wei J-M, Wang S-Q, Wang M-Y, You J-P, Liu D-Y (2007) Rough set based approach for inducing decision trees. Knowl Based Syst 20: 695–702

    Article  Google Scholar 

  • Yao Z, Liu P, Lei L, Yin J (2005) R_C4.5 decision tree model and its applications to health care dataset. In: Proceedings of international conference on services systems and services management—ICSSSM’05, vol 2, pp 13–15, IEEE, 2005, pp 1099–1103

  • Yıldız OT, Alpaydın E (2001) Omnivariate decision trees. IEEE Trans Neural Netw 12(6): 1539–1546

    Article  Google Scholar 

  • Yıldız OT, Alpaydın E (2005) Linear discriminant trees. Int J Pattern Recogn 19(3): 323–353

    Article  Google Scholar 

  • Yıldız OT, Dikmen O (2007) Parallel univariate decision trees. Pattern Recogn Lett 28: 825–832

    Article  Google Scholar 

  • Zadrozny B, Elkan C (2001) Learning and making decisions when costs and probabilities are both unknown. In: Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining. ACM Press, San Francisco, pp 204–213

  • Zhang D, Zhou X, Leung S, Zheng J (2010) Vertical bagging decision trees model for credit scoring. Exp Syst Appl 37: 7838–7843

    Article  Google Scholar 

  • Zhao H (2007) A multi-objective genetic programming approach to developing Pareto optimal decision trees. Decis Support Syst 43: 809–826

    Article  Google Scholar 

  • Zhou Z-H, Chen Z-Q (2002) Hybrid decision tree. Knowl Based Syst 15(8): 515–528

    Article  Google Scholar 

  • Zhou Z-H, Tang W (2003) Selective ensemble of decision trees. In: Lecture notes in artificial intelligence. Springer, Berlin, vol 2639, pp 476–483

  • Zhou Y, Zhang T, Chen Z (2006) Applying Bayesian approach to decision tree. LNAI 4114: 290–295

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Educational Software Development Laboratory, Department of Mathematics, University of Patras, P.A. Box: 1399, Rio, 26 500, Patras, Greece

    S. B. Kotsiantis

Authors
  1. S. B. Kotsiantis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. B. Kotsiantis.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kotsiantis, S.B. Decision trees: a recent overview. Artif Intell Rev 39, 261–283 (2013). https://doi.org/10.1007/s10462-011-9272-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10462-011-9272-4

Keywords

Search

Navigation