8
$\begingroup$

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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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.

In practice, there are optimizations that speed this up significantly:

  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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! Shame on me, I just stuck to the simple introductions and never looked into the actual implementation... No. 1 is really straightforward and I'll definetely look into No. 2! Other than that I was looking for "more creative" approaches. Such as the k-means discretization I mentioned. Or figuring out the distribution of the continuous feature for each class and define the cut point based on those distributions - so a more analytical approach. Do you know of an something like that? $\endgroup$
    – AutoMiner
    Commented Apr 7, 2017 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.