How do the splits points in a decision tree within Random Forest are taken/selected? (Base on which criteria?)

Question

I checked many posts to figure out how random forest (RF) learning algorithm (an ensemble of many decision trees (DT) constructed by Rain forest algorithm) within bagging select split points at each leaf. There are some close questions which are have not been answered in this matter: ref1, ref2. I know that some python package use Splitter implementation, probably based on Gini impurity as they asked here for how it works as well as its reason to use in DT. For example, sklearn package uses CART algorithm to build RF Ref1 Ref2. Also, I found below posts without further explanation about how split points are selected as criteria over dataset exactly:

"... Distance is not a factor with trees - what matters is whether the value is greater than or less than the split point, not the distance from the split point." ref

... unlike linear/logistic regression, RF doesn't work by distance (they work with finding good split for your features), so NO NEED for One-Hot Encoding. ref

Considering an example for continuous target variables through dataframe, once I watched carefully StatQuest: Random Forests Part 1 - Building, Using and Evaluating, and the best I could find with a true example is this video:

Knowing that the decision trees in the random forest are trained on different subsets of the training data (using random features ("feature bagging")), I used and developed the bootstrapped tables or sub-dataframe (resampled but with replacement) in the explanation for 1st DT for better understanding and find relationships in the video example: Here I see 1st DT just both randomly selected variables from data:

x1 =< 4.9  #selected from `id=0` only
x0 =< 4.3  #selected from `id=0` only

So how they selected from id=0 only?

I follow other bootstrapped tables: Then I see 2nd DT just both randomly selected variables from data:

x3 =< 4.6 #selected from `id=4` only
          # No x2 ??

So how they selected just from id=4 only? Is it a random id? I follow other bootstrapped tables: Then I see 3rd DT, just both randomly selected variables from the data:

x2 =< 4.1 #selected from `id=0` or `id=2` not clear?
x2 =< 4.1 #selected from `id=4`

Here is not clear to me why twice x2 was involved in the 3rd tree without involving variable x4?

Finally, I see the fourth DT in the video, from both randomly selected variables from the data:

Then I see 3rd DT, just both randomly selected variables from the data:

x1 =< 4.4 #selected from `id=3` 
x2 =< 6.1 #selected from `id=1`

So Qs:

• Based on which criteria split points are taken/selected for randomly selected pair variables?
• Again, here twice, x1 was involved in the 4th tree without involving variable x1? Does it make sense?
• I'm unsure what I marked based on my finding; explain the "criteria" of x > y, and if so, how it works. Sometimes both randomly selected pair variables are involved in DT; sometimes not.
• I didn't get based on the pick split points y via id=#? Is there any rule, or is it just randomly picked? Can we say it is relative?
• Final decision is being made when the end leaf is 0 or 1?

---

My pythonic implementation:

#Generate data in the video example
import pandas as pd
d = {'x0' : pd.Series([4.3, 3.9, 2.7, 6.6, 6.5, 2.7], index=[0, 1, 2, 3, 4, 5]),
     'x1' : pd.Series([4.9, 6.1, 4.8, 4.4, 2.9, 6.7], index=[0, 1, 2, 3, 4, 5]),
     'x2' : pd.Series([4.1, 5.9, 4.1, 4.5, 4.7, 4.2], index=[0, 1, 2, 3, 4, 5]),
     'x3' : pd.Series([4.7, 5.5, 5.0, 3.9, 4.6, 5.3], index=[0, 1, 2, 3, 4, 5]),
     'x4' : pd.Series([5.5, 5.9, 5.6, 5.9, 6.1, 4.8], index=[0, 1, 2, 3, 4, 5]),
     'y'  : pd.Series([0.0, 0.0, 0.0, 1.0, 1.0, 1.0], index=[0, 1, 2, 3, 4, 5]),
     }

df = pd.DataFrame(d)
print(df)
#    x0   x1   x2   x3   x4    y
#0  4.3  4.9  4.1  4.7  5.5  0.0
#1  3.9  6.1  5.9  5.5  5.9  0.0
#2  2.7  4.8  4.1  5.0  5.6  0.0
#3  6.6  4.4  4.5  3.9  5.9  1.0
#4  6.5  2.9  4.7  4.6  6.1  1.0
#5  2.7  6.7  4.2  5.3  4.8  1.0

#Create RF model

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
plt.style.use('ggplot')
%matplotlib inline
import random
from pprint import pprint
import pdb
from sklearn import tree
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier

#Create and fit RF model with 4 trees
rf  = RandomForestClassifier(n_estimators=4, random_state=0)
rf.fit(df.iloc[:,0:5], df.iloc[:,-1])
#len(rf.estimators_) #4

#Plot the trees for monitoring split points in 1/4 of trees (1st tree)
tree.plot_tree(rf.estimators_[0])

#Plot the trees for monitoring split points in 2/4 of trees (2nd tree)
tree.plot_tree(rf.estimators_[1])

#Plot the trees for monitoring split points in 3/4 of trees (3rd tree)
tree.plot_tree(rf.estimators_[2])

