Machine Deep Learning

MP-2L

Machine Learning

Deep Learning

MASTÈRE PROFESSIONNEL

EN LOGICIELS LIBRES - MP2L

Amel Borgi

PLAN DU COURS

 Chap 1 : Introduction

 Chap 2 : Notions de base

 Chap 3 : Apprentissage supervisé

 Approches numériques

Les arbres de décisions

 Chap 4 : Apprentissage non supervisé

K-means

Les règles d’association

 Chap 5 : Les réseaux de neurones – Deep

learning

Machine Deep Learning

MP-2L

Chap.3 :

Apprentissage supervisé

3.2. Les arbres de décision

PLAN : Chap. 3 Apprentissage supervisé

3.2. Les arbres de décision

 Introduction

 Arbres de décision : principe

 Choix du meilleur attribut de segmentation

 Autres paramètres de construction d’un arbre de

décision (Critère d’arrêt, Discrétisation,…)

 Apprentissage/Prédiction

 Elagage

 Conclusion : méthodes, avantages et limites

Machine Deep Learning

MP-2L

Introduction

Exemple introductif

 Des observations décrites par 2 attributs :

 Gorge irritée à 2 modalités : {oui, non}

 Température à 2 modalités : {< 37,5 , ≥37,5}

 Les observations sont réparties entre 2 classes

{malade, bien portant}

 Extrait de la base d’apprentissage :

Attributs

Classe

Gorge irritée Température

oui

non

oui

37,3

38,5

malade

bien portant

malade

Machine Deep Learning

MP-2L

Exemple introductif

Un nœud = une variable

Une branche = une valeur

Une feuille = un ensemble d’individus

Un parcours = une règle

Si Température < 37,5 Et Gorge irritée

Alors malade

Apprentissage par génération de règles

 Méthodes qui consistent à générer directement

ou indirectement des règles de classification.

 Règles de production de la forme :

Si [prémisse] Alors [conclusion]

 Prémisse : conjonction de descripteurs logiques

du type attribut = valeur

(ou opérateur de comparaison, ensemble de valeurs, …)

 Conclusion : Classe = modalité.

 Méthodes à fort pouvoir explicatif, non paramétriques.

Machine Deep Learning

MP-2L

Les arbres de décision : Pourquoi ?

 Pour certains domaines d'application, il est essentiel de

produire des procédures de classification

compréhensibles par l'utilisateur.

 Les arbres de décision répondent à cette contrainte :

 représentation graphique d’un ensemble de règles

 interprétation aisée

 Algo. d'apprentissage par arbres de décision :

 efficaces (pas toujours !)

 disponibles dans la plupart des environnements de

fouille de données (Weka, R, Tanagra, Orange, ...)

Les arbres de décision :

principe

Machine Deep Learning

MP-2L

Les arbres de décision : Principe

 Classification basée sur une séquence de

questions portant sur un attribut.

 Chaque nœud est associé à un attribut et

représente un test (une question)

 Chaque arc issu de ce nœud correspond à l’une

des valeurs de cet attribut.

 La feuille désigne la classe correspondant à

l’objet à classer

Apprentissage par partitionnement

Objectif : on veut construire des sous-groupes les

plus « homogènes » du point de vue de la

variable à prédire.

La variable qualitative Y prend ses

valeurs dans { , }

Le sous-groupe est

complètement pur (homgène)

du point de vue de Y, il ne

possède que des individus

portant la valeur de Y

Machine Deep Learning

MP-2L

Les arbres de décision : principe

 La construction d’un arbre de décision se fait de manière

descendante, de la racine vers les feuilles, et est

qualifiée dans la littérature anglaise par le terme TDIDT

(Top Down Induction of Decision Trees).

 Les algorithmes de construction d’arbres de décision

procèdent par divisions successives de la base

d’apprentissage, l’algorithme générique formalisé dans

[Marsala 98] est le suivant :

Algorithme de construction d'un

arbre de décision

1. Choisir le « meilleur » attribut Xk, de modalités {vk,1,...,vk,i,...,vk,mk}, au

