Algorithme de classification par les K plus proches voisins

Exercice 1 : prédiction

En guise d'introduction au problème de classification par l'algorithme des k plus proches voisins, répondez au QCM réalisé par Alain Busser :

🥀 QCM

Algorithme de prédiction par les K plus proches voisins

  • Entrées :

    • Un jeu de données d'apprentissage étiquetées c'est-à-dire qu'on dispose d'une table d'enregistrements qui sont caractérisés par des descripteurs et pour lesquels on connaît une étiquette. Par exemple, on a une collection de Pokemons décrits par leur 'nom', leur 'vitesse' et leur 'défense' et pour chacun on connaît une étiquette de 'type' qui peut être 'Feu' ou 'Roche' :
    🐍 Console Python
    [{'nom': 'Salameche', 'defense': '43', 'vitesse': '65', 'type': 'Feu'}, {'nom': 'Reptincel', 'defense': '58', 'vitesse': '80', 'type': 'Feu'}, {'nom': 'Goupix', 'defense': '40', 'vitesse': '65', 'type': 'Feu'}, {'nom': 'Feunard', 'defense': '75', 'vitesse': '100', 'type': 'Feu'}, ..., {'nom': 'Geolithe', 'defense': '105', 'vitesse': '20', 'type': 'Roche'}, {'nom': 'Gigalithe', 'defense': '130', 'vitesse': '25', 'type': 'Roche'}]

    • Une donnée dont l'étiquette est inconnue c'est-à-dire un enregistrement absent du jeu de données d'apprentissage avec les mêmes descripteurs mais sans étiquette.

    • Un paramètre de voisinage \(K\)

    • Une distance.

      Plusieurs distances possibles

      Si on caractérise chaque Pokemon par deux descripteurs 'vitesse' et 'defense', on peut les représenter dans le plan par les points A de coordonnées \((58, 65)\) et B de coordonnées \((80, 58)\). On peut alors calculer la distance AB de plusieurs façons :

      La distance euclidienne qui correspond à celle de la règle graduée : \(AB=\sqrt{(x_{B}-x_{A})^{2}+(y_{B}-y_{A})^{2}}=\sqrt{(80-58)^{2}+(58-65)^{2}} \approx 23,087\)

      alt

      La distance de Manhattan qui correspond à la longueur du chemin parcouru pour aller de \(A\) à \(B\) en se déplaçant le long des arêtes d'un quadrillage généré par un repère orthonormé du plan, comme dans le plan d'une ville où les rues se coupent à angle droit : \(AB=\vert x_{B}-x_{A} \vert + \vert y_{B}-y_{A} \vert =\vert 80 - 58 \vert + \vert 58 - 65 \vert = 22 + 7 = 29\)

      alt

  • Problème à résoudre :

    Comment prédire l'étiquette de la nouvelle donnée à partir des données du jeu de données d'apprentissage ?

    Exemple : prédiction du type d'un Pokémon

    Par exemple on connaît les types des Pokémons du jeu de données d'apprentissage, qu'on a représenté dans le plan en fonction des valeurs de leurs descripteurs 'vitesse' et 'défense'. On attrape un nouveau Pokémon (marqué par une croix), on dispose de sa 'vitesse' et de sa 'défense', comment prédire son type ?

    alt

  • Traitement :

    • On calcule, en fonction des descripteurs et de la distance sélectionnés, les distances entre l'enregistrement sans étiquette et tous les enregistrements du jeu de données d'apprentissage.
    • On sélectionne les K plus proches voisins du nouvel enregistrement.
    • On détermine l'étiquette majoritaire (la plus représentée) parmi ces K plus proches voisins.

    Imparité

    Pour éviter les cas d'égalité il est important de choisir K impair !

  • Sortie :

    • L'algorithme renvoie la prédiction d'une valeur d'étiquette pour l' enregistrement sans étiquette. Il a choisi la valeur majoritaire parmi les étiquettes de ses K plus proches voisins dans le jeu de données d'apprentissage.
Un algorithme d'apprentissage supervisé

