2/25/2024

UNIVERSITE SULTAN MOULAY SLIMANE

FACULTE POLYDISCIPLINAIRE
BENI MELLAL

Module :M354 : Apprentissage Automatique

Licence d'Excellence: Data Science et Sécurité des Systèmes d’Information

[Link]
Email: [Link]@[Link] 2023/2024

Apprentissage Automatique

Chapitre 3- Méthodes de classification: Analyse

discriminante, Arbres de décision et Forêts
aléatoires.
Email: [Link]@[Link]
[Link]

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

1
 2/25/2024

CART - Classification and Regression Trees

L'algorithme CART, pour Classification And Regression Tree (Breiman et al., 1984), est
employé pour former un arbre de décision. Il opère via une approche gloutonne,
récursive et divisive pour partitionner l'espace. X2

t2

t1

X1
s1 s2

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

CART - Classification and Regression Trees

CART repose sur l'utilisation d'un critère de segmentation, lequel est une mesure calculée à partir d'un
sous-ensemble de l'ensemble de données d'apprentissage. Ce critère guide le processus de prise de
décision en déterminant la caractéristique 𝑋𝑗 et la valeur T sur lesquelles la décision sera basée à chaque
nœud.

L’algorithme CART fonctionne de la manière suivante.

1. Calculer la valeur du critère de segmentation, représenté par Ci,j, pour chaque caractéristique en prenant en
compte toutes les observations pour lesquelles la valeur de 𝑋𝑗 est inférieure à 𝑡𝑗 , où 𝑡𝑗 représente la j-ème valeur
possible pour 𝑋𝑗 .

2. Choisir la caractéristique 𝑋𝑗 et le seuil 𝑡𝑗 qui minimisent l'ensemble des Ci,j,

3. Divisez les observations en deux groupes : S1 comprend celles pour lesquelles 𝑋𝑗 < 𝑡𝑗 , et S2 comprend celles pour
lesquelles 𝑋𝑗 ≥ 𝑡𝑗 .

4. Recommencer à l’étape 1 avec le sous-ensemble S1 (respectivement S2) sauf si S1 (respectivement S2) ne contient que
des observations de la même classe.

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

2
 2/25/2024

CART - Classification and Regression Trees

L'un des jeux de données les plus populaires pour illustrer la classification multi classes est l'ensemble de
données Iris, qui contient des mesures de longueur et de largeur des sépales et des pétales de trois espèces
d'iris : setosa, versicolor et virginica.
Objectif : Prédire l'espèce d'une fleur iris en fonction de ses mesures de sépales et de pétales.
Longueur Largeur Longueur Largeur
Sépale Sépale Pétale Pétale Espèce
5.1 3.5 1.4 0.2 Setosa
4.9 3 1.4 0.2 Setosa
Largeur du péta

5.8 2.6 4 1.2 Versicolor

6.7 3.1 4.7 1.5 Versicolor
6 2.2 5 1.5 Virginica
6.9 3.2 5.7 2.3 Virginica
5.4 3.9 1.3 0.4 Setosa
6.3 3.3 6 2.5 Virginica
6.4 2.8 5.6 2.2 Virginica
5.7 2.8 4.5 1.3 Versicolor
Longueur du pétale
Apprentissage Automatique Chapitre 3: Classification:
Arbres de décision

Arbre de décision- CART - Classification and Regression Trees

Un arbre de décision est un arbre qui,
• À chaque nœud interne a une règle de Longueur du pétale < 2.45
décision qui attribue de manière unique les
instances aux nœuds enfants du nœud actuel.
• À chaque nœud feuille est associée une Largeur du pétale < 1.75.
setosa
étiquette de classe.

virginica
Longueur du pétale < 4.95
Largeur du péta

Largeur du pétale ≥ 1.55

versicolor

CART partitionne les virginica

versicolor
données, ce qui produit
une frontière de décision
orthogonale aux axes
Longueur du pétale
Apprentissage Automatique Chapitre 3: Classification:
Arbres de décision

3
 2/25/2024

Arbre de décision = ensemble de règles

Longueur du pétale < 2.45

Chaque branche d'un arbre de décision peut être formulée

