# Optimized procedure to find best binary split for categorical attributes in decision trees

I'm working on a HW implementation of DT and need a way to optimize the splitting procedure.

Will decision trees perform splitting of nodes by converting categorical values to numerical in practice?

The second thing is that in case of binary classification for Gini impurity there are proofs that shows that the best split from all 2^(L−1) is found much faster you you use the following procedure. Compute purity function for each level subset. Sort variables by the value of impurity function computed on each subset. Than, compute binary splits of subsets where on one side you have first k variables sorted previously, and in the other group the remaining values. This procedure is computed in linear time so, is much efficient and can actually handle variables with more than 32 levels. For details on that see Elements of Statistical Learning, 2ed - page 310, section 9.2.4 Other Issues. You will find there an explanation and following references.

I took a look at the mentioned book, here is the important portion:

When splitting a predictor having q possible unordered values, there are 2^(q−1) − 1 possible partitions of the q values into two groups, and the computations become prohibitive for large q. However, with a 0 − 1 outcome, this computation simplifies. We order the predictor classes according to the proportion falling in outcome class 1. Then we split this predictor as if it were an ordered predictor. One can show this gives the optimal split, in terms of cross-entropy or Gini index, among all possible 2^(q−1)−1 splits....The proof for binary outcomes is given in Breiman et al. (1984) and Ripley (1996)

But I still don't understand exactly how the procedure works. If someone could explain it to me in detail that would be great. Or if someone can share with me the portion of the Breiman or Ripley books where the procedure is explained and proved, that would be great too.

Thanks a lot,

Walter

Let's explain by example. We'll deal with a single predictor and a binary target variable. Assume the single predictor has five unordered classes: $[A,B,C,D,E]$. Each value of the single predictor has associated with it a percentage of observations that take the value of $1$: $[0.84, 0.43, 0.51, 0.62, 0.1]$. 84% of the observations with class $A$ had value $1$, 43% of the observations with class $B$ had value $1$, etc.
So, how do we select the optimum split? We order the classes by the associated percentages of observations that take the value $1$:
$$[A, D, C, B, E] \leftrightarrow [0.84, 0.62, 0.51, 0.43, 0.1]$$
• Yes, that's right. One-hot encoding can't give you $[A,D,C]$ and $[B,E]$ as splits, because it forces the algorithm to split only on $A$ or $B$ or $C$ or $D$ or $E$. – jbowman Aug 11 '20 at 23:00