Chapitre 5: Algorithme des k plus proches voisins

Principe

Principe de l’apprentissage supervisé

À l’heure actuelle, l’intelligence artificielle se base souvent sur l’utilisation de données annotées que l’on fournit à l’ordinateur pour qu’il y trouve des similarités(c’est ce que l’on appelle de l’apprentissage supervisé).

Principe l’algorithme des k plus proches voisins

On dispose d’une collection de données annotées, et on veut savoir à quelle catégorie appartient un nouvel échantillon. Il s’agit d’un problème de classification.

Prenons l’exemple suivant issu de cette page.

Imaginons… On étudie des papillons. Ceux-ci ont une certaine largeur et une certaine longueur. Certains sont des males, d’autres des femelles.

On étudie un certain nombre de ces papillons. Cela constitue un jeu d’apprentissage dont les caractéristiques sont représentées ci-dessous.

A partir de ce jeu d’apprentissage, on cherche à prédire le sexe d’un papillon dont on connaît les dimensions.

L’objectif est maintenant d’identifier le sexe d’un nouveau papillon en s’appuyant sur notre expérience précédente.

Le principe est simple : On fait l’hypothèse que notre papillon a le même sexe que ces voisins.

On voit par exemple que le voisin le plus proche est un paillon mâle:

Cependant, la particularité de l’algorithme des k plus proches voisins est le fait que l’on puisse choisir $k$ , le nombre de plus proches voisins nous permettant de faire notre choix, on va prendre plusieurs voisins pour éviter de se baser que sur une observation pour notre choix.

Voici par exemple l’application pour $k=5$ :

Implémentation naïve en Python

Le code qui suit utilise des méthodes de pandas matplotlib et numpy non vues, il n’est pas nécessaire de savoir le refaire, par contre en utilisant les commentaires vous pouvez voir comment est effectuée la classification dans cette implémentation.

Classification d’élèves en conseil de classe

Nous allons utiliser un fichier csv qui contient les moyennes, absences et mentions d’élèves de lycée.

Vous pouvez visualiser ce fichier ici: https://framagit.org/lyceum/k-plus-proches-voisins/blob/master/data/mentions-anonymised.csv

À partir de ce fichier de données l’algorithme sera capable de vous indiquer quelle sera votre mention (Félicitations, compliments…) en fonction de notre moyenne générale et notre nombre d’absences.

Tracé de la classification

Commençons par observer l’ensemble des données sous forme graphique pour se faire une idée.

%matplotlib inline
import pandas as pd
import matplotlib.pyplot as plt
import numpy as np

# Lecture des données du conseil de classe 
df = pd.read_csv('./data/mentions-anonymised.csv')

# On affiche 3 échantillons du tableau
df.sample(3)

# on ne conserve que 3 colonnes pour cette étude simplifiée
df =  df.loc[:, ['Moyenne Générale', '1/2j abs', 'Mentions']]
df

def tracé_graph():
    for mention in ["Pas de mention","Encouragements", "Compliments", "Félicitations"]:
        df_mention = df.loc[df["Mentions"] == mention]
        plt.scatter(df_mention["1/2j abs"], df_mention["Moyenne Générale"], label=mention, alpha=0.5)
    plt.legend()
tracé_graph()

def k_plus_proches_voisins(moyenne, absences, k=3):
    """Renvoie la classe des k plus proches voisins
    
    Entrée:
        moyenne: moyenne de l'élève
        absences: nb de 1/2j d'absences lors du trimestre
        k: nombre de voisins les plus proches à utiliser(par défaut 3)
        
    Sortie:
        renvoie les classe la plus probable des k plus porches voisins"""
    
    # on commence par afficher notre point sur un graphique
    plt.scatter(absences, moyenne, label="Elève étudié", marker="P")
    
    # on crée une liste pour stocker les distances euclidiennes
    df['distance'] = df.apply(lambda row: ((row["Moyenne Générale"] - moyenne)**2 + (row["1/2j abs"] - absences)**2)**0.5, axis=1)
    # On affiche les trois plus courtes distances
    df_voisins = df.iloc[df.distance.sort_values().index[:k]]
    print(df_voisins)
    # on les marque sur le graph
    plt.scatter(df_voisins["1/2j abs"],
                df_voisins["Moyenne Générale"],
                label="Plus proches voisins", marker="*")
    # On ajoute tous les autres points
    tracé_graph()
    return df_voisins["Mentions"].value_counts().nlargest(1)

Appels de la fonction

k_plus_proches_voisins(12.5, 10)

    Moyenne Générale  1/2j abs        Mentions  distance
32              12.3      11.0     Compliments  1.019804
62              11.6       9.0  Pas de mention  1.345362
66              11.4       9.0  Pas de mention  1.486607

Mentions
Pas de mention    2
Name: count, dtype: int64

k_plus_proches_voisins(12.5, 5)

    Moyenne Générale  1/2j abs        Mentions  distance
65              12.4       5.0  Encouragements       0.1
46              12.9       5.0     Compliments       0.4
58              12.5       4.0  Encouragements       1.0

Mentions
Encouragements    2
Name: count, dtype: int64