sens d’un critère donné, pour partitionner la base d’apprentissage. Un

nœud N(Xk) est créé dans l’arbre, portant un test sur la valeur de Xk.

2. Partitionner la base d’apprentissage courante (au départ de

l’algorithme, c’est la base complète W

de sous-bases W

W = ¨

i que l’attribut possède de modalités vk,i :

)= vk,i}

/ Xk(w

Chaque valeur de l’attribut libelle un arc issu de ce nœud N(Xk) et

associé à la sous-base W

i avec W

i ={w

) avec cet attribut en créant autant

3. A l’aide d’un critère d’arrêt, vérifier la condition d’arrêt sur chaque sous

base W

naissance à une feuille dans l’arbre. Attribuer une classe à cette feuille.

i créée. Une sous-base qui vérifie la condition d’arrêt donne

4. Recommencer en 1 avec les sous-bases qui ne vérifient pas le critère

d’arrêt.

Machine Deep Learning

MP-2L

Algorithme de construction d'un

arbre de décision

 Les paramètres qui conditionnent la structure et

le fonctionnement des différents algorithmes

sont relatifs aux solutions adoptées :

 pour choisir un attribut à l’étape 1,

 pour partitionner la base à l’étape 2

 et pour mesurer le critère d’arrêt à l’étape 3.

Les arbres de décision : Exemple de Quinlan

Chaque individu est décrit par 3 attributs [Quinlan 83] :

Taille : {petit, grand}

Cheveux : {noir, roux, blond}

Yeux : {bleu, brun}

Voici un exemple d’arbre obtenu

par un algorithme :

Attributs

Classe

Taille Cheveux Yeux

petit

blond

grand blond

grand roux

petit

noir

grand noir

grand blond

grand noir

petit

bleu +

brun

bleu +

bleu

bleu +

brun

blond

noir

Cheveux

roux

3 -

0 -

5 -

blond

Yeux

2 -

bleu

0 -

brun

2 -

Machine Deep Learning

MP-2L

Les arbres de décision : Exemple

Chaque individu est décrit par 3 attributs [Quinlan 83] :

Taille : {petit, grand}

Cheveux : {noir, roux, blond}

Yeux : {bleu, brun}

Attributs

Classe

Taille Cheveux Yeux

petit

blond

grand blond

grand roux

petit

noir

grand noir

grand blond

grand noir

petit

bleu +

brun

bleu +

bleu

bleu +

brun

blond

Voici un autre exemple d’arbre obtenu

par un autre algorithme :

Taille

5 -

grand

Cheveux

3 -

petit

Yeux

2 -

brun

bleu

noir

roux

1 -

2 -

0 -

blond

Les arbres de décision : Exemple

 Avec les même données, il est possible de

construire différents arbres, selon la façon dont

sont fixés les paramètres de l’algorithme

générique.

 Nous verrons plus tard, comment fixer les

paramètres de l’algorithme générique de

construction des arbres de décision.

 Pourquoi ne pas générer tous les arbres

possibles, pour une base d’apprentissage

donnée, puis choisir le meilleur ?

Machine Deep Learning

MP-2L

Recherche exhaustive dans

l’ensemble des arbres

possibles

 Impossible :

exponentiel en fonction de

 nombre d ’attributs : d

 nombre moyen de valeurs par attributs : a



(

)

a i

Arbres possibles

72385

18.1018

Quatre problèmes fondamentaux dans

la construction des arbres de décision

 Choix du meilleur attribut de segmentation

Pourquoi l’attribut Cheveux sur le sommet initial ?

 Critère d’arrêt

Comment décider qu’un nœud devient une feuille ?

 Choix des bornes de discrétisation

Découpage des attributs continus

 Prise de décision dans les sous groupes

Comment assigner une modalité de l’attribut à prédire

à une feuille ?

Machine Deep Learning

MP-2L

Choix du meilleur attribut

de segmentation

Choix du « meilleur » attribut

 Pour choisir le test, on utilise des fonctions qui mesurent le

degré de mélange des différentes classes (Gini, entropie…)

 Min de la fct : tous les ex. sont dans une même classe.

 Max de la fct :exemples également répartis entre les classes.

 On estime le degré de mélange espéré en pondérant les

degrés de mélange des fils par la proportion des exemples

allant sur ce fils

Choix du test (attribut) qui fournit le

degré de mélange espéré minimum

 Gain = degré de mélange du noeud courant diminué du

degré de mélange espéré par l'introduction du test (attribut)

Choix du test qui apporte

le gain maximal

Machine Deep Learning

MP-2L

Choix du « meilleur » attribut

de segmentation

Une mesure de discrimination permet de choisir l’attribut

qui réduit au maximum l’incertitude de prédiction des classes.

 Gain d’information (ou information mutuelle)

issu de la mesure d’entropie de Shannon [Quinlan 83]

 Critère de Gini

mesure l’impureté d’un attribut au regard d’une classe

CART [Breiman et al. 84]

 Quantité du Chi 2

choisir l’attribut le plus corrélé avec la variable à prédire

[Rakotomalala 97]

Choix du « meilleur » attribut

de segmentation

Dans ce cours, nous considérons le Gain d’information

(ou information mutuelle) issu de la mesure d’entropie

de Shannon [Quinlan 83].

L’algorithme correspondant est ID3 [Quinlan 83].

Machine Deep Learning

MP-2L

Choix du « meilleur » attribut

de segmentation

L’entropie de Shanon

 Quantité d’information d’un message :

nombre minimal de bits nécessaires pour coder

toutes les significations possibles de ce message

 Entropie en bits d’un message M :

H(M)= log2(n)

n : nb de significations différentes

que peut prendre le message.

 Exemple : Pour coder les 7 jours de la semaine on a

besoin de log2(7)=2.807 bits.

Choix du « meilleur » attribut

de segmentation

L’entropie de Shanon

Machine Deep Learning

MP-2L

Choix du « meilleur » attribut de segmentation

L’entropie de Shanon : Entropie d’information

de l’échantillon S en C classes

 Quantité de bits nécessaires pour connaître

la classe d’une observation :



S(Y)

log.p

)p(

avec pk=Pr(Y=yk) : probabilité de la classe yk

et y1, ..., yC les C classes.

-nulle quand il n’y a qu’une classe

-d’autant plus grande que les classes sont équiprobables

-vaut log2(C) quand les C classes sont équiprobables

-Unité : le bit d’information

Objectif : minimiser l’entropie

Choix du « meilleur » attribut de segmentation

Entropie conditionnelle

 Nb de bits nécessaires pour connaître Y

sachant la valeur xi de l’attribut X

Entropie du

nœud fils i

S(Y/



log.p

)p(

avec pki=Pr(Y=yk /X=xi)

 En moyenne, pour connaître la valeur de Y sachant X :

L = nombre de nœuds fils

Entropie du nœud

fils i

S(Y/X)



log.p

)p(

avec pi=Pr(X=xi)

pi= Fréquence du nœud fils i = (effectif du nœud fils i) / (effectif du sommet père)

Gain d’information : Gain(Y/X) = S(Y) - S(Y/X)

Mesure l’information gagnée par le choix d’une variable.

Machine Deep Learning

MP-2L

Choix du « meilleur » attribut de segmentation

 L’entropie conditionnelle de chaque attribut X

est calculée

 Cela répond à la question : si on choisissait X

pour segmenter la base, qu’est ce que cela

nous ferait gagner en terme d’information ?

 Choix de l’attribut dont le gain d’information

est maximal

 C’est l’attribut ayant l’entropie conditionnelle

minimale

Gain d’information : Exemple de Quinlan

[Quinlan 83]

On considère la base d’apprentissage contenant les 8

exemples ci-dessous. On souhaite construire l’arbre de

décision avec l’algorithme ID3 proposé par Quinlan et

basé sur la maximisation du gain d’information.

Attributs

Classe

Taille Cheveux Yeux

petit

blond

grand blond

grand roux

petit

noir

grand noir

grand blond

grand noir

petit

bleu +

brun

bleu +

bleu

bleu +

brun

blond

Ces exemples sont :

 répartis entre les 2 classes +

et –

 décrits par 3 attributs : Taille,

Cheveux et Yeux

Machine Deep Learning

MP-2L

Gain d’information : exemple de Quinlan

Entropie associée à l’échantillon à la racine :

S(Y)



log.p

)p(

= -(3/8)log2(3/8)-(5/8)log2(5/8) = 0,954

p(+) : estimé par nb d’exemples + / nb total d’exemples = 3/8

p(-) : estimé par nb d’exemples - / nb total d’exemples = 5/8

Attributs

Classe

Taille Cheveux Yeux

petit

blond

grand blond

grand roux

petit

noir

grand noir

grand blond

grand noir

petit

bleu +

brun

bleu +

bleu

bleu +

brun

blond

Pour mémoire :

log2(x)= ln(x)/ln(2)

Pour choisir l’attribut qui sera

à la racine, on doit calculer le

gain apporté par chaque attribut.

L’attribut choisi sera alors celui

qui maximise ce gain.

Pour un attribut X :

Gain(Y/X) = S(Y) - S(Y/X)

Calcul du gain pour l’attribut Taille

 A la racine : S(Y)= -(3/8)log2(3/8)-(5/8)log2(5/8) =0,954

(8 exemples répartis en 3+ et 5-)

 Au nœud : Taille = petit (3 exemples répartis en 1+ et 2-)

S1(Y)= -(1/3)log2(1/3)- (2/3)log2(2/3)

 Au nœud : Taille = grand (5 exemples répartis en 2+ et 3-)

S2(Y)= -(2/5)log2(2/5)- (3/5)log2(3/5)

Attributs

Classe

Taille Cheveux Yeux

petit

blond

grand blond

grand roux

petit

noir

grand noir

grand blond

grand noir

petit

bleu +

brun

bleu +

bleu

bleu +

brun

blond

S(Y/X)



log.p

)p(

S(Y/Taille)= 3/8 S1 + 5/8 S2 =

3/8 x (-(1/3)log2(1/3)- (2/3)log2(2/3))

+ 5/8 x (-2/5log2(2/5) - 3/5log2(3/5))

= 0,950

Gain (Y/Taille)= S(Y) –S(Y/Taille)

= 0,954-0,950 = 0,004

Machine Deep Learning

MP-2L

Calcul du gain pour l’attribut Taille

 A la racine : S(Y)= -(3/8)log2(3/8)-(5/8)log2(5/8) =0.954

(8 exemples répartis en 3+ et 5-)

 Au nœud : Taille = petit (3 exemples répartis en 1+ et 2-)

S1(Y)= -(1/3)log2(1/3)- (2/3)log2(2/3)

 Au nœud : Taille = grand (5 exemples répartis en 2+ et 3-)

S2(Y)= -(2/5)log2(2/5)- (3/5)log2(3/5)

 S(Y/Taille)=3/8 x S1 + 5/8 x S2 = 0.950

0.954

Taille

petit

grand

Gain(Y/Taille) =

S(Y) –S(Y/Taille)

0.950

Gain (Y/Taille)=0.954-0.950

= 0.004

Calcul du gain pour l’attribut Cheveux

 A la racine : S(Y)= -(3/8)log2(3/8)-(5/8)log2(5/8) =0,954

(8 exemples répartis en 3+ et 5-)

 Au nœud : Cheveux = blond (4 exemples répartis en 2+ et 2-)

S1(Y)= -(2/4)log2(2/4)- (2/4)log2(2/4)= 1 (répartition équitable:

entropie maximale)

 Au nœud : Cheveux = roux (1 exemple de classe +)

S2(Y)= 0 (noeud homogène : entropie minimale)

 Au nœud : Cheveux = noir (3 exemples de classe -)

S3(Y)= 0 (noeud homogène)

 S(Y/Cheveux)=4/8 x S1 + 1/8 x S2 + 3/8 x S3 = 0.5

0.94

5 -

Cheveux

blond

roux

noir

0 -

Gain(Y/Cheveux) =

S(Y) –S(Y/Cheveux)

Gain(Y/Cheveux) =

0.954-0.5=0.454

0.5

Machine Deep Learning

MP-2L

Calcul du gain pour l’attribut Yeux

 A la racine : S(Y)= -(3/8)log2(3/8)-(5/8)log2(5/8) =0.954

(8 exemples répartis en 3+ et 5-)

 Au nœud : Yeux = bleu (5 exemples répartis en 3+ et 2-)

S1(Y)= -(3/5)log2(3/5)- (2/5)log2(2/5)

 Au nœud : Yeux = brun (3 exemples de classe-)

S2(Y)= 0 (noeud homogène)

 S(Y/Yeux)=5/8 x S1 + 3/8 x S2 = 0.607

0.954

Yeux

bleu

brun

Gain(Y/Yeux) =

S(Y) –S(Y/Yeux)

0.607

Gain (Y/Yeux)=0.954-0,607

= 0.347

Récapitulatif des gains d’information

 A la racine : S(Y)= 0,954

 S(Y/Taille) = 0,950

 S(Y/Cheveux)= 0,5

 S(Y/Yeux)=0,607

Gain (Y/Taille)=0.954-0.950= 0.004

Gain(Y/Cheveux) = 0.954-0.5=0.454

Gain (Y/Yeux)=0.954-0.607 =0.347

Le Gain max est atteint pour l’attribut Cheveux (ce qui

correspond à l’entropie conditionnelle minimale)

Choix de l’attribut Cheveux pour

partitionner la base à la racine

5 -

Cheveux

blond

roux

noir

0 -

Machine Deep Learning

MP-2L

Exemple de Quinlan

 Condition d’arrêt : nœud homogène

 Les nœuds Cheveux = roux et Cheveux=noir vérifient la

condition d’arrêt  ils deviennent des feuilles

 Choix de la classe la plus fréquente comme étiquette des feuilles

 Classe + au nœud Cheveux=roux

 Classe – au nœud Cheveux=noir

 Le nœud Cheveux = blond ne vérifie pas la condition d’arrêt

On réitère l’algorithme au nœud Cheveux = blond pour choisir le

meilleur attribut de segmentation parmi ceux restant (Yeux et

Taille) avec la sous-base contenant les 4 exemples ayant

Cheveux = blond

5 -

Cheveux

blond

roux

noir

0 -

Autres paramètres

de construction

d’un arbre de décision

Machine Deep Learning

MP-2L

Critère d’arrêt

 Quand décider qu’un nœud devient une feuille ?

 Plusieurs critères possibles :

Critère retenu dans ID3

 Homogénéité des sous bases (tous les

individus dans la feuille sont de la même classe)

Critère de confiance

Taille de la sous-base (la connaissance produite

doit reposer sur un nombre suffisant d’individus)

Critère de support

 Plus aucun attribut à tester

…

Prise de décision dans les sous

groupes

 Affectation à un sous groupe d’une modalité de

la variable à prédire

 Sous l’hypothèse d’un tirage aléatoire de

l’échantillon dans la base initiale, on assignera

la modalité la plus fréquente aux groupes.

Modalité (classe) le plus fréquente

Machine Deep Learning

MP-2L

Discrétisation des attributs continus

 Dans les arbres de décision, les attributs

continus ne peuvent pas être pris en compte

 une étape de discrétisation est nécessaire.

 Discrétiser un attribut continu consiste à

découper son domaine de variation en un

nombre fini d’intervalles. Ces intervalles sont

ensuite considérés comme des valeurs

discrètes, comme de nouveaux concepts

symboliques.

Discrétisation des attributs continus

 Exemple : on souhaite prédire si on peut jouer au tennis ou

pas, en fonction des attributs : outlook, temp, humidity et

wind.

rain

Day outlook

sunny

D3 overcast

D7 overcast

sunny

rain

D10

sunny

D11

D12 overcast

D13 overcast

D14

rain

temp

humidity wind

weak

strong

weak

strong

weak

strong

weak

strong

high

normal

high

normal

high

normal

high

play

Yes

Machine Deep Learning

MP-2L

Discrétisation des attributs continus

 Exemple : on souhaite prédire si on peut jouer au tennis ou

pas, en fonction des attributs :

 outlook : variable qualitative à valeurs dans {sunny,

overcast, rain}

 temp : variable continue dans [0, 35]

 humidity : variable qualitative (ordinale) à valeurs dans

{normal, high}

 wind : variable qualitative à valeurs dans {weak, strong}

 La variable temp doit être discrétisée.

Discrétisation des attributs continus

 Ex : Discrétisation de la variable continue temp

Points de coupures candidats

Temp

JouerTennis

Yes

 Comment choisir les points de coupure ?

Différentes méthodes de discrétisation existent.

Par exemple la discrétisation régulière en un nombre

prédéfini de sous-intervalles de même taille.

Ici en 3 sous-intervalles :

[0, 15] : faible

]15, 30] : moyenne

]30, 45] : élevée