L'algorithme de prédiction par les K plus proches voisins est un exemple simple d'algorithme de classification par apprentissage supervisé (machine learning): il exploite un jeu de données connu pour apporter une information, plausible mais pas forcément exacte sur une nouvelle donnée. C'est un apprentissage paresseux car il ne construit pas de modèle comme pour un réseau de neurones, il mémorise les données d'entraînement et cherche les K points les plus proches parmi les données d'entraînement pour classifier le nouveau point.

Cette famille d'algorithmes est rattachée à la branche de l'informatique dénommée intelligence artificielle qui peut être définie comme la conception des agents rationnels, autonomes et adaptatifs pour résoudre des problèmes « comme ou mieux » que ne le ferait un être humain.

L'intelligence artificielle est apparue dès les débuts de l'informatique dans les années 1950, le mythe d'une créature artificielle intelligente étant un classique de la littérature (Golem, Frankenstein ...). Après avoir connu, un hiver pendant les années 1980-1990, un renouveau important a lieu depuis les années 2000. Le développement d'idées anciennes comme les réseaux de neurones a été favorisé par une accélération des performances matérielles (GPU) et des volumes de données disponibles (essor du web). Les réseaux de neurones profonds (deep learning) rendent possibles des applications proches de certaines aptitudes considérées auparavant comme caractéristiques de l'humain: reconnaissance d'image, du langage, prise de décision ...

Exercice 2 : ours ou phoque ?

Pour expérimenter l'algorithme de prédiction par les K plus proches voisins, tester l'application développée par Frédéric Boissac. Il faut d'abord positionner des ours ou des phoques sur la banquise, qui constituent le jeu de données d'apprentissage. Puis on place un animal inconnu. Enfin on détermine l'espèce de cet animal avec l'algorithme de prédiction par les K plus proches voisins. On peut faire varier les valeurs du paramètre K.

🐻‍❄️ 🦭 Application

Influence du paramètre K

La prédiction par l'algorithme des K plus proches voisins dépend du paramètre K choisi (toujours impair !).

On donne deux exemples de prédiction réalisées avec l'application de l'exercice 21 dans le cas ci-dessous :

alt

alt

alt

Exercice 3 : classification d'un Pokemon

Compléter les codes sur 💻 Capytale

Dans toutes les questions de cet exercice, on utilise un jeu de données d'apprentissage constitué d'une table table_pokemons de Pokemons représentés par des dictionnaires avec quatre clefs :

  • 'nom' de valeur le nom du Pokemon de type str
  • 'vitesse' de valeur la vitesse du Pokemon de type int
  • 'defense' de valeur la défense du Pokemon de type int
  • 'type' de valeur le type du Pokemon de type str

A chaque Pokemon on associe dans un repère du plan le couple constitué de sa vitesse et de sa défense. On définit la distance entre deux Pokemons comme la distance euclidienne entre leurs couples de coordonnées.

On veut prédire le type d'un nouveau Pokemon dont on connaît la vitesse et la défense mais pas le type, en fonction du type majoritaire parmi ses K plus proches voisins.

Dans cet exercice, vous pouvez réutiliser dans une question les fonctions qui ont validé les tests des questions précédentes.

