Chapitre 7 : Algorithme des k plus proches voisins
Prédire par les voisins
Sur la scène du vol, la brigade a trouvé un cristal inconnu. Est-ce du quartz, de la topaze ou un diamant ? Le laboratoire a mesuré la masse et la dureté de cristaux déjà identifiés. L'algorithme des k plus proches voisins prédit le type du nouveau cristal : on regarde les k cristaux connus qui lui ressemblent le plus, et on retient leur type majoritaire.
Au programme de NSI : Algorithmique : Algorithme des k plus proches voisins. Écrire un algorithme qui prédit la classe d'un élément en fonction de la classe majoritaire de ses k plus proches voisins.
Le principe
masse,durete,type
2.1,7.0,quartz
2.6,7.1,quartz
2.9,6.9,quartz
3.2,7.2,quartz
3.8,8.0,topaze
4.2,8.1,topaze
4.6,7.9,topaze
5.0,8.2,topaze
0.6,9.9,diamant
0.9,10.0,diamant
1.2,9.8,diamant
1.4,10.0,diamant
Chaque cristal est un point dans un plan : sa masse est une coordonnée, sa dureté l'autre. Les cristaux de même type se regroupent. Pour un nouveau cristal, on cherche ses k plus proches voisins parmi les points connus, et on prédit la classe qui revient le plus souvent parmi eux. C'est un exemple très simple d'algorithme d'apprentissage.
La distance entre deux points
« Proche » se mesure avec une distance. Pour deux points (x1, y1) et (x2, y2), la distance euclidienne est √((x1 − x2)² + (y1 − y2)²), c'est-à-dire la longueur du segment qui les relie. En Python : math.sqrt pour la racine carrée, et ** pour la puissance.
import math
def distance(a, b):
return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
print(distance((0, 0), (3, 4)))Trouver les k plus proches
On trie les points connus par distance croissante au nouveau point, avec sorted et key : le chapitre sur les tris sert ici. Les k premiers du résultat sont les k plus proches voisins.
def voisins(donnees, nouveau, k):
classes = sorted(donnees, key=lambda d: distance(d, nouveau))
return [d[2] for d in classes[:k]]Le vote majoritaire
Il reste à trouver la classe la plus fréquente parmi les voisins. On compte chaque classe dans un dictionnaire, puis on prend celle dont l'effectif est le plus grand : max(effectifs, key=effectifs.get). On choisit souvent un k impair pour limiter les égalités.
def majoritaire(classes):
effectifs = {}
for c in classes:
effectifs[c] = effectifs.get(c, 0) + 1
return max(effectifs, key=effectifs.get)
print(majoritaire(['quartz', 'topaze', 'quartz']))Choisir k
À toi de jouer : Exercice guidé
Complète la fonction distance(a, b) qui renvoie la distance euclidienne entre deux points a = (x1, y1) et b = (x2, y2). Par exemple, distance((0, 0), (3, 4)) vaut 5.0.