Notes

Arbres de décision

F. De Comité

Licence-Master Informatique

15 janvier 2009

F. De Comité Arbres de décision

Caractéristiques Notes

Algorithme de classification.
Prédiction d’une classe discrète.
Probabilité d’appartenance à chaque classe.

F. De Comité Arbres de décision

Un exemple Notes

Aspect du ciel
Couvert
Soleil Pluie

Humidité Vent OUI

Forte Fort
Normale Faible

NON OUI NON OUI

F. De Comité Arbres de décision

L’échantillon Notes

Ciel, Température,Humidité,vent,Jouer ?
Soleil,Chaud,Forte,faible,Non
Soleil,Chaud,Forte,Fort,Non
Couvert,Chaud,Forte,faible,Oui
Pluie,Doux,Forte,faible,Oui
Pluie,Frais,Normale,faible,Oui
Pluie,Frais,Normale,Fort,Non
Couvert,Frais,Normale,Fort,Oui
Soleil,Doux,Forte,faible,Non
Soleil,Frais,Normale,faible,Oui
Pluie,Doux,Normale,faible,Oui
Soleil,Doux,Normale,Fort,Oui
Couvert,Doux,Forte,Fort,Oui
Couvert,Chaud,Normale,faible,Oui
Pluie,Doux,Forte,Fort,Non

F. De Comité Arbres de décision

Comprendre l’arbre Notes

Rectangles : tests sur un attribut.

Arcs : valeur de l’exemple pour le test.
Feuilles (ellipses) : classe.

F. De Comité Arbres de décision

Utiliser l’arbre pour classer un exemple Notes

Partir de la racine.
Répondre aux questions en suivant la branche correspondante.
Lire la valeur de la feuille atteinte.

F. De Comité Arbres de décision

Exemple Notes

Aspect du ciel : Soleil

Humidité : Normale
Vent : Faible
Température : 30

Aspect du ciel
Couvert
Soleil Pluie

Humidité Vent OUI

Forte Fort
Normale Faible

NON OUI NON OUI

F. De Comité Arbres de décision

Exemple Notes

Remarques
Pour un exemple, tous les attributs ne servent pas.
Selon l’exemple, des attributs différents sont utilisés.
La température n’intervient pas.

F. De Comité Arbres de décision

Construire des arbres Notes

Algorithme construisant un arbre à partir d’exemples ?

Trouver le meilleur arbre ?
Pour classer exactement l’échantillon ?
Pour classer correctement un nouvel exemple ?

F. De Comité Arbres de décision

Construction des arbres Notes

Remarque
Si deux descriptions identiques ont des classes identiques, alors il
existe un arbre classant parfaitement l’échantillon.

Remarque
Un tel arbre n’est pas forcément intéressant : il colle trop aux
données : mauvais pouvoir de généralisation.

F. De Comité Arbres de décision

Trouver le meilleur arbre Notes

Si la population est infinie : sans espoir.

Population finie : engendrer et tester tous les arbres ?
Impraticable.

F. De Comité Arbres de décision

Construction de l’arbre Notes

Puisqu’on ne peut espérer trouver le meilleur arbre, on se

contentera d’un bon arbre :
Arbre compact : éviter les peignes (listes de décisions).
Arbre d’erreur faible.
Arbre lisible, compréhensible par un non-expert.
Complexité algorithmique (temps espace) acceptable.

F. De Comité Arbres de décision

Algorithme : ID3 C4.5 Notes
Fonction CréerNoeud(S,L)
Entrées
S : ensemble d’exemples.
L : liste des attributs non encore utilisés.

Sortie : Un arbre de décision.

1 Si tous les exemples sont de la même classe, créer et retourner

une feuille étiquetée par cette classe.
2 Sinon :
1 Trouver le meilleur attribut dans L : A
2 Répartir les exemples de S en n sous-ensembles, selon leur
valeur pour cet attribut.
3 Allouer un nœud étiqueté par A
4 Pour toutes les valeurs de A : appeler CréerNoeud(Si ,L − A)
et faire de ces nœuds les fils du nœud étiqueté par A
F. De Comité Arbres de décision

