A Kolmogorov-Smirnoff Metric for Decision Tree Induction
Paul E. Utgoff, J. A. Clouse · 1996
In 1977, Friedman demonstrated that Kolmogorov-Smirnoff distance could be employed effectively as a test selection metric for decision tree induction. We revisit this metric and modify it to handle multiple classes within a single tree, and to be sensitive to missing data values. Empirical results for a large sample of learning tasks, comparing this metric to the gain ratio metric, show a highly significant reduction in tree size and expected number of tests for classification, without a significant change in classification accuracy. 1 Introduction Top-down induction of decision trees is driven by greedy selection of a partition of the training instances that maximizes a heuristic function of that partition. The heuristic function is often called the test selection metric, but it is also known as the splitting criterion, the attribute selection metric, and the partition merit function. A good test selection metric should have a higher value for a better partition, but whether one pa...