Données :
| x1 | x2 |
|---|---|
| 4 | 7 |
| 1 | 6 |
| 6 | 6 |
| 2 | 6 |
| 5 | 2 |
| 3 | 2 |
Appliquez en détaillant raisonnablement chaque étape l'algorithme des k-means avec $K=2$.
Prenez comme centres initiaux $c_1 = (1,6)$ et $c_2 = (6,6)$ dans un premier temps.
Choisissez ensuite $c_1 = (4,3)$ et $c_2 = (4,7)$. Que remarquez-vous ?
Appliquez ensuite l'algorithme CAH sur ces mêmes données.
Dessinez le dendrogramme.
plotCtrs = function(ctrs) {
data = matrix(c(4,7, 1,6, 6,6, 2,6, 5,2, 3,2), byrow=TRUE, ncol=2)
plot(data, xlim=c(0,7), ylim=c(1,8), pch=3, xlab="x1", ylab="x2")
text(c(4,1,6,2,5,3) - 0.2, c(7,6,6,6,2,2), as.character(1:6))
par(new=TRUE)
plot(matrix(ctrs, byrow=TRUE, ncol=2), col=2, xlim=c(0,7), ylim=c(1,8), pch=16, xlab="", ylab="")
grid()
}
plotCtrs(c(1,6, 6,6))
text(c(1,6), c(6,6) - 0.3, c("c1","c2"), col=2)
On obtient facilement les distances (euclidiennes au carré) à $c_1$ respectivement pour les points 1, 2, ..., 6 : (10, 0, 25, 1, 32, 20) et (5, 25, 0, 16, 17, 25).
On en déduit deux groupes suite à la première affectation : (2, 4, 6) et (1, 3, 5).
On recalcule alors les centres : $c_1 = (\frac{1+2+3}{3}, \frac{6+6+2}{3}) = (2, 4.67)$ et $c_2 = (\frac{4+6+5}{3}, \frac{7+6+2}{3}) = (5, 5)$.
plotCtrs(c(2,4.67, 5,5))
text(c(2, 5), c(4.67, 5) - 0.3, c("c1","c2"), col=2)
On voit clairement que 2 et 4 sont plus proches de $c_1$, tandis que 1, 3 et 5 sont plus proches de $c_2$. Enfin concernant 6 on a $d^2(x_6, c_1) < 10$ en considérant le point à coordonnées entières juste au dessus de $c_1$. Or $d^2(x_6, c_2) = 13$ : la composition des groupes ne change pas, on a convergé.
Essayons avec comme centres initiaux $c_1 = (4,3)$ et $c_2 = (4, 7)$ :
plotCtrs(c(4,3, 4,7))
text(c(4,4), c(3,7) - 0.3, c("c1","c2"), col=2)
Graphiquement les points 5 et 6 sont regroupés ($c_1$) ainsi que les points 1, 3 et 4. $x_2$ peut être considéré ambigu, calculons : $d^2(x_2, c_1) = 18$ et $d^2(x_2, c_2) = 10$.
On obtient donc deux groupes (5, 6) et (1, 2, 3, 4).
Recalcul des centres : $c_1 = (\frac{3+5}{2}, \frac{2+2}{2}) = (4, 2)$ et $c_2 = (\frac{1+2+4+6}{4}, \frac{6+6+7+6}{4}) = (3.25, 6.25)$
plotCtrs(c(4,2, 3.25,6.25))
text(c(4,3.25), c(2,6.25) - 0.3, c("c1","c2"), col=2)
Visuellement l'algorithme CAH va d'abord apparier les points 2 et 4 ensemble (coût 1 = $d^2(x_2, x_4)$), puis les points 5 et 6 (coût 4), et enfin les points 1 et 3 (coût 5). En effet la distance du point 1 au groupe 2,4 est égale à $d(x_2, x_1)$ - $x_2$ étant le point le plus éloigné de $x_1$ -, et cette distance est supérieure stricte à $d(x_1, x_3)$.
Après ces fusions, il faut calculer les distances inter-groupes "complete linkage" égales aux distances euclidiennes maximales entre deux paires de points pris dans l'un et dans l'autre cluster. Ainsi
$d^2( (2,4), (1,3) ) = 25$ (paire (2,3)),
$d^2( (2,4), (6,5) ) = 32$ (paire (2,6)),
$d^2( (1,3), (6,5) ) = 26$ (paire (1,6) ; on trouve 25 avec (3,6)).
On fusionne donc (2,4) et (1,3) (coût 25), et enfin (1,2,3,4) avec (5,6) : coût 32 = $d^2(x_2,x_5)$ (seulement 25 avec la paire (3,6)).
Dendrogramme final :
Remarque : en coupant à $K = 2$ on retrouve le résultat des k-means avec le second choix de centres intiiaux.
On considère un jeu de billard simplifié démarrant avec seulement 4 boules.
Pour gagner Alice doit sortir les 2 boules vertes, et Bob les 2 boules bleues.
À chaque tour un joueur sort une seule de ses boules avec probabilité $p_A$ pour Alice et $p_B$ pour Bob.
En cas de succès il rejoue. Sinon rien ne change, et c'est à l'adversaire de jouer.
On considère à présent qu'un joueur peut aussi sortir une boule adverse pendant son tour.
On considère les deux boules vertes (resp. bleues) indistinguables, obtenant exactement 4 configurations distinctes avec au moins une boule de chaque couleur sur la table de jeu : (2,2), (2,1), (1,2), (1,1). Prenons pour convention (arbitraire) que la première coordonnée correspond à une boule d'Alice. Il faut ensuite ajouter deux états correspondants respectivement à une victoire d'Alice et de Bob : (0,$z$) et ($z$,0) où $z$ n'a pas besoin d'être spécifié (ça peut être 2 ou 1 : ça revient au même).
On remarque que les transitions depuis un "état" $(x,y)$ avec $x > 0$ et $y > 0$ ne sont pas les mêmes suivant que le tour soit à Alice ou Bob : il faut donc considérer cette information et subdiviser chacune de ces situations. En effet si c'est à Alice (resp. Bob) de jouer alors on aura une transition vers $(x-1, y)$ (resp. $(x, y-1)$) en cas de succès, et vers $(x, y)$ sinon - en changeant de tour.
Ces réflexions nous amènent à dessiner le graphe suivant, comportant 10 états, en notant $q_A = 1 - p_A$ et $q_B = 1 - p_B$ pour alléger ; j'ai utilisé une double flèche au lieu de deux flèches pour relier les états symétriques suite à un échec, et les ai distingués par une couleur rouge.
$(0,z)$ et $(z,0)$ sont absorbants puisqu'une fois ces états atteints le jeu est terminé. Tous les autres états sont transitoires car si au moins l'un des $p_A$ ou $p_B$ est $> 0$ alors un des deux joueurs finit forcément par gagner (note : en supposant les tours successifs indépendants et en utilisant le fameux lemme de Borel-Cantelli, que l'on peut parfaitement ignorer tant le résultat est intuitif ici).
Écrivons alors la matrice correspondant au graphe :
$$\begin{pmatrix} & 2,2/A & 1,2/A & 2,1/A & 1,1/A & 2,2/B & 2,1/B & 1,2/B & 1,1/B & 0,z & z,0\\ 2,2/A & 0 & p_A & 0 & 0 & q_A & 0 & 0 & 0 & 0 & 0\\ 1,2/A & 0 & 0 & 0 & 0 & 0 & 0 & q_A & 0 & p_A & 0\\ 2,1/A & 0 & 0 & 0 & p_A & 0 & q_A & 0 & 0 & 0 & 0\\ 1,1/A & 0 & 0 & 0 & 0 & 0 & 0 & 0 & q_A & p_A & 0\\ 2,2/B & q_B & 0 & 0 & 0 & 0 & p_B & 0 & 0 & 0 & 0\\ 2,1/B & 0 & 0 & q_B & 0 & 0 & 0 & 0 & 0 & 0 & p_B\\ 1,2/B & 0 & q_B & 0 & 0 & 0 & 0 & 0 & p_B & 0 & 0\\ 1,1/B & 0 & 0 & 0 & q_B & 0 & 0 & 0 & 0 & 0 & p_B\\ 0,z & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ z,0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$La sous-matrice carrée correspondant aux états transitoires est alors notée $Q$, et on note (comme dans le cours) $R$ la matrice $8 \times 2$ correspondant aux deux colonnes de droite sans les deux dernières lignes. Avec $N = (I - Q)^{-1}$ (formule du cours), la probabilité d'être absorbé dans l'état $(0,z)$ (= Alice gagne) est la valeur de coordonnées (1,1) (resp. (5,1)) dans la matrice $N \times R$ si Alice (resp. Bob) commence. La durée moyenne du jeu s'obtient quant à elle en sommant les éléments de la 1ere (resp. 5eme) ligne de $N$ si Alice (resp. Bob) commence.
Notons $w_A$ et $w_B$ les probabilités de sortir une boule adverse sur son tour (au lieu d'une des notres) respectivement pour Alice et Bob. Cela crée des transitions supplémentaires de 2,2/A vers 2,1/B, et 2,1/B vers 1,1/A etc : cf. nouvelle matrice ci-dessous.
Étant donné qu'il y a strictement plus de chances de sortir une boule que dans la modélisation précédente, on en déduit sans faire de calculs que le jeu se terminera plus vite - à condition bien sûr que $w_A$ ou $w_B$ soit $> 0$. Resterait à faire l'application numérique en prenant par exemple $p_A = 0.4$, $p_B = 0.3$, $w_A = 0.2$ et $w_B = 0.2$.
$$\begin{pmatrix} & 2,2/A & 1,2/A & 2,1/A & 1,1/A & 2,2/B & 2,1/B & 1,2/B & 1,1/B & 0,z & z,0\\ 2,2/A & 0 & p_A & 0 & 0 & q_A & w_A & 0 & 0 & 0 & 0\\ 1,2/A & 0 & 0 & 0 & 0 & 0 & 0 & q_A & w_A & p_A & 0\\ 2,1/A & 0 & 0 & 0 & p_A & 0 & q_A & 0 & 0 & 0 & w_A\\ 1,1/A & 0 & 0 & 0 & 0 & 0 & 0 & 0 & q_A & p_A & w_A\\ 2,2/B & q_B & w_B & 0 & 0 & 0 & p_B & 0 & 0 & 0 & 0\\ 2,1/B & 0 & 0 & q_B & w_B & 0 & 0 & 0 & 0 & 0 & p_B\\ 1,2/B & 0 & q_B & 0 & 0 & 0 & 0 & 0 & p_B & w_B & 0\\ 1,1/B & 0 & 0 & 0 & q_B & 0 & 0 & 0 & 0 & w_B & p_B\\ 0,z & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ z,0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$Attention cette fois on a $q_A = 1 - p_A - w_A$ et $q_B = 1 - p_B - w_B$.
On choisira $k = 3$ (trois voisins).
Données :
| x1 | x2 | y |
|---|---|---|
| 2 | 2 | A |
| 4 | 5 | B |
| 7 | 7 | A |
| 4 | 8 | B |
| 9 | 10 | A |
| 5 | 1 | B |
| 5 | 3 | A |
| 1 | 9 | B |
| 8 | 10 | A |
| 3 | 7 | B |
| 10 | 8 | A |
| 8 | 1 | B |
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),
c'est-à-dire le taux d'erreur : #mal classés / #total.
Répétez ensuite l'opération avec pour ensemble d'entraînement les lignes 5 à 12.
plotTest = function(test) {
data = data.frame(x1=c(2,4,7,4,9,5,5,1,8,3,10,8), x2=c(2,5,7,8,10,1,3,9,10,7,8,1), y=c("A","B","A","B","A","B","A","B","A","B","A","B"))
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,1:2], 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 : y associé - en bleu en dessous si inconnu).
9 a pour voisins 5, 3 et 4 de labels A,A,B => on prédit A (classe majoritaire), pas d'erreur commise.
11 a pour voisins 5, 3 et 4 => on prédit A ici aussi, pas d'erreur.
10 a pour voisins 4, 2 et 8 de labels B,B,B => prédiction = B, pas d'erreur.
12 a pour voisins 6 et 7 d'étiquettes A et B. Il faut donc chercher le 3eme voisin, visuellement peu clair, donc on calcule.
$d^2(x_12, x_1) = 6^2 + 1^2 = 37$,
$d^2(x_12, x_2) = 4^2 + 4^2 = 32$,
$d^2(x_12, x_3) = 6^2 + 1^2 = 37$.
Conclusion : le 3eme voisin est le point 2 de label B => pas d'erreur.
Le taux d'erreur vaut donc 0 / 4 = 0. Changeons d'ensemble de test :
plotTest(1:4)
1 a pour voisins 6, 7 et 10 de labels A,B,B => on prédit B (classe majoritaire), erreur.
2 a pour voisins 7, 10 et 6 => on prédit B ici aussi, pas d'erreur.
3 a pour voisins 9, 11 et 5 de labels A,A,A => prédiction = A, pas d'erreur.
(Note : $d^2(x_3, x_5) = 13$ et $d^2(x_3, x_10) = 16$ - visuellement proches, mais la classe majoritaire est déjà connue après recherche des deux premiers voisins).
4 a pour voisins 8, 10 (et un 3eme, $x_7$ ou $x_9$) de labels B,B (et A) => prédiction = B, pas d'erreur.
Le taux d'erreur vaut donc 1 / 4 = 0.25. Pour obtenir une estimation plus fiable de l'erreur de généralisation il faudrait répéter l'opération un grand nombre de fois avec des ensembles de test différents (et en fait, bien sûr, avoir plus de données).
Données artificiellement générées avec A variable catégorielle et B variable réelle :
| A | B | Cible |
|---|---|---|
| X | 1 | 1 |
| Y | 6 | 1 |
| Y | 2 | 1 |
| X | 9 | 2 |
| Z | 5 | 2 |
| Z | 3 | 2 |
| X | 10 | 3 |
| Z | 7 | 3 |
| Y | 8 | 3 |
Construisez un arbre de décision selon la méthode vue en cours, en utilisant l'indice de Gini :
$$I = 1 - \sum_{k=1}^{K} p_k^2$$
où $p_k$ est la proportion de la classe $k$ dans l'ensemble considéré.
Commençons par évaluer les coupures sur la colonne numérique. On trie d'abord les valeurs :
| A | B | Cible |
|---|---|---|
| X | 1 | 1 |
| Y | 2 | 1 |
| Z | 3 | 2 |
| Z | 5 | 2 |
| Y | 6 | 1 |
| Z | 7 | 3 |
| Y | 8 | 3 |
| X | 9 | 2 |
| X | 10 | 3 |
On en déduit des coupures potentielles entre 2 et 3, puis entre 5 et 6, 6-7, 8-9, 9-10. Sans calculs ces deux dernières coupures donneront des résultats moins satisfaisants que la première, respectivement car les deux groupes résultants sont moins purs et car un groupe homogène est de cardinal 1 au lieu de 2 (cela fonctionne car les classes sont équiréparties). Pour le reste il semble que l'on n'échappe pas au calcul, mais regardons au cas où le découpage selon la colonne catégorielle avant toutes choses :
| A | B | Cible |
|---|---|---|
| X | 1 | 1 |
| X | 9 | 2 |
| X | 10 | 3 |
| Y | 6 | 1 |
| Y | 8 | 1 |
| Y | 3 | 3 |
| Z | 3 | 2 |
| Z | 5 | 2 |
| Z | 7 | 3 |
On ne voit rien d'évident, donc on se lance avec la notation $\Delta_G$ = différence d'indices de Gini :
$\Delta_G(2.5) = (2/9) \times (1^2) + (7/9) \times ( (1/7)^2 + 2 \times (3/7)^2 ) \simeq 0.524$
$\Delta_G(5.5) = (4/9) \times ( 2 \times (1/2)^2 ) + (5/9) \times ( 2 \times (1/5)^2 + (3/5)^2 ) \simeq 0.467$
$\Delta_G(6.5) = (5/9) \times ( (2/5)^2 + (3/5)^2 ) + (4/9) \times ( (1/4)^2 + (3/4)^2 ) \simeq 0.567$
$\Delta_G(Y) = (3/9) \times ( (1/3)^2 + (2/3)^2 ) + (6/9) \times ( (1/6)^2 + (2/6)^2 + (3/6)^2 ) \simeq 0.444$
$\Delta_G(Z) = \Delta_G(Y)$ (équirépartition)
$\Delta_G(X) < \Delta_G(Y)$ (subdivisions plus hétérogènes)
=> On coupe d'abord entre 6 et 7 sur la colonne B.
| A | B | Cible |
|---|---|---|
| X | 1 | 1 |
| Y | 2 | 1 |
| Z | 3 | 2 |
| Z | 5 | 2 |
| Y | 6 | 1 |
Sans calculs on voit facilement que séparer $A = Z$ vs. $A \neq Z$ mène à deux feuilles pures : on choisit donc cette règle, puisqu'un examen visuel indique qu'aucune autre ne mènera à un résultat parfait.
| A | B | Cible |
|---|---|---|
| Z | 7 | 3 |
| Y | 8 | 3 |
| X | 9 | 2 |
| X | 10 | 3 |
Ici également compte-tenu du faible nombre de lignes on peut se passer de calculs : il faudra au moins deux découpes pour isoler la cible "2" dans une feuille. Découper suivant $A = X$ vs. $A \neq X$ puis $B < 9.5$ revient au même que de diviser d'abord selon $B$ (on peut aussi choisir la valeur 8.5). On effectue le choix arbitraire de diviser selon A puis B entre 9 et 10 : arbre final.