Table de pokemons
🐍 Script Python
table_pokemons = [
{"nom": "Salameche", "vitesse": 65, "defense": 43, "type": "Feu"},
{"nom": "Reptincel", "vitesse": 80, "defense": 58, "type": "Feu"},
{"nom": "Goupix", "vitesse": 65, "defense": 40, "type": "Feu"},
{"nom": "Feunard", "vitesse": 100, "defense": 75, "type": "Feu"},
{"nom": "Caninos", "vitesse": 60, "defense": 45, "type": "Feu"},
{"nom": "Arcanin", "vitesse": 95, "defense": 80, "type": "Feu"},
{"nom": "Ponyta", "vitesse": 90, "defense": 55, "type": "Feu"},
{"nom": "Galopa", "vitesse": 105, "defense": 70, "type": "Feu"},
{"nom": "Magmar", "vitesse": 93, "defense": 57, "type": "Feu"},
{"nom": "Pyroli", "vitesse": 65, "defense": 60, "type": "Feu"},
{"nom": "Hericendre", "vitesse": 65, "defense": 43, "type": "Feu"},
{"nom": "Feurisson", "vitesse": 80, "defense": 58, "type": "Feu"},
{"nom": "Typhlosion", "vitesse": 100, "defense": 78, "type": "Feu"},
{"nom": "Limagma", "vitesse": 20, "defense": 40, "type": "Feu"},
{"nom": "Magby", "vitesse": 83, "defense": 37, "type": "Feu"},
{"nom": "Entei", "vitesse": 100, "defense": 85, "type": "Feu"},
{"nom": "Poussifeu", "vitesse": 45, "defense": 40, "type": "Feu"},
{"nom": "Chartor", "vitesse": 20, "defense": 140, "type": "Feu"},
{"nom": "Ouisticram", "vitesse": 61, "defense": 44, "type": "Feu"},
{"nom": "Maganon", "vitesse": 83, "defense": 67, "type": "Feu"},
{"nom": "Gruikui", "vitesse": 45, "defense": 45, "type": "Feu"},
{"nom": "Flamajou", "vitesse": 64, "defense": 48, "type": "Feu"},
{"nom": "Flamoutan", "vitesse": 101, "defense": 63, "type": "Feu"},
{"nom": "Darumarond", "vitesse": 50, "defense": 45, "type": "Feu"},
{"nom": "Darumacho", "vitesse": 95, "defense": 55, "type": "Feu"},
{"nom": "Aflamanoir", "vitesse": 65, "defense": 66, "type": "Feu"},
{"nom": "Feunnec", "vitesse": 60, "defense": 40, "type": "Feu"},
{"nom": "Roussil", "vitesse": 73, "defense": 58, "type": "Feu"},
{"nom": "Simularbre", "vitesse": 30, "defense": 115, "type": "Roche"},
{"nom": "Tarinor", "vitesse": 30, "defense": 135, "type": "Roche"},
{"nom": "Regirock", "vitesse": 50, "defense": 200, "type": "Roche"},
{"nom": "Kranidos", "vitesse": 58, "defense": 40, "type": "Roche"},
{"nom": "Charkos", "vitesse": 58, "defense": 60, "type": "Roche"},
{"nom": "Manzai", "vitesse": 10, "defense": 95, "type": "Roche"},
{"nom": "Nodulithe", "vitesse": 15, "defense": 85, "type": "Roche"},
{"nom": "Geolithe", "vitesse": 20, "defense": 105, "type": "Roche"},
{"nom": "Gigalithe", "vitesse": 25, "defense": 130, "type": "Roche"},
 ]
Question 1

Compléter la fonction pokemon_to_coord qui à un Pokemon associe son couple de coordonnées (vitesse, distance).

🐍 Script Python
def pokemon_to_coord(pok):
    """
    Parameters
    ----------
        pok représente un pokemon sous la forme d'un dictionnaire de clefs
        "nom", "defense", "vitesse", "type" :

        {"nom": "Manzai", "defense": 95, "vitesse": 10, "type": "Roche"}

    Returns
    -------
        couple de valeurs (vitesse, defense) de type tuple du pokemon
    """
    return ...
Correction
🐍 Script Python
def pokemon_to_coord(pok):
    """
    Parameters
    ----------
        pok représente un pokemon sous la forme d'un dictionnaire de clefs
        "nom", "defense", "vitesse", "type" :

        {"nom": "Manzai", "defense": 95, "vitesse": 10, "type": "Roche"}

    Returns
    -------
        couple de valeurs (vitesse, defense) de type tuple du pokemon
    """
    return (pok["vitesse"], pok["defense"])
Question 2

Compléter la fonction distance_euclidienne qui prend en arguments deux couples de coordonnées (vitesse, distance) et renvoie la distance eurclidienne entre les deux.

Comparaison de deux flottants

Pour comparer deux flottants on utilise la fonctions indiscernables qui teste si l'écart entre les deux est inférieur à \(10^{-15}\).