Algorithme Notes

But : Obtenir des feuilles où tous les exemples sont de la

même classe.
Moyen :
Trouver le meilleur attribut en chaque nœud.
Pouvoir mesurer le degré de mélange d’un ensemble
d’exemples.

F. De Comité Arbres de décision

Mesure du degré de mélange Notes

n
n exemples, deux classes : 2 exemples de classe c1 −→
mélange maximal.
n exemples, deux classes : n − 1 exemples de classe c1 :
ensemble presque pur.
n exemples, deux classes : 1 exemple de classe c1 : idem.

F. De Comité Arbres de décision

Mesurer le mélange Notes

Fonction de p1 , · · · pn (les proportions d’exemples pour chaque

classe).
Maximale quand tous les pi sont égaux.
Minimale quand tous les exemples sont de la même classe.

Deux classes
Fonction de p (l’autre classe : 1 − p)
1
Maximale pour p = 2
Minimale quand p = 0 ou p = 1

F. De Comité Arbres de décision

Mesurer le mélange Notes

Polynômes : paraboles, quadriques.

Fonction de Gini :
2p(1 − p)
n
X
1− pi 2
i=1

Entropie :
−p log2 (p) − (1 − p) log2 (1 − p)
X
− pi log2 (pi )
i

F. De Comité Arbres de décision

Mesurer le mélange Notes

F. De Comité Arbres de décision

Mesurer le mélange Notes

F. De Comité Arbres de décision

Entropie Notes

Thermodynamique . . .
Théorie de l’information : nombre moyen de bits nécessaires
pour coder la classe d’un exemple . . .

F. De Comité Arbres de décision

Utiliser l’entropie Notes

N examples
Attribut

Nq

N1 N2 N3
(pq1...pqk)
(p11...p1k) (p21...p2k) (p31...p3k)

F. De Comité Arbres de décision

Utiliser l’entropie Notes

Au départ : N exemples, k classes,entropie E .

Pour l’attribut testé : q branches.
Ni exemples suivent la branche i.
Dans la branche i, la répartition des classes est donnée par
pi1 · · · pi k

Questions
Que nous apprend de plus, pour la classe, le fait de connaı̂tre
la valeur de l’exemple pour l’attribut testé ?
Quel est le gain associé à cet attribut ?

F. De Comité Arbres de décision

Gain Notes

Définition
Le gain d’un ensemble d’exemples S pour un attribut A est défini
par :
q
X |Si |
Gain(S, A) = Entropie(S) − × Entropie(Si )
|S|
i=1

Si : sous-ensemble des exemples suivant la branche i

|Si | : cardinal de Si .
q : nombre de branches du test.

Définition
L’attribut choisi par l’algorithme est celui qui maximise le gain.

F. De Comité Arbres de décision

Gain : exemple de calcul Notes

10 exemples, 2 classes (C1 et C2 )

(5 exemples de chaque classe).
deux attributs à tester : A (deux valeurs A1 et A2 ),
et B (deux valeurs B1 et B2 ).
A1 A2 B1 B2
C1 4 1 C1 3 2
C2 1 4 C2 2 3

F. De Comité Arbres de décision

Gain : exemple de calcul Notes

5 5 5 5
E (S) = − × log2 ( ) − × log2 ( ) = 1
10 10 10 10

5 5
Gain(S, A) = 1 − × Entropie(4, 1) − × Entropie(1, 4)
10 10

5 5
Gain(S, A) = 1 − × Entropie(3, 2) − × Entropie(2, 3)
10 10

F. De Comité Arbres de décision

Gain : exemple de calcul Notes

1 1 4 4
Entropie(4, 1) = − × log2 ( ) − × log2 ( ) = 0.72
5 5 5 5
2 2 3 3
Entropie(2, 3) = − × log2 ( ) − × log2 ( ) = 0.97
5 5 5 5

