The efficiency of Decision Tree

Question

When we use top down approach to induce a decision tree, we need to use some kind of splitting criteria to choose the splitting feature and splitting value at a certain internal node.

The criteria could be:

• IG
• IGR
• Gini impurity

But the feature selection seems very computationally intensive. Because we need to enumerate all the existing features and go through all its possible splitting values. And for each of the feature/splitting value, we need to calculate the criteria value and memorize it, and select the best value.

Am I correct on this? Is there anything we can do to improve it?

Answer 1

I will share my experience on implementing those kind of decision trees. There are some ideas which I found also in R, Weka, Python implementations. In order to keep things simple, I will suppose you talk about CART-like trees, but the things I explain could be extended trivially to any kind of decision tree.

• You do not need to store all the splitting candidates. The reason is that you consistently use the same criteria at a given run: IG, IGR, Gini, entropy, error, or other. Thus you need to keep only the best candidate, and fort this candidate you need to have: splitting variable name, numerical split label (for numeric features), string split label (for nominal variable), value for given criteria (used for comparison) and that is all. This will save you some linear memory
• You do not have to split the instances for every candidate, so you first find the best candidate, and only after you eliminated all other weaker candidates, you split your data set. I saw often this mistake, and could make running time explode to $O(n^2)$ at each evaluation node
• For numeric variable to find the best split use a linear algorithm: create two sets of bins, one for left node, one for right, where each there are $k$ bins corresponding to the number of output classes. Initially the left bins will contain all the totals. While iterating substract from the left bins and add for the right bins and then compute splitting value criteria directly from bins. If for each split value you remake the totals from data points you will have again $O(n^2)$
• For nominal variables use the same trick with bins, but this time having $P$ bins where $P$ is the number of factors of the nominal variable.
• You might use presorting of the variables. Initially your sort all the variables before any learning. At each node evaluation use sorted vectors, and after one choose the best split, you will split the data points and also the sorted indexes, in order to send to the child nodes the subset of data and subsets of sorted indexes. Thus you can apply this idea in recursion. Note however that this works if the number of data instances is greater than number of input features
• Use parallelism as much as possible. There are a lot of things which can be parallelized due to their design: evaluate multiple variables in parallel, evaluate multiple trees in parallel (for random forests, bagging)
• Avoid evaluation when is not necessary: if a binary variable was used as split variable than is useless to try to evaluate that again in children nodes, since all the instances will have the same value for this variable
• If you have a binary variable with labels: "male", "female" you can avoid evaluate sending "female" to left, "male" to right and also sending "female" to left and "male to right. Both variants are equivalent.
• For numerical variables, if there are many data points one can avoid evaluating on all split candidate positions, only for a randomly chosen sample of them. This is as far as I know implemented in R. One can safely use this trick for random forests where the precision regarding the split point is not important because is covered by averaging

PS: however I believe this question belongs more to SO