Fiche d’exercices 9

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

Fiche d’exercices — Séance 9 : apprendre sans étiquettes
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 9 : k-means déroulé à la main (en une puis deux dimensions), l’inertie, le coude et la silhouette, l’effet de l’échelle, puis les fondations de l’ACP — variance, covariance, vecteurs propres — et la variance expliquée. Répondre directement sur la fiche.

Aides numériques (valables pour toute la fiche). Distance au carré : \(\lVert \mathbf x-\mathbf c\rVert^2 = \sum_j (x_j-c_j)^2\). Inertie : \(\mathcal I = \sum_k\sum_{i\in C_k}\lVert\mathbf x_i-\mathbf c_k\rVert^2\). Silhouette d’un point : \(s = \dfrac{b-a}{\max(a,b)}\) (\(a\) : distance moyenne à son cluster, \(b\) : au cluster voisin). Variance \(\operatorname{Var}(x)=\frac1n\sum_i(x_i-\bar x)^2\) ; covariance \(\operatorname{Cov}(x,y)=\frac1n\sum_i(x_i-\bar x)(y_i-\bar y)\) ; vecteur propre : \(A\mathbf v=\lambda\mathbf v\) ; variance expliquée par la composante \(i\) : \(\lambda_i/\sum_j\lambda_j\).

Exercice 1 – Une étape de k-means en une dimension

Cinq patients décrits par une seule variable : \(x = 2,\ 3,\ 4,\ 10,\ 12\). On vise \(k=2\), avec les centres initiaux (mal choisis) \(c_1 = 2\) et \(c_2 = 3\).

1. Affecter chaque point au centre le plus proche, puis recalculer les deux centres.

Espace de calcul :

clusters : \(c_1=\) \(c_2=\)

2. Réaffecter avec les nouveaux centres, puis recalculer. Continuer jusqu’à ce que plus rien ne change. Combien d’itérations ?

Espace de calcul :

clusters finaux : centres finaux :

3. Calculer l’inertie avec les centres initiaux (\(2\) et \(3\)), puis l’inertie finale. Que constate-t-on ?

Espace de calcul :

inertie initiale \(=\) inertie finale \(=\)

Exercice 2 – k-means à la main, en deux dimensions

Six patients (deux mesures exprimées sur une même échelle) : \(A(1,1)\), \(B(3,1)\), \(C(2,4)\), \(D(7,7)\), \(E(9,7)\), \(F(8,10)\). On vise \(k=2\), avec des centres initiaux volontairement médiocres : \(\mathbf c_1 = A = (1,1)\) et \(\mathbf c_2 = C = (2,4)\).

1. Affectation 1. Calculer la distance au carré de chaque point aux deux centres, puis affecter.

point	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)
\(d^2\) à \(\mathbf c_1=(1,1)\)
\(d^2\) à \(\mathbf c_2=(2,4)\)
cluster

Inertie après l’affectation 1 :

2. Mise à jour 1. Recalculer les deux centres (moyennes des clusters).

Espace de calcul :

\(\mathbf c_1=\) \(\mathbf c_2=\)

3. Affectation 2 et mise à jour 2. Quel point change de cluster ? Donner les nouveaux centres et l’inertie.

Espace de calcul :

point qui change : \(\mathbf c_1=\) \(\mathbf c_2=\) inertie \(=\)

4. Une troisième affectation change-t-elle quelque chose ? Donner l’inertie finale, et dire si k-means garantit toujours la meilleure solution.

Espace de calcul :

inertie finale \(=\)

Exercice 3 – Combien de clusters ? Coude et silhouette

1. Sur un jeu de patients, l’inertie vaut, selon \(k\) :

\(k\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)
inertie	\(900\)	\(420\)	\(180\)	\(150\)	\(128\)	\(110\)

Calculer le gain d’inertie à chaque ajout de cluster, puis désigner le « coude ».

Espace de calcul :

gains : coude : \(k=\)

2. Pourquoi ne choisit-on pas le \(k\) qui minimise l’inertie ?

3. Calculer la silhouette de trois points et interpréter chacune.

point	\(a\)	\(b\)	\(s\)	interprétation
P	\(1{,}2\)	\(4{,}0\)
Q	\(3{,}0\)	\(2{,}5\)
R	\(2{,}0\)	\(2{,}2\)

Exercice 4 – k-means et l’échelle des variables

Trois patients sont décrits par (âge en années, glycémie en g/L) : Awa \((30;\ 1{,}0)\), Binta \((34;\ 2{,}2)\), Coumba \((50;\ 1{,}0)\). Sur le jeu, âge : \(\sigma = 10\) ; glycémie : \(\sigma = 0{,}5\).

1. En unités brutes, calculer \(d^2(\text{Awa},\text{Binta})\) et \(d^2(\text{Awa},\text{Coumba})\). Qui est la plus proche d’Awa ?

Espace de calcul :

2. Diviser chaque variable par son écart-type (le centrage ne change pas les distances), puis recalculer les deux distances au carré. Qui est maintenant la plus proche ?

Espace de calcul :

3. Qu’aurait fait k-means sans standardisation sur ce jeu ?

Exercice 5 – Variance et covariance

Deux variables mesurées sur quatre patients : \(x = (1,\ 3,\ 5,\ 7)\) et \(y = (2,\ 3,\ 7,\ 8)\).

1. Calculer les moyennes, puis \(\operatorname{Var}(x)\), \(\operatorname{Var}(y)\) et \(\operatorname{Cov}(x,y)\).

patient	\(x_i-\bar x\)	\(y_i-\bar y\)	\((x_i-\bar x)^2\)	\((y_i-\bar y)^2\)	\((x_i-\bar x)(y_i-\bar y)\)
\(1\)
\(2\)
\(3\)
\(4\)
moyenne	—	—

2. Écrire la matrice de covariance. Le signe de la covariance était-il prévisible ?

Espace de calcul :

Exercice 6 – Vecteurs propres d’une matrice de covariance

Soit la matrice de covariance \(C = \begin{pmatrix} 5 & 3\\ 3 & 5\end{pmatrix}\).

1. Calculer \(C\,(1;\ 1)^\top\) et \(C\,(1;\ -1)^\top\). En déduire que ce sont des vecteurs propres, et leurs valeurs propres.

Espace de calcul :

\(\lambda_1=\) (vecteur ) \(\lambda_2=\) (vecteur )

2. Quelle est la direction de plus grande variance ? Quelle part de la variance totale porte-t-elle ?

Espace de calcul :

3. Normaliser le premier vecteur propre (longueur \(1\)). C’est la première composante principale.

Exercice 7 – La variance expliquée : combien de composantes garder ?

Une ACP sur six variables standardisées d’un registre de santé donne les valeurs propres : \[\lambda = (2{,}4;\ 1{,}2;\ 0{,}9;\ 0{,}7;\ 0{,}5;\ 0{,}3) \qquad (\text{somme} = 6).\]

1. Compléter la variance expliquée et la variance cumulée.

composante	PC1	PC2	PC3	PC4	PC5	PC6
part expliquée
cumul

2. Combien de composantes garder pour conserver au moins \(80\,\%\) de la variance ? Que perd-on en ne gardant que deux composantes pour visualiser ?

3. Pourquoi la somme des valeurs propres vaut-elle exactement \(6\) ici ? Pourquoi faut-il standardiser avant une ACP ?

Précédent
Fiche d’exercices 8

Suivant
Fiche d’exercices 10

Pour cette séance

Le cours

• Introduction au ML — Séance 9

À lire en ligne

• TP 9 — Apprentissage non supervisé