Algorithme C4.5 pour reconstruire les arbres de décision

L'algorithme d'arbre de décision C4.5 est une version améliorée de l'algorithme ID3, qui construit des arbres de décision basés sur l'entropie de l'information et le gain d'information. Il est largement utilisé dans les problèmes de classification et de régression et constitue l’un des algorithmes les plus couramment utilisés dans les domaines de l’apprentissage automatique et de l’exploration de données.

L'idée principale de l'algorithme C4.5 est de maximiser le gain d'informations en divisant l'ensemble de données. Cet algorithme adopte une méthode de fractionnement récursive descendante, en partant du nœud racine et en sélectionnant une fonctionnalité optimale pour le fractionnement en fonction de l'ensemble de données existant. En calculant le gain d'informations de chaque caractéristique, la caractéristique présentant le gain d'informations le plus important est sélectionnée comme caractéristique de division, et l'ensemble de données est divisé en plusieurs sous-ensembles en fonction de la valeur de la caractéristique. Chaque sous-ensemble correspond à un sous-arbre, puis la même opération de division est effectuée sur chaque sous-ensemble de manière récursive jusqu'à ce que tous les nœuds feuilles appartiennent à la même catégorie ou qu'une condition d'arrêt prédéterminée soit atteinte. L'arbre de décision final peut être utilisé pour classer de nouveaux échantillons ou prédire la régression. Les nœuds de l'arbre de décision représentent une caractéristique, les bords représentent la valeur de la caractéristique et les nœuds feuilles représentent la catégorie de l'échantillon ou la valeur prédite. En suivant le chemin du nœud racine au nœud feuille de l'arbre de décision, la catégorie à laquelle appartient l'échantillon ou la valeur prédite peut être déterminée en fonction des valeurs caractéristiques de l'échantillon. L’avantage de l’algorithme C4.5 est qu’il peut gérer des caractéristiques discrètes et continues et qu’il présente une bonne interprétabilité et compréhensibilité. Cependant, l'algorithme C4.5 rendra l'arbre de décision trop complexe lorsqu'il existe de nombreuses valeurs de caractéristiques, et il est sujet à des problèmes de surajustement. Afin de résoudre ce problème, la prise de décision peut être optimisée grâce à des méthodes telles que l'élagage. L'algorithme C4.5 introduit le taux de gain d'informations lors de la sélection des fonctionnalités. Par rapport au gain d'informations de l'algorithme ID3, il prend en compte l'entropie de l'algorithme. fonctionnalité elle-même. En divisant le gain d'informations par l'entropie de la caractéristique, le taux de gain d'informations peut éliminer l'influence de la caractéristique elle-même et mesurer plus précisément la contribution de la caractéristique à la classification. De plus, l'algorithme C4.5 applique également une stratégie d'élagage pour éviter que des problèmes de surajustement ne surviennent.

Les étapes spécifiques de l'algorithme C4.5 sont les suivantes :

Dans l'algorithme C4.5, afin de sélectionner les caractéristiques optimales pour le fractionnement, le taux de gain d'information est utilisé pour évaluer l'importance de la caractéristiques. Le rapport de gain d'informations est défini comme le gain d'informations divisé par l'entropie des caractéristiques, et sa formule de calcul est GainRatio(D,A)=Gain(D,A)/SplitInformation(D,A). En calculant le taux de gain d'informations de chaque fonctionnalité, la fonctionnalité ayant la valeur la plus élevée peut être sélectionnée comme fonctionnalité de fractionnement optimale. Le but est de prendre en compte l'influence de l'entropie des caractéristiques pour surmonter le biais du gain d'information et ainsi mieux sélectionner les caractéristiques à diviser.

où Gain(D,A) représente le gain d'informations obtenu en utilisant la fonctionnalité A pour diviser l'ensemble de données D, et SplitInformation(D,A) représente les informations requises pour utiliser la fonctionnalité A pour diviser l'ensemble de données D, c'est-à-dire la fonctionnalité L'entropie de A. L'algorithme C4.5 sélectionne la fonctionnalité avec le taux de gain d'informations le plus élevé comme fonctionnalité divisée du nœud actuel.

2. Divisez l'ensemble de données en plusieurs sous-ensembles en fonction des valeurs des caractéristiques sélectionnées. Pour les entités discrètes, chaque valeur correspond à un sous-ensemble ; pour les entités continues, la méthode de dichotomie ou multi-sections peut être utilisée pour diviser afin d'obtenir plusieurs sous-ensembles.

3. Effectuez de manière récursive la même opération de fractionnement sur chaque sous-ensemble jusqu'à ce que la condition d'arrêt soit remplie. La condition d'arrêt peut être l'atteinte d'une profondeur d'arbre prédéterminée, d'un nombre de nœuds feuilles ou d'une précision de classification, etc.

4. Effectuer l'opération d'élagage. L'algorithme C4.5 utilise la méthode de post-élagage pour élaguer l'arbre de décision complet après l'avoir obtenu afin de supprimer certains nœuds divisés inutiles, améliorant ainsi la capacité de généralisation du modèle.

Et l'algorithme C4.5 peut également gérer le problème des valeurs manquantes. Il utilise la méthode de vote majoritaire pour résoudre le traitement des valeurs manquantes, c'est-à-dire que les valeurs manquantes sont classées dans la catégorie avec le plus d'occurrences. .

L'algorithme C4.5 présente les avantages suivants :

peut gérer à la fois des fonctionnalités discrètes et continues.

Utilisez le taux de gain d'informations au lieu du gain d'informations pour mieux gérer le problème de sélection des fonctionnalités.

• Adoptez une méthode post-taille pour éviter un ajustement excessif.
• Les arbres de décision sont faciles à interpréter et à comprendre et peuvent être utilisés pour la visualisation.
• L'algorithme C4.5 présente également quelques défauts :

Pour les données clairsemées de grande dimension, les arbres de décision sont sujets au surajustement.

Les arbres de décision sont sensibles au bruit et aux valeurs aberrantes.

• L'effet de classification des arbres de décision n'est pas nécessairement meilleur que celui des autres algorithmes. Il est nécessaire de choisir l'algorithme approprié en fonction du scénario d'application spécifique.
• En bref, l'algorithme C4.5 est un algorithme d'arbre de décision couramment utilisé. Il utilise l'entropie de l'information et le gain d'information pour sélectionner les meilleurs attributs de partition. Il peut gérer les problèmes multi-catégories et de valeurs manquantes et a une précision de classification élevée. . efficacité et interprétabilité, et est largement utilisé dans les domaines de l’apprentissage automatique et de l’exploration de données.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!