La variable temp est devenue

ordinale à valeurs dans :

{faible, moyenne, élevée}.

Machine Deep Learning

MP-2L

Discrétisation des attributs continus

 Comment choisir le point de coupure ?

Différentes méthodes de discrétisation existent :

 Non supervisées (régulière, fréquences égales, …)

Ne prend pas en compte la connaissance des

classes pour déterminer les points de coupures

 Supervisées (Chimerge [Kerber 92], MDLPC [Fayyad et

al. 93], …)

Prend en compte la connaissance des classes pour

déterminer les points de coupures

Apprentissage/

Prédiction

Machine Deep Learning

MP-2L

Erreur empirique ou taux

d’erreur en re-substitution

 Erreur empirique d’un arbre de décision :

erreur sur l’ensemble d’apprentissage.

l'erreur empirique est une vision très optimiste

de l'erreur réelle,

trouver un arbre de décision d'erreur

empirique minimale est, en général, un

problème NP-complet.

Arbre de décision parfait

 Un arbre de décision parfait est un arbre

de décision tel que tous les exemples de

l'ensemble d'apprentissage soient

correctement classifiés, càd :

 Un tel arbre n'existe pas toujours

Machine Deep Learning

MP-2L

Arbre de décision et règles de

décision

 Chaque chemin dans un arbre de décision(depuis la

racine jusqu’à une feuille) effectue une série de tests sur

