Plan

• Introduction à la science des données

• Notions d’apprentissage statistique
Apprentissage automatique • Bayes Naïf
• Arbres de décision
Lecture 3: Arbres de décision
• Réseaux de neurones artificiels
Département Génie Informatique, FST de Tanger • Labs + 2 Devoirs (Python)
M. AIT KBIR • 1 CC

2018-2019 M. AIT KBIR (MST MBD/SIM) 2

Arbres de décision : Exemples Entropie: Définition

Le terme entropie caractérise le degré de désorganisation, ou

d'imprédictibilité du contenu en information d'un système.

Utile dans :
• Codage de l’information
• Physique statistique
• Apprentissage automatique

2018-2019 M. AIT KBIR (MST MBD/SIM) 3 2018-2019 M. AIT KBIR (MST MBD/SIM) 4
 Entropie Entropie : codage de l’information

• Entropie élevée : variable aléatoire est issu d’une distribution plate

• Entropie basse : variable aléatoire issu d’une distribution non plate
(avec des vallées et des pics)

2018-2019 M. AIT KBIR (MST MBD/SIM) 5 2018-2019 M. AIT KBIR (MST MBD/SIM) 6

Entropie : codage de l’information Arbre décision: diviser pour régner

Les états sont équiprobables: Pour créer un arbre de décision, on doit prendre
une décision sur l’ensemble de données pour
savoir la caractéristique à utiliser pour fractionner
les données. Ensuite, diviser le jeu de données en
sous-ensembles. On parcourt ensuite les branches
à partir du nœud créé. Si les données sur une
Longueur moyenne du code: sous-branche appartiennent à la même classe, on
a pas besoin de continuer à les diviser. Si les
données ne sont pas identiques, on doit répéter le
processus de division sur ce sous-ensemble.

2018-2019 M. AIT KBIR (MST MBD/SIM) 7 2018-2019 M. AIT KBIR (MST MBD/SIM) 8
 Algorithme : ID3 (Iterative Dichotomiser 3)
Mesure de d’information Développé en 1986 par Ross Quinlan

Le changement d'information avant et après la

division est connu sous le nom de gain
d’information. On fractionne les données en
choisissant chaque fois la division qui donne le
gain d’information le plus élevé.

2018-2019 M. AIT KBIR (MST MBD/SIM) 9 2018-2019 M. AIT KBIR (MST MBD/SIM) 10

Detectlanguage

Algorithme ID3: Stratégie de croissance de l’arbre

Gain d’information
• Règle de fractionnement: qui détermine le seuil de
décision sur les données d'un nœud.
• Condition d’arrêt: qui détermine la fin de la
récursivité. C'est la règle qui détermine si un nœud
est feuille ou non. Par exemple: tous les exemples
appartiennent à la même classe, Il ne reste aucun
attribut pour plus de fractionnement ou il n'y a plus
d’exemples
• Règle d'étiquetage: qui attribue une étiquette de
classe à chaque nœud feuille, le vote à la majorité
est utilisé pour classer la feuille.

2018-2019 M. AIT KBIR (MST MBD/SIM) 11 2018-2019 M. AIT KBIR (MST MBD/SIM) 12
 Gain d’information (Exemple : jouer au tennis)
Entropie : Division
Day Outlook Temperature Humidity Wind PlayTennis

1 sunny hot high weak no

2 sunny hot high strong no
3 overcast hot high weak yes
4 rain mild high weak yes
5 rain cool normal weak yes
6 rain cool normal strong no
7 overcast cool normal strong yes
8 sunny mild high weak no
9 sunny cool normal weak yes
10 rain mild normal weak yes
11 sunny mild normal strong yes
12 overcast mild high strong yes
Si on transfert l’unique (+) du deuxième 13 overcast hot normal weak yes
ensemble sur le premier: 14 rain mild high strong no
GI = 0.99-0.45=0,54 > 0,38

2018-2019 M. AIT KBIR (MST MBD/SIM) 13 2018-2019 M. AIT KBIR (MST MBD/SIM) 14