🐍 Script Python
def indiscernables(f1, f2):
    """Test si deux flottants sont indiscernables
    près

    Args:
        f1 et f2 de type float

    Returns:
        booléen
    """
    return abs(f1 - f2) < 10 ** (-15)
🐍 Script Python
import math

def indiscernables(f1, f2):
    """Test si deux flottants sont indiscernables
    près

    Args:
        f1 et f2 de type float

    Returns:
        booléen
    """
    return abs(f1 - f2) < 10 ** (-15)

def distance_euclidienne(coord1, coord2):
    """
    Parameters
    ----------
        coord1 et coord2 deux couples d'entiers représentant
        des coordonnées (vitesse, defense) associées à des Pokemons

    Returns
    -------
        distance euclidienne entre coord1 et coord2 de type float
    """
    # déballage de tuple
    x1, y1 = coord1
    x2, y2 = coord2
    return ...
Correction
🐍 Script Python
def distance_euclidienne(coord1, coord2):
    """
    Parameters
    ----------
        coord1 et coord2 deux couples d'entiers représentant
        des coordonnées (vitesse, defense) associées à des Pokemons

    Returns
    -------
        distance euclidienne entre coord1 et coord2 de type float
    """
    x1, y1 = coord1
    x2, y2 = coord2
    return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
Question 3

Compléter la fonction table_distance qui prend en argument un nouveau Pokemon représenté par un dictionnaire ayant au moins pour clefs vitesse et defense et qui renvoie un tableau des couples (distance entre le nouveau Pokemon et un Pokemon du jeu de données, type/étiquette du Pokemon du jeu de données) pour tous les Pokemons du jeu de données d'apprentissage de table_pokemons.

🐍 Script Python
import math

def table_distance(nouveau_pok):
    """
    Parameters
    ----------
    nouveau_pok: un nouveau Pokemon représenté par un dictionnaire
    avec au moins les clefs 'vitesse' et 'defense' associées à des valeurs
    de type int

    Returns
    -------
    tab_distance un tableau de tuples (distance entre nouveau_pok et un
    pokemon du jeu de données table_pokemons, étiquette de ce pokemon)
    """
    ...
Correction
🐍 Script Python
def table_distance(nouveau_pok):
    """
    Parameters
    ----------
    nouveau_pok: un nouveau Pokemon représenté par un dictionnaire
    avec au moins les clefs 'vitesse' et 'defense' associées à des valeurs
    de type int

    Returns
    -------
    tab_distance un tableau de tuples (distance entre nouveau_pok et un
    pokemon du jeu de données table_pokemons, étiquette de ce pokemon)
    """
    coord_nouveau = pokemon_to_coord(nouveau_pok)
    return [
        (distance_euclidienne(coord_nouveau, pokemon_to_coord(pok)), pok["type"])
        for pok in table_pokemons
    ]
Question 4

Compléter la fonction kpp_voisins qui prend deux arguments :

  • un tableau renvoyé par fonction table_distance : couples (distance, type/étiquette) par rapport à tous les Pokemons du jeu de données d'apprentissage de table_pokemons pour un nouveau Pokemon
  • un entier positif k

kpp_voisins renvoie le tableau des types/étiquettes des k plus proches voisins c'est-à-dire des k premiers couples lorsqu'on a trié les couples par distance croissante.

🐍 Script Python
def clef_tri(couple):
    """Clef de tri pour trier un couple de valeurs selon
    la première composante"""
    return couple[0]


def kpp_voisins(tab_distance, k):
    """
    Parameters
    ----------
    tab_distance un tableau de tuple (distance entre deux  pokemons
    , type/étiquette) renvoyé par table_distance

    k : un entier positif

    Returns
    -------
    kppv tableau des types/étiquetets des  k plus proches voisins
    selon le critère de distance
    """
    # précondition
    assert 1 <= k <= len(tab_distance)
    # tri selon la première composante de chaque tuple (la distance)
    tab_tri = sorted(tab_distance, key=...)
    kppv = ...
    return kppv
