Annuler
connectez vous
- Un petit rappel de Cours sur le dénombrement - terminale
- Sept Exercices Q.C.M. sur le dénombrement - terminale
- Complexes, calcul vectoriel, problème - sujet de bac - terminale
- Enseignement scientifique : suite, probabilité, fonction - sujet de bac - terminale
- Enseignement scientifique : suite, probabilité, fonction - sujet de bac - terminale
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. TerminaleForum de terminale Autres ressourcesTopics traitant de Autres ressources [tout]Lister tous les topics de mathématiques
Niveau terminale
algorithme des k plus proches voisins - python
Posté par anon62le
Bonjour, auriez-vous une idée de programme python pour la question suivante d'un TP de mathématiques ?
On suppose que les données d'apprentissage de la machine sont classifiées en deux catégories.
On veut placer dans l'une ou l'autre de ces deux catégories une donnée nouvelle. Pour cela, on calcule sa
distance à chacune des données déjà étiquetées et on lui attribue la catégorie de son plus proche voisin.
Exercice : Dépistage automatique d'une tumeur maligne
On se propose de répartir en deux catégories (Maligne, Bénigne) des tumeurs du sein dont on connaît un
certain nombre de caractéristiques. Dans la réalité, un tel diagnostic automatique est effectué à partir de données
d'apprentissage portant sur une cinquantaine de caractéristiques mesurées sur un échantillon d'un millier de
tumeurs déjà étiquetées « Maligne » ou « Bénigne ». Dans un souci de simplification, on se restreint ici à 2
caractéristiques (diamètre et concavité) mesurées sur un panel de 10 patientes.
Données d'apprentissage :
| Diametre | Concavite | Categorie |
| 13.2 | 8.3 | Benigne |
| 18.7 | 19.7 | Benigne |
| 8.2 | 15.9 | Maligne |
| 13.2 | 9 | Benigne |
| 13.5 | 4.8 | Maligne |
| 11.8 | 1.7 | Maligne |
| 13.6 | 1.9 | Maligne |
| 12 | 2 | Maligne |
| 18.2 | 17.7 | Benigne |
| 12 | 6.6 | Maligne |
On considère une nouvelle tumeur de diamètre et de concavité connues et on cherche à savoir si elle est
maligne (M) ou bénigne (B).
On va utiliser la méthode dite « du plus proche voisin » :
On place dans un repère les 10 points correspondant aux 10 données connues (en abscisse le diamètre,
en ordonnée la concavité), en distinguant les tumeurs malignes (triangles rouges) et les tumeurs bénignes
(losanges bleus).
On place ensuite la nouvelle donnée (représentée par un point vert) et on lui attribue la catégorie (M ou B) de son
plus proche voisin.
1)Ecrire une fonction distance qui calcule la distance entre le nouveau point et les 10 autres points et qui
range les valeurs dans une liste dans l'ordre croissant.
Fait : from math import sqrt
from matplotlib import pyplot as pl
def distance(x,y):
x_b=[13.2,18.7,13.2,18.2,8.2,13.5,11.8,13.6,12,12]
y_b=[8.3,19.7,9,17.7,15.9,4.8,1.7,1.9,2,6.6]
x=x
y=y
L=[]
for k in range(0,10):
a=sqrt((x-x_b[k])**2+(y-y_b[k])**2)
L.append(a)
pl.plot(x_b, y_b,'o',color='b')
pl.plot(x, y,'o',color='g')
pl.show
return(sorted(L))
on considère les 5 points les plus proches du nouveau point et on lui attribue
la catégorie (M ou B) la plus représentée. C'est la méthode des « k » plus proches voisins (avec k=5 ici).
a) Pourquoi préfèrera-t-on choisir un nombre impair de voisins ? --> Fait
b) Ecrire une fonction distance5 qui calcule la distance entre le nouveau point et les 5 points les plus proches de celui-ci et qui trace le graphique avec le nouveau point en bleu si on lui attribue la catégorie B, en rouge sinon. --> C'est cette question qui me pose problème.
Bonjour,
vous pouvez créer un tableau des 5 plus proches voisins du nouveau point : D5(i) avec i=1 à 5
Vous commencer par calculer la distance du nouveau point avec les 5 premiers de votre tableau de points existants. Vous les rangez dans D5(i). Vous calculer la distance ( indice k=6 du tableau de points existants) avec le suivant et comparer avec ce que vous dans D5(i) si la distance est plus grande vous laisser le tableau tel quel, sinon vous supprimer de D5(i) le voisin le plus éloigné du nouveau point et vous le remplacer par le nouveau. Trié D5(i) me semble pratique.
Tu as déjà créé une fonction appelée distance, qui renvoie un tableau avec les 10 distances, triées de la plus petite à la plus grande.
Ici, tu peux réutiliser cette fonction. Il faut garder uniquement les 5 première lignes du tableau ci-dessus.
Euh, non !
Pour la question 1, tu dis que tu as fait, mais tu n'as pas fait.
La fonction que tu proposes, elle calcule les distance entre un point nouveau et chacun des 10 points de référence. Ok.
Elle recherche la distance la plus courte. Ok.
Mais on perd en route l'information essentielle : le point le plus proche du nouveau point, c'est quel point ? Est-il de type M ou B ?
Ton énoncé n'est pas claire, il manque des choses, on fait quoi là ? Les 5 plus proches ou le plus proche ? Il faudrait tout l'énoncé avec ses questions et ses séparations de parties.
La 1) :
x=x et y=y sont des lignes inutiles.
Pour afficher des points on utilise la méthode scatter de pyplot. Si tu ne l'as pas vu en cours, ce n'est pas important, on se contentera de plot.
Mais il n'est pas demandé à cette fonction d'afficher quoi que ce soit.
Pour la b), la 1) est bizarre. C'est bien beau d'avoir une liste de distance croissante, mais si on ne sait pas quel point va avec, on va devoir tout refaire dans la b). C'est les valeurs de quoi exactement qu'on doit ranger ? Et puis elle renvoie rien cette fonction ? Pas claire.
L'ensemble des info s'écrirait comme une liste dans laquelle chaque valeur est une liste composée de [x_b[k], y_b[k], catégorie[k]]
On reprogramme une fonction similaire à sorted : on fait la liste distance, sans désordonner cette liste, et dans une nouvelle liste, pour chaque point (ici il s'agit de points à 3 coordonées), tant que sa distance est plus grande que le i_ème de la liste déjà rangée, on incrémente l'indice auquel on le rangera.
Maintenant, les 5 plus proches voisins d'un point (x,y, catégorie) correspondent aux 5 premières valeurs de la liste des données rangée dans l'ordre des distances croissantes.
Et il suffit de pl.plot(notre_liste[0], notre_liste[1]), et de gérer cette histoire de couleur.
Si on veut suivre l'énoncé tel que présenté, on connait la distance des 5 points les plus proches. Donc on teste 1 à 1 quel point correspond à cette distance dans la liste des données (attention, si on a plusieurs distances identiques pour plusieurs points différents, à ne pas attribuer à ces distances le même point). Et maintenant on connaît les 3 infos sur ces points. Plus qu'à faire ce qu'on demande.
Et pour réaliser ma proposition, le plus simple est d'utiliser le paramètre key de la fonction sorted(), mais si tu ne l'as pas vu...
salut
juste pour info :
anon62le @ 02-06-2021 à 16:39
on considère les 5 points les plus proches du nouveau point et on lui attribue
la catégorie (M ou B) la plus représentée. C'est la méthode des « k » plus proches voisins (avec k=5 ici).
a) Pourquoi préfèrera-t-on choisir un nombre impair de voisins ? --> Fait.
pourrais-tu nous dire ce que tu as répondu et pourquoi ?
on considère les 5 points les plus proches du nouveau point et on lui attribue
la catégorie (M ou B) la plus représentée. C'est la méthode des « k » plus proches voisins (avec k=5 ici).
a) Pourquoi préfèrera-t-on choisir un nombre impair de voisins ? --> Fait.
merci par avance ...
le but de choisir un nombre impair de voisin est de pouvoir trancher plus facilement entre M ou B, imaginons que notre point soit équidistant de deux points, et bien ainsi on peut trancher avec un 5ème point qui soit M ou B.
Pour l'algo python, j'ai un peu avancé mais j'ai toujours un peu de mal à comprendre cette histoire : " On reprogramme une fonction similaire à sorted : on fait la liste distance, sans désordonner cette liste, et dans une nouvelle liste, pour chaque point (ici il s'agit de points à 3 coordonées), tant que sa distance est plus grande que le i_ème de la liste déjà rangée, on incrémente l'indice auquel on le rangera. "
merci
c'est pourtant simple :
1/ on entre les points (tumeur) dans une liste (coordonnées, caractère) L1
caractère : B ou M
2/ on crée une fonction distance entre deux points
3/ on crée une liste L2 = [distance, caractère] des distances du nouveau point P (nouvelle tumeur) aux points de L1
4/ on ordonne L2 (dans l'ordre croissant) suivant la distance
5/ on prend ses cinq premiers points et on regarde leur caractère
6/ on en déduit le caractère du nouveau point P (de la nouvelle tumeur)
Si tu ne l'as pas appris, tu ne l'utilises pas.
Je te montrerai à la fin comment faire si tu veux, pour éviter d'avoir à réinventer l'eau chaude toutes les 5min.
Fais ce que t'a dit carpediem dans son dernier message. Moi je t'invitais à tout refaire du début, lui te conseille de prendre appuie sur la fonction sorted() que tu maîtrises déjà. C'est mieux. Et il sera difficile d'être plus claire.
Et j'aimerai toujours avoir un énoncé complet.
Parce que tel que présenté, l'énoncé pousse à retrouver quels sont les plus proches voisins, en connaissant leur distance.
Donne tes propositions, pas seulement tes questions.
Je comprends l'idée mais je patauge un peu.
from math import sqrt
from matplotlib import pyplot as pl
def distance5(x,y):
x_b=[13.2,18.7,13.2,18.2,8.2,13.5,11.8,13.6,12,12]
y_b=[8.3,19.7,9,17.7,15.9,4.8,1.7,1.9,2,6.6]
catégorie=['B','B','M','B','M','M','M','M','B','M']
distance=[]
L=[[x_b], [y_b], [catégorie]]
L2=[]
for k in range(0,10):
a=sqrt((x-x_b[k])**2+(y-y_b[k])**2)
distance.append(a)
for k in range(0,5):
L2.append(sorted(distance[k]),catégorie[k])
if L2.count('B')>2 :
pl.plot(x, y,'o',color='b')
else :
pl.plot(x, y,'o',color='r')
pl.plot(x_b, y_b,'o',color='g')
pl.show
return(L2)
L = [x_b, y_b, categorie] plutôt. Mais ce conseil était assez mauvais, tu ne pourras pas utliser sorted() convenablement avec cette représentation (mais bon dans ma tête on allait pas l'utiliser).
C'est mieux de lire le tableau par ligne.
C'est à dire : L = [ (13.2 , 8.3, 'B') , (diamètre, concavité, catégorie) ... ]
De même pour la liste L2, on aura [ (distance, catégorie) ], où distance et catégorie ne sont pas des listes mais la distance et la catégorie d'une tumeur.
Ainsi chaque élément de L et L2 correspond à une tumeur, et ils sont comparables.
Il y a un problème à cette ligne :
Citation :
for k in range(0,5):
L2.append(sorted(distance[k]),catégorie[k])
for k in range(0,5):
L2.append(sorted(distance[k]),catégorie[k])
sorted(distance[k]) ne trie rien du tout. Tu fais trier la liste distance[k], soit 1 nombre, tout seul. Et si tu mets sorted(distance)[k], tu ranges les distances mais les catégories ne suivent pas.
Ce qu'on fait : On a une liste L2 = [ (distance, catégorie) ...] (où on a bien la correspondance, entre les distances et leur catégorie : on sait que la k-ème tumeur de distance L2[k][0] a bien pour catégorie L2[k][1]).
sorted(L2) renverra la liste L2 rangée par distance croissante. Ainsi on ne perd pas la catégorie, car on range les tuples (distance, catégorie).
Et on n'a pas géré la couleur des points des données, comme il est demandé dans une partie de l'énoncé.
tu patauges parce que tu ne fais pas ce qu'on te dit !!!
as-tu lu ce que j'ai écrit ?
dans un premier temps on se moque de la représentation graphique !!!
mon niveau est modeste en python et NoPseudoDispo me corrigera éventuellement ...
def dist (..., ...) :
# fonction distance
n = int(input( "nb données ?")
L = []
for k in range(n) :
diam = eval(input("diamètre ?")
conc = eval(input("concavité ?")
cat = input(catégorie B ou M ?")
L.append([diam, conc, cat]
print("nouvelle tumeur")
diam = eval(input("diamètre ?")
conc = eval(input("concavité ?")
D = []
for k in range(n) :
d = dist(diam, conc, L[k][1], L[k][2]) # si c'est bien ainsi qu'on repère un élément d'une liste d'une liste !!!
D.append[d, L[k][3]]
"trier D" # on trie D suivant le premier élément des listes que D contient ...
L contient donc dans notre exemple 25 (sous) listes L = [[13,2 ; 8,3 ; B], [18,7 ; 19,7 ; B] , ....]