III .2.4 ALGORITHME ID3 [4, 13]
L'algorithme ID3 à été
développé à l'origine par ROSS QUINLAN. C'est un
algorithme de classification supervisé. 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. Il 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.
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;
Mémoire MANKAMBA YANKUMBA Jean Luc UKA 2015 - 2016
|
33
|
MISE EN PLACE D'UN SYSTEME DECISIONNEL BASE SUR LE DATA MART ET
L'ARBRE DE DECISION POUR LE RECRUTEMENT DU PERSONNEL A LA DGR KOC
|
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);
Fin pour Fin sinon
Fin sinon
Retourner racine;
Fin
| 
