Chapitre 2 :

Arbres de décision

1
Fouille de données

Cette phase est au coeur du processus ECD.

Trois catégories de méthodes :

● Les techniques de visualisation et de description ;
● Les techniques de classification et de structuration ;
● Les techniques d’explication et de prédiction.

Deux catégories d’apprentissage :

● Apprentissage non-supervisé (Unsupervised
Learning).
● Apprentissage supervisé (Supervised Learning) ;

Procédure obtenue = "classifieur"

2
Classification supervisée

Définition : Classification supervisée

● Processus à deux phases:
1. Apprentissage : construire un modèle (ou classifieur)
qui décrit un ensemble prédéterminé de classes de
données

2.Classement : utiliser le classifieur pour affecter une

classe à un nouvel objet

Principe
● On utilise des données « historiques » ou connues pour
construire un modèle.

● Ce modèle est ensuite utilisé dans le but de classer les

nouvelles observations

3
 Classification supervisée
Exemple introductif: Modèle de prédiction pour le diagnostic
Chaque instance est décrite par un vecteur d’ attributs/valeurs
Toux Fièvre Poids Douleur
Mariem non oui normal gorge
Farid non oui normal abdomen
Salah oui oui maigre aucune
Nizar oui non obese tête

En entrée : un ensemble d’instances et leur classe

(correctement associées par un “professeur” ou “expert”)
Toux Fièvre Poids Douleur Diagnostic
Marie non oui normal gorge rhume
Farid non oui normal abdomen appendicit
..... e

L’algorithme d’apprentissage doit construire un modèle de

prédiction permettant de prédire (ou « deviner ») l’appartenance
d’un individu à une classe en fonction de ses caractéristiques .

4
 Classification supervisée
Apprendre, c'est trouver une fonction F …

 est la population (la « réalité »)

 X
E
E est l ’ensemble des descriptions
des éléments de la population Y F
K
K est l ’ensemble des classes
● le plus souvent construite par
le jugement d’un expert

X:E
X est la fonction qui associe à tout élément de  sa description

Y:K
Y est la fonction qui associe à tout élément de  sa classe

On cherche une fonction F : E  K

5
Classification supervisée

Plusieurs techniques:
Arbres de décision
Réseaux de neurones
Machines à vecteur de support (SVM)
Réseaux bayésiens
Algorithmes génétiques, ….
…

6
Arbres de décision

Principe
● Classer les objets en sous-classes par divisions hiérarchiques
=> construction automatique à partir d ’un échantillon de la base

● Décomposer l’espace des caractéristiques selon la variable la

plus discriminante à chaque étape

Algorithme de base :
1. Choisir le "meilleur" attribut
2. Etendre l'arbre en rajoutant une nouvelle branche pour chaque
valeur de l'attribut
3. Répartir les exemples d'app. sur les feuilles de l'arbre
4. Si aucun exemple n'est mal classé alors
arrêt, sinon repéter les étapes 1-4 pour les
feuilles

7
Arbres de décision

Un nœud

Une branche S
Une feuille v3
v1 v2 v1
Un parcours
v3

v2

8
Arbres de décision

Un nœud

Une branche S
Une feuille v3
v1 v2 v1
Un parcours
v3

v2

9
Arbres de décision

Un nœud

Une branche S
Une feuille v3
v1 v2 v1
Un parcours
v3

v2

10
Arbres de décision

Un nœud

Une branche S
Une feuille v3
v2 v1
Un parcours
V1<Y
v3
v2
Si V3 > X
et V1 < Y
alors <Classe>

•Les arbres de décision sont des classifieurs pour des instances

représentées dans un formalisme attribut/valeur
• Un arbre de décision peut être traduit sous forme de règles de décision

11
 Arbres de décision

On attribut la classe majoritaire à une feuille

Master MRI
Mohamed HAMMAMI 12
 Exemple introductif

N° Outlook Temperature Humidity Windy Play? Objectif :

1 Sunny hot high false No
•Prédire si un match de foot
2 Sunny hot high true No
va avoir lieu ou non.
3 overcast hot high false Yes
4 rain mild high false Yes
5 Rain cool normal false Yes
•Établir une relation entre le
6 rain cool normal true No
fait de jouer ou pas et les
7 overcast cool normal true Yes
conditions météorologiques.
8 sunny mild high false No
9 sunny cool normal false Yes • Variable à expliquer (cible) :
10 rain mild normal false Yes Play (2 classes yes et no).
11 sunny mild normal true Yes
12 overcast mild high true Yes •Variables explicatives :
13 Overcast hot normal false Yes Outlook, Temperature, Humidity
14 rain mild high true No et Windy

13
Comment construire un arbre de décision ?

Deux phases de construction :