comme une règle conjonctive unique :
si condition1 (x) et condition2 (x) et ... et conditionk (x), setosa Largeur du pétale < 1.75.
alors y = étiquette de classe à la feuille de la branche.
Un arbre de décision est équivalent à un ensemble de telles
virginica
règles, une pour chaque branche.
Longueur du pétale < 4.95

Largeur du pétale ≥ 1.55

versicolor

Ensemble de règles :
virginica
versicolor
•Longueur du pétale < 2.45 → classe = setosa
•Longueur du pétale ≥ 2.45 et Largeur du pétale < 1.75 et Longueur du pétale < 4.95 → classe = versicolor
•Longueur du pétale ≥ 2.45 et Largeur du pétale < 1.75 et Longueur du pétale ≥ 4.95 et Largeur du pétale ≥ 1.55 → classe= versicolor
•Longueur du pétale ≥ 2.45 et Largeur du pétale < 1.75 et Longueur du pétale ≥ 4.95 et Largeur du pétale < 1.55 → classe= virginica
•Longueur du pétale ≥ 2.45 et Largeur du pétale ≥ 1.75 → classe = virginica
Apprentissage Automatique Chapitre 3: Classification:
Arbres de décision

Utiliser un arbre de décision

La classe d’une observation x dans X est prédite par : Longueur du pétale < 2.45

1. en commençant par le nœud racine,

2. à chaque nœud interne setosa Largeur du pétale < 1.75.
• évaluer la règle de décision pour x
• se diriger vers le nœud enfant sélectionné par la règle de
décision, (par défaut : gauche = « Vrai", droite = « Faux") virginica
3. une fois qu'un nœud feuille est atteint, Longueur du pétale < 4.95
• prédire la classe attribuée à ce nœud en tant que classe du
cas x. Largeur du pétale ≥ 1.55
versicolor

Example:
virginica
x : Longueur du pétale = 5, Largeur du pétale = 1.5 versicolor

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

4
 2/25/2024

Variable de séparation

À chaque nœud est associée une variable de séparation (splitting variable) 𝑗 ∈ 1, … , 𝑝 qui sera utilisée
pour partitionner les données.
Cette variable de séparation divise les données en deux régions, correspondant aux enfants du nœud en
question.
En supposant n observations 𝑥Ԧ 1 , 𝑥Ԧ 2 , …, 𝑥Ԧ 𝑛 de 𝑥 étiquetées par 𝑦Ԧ 1 , 𝑦Ԧ 2 , …, 𝑦Ԧ 𝑛 , et R régions
𝑅1 , 𝑅2 , … , 𝑅𝑅 , . . . , on peut écrire:

la variable de séparation est la variable de séparation est une la variable de séparation est une
binaire variable discrète variable réelle
𝑅𝐺 𝑗, 𝑠 = { 𝑋 : 𝑋𝑗 = 0 } 𝑅𝐺 𝑗, 𝑠 = { 𝑋 : 𝑋𝑗 ∈ 𝑆𝑒 } 𝑅𝐺 𝑗, s = { 𝑋 : 𝑋𝑗 < s }

𝑅𝐷 𝑗, 𝑠 = { 𝑋 : 𝑋𝑗 = 1 } 𝑅𝐷 𝑗, 𝑠 = { 𝑋 : 𝑋𝑗 ∈ 𝑆𝑒 } 𝑅𝐷 𝑗, 𝑠 = { 𝑋 : 𝑋𝑗 ≥ s}

Email: [Link]@[Link]
Si nous considérons une variable continue 𝑋𝑗 et supposons que les valeurs prises par cette variable dans 𝑥 soient
𝑋𝑗𝑖+𝑋𝑗𝑖+1

[Link]
ordonnées telles que 𝑋𝑗1 ≤ 𝑋𝑗2 ≤ ... ≤ 𝑋𝑗𝑛 , alors les valeurs possibles de 𝒔 sont pour toutes les valeurs de 𝑖 tells
2
que 𝑋𝑗𝑖 ≠ 𝑋𝑗𝑖+1
Apprentissage Automatique Chapitre 3: Classification:
Arbres de décision

Comment choisir une séparation ?