Gain(S, A) = 1 − 0.5 × 0.72 − 0.5 × 0.72 = 0.28

Gain(S, B) = 1 − 0.5 × 0.97 − 0.5 × 0.97 = 0.03

F. De Comité Arbres de décision

Gain : exemple de calcul Notes

L’attribut A conduit au meilleur gain : les deux fils du nœud

sont plus purs
Connaı̂tre la valeur d’un exemple pour l’attribut A m’apporte
en moyenne plus d’information sur sa classe que sa valeur
pour l’attribut B
Cette connaissance me permet de diminuer l’erreur de
classification.

F. De Comité Arbres de décision

Concavité Notes

F. De Comité Arbres de décision

Aspect du ciel Notes

5 4 5
Gain(Aspect,S) = E (S)− ×E (3, 2)− ×E (4, 0)− ×E (2, 3)
14 14 14
9 9 5 5
E (S) = − × log2 ( ) − × log2 ( )
14 14 14 14
E (4, 0) = 0
2 2 3 3
E (3, 2) = E (2, 3) = − × log2 ( ) − × log2 ( )
5 5 5 5
Gain(Aspect,S) = 0.246

F. De Comité Arbres de décision

Gain : exemple Notes

Aspect du ciel Humidité

Soleil Couvert Pluie Haute Normale

(2,3) (6,1)
(4,0)
(3,2) (3,4)

Temperature Vent

Chaud Modéré Froid Faible Fort

(2,2) (4,2) (3,1) (3,3)

(6,2)

F. De Comité Arbres de décision

Gain deuxième exemple Notes

Aspect : 0.246
Humidité : 0.151
Vent : 0.048
Température : 0.029
C’est Aspect qui est choisi à la racine.

F. De Comité Arbres de décision

Gain : deuxième exemple Notes

Couvert : tous les exemples sont de la même classe : fini.

Soleil :
Humidité : 0.970 −→ choisi.
Température : 0.570
Vent : 0.019
Pluie : Vent est choisi.

F. De Comité Arbres de décision

Quelques remarques Notes

Remarque
Lecture aisée, possibilité d’extraire des règles :
si (Aspect=Soleil) et (Humidité=Normale) alors oui

Remarque
Permet de repérer les attributs les plus déterminants pour la
classification.

Remarque
Complexité : A chaque niveau de l’arbre, pour chaque attribut
possible, parcourir l’ensemble complet des exemples :
0(n × k × p) ' 0(n) (n : nombre d’exemples, p : nombre
d’attributs, k : profondeur de l’arbre).

F. De Comité Arbres de décision

Biais Notes

On ne parcourt pas l’ensemble de tous les arbres possibles.

Au départ, tous les arbres sont possibles
Quand un attribut est choisi : on restreint l’espace de
recherche.
On ne remet jamais en cause les choix précédents.
En sélectionnant les attributs les plus discriminants d’abord,
on engendre des arbres courts et compacts
(par observation . . .).

F. De Comité Arbres de décision

Limitations Notes

3 attributs binaires (0,1), 8 exemples (de 0 à 7 écrit en

binaire), 2 classes (parité du nombre de ’1’ dans la
description).
Aucun des attributs n’apporte de gain −→ arbre réduit à sa
racine.
Un arbre parfait existe pourtant !

F. De Comité Arbres de décision

Attributs continus Notes

A partir de cet attribut continu, obtenir un test binaire (n-aire).

Couper l’intervalle des valeurs de l’attribut en ce nœud en n
sous-intervalles : discrétiser.
Combien d’intervalles ?
Où effectuer les coupures ?
Pas de solution trop coûteuse ! (ne pas explorer toutes les
coupures en n intervalles, n variant).

F. De Comité Arbres de décision

Attributs continus Notes

Exemples

Exemple E1 E2 E3 E4 E5 E6
valeur 2 3 1 0 0 5
classe 1 2 2 2 1 1

Ordonner selon les valeurs de l’attribut :

