Recherche de la valeur de k⚓︎
Tester les limites
Comme nous l'avons vu, le résultat obtenu peut différer selon la valeur de k utilisée. Afin de trouver la meilleure valeur de k utiliser, il est possible d'en tester plusieurs pour trouver celle qui donne les meilleurs résultats. Pour cela, il faut un nouvel échantillon que l'on peut classifier de façon exacte.
Nous allons reprendre notre carré avec 4 zones et générer de nouvelles valeurs, mais cette fois en nous concentrant sur les frontières entre les zones pour tester les valeurs limites. La fonction suivante permet de générer un échantillon de test :
from random import gauss, uniform
def generation_echantillon_test(n):
liste = []
for i in range(n):
if i%2 == 0:
x = gauss(xmoy, (xmax-xmin)/10)
y = uniform(ymin, ymax)
else:
x = uniform(xmin, xmax)
y = gauss(ymoy, (ymax-ymin)/10)
liste.append((x, y))
return liste
L'expression gauss(mu, sigma) génère une valeur aléatoire selon une loi normale d'espérance mu et d'écart-type sigma. C'est-à-dire que les valeurs obtenues sont proches de mu et plus sigma est grand, plus elles seront proches de cette valeur moyenne.
Les valeurs générées ont donc une chance sur deux d'être proches de la frontière horizontale ou de la frontière verticale. Afin de déterminer de façon exacte la catégorie à laquelle appartient chacun des points de l'échantillon de test, nous allons utiliser la fonction suivante :
def determine_categorie(pt):
x, y = pt
reponse = 0
if x > xmoy:
reponse += 1
if y > ymoy:
reponse += 2
return reponse
Ces deux fonctions peuvent être utilisée dans les exercices suivants.
Exercice 7
Écrire une fonction taux_reussite qui prend en paramètre une liste de valeurs à tester echant_test, un dictionnaire echantillon, un entier k et une fonction distance, et qui renvoie le taux de réussite obtenu en comparant les valeurs attendues avec les valeurs obtenues pour toutes les valeurs de echant_test en utilisant l'algorithme des k plus proches voisins sur l'échantillon et la distance donnés.
>>> echantillon = generation_echantillon(10)
>>> echant_test = generation_echantillon_test(100)
>>> taux_reussite(echant_test, echantillon, 3, distance_euclidienne)
0.67
>>> taux_reussite(echant_test, echantillon, 3, distance_manhattan)
0.65
>>> taux_reussite(echant_test, echantillon, 7, distance_euclidienne)
0.7
>>> taux_reussite(echant_test, echantillon, 7, distance_manhattan)
0.69
Influence de la taille de l'échantillon
Vous pouvez remarquer que lorsque la taille de l'échantillon initial augmente, le taux de réussite augmente également.
>>> echantillon = generation_echantillon(100)
>>> echant_test = generation_echantillon_test(100)
>>> taux_reussite(echant_test, echantillon, 7, distance_euclidienne)
0.93
>>> echantillon = generation_echantillon(1000)
>>> echant_test = generation_echantillon_test(100)
>>> taux_reussite(echant_test, echantillon, 7, distance_euclidienne)
0.98
Exercice 8
Écrire une fonction choix_k qui prend en paramètre une liste de valeurs à tester echant_test, un dictionnaire echantillon, un entier k_max et une fonction distance, et qui renvoie la valeur de k comprise entre 1 et k_max qui renvoie le meilleur taux de réussite pour les échantillons donnés.
>>> echantillon = generation_echantillon(10)
>>> echant_test = generation_echantillon_test(100)
>>> choix_k(echant_test, echantillon, 10, distance_euclidienne)
9
>>> choix_k(echant_test, echantillon, 10, distance_manhattan)
8
# Tests (insensible à la casse)(Ctrl+I)
Optimisation pour de très grands échantillons
La meilleur valeur de k peut être différente ou la même selon les distances et les échantillons. Lorsque la taille de l'échantillon augmente, le temps de calcul nécessaire augmente aussi. Pour limiter cette augmentation, il est possible de ne pas rechercher les k plus proches voisins pour chaque valeur de k, mais plutôt de le faire pour k_max et ensuite, lors de l'étude de la liste de plus proches voisins, il suffit de noter à chaque étape si la catégorie trouvée est la bonne ou pas.
Pour aller plus loin
Dans la base des iris, il y a également les informations sur les sépales. Cela fait donc 4 mesures par iris.
Toutes les données se trouvent dans le fichier iris-complet.csv.
Vous pouvez utiliser ce fichier pour avoir des résultats plus précis, mais cela nécessite de reprendre quasiment toutes les fonctions.
# Tests(insensible à la casse)(Ctrl+I)