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.

Gini Impurity

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:

Where

• $m_i$ - number of instances of class $i$ in a node;
• $m$ - number of instances in a node;
• $p_i = \frac{m_i}{m}$ - probability of choosing class $i$.

And for multiclass classification, the formula is:

Where

• $C$ - number of classes.

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).

Entropy

The entropy is another measure of the impurity. For a binary classification problem, the entropy $H$ of a node is calculated using the formula:

where:

• $p$ is the proportion of positive examples (class 1);
• $1 - p$ is the proportion of negative examples (class 0).

For a multiclass classification problem, the entropy $H$ of a node is calculated using the formula:

where:

• $k$ is the number of classes;
• $p_i$ is the proportion of examples belonging to class $i$ in the node.

Similarly to Gini impurity, we can measure how good a split is by calculating the weighted sum of entropy values for the child nodes obtained from the split. This is the value we want to minimize in order to maximize the information gain.