III .2.2 EXEMPLE PRATIQUE
Pour introduire et exécuter "à la main"
l'algorithme ID3 nous allons tout d'abord considérer l'exemple
ci-dessous: Une entreprise possède les informations suivantes sur ses
clients et souhaite pouvoir prédire à l'avenir si un client
donné effectue des consultations de compte sur Internet.
EXEMPLE PRATIQUE D'UN ALGORITHME ID3
|
client
|
Moyenne des montants
|
Age
|
Lieu de Résidence
|
Etudes supérieures
|
Consultation par internet
|
|
1
|
Moyen
|
Moyen
|
Village
|
Oui
|
oui
|
|
2
|
Elevé
|
Moyen
|
Bourg
|
Non
|
non
|
|
3
|
Faible
|
Age
|
Bourg
|
Non
|
non
|
|
4
|
Faible
|
Moyen
|
Bourg
|
Oui
|
oui
|
|
5
|
Moyen
|
Jeune
|
Ville
|
Oui
|
Oui
|
|
6
|
Elevé
|
Agé
|
Ville
|
Oui
|
non
|
|
7
|
Moyen
|
Agé
|
Ville
|
Oui
|
non
|
|
8
|
Faible
|
Moyen
|
Village
|
Non
|
non
|
Tableau III 3:exemples pratiques
Ici, on voit bien que la procédure de classification
à trouver, qui à partir de la description d'un client, nous
indique si le client effectue la consultation de ses comptes par Internet,
c'est-à-dire la classe associée au client.
- le premier client est décrit par (M : moyen, Age :
moyen, Résidence : village, Etudes : oui) et a pour classe Oui.
Mémoire MANKAMBA YANKUMBA Jean Luc UKA 2015 - 2016
|
34
|
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
|
- le deuxième client est décrit par (M :
élevé, Age : moyen, Résidence : bourg, Etudes : non) et a
pour classe Non.
Pour cela, nous allons construire un arbre de décision
qui classifie les clients. Les arbres sont construits de façon
descendante. Lorsqu'un test est choisi, on divise l'ensemble d'apprentissage
pour chacune des branches et on
Réapplique récursivement l'algorithme.
H(C[Lieu) = -P (bourg). (P (C[bourg) log (P (C[bourg)) + P (C
[bourg)
Choix du meilleur attribut : Pour cet
algorithme deux mesures existent pour choisir le meilleur attribut : la mesure
d'entropie et la mesure de fréquence:
L'entropie : Le gain (avec pour fonction i
l'entropie) est également appelé l'entropie de Shannon et
peut se réécrire de la manière suivante :
Pour déterminer le premier attribut test (racine de
l'arbre), on recherche l'attribut d'entropie la plus faible. On doit donc
calculer H(C[Solde), H(C[Age), H(C[Lieu), H(C[Etudes), où la classe C
correspond aux personnes qui consultent leurs comptes sur Internet.
H(C[Solde) = -P (faible).(P (C[faible) log(P (C[faible)) + P
(C [faible) log(P (C[faible)))-P (moyen).(P (C[moyen) log(P (C[moyen)) + P
(C[moyen) log(P (C[moyen)))-P (eleve).(P (C[eleve) log(P (C[eleve)) + P
(C[eleve) log(P(C[eleve)))H(C[Solde)
H(C[Solde) = -3/8(1/3.log(1/3) + 2/3.log(2/3)-3/8(2/3.log(2/3) +
1/3.log(1/3)
-2/8(0.log (0) + 1.log(1)
H (C[Solde) = 0.20725
H(C[Age) = -P (jeune).(P (C[jeune) log(P (C[jeune)) + P (C
[jeune) log(P (C[jeune)))-P (moyen).(P (C[moyen) log(P (C[moyen)) + P (C
[moyen) log(P (C[moyen)))-P (age).(P (C[age) log(P (C[age)) + P (C[age) log(P
(C[age)))
H(C[Age) = 0.15051
Log (P (C[bourg)))-P (village).(P (C[village) log(P
(C[village)) + P (C [village) log(P (C[village)))-P (ville).(P (C[ville) log(P
(C[ville)) + P (C[ville)
Log (P (C[ville)))
H(C[Lieu) = 0.2825
H(C[Etudes) = -P (oui).(P (C[oui) log(P (C[oui)) + P (C [oui)
log(P (C[oui)))
-P (non).(P (C[non) log(P (C[non)) + P (C[non) log(P (C[non)))
H(C[Etudes) = 0.18275 Le premier attribut est donc l'âge (attribut dont
l'entropie est minimale). On obtient l'arbre suivant :
FIG III 1:Arbre de décision construit à partir de
l'attribut àge
Mémoire MANKAMBA YANKUMBA Jean Luc UKA 2015 - 2016
|
35
|
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
|
Pour la branche correspondant à un âge moyen, on
ne peut pas conclure, on doit donc
recalculer l'entropie sur la partition correspondante.
H(C|Solde) = -P (faible).(P (C|faible) log(P (C|faible)) + P
(C |faible) log(P
(C|faible)))-P (moyen).(P (C|moyen) log(P (C|moyen)) + P
(C|moyen)
Log (P (C|moyen)))-P (eleve). (P (C|eleve) log(P (C|eleve)) +
P (C|eleve) log(P
(C|eleve)))
H(C|Solde) = -2/4(1/2.log(1/2) + 1/2.log(1/2)-1/4(1.log(1) +
0.log(0)
-1/4(0.log (0) + 1.log (1)
H (C|Solde) = 0.15051
H(C|Lieu) = -P (bourg).(P (C|bourg) log(P (C|bourg)) + P (C
|bourg) log(P
(C|bourg)))-P (village).(P (C|village) log(P (C|village)) + P
(C |village) log(P
(C|village)))-P (ville).(P (C|ville) log(P (C|ville)) + P
(C|ville) log(P (C|ville)))
H (C|Lieu) = 0.30103
H (C|Etudes) = -P (oui).(P (C|oui) log(P (C|oui)) + P (C |oui)
log(P (C|oui)))
-P (non). (P (C|non) log(P (C|non)) + P (C|non) log(P
(C|non))) H(C|Etudes) = 0
L'attribut qui a l'entropie la plus faible est « Etudes
».
L'arbre devient alors :
FIG III 2:Arbre de décision finale
L'ensemble des exemples est classé et on constate que sur
cet ensemble d'apprentissage, seuls deux attributs sur les quatre sont
discriminants.
| 
