Decision tree induction for classification selects, at each node, the attribute (and, for binary trees, the split point) that minimizes an impurity measure computed over the resulting child regions, with cross entropy and the Gini index as the two standard measures. The cross entropy at a node is the sum over class labels of −p log p using the empirical class proportions as an unbiased estimator of the unknown true conditional distribution, and the score for a candidate split is the average of the child entropies weighted by the fraction of training points falling into each branch; the attribute yielding the lowest weighted impurity is selected, since impurity is what the split is meant to eliminate. The procedure is recursive — each branch restricts the data to the instances matching that branch's attribute value and repeats over the remaining attributes — and differs between multiway splits, where an attribute with q values produces q branches and no split point need be chosen, and binary splits, where every candidate partition of the attribute's values must additionally be evaluated.
Decision tree induction for classification selects, at each node, the attribute (and, for binary trees, the split point) that minimizes an impurity measure computed over the resulting child regions, …