#Plot the trees for monitoring split points in 3/4 of trees (4th tree)
tree.plot_tree(rf.estimators_[3])

Answer 1

You're asking multiple questions, so I will try to answer them all, and then give a piece of code that I used for exploration.

First, here is a summary of how a RandomForestClassifier works:

1. it creates subdataset from the original, using random subsampling of samples and features.
2. it fits DecisionTreeClassifier based on each subdataset.
   • to select the best threshold from the subfeatures that leads to the best split, multiple thresholds are evaluated using a criteria. See the first answer for details.
3. perform a majority vote or an average prediction based on all decision trees prediction

Based on which criteria split points are taken/selected for randomly selected pair variables?

For every feature available for a node¹, separation criteria are computed for multiple thresholds. They are multiple possible implementations for them:

• use all data values as thresholds (which seem to be used in the video)
• use the middle points of all successive data values (used by sklearn here)

So using your data and sklearn convention, if x1 is tested with all samples, the following thresholds are evaluated: [3.65, 4.6, 4.85, 5.5, 6.4]. When it is evaluated, separation criteria are computed as explained in this mathematical formulation. Then the threshold with the best separation criteria is selected.

See this very nice video about decision trees and how ther are built. (9:57 for continuous data + gini impurity computation)

¹ So it doesn't compare multiple features. It is not relative. If you need such behaviour, you could add x-y as an input feature

plot_tree interpretation (EDIT)

value=[2,4] in plot_tree means that you have currently 6 samples¹. 2 from class 0 and 4 from class 1. In your rf.estimators_[3], this dataset has been splitted with feature 0 because it has been evaluated as the best split (minimum impurity with gini=0.444). 3 samples from class 1 went to the right leaf, and the others went to the left node before being splitted again by feature 3.

¹ The number of values doesn't sum to the number of samples because of bootstraping.

Again, here twice, x1 was involved in the 4th tree without involving variable x1? Does it make sense?

I didn't get based on the pick split points y via id=#? Is there any rule, or is it just randomly picked? Can we say it is relative?

I think, if I understand correctly, that you're confusing the build from the video and the one from sklearn. They are different because of the random subsampling, both on samples and features. To generate new samples to be used for DecisionTreeClassifier, see this sklearn _generate_sample_indices() function. In the video, samples id are not the same.

So, x1 is used in the 4th tree of the video, but not in the 4th tree in your code.

I'm unsure what I marked based on my finding; explain the "criteria" of x > y, and if so, how it works. Sometimes both randomly selected pair variables are involved in DT; sometimes not.

Multiple criteria can be used. In sklearn, 3 are possible:

• gini (default)
• entropy
• log_loss

Here are their mathematical formulation.

At each node, a lot of thresholds are evaluated and criteria computed. For example, in the video, for the 1st tree in the 1st node, the following subdataset is used:

For x0, they are 3 different values, so 3 thresholds are evaluated. For x1, 4. That makes 7 entropy (or gini) criteria values. The best is then selected.

Final decision is being made when the end leaf is 0 or 1?

Once again, they are multiple implementations. The original paper used a majority vote, but as mentioned in the sklearn doc:

In contrast to the original publication [B2001], the scikit-learn implementation combines classifiers by averaging their probabilistic prediction, instead of letting each classifier vote for a single class.

I hope it helps.

SAMPLE CODE

Here is a sample code that you can execute with your code, and that shows the 4 DecisionTreeClassifier()s build from the subdatasets. Note that I did not find an explicit function to extract the sub-feature indexes. Note that if you plot the trees, they are all similar to the ones built from RandomForestClassifier() except for the 3rd, but its first node has the same best gini separation. So the difference comes from a different order somewhere; I did not figure out where...

from sklearn.ensemble._forest import _generate_sample_indices
sub_features_indexes = [
    [0, 1], # pair features (x0 , x1) based on video tutorial
    [2, 3], # pair features (x2 , x3) based on video tutorial
    [2, 4], # pair features (x2 , x4) based on video tutorial
    [1, 3]  # pair features (x1 , x3) based on video tutorial
]

for i in range(4):
    seed = rf.estimators_[i].random_state
    boostraped_samples = df.loc[_generate_sample_indices(seed, 6, 6)].sort_index()
    
    #sliced frame based on video tutorial
    boostraped_samples_dfslice = boostraped_samples[boostraped_samples.columns[[sub_features_indexes[i][0],sub_features_indexes[i][1], -1 ]]] 
    display(boostraped_samples_dfslice)

    dtc = DecisionTreeClassifier(random_state=seed)
    dtc.fit(boostraped_samples.iloc[:,sub_features_indexes[i]], boostraped_samples.iloc[:,-1])

    tree.plot_tree(dtc)
    plt.show()

EDIT

So how they selected just from id=4 only? Is it a random id?

When evaluating the value of id=4, so 4.6, as a threshold, the labels are perfectly separated, so there is no need to go further. But, that doesn't mean x2 was not evaluated. It was, but it doesn't separate the labels better than choosing 4.6 as the threshold on feature x3