Algorithme des k plus proches voisins : exercices de 1re NSI

On calcule l'écart des abscisses : $4-1=3$.

On calcule l'écart des ordonnées : $6-2=4$.

On additionne les carrés : $3^2+4^2=9+16=25$.

On prend la racine carrée : $d(A,B)=\sqrt{25}=5$.

$XP_1=\sqrt{(1-4)^2+(1-5)^2}=\sqrt{9+16}=5$.

$XP_2=\sqrt{(2-4)^2+(5-5)^2}=\sqrt{4}=2$.

$XP_3=\sqrt{(6-4)^2+(2-5)^2}=\sqrt{4+9}=\sqrt{13}\approx 3{,}61$.

$XP_4=\sqrt{(5-4)^2+(6-5)^2}=\sqrt{2}\approx 1{,}4142$.

La plus petite distance est $XP_4$ : le plus proche voisin est $P_4$, de classe bleu.

Distances : $XA=\sqrt{4+1}=\sqrt5$, $XB=\sqrt{1+0}=1$, $XC=\sqrt{0+4}=2$, $XD=\sqrt{9+9}=\sqrt{18}$, $XE=\sqrt{16+25}=\sqrt{41}$, $XF=\sqrt{4+9}=\sqrt{13}$.

Classement croissant : $B\,(1)$, $C\,(2)$, $A\,(\sqrt5\approx 2{,}24)$, $F\,(\sqrt{13}\approx 3{,}61)$, $D\,(\sqrt{18}\approx 4{,}24)$, $E\,(\sqrt{41}\approx 6{,}40)$.

Les trois plus proches voisins sont $B$ (rouge), $C$ (bleu) et $A$ (rouge).

Vote : 2 rouges contre 1 bleu, donc la classe majoritaire est rouge.

Le troisième voisin est $A$ : $d=\sqrt5\approx 2{,}2361$.

Les distances à l'origine sont $1$, $2$, $3$, $4$, $5$ pour $P_1$, $P_2$, $P_3$, $P_4$, $P_5$ : le classement suit l'ordre des numéros.

Pour $k=1$ : seul $P_1$ compte, donc la classe est bleu.

Pour $k=3$ : $P_1$ (bleu), $P_2$ (rouge), $P_3$ (rouge) ; 2 rouges contre 1 bleu, donc rouge.

Pour $k=5$ : les cinq points sont retenus ; 3 bleus ($P_1$, $P_4$, $P_5$) contre 2 rouges, donc bleu.

Pour $k=5$, il y a 3 voisins bleus.

Écarts de surface avec 58 m² : $18$ (40), $8$ (50), $3$ (55), $12$ (70), $32$ (90).

Les trois plus petits écarts sont $3$, $8$ et $12$ : les appartements de 55, 50 et 70 m².

Leurs prix sont 160, 150 et 215 k€.

On fait la moyenne : $\dfrac{160+150+215}{3}=\dfrac{525}{3}=175$.

Valeurs brutes : $QP_1=\sqrt{1^2+600^2}\approx 600{,}0008$ et $QP_2=\sqrt{20^2+50^2}=\sqrt{2900}\approx 53{,}85$. Le plus proche est $P_2$, alors qu'il a 20 ans de plus que $Q$.

Normalisation de l'âge : $\dfrac{\text{âge}-20}{40}$. On obtient $Q:0{,}25$, $P_1:0{,}275$, $P_2:0{,}75$.

Normalisation du salaire : $\dfrac{\text{salaire}-1000}{3000}$. On obtient $Q:0{,}3333$, $P_1:0{,}5333$, $P_2:0{,}35$.

Distances normalisées : $QP_1=\sqrt{0{,}025^2+0{,}2^2}\approx 0{,}2016$ et $QP_2=\sqrt{0{,}5^2+0{,}0167^2}\approx 0{,}5003$.

Le plus proche voisin devient $P_1$. La distance normalisée $QP_1$ vaut environ $0{,}2016$.

Pour un nouveau point, la recherche naïve passe sur l'ensemble des $n$ points : 5 000 distances ⁴.

Pour 200 nouveaux points : $5\,000\times 200=1\,000\,000$ distances.

Si le jeu double ($n=10\,000$), le total double aussi : $2\,000\,000$ distances. Le temps de calcul est linéaire en $n$ ⁴.

Aucune phase d'entraînement n'est nécessaire : il suffit de stocker le jeu de données ². Le travail se fait entièrement au moment de classer.

distance : on importe sqrt depuis le module math, puis on renvoie sqrt((p[0]-q[0])**2 + (p[1]-q[1])**2).

k_plus_proches : on parcourt toutes les données (parcours séquentiel), on construit une liste liste de couples (distance(point, x), classe), on la trie avec liste.sort() et on renvoie liste[:k].

classe_majoritaire : on parcourt les voisins en comptant les classes dans un dictionnaire effectifs, puis on parcourt les clés pour garder celle dont l'effectif est le plus grand.

Test : avec x = (3, 2) et k = 3, les voisins sont ceux de l'exercice du vote (rouge, bleu, rouge), donc le programme renvoie "rouge".

Code complet :

from math import sqrt

def distance(p, q):
    return sqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2)

def k_plus_proches(donnees, x, k):
    liste = []
    for point, classe in donnees:
        liste.append((distance(point, x), classe))
    liste.sort()
    return liste[:k]

def classe_majoritaire(voisins):
    effectifs = {}
    for d, classe in voisins:
        effectifs[classe] = effectifs.get(classe, 0) + 1
    meilleure = None
    for classe in effectifs:
        if meilleure is None or effectifs[classe] > effectifs[meilleure]:
            meilleure = classe
    return meilleure

Le meilleur résultat est 7 points bien classés sur 8, obtenu pour $k=3$.

Taux de réussite : $\dfrac{7}{8}\times 100=87{,}5\ \%$.

Si l'on teste un point du jeu avec $k=1$, son plus proche voisin est lui-même, à la distance 0, donc il reçoit toujours sa propre classe : le taux serait de 100 % sans rien prouver.

D'où l'intérêt de points de test mis de côté, absents du jeu de données utilisé pour chercher les voisins.