•CART utilise une approche gloutonne pour diviser les données à chaque
nœud.
Il évalue toutes les divisions possibles et sélectionne celle qui réduit au mieux
l'impureté des sous-ensembles résultants.

Pour les problèmes de classification, CART utilise l'impureté de Gini comme critère de
division. Plus l'impureté de Gini est faible, plus le sous-ensemble est pur.

Pour les problèmes de régression, CART utilise la réduction des résidus comme critère de
division. Plus la réduction des résidus est faible, meilleure est l'ajustement du modèle aux
Email: [Link]@[Link]

données.
[Link]

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

5
 2/25/2024

Fonction de coût - Arbre de classification

• Pour un arbre de classification, on utilisera comme fonction de coût l’indice de Gini :

• Pour un ensemble d’observations 𝑋 avec 𝑘 classes : 𝑔𝑖𝑛𝑖 𝑋 = σ𝑘𝑖=1 𝑝𝑖 1 − 𝑝𝑖

où 𝑝𝑖 est la proportion des observations de la classe 𝑖

si un ensemble de données 𝑋 est divisé en deux sous-ensembles, 𝐷1 et 𝐷2, selon l'attribut A,

l'indice de Gini est défini comme suit :
𝐷1 𝐷2
𝑔𝑖𝑛𝑖𝐴 𝑋 = 𝑔𝑖𝑛𝑖 𝐷1 + 𝑔𝑖𝑛𝑖 𝐷2
𝐷 𝐷

Tel que ∶ 𝑔𝑖𝑛𝑖 𝐷𝑖 = σ𝑘𝑖=1 𝑝𝑖 1 − 𝑝𝑖 = 1 − σ𝑘𝑖=1 𝑝𝑖2

Indice de Gini : ∆𝑔𝑖𝑛𝑖 = 𝑔𝑖𝑛𝑖 𝑋 − 𝑔𝑖𝑛𝑖𝐴 𝑋

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

Fonction de coût - Arbre de classification

En plus de l'impureté de Gini, il existe d'autres mesures d'impureté telles que l'erreur de classification et
l'entropie croisée.
Nous utiliserons la notation pc(R) pour représenter la proportion d'exemples d'entraînement dans la région R qui
appartiennent à la classe 𝑐. 1 𝑖
𝑝𝑐 𝑅 = ෍ 𝛿( 𝑦 , 𝑐)
𝑅
𝑖:𝑥Ԧ 𝑖 ∈𝑅
Erreur de classification :

L'erreur de classification est utilisée pour mesurer l'impureté d'une région R

en calculant la proportion d'exemples de cette région qui ne sont pas de la
classe majoritaire.

𝐼𝑚𝑝 𝑅 = 1 − max 𝑝𝑐 (𝑅)

𝑐=1,…,𝐶

Entropie croisée
L'entropie croisée est utilisée pour mesurer l'impureté d'une région R afin
de sélectionner la séparation qui maximise le gain d'information.
𝐶

𝐼𝑚𝑝 𝑅 = − ෍ 𝑝𝑐 𝑅 𝑙𝑜𝑔2 𝑝𝑐 (𝑅)

𝑐=1
Apprentissage Automatique Chapitre 3: Classification:
Arbres de décision

6
 2/25/2024

Impureté de Gini (CART) - Exemple

vole ? couleur classe Couleur Vole ?

