Decision tree learning

Tree models where the target variable can take a discrete set of values are called classification trees; in these tree structures, leaves represent class labels and branches represent conjunctions of features that lead to those class labels. Decision trees where the target variable can take continuous values (typically real numbers) are called regression trees. More generally, the concept of regression tree can be extended to any kind of object equipped with pairwise dissimilarities such as categorical sequences.^[1]


Decision trees are among the most popular machine learning algorithms given their intelligibility and simplicity.^[2]


In decision analysis, a decision tree can be used to visually and explicitly represent decisions and decision making. In data mining, a decision tree describes data (but the resulting classification tree can be an input for decision making).

Decision trees used in data mining are of two main types:


The term classification and regression tree (CART) analysis is an umbrella term used to refer to either of the above procedures, first introduced by Breiman et al. in 1984.^[7] Trees used for regression and trees used for classification have some similarities – but also some differences, such as the procedure used to determine where to split.^[7]


Some techniques, often called ensemble methods, construct more than one decision tree:


A special case of a decision tree is a decision list,^[14] which is a one-sided decision tree, so that every internal node has exactly 1 leaf node and exactly 1 internal node as a child (except for the bottommost node, whose only child is a single leaf node). While less expressive, decision lists are arguably easier to understand than general decision trees due to their added sparsity, permit non-greedy learning methods^[15] and monotonic constraints to be imposed.^[16]


Notable decision tree algorithms include:


ID3 and CART were invented independently at around the same time (between 1970 and 1980), yet follow a similar approach for learning a decision tree from training tuples.


It has also been proposed to leverage concepts of fuzzy set theory for the definition of a special version of decision tree, known as Fuzzy Decision Tree (FDT).^[23] In this type of fuzzy classification, generally, an input vector ${\displaystyle {\textbf {x}}}$ is associated with multiple classes, each with a different confidence value. Boosted ensembles of FDTs have been recently investigated as well, and they have shown performances comparable to those of other very efficient fuzzy classifiers.^[24]