Exercices distances et plus proches voisins (8.2.3)

Exercice 11

Exercice de compréhension élémentaire de la séparation linéaire et des plus proches voisins.

Placer les points correspondants aux extrémités des vecteurs
L'échantillon n'est pas linéairement séparable car il n'existe pas de droite séparant les points positifs du point négatif.
Pour déterminer les points les plus proches de a que de d, on trace la médiatrice du segment [ad] qui est la droite d'équation y = -x+4. On trace de même la médiatrice de [bd] qui est la droite d'équation y =-x-2. On trace de même la médiatrice de [cd] qui est la droite d'équation y = 4. On obtient un triangle délimité par les points E(3,1), F(6,4) et G(0,4). Les points à l'intérieur du triangle seront classés dans la classe -1 car leur plus proche voisin est d. Les points à l'extérieur du triangle seront classés dans la classe +1 car leur plus proche voisin est a, b ou c.

Exercice 12

L'objectif de cet exercice élémentaire est de faire comprendre que la distance euclidienne est sensible aux échelles de valeurs des attributs et que, pour toute méthode d'apprentissage basée sur une distance euclidienne, il est conseillé de normaliser les attributs.

d(a,m) = sqrt((1-3)^2+(0.9-0.1)^2) = sqrt(4+0.64) où sqrt désigne la fonction racine carrée. De même d(b,m)=sqrt(9+0.01) donc le plus proche voisin de m est a.
Si on normalise en divisant la première coordonnée par 10, les nouvelles descriptions de a, b et m sont (0.3,0.1), (0.4,0.8) et (0.1,0.9). On en déduit que d(a,m) = sqrt((0.1-0.3)^2+(0.9-0.1)^2) = sqrt(0.04+0.64) et que d(b,m)=sqrt(0.09+0.01). Par conséquent, le plus proche voisin de m est b. Ceci car a et m ont des deuxièmes coordonnées éloignées.

Exercice 13

L'objectif de cet exercice est de montrer qu'il existe différentes distances et différentes géométries. Par exemple, la distance de la vie courante est la distance euclidienne que vous avez vu en mathématique. Mais, dans la vie courante, il existe d'autres distances comme la distance entre deux villes qui est la somme des distances entre des étapes sur le graphe des routes ou la distance à vol d'oiseau qui est une distance sur une sphère (la terre). Ici, nous voyons les principales distances de base utilisées en apprentissage machine.

d1(a,b) = |3-1|+|1-1| = 2, d1(a,c) = |3-1|+|2-1| = 3, d1(a,b) = |3-2|+|3-1| = 3. De même on aurait d1(b,c)=1, d1(b,d)=3 et d1(c,d)=2. Cette distance est appelée distance de Manhattan car à New-York les rues sont perpendiculaires donc pour aller d'un point à un autre il faut se déplacer selon ces deux axes de rue. Par exemple, pour aller de a à d, je dois faire 1 unité horizontalement et 2 unités verticalement soit une distance de 3.
le "cercle" de centre a et de rayon 2 pour d1 est l'ensemble des points qui sont à une distance 2 de a pour d1. Ce cercle est un carré dont les extrémités ont pour coordonnée (3,1), (1,3), (-1,1) et (1, -1).
le cercle de centre a et de rayon 2 pour d2 est l'ensemble des points qui sont à une distance 2 de a pour d2 et c'est le cercle usuel que vous pouvez tracer au compas.
le "cercle" de centre a et de rayon 2 pour dinf est l'ensemble des points qui sont à une distance 2 de a pour dinf. Ce cercle est un carré dont les extrémités ont pour coordonnée (3,-1), (3,3), (-1,3) et (-1, -1).
Le plus proche voisin de m pour d1 est a car d1(m,a) = 3 et d1(m,b) = 4. Le plus proche voisin de m pour d2 (la distance euclidienne) est b car d2(m,a) = 3 et d1(m,b) = sqrt(8) ~ 2.828 < 3. Pour utiliser une méthode de plus proche voisin, il faut disposer d'une distance appropriée au problème.

Exercice 14

L'objectif de cet exercice est d'introduire une similarité (et une distance) très utilisée en recherche d'information qu'est la similarité cosinus. Vous pouvez par exemple consulter le cours suivant sur mon site pour comprendre l'intérêt de cette similarité pour la recherche d'information mais de nombreuses autres sources sont disponibles.

cos(a,a) = (2x2+1x1)/(sqrt(2^2+1^2)sqrt(2^2+1^2)) = 5/(sqrt(5)sqrt(5))=5/5=1. De la même façon, on trouve que cos(a,b) = 1, cos(a,c) = 6/(sqrt(40) ~ 0.95, cos(a,d) = 0 et cos(a,e) = -1. Si vous représentez les vecteurs, vous pouvez constater que la valeur dépend de l'angle que font les vecteurs : a et a, de même que a et b, ont un angle nul et on trouve un cosinus de 1 ; l'angle entre a et b est petit donc on trouve un cosinus proche de 1 ; les vecteurs a et d sont orthogonaus et on trouve un cosinus nul, les vecteurs a et e ont un angle de 180 degrés et on trouve un cosinus de -1. On peut voir pour a et b que le cosinus ne dépend pas de la norme. Ceci est dû au fait que, dans le calcul du cosinus, on divise par les normes des vecteurs ce qui permet de normaliser le cosinus pour qu'il prenne des valeurs entre 0 et 1.
cos(x,y) prend ses valeurs dans l'intervalle [-1,1] donc 1-cos(x,y) prend ses valeurs dans l'intervalle [0,2] donc dcos(x,y) prend ses valeurs dans l'intervalle [0,1]. dcos(x,x) = (1-cos(x,x))/2 = (1-1)/2 = 0 car cos(x,x) = (||x||^2)/(||x||||x||)=1. On a dcos(x,y)=dcos(y,x) car, par définition, cos(x,y)=cos(y,x). L'inégalité triangulaire n'est pas vérifiée car on peut trouver des vecteurs x, y et z tels que d(x,y) est plus grand que d(x,z)+d(z,x) (trouvez-en des exemples) alors que l'inégalité triangulaire que doit vérifier une distance stipule que le plus cours chemin est toujours la ligne droite, i.e. que quels que soient x, y et z, on a toujours d(x,y) <= d(x,z) + d(z,y).
dang est une distance car dang(x,y)=0 si et seulement si x=y (facile) ; pour tout x et y, on a dang(x,y)=dang(y,x) (facile) ; et, pour tout x, y et z, on a d(x,y) <= d(x,z) + d(z,y) (un peu technique et sans intérêt pour nous).

Google Sites

Report abuse