Les algorithmes ID3 et C4.5 sont deux algorithmes utilisés en apprentissage automatique (machine learning) pour la construction de modèles de classification. Ces algorithmes sont largement utilisés dans le domaine de l'intelligence artificielle et sont considérés comme des références dans le domaine de la classification.
1. Algorithme ID3
L'algorithme ID3 (Iterative Dichotomiser 3) a été développé par Ross Quinlan en 1986. Il est utilisé pour construire un arbre de décision à partir d'un ensemble de données d'entrainement. L'objectif de l'algorithme ID3 est de trouver l'attribut qui divise le mieux les données en classes homogènes.
Définition
Attribut discriminant
Dans l'algorithme ID3, l'attribut discriminant est choisi en utilisant une mesure de gain d'information, généralement l'entropie ou l'indice de Gini. L'attribut qui maximise le gain d'information est sélectionné comme attribut discriminant.
L'algorithme ID3 utilise une approche récursive pour construire l'arbre de décision. À chaque étape, l'algorithme sélectionne l'attribut discriminant et divise les données d'entrainement en sous-ensembles en fonction de la valeur de cet attribut. Le processus est répété jusqu'à ce que toutes les données soient parfaitement classifiées ou que tous les attributs aient été utilisés.
Définition
Arbre de décision
L'arbre de décision construit par l'algorithme ID3 est un modèle de classification composé de nœuds internes et de feuilles. Chaque nœud interne correspond à un attribut discriminant et chaque feuille correspond à une classe ou à une décision. L'arbre de décision permet de classer de nouvelles instances en suivant le chemin approprié dans l'arbre jusqu'à atteindre une feuille.
2. Algorithme C4.5
L'algorithme C4.5 a été développé par Ross Quinlan en 1993 comme une amélioration de l'algorithme ID3. C4.5 est également utilisé pour construire des arbres de décision mais propose des améliorations par rapport à ID3.
Définition
Gain ratio
L'amélioration principale de l'algorithme C4.5 par rapport à ID3 est l'utilisation d'une mesure de gain d'information normalisée appelée gain ratio. Le gain ratio prend en compte le nombre de valeurs possibles pour un attribut et prévient le biais en faveur des attributs avec un grand nombre de valeurs.
C4.5 utilise également une approche récursive pour construire l'arbre de décision, en sélectionnant l'attribut discriminant avec le gain ratio le plus élevé à chaque étape.
Une autre amélioration de C4.5 est la gestion des valeurs manquantes. L'algorithme divise les données d'entrainement en fonction de la valeur de l'attribut discriminant, mais peut également gérer les instances avec des valeurs manquantes en les assignant à chaque branche de l'arbre avec une probabilité basée sur la distribution des instances complètes.
3. Résumé
Les algorithmes ID3 et C4.5 sont deux algorithmes utilisés pour construire des arbres de décision dans le domaine de l'apprentissage automatique. L'algorithme ID3 utilise le gain d'information pour choisir l'attribut discriminant, tandis que l'algorithme C4.5 utilise le gain ratio. C4.5 propose également des améliorations telles que la gestion des valeurs manquantes. Ces deux algorithmes sont largement utilisés dans le domaine de l'intelligence artificielle pour la classification de données.
A retenir :
...