●Construction descendante
● Au début, tous les individus de la base d’apprentissage
sont affectés au nœud racine de l’arbre.
● On partitionne de manière récursive en choisissant un
attribut d’éclatement à chaque nœud de l’arbre.

●Construction ascendante (élagage)

● Supprimer les sous-arbres ou les branches, dans une
approche ascendante de façon à améliorer la précision
estimé de nouveaux cas.

14
Nœud racine de l’arbre

N° Outlook Temperature Humidity Windy Play?

1 Sunny hot high false No 9 (64,3%) Yes
2 Sunny hot high true No
3 overcast hot high false Yes 5 (36,7%) No
4 rain mild high false Yes
5 Rain cool normal false Yes
6 rain cool normal true No
Le nœud racine comprend
7 overcast cool normal true Yes
8 sunny mild high false No
tous les individus de la
9 sunny cool normal false Yes base d’apprentissage
10 rain mild normal false Yes partitionnés selon la classe
11 sunny mild normal true Yes à prédire (variable cible).
12 overcast mild high true Yes
13 Overcast hot normal false Yes
14 rain mild high true No

15
Comment éclater le nœud racine ?

9 (64,3%) Yes J3,J4,J5,J7,J9,J10,J11,J12,J13

5 (36,7%) No J1,J2, J6,J8,J14

+ J4,J5,J10
+ J9,J11
- J1,J2,J8 - J6,J14

+ J3,J13,J7,J12
-
16
Comment éclater le nœud racine ?

9 (64,3%) Yes J3,J4,J5,J7,J9,J10,J11,J12,J13

5 (36,7%) No J1,J2, J6,J8,J14

+ J3,J13 + J5,J7,J9
- J1,J2 - J6

+ J4,J10,J11,J13
- J8,J14

17
Comment éclater le nœud racine ?

9 (64,3%) Yes J3,J4,J5,J7,J9,J10,J11,J12,J13

5 (36,7%) No J1,J2, J6,J8,J14

+ J3,J4,J12 + J5,J7,J9,J10,J11,J13
- J1,J2, J8, J14 - J6

18
Comment éclater le nœud racine ?

9 (64,3%) Yes J3,J4,J5,J7,J9,J10,J11,J12,J13

5 (36,7%) No J1,J2, J6,J8,J14

+ J3,J4,J5,J9,10,J13 + J7,J11,J12
- J1,J8 - J2,J6,J14

19
Quelle est la variable à choisir ?

20
Quelle est la variable à choisir ?

Il faut choisir la variable qui :

mène aux sous-ensembles d’individus les plus homogènes

possible en fonction de la classe à prédire.

mène à la création de nœuds fils les plus purs possible.

diminue le plus possible le désordre (l’entropie) de la classe à
prédire dans les nœuds fils.

mène à une nouvelle partition d’individus qui diminue l’entropie

en cours.

21
Quelle est la variable à choisir ?

22
 Deuxième partition de l’arbre

9 (64,3%)
S0 5 (36,7%)

Sunny Overcast Rainy

2 (40%) 4 (100%) 3 (60%)

S1
3 (60%) 0 (0%) 2 (40%)

23
Quel est le nœud à éclater ?

9 (64,3%)

5 (36,7%)

Sunny Overcast Rainy

2 (40%) 4 (100%) 3 (60%)

3 (60%) 0 (0%) 2 (40%)

24
Quelle est la variable à choisir ?

9 (64,3%)

5 (36,7%)

Sunny Overcast Rainy

2 (40%) 4 (100%) 3 (60%)

3 (60%) 0 (0%) 2 (40%)

25
Quelle est la variable à choisir ?

9 (64,3%)

5 (36,7%)

Sunny Overcast Rainy

2 (40%) 4 (100%) 3 (60%)

3 (60%) 0 (0%) 2 (40%)

26
Quelle est la variable à choisir ?

9 (64,3%)

5 (36,7%)

Sunny Overcast Rainy

2 (40%) 4 (100%) 3 (60%)

3 (60%) 0 (0%) 2 (40%)

27
Troisième partition de l’arbre

9 (64,3%)
S0 5 (36,7%)

Sunny Overcast Rainy

2 (40%) 4 (100%) 3 (60%)

S1
3 (60%) 0 (0%) 2 (40%)

High Normal

S2
0 (0%) 2 (100%)

3 (100%) 0 (0%)

28
 Quatrième partition de l’arbre

9 (64,3%)

5 (36,7%)

Sunny Overcast Rainy

2 (40%) 4 (100%) 3 (60%)

3 (60%) 0 (0%) 2 (40%)

High Normal False True

0 (0%) 2 (100%) 3 (100%) 0 (0%)

3 (100%) 0 (0%) 0 (0%) 2 (100%)

S3
29
Mesure d’impureté
Il y a le plus souvent de nombreux arbres de
décision possibles corrects.