non marron mammifère
non blanc mammifère
oui marron oiseau
oui blanc oiseau
marron blanc oui non
non blanc mammifère
non marron oiseau 1 mammifère 2 mammifères 3 mammifères
3 oiseaux
oui blanc oiseau 2 oiseaux 1 oiseau 1 oiseau
2 2
3 4
𝑔𝑖𝑛𝑖 𝑋 = 1 − − ≈ 0.489
7 7 2 2
1 2
𝑔𝑖𝑛𝑖 (𝑋𝑐𝑜𝑢𝑙𝑒𝑢𝑟=𝑚𝑎𝑟𝑟𝑜𝑛 ) = 1 − − ≈ 0.444 𝑔𝑖𝑛𝑖 (𝑋𝑐𝑜𝑢𝑙𝑒𝑢𝑟=𝑏𝑙𝑎𝑛𝑐 ) = 0.5
3 3
𝟑 𝟒
△ 𝒈𝒊𝒏𝒊 𝑿, 𝒄𝒐𝒖𝒍𝒐𝒓 = 𝟎. 𝟒𝟖𝟗 − ∙ 𝟎. 𝟒𝟒𝟒 − ∙ 𝟎. 𝟓 ≈ 𝟎. 𝟎𝟏𝟑
𝟕 𝟕 2 2
3 1
𝑔𝑖𝑛𝑖 (𝑋𝑣𝑜𝑙𝑒=𝑜𝑢𝑖 ) = 0 𝑔𝑖𝑛𝑖 (𝑋𝑣𝑜𝑙𝑒=𝑛𝑜𝑛 ) = 1 − − ≈ 0. 375
𝟑 𝟒 4 4
△ 𝒈𝒊𝒏𝒊 𝑿, 𝒗𝒐𝒍𝒆 = 𝟎. 𝟒𝟖𝟗 − ∙ 𝟎 − ∙ 𝟎. 𝟑𝟕𝟓 ≈ 𝟎. 𝟐𝟕𝟒
𝟕 𝟕
Apprentissage Automatique Chapitre 3: Classification:
Arbres de décision

Impureté de Gini (CART) - Exercice

– Pour illustrer comment l'impureté de Gini est calculée, considérons l'exemple suivant.
– Supposons que nous ayons un problème de classification binaire, où nous voulons prédire si une
personne achètera un produit particulier en fonction de son âge et de son revenu.

Nous voulons construire un arbre de décision pour prédire si une personne achètera le produit en fonction
de son âge et de son revenu.

Age et Revenu sont des Attributs continus Age Revenu Acheter

30 2000 Oui
Comment trouver la division avec l’indice de Gini le plus élevé ?
40 5000 Oui
• Pour chaque caractéristique continue A : 20 3000 Non
• Trier les exemples selon la valeur de A 50 6000 Non
• Pour chaque paire ordonnée (x,y) avec des étiquettes
différentes , vérifier le point médian comme seuil possible. 60 8000 Oui

Chapitre 3: Classification:
Apprentissage Automatique
Arbres de décision

7
 2/25/2024

Fonction de coût - Arbres de régression

Dans la régression (exemple ci-contre), la manière simple peut

consister à utiliser la régression linéaire pour résoudre ce cas.
Size (m2) | Nombre |Prix
Cette fois-ci, la manière de résoudre le cas de la régression utilisera | Chambre |
un arbre de décision. ------------------------------------
Pour un arbre de régression, pour calculer la fonction coût 𝐻(), il 100 |2 | 30000
150 |3 | 45000
existe plusieurs mesures d'impureté : 120 |2 | 36000
170 |4 | 50000
90 |1 | 27000
Erreur quadratique moyenne (Mean Squard Error) : Cette méthode 130 |3 | 40000
est similaire à la minimisation des moindres carrés dans un modèle linéaire. Les 180 |4 | 55000
divisions sont choisies pour minimiser la somme résiduelle des carrés entre 110 |2 | 32000
l'observation et la moyenne dans chaque nœud 𝑚 160 |3 | 48000

Email: [Link]@[Link]
1 1 140 |2 | 38000
𝐻(𝑅𝑚 ) = |𝑅 ො 2
σ𝑖∈𝑅𝑚(𝑦𝑖 − 𝑦) Où : 𝑦
ො = |𝑅 σ𝑦∈𝑅𝑚 𝑦
𝑚| 𝑚| Exemple d’un datset de régression

[Link]
Apprentissage Automatique Chapitre 3: Classification:
Arbres de décision

Fonction de coût - Arbres de régression

Déviance demi-Poisson : est une mesure utilisée dans les modèles de régression
pour évaluer l'ajustement d'un modèle de régression aux données observées.

1 𝑦𝑖 1
𝐻(𝑅𝑚 ) = σ𝑖∈𝑅𝑚 (𝑦𝑙𝑜𝑔 − 𝑦𝑖 + 𝑦)
ො Où : 𝑦ො = σ𝑦∈𝑅𝑚 𝑦
|𝑅𝑚 | 𝑦ො |𝑅𝑚 |

