Données :
| x1 | x2 |
|---|---|
| 4 | 3 |
| 2 | 4 |
| 1 | 5 |
| 1 | 1 |
| 2 | 1 |
| 5 | 3 |
Appliquez en détaillant raisonnablement chaque étape l'algorithme des k-means avec $K=2$.
Prenez comme centres initiaux $c_1 = (2,3)$ et $c_2 = (5,5)$ dans un premier temps.
Choisissez ensuite $c_2 = (1,3)$ sans changer $c_1$. Que remarquez-vous ?
Appliquez ensuite l'algorithme CAH "complete linkage" sur ces mêmes données. Dessinez le dendrogramme.
plotCtrs = function(ctrs) {
data = matrix(c(4,3, 2,4, 1,5, 1,1, 2,1, 5,3), byrow=TRUE, ncol=2)
plot(data, xlim=c(0,6), ylim=c(0,6), pch=3, xlab="x1", ylab="x2")
text(c(4,2,1,1,2,5) - 0.2, c(3,4,5,1,1,3), as.character(1:6))
par(new=TRUE)
plot(matrix(ctrs, byrow=TRUE, ncol=2), col=2, xlim=c(0,6), ylim=c(0,6), pch=16, xlab="", ylab="")
grid()
}
plotCtrs(c(2,3, 5,5))
text(c(2,5) - 0.2, c(3,5), c("c1","c2"), col=2)
On obtient facilement les distances (euclidiennes au carré) à $c_1$ respectivement pour les points 1, 2, ..., 6 : (4, 1, 5, 5, 4, 9) et (5, 10, 16, 32, 25, 4). On en déduit deux groupes suite à la première affectation : (1, 2, 3, 4, 5) et 6 (isolé).
On recalcule alors les centres : $c_1 = (\frac{4+2+1+1+2}{5}, \frac{3+4+5+1+1}{5}) = (2, 2.8)$ et $c_2 = (5, 3)$ (un seul point : pas de calcul à faire pour $c_2$).
plotCtrs(c(2,2.8, 5,3))
text(c(1.8, 5.2), c(2.8, 3), c("c1","c2"), col=2)
Les distances euclidiennes sont alors un peu plus compliquées à calculer car $c_1$ n'est pas sur la grille. On peut cependant s'épargner le calcul dans ce cas simple où il est évident graphiquement que le point 1 passe dans le second cluster, tandis que les 4 autres points restent nettement plus proches de $c_1$.
On recalcule les centres : $c_1 = (\frac{2+1+1+2}{4}, \frac{4+5+1+1}{4}) = (1.5, 2.75)$ et $c_2 = (\frac{4+5}{2}, \frac{3+3}{2} = (4.5, 3))$
plotCtrs(c(1.5,2.75, 4.5,3))
text(c(1.5, 4.5) - 0.2, c(2.75, 3), c("c1","c2"), col=2)
L'algorithme a alors convergé (évidence graphique : les compositions ne changent plus).
Essayons avec comme centre initial $c_2 = (1,3)$ :
plotCtrs(c(2,3, 1,3))
text(c(2,1) - 0.2, c(3,3), c("c1","c2"), col=2)
Graphiquement les points 3 et 4 sont plus proches de $c_2$, et de même les points 2 et 5 sont plus proches de $c_1$. Il est clair que 1 et 6 sont plus proches de $c_1$ également. D'où les regroupements initiaux en (1, 2, 5, 6) et (3, 4).
Recalcul des centres : $c_2$ ne bouge pas (il est déjà au milieu du segment 3-4). $c_1 = (\frac{2+2+4+5}{4}, \frac{1+3+3+4}{4}) = (3.25, 2.75)$
plotCtrs(c(3.25,2.75, 1,3))
text(c(3.25,1) - 0.2, c(2.75,3), c("c1","c2"), col=2)
Graphiquement, Les points 1 et 6 restent dans le cluster 1 tandis que 3 et 4 restent dans l'autre. Le point 2 passe dans le second groupe, et pour 5 il faut calculer :
$d^2(p_5, c_1) = (2 - 3.25)^2 + (1 - 2.75)^2 = 4.625$ et $d^2(p_5, c_2) = (2 - 1)^2 + (1 - 3)^2 = 5$.
On obtient donc à l'issue de cette itération deux groupes : (1, 5, 6) et (2, 3, 4).
Recalcul des centres : $c_1 = (\frac{2+4+5}{3}, \frac{1+3+3}{3}) = (3.67, 2.33)$ et $c_2 = (\frac{1+2+1}{3}, \frac{1+4+5}{3}) = (1.33, 3.33)$.
plotCtrs(c(3.67,2.33, 1.33,3.33))
text(c(3.67,1.33) - 0.2, c(2.33,3.33), c("c1","c2"), col=2)
Le groupe du point 5 reste visuellement ambigu (les autres sont clairs).
$d^2(p_5, c_1) = (2 - 3.67)^2 + (1 - 2.33)^2 = 4.6$ et $d^2(p_5, c_2) = (2 - 1.33)^2 + (1 - 3.33)^2 = 5.9$.
L'algorithme a donc convergé, vers des groupes différents : illustration de la sensibilité de l'algorithme aux conditions initiales.
Concernant l'algorithme CAH, il est clair que trois groupes vont se former dans un premier temps : $G_1$ 1-6, $G_2$ 4-5 (ordre arbitraire) puis $G_3$ 2-3. Il n'y a plus que trois distances à calculer, correspondants aux plus grands écarts inter-points :
$d^2(G_1, G_2) = d^2(p_4, p_6)$ (évidence graphique) $ = 20$.
$d^2(G_1, G_3) = d^2(p_3, p_6) = 20$.
$d^2(G_2, G_3) = d^2(p_3, p_5) = 17.
On fusionne donc d'abord $G_2$ et $G_3$, puis $G_1$ avec le reste, obtenant le dendrogramme suivant.
Modélisez la situation par une chaîne de Markov.
Combien de joueurs parviennent à passer les 6 épreuves ? (Justifiez)
Quelle est la probabilité de gagner ? (Expliquez le calcul)
Modifiez la modélisation pour prendre cela en compte.
Comment est impactée qualitativement la probabilité de gagner ? (Justifiez).
Il est clair qu'il faudra un état par manche (signifiant "on est en train de jouer cette manche"), donc au moins 6. Ensuite on pourra considérer qu'être éliminé et refuser de jouer revient au même (dans les deux cas on ne gagne rien - bien sûr dans la série on meurt, mais ce n'est pas spécifié dans l'énoncé, et donc hors sujet) : appelons cet état "R". Enfin on peut gagner : état "G". Il faut aussi un état initial lorsque l'on décide de jouer ou non : appelons-le "I".
Depuis I on peut d'après l'énoncé se rendre en R ou bien 1 (première manche). Quand on a atteint R on y reste, et de même pour G. Enfin, depuis une manche 1 à 5 on peut progresser vers la suivante ou bien vers l'état R. Depuis le 6eme et dernier jeu on va vers R ou G. Sans plus d'information on suppose l'équiprobabilité, et donc si la moitié des joueurs est éliminée après chaque jeu notre probabilité de succès vaut 0.5.
À l'issue d'une épreuve le nombre de participants est réduit de moitié, donc au bout de $n$ jeux leur nombre est divisé par $2^n$ (récurrence immédiate disons...). Après 6 épreuves on obtient alors $\frac{64}{2^6} = \frac{64}{64} = 1$ unique vainqueur.
Pour gagner il ne faut pas refuser de jouer, puis remporter chaque épreuve. La probabilité se calcule donc comme un produit $0.95 \times 0.5 \times \dots \times 0.5$, avec autant de 0.5 qu'il y a de jeux. On gagne alors avec probabilité $0.95 \times 0.5^6 \simeq 0.0078$.
En fait on peut garder la modélisation (presque) telle quelle, l'état R valant également pour "on a arrêté le jeu". Les états et transitions ne changent pas, mais les probabilités d'évoluer de 1 à 2 puis 2 à 3 etc s'en trouvent affectée : elles diminuent légèrement (proportionnellement à la probabilité d'arrêter le jeu, qui peut évoluer au fil des manches). Notant $a_1, \dots, a_6$ les probabilités d'arrêter le jeu avant ou pendant les épreuves correspondantes, on obtient :
$$\begin{pmatrix} & I & 1 & 2 & 3 & 4 & 5 & 6 & G & R\\ I & 0 & 0.95 & 0 & 0 & 0 & 0 & 0 & 0.05\\ 1 & 0 & 0 & 0.5 - a_1 & 0 & 0 & 0 & 0 & 0 & 0.5 + a_1\\ 2 & 0 & 0 & 0 & 0.5 - a_2 & 0 & 0 & 0 & 0 & 0.5 + a_2\\ 3 & 0 & 0 & 0 & 0 & 0.5 - a_3 & 0 & 0 & 0 & 0.5 + a_3\\ 4 & 0 & 0 & 0 & 0 & 0 & 0.5 - a_4 & 0 & 0 & 0.5 + a_4\\ 5 & 0 & 0 & 0 & 0 & 0 & 0 & 0.5 - a_5 & 0 & 0.5 + a_5\\ 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.5 - a_6 & 0.5 + a_1\\ G & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ R & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$La probabilité de gagner correspond alors à la multiplication suivante : $0.95 \times \prod_{i=1}^{6} (0.5 - a_i)$, strictement inférieure à la probabilité précédente dès lors qu'un des $a_i$ est $> 0$, puisque tous les termes dans la multiplication sont inférieurs ou égaux à leurs homologues précédents. C'est logique : si on laisse plus d'options pour arrêter le jeu, on aura moins de chances de gagner.
On choisira $k = 2$ (deux voisins).
Données :
| x1 | x2 | y |
|---|---|---|
| 2 | 2 | 1.0 |
| 4 | 5 | 4.0 |
| 7 | 7 | 8.0 |
| 4 | 8 | 6.0 |
| 9 | 10 | 11.0 |
| 5 | 1 | 2.0 |
| 5 | 3 | 3.0 |
| 1 | 9 | 10.0 |
| 8 | 10 | 10.0 |
| 3 | 7 | 5.0 |
| 10 | 8 | 12.0 |
| 8 | 1 | 1.0 |
Considérant comme ensemble d'entraînement les lignes 1 à 8, calculez l'erreur $E$ réalisée sur l'ensemble de test (lignes 9 à 12).
Cette dernière erreur $E$ est calculée ici comme la moyenne des erreurs absolues.
Répétez ensuite l'opération avec pour ensemble d'entraînement les lignes 5 à 12. Que remarquez-vous ?
plotTest = function(test) {
data = matrix(c(2,2,1.0, 4,5,4.0, 7,7,8.0, 4,8,6.0, 9,10,11.0, 5,1,2.0, 5,3,3.0, 1,9,10.0, 8,10,10.0, 3,7,5.0, 10,8,12.0, 8,1,1.0), byrow=TRUE, ncol=3)
plot(data[-test,1:2], xlim=c(0,11), ylim=c(0,11), pch=3, xlab="x1", ylab="x2")
text(data[-test,1] - 0.4, data[-test,2], as.character((1:12)[-test]))
text(data[-test,1], data[-test,2] + 0.4, data[-test,3], col=colors()[258])
par(new=TRUE)
plot(data[test,], col=2, xlim=c(0,11), ylim=c(0,11), pch=16, xlab="", ylab="")
text(data[test,1] - 0.4, data[test,2], as.character((1:12)[test]), col=2)
text(data[test,1], data[test,2] - 0.4, data[test,3], col=4)
grid()
}
plotTest(9:12)
(À gauche en rouge : numéro du point. Au dessus en vert : valeur associée - en bleu en dessous si inconnue).
9 a pour voisins 5 et 3 => on prédit 11+8 / 2 = 9.5 au lieu de 10.
11 a pour voisins 5 et 3 => on prédit 11+8 / 2 = 9.5 au lieu de 10.
10 a pour voisins 4 et 2 => on prédit 6+4 / 2 = 5 = valeur réelle (pas d'erreur).
12 a pour voisins 6 et 7 => on prédit 3+2 / 2 = 2.5 au lieu de 1.
Moyenne des erreurs $= \frac{0.5+0.5+0+1.5}{4} = 0.625$.
On change d'ensemble de test :
plotTest(1:4)
1 a pour voisins 6 et 7 => on prédit 3+2 / 2 = 2.5 au lieu de 1.
2 a pour voisins 10 et 7 => on prédit 5+3 / 2 = 4 = valeur réelle (pas d'erreur).
3 a pour voisins 9 et 11 => on prédit 10+12 / 2 = 11 au lieu de 8.
4 a pour voisins 10 et 8 => on prédit 10+5 / 2 = 7.5 au lieu de 6.
Moyenne des erreurs $= \frac{1.5+0+3+1.5}{4} = 1.5$.
L'erreur a plus que doublé en changeant d'ensemble de test. C'est pourquoi on effectue ce calcul sur de nombreux ensembles de test pris aléatoirement pour avoir une meilleure estimation des performances.
L'échantillon ci-dessous correspond à un sous-ensemble du jeu de données "zoo" classant des animaux par groupes : https://archive.ics.uci.edu/ml/datasets/Zoo.
Tous les attributs sont booléens sauf le nombre de pattes : entier.
| Aquatique | Prédateur | #Pattes | Groupe |
|---|---|---|---|
| 0 | 0 | 4 | A |
| 0 | 1 | 4 | A |
| 1 | 1 | 0 | A |
| 1 | 0 | 0 | B |
| 1 | 1 | 0 | B |
| 1 | 1 | 0 | B |
| 1 | 1 | 6 | C |
| 1 | 1 | 8 | C |
| 0 | 1 | 8 | C |
Construisez un arbre de décision selon la méthode vue en cours, en utilisant l'indice de Gini rappelé ci-dessous :
$$I = 1 - \sum_{k=1}^{K} p_k^2$$
où $p_k$ est la proportion de la classe $k$ dans l'ensemble considéré.
Les découpages selon des variables booléennes sont uniques : les 0 d'un côté et les 1 de l'autre. Il n'y a donc qu'une seule variation d'indice de Gini à calculer pour les colonnes 1 et 2. Concernant la 3eme colonne on commence par trier les valeurs : 0,0,0,0,4,4,6,8,8. On peut donc couper entre 0 et 4 ($d_2$), puis entre 4 et 6 ($d_5$), et enfin entre 6 et 8.
On remarque cependant que #Pattes >= 6 correspond au même groupe, C => aucun intérêt de découper entre 6 et 8.
Rappel du calcul à effectuer : somme des $p_k^2$ dans chaque cellule (définie par un découpage sur une colonne), pondérés par les proportions (tailles des cellules). Notons cette quantité $\Delta_G$.
$\Delta_G(\texttt{Aquatique}) = \frac{3}{9} \left( \left(\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2 \right) + \frac{6}{9} \left( \left(\frac{1}{6}\right)^2 + \left(\frac{2}{6}\right)^2 + \left(\frac{3}{6}\right)^2 \right) \simeq 0.44$
$\Delta_G(\texttt{Predateur}) = \frac{2}{9} \left( \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 \right) + \frac{7}{9} \left( \left(\frac{2}{7}\right)^2 + \left(\frac{2}{7}\right)^2 + \left(\frac{3}{7}\right)^2 \right) \simeq 0.38$
$\Delta_G(d_2) = \frac{4}{9} \left( \left(\frac{1}{4}\right)^2 + \left(\frac{3}{4}\right)^2 \right) + \frac{5}{9} \left( \left(\frac{2}{5}\right)^2 + \left(\frac{3}{5}\right)^2 \right) \simeq 0.57$
$\Delta_G(d_5) = \frac{3}{9} \left( \left(\frac{3}{3}\right)^2 \right) + \frac{6}{9} \left( \left(\frac{3}{6}\right)^2 + \left(\frac{3}{6}\right)^2 \right) \simeq 0.67$
On choisit donc $d_5$ : division #Pattes < 5 ou >= 5. Le groupe correspondant à #Pattes >= 5 est pur, on itère donc sur les 6 lignes restantes :
$\Delta_G(\texttt{Aquatique}) = \frac{2}{6} \left( \left(\frac{2}{2}\right)^2 \right) + \frac{4}{6} \left( \left(\frac{1}{4}\right)^2 + \left(\frac{3}{4}\right)^2 \right) = 0.75$
$\Delta_G(\texttt{Predateur}) < \Delta_G(\texttt{Aquatique})$ car la répartition passe de (A,A - A,B,B,B) à (A,B - A,A,B,B) : pire dans chaque groupe.
$\Delta_G(d_2) = \Delta_G(\texttt{Aquatique})$ (même découpage !).
($d_5$ a déjà été utilisée).
On a donc le choix entre les variables Aquatique et #Pattes : prenons la première, pour changer.
Aquatique = 0 est pur (deux élements, label A).
Aquatique = 1 en revanche contient A,B,B,B, mais à ce stade on note un souci technique : la ligne correspondant au label A est identique à deux des trois lignes portant l'étiquette B. Quoiqu'on fasse, donc, on n'ira pas plus loin : la ligne "A" ne se séparera jamais des deux lignes "B" identiques. On pourrait à la limite séparer la ligne "B" avec Prédateur = 0, mais ça ne présente aucun intérêt (ce serait intéressant si cette ligne avait une autre étiquette).
Impossible d'aller plus loin : une feuille reste impure (le problème vient des données).
Considérant ce sous-ensemble du jeu de données iris
| Sepal.Length | Sepal.Width | Petal.Length | Petal.Width | Species |
|---|---|---|---|---|
| 5.1 | 3.5 | 1.4 | 0.2 | setosa |
| 4.9 | 3.0 | 1.4 | 0.2 | setosa |
| 7.0 | 3.2 | 4.7 | 1.4 | versicolor |
| 6.4 | 3.2 | 4.5 | 1.5 | versicolor |
| 6.3 | 3.3 | 6.0 | 2.5 | virginica |
| 5.8 | 2.7 | 5.1 | 1.9 | virginica |
Indiquez en vous inspirant de l'exercice "Pierre Feuille Ciseaux" un réseau sans couches cachées permettant de classer les entrées dans l'une des trois espèces.
Initialisez les poids à zéro puis effectuez deux itérations d'apprentissage en considérant deux lignes différentes (au choix) correspondant à deux espèces.
Le réseau aura 4 entrées (les 4 variables $x_1$ à $x_4$) + un biais noté $x_0$ fixé à 1 (arbitrairement). En sortie trois neurones correspondant respectivement aux espèces Setosa, Versicolor et Virginica. Cela définit en fait trois réseaux à une seule sortie. Idéalement, chacun d'eux est à terme spécialisé dans la séparation "Une espèce vs. le reste". En pratique cependant on pourra s'arrêter lorsque la réponse maximale (parmi les 3) correspond à l'espèce à prédire. L'algorithme est le même dans les deux cas, cf. formule donnée dans le cours : $w_i(t+1) = w_i(t) + (d - z) x_i$ où $d$ est la valeur attendue et $z$ la valeur effectivement prédite (*). En d'autres termes on fait en sorte que $w_i(t) x_i$ augmente (resp. diminue) si la valeur prédite est trop petite (resp. trop grande).
Concernant le point (*), on remarque ici qu'il n'y a pas de valeur fixée à prédire : on peut considérer par exemple que tout résultat supérieur strict aux valeurs des autres neurones de sortie définit la réponse, et ajuster à chaque fois en prenant $d - z = \pm 1$ (arbitrairement).
Considérons les lignes 1 et 3. Initialement tout est à zéro, donc on obtient $(0, 0, 0)$. On renforce alors les poids menant à Setosa :
Setosa :
$w_0 \leftarrow 0 + 1$
$w_1 \leftarrow 0 + 5.1$
$w_2 \leftarrow 0 + 3.5$
$w_3 \leftarrow 0 + 1.4$
$w_4 \leftarrow 0 + 0.2$
Ensuite, la ligne 3 a pour étiquette Versicolor mais le calcul mène logiquement à une réponse négative - elle est positive seulement pour Setosa. On renforce donc les poids menant à Versicolor et diminue ceux relatif à Setosa :
Setosa :
$w_0 \leftarrow 1 - 1$
$w_1 \leftarrow 5.1 - 7.0$
$w_2 \leftarrow 3.5 - 3.2$
$w_3 \leftarrow 1.4 - 4.7$
$w_4 \leftarrow 0.2 - 1.4$
Versicolor :
$w_0 \leftarrow 0 + 1$
$w_1 \leftarrow 0 + 7.0$
$w_2 \leftarrow 0 + 3.2$
$w_3 \leftarrow 0 + 4.7$
$w_4 \leftarrow 0 + 1.4$
Etc : à chaque itération on considère en cas d'erreur la paire "prédit - prévue" et on change les poids correspondant.