Lors de l'entraînement, il est nécessaire de trouver la meilleure séparation à chaque nœud de décision. Lorsque les données sont divisées en deux nœuds, l'objectif est que les différentes classes se retrouvent dans des nœuds distincts.

• Meilleur cas possible : tous les points de données d'un nœud appartiennent à la même classe ;
• Pire cas possible : un nombre égal de points de données pour chaque classe.

Impureté de Gini

Pour évaluer la qualité d'une séparation, il est possible de calculer l'impureté de Gini. Il s'agit de la probabilité que, si l'on prend au hasard deux points dans un nœud (avec remise), ils appartiennent à des classes différentes. Plus cette probabilité (impureté) est faible, meilleure est la séparation.

Vous pouvez calculer l'impureté de Gini pour la classification binaire à l'aide de la formule suivante :

Où

• $m_i$ - nombre d'instances de la classe $i$ dans un nœud ;
• $m$ - nombre d'instances dans un nœud ;
• $p_i = \frac{m_i}{m}$ - probabilité de choisir la classe $i$.

Et pour la classification multiclasse, la formule est :

Où

• $C$ - nombre de classes.

La qualité de la séparation peut être mesurée en prenant la somme pondérée des scores de Gini pour les deux nœuds obtenus après une séparation. C'est cette valeur que l'on cherche à minimiser.

Pour séparer un nœud de décision, il est nécessaire d'identifier une caractéristique sur laquelle effectuer la séparation ainsi que le seuil correspondant :

Au niveau d’un nœud de décision, l’algorithme recherche de manière gloutonne le meilleur seuil pour chaque caractéristique. Il choisit ensuite la séparation ayant la plus faible impureté de Gini parmi toutes les caractéristiques (en cas d’égalité, le choix est fait aléatoirement).

Entropie

L’entropie est une autre mesure de l’impureté. Pour un problème de classification binaire, l’entropie $H$ d’un nœud est calculée à l’aide de la formule :

où :

• $p$ est la proportion d’exemples positifs (classe 1) ;
• $1 - p$ est la proportion d’exemples négatifs (classe 0).

Pour un problème de classification multiclasse, l’entropie $H$ d’un nœud est calculée à l’aide de la formule :

où :

• $k$ est le nombre de classes ;
• $p_i$ est la proportion d’exemples appartenant à la classe $i$ dans le nœud.

De manière similaire à l’impureté de Gini, il est possible d’évaluer la qualité d’une séparation en calculant la somme pondérée des valeurs d’entropie pour les nœuds enfants issus de la séparation. C’est cette valeur que l’on cherche à minimiser afin de maximiser le gain d’information.