les valeurs des attributs pour déduire la classe à affecter

aux valeurs testées.

 Un chemin est donc équivalent à une règle de

production Si [prémisse] Alors [conclusion]. La prémisse

de cette règle est une conjonction des tests réalisés sur

le parcours en question, et la partie conclusion contient

la classe libellant la feuille du chemin, atteinte en fin de

parcours.

 Un arbre de décision correspond donc à une base de

règles de classification, et toute nouvelle observation

peut être classée par l’usage de la méthode d’inférence

classique du raisonnement par déduction.

Arbre de décision et règles de

décision

météo

soleil

nuage

pluie

température

oui

vent

<= 10

>10

et <= 37.5

> 37.5

> 20

<= 20

non

oui

non

oui

Règle 1:

SI (météo=“soleil”) ET (température<=10)

ALORS (jouer=“non”)

Règle 2:

SI (météo=“pluie”) ET (vent>20)

ALORS (jouer=“non”)

Règle 3:

SI (météo=“nuage”)

ALORS (jouer=“oui”)

. . .

Machine Deep Learning

MP-2L

Les arbres de décision :

apprentissage / prédiction

 La phase d’apprentissage :

 Construction d’un arbre de décision à partir de

la base d’apprentissage.

 La fonction de classement est représentée par:

 l’arbre de décision obtenu

 ou la base de règles obtenue à partir de

