L'objectif de cet exercice est de prédire la couleur d'un point par rapport à ses coordonnées avec un algorithme K-NN.
Pour cela nous allons générer un ensemble de données où chaque donnée est composée de deux coordonnées et d'une couleur.
Voici une fonction qui permet de générer un ensemble de données :
from random import *
def generer_groupe():
g=[]
for a in range(randint(10,30)):
g.append([randint(0,400),randint(0,300),"red"])
for a in range(randint(10,30)):
g.append([randint(0,400),randint(0,300),"green"])
return g
generer_groupe ?
Ecrire une fonction distance2 qui renvoie la distance au carré entre 2 points connaissant leurs coordonnées.
Ecrire une fonction liste_distance_groupe de paramètres (x, y, groupe) où x et y sont des coordonnées et groupe, un ensemble de données, qui renvoie un tableau de listes [d, color] où d est la distance avec le point (x,y) et color est la couleur pour chaque donnée.
Ecrire une fonction k_proches_voisins de paramètres (k, liste) où k est le nombres de voisins plus proches et liste est le tableau générer par la fonction liste_distance_groupe, qui renvoie les k distances les plus petites et leur couleur associée.
Ecrire une fonction prediction de paramètres (x, y, k, groupe) définis précédemment qui renvoie la prédiction de lacouleur ("red" ou "green") du point de coordonnées x et y.
Modifier les fonctions (si nécessaire) pour avoir un ensemble de données avec une troisième couleur "blue".
Voici le code permettant d'obtenir cela :
from random import *
from math import sqrt
from pygame import *
def generer_groupe():
g=[]
for a in range(randint(15,30)):
g.append([randint(0,400),randint(0,300),"red"])
for a in range(randint(15,30)):
g.append([randint(0,400),randint(0,300),"green"])
for a in range(randint(15,30)):
g.append([randint(0,400),randint(0,300),"blue"])
return g
s=generer_groupe()
def distance2(x1,y1,x2,y2):
return (x1-x2)**2+(y1-y2)**2
def liste_distance_groupe(x,y,groupe):
l=[]
for a in groupe:
l.append([distance2(x,y,a[0],a[1]),a[2]])
return l
d=liste_distance_groupe(100,100,s)
def k_proches_voisins(k,liste):
liste_classee=sorted(liste, key=lambda x: x[0])
return liste_classee[:k]
def prediction(x,y,k,groupe):
global t
d=liste_distance_groupe(x,y,groupe)
t=k_proches_voisins(k,d)
red=0
green=0
for a in t:
if a[1]=="red":
red+=1
if a[1]=="green":
green+=1
blue=k - red -green
if red > green and red > blue:
return "red"
elif green > red and green > blue:
return "green"
elif blue > red and blue > green:
return "blue"
else:
return "pas de prediction"
#variables pygame
width = 640
height = 300
init()
display.set_caption('Algorithme KNN')
mafont = font.SysFont("monospace", 20)
screen = display.set_mode((width, height))
clock = time.Clock()
running = True
x=0
y=0
r=0
p=""
#k=int(input("k= "))
k=7
while running:
draw.rect(screen,(0,0,0),Rect(0,0,640,400))
draw.circle(screen, (0,100,100),(x,y), r)
red = (155,0,0)
green = (0, 155,0)
blue= (0, 0, 155)
for a in s:
if a[2]=="red":
#screen.set_at((a[0], a[1]), (0,0,0))
draw.circle(screen, (255,0,0),(a[0], a[1]), 2)
elif a[2]=="blue":
#screen.set_at((a[0], a[1]), (0,0,0))
draw.circle(screen, (0,0,255),(a[0], a[1]), 2)
else:
#screen.set_at((a[0], a[1]), (255,255,255))
draw.circle(screen, (0,255,0),(a[0], a[1]), 2)
for events in event.get():
if events.type == QUIT:
running = False
quit()
if events.type == MOUSEBUTTONDOWN:
if events.button == 1: #Si clic gauche
#On change les coordonnées du perso
if 420 < events.pos[0] < 470 and 40 < events.pos[1] < 65 and k>1:
k-=1
r=0
if 540 < events.pos[0] < 590 and 40 < events.pos[1] < 65:
k+=1
r=0
if events.pos[0] < 400:
x=events.pos[0]
y=events.pos[1]
p=prediction(x,y,k,s)
r=int(sqrt(t[k-1][0])+1)
text = mafont.render("k="+str(k),True,(0, 255, 0))
screen.blit(text,(485, 40))
draw.rect(screen,(100,100,100),Rect(420,40,50,25))
text2 = mafont.render("-1",True,(128, 0, 0))
screen.blit(text2,(430, 40))
draw.rect(screen,(100,100,100),Rect(540,40,50,25))
text3 = mafont.render("+1",True,(128, 0, 0))
screen.blit(text3,(550, 40))
text4 = mafont.render("prédiction : "+p,True,(255, 255, 255))
screen.blit(text4,(420, 70))
display.flip()Analyser et tester ce code.