Global Evaluation for Decision Tree Learning

We transfer distances on clusterings to the building process of decision trees, and as a consequence extend the classical ID3 algorithm to perform modifications based on the global distance of the tree to the ground truth--instead of considering single leaves. Next, we evaluate this idea in comparison with the original version and discuss occurring problems, but also strengths of the global approach. On this basis, we finish by identifying other scenarios where global evaluations are worthwhile. The classification problem in machine learning asks, given some observed instances with known outcomes (called the labeled training data), to make predictions on outcomes of unseen instances. Formally, let Ω be a universe of instances. R. Outcomes of instances in the training set X Ω, also called class labels, are given by a map y: Ω {1,..., k}. One popular choice of a model to train is the decision tree.