Introduction : Arbres de décision et nécessité de la pureté

Les arbres de décision sont l'un des algorithmes d'apprentissage supervisé les plus intuitifs et les plus largement utilisés dans l'apprentissage automatique. Ils modélisent les décisions en tant que structure d'arbre, où les nœuds internes représentent des tests sur les caractéristiques, les branches représentent les résultats de ces tests, et les nœuds de feuilles représentent des prédictions finales.

Le défi principal dans la construction d'un arbre de décision consiste à décider où diviser les données à chaque nœud. L'algorithme doit choisir la fonction et la valeur de division qui sépare le mieux les classes cibles. C'est là que l'entropie entre en jeu. L'entropie, empruntée à la théorie de l'information, fournit une mesure mathématique de l'incertitude ou de l'impureté dans un ensemble de données.

Qu'est-ce que l'entropie?

Dans le langage quotidien, l'entropie fait référence au hasard ou au chaos. Dans le contexte des arbres de décision, l'entropie quantifie la quantité d'imprévisibilité dans un ensemble de données par rapport à la variable cible. Si tous les exemples dans un noeud appartiennent à la même classe, le noeud est pure et son entropie est zéro. Inversement, si les classes sont uniformément mélangées, l'entropie atteint son maximum.

Pour un problème de classification binaire (p. ex. positif ou négatif), l'entropie est définie comme suit:

Entropie = –p+ log2(p+) – p− log2(p−)

où p+ est la proportion d'exemples positifs et p− = 1 – p+. La base logarithmique 2 est utilisée parce que l'information en bits est mesurée en binaire. Lorsqu'il y a plus de deux classes, la formule se généralise à:

Entropie = – γ pi log2(pi) pour toutes les classes i.

La valeur résultante varie de 0 (parfaitement pure) à log2(k) pour les classes k (impureté maximale). Pour un cas binaire, l'entropie maximale est de 1,0 lorsque p+ = p− = 0,5.

Un exemple rapide

Entropie = –0,5 log2(0,5) –0,5 log2(0,5) = –0,5 * (–1) – 0,5 * (–1) = 0,5 + 0,5 = 1,0. Maintenant, considérez un ensemble de données avec 9 positifs et 1 négatif: entropie = –0,9 log2(0,9) – 0,1 log2(0,1) -0,9 * (–0,152) – 0,1 * (–3,322) -0,137 + 0,332 = 0,469. Le deuxième ensemble de données est beaucoup plus prévisible.

Pourquoi la base 2 ?

Le choix de base 2 est enraciné dans la théorie de l'information de Claude Shannon. Un peu est l'unité fondamentale de l'information, représentant un choix binaire. L'entropie de base 2 donne le nombre moyen de bits nécessaires pour coder la classe d'un échantillon aléatoire. Si vous connaissez déjà la distribution, l'entropie inférieure signifie moins de bits sont nécessaires pour communiquer le résultat.

Gain d'information : comment l'entropie guide les séparations

Le simple calcul de l'entropie n'est pas suffisant; l'objectif est de réduire le résultat après scission. Le gain d'information (IG) mesure la réduction prévue de l'entropie causée par la partition des données selon une fonction. La fonctionnalité et la valeur fractionnée qui produisent le gain d'information le plus élevé sont choisies pour le nœud.

La formule pour obtenir des renseignements est la suivante :

Gain d'information = Entropie(parent) – -- (=Si-) * Entropie(Si-)

où S est l'ensemble de données parent, Si sont les sous-ensembles enfants après la fraction, et . , indique le nombre d'échantillons. La somme est une moyenne pondérée des entropies enfants.

Exemple travaillé

Imaginez un nœud parent avec 30 échantillons : 16 classes A et 14 classes B. Entropy(parent) = –(16/30) log2(16/30) – (14/30) log2(14/30) -0.996.

Maintenant, considérez une fraction sur la caractéristique X qui crée deux enfants : Child1 a 20 échantillons (15 A, 5 B) → entropie = –0,75 log2(0,75) – 0,25 log2(0,25) -0,811; Child2 a 10 échantillons (1 A, 9 B) → entropie = –0,1 log2(0,1) – 0,9 log2(0,9) -0,469. Entropie enfant pondérée = (20/30)*0,811 + (10/30)*0,469 -0,541 + 0,156 = 0,697. Gain d'information = 0,996 – 0,697 = 0,299.

Si une autre division donne plus d'IG, cette division est préférée. L'algorithme évalue toutes les fonctionnalités et les seuils de division possibles pour trouver la meilleure.

Limites du gain en information

Le gain d'information tend à favoriser des caractéristiques avec de nombreuses valeurs distinctes (par exemple, une colonne d'ID unique) parce que la fractionnement d'une telle fonctionnalité crée de nombreux enfants purs, donnant des IG élevés. Cela peut conduire à un surajustement. Pour contrer cela, des variantes comme Ratio de gain (utilisé dans C4.5) normaliser IG par l'information intrinsèque de la fraction.

