0
$\begingroup$

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?
$\endgroup$
0
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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