Fiche d’exercices 3

Fiche d’exercices de la séance 3 d’Introduction au Machine Learning.
Auteurs

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

Fiche d’exercices — Séance 3 : l’apprentissage supervisé et l’arbre de décision
Introduction au ML – Dr. El Hadji Bassirou TOURÉ – DMI \(\cdot\) FST \(\cdot\) UCAD \(\bullet\) Travail à la main, sans machine

Cette fiche reprend, exercice par exercice, les calculs de la Séance 3 : accuracy et baseline, dimensions et découpage, le modèle d’arbre en formule, entropie et Gini, la construction d’un arbre à la main, puis le diagnostic par la profondeur. Répondre directement sur la fiche.

Aides numériques (valables pour toute la fiche). \(\log_2 3 = 1{,}585\). Entropie d’un nœud binaire dont une classe occupe la proportion \(p\) :

\(p\) \(1/2\) \(1/4\) ou \(3/4\) \(1/3\) ou \(2/3\) \(2/5\) ou \(3/5\) \(1/5\) ou \(4/5\)
\(H\) \(1{,}000\) \(0{,}811\) \(0{,}918\) \(0{,}971\) \(0{,}722\)

Un nœud pur (une seule classe) a \(H = 0\).

Exercice 1 – Accuracy et baseline

Au dispensaire de Tivaouane, un modèle de dépistage a été testé sur \(10\) patients (P \(=\) paludisme, N \(=\) sain) :

patient 1 2 3 4 5 6 7 8 9 10
réalité \(y_i\) N N P N N N P N N N
prédiction \(\hat y_i\) N P P N N N N N P N
verdict (✓ ou \(\times\))
  1. Remplir la ligne « verdict » en comparant \(y\) et \(\hat y\) composante par composante.

Nombre de prédictions correctes :

  1. En déduire l’accuracy du modèle.

Espace de calcul :

accuracy \(=\)

  1. Calculer l’accuracy de la baseline majoritaire (le modèle qui prédit toujours la classe la plus fréquente du tableau).

Espace de calcul :

Classe majoritaire : accuracy de la baseline \(=\)

  1. Comparer les deux accuracies et conclure : ce modèle apporte-t-il quelque chose ?

Exercice 2 – Dimensions et découpage

Une cohorte de Kaolack compte \(1\,200\) patients, chacun décrit par \(5\) caractéristiques (âge, glycémie, hémoglobine, fièvre, saison) ; la cible est le paludisme, présent chez \(12\,\%\) des patients.

  1. Dimensions de la matrice de design \(X\) : du vecteur cible \(y\) :

  2. Découpage train/test à \(75/25\).

Espace de calcul :

Train : patients Test : patients

  1. Le découpage est stratifié.

Espace de calcul :

Positifs dans le train : positifs dans le test :

  1. Sans stratification, qu’est-ce qui pourrait mal se passer ?

Exercice 3 – Le modèle en formule : la somme d’indicatrices

La Séance 3 définit l’arbre formellement : il partitionne l’espace des entrées en \(M\) régions disjointes \(R_1, \dots, R_M\) (les feuilles) et prédit \[f(x) \;=\; \sum_{m=1}^{M} \hat c_m \, \mathbf{1}[x \in R_m],\] où \(\mathbf{1}[\cdot]\) vaut \(1\) si la condition est vraie et \(0\) sinon, et où \(\hat c_m\) est la classe majoritaire des exemples d’entraînement tombés dans \(R_m\).

Au poste de santé de Ziguinchor, l’arbre suivant a été construit (cible codée P \(= 1\), N \(= 0\)) : la racine applique la coupure (fièvre, \(38{,}5\)) ; le nœud droit (fièvre \(\geq 38{,}5\)) applique ensuite la coupure (âge, \(30\)) ; le nœud gauche est une feuille. Répartition des exemples d’entraînement :

feuille condition exemples d’entraînement
\(R_1\) fièvre \(< 38{,}5\) \(1\) P et \(3\) N
\(R_2\) fièvre \(\geq 38{,}5\) et âge \(< 30\) \(3\) P et \(0\) N
\(R_3\) fièvre \(\geq 38{,}5\) et âge \(\geq 30\) \(0\) P et \(1\) N
  1. Déterminer les classes majoritaires (en code \(0/1\)) : \(\hat c_1 =\) \(\hat c_2 =\) \(\hat c_3 =\)

Écrire la formule complète de \(f(x)\) pour cet arbre :

\(f(x) =\)

  1. Pour chacun des trois patients, calculer les indicatrices une à une, puis \(f(x)\) :
patient \(x\) \(\mathbf{1}[x \in R_1]\) \(\mathbf{1}[x \in R_2]\) \(\mathbf{1}[x \in R_3]\) \(f(x)\) prédiction (P/N)
(fièvre \(39{,}0\), âge \(24\))
(fièvre \(38{,}0\), âge \(70\))
(fièvre \(40{,}2\), âge \(55\))
  1. Combien d’indicatrices valent \(1\) simultanément dans chaque cas ?