Comparaison de l'entropie avec l'impureté de Gini

L'impureté de Gini est un autre critère de division utilisé dans l'algorithme CART (Arbres de classification et de régression). Il mesure la probabilité de classification erronée d'un échantillon choisi au hasard s'il a été étiqueté au hasard selon la distribution de classe dans le noeud. La formule:

Gini = 1 – --]

Dans un cas binaire, Gini = 2p+(1 – p+). Le maximum de Gini est de 0,5 (classes équilibrées) et le minimum est de 0 (pure).

L'impureté entropie et Gini sont des fonctions convexes, ce qui signifie qu'elles se comportent de la même manière dans la pratique. Le choix entre elles revient souvent à l'efficacité computationnelle : Gini n'exige pas de logarithmes, donc il peut être légèrement plus rapide. Cependant, l'entropie a une justification information-théorique plus forte.

Entropie dans les arbres de régression

Les arbres de décision peuvent également résoudre des problèmes de régression (prédicatifs de valeurs continues).Dans la régression, l'entropie n'est pas appropriée parce que la cible n'est pas catégorique. L'algorithme utilise plutôt réduction de la variation ou erreur carrée moyenne (EME) comme critère de division. L'idée est analogue : à chaque nœud, nous nous séparons pour minimiser la somme pondérée des variances des nœuds enfants.