Erreur Absolue Moyenne (Mean Absolute Error ) : value la moyenne des écarts
absolus entre les valeurs observées et les valeurs prédites par le modèle.

1
𝐻(𝑅𝑚 ) = ෍ ( 𝑦𝑖 − 𝑚𝑒𝑑𝑖𝑎𝑛(𝑦)
ො ) Où : 𝑚𝑒𝑑𝑖𝑎𝑛(𝑦)
ො = 𝑚𝑒𝑑𝑖𝑎𝑛 𝑦
Email: [Link]@[Link]

|𝑅𝑚 | 𝑦∈𝑅𝑚
𝑖∈𝑅𝑚
[Link]

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

8
 2/25/2024

Fonction de coût - Arbres de régression

Construire un arbre de régression :

• Diviser l'espace des prédicteurs en J régions distinctes et non superposées 𝑅1 , 𝑅2 , … , 𝑅𝐽

• Pour déterminer la "meilleure" division, nous devons trouver les régions 𝑅1 , 𝑅2 , … , 𝑅𝐽 qui minimisent la
Somme des Erreurs Quadratiques Moyennes (Sum of Mean Squared Error).
𝐽
1
𝑆𝑀𝑆𝐸 = ෍ ො 2
෍ (𝑦𝑖 − 𝑦)
|𝑅𝑚 |
𝑗=1 𝑖∈𝑅𝑚

1 1
𝑆𝑀𝑆𝐸 = ො 2 +
σ𝑖∈𝑅𝑔 (𝑦𝑖 − 𝑦) ො 2
σ𝑖∈𝑅𝑔 (𝑦𝑖 − 𝑦)

Email: [Link]@[Link]
|𝑅𝑔 | |𝑅𝑑 |

[Link]
Apprentissage Automatique Chapitre 3: Classification:
Arbres de décision

Arbres de régression - exemple

X Y X Y
12 10 19 55
13 10 21 80
22 83
14 13
23 80
15 20
24 83
17.5 35 25 85
18 44 28 100
18.5 52 29 100
120

100

80
Email: [Link]@[Link]

60

40
Comment CART procède-t-il au fractionnement de
[Link]

20

0
l'ensemble de données (prédicteur = 1) ?
0 5 10 15 20 25 30 35

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

9
 2/25/2024

Arbres de régression - exemple

X Y X Y
12 10 19 55
13 10 21 80
22 83
R1 R2
14 13
23 80
15 20
24 83
17.5 35 25 85
18 44 28 100
18.5 52 29 100

Afin de déterminer la "meilleure" division, nous devons

minimiser la 𝑆𝑀𝑆𝐸 . Tout d'abord, nous calculons X<=12.5
Erreur quadratique moyenne 𝐻(𝑅𝑚 ) en divisant en #observations 15

Email: [Link]@[Link]
deux régions, en commençant par 𝑘 la première Moyenne 56.667
observation X=12. 1
𝐻(𝑅 ) =
𝑚 ෍(𝑦 − 𝑦)ො 2 𝑖
|𝑅𝑚 |
𝑖∈𝑅

[Link]
𝑆𝑀𝑆𝐸 = (10-10)2+ 1/14 *( (10-60)2+ (13-60)2+ (20-60)2+ (35-60)2+ #observations 1 #observations 14
(44-60)2+ (52-60)2+… (100-60)2 )= 925.85 Moyenne 10 Moyenne 60

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

Arbres de régression - exemple

X Y X Y
12 10 19 55
13 10 21 80
22 83
R1 R2
14 13
23 80
15 20
24 83
17.5 35 25 85
18 44 28 100
18.5 52 29 100

calculez la 𝑆𝑀𝑆𝐸 en divisant en deux régions à partir de la X<=13.5

deuxième observation #observations 15
Email: [Link]@[Link]

Moyenne 56.667
𝑆𝑀𝑆𝐸 = ½*((10-10)2+ (10-10)2 )+ 1/13 * ((13- 63.84)2+ (20- 63.84)2+ (35-
63.84)2+ (44- 63.84)2+ (52- 63.84)2+… (100- 63.84)2 )= 789.97
[Link]