Correction
🐍 Script Python
def kpp_voisins(tab_distance, k):
    """
    Parameters
    ----------
    tab_distance un tableau de tuple (distance entre deux  pokemons
    , type/étiquette) renvoyé par table_distance

    Returns
    -------
    kppv tableau des types/étiquetets des  k plus proches voisins
    selon le critère de distance
    """
    # précondition
    assert 1 <= k <= len(tab_distance)
    # tri selon la première composante de chaque tuple (la distance)
    tab_tri = sorted(tab_distance, key=clef_tri)
    kppv = [tab_tri[i][1] for i in range(k)]
    return kppv
Question 5

Compléter la fonction element_majoritaire qui prend en argument un tableau de types/étiquettes de type str et qui renvoie le type/étiquette majoritaire.

🐍 Script Python
def element_majoritaire(k_voisins):
    """
    Parameters
    ----------
    k_voisins : tableau des types/étiquettes des k plus proches voisins

    Returns
    -------
    voisin_majoritaire : chaine de caractère type str, étiquette majoritaire
    parmi les kplus proches voisins voisins
    """
    occurence = dict()
    voisin_majoritaire = k_voisins[0]
    for voisin in k_voisins:
        if ...:
            occurence[voisin] = 1
        else:
            occurence[voisin] = ...
        if occurence[...] > occurence[...]:
            voisin_majoritaire = ...
    return voisin_majoritaire
Correction
🐍 Script Python
def element_majoritaire(k_voisins):
    """
    Parameters
    ----------
    k_voisins : tableau des types/étiquettes des k plus proches voisins

    Returns
    -------
    voisin_majoritaire : chaine de caractère type str, étiquette majoritaire
    parmi les kplus proches voisins voisins
    """
    occurence = dict()
    voisin_majoritaire = k_voisins[0]
    for voisin in k_voisins:
        if voisin not in occurence:
            occurence[voisin] = 1
        else:
            occurence[voisin] = occurence[voisin] + 1
        if (
            occurence[voisin] > occurence[voisin_majoritaire]
        ):
            voisin_majoritaire = voisin
    return voisin_majoritaire
Question 6

Compléter la fonction prediction_kpp qui prend deux arguments :

  • un nouveau Pokemon représenté sous la forme dictionnaire avec au moins deux clefs vitesse et defense, dont on ne connaît pas le type/étiquette
  • un entier positif k

prediction_kpp renvoie une prédiction du type type/étiquette de ce nouveau Pokemon par sélection de l'étiquette majoritaire parmi les étiquettes des k plus proches voisins du nouveau Pokemon dans le jeu de données d'apprentissage table_pokemons.

🐍 Script Python
def prediction_kpp(nouveau_pok, k):
    """
    Parameters
    ----------
    nouveau_pok: un nouveau Pokemon représenté par un dictionnaire
    avec au moins les clefs 'vitesse' et 'defense' associées à des valeurs
    de type in
    
    k : un entier positif, paramètre de voisinage
    
    Returns
    -------
    voisin_majoritaire : une chaine de caractère
    l'étiquette majoritaire parmi les k plus proches voisins 
    dans le jeu de données table_pokemons
    pour la distance euclidienne        
    """
    td = table_distance(...)
    kppv = kpp_voisins(..., ...)
    voisin_majoritaire = element_majoritaire(...)
    return voisin_majoritaire
Correction
🐍 Script Python
def prediction_kpp(nouveau_pok, k):
    """
    Parameters
    ----------
    nouveau_pok: un nouveau Pokemon représenté par un dictionnaire
    avec au moins les clefs 'vitesse' et 'defense' associées à des valeurs
    de type in
    
    k : un entier positif, paramètre de voisinage
    
    Returns
    -------
    voisin_majoritaire : une chaine de caractère
    l'étiquette majoritaire parmi les k plus proches voisins 
    dans le jeu de données table_pokemons
    pour la distance euclidienne        
    """
    td = table_distance(nouveau_pok)
    kppv = kpp_voisins(td, k)
    voisin_majoritaire = element_majoritaire(kppv)
    return voisin_majoritaire