Exemple E4 E5 E3 E1 E2 E6
valeur 0 0 1 2 3 5
classe 2 1 2 1 2 1

F. De Comité Arbres de décision

Attributs continus Notes

7 coupures binaires possibles : laquelle apporte le meilleur gain ?
Remarque
L’entropie initiale étant toujours la même, on se contenter de minimiser
l’entropie moyenne des fils.

Coupure 1 : un seul fils (3 c1, 3 c2) : entropie moyenne nulle, pas de

gain.
1 5
Coupure 2 : 6 × E (0, 1) + 6 × E (3, 2) = 0.8 Coupure choisie.
2 4
Coupure 3 : 6 × E (1, 1) + 6 × E (2, 2) pas de gain.
3 3
Coupure 4 : 6 × E (1, 2) + 6 × E (2, 1) = 0.92
4 1
Coupure 5 : 6 × E (2, 2) + 6 × E (1, 1) : comme la coupure 3 (pas de
gain).
Coupure 6 : comme la coupure 2.
Coupure 7 : voir coupure 1.

F. De Comité Arbres de décision

Attributs continus Notes

Complexité : coût d’un tri (la recherche de la coupure peut se

faire en temps linéaire).
Complexité de l’algorithme complet : O(n log n).
Seuil choisi = information supplémentaire sur les données
(discrétisation . . .).

F. De Comité Arbres de décision

Attributs continus Notes

F. De Comité Arbres de décision

Attributs continus Notes

Largeur des pétales
>0.6

<=1.7
Largeur des pétales

<=0.6 >4.9
Longueur des pétales

>1.7 Largeur des pétales
<=4.9

<=1.5 >1.5

Serosa Virginica Versicolor

Virginica Versicolor

F. De Comité Arbres de décision

Valeurs manquantes Notes

Différentes stratégies
Ignorer l’exemple : modifie l’échantillon . . ..
Créer une nouvelle valeur ’manquant’ : être manquant devient
un critère apparaissant dans le modèle . . ..
Remplacer la valeur :
Au hasard
Majoritaire (en général, par rapport à la classe, par rapport à
des exemples similaires : cf clustering . . .)

F. De Comité Arbres de décision

Valeurs manquantes Notes

Une autre stratégie

Soit un exemple ayant une valeur manquante pour l’attribut
en cours d’évaluation.
Puisqu’on ne connaı̂t pas la valeur de l’attribut pour cet
exemple, on va lui affecter une probabilité d’avoir chaque
valeur de l’attribut.
On estimera cette probabilité à partir des exemples ayant une
valeur pour cet attribut (proportions d’exemples sur chaque
branche)
On affectera à chaque branche une partie de l’exemple.

F. De Comité Arbres de décision

Valeurs manquantes : exemple Notes

Exemple E1 E2 E3 E4 E5 E6
valeur A1 A2 A2 ? A2 A1
classe C1 C1 C2 C2 C1 C2

F. De Comité Arbres de décision

Valeurs manquantes Notes

Gain calculé sur les exemples sans valeur manquante.

Gain coefficienté par la proportion d’exemples sans valeur
manquante.
3 2
Ensuite : 5 de D4 suivent la branche A1, 5 suivent la branche
A2.

F. De Comité Arbres de décision

Valeurs manquantes Notes

Remarque
A chaque exemple présent en un nœud, est associé un poids : c’est
ce poids qui est pris en compte lors des calculs de gain.

Remarque
Le calcul du gain s’étend sans problème aux poids fractionnaires,
de même que la définition de la classe majoritaire en une feuille.

Remarque
Une fraction d’exemple peut encore ensuite être fractionnée à
nouveau.

F. De Comité Arbres de décision

Valeurs manquantes Notes

Classification
Si l’exemple arrive en un nœud correspondant à un attribut
pour lequel sa valeur est manquante, il suit toutes les
branches issues de ce test, au prorata du nombre d’exemples
ayant suivi ces branches lors de la construction de l’arbre.
On calcule alors la probabilité qu’il a d’appartenir à chaque
classe.
La classe de plus forte probabilité est alors affectée à cet
exemple.

