Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Apprendre Division des Nœuds | Arbre de Décision
Classification avec Python

bookDivision des Nœuds

Lors de l'entraînement, il est nécessaire de déterminer 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 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.

Le calcul de l'impureté de Gini pour la classification binaire s'effectue à l'aide de la formule suivante :

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

Où

  • mim_i - nombre d'instances de la classe ii dans un nœud ;
  • mm - nombre d'instances dans un nœud ;
  • pi=mimp_i = \frac{m_i}{m} - probabilité de choisir la classe ii.

Pour la classification multiclasse, la formule est :

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

Où

  • CC - nombre de classes.

L'évaluation de la qualité d'une séparation s'effectue en calculant la somme pondérée des scores de Gini pour les deux nœuds issus de la séparation. Cette valeur doit être minimisée.

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 :

À 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 avec la plus faible impureté de Gini parmi toutes les caractéristiques (en cas d’égalité, le choix est aléatoire).

Entropie

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

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

où :

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

Pour un problème de classification multiclasse, l’entropie HH d’un nœud est calculée selon la formule :

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)

où :

  • kk est le nombre de classes ;
  • pip_i est la proportion d’exemples appartenant à la classe ii 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.

Note
Remarque

L'entropie est maximale lorsque toutes les classes sont représentées de manière égale. Elle est minimale (0) lorsque tous les exemples appartiennent à une seule classe (nœud pur).

question mark

Choisir une meilleure séparation.

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 3. Chapitre 2

Demandez à l'IA

expand

Demandez à l'IA

ChatGPT

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Suggested prompts:

Can you explain the difference between Gini impurity and entropy?

How do you choose between using Gini impurity and entropy in practice?

Can you show an example calculation for Gini impurity or entropy?

Awesome!

Completion rate improved to 4.17

bookDivision des Nœuds

Glissez pour afficher le menu

Lors de l'entraînement, il est nécessaire de déterminer 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 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.

Le calcul de l'impureté de Gini pour la classification binaire s'effectue à l'aide de la formule suivante :

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

Où

  • mim_i - nombre d'instances de la classe ii dans un nœud ;
  • mm - nombre d'instances dans un nœud ;
  • pi=mimp_i = \frac{m_i}{m} - probabilité de choisir la classe ii.

Pour la classification multiclasse, la formule est :

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

Où

  • CC - nombre de classes.

L'évaluation de la qualité d'une séparation s'effectue en calculant la somme pondérée des scores de Gini pour les deux nœuds issus de la séparation. Cette valeur doit être minimisée.

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 :

À 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 avec la plus faible impureté de Gini parmi toutes les caractéristiques (en cas d’égalité, le choix est aléatoire).

Entropie

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

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

où :

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

Pour un problème de classification multiclasse, l’entropie HH d’un nœud est calculée selon la formule :

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)

où :

  • kk est le nombre de classes ;
  • pip_i est la proportion d’exemples appartenant à la classe ii 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.

Note
Remarque

L'entropie est maximale lorsque toutes les classes sont représentées de manière égale. Elle est minimale (0) lorsque tous les exemples appartiennent à une seule classe (nœud pur).

question mark

Choisir une meilleure séparation.

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 3. Chapitre 2
some-alt