Parmi toutes les hypothèses cohérentes possibles,

laquelle faut-il choisir en vue d’une bonne
généralisation ?
●La réponse intuitive ...
... est-elle confirmée par la théorie ?

Impossibilité de procéder par énumération /

évaluation
● 4 attributs & 3 valeurs / attribut : 55296 arbres

Nécessité d’une démarche constructive itérative

30
Mesure d’impureté
Critères de choix de chaque noeud
●La notion de mesure d’impureté

Cette mesure doit :

●être égale à zéro pour un nœud pur de l’arbre de décision
●être croissante en fonction du désordre d’un nœud. Plus le
désordre est grand, plus la valeur de la mesure est grande.
●avoir des valeurs additives pour évaluer le désordre d’une
partition de l’arbre de décision.

 Entropie de Shannon
 Entropie de Boltzmann
 Index de Gini

31
Entropie de Shannon
Shannon en 1949 a proposé une mesure d’entropie
valable pour les distributions discrètes de probabilité.

Elle exprime la quantité d’information, c’est à dire le

nombre de bits nécessaire pour spécifier la distribution

Pour un nœud s, l’entropie d'information est :

où pi est la probabilité de la classe Ci.

32
 Entropie de Shannon
9 9 5 5 9 (64,3%) Yes
I (s0 )   log 2 ( )  log 2 ( )  0,94
14 14 14 14 5 (36,7%) No

Sunny Overcast Rainy

2 (40%) 4 (100%) 3 (60%)

s11 3 (60%) s12 0 (0%) s13 2 (40%)

2 2 3 3
I (s11 )   log 2 ( )  log 2 ( )  0,97
5 5 5 5
4 4 0 0 NB
I (s )   log ( )  log ( )  0 Log2(x) = Log(x) / Log(2)
12 2 2
4 4 4 4

3 3 2
I (s13 )   log 2 ( )  log 2 ( 2 )  0,97
5 5 5 5
33
Entropie de Shannon

Pour une partition S l’entropie d'information est :

I (S)  
Card(s)
I (s)
sS Card()

où I(s) est l’entropie d’information du nœud s

34
Entropie de Shannon

9 (64,3%) Yes
5 (36,7%) No

Sunny Overcast Rainy

2 (40%) 4 (100%) 3 (60%)

S1 3 (60%) 0 (0%) 2 (40%)

5 4 5
I (S)  I (s11 )  I (s12 )  I (s13 )
14 14 14

35
Entropie de Shannon

Critère de partitionnement
● Gain d’incertitude:

(st1)I(St)I(St1)

Objectif : Maximiser le gain d’incertitude

● Un nœud p est terminal si : tous les éléments

associés à ce nœud sont dans une même classe
ou si aucun test n’a pu être séléctionner
36
Entropie de Shannon

Pour les exemples initiaux

I(S) = - 9/14 log2(9/14) - 5/14 log2(5/14)

Entropie de l’arbre associé au test sur Outlook ?

●E(Outlook) = 5/14 I(S11) + 4/14 I(S12) + 5/14 I(S13)
Gain(Outlook) = 0.940 - 0.694 = 0.246 bits

●Gain(Temperature) = 0.029 bits

●Gain(Humidity) = 0.151 bits
●Gain(Windy) = 0.048 bits

Choix de l’attribut Outlook pour le premier test

37
Arbre final obtenu

Outlook

sunny rain
overcast

Humidity Yes Windy

high normal true false

No Yes No Yes

38
Algorithmes d’apprentissage

ID3  [Quinlan,1986]

C4.5  [Quinlan,1993]

CART  [Briemen,1984]

SIPINA [Zighed,1992]

...

39
 ID3, C4.5

 Graphe arborescente n-aire

So
 Passage d’une partition St à St1 exclusivement
par segmentation
10
 Critère de sélection de variable S1 S2
20
ID3: Gain Informationnel
C4.5: Ratio de gain Xj

S3 5 S4 5
 Élagage d’arbre 20 0
ID3: non
Xi
C4.5: oui

1 0 4
10 8 2
S5 S6 S7

40
 ID3, C4.5

- Critère de partitionnement
ID3 ● maximiser le gain d’incertitude entre I(S t) et I(S t+1)
● Utilisation de l’entropie de Shannon:

Exemple:
So
 ( S t 1 )  I ( S 1 )  I ( S 3 , S 4 )

 
10
S1 S2
  1 0 lo g 2 1 0  2 0 lo g 2 2 0 20
30 30 30 30 Xj
- [ - 25 ( 5 log 2 5 + 20 log 2 20) - 5 (5 log 2 5 + 0 log 2 0 )]
30 25 25 25 25 30 5 5 5 5 5 5
S3 S4
20 0
Xi
= 0.9183- 0.7739
= 0.1443 1 0 4
10 8 2
S5 S6 S7