Remarque
La valeur de retour du classifieur pourrait être justement ce
vecteur de probabilités.

F. De Comité Arbres de décision

Valeur manquantes : Exemple Notes

On reprend l’exemple du golf (1er exemple modifié :

humidity=high changé en ?) :
sunny hot ? FALSE no
sunny hot high TRUE no
overcast hot high FALSE yes
rainy mild high FALSE yes
rainy cool normal FALSE yes
rainy cool normal TRUE no
overcast cool no normal TRUE yes
sunny mild high FALSE no
sunny cool normal FALSE yes
rainy mild normal FALSE yes
sunny mild normal TRUE yes
overcast mild high TRUE yes
overcast hot normal FALSE yes
rainy mild high TRUE no

F. De Comité Arbres de décision

 Notes

outlook = overcast : yes outlook = overcast : yes

(4.0) (4.0)
outlook = sunny : outlook = sunny :
| humidity = high : no | humidity = high : no
(3.0) (2.5)
| humidity = normal : yes | humidity = normal :
(2.0) | | temperature = hot : no
outlook = rainy : (0.5)
| windy = TRUE : no (2.0) | | temperature = mild :
| windy = FALSE : yes (3.0) yes (1.0)
| | temperature = cool :
yes (1.0)
outlook = rainy :
| windy = TRUE : no (2.0)
| windy = FALSE : yes (3.0)

F. De Comité Arbres de décision

Valeurs manquantes : exemple Notes

Le premier attribut est toujours outlook : son gain n’est pas modifié,
celui de humidity diminue.
Pour outlook=sunny : 5 exemples, dont un avec valeur manquante.

4 1 1
Gain(Hum,S) = × (E(3, 2) − × E(0, 2) − × E(0, 2))
5 2 2
4
Gain(Hum,S) = × (E(3, 2) − 0)
5
Gain maximum !
L’exemple à valeur manquante descend dans les deux branches
(d’où les 2.5 et 0.5).

F. De Comité Arbres de décision

Valeurs manquantes : exemple Notes

Utilisation en classification
A partir de l’arbre construit sans valeurs manquantes

outlook = overcast : yes (4.0)

outlook = sunny :

| humidity = high : no (3.0) | humidity = normal :

yes (2.0)
outlook = rainy :
| windy = TRUE : no (2.0)

| windy = FALSE : yes (3.0)

F. De Comité Arbres de décision

Valeurs manquantes : exemple Notes

Soit l’exemple ( ?, hot,high,FALSE).

il descend dans les 3 branches de outlook :
4
14 dans overcast : classe yes.
5
14 dans sunny : puis dans humidity=high : classe no.
5
14 dans rainy : puis dans windy=false : classe yes.
9 5
Proba(yes)= 14 Proba(no)= 14 : on lui attribue la classe yes.

F. De Comité Arbres de décision

Gain ratio Notes

Le critère du gain avantage les attributs discrets ayant beaucoup

de valeurs distinctes :
Soit A un attribut tel que les n exemples aient une valeur différente
pour A
n
X 1
Gain(A, S) = Entropie(S) − × Entropie(0, 1)
n
i=1

Gain(A, S) = Entropie(S) maximum !

F. De Comité Arbres de décision

Gain ratio Notes

Pénaliser les attributs :

Prenant beaucoup de valeurs différentes.
Répartissant équitablement les exemples dans toutes les
branches.

F. De Comité Arbres de décision

Gain ratio Notes

Definition
k
X |Si | |Si |
SplitInfo(S, A) = − × log2
|S| |S|
i=1
avec :
S : ensemble d’exemples. Si : nombre d’exemples valant Ai
pour l’attribut A.
k : nombre de valeurs de l’attribut A

F. De Comité Arbres de décision

Gain Ratio Notes

Definition
Gain(S, A)
GainRatio(S, A) =
SplitInfo(S, A)

F. De Comité Arbres de décision