Gain d’information (Exemple : jouer au tennis) Gain d’information (Exemple : jouer au tennis)

2018-2019 M. AIT KBIR (MST MBD/SIM) 15 2018-2019 M. AIT KBIR (MST MBD/SIM) 16
 Gain d’information (Exemple : jouer au tennis)
Indice Gini : mesure d’impureté

Le coefficient de Gini est une mesure statistique qui

permet de mesurer des disparités dans une population. Si
S contient des exemples issus de C classes
C
:
Gini ( S ) = 1 − ∑ p ( w j ) 2
j =1

Lors de la construction d’un arbre de décision, il s’agit de

fractionner par rapport à la caractéristique avec la valeur
minimal de l’indice. j 2
1 C Mi ( S im )
Gini ( x i ) = 1 −
S
∑∑
j =1 m =1 S im

2018-2019 M. AIT KBIR (MST MBD/SIM) 17 2018-2019 M. AIT KBIR (MST MBD/SIM) 18

Arbres de décision Arbres de décision: problèmes

Avantages: • Choix d’une mesure qui permet d’évaluer
• Les arbres peuvent gérer les espaces de grande dimensionnalité
aisément. objectivement la qualité d’un fractionnement et ainsi
• Vu la nature hiérarchique de l’algorithme, le calcul des probabilité de sélectionner le meilleur parmi les descripteurs
est extrêmement rapide.
• Les arbres peuvent traiter des données caractéristiques discrètes
candidats par rapport à un nœud.
aussi bien que continues. • Choix d’un ou plusieurs seuil pour les attributs
Inconvénients: continus et la mise en concurrence de ces derniers et
• ID3 n’est pas adapté aux attributs continus
• Souffre de quelques problèmes comme le sur-apprentissage, il peut
les attributs discrets.
donne comme résultat un optimum local et non pas la solution • Utilisation des règles efficaces pour définir la taille
globale.
• L’arbre peut nécessiter l’élagage
adéquate de l’arbre de décision lorsqu’un
Autres algorithmes adaptés aux caractéristiques continues: C4.5 partitionnement pur des observations de la base n’est
et C5.0 (successeurs de ID3) et CART (Classification and pas possible.
Regression Trees). • Utilisation des règles de décision optimales lorsque
qu’une feuille contient des exemples avec des
2018-2019 M. AIT KBIR (MST MBD/SIM)
19 classes différentes.M. AIT KBIR (MST MBD/SIM)
2018-2019
20
 Arbres de décision (C 4.5), R. Quinlan, 1993 Arbres de décision : CART
C4.5 est une amélioration de ID3 qui permet de traiter les attributs numériques (Classification and Regression Trees), L. Breiman et al., 1984
continus, par le partitionnement de ces derniers en un ensemble d’intervalles.
L’arbre générée est formulée sous forme d’un nombre de règles SI-ALORS. Cette CART supporte des valeurs numériques continues
technique fractionne par rapport à xi qui maximise le rapport de gain suivant:
pour l’attribut cible (Régression), au lieu d’avoir
comme valeurs possibles un ensemble d’étiquettes.
CART impose une construction d’arbres binaires, les
valeurs des attributs sont regroupées en deux sous-
ensembles de manière à avoir le gain d’information
maximum à chaque nœud. Le critère Gini est utilisé
Il s’agit de trier les valeurs de l’attribut, itérer à travers les seuils, moyenne des pour le fractionnement.
deux valeurs qui correspondent au changement de classe, et séparer le jeu de
données en deux ensembles. Puis calculer le rapport de gain pour chaque valeur Temps de construction de l’arbre est élevé, surtout
du seuil, pour garder celle qui correspond au maximum.
lorsque la base des exemples est de grande taille.
Mais, on obtient un arbre avec des bonnes
performances.
21 22
2018-2019 M. AIT KBIR (MST MBD/SIM) 2018-2019 M. AIT KBIR (MST MBD/SIM)

Arbres de décision (CHAID)

(CHi-squared Automatic Interaction Detection) – G, Kass, 1980

23
2018-2019 M. AIT KBIR (MST MBD/SIM)