---
tags: corrTD, info, knn, 2425
---
# <center>TD5 : algorithme des k plus proches voisins</center>
Documents de base : le [cours](http://demeslay.maths.free.fr/fichiers/info/spe/03_Algo_apprentissage.pdf) et le [TD5](http://demeslay.maths.free.fr/fichiers/info/spe/TD05_KNN.pdf).
[TOC]
### Exercice 1 : distance :straight_ruler:
* **Q1.** On utilise la définition $d(A, B) = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2}$.
```python=
def distance2(pt1: (float, float), pt2: (float, float)) -> float:
"""
Carré de la distance euclidienne entre les deux points du plan.
"""
return (pt1[0] - pt2[0])**2 + (pt1[1] - pt2[2])**2
```
* **Q2.** On procède de même mais avec un algorithme de somme pour prendre en compte les $n$ coordonnées.
```python=
def distance(pt1: tuple, pt2: tuple) -> float:
"""
Carré de la distance euclidienne entre les deux points
d'un espace de dimension quelconque.
"""
assert len(pt1) == len(pt2)
dist = 0
for i in range(len(pt1)):
dist = dist + (pt1[i] - pt2[i])**2
return dist
```
### Exercice 2 : déterminer les k plus proches voisins
* **Q1.** Il y a trois tris relativement abordables vus en première année. Les trois se font « en place », c'est-à-dire qu'ils modifient la liste à trier (et ne renvoie rien, ils agissent par effet de bord).
* *Tri à bulles* : les éléments « remontent » tant qu'ils sont plus grands que les suivants.
```python=
def tri_bulles(L: list) -> None:
n = len(L)
for i in range(n):
for j in range(n-i-1):
if L[j] > L[j+1]:
L[j], L[j+1] = L[j+1], L[j]
```
* *Tri par sélection* : à la i-ème étape (i commence à 0), on cherche le minimum parmi les éléments d'indice supérieur ou égal à i et on le place ensuite en i-ème position.
```python=
def tri_selection(L: list) -> None:
n = len(L)
for i in range(n):
# Recherche du minimum dans L[i:]
pos_mini = i
val_mini = L[i]
for j in range(i, n):
if L[j] < val_mini:
val_mini = L[j]
pos_mini = j
# On le place à la position i
L[i], L[pos_mini] = L[pos_mini], L[j]
```
* *Tri par insertion* : c'est le tri du joueur de cartes. Au fur et à mesure du parcours de la liste, on insère l'élément à la bonne place parmi les éléments préalablement triés.
```python=
def tri_insertion(L: list) -> None:
n = len(L)
for i in range(1, n):
# Ici L[:i-1] est triée
j = i
val_a_placer = L[i]
while j > 0 and L[j-1] > val_a_placer:
L[j] = L[j-1]
j = j-1
L[j] = val_a_placer
# Ici L[:i] est triée
```
* **Q2.** Adaptons par exemple le tri à bulles, le principe est le même pour les autres. Il suffit de distinguer deux opérations : les comparaisons s'effectuent sur le flottant mais les échanges doivent être faits entre les couples.
```python=
def tri_couples(ensemble: [(tuple, float)]) -> None:
"""
Tri de la liste ensemble par ordre croissant de
la valeur du flottant (2e élément du couple).
"""
n = len(ensemble)
for i in range(n):
for j in range(n-i-1):
# On comparer les valeurs des float des deux couples
if ensemble[j][1] > ensemble[j+1][1]:
# On échange les couples
ensemble[j], ensemble[j+1] = ensemble[j+1], ensemble[j]
```
* **Q3.** On réutilise les fonctions précédentes. Tout d'abord, on va calculer la distance entre `point` et chaque élément de `ensemble` et les stocker dans une liste sous forme de couple `(tuple, float)`. Ensuite, grâce à la question précédente, on va trier cette liste suivant la valeur de la distance (le flottant). Enfin, on garde les k premiers éléments de la liste qui correspondent aux k éléments à la plus petite distance de `point`.
```python=
def kppv(ensemble: list, point: tuple, k: int) -> list:
"""
Renvoie les k plus proches voisins (distance minimale)
de point parmi les éléments de ensemble.
"""
# Création d'une liste (pt, distance entre pt et point)
voisins = []
for i in range(ensemble):
dist = distance(ensemble[i], point)
voisins.append(ensemble[i], dist)
# On trie par effet de bord, la liste est modifiée
# donc pas de voisins = tri_couples(voisins)
tri_couples(voisins)
# On renvoie les k plus proches
return voisins[:k]
```
Pour celles et ceux qui ne sont pas à l'aise avec l'opération de tranches `voisins[:k]`, on peut remplacer la ligne 7 précédente par les lignes suivantes :
```python=
plus_proches = []
for i in range(k):
plus_proches.append(voisins[i])
return plus_proches
```
### Exercice 3 : classe majoritaire
* **Q1.**
```python=
def classe_majo(points: list) -> str:
"""
Renvoie la classe majoritaire parmi les éléments de points.
points est une liste de couples (coord, classe).
"""
# Étape 1 : on compte les occurrences de chaque classe
presents = {}
for element in points:
if element[1] not in presents:
presents[element[1]] = 1
else:
presents[element[1]] += 1
# Étape 2 : on détermine le maximum dans ce dict
maxi = 0
classe_maxi = ""
for classe in presents:
if presents[classe] > maxi:
maxi = presents[classe]
classe_maxi = classe
return classe_maxi
```
* **Q2.** Il s'agit de modifier l'étape 2 de la fonction ci-dessus. Une façon de procéder (mais pas optimale) est de déterminer le nombre maximal d'occurrences puis de garder toutes les classes apparaissant ce nombre de fois.
```python=13
# Étape 2
# 2.1 Nombre maxi d'occurrences
maxi = 0
for classe in presents:
if presents[classe] > maxi:
maxi = presents[classe]
# 2.2 Toutes les classes apparaissant ce nb maxi de fois
pres_maxi = []
for classe in presents:
if presents[classe] == maxi:
pres_maxi.append(classe)
# 2.3 Renvoi aléatoire d'une de ces classes
return random.choice(pres_maxi)
```
On peut bien sûr améliorer cela en s'évitant le double parcours du dictionnaire `presents` en mettant à jour au fur et à mesure la liste des classes majoritaires.
```python=13
# Étape 2
maxi = 0
classe_maxi = [] # les classes apparaissant maxi fois
for classe in presents:
# 1er cas : nouvelle classe majoritaire
if presents[classe] > maxi:
classe_maxi = [classe]
maxi = presents[classe]
# 2e cas : égalité avec le maxi actuel
elif presents[classe] == maxi:
classe_maxi.append(classe)
return choice(classe_maxi)
```
### Exercice 4 : taux bonne prédiction
Il suffit de calculer le ratio « nombre bonnes prédictions / nombre prédictions » à l'aide d'un algorithme de somme.
```python=
def taux_bonne_prediction(donnees_test: [int], predictions: [int]) -> float:
"""
Renvoie le taux de bonnes prédictions.
Les listes donnees_test et predictions sont des listes de classes
(entier de 0 à nb_classes-1), et sont supposées de même longueur.
On suppose également que les points sont donnés dans le même ordre
dans ces deux listes.
"""
assert len(donnees_test) == len(predictions) # Vérification même longueur
bonne_pred = 0
for i in range(len(donnees_test)):
if donnees_test[i] == predictions[i]:
bonne_pred = bonne_pred + 1
return bonne_pred / len(predictions)
```
### Exercice 5 : matrice de confusion
```python=
def matrice_confusion(donnees_test: [int], predictions: [int], nb_classes: int) -> [[int]]:
"""
Renvoie la matrice de confusion associées aux predictions par rapport
aux donnees_test étiquetées.
Les listes donnees_test et predictions sont des listes de classes
(entier de 0 à nb_classes-1), et sont supposées de même longueur.
On suppose également que les points sont donnés dans le même ordre dans
ces deux listes.
"""
assert len(donnees_test) == len(predictions) # Vérification même longueur
# Création d'une matrice de 0 de la bonne taille.
matrice = [[0 for j in range(nb_classes)] for i in range(nb_classes)]
for k in range(len(donnees_test)):
ligne = donnees_test[k]
colonne = predictions[k]
matrice[ligne][colonne] += 1
return matrice
```
:::danger
**Attention** : la commande `[[0]*nb_classes]*nb_classes` ne convient pas pour créer la matrice de 0 car elle engendrera des effets non désirés lorsqu'on en modifiera des valeurs.
Pour le voir, exécuter pas à pas (bouton Next) le code ci-dessous ou sur <a href="https://pythontutor.com/render.html#code=A%20%3D%20%5B%5B0%5D%20*%203%5D%20*%204%0AA%5B1%5D%5B0%5D%20%3D%202%0Aa%20%3D%20A%5B2%5D%5B0%5D%20%20%23%20Surprenant,%20non%20%3F%0A%0AB%20%3D%20%5B%5B0%20for%20i%20in%20range%283%29%5D%20for%20j%20in%20range%284%29%5D%0AB%5B1%5D%5B0%5D%20%3D%202%0Ab%20%3D%20B%5B2%5D%5B0%5D&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false">cette page</a>. En particulier, regarder le début, être surpris par la valeur de `a`, puis passer directement de l'étape 4 à l'étape 35 et voir la différence de comportement pour `b`.
:::
<iframe width="800" height="600" frameborder="1" src="https://pythontutor.com/iframe-embed.html#code=A%20%3D%20%5B%5B0%5D%20*%203%5D%20*%204%0AA%5B1%5D%5B0%5D%20%3D%202%0Aa%20%3D%20A%5B2%5D%5B0%5D%20%20%23%20Surprenant,%20non%20%3F%0A%0AB%20%3D%20%5B%5B0%20for%20i%20in%20range%283%29%5D%20for%20j%20in%20range%284%29%5D%0AB%5B1%5D%5B0%5D%20%3D%202%0Ab%20%3D%20B%5B2%5D%5B0%5D&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false"> </iframe>
### Exercice 6 : analyse des résultats
* **Q1.** Il s'agit encore une fois d'un algorithme de somme. On doit d'une part calculer la somme des termes diagonaux (ils correspondent aux bonnes prédictions) et d'autre part la somme de tous les termes pour avoir le nombre total de prédictions.
```python=
def taux_bonne_prediction_mat(confusion: [[int]]) -> float:
"""
Renvoie le taux de bonne prédiction avec des résultats donnés
sous forme d'une matrice de confusion.
"""
nb_pred = 0
bonne_pred = 0
n = len(confusion) # taille de la matrice = nb lignes = nb colonnes
for i in range(n):
bonne_pred += confusion[i][i]
for j in range(n):
nb_pred += confusion[i][j]
return bonne_pred / nb_pred
```
* **Q2.** C'est à peu près la même chose mais on ne s'intéresse qu'à une seule ligne.
```python=
def taux_correct_classe(confusion: [[int]], classe: int) -> float:
"""
Renvoie le taux de bonne prédiction pour la classe donnée avec des
résultats donnés sous forme d'une matrice de confusion.
"""
nb_pred = 0
bonne_pred = confusion[classe][classe]
for j in range(len(confusion)):
nb_pred += confusion[classe][j]
return bonne_pred / nb_pred
```