III .2.2 DEFINITION
Un arbre de décision est un outil d'aide à la
décision et à l'exploration de données. Il permet de
modéliser simplement, graphiquement et rapidement un
phénomène mesuré plus ou moins complexe. Sa
lisibilité, sa rapidité d'exécution et le peu
d'hypothèses nécessaires a priori expliquent sa popularité
actuelle.
[50]
III .2.3 CARACTERISTIQUES ET AVANTAGES :
Le caractéristique principale est la lisibilité
du modèle de prédiction que l'arbre de décision fourni, et
de faire faire comprendre ses résultats afin d'emporter
l'adhésion des décideurs.
Cet arbre de décision à également la
capacité de sélectionner automatiquement les variables
discriminantes dans un fichier de données contenant un très grand
nombre de variables potentiellement intéressantes. En ce sens, constitue
aussi une technique exploratoire privilégiée pour
appréhender de gros fichiers de données.
III .2.4 ALGORITHME ID3
L'algorithme ID3 à été
développé à l'origine par ROSS QUINLAN. C'est un
algorithme de classification supervise. C'est-a-dire 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. Permet aussi de générer des arbres de
décisions à partir de données. Imaginons que nous ayons
à notre disposition un ensemble d'enregistrements ayant la même
structure, à savoir un certain nombre de paires attribut ou valeur.
L'un de ses attributs représente la catégorie de
l'enregistrement. Le problème consiste à construire un arbre de
décision qui sur la base de réponses à des questions
posées sur des attributs non cible peut prédire correctement la
valeur de l'attribut cible. Souvent l'attribut cible pend seulement les valeurs
vrai, faux ou échec, succès.
[51]
III .2.5 PRINCIPES
Les principales idées sur lesquels repose ID3 sont les
suivantes : ? Dans l'arbre de décision chaque noeud correspond à
un attribut non cible et chaque arc a une valeur possible de cet attribut. Une
feuille de l'arbre donne la valeur escomptée de l'attribut cible pour
l'enregistrement testé décrit par le chemin de la racine de
l'arbre de décision jusqu'à la feuille. (Définition d'un
arbre de décision).
? Dans l'arbre de décision, à chaque noeud doit
être associé l'attribut non cible qui apporte le plus
d'information par rapport aux autres attributs non encore utilisés dans
le chemin depuis la racine.(Critère d'un bon arbre de décision)
.
? L'entropie est utilisée pour mesurer la
quantité d'information apportée par un noeud.( cette notion a
été introduite par Claude Shannon lors de ses recherches
concernant la théorie de l'information qui sert de base à
énormément de méthodes du datamining.
Algorithme
Entrées : ensemble d'attributs A; échantillon E;
classe c
Début
Initialiser à l'arbre vide;
Si tous les exemples de E ont la même classe c
Alors étiqueter la racine par c;
Sinon si l'ensemble des attributs A est vide
Alors étiqueter la racine par la classe majoritaire dans
E;
Si non soit a le meilleur attribut choisi dans A;
Étiqueter la racine par a;
Pour toute valeur v de a
Construire une branche étiquetée par v;
Soit Eav l'ensemble des exemples tels que e(a) = v;
ajouter l'arbre construit par ID3(A-{a}, Eav, c);
[52]
Fin pour Fin sinon
Fin sinon
Retourner racine;
Fin
| 
