Durante o treinamento, precisamos encontrar a melhor divisão em cada Nó de Decisão. Quando dividimos os dados em dois nós, queremos que classes diferentes estejam em nós distintos.

• Melhor cenário: Todos os pontos de dados em um nó pertencem à mesma classe.
• Pior cenário: Número igual de pontos de dados para cada classe.

Para medir o quão boa é uma divisão, podemos calcular a Impureza de Gini. É a probabilidade de que, se pegarmos aleatoriamente dois pontos de um nó (com reposição), eles serão de classes diferentes. Quanto menor essa probabilidade (impureza), melhor a divisão.

Você pode calcular a impureza de Gini para classificação binária usando a seguinte fórmula:

E para classificação multiclasse, a fórmula é:

Podemos medir a qualidade da divisão calculando a soma ponderada dos índices de Gini para ambos os nós obtidos a partir de uma divisão. Esse é o valor que queremos minimizar. Para dividir um Nó de Decisão, precisamos encontrar um recurso para dividir e o limiar correspondente.

Em um Nó de Decisão, o algoritmo busca avidamente o melhor limiar para cada característica. Depois, ele escolhe a divisão com a menor impureza de Gini entre todas as características (se houver um empate, ele escolhe aleatoriamente).