Chapitre 10 : Algorithme des k plus proches voisins



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

Il va permettre de prédire si un élément est un menbre d'un groupe ou d'un catégorie donnée

Problème de classification

Une société "Amazing" souhaite faire de la publicitée ciblée selon les caractéristiques des clients.
Voici les informations recueillies sur un échantillon :
  1. Bob, 43 ans nouvel utilisateur du site effectue en moyenne 18 clics par jour.
    1. En observant son plus proche voisin, peut-on proposer à Bob un abonnement Premium ?
    2. En observant ses 3 plus proches voisins, peut-on proposer à Bob un abonnement Premium ?
  2. Bob Junior, 23 ans nouvel utilisateur du site effectue en moyenne 9 clics par jour.
    1. En observant son plus proche voisin, peut-on proposer à Bob Junior un abonnement Premium ?
    2. En observant ses 3 plus proches voisins, peut-on proposer à Bob Junior un abonnement Premium ?
    1. ...
    2. ...
    1. ...
    2. ...

Algorithme de prédiction

Nous avons à disposition une table de données : à télécharger
On souhaite déterminer à quelle 'Maison' les élements cibles suivants appartiennent : 
eleve1={'Nom': 'Hermione', 'Courage': '8', 'Loyauté': '6', 'Sagesse': '6', 'Malice': '6'}
eleve2={'Nom': 'Cho', 'Courage': '7', 'Loyauté': '6', 'Sagesse': '9', 'Malice': '6'}
eleve3={'Nom': 'Drago', 'Courage': '6', 'Loyauté': '6', 'Sagesse': '5', 'Malice': '8'}
eleve4={'Nom': 'Cédric', 'Courage': '7', 'Loyauté': '10', 'Sagesse': '5', 'Malice': '6'}

Principal général :
  1. On met en place le calcul d'une distance entre deux éléments de la table de données.
  2. On cherche les k (k étant un entier strictement positif) plus proches voisins de la cible
  3. On détermine la classe majoritaire dans les k plus proches voisins de la cible


Lecture des données


