1NSI / Séquence 10 : Argent, sac-à-dos et boule de cristal / Chapitre 2 : Algorithme des k plus proches voisins
Algorithmes des $k$ plus proches voisins

Activité d’introduction

Objectifs :

Nous allons travailler avec le fichier pokemons.csv contenant certaines caractéristiques de Pokémons. Chaque Pokémon du fichier est caractérisé par : son type, ses points de vie et la valeur de son attaque. Pour simplifier, nous ne considérons que deux types de Pokémon : Eau et Psy.

Question 1 : Ouvrez le fichier pokemons.csv avec le bloc note pour visualiser son contenu. Quel est le caractère de séparation utilisé ?

Réponse :

On peut mémoriser les données du fichier csv dans une table pokemons afin de pouvoir travailler sur les données.

import csv
fichier = open('data/pokemons.csv', 'r', encoding = 'UTF-8')
t = csv.DictReader(fichier, delimiter=';')
pokemons = [dict(ligne) for ligne in t] # création et construction du tableau par compréhension
fichier.close()

On peut alors afficher le contenu de la table pokemons.

pokemons
[{'Nom': 'Aligatueur', 'Type': 'Eau', 'Points de vie': '85', 'Attaque': '105'},
 {'Nom': 'Bargantua', 'Type': 'Eau', 'Points de vie': '70', 'Attaque': '92'},
 {'Nom': 'Carabaffe', 'Type': 'Eau', 'Points de vie': '59', 'Attaque': '63'},
 {'Nom': 'Clamiral', 'Type': 'Eau', 'Points de vie': '95', 'Attaque': '100'},
 {'Nom': 'Crefadet', 'Type': 'Psy', 'Points de vie': '75', 'Attaque': '125'},
 {'Nom': 'Crocrodil', 'Type': 'Eau', 'Points de vie': '65', 'Attaque': '80'},
 {'Nom': 'Deoxys', 'Type': 'Psy', 'Points de vie': '50', 'Attaque': '70'},
 {'Nom': 'Deoxys', 'Type': 'Psy', 'Points de vie': '50', 'Attaque': '95'},
 {'Nom': 'Deoxys', 'Type': 'Psy', 'Points de vie': '50', 'Attaque': '150'},
 {'Nom': 'Deoxys', 'Type': 'Psy', 'Points de vie': '50', 'Attaque': '180'},
 {'Nom': 'Ecayon', 'Type': 'Eau', 'Points de vie': '49', 'Attaque': '49'},
 {'Nom': 'Eoko', 'Type': 'Psy', 'Points de vie': '75', 'Attaque': '50'},
 {'Nom': 'Gamblast', 'Type': 'Eau', 'Points de vie': '71', 'Attaque': '73'},
 {'Nom': 'Gobou', 'Type': 'Eau', 'Points de vie': '50', 'Attaque': '70'},
 {'Nom': 'Groret', 'Type': 'Psy', 'Points de vie': '80', 'Attaque': '45'},
 {'Nom': 'Mateloutre', 'Type': 'Eau', 'Points de vie': '75', 'Attaque': '75'},
 {'Nom': 'Mesmerella', 'Type': 'Psy', 'Points de vie': '60', 'Attaque': '45'},
 {'Nom': 'Mew', 'Type': 'Psy', 'Points de vie': '100', 'Attaque': '100'},
 {'Nom': 'Mewtwo', 'Type': 'Psy', 'Points de vie': '106', 'Attaque': '110'},
 {'Nom': 'Mewtwo', 'Type': 'Psy', 'Points de vie': '106', 'Attaque': '150'},
 {'Nom': 'Mewtwo', 'Type': 'Psy', 'Points de vie': '106', 'Attaque': '190'},
 {'Nom': 'Munna', 'Type': 'Psy', 'Points de vie': '76', 'Attaque': '25'},
 {'Nom': 'Nucleos', 'Type': 'Psy', 'Points de vie': '45', 'Attaque': '30'},
 {'Nom': 'Octillery', 'Type': 'Eau', 'Points de vie': '75', 'Attaque': '105'},
 {'Nom': 'Okeoke', 'Type': 'Psy', 'Points de vie': '95', 'Attaque': '23'},
 {'Nom': 'Phione', 'Type': 'Eau', 'Points de vie': '80', 'Attaque': '80'},
 {'Nom': 'Poissoroy', 'Type': 'Eau', 'Points de vie': '80', 'Attaque': '92'},
 {'Nom': 'Prinplouf', 'Type': 'Eau', 'Points de vie': '64', 'Attaque': '66'},
 {'Nom': 'Rosabyss', 'Type': 'Eau', 'Points de vie': '55', 'Attaque': '84'},
 {'Nom': 'Siderella', 'Type': 'Psy', 'Points de vie': '70', 'Attaque': '55'},
 {'Nom': 'Spoink', 'Type': 'Psy', 'Points de vie': '60', 'Attaque': '25'},
 {'Nom': 'Symbios', 'Type': 'Psy', 'Points de vie': '110', 'Attaque': '65'},
 {'Nom': 'Tarpaud', 'Type': 'Eau', 'Points de vie': '90', 'Attaque': '75'},
 {'Nom': 'Tiplouf', 'Type': 'Eau', 'Points de vie': '53', 'Attaque': '51'}]