l’arbre

 La phase reconnaissance (de prédiction) :

 Utiliser l’arbre ou la base de règles pour classer

une nouvelle observation (représentée par le

vecteur de ses attributs)

Les arbres de décision :

apprentissage / prédiction

 La phase reconnaissance (de prédiction) :

Le classement d’un nouvel individu est réalisé

en le présentant séquentiellement aux nœuds de

l’arbre. Il est d’abord présenté à la racine où un

test est réalisé sur la valeur qu’il possède pour

l’attribut libellant ce nœud. Selon le résultat du

test, l’individu suit l’arc libellé par ce résultat pour

atteindre soit un nouveau nœud où le processus

de comparaison est réitéré, soit une feuille. Dans

ce dernier cas, la classification est terminée : le

nouvel individu est affecté à la classe libellant

cette feuille.

Machine Deep Learning

MP-2L

Les arbres de décision: Phase

d’apprentissage

Algorithmes

d’arbres de

décision

Données

D’apprentissage

temp

hot

mild

cool

mild

cool

mild

hot

mild

humidity wind

weak

strong

weak

strong

weak

strong

weak

strong

high

normal

high

normal

high

normal

high

play

Yes

Modèle :

arbre de décision

SI (météo=“soleil”) ET (température<=10)

ALORS (jouer=“non”)

…

rain

Day outlook

sunny

D3 overcast

D7 overcast

sunny

rain

D10

sunny

D11

D12 overcast

D13 overcast

D14

rain

Les arbres de décision: phase de

reconnaissance

Modèle:

arbre de décision

Données

de test

Nouvelles données

(sunny, T >10, hum:high, vent :strong)

Day outlook

sunny

D3 overcast

D7 overcast

sunny

rain

temp

hot

mild

cool

mild

humidity wind

weak

strong

weak

strong

weak

high

normal

high

play

Yes

joue t-il au tennis?

Yes

Machine Deep Learning

MP-2L

Élagage

Élaguer l’arbre

 Objectif : minimiser la longueur de la description des

données par un arbre. Corriger le sur-apprentissage

 Cette méthode coupe des parties de l'arbre en

choisissant un noeud et en enlevant tout son sous-arbre.

 Ceci fait donc du noeud une feuille et on lui attribue la

valeur de classification qui revient le plus souvent.

 Des noeuds sont enlevés seulement si l'arbre

résultant n'est pas pire que l'arbre initial sur les

exemples de validation.

 On continue tant que l'arbre résultant offre de

meilleurs résultats sur les exemples de validation.

Machine Deep Learning

MP-2L

Elagage : différentes méthodes

 Arrêt aussitôt que possible :

 cesser d'étendre lorsque le partitionnement

n'est plus significatif

 test si la partition produite améliore la précision.

 Élagage a posteriori :

 construire l'arbre entier

 supprimer les noeuds inutiles (test approprié).

Conclusion

Méthodes, avantages et limites

Machine Deep Learning

MP-2L

Les arbres de décision : les méthodes

 Trois systèmes ont plus particulièrement marqué

les travaux sur les arbres de décision :

 ID3 (critère de segmentation : Gain d’information)

et C4.5 (critère de segmentation Ratio de Gain)

[Quinlan 83] [Quinlan 93]

(cid:1) dans la communauté IA

 CART (critère de segmentation : Critère de Gini)

[Breiman et al. 84]

(cid:1) origine statistique

Les arbres de décision: les

méthodes

 Ces méthodes permettent d’obtenir divers graphes :

 des arbres n-aires (ID3, C4.5, ChAid)

 des arbres binaires (CART)

 des latticiels (SIPINA)

 Grandes qualités :

 Traduction immédiate en règles

 Technique visuelle (plus parlante, plus compréhensible)

 Disponibles dans la plupart des environnements de

fouille de données (Weka, R, Tanagra, Orange, ...)

Machine Deep Learning

MP-2L

Les arbres de décision: les limites

 La manière de procéder dans la construction du graphe :

 La segmentation pure (ID3, C4.5),

 Le regroupement des modalités d’une variable (ChAid,

CART),

 La fusion des sommets n’ayant pas le même

ascendant (SIPINA)

 Le choix des critères pour trouver la meilleure variable ou

pour mesurer le taux d’erreur lors de l’élagage.

 Le grand handicap : traiter le cas où la variable à

expliquer (à prédire) est continue.

Machine Learning and Decision Trees

Machine Learning and Decision Trees