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.

quoting from this thread:

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]$$

Now we've created an ordering of the predictor (for this step of the overall process only!) Finding the optimum split of this "locally-ordered" predictor is straightforward, as it can be done as if the predictor really were ordered, and Breiman showed that the optimum split of the locally-ordered version of the predictor is also the optimum split of the unordered predictor itself.

• does this hold if we one hot encode, A B,C,D,E? – Maths12 Aug 11 at 11:39
• @Maths12 - No, because the possible splits with one hot encoding are A - not A, B - not B, etc. We can't order across the one hot encoded class variables (in principle we could, but existing algorithms don't.) – jbowman Aug 11 at 16:57
• so in the above example it is assuming that we don't do any encoding , if so this would be for decision tree? if we one hot encode then the tree can only go in one direction i.e. only 2 possible splits? – Maths12 Aug 11 at 17:22
• 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 at 23:00