# How to (better) discretize continuous data in decision trees?

Standard decision tree algorithms, such as ID3 and C4.5, have a brute force approach for choosing the cut point in a continuous feature. Every single value is tested as a possible cut point. (By tested I mean that e.g. the Information gain is calculated at every possible value.)

With many continuous features and a lot of data (hence many values for each feature) this apporach seems very inefficient!

I'm assuming finding a better way to do this is a hot topic in Machine Learning. In fact my Google Scholar search revealed some alternative approaches. Such as discretizing with k-means. Then there seem to be a lot of papers that tackle specific problems in specific domains.

But is there a recent review paper, blog post or book that gives an overview on common apporaches for discretization? I couldn't find one...

Or else, maybe one of you is an expert on the topic and willing to write up a small overview. That would be tremendously helpful!

No, you probably don't want to try all possible cut points in a serious implementation. That's how we describe it in simple introductions to ID3, because it's easier to understand, but it's typically not how it is actually implemented, because it is slow. In particular, if there are $n$ data points, then you'll need to test $n-1$ candidate thresholds; using the naive algorithm to calculate the information gain of each of those candidate thresholds takes $O(n)$ time per candidate, for a total of $O(n^2)$ time.
1. Don't try all possible thresholds. Instead, pick a random sample of 1000 candidate thresholds (chosen uniformly at random out of the set of $n-1$ candidate thresholds), calculate the information gain for each, and choose the best one.
2. Use dynamic programming to efficiently compute the information gain of all $n-1$ splits, in total of $O(n)$ time, by reusing computation. The algorithm is pretty straightforward to derive.