Algorithme ID3

Infos
L’algorithme ID3 a été développé à l’origine par J. Ross Quinlan. Il a tout d’abord été publié dans le livre ‘’Machine Learning’’ en 1986. C’est un algorithme de classification supervisé, c’est-à-dire qu'il se base sur des exemples déjà classés dans un ensemble de classes pour déterminer un modèle de classification. Le modèle que produit ID3 est un arbre de décision. Cet arbre servira à classer de nouveaux échantillons. L'algorithme C4.5 est
Algorithme ID3

L’algorithme ID3 a été développé à l’origine par J. Ross Quinlan. Il a tout d’abord été publié dans le livre ‘’Machine Learning’’ en 1986. C’est un algorithme de classification supervisé, c’est-à-dire qu'il se base sur des exemples déjà classés dans un ensemble de classes pour déterminer un modèle de classification. Le modèle que produit ID3 est un arbre de décision. Cet arbre servira à classer de nouveaux échantillons. L'algorithme C4.5 est une amélioration d'ID3, notamment du point de vue de la facilité d'implémentation. =Principe général= Chaque exemple en entrée est constitué d'une liste d'attributs. Un de ces attributs est l’attribut « cible » et les autres sont les attributs « non cibles ». En fait l’arbre de décision va permettre de prédire la valeur de l’attribut « cible » à partir des autres valeurs. Bien entendu, la qualité de la prédiction dépend des exemples : plus ils sont variés et nombreux, plus la classification de nouveaux cas sera fiable. Un arbre de décision permet de remplacer un expert humain dont il modélise le cheminement intellectuel. A chaque nœud correspond une question sur un attribut non cible. Chaque valeur différente de cet attribut sera associée à un arc ayant pour origine ce nœud. Les feuilles de l'arbre, quant à elles, indiquent la valeur prévue pour l’attribut cible relativement aux enregistrements contenus par la branche (indiqués par les différents arcs) reliant la racine à cette feuille. ID3 construit l'arbre de décision récursivement. À chaque étape de la récursion, il calcule parmi les attributs restant pour la branche en cours, celui qui maximisera le gain d'information. C’est-à-dire l'attribut qui permettra le plus facilement de classer les exemples à ce niveau de cette branche de l'arbre. On appelle ce calcul l'entropie de Shannon dont voici la formule utilisée : I_(i) = - \sum^_ f (i, j) \log f (i, j) =Algorithme= fonction ID3(exemples, attributCible, attributsNonCibles) si exemples est vide alors /
- Nœud terminal
-/ retourner un nœud Erreur sinon si attributsNonCibles est vide alors /
- Nœud terminal
-/ retourner un nœud ayant la valeur la plus représentée pour attributCible sinon si tous les exemples ont la même valeur pour attributCible alors /
- Nœud terminal
-/ retourner un nœud ayant cette valeur sinon /
- Nœud intermédiaire
-/ attributSélectionné = attribut maximisant le gain d'information parmi attributsNonCibles attributsNonCiblesRestants = suppressionListe(attributsNonCibles, attributSélectionné) nouveauNœud = nœud étiqueté avec attributSélectionné pour chaque valeur de attributSélectionné faire exemplesFiltrés = filtreExemplesAyantValeurPourAttribut(exemples, attributSélectionné, valeur) nouveauNœud->fils(valeur) = ID3(exemplesFiltrés, attributCible, attributsNonCiblesRestants) finpour retourner nouveauNœud =Références= =Voir aussi=
-Arbre de décision Catégorie:Algorithme Catégorie:Intelligence artificielle de:ID3 el:Αλγόριθμος ID3 en:ID3 algorithm es:Algoritmo id3 ja:ID3
Sujets connexes
Algorithme C4.5   Arbre de décision   Entropie de Shannon  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^