I'm working on a HW implementation of DT and need a way to optimize the splitting procedure.
quoting from this thread:
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,