Continuous variable evaluation in decision trees I was going through the C4.5 and ID3 algorithms used to construct a decision tree. Was wondering if there is an efficient way to compute information gain from a continuous variable (during the step where the variable to split is selected), other than evaluating each knot and selecting the best information gain knot for this variable.
Especially if the variable has almost a million distinct values.
 A: As you may know, the ID3 algorithm or Iterative Dichotomiser 3 popularized by Quinlan (1986), as its name says, searches for the optimal splitting-point on your training data that maximizes the information gain. As long as I know, vanilla ID3 doesn't handle continuous predictor nor outcome variables.
C4.5 and CART (Breiman et al., 1984) are improvements of the ID3 algorithm and these two handle continuous data in both predictors and outcome using variance reduction, but you're right, in the sense that their implementation would be inneficient if one or more of your continuous predictors has a million distinct values.
I see two paths you could take IF you really want to use decision trees, given that you have a million (or more) data points:

*

*Use business knowledge to bin your continuous variable(s) This way, the algorithm won't need to calculate $N-1$ variance reductions, where $N$ is the number of distinct values that your variable takes on the training set.


*Use a standard number of bins, like 5 or 9.
As you can see, both strategies involve binning, then you're trading information by having a practical more efficient workflow. Assuming that you have millions of data points, low computer power and a need for explainability, I suggest to use google colab or any cloud provider, so you don't suffer efficiency problems. Another approach would be to sample your training data to a smaller size; with so many data points your sample should be representative.
Bibliography

*

*J.R. Quinlan Induction on Decision Trees 1986

*L. Breiman, J.H. Friedman, R.A. Olsen, C.J. Stone Classification and Regression Trees 1984