Expliquer pourquoi il ne peut pas en être autrement, et ce que cela implique pour la somme \(\sum_m \hat c_m \mathbf{1}[x \in R_m]\).

  1. Écrire les deux coupures de l’arbre sous la forme \((j, s)\) de la séance :

nœud racine : \((j, s) =\) nœud droit : \((j, s) =\)

  1. Les régions \(R_1, R_2, R_3\) recouvrent-elles tout l’espace des entrées ? Justifier, puis dire ce qui se passerait pour \(f\) si une zone n’était couverte par aucune région.

Exercice 4 – Entropie et indice de Gini

Trois nœuds d’un arbre contiennent : nœud \(A\) : \(8\) P / \(0\) N nœud \(B\) : \(4\) P / \(4\) N nœud \(C\) : \(6\) P / \(2\) N

  1. Sans aucun calcul, classer les trois nœuds du plus pur au moins pur :

  2. Calculer l’entropie \(H = -\sum_k p_k \log_2 p_k\) de chaque nœud. Pour le nœud \(C\), détailler le calcul à partir de \(\log_2 3 = 1{,}585\).

\(H_A =\) \(H_B =\)

\(H_C\), calcul détaillé :

  1. Calculer l’indice de Gini \(G = 1 - \sum_k p_k^2\) des trois nœuds.

Espace de calcul :

\(G_A =\) \(G_B =\) \(G_C =\)

  1. Les deux mesures donnent-elles le même classement qu’en (a) ?

Valeurs extrêmes possibles pour un nœud à deux classes : \(H \in\) \(G \in\)

Exercice 5 – Construire l’arbre à la main

Huit patients du district de Thiès (cible : paludisme, P/N) :

patient fièvre (°C) âge (ans) cible
1 \(37{,}2\) \(25\) N
2 \(37{,}8\) \(45\) N
3 \(38{,}0\) \(19\) N
4 \(38{,}2\) \(33\) P
5 \(38{,}9\) \(7\) P
6 \(39{,}4\) \(15\) P
7 \(39{,}8\) \(22\) P
8 \(40{,}1\) \(61\) N

Gain d’une coupure : \(\;\text{gain} = H(\text{parent}) - \big(\tfrac{n_g}{n} H(\text{gauche}) + \tfrac{n_d}{n} H(\text{droite})\big)\).

  1. Entropie de la racine : composition (P/N) : \(\Rightarrow\) \(H(\text{racine}) =\)

  2. Le duel. Deux coupures candidates pour la racine : A \(= (\text{fièvre},\ 38{,}5)\) et B \(= (\text{âge},\ 30)\). Compléter :

coupure gauche (P/N) \(H(\text{gauche})\) droite (P/N) \(H(\text{droite})\) gain
A : (fièvre, \(38{,}5\))
B : (âge, \(30\))

Espace de calcul :

Coupure retenue : Justification :

  1. Purifier le nœud gauche (fièvre \(< 38{,}5\), patients \(1\) à \(4\)). Deux candidates : (fièvre, \(38{,}1\)) et (âge, \(30\)).

Espace de calcul :

gain de (fièvre, \(38{,}1\)) \(=\) gain de (âge, \(30\)) \(=\) retenue :

  1. Purifier le nœud droit (fièvre \(\geq 38{,}5\), patients \(5\) à \(8\)) avec la candidate (âge, \(30\)).

Espace de calcul :

gain \(=\) Pourquoi la construction s’arrête-t-elle ici ?

  1. Dessiner l’arbre final (nœuds avec leurs coupures, feuilles avec leur classe), puis vérifier qu’il classe correctement les \(8\) patients d’entraînement.

  2. Nouveau patient : fièvre \(38{,}3\), âge \(28\). Suivre son chemin nœud par nœud et donner la prédiction.

Prédiction :

  1. Retour à la formule. Écrire les régions \(R_1, \dots, R_4\) de l’arbre final et la valeur \(\hat c_m\) de chacune — autrement dit, le \(f(x)\) de l’exercice 3 pour cet arbre.
région condition \(\hat c_m\)
\(R_1\)
\(R_2\)
\(R_3\)
\(R_4\)

\(f(x) =\)

Exercice 6 – Profondeur et diagnostic

Sur un jeu de dépistage, trois arbres ont été entraînés puis évalués. Baseline majoritaire : \(0{,}61\).

profondeur accuracy train accuracy test écart train \(-\) test diagnostic
\(2\) \(0{,}74\) \(0{,}73\)
\(5\) \(0{,}85\) \(0{,}83\)
\(14\) \(0{,}99\) \(0{,}76\)

  1. Remplir la colonne des écarts.

  2. Remplir la colonne diagnostic (sous-ajusté / bien ajusté / sur-ajusté), puis justifier chaque diagnostic en une phrase, en s’appuyant sur les écarts et sur la baseline.

profondeur \(2\) :

profondeur \(5\) :

profondeur \(14\) :

  1. Profondeur à retenir : sur la foi de quel chiffre ?

  2. L’arbre de profondeur \(14\) a la meilleure accuracy d’entraînement. Expliquer pourquoi ce chiffre ne doit jamais servir à choisir un modèle.

Pour cette séance

Le cours

À lire en ligne

Retour au sommet