Decision tree induction ordinarily assumes continuous attributes so that a split can be expressed as a threshold, but categorical (discrete, unordered) attributes admit no natural split point and instead require partitioning the attribute's value set into two subsets, of which there are exponentially many (on the order of 2^(q−1) − 1 for q values) — computationally infeasible to enumerate. For binary classification this exhaustive search can be avoided: computing, for each attribute value, the fraction of training instances with that value belonging to the positive class, and sorting the values by that fraction, reduces the candidate splits to the q−1 prefix/suffix cuts of the sorted ordering. This ordering heuristic is provably optimal for two-class problems — it yields the same best split as exhaustive subset search under standard impurity criteria such as Gini index, information gain, or misclassification error — and situates the treatment of categorical attributes within the broader theory of splitting-criterion selection in decision tree learning.
Decision tree induction ordinarily assumes continuous attributes so that a split can be expressed as a threshold, but categorical (discrete, unordered) attributes admit no natural split point and ins…