Élagage de l'arbre de décision

L'élagage est une technique de compression des données utilisée dans les algorithmes d'apprentissage automatique et de recherche , qui réduit la taille des arbres de décision en supprimant les sections de l'arbre qui ne sont pas critiques et redondantes pour classer les instances. L'élagage réduit la complexité du classificateur final et améliore donc la précision prédictive en réduisant le surajustement .

L'une des questions qui se pose dans un algorithme d'arbre de décision est la taille optimale de l'arbre final. Un arbre trop grand risque de suradapter les données d'apprentissage et de mal généraliser à de nouveaux échantillons. Un petit arbre peut ne pas capturer d'informations structurelles importantes sur l'espace d'échantillonnage. Cependant, il est difficile de dire quand un algorithme d'arbre doit s'arrêter car il est impossible de dire si l'ajout d'un seul nœud supplémentaire réduira considérablement l'erreur. Ce problème est connu sous le nom d' effet d'horizon . Une stratégie courante consiste à développer l'arbre jusqu'à ce que chaque nœud contienne un petit nombre d'instances, puis à utiliser l'élagage pour supprimer les nœuds qui ne fournissent pas d'informations supplémentaires.

L'élagage doit réduire la taille d'un arbre d'apprentissage sans réduire la précision prédictive telle que mesurée par un ensemble de validation croisée . Il existe de nombreuses techniques d'élagage d'arbre qui diffèrent selon la mesure utilisée pour optimiser les performances.

Les processus de taille peuvent être divisés en deux types (pré- et post-taille).

Les procédures de pré-élagage empêchent une induction complète de l'ensemble d'apprentissage en remplaçant un critère stop() dans l'algorithme d'induction (par exemple, profondeur maximale de l'arbre ou gain d'information (Attr)> minGain). Les méthodes de pré-élagage sont considérées comme plus efficaces car elles n'induisent pas un ensemble entier, mais plutôt que les arbres restent petits dès le départ. Les méthodes de pré-élagage partagent un problème commun, l'effet d'horizon. Cela doit être compris comme la fin prématurée non désirée de l'induction par le critère stop().

L'élagage postérieur (ou élagage simple) est la méthode la plus courante pour simplifier les arbres. Ici, les nœuds et les sous-arbres sont remplacés par des feuilles pour réduire la complexité. L'élagage peut non seulement réduire considérablement la taille, mais également améliorer la précision de la classification des objets invisibles. Il se peut que la précision de l'affectation sur l'ensemble de train se détériore, mais la précision des propriétés de classification de l'arbre augmente globalement.

Les procédures sont différenciées en fonction de leur approche dans l'arbre (top-down ou bottom-up).

Ces procédures démarrent au dernier nœud de l'arbre (le point le plus bas). Elles déterminent ensuite de manière récursive et ascendante la pertinence de chaque nœud individuel. Si la pertinence pour la classification n'est pas donnée, le nœud est supprimé ou remplacé par une feuille. L'avantage est qu'aucun sous-arbre pertinent ne peut être perdu avec cette méthode. Ces méthodes comprennent l'élagage à erreur réduite (REP), l'élagage à coût complexe minimal (MCCP) ou l'élagage à erreur minimale (MEP).

Contrairement à la méthode ascendante, cette méthode démarre à la racine de l'arbre. En suivant la structure ci-dessous, un contrôle de pertinence est effectué qui décide si un nœud est pertinent pour la classification de tous les n éléments ou non. En élaguant l'arbre au niveau d'un nœud interne, il peut arriver qu'un sous-arbre entier (indépendamment de sa pertinence) soit supprimé. L'un de ces représentants est l'élagage des erreurs pessimistes (PEP), qui donne d'assez bons résultats avec des éléments invisibles.

L'une des formes les plus simples d'élagage est l'élagage à erreur réduite. En commençant par les feuilles, chaque nœud est remplacé par sa classe la plus populaire. Si la précision de la prédiction n'est pas affectée, le changement est conservé. Bien qu'un peu naïf, l'élagage à erreur réduite présente l'avantage de la simplicité et de la rapidité .

L'élagage de la complexité des coûts génère une série d'arbres ⁠ ⁠ où ⁠ ⁠ est l'arbre initial et ⁠ ⁠ est la racine seule. À l'étape ⁠ ⁠ , l'arbre est créé en supprimant un sous-arbre de l'arbre ⁠ ⁠ et en le remplaçant par un nœud feuille avec une valeur choisie comme dans l'algorithme de construction d'arbre. Le sous-arbre qui est supprimé est choisi comme suit :

1. Définissez le taux d’erreur de l’arbre ⁠ ⁠ sur l’ensemble de données ⁠ ⁠ comme ⁠ ⁠ .
2. Le sous-arbre qui est minimisé est choisi pour être supprimé.

La fonction ⁠ ⁠ définit l'arbre obtenu en élaguant les sous-arbres ⁠ ⁠ de l'arbre ⁠ ⁠ . Une fois la série d'arbres créée, le meilleur arbre est choisi par précision généralisée telle que mesurée par un ensemble d'apprentissage ou une validation croisée.

L'élagage peut être appliqué dans un schéma de compression d'un algorithme d'apprentissage pour supprimer les détails redondants sans compromettre les performances du modèle. Dans les réseaux neuronaux, l'élagage supprime des neurones entiers ou des couches de neurones.