Sur-spécialisation Notes

C4.5 continue à faire croı̂tre l’arbre tant que :

Il reste un nœud contenant des exemples de plusieurs classes.
Il reste au moins un test utilisable.
Il reste un gain intéressant.

F. De Comité Arbres de décision

La sur-spécialisation Notes

L’arbre obtenu alors :

Est grand.
Compliqué (difficilement lisible).
Trop proche des données de l’ensemble d’apprentissage.

surspécialisation = overfitting

F. De Comité Arbres de décision

Sur-spécialisation Notes

Exemple
Deux classes : c0 et c1
c0 est la classe majoritaire, probabilité p > 0.5
Les descriptions ne sont pas corrélées avec les classes.

Premier classifieur : règle majoritaire : erreur 1 − p

F. De Comité Arbres de décision

Sur-Spécialisation Notes
Deuxième classifieur
Un arbre à un seul test (binaire) :

Attribut 

p1 (1-p1)

C1 C2

F. De Comité Arbres de décision

Sur-spécialisation Notes

Erreur du deuxième classifieur

Probabilité pour un exemple de descendre dans la première
branche : p1 .
Probabilité pour cet exemple d’être mal classé : (1 − p)
Probabilité pour un exemple de descendre dans la deuxième
branche : (1 − p1 )
Probabilité pour cet exemple d’être mal classé : p.
Probabilité d’erreur du classifieur :

p1 (1 − p) + (1 − p1 )p

p1 (1 − p) + (1 − p1 )p ≥ p1 (1 − p) + (1 − p1 )(1 − p)
p1 (1 − p) + (1 − p1 )p ≥ (1 − p)
L’inégalité est stricte dès que p > 0.5

F. De Comité Arbres de décision

Sur-spécialisation Notes

Remplacer l’arbre par un nœud donne un meilleur arbre !

Des cas similaires se rencontrent souvent à partir d’une
certaine profondeur dans l’arbre.
Les exemples sont moins nombreux : les régularités sont plus
probablement dûes au hasard.
Créer de nouveaux nœuds : n’apporte rien, ou pire, sème la
confusion !

F. De Comité Arbres de décision

Sur-spécialisation Notes

Remèdes
S’arrêter avant d’engendrer un nœud inutile (pre-élagage).
Construire l’arbre, puis supprimer les nœuds “trop
spécialisants” (post-élagage).

F. De Comité Arbres de décision

Pré-élagage Notes

Selon quel critère renoncera-t-on à développer un nœud ?

Gain pas assez important :
On risque d’ignorer un test qui “prépare le terrain” pour un ou
plusieurs tests plus discriminants.
Comment fixer le seuil des gains intéressants ?
Interêt : diminue le temps de calcul de l’arbre . . .

F. De Comité Arbres de décision

Post-élagage Notes

Principe
Construire l’arbre complet.
Pour chaque nœud interne, regarder s’il ne serait pas meilleur
de le remplacer :
Par une feuille.
Par un de ses fils (son fils le plus fréquent).

F. De Comité Arbres de décision

Post-élagage Notes

physician fee freeze = n :

| adoption of the budget resolution = y : democrat (151.0)
| adoption of the budget resolution = u : democrat (1.0)
| adoption of the budget resolution = n :
| | education spending = n : democrat (6.0)
| | education spending = y : democrat (9.0)
| | education spending = u : republican (1.0)
physician fee freeze = y :
| synfuels corporation cutback = n : republican (97.0/3.0)
| synfuels corporation cutback = u : republican (4.0)
| synfuels corporation cutback = y :
| | duty free exports = y : democrat (2.0)
| | duty free exports = u : republican (1.0)
| | duty free exports = n :
| | | ...................
physician fee freeze = u :
| water project cost sharing = n : democrat (0.0)
| water project cost sharing = y : democrat (4.0)
| water project cost sharing = u :
| | mx missile = n : republican (0.0)
| | mx missile = y : democrat (3.0/1.0)
| | mx missile = u : republican (2.0)

