Impureté de Gini — un autre critère pour diviser un nœud dans un arbre de décision
En tant qu’algorithme d’apprentissage automatique classique le plus populaire, l’arbre de décision est beaucoup plus intuitif que les autres pour son explicabilité. Dans mes articles précédents, j’ai introduit les algorithmes ID3 et C4.5 pour construire des modèles d’arbres de décision.
- Bases de l’arbre de décision et algorithme ID3
- Inconvénients ID3 et C4.5 Algorithme
Dans cet article, je vais présenter un algorithme supplémentaire appelé CART pour construire un modèle d’arbre de décision, qui est également probablement le plus couramment utilisé. BTW, c’est l’algorithme par défaut lorsque vous utilisez la bibliothèque Scikit-Learn pour un classificateur d’arbre de décision.
L’algorithme CART est une abréviation des arbres de classification et de régression. Il a été inventé par Breiman et al. en 1984.
Il est généralement très similaire à C4.5, mais ont les caractéristiques principales suivantes:
- Plutôt que des arbres généraux qui pourraient avoir plusieurs branches, CART utilise un arbre binaire, qui n’a que deux branches de chaque nœud.
- CART utilise l’impureté de Gini comme critère pour diviser le nœud, pas le Gain d’informations.
- CART prend en charge les variables cibles numériques, ce qui lui permet de devenir un arbre de régression qui prédit des valeurs continues.
Cet article se concentrera sur CART en tant qu’arbre de classification.
Impureté de Gini
Tout comme les algorithmes ID3 et C4.5 qui s’appuient sur le gain d’informations comme critère pour diviser les nœuds, l’algorithme CART utilise un autre critère appelé Gini pour diviser les nœuds.
Si vous avez déjà appris l’économie, vous devez connaître l’indice de Gini, qui indique l’inégalité des revenus ou de la richesse au sein d’une nation ou de tout autre groupe de personnes.
Dans l’algorithme CART, il utilise intuitivement le coefficient de Gini dans un but similaire. Autrement dit, le plus grand coefficient de Gini signifie la plus grande impureté du nœud. Similaire à ID3 et C4.5 en utilisant le gain d’informations pour sélectionner le nœud avec plus d’incertitude, le coefficient de Gini guidera l’algorithme CART pour trouver le nœud avec une incertitude plus grande (c’est-à-dire une impureté), puis le diviser.
La formule du coefficient de Gini est relativement plus simple que le Gain d’Information et le Rapport de Gain d’Information que nous avons utilisés dans les deux autres algorithmes de l’Arbre de décision. Il est montré comme suit.
- p(Ck/t) est la probabilité qu’un nœud t soit de catégorie Ck.
- Le coefficient de Gini du nœud t est 1 moins la somme de la probabilité de toutes les catégories.
N’ayez pas peur de la formule. Prenons un exemple pour le démontrer. Je promets que ce n’est pas difficile à comprendre.
L’exemple ci-dessous a été utilisé dans tous les autres articles que j’ai écrits sur l’arbre de décision.
Supposons que nous souhaitions démarrer l’arbre de décision en divisant en utilisant la fonction « Météo ». Ensuite, nous devons calculer les coefficients de Gini pour ses conditions. Concentrons-nous sur l’attribut météo et les résultats, qui sont présentés dans les tableaux ci-dessous.
Il est assez facile de calculer la probabilité p (Ck |t). Par exemple, si l’on considère l’attribut « météo = ensoleillé », il a 1 « oui » et 2 « non » sur 3 échantillons totalement. Par conséquent, la probabilité de la catégorie « oui » est de 1/3 et de 2/3 pour la catégorie « non ». On peut alors facilement calculer le coefficient de Gini pour chacun d’eux comme suit.