#observations 2 #observations 13
Moyenne 10 Moyenne 63.84

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

10
 2/25/2024

Arbres de régression - exemple

X Y X Y
12 10 19 55
13 10 21 80
22 83
R1 R2
14 13
23 80
15 20
24 83
17.5 35 25 85
18 44 28 100
18.5 52 29 100

calculez la 𝑆𝑀𝑆𝐸 en divisant en deux régions à partir de la X<=14.5

troisième observation #observations 15

Email: [Link]@[Link]
𝑆𝑀𝑆𝐸 = 1/3 * ((10-11)2+ (10-11)2+ (13- 11)2)+ 1/12 *((20- 68.08)2+ Moyenne 56.667
(35- 68.08)2+ (44- 68.08)2+ (52- 68.08)2+… (100- 68.08)2 )= 624.40

[Link]
#observations 3 #observations 12
Moyenne 11 Moyenne 68.08

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

Arbres de régression - exemple

X Y X Y
12 10 19 55
13 10 21 80
22 83
R1 R2
14 13
23 80
15 20
24 83
17.5 35 25 85
18 44 28 100
18.5 52 29 100

calculez la 𝑆𝑀𝑆𝐸 en divisant en deux régions à partir de la X<=16.25

quatrième observation #observations 15
Email: [Link]@[Link]

Moyenne 56.667
𝑆𝑀𝑆𝐸 = 1/4* ((10-13.25)2+ (10-13.25)2+ (13- 13.25)2+ (20- 13.25)2)+
1/11* ((35- 72.45)2+ (44- 72.45)2+ (52- 72.45)2+… (100- 72.45)2 )=
[Link]

466.38
#observations 4 #observations 11
Moyenne 13.25 Moyenne 72.45

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

11
 2/25/2024

Arbres de régression - exemple

X Y X Y
12 10 19 55
13 10 21 80
R1 R2
22 83
14 13
23 80
15 20
24 83
17.5 35 25 85
18 44 28 100
18.5 52 29 100

calculez la RSS en divisant en deux régions à partir de la Cinquième X<=17.75

observation : #observations 15

Email: [Link]@[Link]
Moyenne 56.667

𝑆𝑀𝑆𝐸 = 1/5 * ((10- 17.6)2+ (10- 17.6)2+ (13- 17.6)2+ (20- 17.6)2+ (35-

[Link]
17.6)2)+ 1/10 * ((44- 76.2)2+ (52- 76.2)2+… (100- 76.2)2 )= 429.36
#observations 5 #observations 10
Moyenne 17.6 Moyenne 76.2

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

Arbres de régression - exemple

X Y X Y
12 10 19 55
13 10 21 80
R1 R2
22 83
14 13
23 80
15 20
24 83
17.5 35 25 85
18 44 28 100
18.5 52 29 100

calculez la 𝑆𝑀𝑆𝐸 en divisant en deux régions à partir de la sixième

observation : X<=18.25
𝑆𝑀𝑆𝐸 =1/6 * ( (10- 22)2+
(10-22)2+(13-22)2+ (20- 22)2+
(35- 22)2+ #observations 15
(44- 22)2)+ 1/9 * ( (52- 79.77)2+… (100- 79.77)2 )= 421.17 Moyenne 56.667

On continue le calcul pour toutes les observations. L’observation

qui présente la SMSE minimale sera considérée comme critère #observations 6 #observations 9
de division pour la racine de l'arbre. Moyenne 22 Moyenne 79.77

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

12
 2/25/2024

Méthodes de régularisation
Dans le but de prévenir le surajustement (overfitting) on recourt aux méthodes de régularisation.
Les arbres de décision ont tendance à s'adapter trop étroitement aux données d'entraînement, ce qui peut
entraîner une performance médiocre sur de nouvelles données. La régularisation permet de contrôler la
croissance de l'arbre et de limiter sa complexité, ce qui favorise une meilleure généralisation et une
réduction du surajustement.
Il existe plusieurs méthodes de régularisation simples :
• Nombre minimum de points par feuille :
exiger que chaque feuille couvre un nombre minimum donné de points d'entraînement.

