Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Aprenda Splitting the Nodes | Section
Classification with Python

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

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:

gini=1−p02−p12=1−(m0m)2−(m1m)2\text{gini} = 1 - p_0^2 - p_1^2 = 1 - (\frac{m_0}{m})^2 - (\frac{m_1}{m})^2

Where

  • mim_i - number of instances of class ii in a node;
  • mm - number of instances in a node;
  • pi=mimp_i = \frac{m_i}{m} - probability of choosing class ii.

And for multiclass classification, the formula is:

gini=1−∑i=0Cpi2=1−∑i=0C(mim)2\text{gini} = 1 - \sum_{i=0}^C p_i^2 = 1 - \sum_{i=0}^C(\frac{m_i}{m})^2

Where

  • CC - 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 HH of a node is calculated using the formula:

H(p)=−plog⁡2(p)−(1−p)log⁡2(1−p)H(p) = -p \log_2(p) - (1 - p) \log_2(1 - p)

where:

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

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

H(p1,p2,…,pk)=−∑i=1kpilog⁡2(pi)H(p_1, p_2, \dots, p_k) = -\sum_{i=1}^{k} p_i \log_2(p_i)

where:

  • kk is the number of classes;
  • pip_i is the proportion of examples belonging to class ii 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.

Note
Note

The entropy is maximum when all classes are equally represented. It is minimum (0) when all examples belong to one class (pure node).

question mark

Choose a better split.

Select the correct answer

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 1. Capítulo 15

Pergunte à IA

expand

Pergunte à IA

ChatGPT

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

bookSplitting the Nodes

Deslize para mostrar o menu

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:

gini=1−p02−p12=1−(m0m)2−(m1m)2\text{gini} = 1 - p_0^2 - p_1^2 = 1 - (\frac{m_0}{m})^2 - (\frac{m_1}{m})^2

Where

  • mim_i - number of instances of class ii in a node;
  • mm - number of instances in a node;
  • pi=mimp_i = \frac{m_i}{m} - probability of choosing class ii.

And for multiclass classification, the formula is:

gini=1−∑i=0Cpi2=1−∑i=0C(mim)2\text{gini} = 1 - \sum_{i=0}^C p_i^2 = 1 - \sum_{i=0}^C(\frac{m_i}{m})^2

Where

  • CC - 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 HH of a node is calculated using the formula:

H(p)=−plog⁡2(p)−(1−p)log⁡2(1−p)H(p) = -p \log_2(p) - (1 - p) \log_2(1 - p)

where:

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

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

H(p1,p2,…,pk)=−∑i=1kpilog⁡2(pi)H(p_1, p_2, \dots, p_k) = -\sum_{i=1}^{k} p_i \log_2(p_i)

where:

  • kk is the number of classes;
  • pip_i is the proportion of examples belonging to class ii 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.

Note
Note

The entropy is maximum when all classes are equally represented. It is minimum (0) when all examples belong to one class (pure node).

question mark

Choose a better split.

Select the correct answer

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 1. Capítulo 15
some-alt