9. Decision Trees

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.