• Nombre maximum de feuilles :

limiter le nombre maximum des nœuds feuilles.

• Profondeur maximale :

Email: [Link]@[Link]
limiter la profondeur maximale de l'arbre.

Le nombre de points par feuille, le nombre de feuilles, etc. peuvent être considérés comme un

[Link]
hyperparamètre de la méthode d'apprentissage de l'arbre de décision.

Apprentissage Automatique Chapitre 3: Classification:

Arbres de décision

Arbres et Forêts aléatoires (Random Forests)

Les méthodes ensemblistes, comme les forêts aléatoires, reposent sur une idée
centrale commune qui est assez intuitive :
Si un seul médecin vous annonce probablement une Vous sollicitiez l'avis d'autres personnes
maladie grave nécessitant une intervention chirurgicale. ou d'experts avant de former le vôtre.
que ferez-vous ?

Les méthodes ensemblistes reposent sur le même principe ! Plutôt que

de compter sur un seul modèle très complexe pour tout faire, elles
construisent plusieurs estimateurs de qualité individuelle moindre.
Chaque estimateur a une perspective partielle du problème et s'efforce de le résoudre
Email: [Link]@[Link]

avec les données disponibles.

[Link]

Ensuite, ces différents estimateurs sont combinés pour fournir une vue d'ensemble.

Apprentissage Automatique Chapitre 3: Classification:

Forêts aléatoires.

13
 2/25/2024

Arbres et Forêts aléatoires (Random Forests)

➢ Au lieu de construire un seul arbre de décision et l'utiliser pour faire des prédictions,
construisez plusieurs arbres légèrement différents et combinez leurs prédictions.
• Nous disposons d'un seul ensemble de données, alors comment obtenons-nous des
arbres légèrement différents ?

• 1. Bagging (Bootstrap Aggregating):

o Prenez des sous-ensembles aléatoires de points de données de l'ensemble
d'entraînement pour créer N plus petits ensembles de données.
o Ajustez un arbre de décision sur chaque sous-ensemble.

• 2. Méthode du sous-espace aléatoire (également connue sous le nom de Feature

Bagging) :
o Ajustez N arbres de décision différents en contraignant chacun à fonctionner sur un
sous-ensemble aléatoire de fonctionnalités.

Apprentissage Automatique Chapitre 3: Classification:

Forêts aléatoires.

Méthodes parallèles : Bagging

Supposons n observations 𝑥Ԧ 1 , 𝑥Ԧ 2 , …, 𝑥Ԧ 𝑛 de 𝑥 étiquetées par 𝑦Ԧ 1 , 𝑦Ԧ 2 , …, 𝑦Ԧ 𝑛

➢ Le bagging, introduit par Leo Breiman (1996), implique la création de B

versions de l'ensemble de données 𝑥 par échantillonnage.
➢ Chaque modèle faible est formé sur l'un de ces échantillons, ce qui peut être
réalisé de manière parallèle. Ensuite, les B prédictions sont combinées de la
manière suivante :
o Pour un problème de classification, elles sont combinées par vote
majoritaire.
Email: [Link]@[Link]

o Pour un problème de régression, elles sont combinées en prenant la

moyenne.
[Link]

Apprentissage Automatique Chapitre 3: Classification:

Forêts aléatoires.

14
 2/25/2024

Bagging : phase de l'entraînement

N sous-ensembles (avec
remplacement)

Algorithme
d'apprentissage
AD
Données
d’entraînement
Algorithme
d'apprentissage
AD

Algorithme
d'apprentissage
AD

Algorithme
d'apprentissage
AD

Apprentissage Automatique Chapitre 3: Classification:

Forêts aléatoires.

Bagging – phase de Test

Un échantillon de
test

Vote

Prédiction finale: 75%

Apprentissage Automatique Chapitre 3: Classification:

Forêts aléatoires.

15
 2/25/2024

Méthode du sous-espace aléatoire lors de l'apprentissage

Elle consiste à entraîner plusieurs modèles des arbres de décision) sur des sous-ensembles aléatoires des
caractéristiques (ou des colonnes) des données. Cela permet de créer une diversité parmi les modèles individuels et de
réduire le surajustement (overfitting).

