Le « calendrier de l’Avent » d’apprentissage automatique Jour 7 : classificateur d’arbre de décision

nous avons exploré comment un Régresseur d’arbre de décision choisit sa répartition optimale en minimisant le Erreur quadratique moyenne (MSE).

Aujourd’hui pour le jour 7 du « Calendrier de l’Avent » de Machine Learning, nous poursuivons la même approche mais avec un Classificateur d’arbre de décisionle pendant de classification du modèle d’hier.

Expérience d’intuition rapide avec deux ensembles de données simples

Commençons par un très petit ensemble de données de jouets que j’ai généré, avec une caractéristique numérique et une variable cible avec deux classes : 0 et 1.

L’idée est de couper l’ensemble de données en deux parties, sur la base d’une seule règle. Mais la question est : quelle devrait être cette règle ? Quel est le critère qui nous indique quelle répartition est la meilleure ?

Désormais, même si nous ne connaissons pas encore les mathématiques, nous pouvons déjà examiner les données et deviner d’éventuels points de partage.

Et visuellement, ce serait 8 ou 12droite?

Mais la question est de savoir laquelle est la plus adaptée numériquement.

Si nous pensons intuitivement :

• Avec une scission à 8:
  • côté gauche : pas d’erreur de classification
  • côté droit : une erreur de classification
• Avec une scission à 12:
  • côté droit : pas d’erreur de classification
  • côté gauche : deux erreurs de classement

Alors clairement, le partage à 8 se sent mieux.

Maintenant, regardons un exemple avec trois cours. J’ai ajouté quelques données aléatoires supplémentaires et créé 3 classes.

Ici je les étiquete 0, 1, 3et je les trace verticalement.

Mais il faut être prudent : ces chiffres sont juste les noms de catégoriespas des valeurs numériques. Ils ne doivent pas être interprétés comme « ordonnés ».

L’intuition est donc toujours : Dans quelle mesure chaque région est-elle homogène après la scission ?

Mais il est plus difficile de déterminer visuellement la meilleure répartition.

Maintenant, nous avons besoin d’une manière mathématique pour exprimer cette idée.

C’est exactement le sujet du prochain chapitre.

Mesure des impuretés comme critère de division

Dans le régresseur d’arbre de décision, nous savons déjà :

• La prédiction pour une région est la moyenne de la cible.
• La qualité d’une division se mesure par MSE.

Dans le classificateur d’arbre de décision :

• La prédiction pour une région est la classe majoritaire de la région.
• La qualité d’une division est mesurée par un mesure des impuretés: Impureté Gini ou Entropie.

Les deux sont standard dans les manuels et les deux sont disponibles dans scikit-learn. Gini est utilisé par défaut.

MAIS, qu’est-ce que cette mesure d’impureté, vraiment ?

Si vous regardez les courbes de Gini et Entropieils se comportent tous les deux de la même manière :

• Ils sont 0 lorsque le nœud est pur (tous les échantillons ont la même classe).
• Ils atteignent leur maximum quand les cours sont uniformément mélangé (50 pour cent / 50 pour cent).
• La courbe est lissesymétrique, et augmente avec le désordre.

C’est la propriété essentielle de tout mesure des impuretés:

L’impureté est faible lorsque les groupes sont propres et élevée lorsque les groupes sont mélangés.

Nous utiliserons donc ces mesures pour décider quelle division créer.

Divisé avec une seule fonctionnalité continue

Tout comme pour le Decision Tree Regressor, nous suivrons la même structure.

Liste de toutes les divisions possibles

Exactement comme la version régresseur, avec une caractéristique numérique, les seules divisions que nous devons tester sont les points médians entre les valeurs x triées consécutives.

Pour chaque division, calculez l’impureté de chaque côté

Prenons par exemple une valeur fractionnée, x = 5,5.

Nous séparons l’ensemble de données en deux régions :

• Région L : x < 5,5
• Région R : x ≥ 5,5

Pour chaque région :

1. On compte le nombre total d’observations
2. Nous calculons l’impureté de Gini
3. Enfin, nous calculons l’impureté pondérée de la scission

Sélectionnez la division avec la plus faible impureté

Comme dans le cas du régresseur :

• Répertoriez toutes les divisions possibles
• Calculer l’impureté pour chacun
• La répartition optimale est celle avec impureté minimale

Tableau synthétique de tous les fractionnements

Pour que tout soit automatique dans Excel,
nous organisons tous les calculs dans une tableoù:

• chaque ligne correspond à une division de candidats,
• pour chaque ligne, on calcule :
  • Gini du gauche région,
  • Gini du droite région,
  • et le Gini global pondéré de la scission.

Ce tableau donne un aperçu clair et compact de chaque division possible,
et la meilleure répartition est simplement celle avec la valeur la plus basse dans la dernière colonne.

Classification multiclasse

Jusqu’à présent, nous travaillions avec deux classes. Mais l’impureté Gini s’étend naturellement à trois courset la logique de la scission reste exactement la même.

Rien ne change dans la structure de l’algorithme :

• nous listons toutes les scissions possibles,
• on calcule l’impureté de chaque côté,
• on prend la moyenne pondérée,
• nous sélectionnons la division avec la plus faible impureté.

Seule la formule de l’impureté Gini s’allonge légèrement.

Impureté Gini avec trois classes

Si une région contient les proportions p1, p2, p3

pour les trois classes, alors l’impureté de Gini est :

La même idée qu’avant :
une région est « pure » lorsqu’une classe domine,
et l’impureté devient grande lorsque les classes sont mélangées.

Régions gauche et droite

Pour chaque fractionnement :

• La région L contient quelques observations des classes 1, 2 et 3
• La région R contient les observations restantes

Pour chaque région :

1. compter combien de points appartiennent à chaque classe
2. calculer les proportions p1,p2,p3
3. calculer l’impureté Gini en utilisant la formule ci-dessus

Tout est exactement pareil que dans le cas binaire, avec juste un terme supplémentaire.

Tableau récapitulatif des répartitions en 3 classes

Comme auparavant, nous rassemblons tous les calculs dans un seul tableau :

• chaque ligne est une division possible
• on compte la classe 1, la classe 2, la classe 3 à gauche
• on compte la classe 1, la classe 2, la classe 3 à droite
• nous calculons Gini (Gauche), Gini (Droite)​ et le Gini pondéré

La rupture avec le plus petite impureté pondérée est celui sélectionné par l’arbre de décision.

Nous pouvons facilement généraliser l’algorithme aux classes K, en utilisant ces formules suivantes pour calculer Gini ou Entropie

Dans quelle mesure les mesures d’impuretés sont-elles réellement différentes ?

Or, on mentionne toujours Gini ou Entropie comme critère, mais est-ce qu’ils diffèrent vraiment? En regardant les formules mathématiques, certains diront peut-être

La réponse n’est pas tellement.

En théorie, dans presque toutes les situations pratiques :

• Gini et l’entropie choisissez la même répartition
• La structure arborescente est presque identique
• Les prédictions sont le même

Pourquoi?

Parce que leurs courbes se ressemblent énormément.

Ils culminent tous deux à un mélange de 50 pour cent et chutent à zéro à la pureté.

La seule différence est le forme de la courbe :

• Gini est un quadratique fonction.​ Cela pénalise les erreurs de classification de manière plus linéaire.
• Entropie est un logarithmique fonction, elle pénalise donc l’incertitude un peu plus fortement près de 0,5.

Mais la différence est infime, en pratique, et vous pouvez le faire dans Excel !

Autres mesures d’impuretés ?

Autre question naturelle : est-il possible d’inventer/utiliser d’autres mesures ?

Oui, vous pouvez inventer votre propre fonction, à condition que :

• C’est 0 quand le nœud est pur
• C’est maximale quand les classes sont mixtes
• C’est lisse et strictement croissant en « désordre »

Par exemple : Impureté = 4*p0*p1

Il s’agit d’une autre mesure d’impureté valide. Et c’est en fait égal à Gini multiplié par une constante lorsqu’il n’y a que deux classes.

Donc encore une fois, ça donne les mêmes divisions. Si vous n’êtes pas convaincu, vous pouvez

Voici quelques autres mesures qui peuvent également être utilisées.

Exercices sur Excel

Tests avec d’autres paramètres et fonctionnalités

Une fois que vous avez construit le premier fractionnement, vous pouvez étendre votre fichier :

• Essayer Entropie à la place de Gini
• Essayez d’ajouter caractéristiques catégorielles
• Essayez de construire le prochaine division
• Essayez de changer profondeur maximale et observez le sous-ajustement et le sur-ajustement
• Essayez de créer une matrice de confusion pour les prédictions

Ces tests simples vous donnent déjà une bonne intuition du comportement des véritables arbres de décision.

Implémentations des règles pour Titanic Survival Dataset

Un exercice de suivi naturel consiste à recréer les règles de décision pour le célèbre Ensemble de données de survie du Titanic (CC0 / Domaine public).

Premièrement, nous pouvons commencer avec seulement deux fonctionnalités : sexe et âge.

Implémenter les règles dans Excel est long et un peu fastidieux, mais c’est justement le but : cela permet de se rendre compte à quoi ressemblent réellement les règles de décision.

Ils ne sont rien d’autre qu’une séquence de SI/SINON déclarations, répétées encore et encore.

C’est la véritable nature d’un arbre de décision : des règles simples, empilées les unes sur les autres.

Conclusion

La mise en œuvre d’un classificateur d’arbre de décision dans Excel est étonnamment accessible.

Avec quelques formules, vous découvrez le cœur de l’algorithme :

• lister les divisions possibles
• calculer l’impureté
• choisissez la répartition la plus propre

Ce mécanisme simple est à la base de modèles d’ensemble plus avancés comme Arbres améliorés par dégradédont nous parlerons plus tard dans cette série.

Et restez à l’écoute pour Jour 8 demain!