Thinking of the RandomForestClassifier function in sklearn.ensemble, I understand that at each non-terminal node the algorithm:
- Randomly selects a subset of size max_features from the set of all features
- 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:
- Does sklearn check all possibilities like above?
- 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?