Splitting the Nodes

During training, we need to find the best split at each decision node. When we split the data into two nodes, we aim for different classes to be in separate nodes.

• Best case scenario: all data points in a node belong to the same class.
• Worst case scenario: an equal number of data points for each class.

To measure how good a split is, we can calculate the Gini impurity. It is the probability that if we randomly take two points from a node (with replacement), they will be of different classes. The lower this probability (impurity), the better the split.

You can calculate the Gini impurity for binary classification using the following formula:

And for multiclass classification, the formula is:

We can measure how good the split is by taking the weighted sum of Gini scores for both nodes obtained from a split. That's the value we want to minimize.

To split a decision node, we need to find a feature to split on and the threshold:

At a decision node, the algorithm greedily finds the best threshold for each feature. Then it chooses the split with the lowest Gini impurity out of all features (if there is a tie, it chooses randomly).