How does sklearn random forest decide feature threshold at node splitting exactly?

Question

Thinking of the RandomForestClassifier function in sklearn.ensemble, I understand that at each non-terminal node the algorithm:

1. Randomly selects a subset of size max_features from the set of all features
2. Searches for the feature x and the threshold value x_0 such that when the node is split according to {x<=x_0} and {x>x_0}, the Gini impurity is minimized (I'm using the Gini setting)

My question is about how exactly this search is carried out and a value for x_0 chosen. The obvious method would be to just test all possibilities, taking into account that only the order of x_0 relative to the training set matters. That is, look at the x-values of all training points. If a is the largest of these values <= x_0 and b is the smallest of these values > x_0, then any other choice of x_0 within the half-open interval [a,b) would have produced exactly the same splitting. So it suffices to test one value of x_0 from each half-open interval and choose the one with the lowest Gini impurity.

To be specific then, my question is:

1. Does sklearn check all possibilities like above?
2. The value of x_0 makes no difference in the training step as long its nearest neighbors in the training set don't change. But it may make a difference in the testing step, when the tree is applied to new data points. So how does sklearn decide a specific value for x_0 in the training step?

Answer 1

After some searching, I found this source code:

https://github.com/scikit-learn/scikit-learn/blob/7813f7efb5b2012412888b69e73d76f2df2b50b6/sklearn/tree/_splitter.pyx#L467

I think, but am not 100% sure as my code comprehension is imperfect, that:

1. Yes
2. x_0 = (a+b)/2, where a is the nearest neighbor to the left and b is the nearest neighbor to the right

Answer 2

I think this course can give the answer to the question you are looking for by explaining the concept on the basics of a Decision Tree.

How a Decision Tree Works with Numerical Features

Suppose we have a numeric feature "Age" that has a lot of unique values. A decision tree will look for the best (according to some criterion of information gain) split by checking binary attributes such as "Age <17", "Age < 22.87", and so on. But what if the age range is large? Or what if another quantitative variable, "salary", can also be "cut" in many ways? There will be too many binary attributes to select from at each step during tree construction. To resolve this problem, heuristics are usually used to limit the number of thresholds to which we compare the quantitative variable.

[...]We see that the tree used the following 5 values to evaluate by age: 43.5, 19, 22.5, 30, and 32 years. If you look closely, these are exactly the mean values between the ages at which the target class "switches"[...]