Algorithme ID3

L’algorithme ID3 a été développé à l’origine par 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.

Sommaire

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 ». On appelle aussi cette "cible" la "classe". 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. À 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_{E}(i) = - \sum^{m}_{j=1}  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

  • J. Ross Quinlan, Machine Learning, 1986, « Induction of decision trees », p. 81-106

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme ID3 de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Id3 —  Pour l’article homonyme, voir Algorithme ID3.  ID3 est le nom des métadonnées pouvant être insérées dans un fichier audio comme MP3. Ces métadonnées permettent d avoir des informations sur le contenu du fichier comme le titre, le nom… …   Wikipédia en Français

  • ID3 —  Pour l’article homonyme, voir Algorithme ID3.  ID3 est le nom des métadonnées pouvant être insérées dans un fichier audio comme MP3. Ces métadonnées permettent d avoir des informations sur le contenu du fichier comme le titre, le nom… …   Wikipédia en Français

  • Algorithme C4.5 — Pour les articles homonymes, voir C4. L’algorithme C4.5 est un algorithme de classification supervisé, publié par Ross Quinlan. Il est basé sur l algorithme ID3 auquel il apporte plusieurs améliorations. C4.5 À partir d un échantillon d… …   Wikipédia en Français

  • Algorithme CART — Pour les articles homonymes, voir Cart (homonymie). L’algorithme CART dont l’acronyme signifie « Classification And Regression Trees », s’attelle à construire un arbre de décision en classifiant un ensemble d’enregistrements. Cet arbre… …   Wikipédia en Français

  • ID3v1 — ID3  Pour l’article homonyme, voir Algorithme ID3.  ID3 est le nom des métadonnées pouvant être insérées dans un fichier audio comme MP3. Ces métadonnées permettent d avoir des informations sur le contenu du fichier comme le titre, le… …   Wikipédia en Français

  • ID3v2 — ID3  Pour l’article homonyme, voir Algorithme ID3.  ID3 est le nom des métadonnées pouvant être insérées dans un fichier audio comme MP3. Ces métadonnées permettent d avoir des informations sur le contenu du fichier comme le titre, le… …   Wikipédia en Français

  • C4.5 — Algorithme C4.5 Pour les articles homonymes, voir C4. L’algorithme C4.5 est un algorithme de classification supervisé, publié par Ross Quinlan. Il est basé sur l algorithme ID3 auquel il apporte plusieurs améliorations. A partir d un échantillon… …   Wikipédia en Français

  • Glossaire du data mining — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • DiscId — Le DiscId est un identifiant calculable pour tout CD Audio. Cet identifiant est un nombre dont la valeur dépend du nombre de pistes sur le CD, et de la position de chaque piste. Lors de l extraction des pistes audio numériques d un CD audio, il… …   Wikipédia en Français

  • MPEG-1/2 Audio Layer 3 — « MP3 » redirige ici. Pour l’album de M. Pokora, voir MP3 (album). Le MPEG 1/2 Audio Layer 3, plus connu sous son abréviation de MP3, est la spécification sonore du standard MPEG 1/MPEG 2, du Moving Picture Experts Group (MPEG). C est… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”