Introduction au ML
Arbre de décisions
Faten Chakchouk
Enseignant - Chercheur
Brest Cancer : Tumeur bénigne ou maligne ?
from [Link] import load_breast_cancer
breast_cancer = load_breast_cancer()
print(breast_cancer.DESCR)
**Data Set Characteristics:**
:Number of Instances: 569
:Number of Attributes: 30 numeric, predictive attributes and the class
:Attribute Information:
- radius (mean of distances from center to points on the perimeter)
- texture (standard deviation of gray-scale values)
- perimeter
- area
- smoothness (local variation in radius lengths)
- compactness (perimeter^2 / area - 1.0)
- concavity (severity of concave portions of the contour)
- concave points (number of concave portions of the contour)
- symmetry
- fractal dimension ("coastline approximation" - 1)
Brest Cancer : Tumeur bénigne ou maligne ?
Brest Cancer : Tumeur bénigne ou maligne ?
Concave points
<=0.051 un nœud
Arcs : Réponses
possibles au test du Test sur un unique
True False
nœud attribut.
Radius Radius
<=14.98 <=11.345
Feuilles de
l’arbre = classes
257 Benign 9 Benign 4 Benign 15 Benign
7 malignant 11 malignant 0 malignant 152 malignant
Benign Malignant Benign Malignant
Arbres de décision
Définitions
Les arbres de décision ont une structure hiérarchique et sont composés de nœuds et de
feuilles reliés par des branches (arcs).
La racine est placée en haut et les feuilles en bas.
Les nœuds internes sont appelés des nœuds de décision. Ils peuvent contenir une ou plusieurs
règles (aussi appelées tests ou conditions).
La racine constitue le point de départ de l'arbre et représente l'ensemble des données
d'apprentissage.
Ces données sont segmentées en plusieurs sous-groupes, en fonction d'une variable
discriminante (un des attributs).
Instances ou attributs : Les valeurs que peut prendre une variable dans un arbre de décision.
Les feuilles de l’arbre : les classes à prédire ou variable cible (classification ou régression).
Après sa construction, un arbre de décision peut être traduit sous la forme
d’un ensemble de règles de décision.
Arbre de décision
Exemple 2
Température
>37
Classification : Malade ou sain
Attributs : température, Toux Oui Non
Malade Toux
Une fois l'arbre construit à partir des données
d'apprentissage, on peut prédire un nouveau cas en le
faisant descendre le long de l'arbre, jusqu'à une
feuille.
Malade Sain
Arbre de décision
Exemple 3
◉ Quelle variable discrimine le mieux l’ensemble
des données et laquelle doit être considérée en
premier ?
◉ Si plusieurs structures d’arbre répondent aux
situations décrites laquelle doit-on choisir ?
◉ Quel critère permet de maximiser la robustesse
de l’arbre ?
Arbre de décision
Algorithme générique d’apprentissage
Arbre de décision
Algorithme d’apprentissage
Nœud Terminal?
− Lorsque (presque) tous les exemples de S
en ce nœud sont dans la même classe, Sélection d’un test ?
− Lorsqu’il n’y a plus d’attributs à tester à ce Choix de l’attribut qui fait le mieux progresser la
niveau discrimination des données de S : Maximiser le
gain en information.
Quelle classe à un Nœud terminal ? − Indice de Gini (CART)
− La Classe majoritaire − Critère d’entropie (ID3, C4.5)
− La Classe la plus représentée, si égalité
Arbre de décision
Entropie et gain d’informations
Entropie Soit un ensemble de données T caractérisé par n
− L’Entropie d’une distribution de probabilité classes (C1, C2, ..., Cn) selon une variable cible.
La quantité d’informations nécessaire pour
identifier la classe d’un individu de l’ensemble T
correspond à l’entropie E(P), où P est la
distribution de probabilité de la partition (C1, C2, ...,
Cn) :
log désigne la fonction de logarithme en base 2.
Arbre de décision
Entropie et gain d’informations
Données Entropie
o S un échantillon, y l’attribut cible 𝐒𝐢 𝑺𝒊
𝐤
o S1, ...Sk partition de S selon les classes de y E(S) = -∑𝐢"𝟏 log 𝟐
𝐒 𝑺
Exemple
variable cible y
La variable cible « jouer » prend deux valeurs
: Oui (9) et Non (5)
o S1 ={J1,J2,J6,J8,J14}; S! =5
o S2 ={J3,J4,J5,J7,J9, J10,J11,J12,J13}; S" =9
𝟗 𝟗 𝟓 𝟓
E(S) = − 𝐥𝐨𝐠 𝟐 − 𝐥𝐨𝐠 𝟐 = 𝟎, 𝟗𝟒
𝟏𝟒 𝟏𝟒 𝟏𝟒 𝟏𝟒
Arbre de décision
Entropie et gain d’informations
Entropie par rapport à un attribut X E(X,T) Gain en Information de l’attribut X
Gain d’ Entropie de X
Supposons que l’ensemble des données T est,
partitionnée en (T1, T2, ..., Tm).
m : nombre de valeurs que peut prendre
l’attribut X considéré.
Quantité d’Information nécessaire pour
identifier la classe d’un individu de Tj
Arbre de décision
Entropie et gain d’informations
Comment choisir un test parmi les attributs disponibles ?
Calculer le Gain d’information pour chaque attribut
Sélection de l’attribut qui maximise le Gain en
Information
Arbre de décision
Entropie et gain d’informations
Comment choisir un test parmi les attributs disponibles ?
Exemple
Calculer le Gain en Information pour chaque
attribut ?
1. Gain(Ciel)
2. Gain(Temp.)
3. Gain (Humidité)
4. Gain (Vent)
𝟗 𝟗 𝟓 𝟓
E(Jouer) = − 𝐥𝐨𝐠 𝟐 − 𝐥𝐨𝐠 𝟐 = 𝟎, 𝟗𝟒
𝟏𝟒 𝟏𝟒 𝟏𝟒 𝟏𝟒
Arbre de décision
Entropie et gain d’informations : Exemple
Peut prendre une des trois valeurs Soleil, Couvert,
Pluie
Variable : Ciel ---- 3 partitions
dont les éléments appartiennent
à l’une des classes de « Jouer »
Arbre de décision
Entropie et gain d’informations : Exemple
Arbre de décision
Entropie et gain d’informations : Exemple
Arbre de décision
Entropie et gain d’informations : Exemple
Remarque :
Pour calculer log2 à partir de logb
Arbre de décision
Entropie et gain d’informations : Exemple
Pour la branche Soleil, le gain est recalculé pour les attributs Température,
Humidité et Vent seulement pour les jours où l’attribut Ciel = Soleil
Arbre de décision
Indice de Gini et gain d’informations
Indice de Gini
Mesure l’impureté mesure le taux d'impureté de la
distribution des classes de points de données, ou le taux
de mélange des classes.
Plus l’indice de Gini est faible, plus le mélange est pur.
Par exemple, lorsque l'ensemble de données ne
contient qu'une seule classe :
- Proportion de la classe =1.
- IG= 1- (12+ 02 ) = 0.
Gain de Gini
- j
Arbre de décision
Indice de Gini et gain d’informations
Comment choisir un test parmi les attributs disponibles ?
Calculer le Gain d’information pour chaque attribut
Sélection de l’attribut qui maximise le Gain en Information.
OU Bien Sélection de l’attribut qui minimise :
Rappel : Type de variables/Attributs
Variable
catégorique Numérique
nominale ordinale Continue Discrète
Arbre de décision
Indice de Gini et gain d’informations
Comment choisir un test parmi les attributs disponibles ?
Attribut catégorique
Division multiple : autant de partitions que de valeurs distinctes.
Taillee
petite Moyenne Large
Division binaire : Division des valeurs en deux sous-ensembles ⇒ Trouver le
partitionnement optimal.
OU Taillee OU Taillee
Taillee
Petite, Moyenne Large Large, Moyenne
Petite, Large Moyenne Petite
Arbre de décision
Indice de Gini et gain d’informations
Comment choisir un test parmi les attributs disponibles ?
Attribut numérique continu
Différentes manières de discrétiser :
Revenu imposable > 80K Revenu imposable?
Oui Non
< 𝟏𝟎𝑲 > 𝟖𝟎𝑲
[𝟏𝟎𝑲, 𝟐𝟓𝑲) [𝟐𝟓𝑲, 𝟓𝟎𝑲) [𝟐𝟓𝑲, 𝟓𝟎𝑲)
Division binaire Discrétisation pour former un attribut ordinal.
Arbre de décision
Indice de GINI
Exemple
Calculer le Gain en Information pour chaque
attribut en se basant sur l’indice de GINI ?
1. Gain(Ciel)
2. Gain(Temp.)
3. Gain (Humidité)
4. Gain (Vent)
𝟐 𝟐
𝟗 𝟓
IG (Jouer) = 𝟏 − 𝟏𝟒 −
𝟏𝟒
= 𝟎, 𝟒𝟔
Arbre de décision
Indice de GINI
Exemple Cas division multiple 𝟐 𝟐
𝟗 𝟓
IG (Jouer) = 𝟏− −
𝟏𝟒 𝟏𝟒
Pour Ciel=Soleil : 5 observations (2 oui et 3 Non)
I(Ciel=Soleil) =1-(2/5)2-(3/5)2= 12/25=0,48
Pour Ciel=Couvert : 4 observations (4 Oui,0 Non)
I(Ciel=Couvert ) = 1-(4/4)2-(0/4)2= 0
Pour Ciel=Pluie : 5 observations (3 oui et 2 Non)
I(Ciel= Pluie) =1-(3/5)2-(2/5)2= 12/25
IG(Ciel) = 5/14 x I(Ciel=Soleil) +4/14 x I(Ciel=Couvert )+5/14 I(Ciel= Pluie)
= 12/35 = 0,34
Arbre de décision
Indice de GINI
Exemple Cas division binaire 𝟐 𝟐
𝟗 𝟓
IG (Jouer) = 𝟏− −
𝟏𝟒 𝟏𝟒
Pour Ciel=Soleil, Pluie : 10 observations (5 oui et 5
Non)
I(Ciel=Soleil/Pluie) =1-(5/10)2-(5/10)2= 0,5
Pour Ciel=Couvert : 4 observations (4 Oui,0 Non)
I(Ciel=Couvert ) = 1-(4/4)2-(0/4)2= 0
IG(Ciel) = 10/14 x I(Ciel=Soleil/Pluie) +4/14 x I(Ciel=Couvert )
= 10/14 * 0,5= 0,36
Arbre de décision
Entropie et gain d’informations - Exemple 2
Données : un tableau d'observations
Problème :
Pourquoi certains attrapent un coup de soleil ? Comment prédire le résultat
pour une nouvelle personne (coup de soleil ou RAS : Rien A Signaler) ?
Arbre de décision
Indice de Gini et gain d’informations - Exemple 2
Données : un tableau d'observations
Problème :
Comment prédire le résultat internet pour un client (le client consulte ses
comptes sur internet ou non ) ?