Voici une table de données sous la forme d'un fichier csv à télécharger et ci-dessous, le code Python permettant d'exploiter les données de ce fichier 
def read_csv(filename):
    """
    :param filename: (String) filename of csv file
    :return: (list of Pokemon) list of Poudlard students read
    res = []

    with open(filename) as f:
        liste_clef=f.readline()
        liste_clef=liste_clef.replace('"', '').strip().split(',')
        l = f.readline()
        while l != '':
            args = l.replace('"', '').strip().split(',')
            dico={}
            i=0
            for c in liste_clef:
                dico[c]=args[i]
                i=i+1
            res.append(dico)
            l = f.readline()
    return res


Data=read_csv("choixpeauMagique.csv")
  1. Tester le code ci-dessus.
  2. Quel est le type de la variable Data
  3. Que contient cette variable ?
  4. Combien y-a t-il d'élèves ?
  5. Combien y-a t-il d'élèves de Serpentar ?
  1. ...
  2. ...
  3. ...
  4. ...
  5. ...

Calcul de la distance


Voici deux élèves :
{'Nom': 'Adrian', 'Courage': '9', 'Loyauté': '4', 'Sagesse': '7', 'Malice': '10', 'Maison': 'Serpentar'}
{'Nom': 'Andrew', 'Courage': '9', 'Loyauté': '3', 'Sagesse': '4', 'Malice': '7', 'Maison': 'Griffondor'}
Calculer à la main la distance entre ces deux élèves ?
...

Ecrire une fonction distance qui calcule la distance entre deux élèves données ?
Par exemple : 
Adrian={'Nom': 'Adrian', 'Courage': '9', 'Loyauté': '4', 'Sagesse': '7', 'Malice': '10', 'Maison': 'Serpentar'}
Andrew={'Nom': 'Andrew', 'Courage': '9', 'Loyauté': '3', 'Sagesse': '4', 'Malice': '7', 'Maison': 'Griffondor'}
distance(Adrian,Andrew)
>>> 19
...

Recherche des voisins les plus proches


Ecrire une fonction plus_proches_voisins qui affiche le voisin le plus proche de Hermione. 
eleve1={'Nom': 'Hermione', 'Courage': '8', 'Loyauté': '6', 'Sagesse': '6', 'Malice': '6'}
...


A l'aide de votre fonction ci-dessus, compléter : 
def plus_proche_voisin(Data,eleve,k):
	'''
	Afficher  le nom de l'école des k plus proches voisins  de  eleve.
	Exemple :
	>>>Data=read_csv("choixpeauMagique.csv")
	>>>eleve={'Nom': 'Hermione', 'Courage': '8', 'Loyauté': '6', 'Sagesse': '6', 'Malice': '6', 'Maison' : ''}
	>>>plus_proche_voisin(data,eleve1,8)
['Griffondor', 'Griffondor', 'Griffondor', 'Griffondor', 'Poufsouffle', 'Serpentar', 'Griffondor', 'Serdaigle']

	'''
    
    
    
    
    
    
    
    
    return liste
Aide : 
>>> L=[(3,'Bob'),(5,'Stuart'),(1,'Roger'),(2,'Kevin')]
>>> L.sort()
>>> L
[(1, 'Roger'), (2, 'Kevin'), (3, 'Bob'), (5, 'Stuart')]
...


Tester l'algorithme ci-dessus avec plusieur valeurs de k pour déterminer la 'Maison' de : 
eleve1={'Nom': 'Hermione', 'Courage': '8', 'Loyauté': '6', 'Sagesse': '6', 'Malice': '6'}
eleve2={'Nom': 'Cho', 'Courage': '7', 'Loyauté': '6', 'Sagesse': '9', 'Malice': '6'}
eleve3={'Nom': 'Drago', 'Courage': '6', 'Loyauté': '6', 'Sagesse': '5', 'Malice': '8'}
eleve4={'Nom': 'Cédric', 'Courage': '7', 'Loyauté': '10', 'Sagesse': '5', 'Malice': '6'}
...


Compléter la fonction ci-dessous : 
def classse(Data,eleve,k):
	'''
	affiche la 'Maison' la plus fréquente dans les k plus proche voisins de eleve.
	'''
...


Remarque : Cet algorithme de prédiction n'est pas sans risque de commaitre un erreur.


Efficacité de l'algorithme

Pour déterminer la valeur de k qui provoque en moyenne le moins d'erreurs. On va procéder ainsi : 
Data=read_csv("choixpeauMagique.csv")
  1. On supprime le premier élève de Data (voir code ci-dessous)
  2. On recherche les k plus proches voisins de l'élève supprimé.
  3. On gagne un point si la prédiction est correcte.

On répéte le principe ci-dessus pour tous les élève de Data en comptant le nombre de bonnes réponses.

Remarque : Ce type d'algorithme est qualifié d' algorithme d'apprentissage. 
def supprimer(Data,eleve):
	'''
	param :  Data  est une list contenant des dictionnaires (caracteristiques des élèves)
			eleve un dictionnaire qui appartient à Data .
	result : On supprime le dictionnaire  eleve  de Data et on renvoit la liste
    L=[]
    for element in Data:
        if element!=eleve:
            L.append(element)
    return L
  1. Compléter le tableau ci-dessous :
    Valeur de k Nombre de bonnes réponses
    1
    2
    3
    ...
    15
  2. Quel est le meilleur choix pour k ?
  3. En déduire la 'Maison' des élèves : 
    eleve1={'Nom': 'Hermione', 'Courage': '8', 'Loyauté': '6', 'Sagesse': '6', 'Malice': '6'}
eleve2={'Nom': 'Cho', 'Courage': '7', 'Loyauté': '6', 'Sagesse': '9', 'Malice': '6'}
eleve3={'Nom': 'Drago', 'Courage': '6', 'Loyauté': '6', 'Sagesse': '5', 'Malice': '8'}
eleve4={'Nom': 'Cédric', 'Courage': '7', 'Loyauté': '10', 'Sagesse': '5', 'Malice': '6'}
  4. A l'aide d'un moteur de recherche, vérifier que vos prédictions sont bonnes.
...