Question 2 : Quel est le type de données des éléments du tableau pokemons ?

Réponse :

Prenons le premier Pokemon de la table (n’oubliez pas d’exécuter la cellule ci-dessous pour que la variable pokemon1soit créée).

pokemon1 = {'Nom': 'Aligatueur', 'Type': 'Eau', 'Points de vie': '85', 'Attaque': '105'}

Question 3 : Ecrivez les instructions permettant d’accéder à son type, puis à son nombre de points de vie et enfin à sa valeur d’attaque.

# à compléter
# à compléter
# à compléter

Question 4 : Quel est le nom du pokémon n°27 de la table pokemons ?

# à compléter

Récupérer des données simples

Imaginons que nous souhaitions connaître la valeur d’attaque du Pokémon 'Groret'. La méthode la plus naturelle est de parcourir toute la table jusqu’à trouver ce Pokémon et d’afficher sa valeur d’attaque.

for p in pokemons:
    if p['Nom'] == 'Groret':
        print(p['Attaque'])
45

Question 5 : Ecrivez une fonction type_de(nom, pokemons) qui renvoie le type du pokemon appelé nom_pokemon (chaîne de caractères) de la table pokemons. Quelques assertions devant être vérifiées par votre fonction sont données ci-dessous.

def type_de(nom_pokemon, pokemons):
    for p in pokemons:
        # à compléter
        
assert type_de('Symbios', pokemons) == 'Psy'
assert type_de('Clamiral', pokemons) == 'Eau'

Sélection de lignes

Il est très rapide de sélectionner les lignes d’une table qui nous intéressent pour créer une nouvelle table.

A partir de la table de départ, on peut facilement créer une nouvelle table contenant tous les Pokémons dont la valeur d’attaque vaut 80. Voici comment faire avec une construction par compréhension.

pokemon_attaque_80 = [p for p in pokemons if int(p['Attaque']) == 80]
pokemon_attaque_80
[{'Nom': 'Crocrodil', 'Type': 'Eau', 'Points de vie': '65', 'Attaque': '80'},
 {'Nom': 'Phione', 'Type': 'Eau', 'Points de vie': '80', 'Attaque': '80'}]

Vous noterez qu’il était impératif de convertir la chaîne de caractères renvoyée par p['Attaque'] en un entier pour faire la comparaison avec 80.

Question 6 : Créez une table resistants contenant les Pokemons dont les points de vie sont supérieurs ou égaux à 100.

# à compléter

Question 7 : Créez une table pokemons_eau et une table pokemons_psy contenant respectivement tous les Pokémons de type 'Eau'.

# à compléter
# à compléter

Si les deux tests suivants ne sont pas validés, vous devez reprendre la question 7.

assert len(pokemons_eau) == 16
assert len(pokemons_psy) == 18

Question 8 : Que signifient ces deux assertions ?

Réponse :

Classification des Pokemons

Nous allons utiliser la bibliothèque matplotlib pour représenter graphiquement nos données sur les Pokémons.

Travail préliminaire

Le code suivant permet de représenter un nuage de points dont les coordonnées sont stockées dans deux tableaux.

%matplotlib inline
import matplotlib.pyplot as plt
X = [0, 2, 5, 9, 7]  # tableau avec les abscisses
Y = [5, 7, 12, 3, 8] # tableau avec les ordonnées
plt.plot(X,Y,'ro') # r pour red, o pour un cercle. voir https://matplotlib.org/api/markers_api.html
plt.show()

png

Question 9 : Rendez-vous à l’adresse https://matplotlib.org/api/markers_api.html. Modifiez le code précédent pour remplacer les cercles rouges par des carrés bleus.

On peut représenter dans un repère les différents Pokémons en fonction de leurs points de vie (en asbcisse) et de leus valeurs d’attaque (en ordonnée).

points_de_vie = [int(p['Points de vie']) for p in pokemons] # construction du tableau des points de vie
valeur_attaque = [int(p['Attaque']) for p in pokemons] # construction du tableau des valeurs d'attaque
plt.plot(points_de_vie, valeur_attaque, 'ro') # construction du graphique
plt.show() # affichage du graphique

png

Classification selon le type

Question 10 : Faites apparaître sur le même graphique, les Pokémons de type 'Eau' en bleu et les Pokémons de type 'Psy' en rouge. On mettra, comme précédemment, leurs points de vie en abscisses et leurs valeurs d’attaques en ordonnées.

%matplotlib inline
import matplotlib.pyplot as plt
# à compléter

Vous devez obtenir un graphique similaire à celui ci-dessous dans lequel les points bleus désignent les Pokémons de type 'Eau' et les points rouges ceux de type 'Psy'.

graphique

La répartition des points laisse apparaître assez clairement deux classes.

Question 11:

Réponse :


Références :


Germain BECKER, Lycée Mounier, ANGERS Licence Creative Commons