Algorithme

Couleur
Couleur
Données d'apprentissage
d’entraînement AD

Couleur Poids(g) ph Texture Classe Poids Poids

Orange 101 3.7 Lisse Orange
Rouge 85 3.3 Lisse Pomme
Rouge 117 3.4 Rugueux Orange Texture Algorithme

Texture
Vert 83 3.5 Lisse Pomme d'apprentissage
Vert 111 3.5 Rugueux Pomme AD
…
Orange 121 3.9 Rugueux Orange

Algorithme
d'apprentissage
AD

Poids Poids

Apprentissage Automatique Chapitre 3: Classification:

Forêts aléatoires.

Méthode du sous-espace aléatoire lors de Test

les prédictions des différents

modèles peuvent être combinées
de différentes manières, comme
par un vote majoritaire, pour
Couleur

obtenir une prédiction finale.

Un échantillon de Poids
test

Rouge 87 3.2 Lisse ? Vote

Prédiction finale: 66%

Poids

Apprentissage Automatique Chapitre 3: Classification:

Forêts aléatoires.

16
 2/25/2024

Méthodes séquentielles : Boosting

Réajuster en fonction
Tous les échantillons
des erreurs du modèle
ont le même poids.

Réajuster en
fonction des erreurs
du modèle actuel.

Email: [Link]@[Link]
L’approche séquentielle du boosting vise à construire un ensemble de modèles faibles

[Link]
focalisés sur les erreurs du modèle. À chaque itération, des apprenants faibles sont
ajoutés pour renforcer les performances du modèle final.
Apprentissage Automatique Chapitre 3: Classification:
Forêts aléatoires.

Méthodes séquentielles : Boosting

Le modèle suivant prend en compte

les échantillons pondérés

Entraîner les modèles de manière itérative, tout en amenant le modèle actuel à se

concentrer sur les erreurs des précédents en augmentant le poids des échantillons mal
classés.
Apprentissage Automatique Chapitre 3: Classification:
Forêts aléatoires.

17
 2/25/2024

Méthodes séquentielles : Boosting

Entraîner les modèles de manière itérative, tout en amenant le modèle actuel à se
concentrer sur les erreurs des précédents en augmentant le poids des échantillons mal
classés.

Vote

Apprentissage Automatique Chapitre 3: Classification:

Forêts aléatoires.

Méthodes ensemblistes - Forêts aléatoires

Couleur Poids(g) ph Texture Classe
Orange 101 3.7 Lisse Orange
Rouge 85 3.3 Lisse Pomme
Rouge 117 3.4 Rugueux Orange
Vert 83 3.5 Lisse Pomme
Vert 111 3.5 Rugueux Pomme
…
Orange 121 3.9 Rugueux Orange

Méthode du sous-espace aléatoire +

Algorithme d'apprentissage d'arbre de décision

Arbre 1 Arbre 2 Forêts aléatoires Arbre N

Apprentissage Automatique Chapitre 3: Classification:

Forêts aléatoires.

18
 2/25/2024

Méthodes ensemblistes - Forêts aléatoires

• Les méthodes ensemblistes combinent plusieurs algorithmes d'apprentissage pour obtenir des
améliorations de performances par rapport à leurs composants.

• Méthodes d'ensemble couramment utilisées :

➢ Bagging (utilisation de plusieurs modèles sur des sous-ensembles aléatoires d'échantillons de
données)
➢ Méthode du sous-espace aléatoire (utilisation de plusieurs modèles sur des sous-ensembles
aléatoires de caractéristiques)
➢ Boosting (entraînement de modèles de manière itérative, tout en amenant le modèle actuel à
se concentrer sur les erreurs des précédents en augmentant le poids des échantillons mal
classés)

• Les Forêts Aléatoires sont une méthode d'apprentissage ensembliste qui utilise
l'apprentissage par arbre de décision pour construire plusieurs arbres grâce au bagging et à
la méthode du sous-espace aléatoire. Elles corrigent le problème de surajustement des
arbres de décision !
Apprentissage Automatique Chapitre 3: Classification:
Forêts aléatoires.

19