Decision Trees

Vladimir Shikhman () and David Müller ()
Additional contact information
Vladimir Shikhman: Chemnitz University of Technology
David Müller: Chemnitz University of Technology

Chapter 9 in Mathematical Foundations of Big Data Analytics, 2021, pp 171-191 from Springer

Abstract: Abstract Decision tree learning is one of the predictive modelling approaches widely used in the fields of data mining and machine learning. It uses a decision tree to go through testing an object in the nodes to conclusions about its target variable’s value in the leaves. Decision trees are among the most popular machine learning algorithms given their intelligibility and simplicity. The applications range from the prediction of Titanic survival to the artificial intelligence chess playing. In this chapter, we focus on the classification decision trees, so that their leaves represent class labels. The quality of such decision trees is measured by means of both the misclassification rate on the given data, and the average external path length. Especially for identification decision trees with zero misclassification rate, we show that finding those with the minimal average external path length is an NP-complete problem. Due to this negative theoretical result, top-down and bottom-up heuristics are proposed to nevertheless construct decision trees whose quality is sufficient at least from the practical point of view. Based on various generalization errors, such as train error, entropy, and Gini index, we present the iterative dichotomizer algorithm for this purpose. The iterative dichotomizer splits at each step the data set by maximizing the gain derived from the chosen generalization error. Afterwards, we briefly elaborate on the pruning of decision trees.

Date: 2021
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-662-62521-7_9

Ordering information: This item can be ordered from
http://www.springer.com/9783662625217

DOI: 10.1007/978-3-662-62521-7_9

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().