Algorithme ID3
ID3 (Dichotomiser itératif 3) est un algorithme employé pour produire d'un arbre de décision .
L'algorithme est basé sur le rasoir d'Occam de : il préfère de plus petits arbres de décision (des théories plus simples) au-dessus de les plus grandes. Cependant, il ne produit pas toujours le plus petit arbre, et est donc un heuristique. Le rasoir d'Occam est formalisé using le concept de l'entropie de l'information de :
L'algorithme ID3 peut être récapitulé comme suit :
prennent tous les attributs inutilisés et comptent leur entropie au sujet de
Une explication de l'exécution d'ID3 peut être trouvée à l'algorithme du C4.5, qui est une version prolongée d'ID3.
Algorithme
L'algorithme réel est comme suit :(Exemples, Target_Attribute, attributs)
- ID3 Créer un noeud de racine pour l'arbre
Si tous les exemples sont positifs, renvoyer la racine d'arbre de simple-noeud, avec l'étiquette = +.
Si tous les exemples sont négatifs, renvoyer la racine d'arbre de simple-noeud, avec l'étiquette = -.
Si le nombre d'attributs de prévision est vide, alors renvoyer la racine d'arbre de noeud simple, avec l'étiquette = la plupart de valeur commune de l'attribut de cible dans les exemples.
Autrement commencer
Attribut d'arbre de décision pour la racine = l'A.
Pour chaque valeur possible, , d'A,
Ajouter une nouvelle branche d'arbre au-dessous de la racine, correspondant à l'essai A = .
Laisser les exemples (), être le sous-ensemble d'exemples qui ont la valeur pour A
Si les exemples () est vide
Alors au-dessous de cette nouvelle branche ajouter un noeud de feuille avec l'étiquette = la plupart de valeur à atteindre commune dans les exemples
Autrement au-dessous de cette nouvelle branche ajouter le sous-arbre ID3 (exemples (), Target_Attribute, attributs - {A})
Racine de retour
.
| Random links: | Extended Binary Coded Decimal Interchange Code | Transfert de chaleur | Patinage de vitesse aux 1928 Jeux Olympiques d'hiver | Saga illimitée | Lullingstone | Algoritmo_ID3 |