Principe de l'algorithme

Article Wikipedia: https://fr.wikipedia.org/wiki/M%C3%A9thode_des_k_plus_proches_voisins

Implémentation naïve en Python


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

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

# On affiche 3 échantillons du tableau
df.sample(3)
Résultat
Mentions 1/2j abs Rang Moyenne Générale PHILOSOPHIE HISTOIRE-GEOGRAPHIE MATHEMATIQUES PHYSIQUE-CHIMIE SCIENCES VIE & TERRE ED.PHYSIQUE & SPORT. ... ESPAGNOL LV2 ITALIEN LV2 JAPONAIS LV2 SPECIALITE SVT SPECIALITE PHYS NISSART LV3 SPECIALITE MATHS SPECIALITE ISN arts fac ENS. MORAL & CIVIQUE
36 Compliments 2.0 13.0 13.5 14.3 14.5 13.3 11.5 15.7 18.0 ... NaN 10.8 NaN NaN NaN 14.7 10.5 NaN NaN NaN
30 Compliments 10.0 13.9 11.0 11.0 13.5 14.0 14.2 19.5 13.0 ... 15.5 NaN NaN NaN 17.9 14.5 NaN NaN 14.0 NaN
50 Compliments 17.0 17.0 12.6 15.5 13 10.7 8.0 13.2 16.0 ... NaN NaN NaN 13.4 NaN NaN NaN NaN 16.8 NaN

3 rows × 22 columns


Entrée
# on ne conserve que 3 colonnes pour cette étude simplifiée
df =  df.loc[:, ['Moyenne Générale', '1/2j abs', 'Mentions']]
df
Résultat
Moyenne Générale 1/2j abs Mentions
0 17.4 3.0 Félicitations
1 18.1 5.0 Félicitations
2 18.2 NaN Félicitations
3 17.0 1.0 Félicitations
4 17.6 2.0 Félicitations
... ... ... ...
91 9.0 12.0 Encouragements
92 9.4 14.0 Pas de mention
93 7.7 49.0 Pas de mention
94 12.3 32.0 Pas de mention
95 11.7 33.0 Pas de mention

96 rows × 3 columns


Entrée
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()

png


Entrée
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)
        
        
    
    
    
    # on mesure la distance euclidienne de notre
k_plus_proches_voisins(12.5, 10)
Sortie
    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

Résultat
Pas de mention    2
Name: Mentions, dtype: int64

png

On observe donc que l'élève n'aurait pas de mention malgré ses 12.5 de moyenne, Voyons ce qu'il en est si on réduit le nombre d'absences à 5.


Entrée
k_plus_proches_voisins(12.5, 5)
Sortie
    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

Résultat
Encouragements    2
Name: Mentions, dtype: int64

png

L'élève a maintenant les encouragements.

Notes sur l'algorithme

Cet algorithme(brute-force) est peu efficace avec une complexité de O[DN2]O[D N^2](voir doc sklearn).

D'autres part, il serait bon de mettre à l'échelle les données utilisées, car on voit bien que l'échelle des absences est trois fois plus grande que les moyennes, et ainsi a un importance accrue dans le calcul de la distance des voisins.

Bibliographie