Pour la régression, la quantité est souvent appelée réduction moyenne des erreurs carrées ou [réduction totale de la variance[. Le principe est exactement le même que le gain d'information : mesurer l'impureté (variance) du parent, puis la moyenne pondérée des enfants, et maximiser la différence.

Construire un arbre décisionnel complet : de la racine à la feuille

Maintenant que nous comprenons l'entropie et le gain d'information, let ,s marche à travers la façon dont un algorithme d'apprentissage d'arbre de décision typique (comme ID3, C4.5, ou CART) construit un arbre:

  1. Commencez avec l'ensemble de données au nœud racine.
  2. Calculer l'impureté de la racine en utilisant l'entropie (pour la classification) ou la variance (pour la régression).
  3. Pour chaque fonction, évaluer chaque point de partage possible (pour les caractéristiques numériques, trier les valeurs et considérer les points médians entre des valeurs distinctes consécutives; pour les caractéristiques catégoriques, considérer les sous-ensembles ou l'encodage à une seule chaleur).
  4. Calculer le gain d'information (ou le rapport de gain, la réduction de Gini, etc.) pour chaque fraction.
  5. Choisir la fraction qui donne le gain le plus élevé.
  6. Partition les données[ et répéter récursivement les étapes 2 à 5 pour chaque nœud d'enfant.
  7. Les critères de remplissage[ empêchent la croissance infinie : profondeur maximale, échantillons minimums par feuille, diminution minimale d'impureté, ou lorsque tous les échantillons dans un noeud appartiennent à une classe.
  8. Prune l'arbre (soit pré-élagage via des hyperparamètres ou post-élagage en coupant les branches qui ne améliorent pas les performances sur un ensemble de validation) pour combattre le surajustement.

Manipulation Caractéristiques catégoriques et numériques

Le fractionnement basé sur l'entropie fonctionne pour les deux types de caractéristiques, mais l'approche diffère :

  • Caractéristiques numériques: L'algorithme trie les valeurs uniques et teste chaque seuil possible. Pour l'efficacité, il ne tient souvent compte que des seuils entre les valeurs triées consécutives où l'étiquette de classe change.
  • Caractéristiques catégoriques: Pour les scissions binaires, l'algorithme peut envisager de regrouper les catégories en deux sous-ensembles. Pour les scissions multi-directions (comme dans ID3), chaque catégorie devient une branche.

Manipulation des valeurs manquantes

Les ensembles de données du monde réel contiennent souvent des valeurs manquantes. Les arbres de décision peuvent les gérer de plusieurs façons :

  • Scissions de substitution: Lorsqu'on divise une fonction, une fonction de sauvegarde qui imite le mieux la scission est utilisée pour les échantillons qui ne sont pas dotés de la fonction primaire.
  • instances fractionnelles: Attribuer un échantillon à plusieurs enfants dont le poids est proportionnel à la probabilité de chaque enfant, en fonction des données non manquantes.
  • Imputation simple[ : Remplacer les valeurs manquantes par le mode ou la médiane avant de construire l'arbre.

De nombreuses bibliothèques, comme scikit-learn, ne gèrent pas les valeurs manquantes en interne et s'attendent à les imputer au préalable. XGBoost et LightGBM, cependant, apprennent la meilleure direction pour les valeurs manquantes pendant l'entraînement.

Sur-aménagement et taille

Un arbre de décision cultivé à la profondeur maximale mémorise parfaitement les données d'entraînement, y compris le bruit, conduisant à une mauvaise généralisation. La réduction de l'entropie continue jusqu'à ce que chaque feuille soit pure, mais cela profite rarement aux performances de test.

Pré-élagage (arrêt précoce)

Arrêter la croissance des arbres avant qu'elle ne s'adapte au mieux en appliquant des contraintes : limiter la profondeur maximale, exiger un nombre minimum d'échantillons par feuille ou exiger une réduction minimale des impuretés (p. ex., la diminution de l'entropie doit être > 0,01).

Ébauche après la taille (Ébauche de complexité des coûts)

L'algorithme considère un compromis entre la complexité de l'arbre (nombre de feuilles) et l'erreur d'entraînement. Un paramètre de complexité (alpha) pénalise les feuilles supplémentaires. Scikit-learn , offre une taille de complexité par rapport aux coûts via .

Les deux techniques de taille permettent de s'assurer que les fractions entropiées ne sont pas trop granuleuses et que l'arbre reste interprétable tout en généralisant bien.

Entropie dans les méthodes d'ensemble

Bien qu'un arbre de décision unique puisse être instable (de petits changements de données peuvent entraîner un arbre très différent), l'entropie reste un concept fondamental dans les méthodes d'ensemble :

  • Random Forests: Construire de nombreux arbres à l'aide d'échantillons de bootstrap et de sous-ensembles aléatoires. Chaque arbre utilise généralement l'entropie ou Gini pour se diviser.
  • Gradient Boosting[: Les arbres sont construits successivement pour corriger les erreurs des arbres précédents. L'entropie est utilisée comme objectif (par la perte d'entropie croisée) pour la classification des forêts dans des bibliothèques comme XGBoost.

Comprendre l'entropie aide à interpréter pourquoi une fraction particulière a été choisie dans un arbre individuel, ce qui est essentiel pour le débogage du modèle et l'analyse de l'importance des caractéristiques.

Considérations pratiques lors de l'utilisation de l'entropie

Premièrement, calculer l'entropie avec soin en utilisant des logarithmes — éviter log(0) non défini en définissant 0 log2(0) comme 0. Deuxièmement, être conscient que les calculs d'entropie sont sensibles au déséquilibre des classes; un noeud avec 99 % d'une classe et 1 % d'une autre a une faible entropie mais peut ne pas indiquer une bonne fraction si la classe minoritaire est importante.

De plus, les arbres de décision avec entropie peuvent être à forte intensité de mémoire pour les grands ensembles de données parce qu'ils évaluent toutes les fonctionnalités et les points de division. Les bibliothèques utilisent des algorithmes comme sort-and-scan pour calculer l'entropie pour les fonctionnalités numériques dans le temps O(n log n).

Références externes pour une lecture plus approfondie:

Au-delà de la classification : Entropie et gain d'information dans la sélection des éléments

L'entropie n'est pas seulement utilisée dans les arbres de décision — elle permet également de sélectionner les techniques de sélection des caractéristiques. L'information mutuelle[ entre la fonctionnalité et la cible est directement liée à l'acquisition d'informations.

Par exemple, si la fonctionnalité X a des informations mutuelles élevées avec la cible Y, alors savoir X réduit considérablement l'incertitude au sujet de Y. C'est exactement la réduction de l'entropie obtenue en se fractionnant sur X. Les bibliothèques comme scikit-learn fournissent et .

Limites des arbres décisionnels fondés sur l'entropie

Malgré leur pouvoir, les arbres de décision construits avec de l'entropie présentent quelques inconvénients:

  • Instabilité : De petites variations de séries de données peuvent modifier radicalement la structure de l'arbre.
  • Bias vers des fonctionnalités avec de nombreux niveaux: L'information gagne favorise des fonctionnalités de haute cardinalité.
  • Poor manipulation de la structure additive: Les arbres sont des modèles à constantes à la pièce, donc ils peinent à apprendre les relations linéaires.
  • Nature grêle: L'algorithme fait des scissions localement optimales, qui peuvent ne pas être globalement optimales.

En pratique, combiner des arbres de décision basés sur l'entropie avec des méthodes d'accordage hyperparamétrique et d'ensemble appropriées donne des modèles robustes pour de nombreux ensembles de données tabulaires.

Conclusion : L'entropie comme fondation pour des fractionnements éclairés

Entropy fournit une façon théorique et informative d'évaluer la qualité d'une scission lors de la construction d'un arbre de décision. En mesurant le désordre dans un ensemble de données et en cherchant à le réduire à chaque étape, nous pouvons construire des arbres qui divisent efficacement et précisément l'espace de la fonctionnalité. Que vous soyez un apprentissage étudiant machine ou un praticien déployant des modèles, comprendre l'entropie approfondit votre compréhension de la façon dont les arbres de décision -pensez.

Lorsque vous appliquez des arbres de décision, rappelez-vous que l'entropie est un outil — pas une fin. Combinez-le avec des techniques de validation, de taille et d'ensemble appropriées pour libérer tout son potentiel. Et si vous gérez des pipelines de données pour l'apprentissage automatique, des outils comme Directus peuvent vous aider à collecter, organiser et servir les ensembles de données de haute qualité dont dépendent les arbres de décision.