Loading [MathJax]/jax/output/HTML-CSS/fonts/STIX-Web/fontdata.js

k plus proches voisins

📝 Rappels 📝

L'algorithme des k plus proches voisins est un algorithme de classification.

On utilise cet algorithme lorsqu'on dispose :

  • d'une population d'individus de référence possédant chacun :

    • des caractéristiques numériques (taille, poids, volume, chiffre d'affaires, âge etc.),
    • une étiquette (ou classe) pouvant prendre quelques valeurs seulement (par exemple "malade ou sain", "noir, gris ou blanc", "coupable ou innocent" etc.).
  • d'un individu possédant :

    • des caractéristiques numériques (taille, poids, volume, chiffre d'affaires, âge etc.),
    • MAIS dont l'étiquette est INCONNUE.

Le but de l'algorithme est de prédire l'étiquette de cet individu, c'est à dire de prédire la classe d'un individu (d'où l'appartenance de cet algorithme à la grande famille des algorithmes de classification).

Remarque : Il y a des algorithmes de classification que vous connaissez déjà. Par exemple ceux qui - sur vos smartphones - identifient ce que vous avez pris en photo. Celui que nous allons étudier ici (les k plus proches voisins) est un des plus simples algorithmes de classification).

Voici un exemple pour lequel on considère différents personnages rencontrés dans un jeu :

population =    [{'famille': 'renard', 'logique': 5, 'force': 6, 'cooperation': 4} ,
                 {'famille': 'rhino',  'logique': 4, 'force': 7, 'cooperation': 3} ,
                 {'famille': 'renard', 'logique': 6, 'force': 4, 'cooperation': 4} ,
                 {'famille': 'renard', 'logique': 7, 'force': 6, 'cooperation': 3} ,
                 {'famille': 'rhino',  'logique': 6, 'force': 8, 'cooperation': 3} ,
                 {'famille': 'renard', 'logique': 6, 'force': 6, 'cooperation': 5} ,
                 {'famille': 'rat',    'logique': 5, 'force': 3, 'cooperation': 5} ,
                 {'famille': 'rhino',  'logique': 5, 'force': 8, 'cooperation': 4} ,
                 {'famille': 'rat',    'logique': 4, 'force': 3, 'cooperation': 5} ,
                 {'famille': 'rhino',  'logique': 6, 'force': 6, 'cooperation': 6} ,
                 {'famille': 'renard', 'logique': 6, 'force': 6, 'cooperation': 6} ,
                 {'famille': 'rhino',  'logique': 5, 'force': 9, 'cooperation': 4} ,
                 {'famille': 'rhino',  'logique': 3, 'force': 6, 'cooperation': 6} ,
                 {'famille': 'rhino',  'logique': 7, 'force': 8, 'cooperation': 5} ,
                 {'famille': 'renard', 'logique': 8, 'force': 4, 'cooperation': 6} ,
                 {'famille': 'rat',    'logique': 6, 'force': 4, 'cooperation': 7} ,
                 {'famille': 'rat',    'logique': 6, 'force': 4, 'cooperation': 8} ,
                 {'famille': 'rat',    'logique': 5, 'force': 3, 'cooperation': 8} ,
                 {'famille': 'rhino',  'logique': 7, 'force': 9, 'cooperation': 7} ,
                 {'famille': 'rat',    'logique': 4, 'force': 2, 'cooperation': 8}]

On dispose par ailleurs de ce personnage dont on ne connait pas la famille :

perso = {'famille': '???', 'logique': 5, 'force': 5, 'cooperation': 4}

On souhaite prédire s'il s'agit d'un rat, d'un rhino ou d'un renard.

Sur cet exemple :

  • les caractéristiques numériques des individus sont données par les champs 'logique', 'force' et 'cooperation',
  • l'étiquette ou classe des individus est donnée par le champ 'famille'.

Le principe de l'algorithme des k plus proches voisins est le suivant :

    1. Pour chaque individu de la population, calculer sa distance au personnage dont on cherche à prédire la famille,
    1. Trier ensuite les individus de la population par distance croissante,
    1. Ne garder que les k ayant la plus petite distance,
    1. Parmi ces k individus, prédire la famille qui est la plus présente parmi eux.

On pourra consulter cette image animée pour une visualisation plus graphique de cet algorithme.

📝 Fin des rappels 📝

Sur notre exemple voici ce que cela donne en prenant k = 5:

  • On calcule les distances au personnage puis on trie par distance croissante (remarquer que les individus en haut de la table ont des caractéristiques très proches de l'individu que l'on cherche à classifier) :
perso = {'famille': '???', 'logique': 5, 'force': 5, 'cooperation': 4}

population =    [{'famille': 'renard', 'logique': 5, 'force': 6, 'cooperation': 4, 'distance': 1.0} ,
                 {'famille': 'renard', 'logique': 6, 'force': 4, 'cooperation': 4, 'distance': 1.41} ,
                 {'famille': 'renard', 'logique': 6, 'force': 6, 'cooperation': 5, 'distance': 1.73} ,
                 {'famille': 'rat',    'logique': 5, 'force': 3, 'cooperation': 5, 'distance': 2.24} ,
                 {'famille': 'rhino',  'logique': 4, 'force': 7, 'cooperation': 3, 'distance': 2.45} ,
                 {'famille': 'renard', 'logique': 7, 'force': 6, 'cooperation': 3, 'distance': 2.45} ,
                 {'famille': 'rat',    'logique': 4, 'force': 3, 'cooperation': 5, 'distance': 2.45} ,
                 {'famille': 'rhino',  'logique': 6, 'force': 6, 'cooperation': 6, 'distance': 2.45} ,
                 {'famille': 'renard', 'logique': 6, 'force': 6, 'cooperation': 6, 'distance': 2.45} ,
                 {'famille': 'rhino',  'logique': 5, 'force': 8, 'cooperation': 4, 'distance': 3.0} ,
                 {'famille': 'rhino',  'logique': 3, 'force': 6, 'cooperation': 6, 'distance': 3.0} ,
                 {'famille': 'rhino',  'logique': 6, 'force': 8, 'cooperation': 3, 'distance': 3.32} ,
                 {'famille': 'rat',    'logique': 6, 'force': 4, 'cooperation': 7, 'distance': 3.32} ,
                 {'famille': 'rhino',  'logique': 7, 'force': 8, 'cooperation': 5, 'distance': 3.74} ,
                 {'famille': 'renard', 'logique': 8, 'force': 4, 'cooperation': 6, 'distance': 3.74} ,
                 {'famille': 'rhino',  'logique': 5, 'force': 9, 'cooperation': 4, 'distance': 4.0} ,
                 {'famille': 'rat',    'logique': 6, 'force': 4, 'cooperation': 8, 'distance': 4.24} ,
                 {'famille': 'rat',    'logique': 5, 'force': 3, 'cooperation': 8, 'distance': 4.47} ,
                 {'famille': 'rat',    'logique': 4, 'force': 2, 'cooperation': 8, 'distance': 5.1} ,
                 {'famille': 'rhino',  'logique': 7, 'force': 9, 'cooperation': 7, 'distance': 5.39}]
  • On ne garde que les k = 5 plus proches de notre individu :
cinq_plus_proches = [{'famille': 'renard', 'logique': 5, 'force': 6, 'cooperation': 4, 'distance': 1.0} ,
                     {'famille': 'renard', 'logique': 6, 'force': 4, 'cooperation': 4, 'distance': 1.41} ,
                     {'famille': 'renard', 'logique': 6, 'force': 6, 'cooperation': 5, 'distance': 1.73} ,
                     {'famille': 'rat',    'logique': 5, 'force': 3, 'cooperation': 5, 'distance': 2.24} ,
                     {'famille': 'rhino',  'logique': 4, 'force': 7, 'cooperation': 3, 'distance': 2.45}]    
  • Parmi eux il y a 3 renards, 1 rat et 1 rhino : on prédit donc que la classe de notre individu est 'renard'.

Question 1 :

La fonction distance ci-dessous permet de calculer la distance entre deux individus représentés par leur dictionnaire (comme ci-dessus).

En déduire la distance entre les deux individus test1 et test2.

Entrée[ ]:
Entrée[ ]:

Question 2 :

En utilisant notamment la méthode deepcopy du module copy, programmer la fonction completer_et_trier qui :

  • prend en paramètres :

    • une table population modélisant une population d'individus (comme ci-dessus),
    • un dictionnaire personnage dont on souhaite déterminer la classe (comme ci-dessus),
  • renvoie une copie de cette table avec le champ 'distance' ajouté à chacun des individus, copie qui sera triée par ordre croissant de distance.

Pour cela on codera également une fonction clef de tri qui renvoie la valeur d'un dictionnaire associée à la clef 'distance'.

Entrée[ ]:
Entrée[ ]:
Solution
from copy import deepcopy

def dist(personnage):
    return personnage['distance']

def completer_et_trier(population, personnage):
    population_copy = deepcopy(population)
    for individu in population_copy:
        individu['distance'] = distance(individu, personnage)
    
    population_copy.sort(key = dist, reverse = False)
    return population_copy

Question 3 :

Programmer une fonction prediction qui :

  • prend en paramètres :
    • une table pop_triee modélisant la population, complétée avec les distances et triée par ordre croissant,
    • un entier positif k
  • renvoie la famille majoritaire au sein des k premiers individus de la table (c'est à dire la famille majoritaire au sein des k plus proches voisins).

On pourra utiliser la fonction max_dico qui renvoie la clef correspondant à la plus grande valeur d'un dictionnaire.

Entrée[ ]:
Entrée[ ]:
Entrée[ ]:
Solution
def prediction(pop_triee, k):
    compteurs = {'renard' : 0, 'rat': 0, 'rhino': 0} # avec ce dictionnaire on compte les renards, rats et rhinos
    for i in range(k):
        compteurs[pop_triee[i]['famille']] += 1
    return max_dico(compteurs)

Question 4 :

En utilisant les fonctions des questions 2 et 3 effectuer une prédiction pour la situation ci-dessous.

Vérifier que pour k = 3 et k = 6 on n'obtient pas la même prédiction.

Entrée[ ]:
Entrée[ ]:
Solution

Avec k = 3 la prédiction est 'rat' alors qu'avec k = 6 la prédiction est 'renard' :

pop_triee = completer_et_trier(population, personnage)
prediction(pop_triee, 3), prediction(pop_triee, 6)     

Pour information

Fonction permettant de générer des individus dont les trois caractéristiques (logique, force, coopération) sont, pour chacune des trois familles, incluses dans des «parallélépipèdes en 3D» qui se chevauchent partiellement.

Entrée[ ]: