Division des Nœuds

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 scénario : tous les points de données d’un nœud appartiennent à la même classe ;
• Pire scénario : un nombre égal de points de données pour chaque classe.

Impureté de Gini

Pour évaluer la qualité d'une séparation, on peut calculer l'impureté de Gini. Il s'agit de la probabilité que, si l'on sélectionne aléatoirement 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 une 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é d'une séparation peut être mesurée par la somme pondérée des scores de Gini pour les deux nœuds issus d'une séparation. C'est cette valeur que l'on cherche à minimiser.

Pour diviser un nœud de décision, il faut 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.