F. De Comité Arbres de décision

Post-élagage Notes

physician fee freeze = n : democrat (168.0/2.6)

physician fee freeze = y : republican (123.0/13.9)
physician fee freeze = u :
| mx missile = n : democrat (3.0/1.1)
| mx missile = y : democrat (4.0/2.2)
| mx missile = u : republican (2.0/1.0)

F. De Comité Arbres de décision

Post-élagage Notes

Deux nœuds ont été remplacés par des feuilles.

Un autre nœud a été remplacé par un de ses fils.
Le nombre de mal classés pour chaque feuille est une
estimation pessimiste.

F. De Comité Arbres de décision

Post-élagage Notes

Comment faire ?
Si on connaissait exactement les taux d’erreur en chaque
nœud :
On calculerait l’erreur en chaque nœud (i.e. la somme des
erreurs de ses fils).
On comparerait à l’erreur obtenue si ce nœud n’était pas
développé (i.e. restait une feuille).
Si cette deuxième erreur est plus faible : on remplace le nœud
par la feuille.
(idem pour comparer un nœud avec son fils le plus fréquent).
Peut-on estimer ces taux d’erreur ?

F. De Comité Arbres de décision

Estimer les erreurs Notes

Utilisation d’un ensemble de validation :

Il faut réserver beaucoup d’exemples (descente dans l’arbre)
L’ensemble d’apprentissage en est réduit d’autant.
L’arbre obtenu est moins bon.
Utiliser l’ensemble d’apprentissage . . .attention au biais !

F. De Comité Arbres de décision

Post-élagage Notes

Pour un nœud donné, soit N le nombre d’exemples arrivant en

ce nœud.
Soit, parmi ces N exemples, E le nombre d’exemples mal
classés (dans la suite de l’arbre).
E
Le taux d’erreur N est manifestement optimiste.
Trouver une valeur plus pessimiste de la probabilité d’erreur
en ce nœud.

F. De Comité Arbres de décision

Estimation pessimiste de l’erreur Notes

Soit p la “vraie” probabilité d’erreur en ce nœud.

E
Soit N la probabilité optimiste constatée en ce nœud.
E
Quelle est la valeur maximale de p qui fait qu’une erreur de N
ne soit pas rare ?
E
Quelle est la valeur maximale de p telle que obtenir N erreurs
s’observe dans au moins 25% des cas ?

F. De Comité Arbres de décision

Estimation pessimiste Notes

Soit p la probabilité de mal classer un exemple.

Probabilité de rencontrer E erreurs pour N exemples :

CNE p E (1 − p)N−E

(loi binomiale).
Calculer l’intervalle de confiance (binomiale −→ loi normale
−→ tables).
p est l’estimation pessimiste de l’erreur.

F. De Comité Arbres de décision

Loi binomiale (n = 40, p = 0.3) Notes

F. De Comité Arbres de décision

Loi normale approchant Notes

F. De Comité Arbres de décision

Vérification Notes

F. De Comité Arbres de décision

Intervalles de confiance Notes

Dans 80% des cas, la valeur de la variable aléatoire est dans la

zone hachurée.

F. De Comité Arbres de décision

Intervalles de confiance Notes

Dans 90% des cas, la valeur de la variable aléatoire est dans la

zone hachurée.

F. De Comité Arbres de décision

Exemple Notes

Attribut
(15,1)
0.157

C1 C1 C0
(6,0) (9,0) (1,0)
0.206 0.143 0.75

F. De Comité Arbres de décision

Exemple Notes

Evaluation on training data (300 items) :

Before Pruning After Pruning
---------------- ---------------------------
Size Errors Size Errors Estimate

25 8( 2.7%) 7 13( 4.3%) ( 6.9%) <<

Evaluation on test data (135 items) :

Before Pruning After Pruning
---------------- ---------------------------
Size Errors Size Errors Estimate
25 7( 5.2%) 7 4( 3.0%) ( 6.9%) <<

F. De Comité Arbres de décision