41
ID3, C4.5

C4.5 I ( S j )   ( S t 1 )
 ( S t 1 )  
n kj n kj
  lo g 2
k 1 n j nj

Facteur visant à pénaliser la prolifération des sommets

I (S1)  I (S 3 , S 4 )
 ( S t 1 ) 
Sur le même exemple:
 2 5 log 2 2 5  5 log 2
5
30 30 30 30

( S t  1 )  0.91830.7739
25log2 2 5  5 log2 5
30 30 30 30
= 0.222

42
ID3, C4.5

Conditions d’arrêt:
1. Tous le sommets sont saturés
2. Contrainte d’admissibilité
3. Gain d’information minimal 

43
CART

Segmentation par arbre binaire

Choisie parmi p variable, une bi-partition S1={Sg1,Sd1} So

Soit : ng  card(Sg)
Sg1 Sd1
nd  card(Sd)

nig et nid effectifs de la classe ci

Sg2 Sg2

Critères utilisés
Indice de Gini : M=2
Indicateur de Towing : M>2
Élagage d’arbre
CART: oui

44
CART

Indice de Gini (M=2)

ng m
nig  nig  nd m
 nid 
 
nid
I (s g  sd )   1   1 n 
ng  n g  n
n i1  i1 nd  d 

- Maximiser la variation d’impureté J G (s g  sd )

nig  nid  nig  nid

m

J G (s g  sd )   1   I (sg  sd )
i1 n  n 
Ou encore
n
2
ng nd m  nig 
J G (s g  sd ) 
n n
 
i1  ng
id

nd 

45
CART

Indicateur de Towing (M > 2)

2
 m nig nid 
ng nd

JT (sg  sd ) n n
  
4  i1 ng nd 

On cherche la bipartition qui maximise J T (s g  sd )

46
SIPINA

Avantages SIPINA ?

Exclusivement Divisif
Méthodes arborescentes
Insensibilité à l effectif

Fusion

SIPINA
Sensibilité à l’effectif

47
 SIPINA

Inconvénients des Méthodes Classiques

• Insensibilité à l’effectif Distributions sur les deux classes sont analogues

40 4 Deux figures sont parfaitement décrites par

20 2 Les fréquences conditionnelles

40 0 4 0
0 20 0 2

A B

Il semble clair que les règles issues de A sont

L’effectif en A est dix fois plus grand que B Statistiquement meilleures

48
SIPINA
• Non décroissance du critère

S0 40
20
 (S ) 0

20 20
S={S1,S2} S0 est équivalente à S
10 10

- En terme d’effectif, les règles issues de S1 et S2 devraient être appréciées différemment

- ils couvrent un effectif plus faible devraient être pénalisées

49
SIPINA
Objectif: maximiser (Si)
Ajout d’un parametre λ
● qui contrôle le développement du graphe et pénalise
les nœuds de faible effectif
● de ce fait , favorise les fusions entre les sommets

S0

S1 S2

S3 S4 S5 S6

S9

50
SIPINA

Critère de partitionnement
● maximiser le gain d’incertitude:

  (S I ) I  (S i) I  (S i 1)
● Utilisation de l’entropie de Shannon:
K nj m nij   nij   
I (Si )   

n 
 n  m
lo g 2


n j  m 
j 1 i 1 j

● Utilisation de l’entropie quadratique :

K
nj m
n ij    n ij  
I  S i   
j 1

n  i 1
nj  m
1  )
n i  m  

51
 SIPINA

Comment passer de Si à Si+1 ?

Partition courante de Si

S3

S1 S2

Phase 1: Passage de Si à Si+1 par regroupement

S i1 1  s 3 , s 1  s 2   
  S i11   S ' i  1   m a x   S i j 1 
j 1 , 2 , 3
S i21  s1 , s 2  s 3    S 2

Si   S ' i 1   0 alors Si+1=S'i+1

i 1

S i31  s 2 , s1  s 3   S i31 
Repartir à la phase 1

52
SIPINA

Phase 2: Passage de Si à Si+1 par regroupement-éclatement

- Supposons on a 3 variables exogènes

Éclatement du premier regroupement par les 3 variables

- Sur chacun des sommets issu d’un regroupement, on cherche par ´éclatement,
avec toutes les variables Xj la meilleure partition

53
SIPINA

Phase 3: Passage de Si à Si+1 par éclatement

- Éclatement des sommets par les 3 variables

54
Inconvénients des arbres de décision

Le choix d’une branche n’est plus jamais

remis en cause.

L’apprentissage nécessite un grand nombre

d’individus.
La forme des modèles obtenus ne correspond
pas forcément à celle de l’échantillon.
Le temps de calcul d’un arbre est long.

Mauvaise performance s’il y a beaucoup de

classes

55