File: td_note_2010.tex, line 30
def sous_nuage (nb, x, y, v) : # retourne une liste de 2-uples
File: td_note_2010.tex, line 35
def n_sous_nuages (n, nb) : # retourne une liste de 2-uples
File: td_note_2010.tex, line 41
import matplotlib.pyplot as plt
x = [ ... ]
y = [ ... ]
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot (x,y, 'o')
plt.savefig ("im1.png") # ou plt.show () pour afficher le graphe
File: td_note_2010.tex, line 52
def random_class (points, n) : # retourne une liste d'entiers
File: td_note_2010.tex, line 67
def proche_barycentre (point, barycentres) : # retourne un entier
File: td_note_2010.tex, line 72
def association_barycentre (points, barycentres) : # retourne une liste d'entiers
File: td_note_2010.tex, line 82
def barycentre_classe (points, classes, numero_class) : # retourne un 2-uple def tous_barycentres (points, classes) : # retourne une liste de 2-uples
File: td_note_2010.tex, line 88
def nuees_dynamiques (points, nombre_classes) : # retourne une liste d'entiers
File: td_note_2010.tex, line 98
import matplotlib.pyplot as plt
x1 = [ ... ]
y1 = [ ... ]
x2 = [ ... ]
y2 = [ ... ]
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot (x1,y1, 'o')
ax.plot (x2,y2, 'x') # ligne ajoutée, 'x', 'bo', ...
plt.savefig ("im2.png") # 'rx', 'go', 'gs', 'bs', ...
File: td_note_2010.tex, line 133
def n_sous_nuages (n, nb):
m = []
for i in range (0,n):
x = 5*random.random()
y = 5*random.random()
d = sous_nuage(nb,x,y,1)
m += d
return m
File: td_note_2010.tex, line 146
def n_sous_nuages (n, nb):
m = []
for i in range (0,n):
x = random.randint(0,20)
y = random.randint(0,20)
d = sous_nuage(nb,x,y,1)
m += d
return m
File: td_note_2010.tex, line 168
def n_sous_nuages (n, nb):
m = []
for i in range (0,n):
x = random.gauss(0,1)
y = random.gauss(0,1)
d = sous_nuage(nb,x,y,1)
m += d
return m
File: td_note_2010.tex, line 191
def n_sous_nuages (n, nb):
m = []
for i in range (0,n):
x = random.gauss(0,1)
y = random.gauss(0,1)
d = sous_nuage(nb,x,y,1)
m += [ d ]
# le résultat n'est
# plus une liste
return m
File: td_note_2010.tex, line 209
import matplotlib.pyplot as plt
x = [ p [0] for p in n_sous_nuages (3,50) ]
y = [ p [1] for p in n_sous_nuages (3,50) ]
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot (x,y, 'o' )
plt.savefig ("im1.png")
File: td_note_2010.tex, line 223
def random_class(l,n):
l = []
for i in range(0,len(l)):
l += [ random.randint (1,n) ]
return l
File: td_note_2010.tex, line 234
def random_class(l,n):
l = []
for i in range(0,len(l)):
l += [ random.randint (0,n) ]
return l
File: td_note_2010.tex, line 245
d= ( (p[0]-f[0])**2+(p[1]-f[1])**2 ) ** (1/2)
File: td_note_2010.tex, line 251
def proche_barycentre (point,barycentres):
d=distance_euclidienne(point,barycentres[0])
for i in range (0,len(barycentres)):
if distance_euclidienne(point,barycentres[i])<=d:
d=distance_euclidienne(point,barycentres[i])
return d
File: td_note_2010.tex, line 265
def barycentre_classe (points, classes, numero_class):
x=0
y=0
for i in range (0,len(classes)):
if classes[i]==numero_class: # ligne importante
l=point[i]
x=x+l[0]
y=y+l[1]
c=[x/n,y/n] # ligne importante
return c
File: td_note_2010.tex, line 284
def tous_barycentres (points,classes):
c=[]
for i in classes : # or on a len(classes) == len(points)
c+=[barycentre_classe (points,classes,i)]
return c
File: td_note_2010.tex, line 294
def tous_barycentres (points,classes):
c=[]
mx=max(classes) # il faut ajouter +1
for i in range(0,mx) :
c+=[barycentre_classe (points,classes,i)]
return c
File: td_note_2010.tex, line 309
def nuees_dynamiques (points,nombre_classes):
l = random_class (points,nombre_classes)
for j in range (0,10):
c = tous_barycentres (points, l)
a = association_barycentre (points,c)
# il faut ajouter ici l = a pour corriger la fonction
return a
File: td_note_2010.tex, line 321
def nuees_dynamiques (points,nombre_classes):
for j in range (0,10):
l = random_class (points,nombre_classes)
c = tous_barycentres (points, l)
a = association_barycentre (points,c)
l = a
return a
File: td_note_2010.tex, line 333
def nuees_dynamiques (n,nb):
for j in range (0,10):
points = n_sous_nuage (n,nb)
l = random_class (points,nombre_classes)
c = tous_barycentres (points, l)
a = association_barycentre (points,c)
l = a
return a
, correction 2010
# coding: latin-1
import random
import numpy
def dessin (nuage, image = None) :
"""dessine un nuage de points
@param nuage le nuage de points
@param image si None, on affiche le nuage au travers d'une fenêtre,
sinon, image correspond à un nom d'image
sur disque dur qui contiendra le graphique final"""
import matplotlib.pyplot as plt
x = [ p[0] for p in nuage ]
y = [ p[1] for p in nuage ]
plt.clf ()
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot (x,y, 'o')
if image == None : plt.show ()
else : plt.savefig (image)
def dessin_classes (nuage, classes, image = None) :
"""dessine un nuage, donne des couleurs différentes
selon que le point appartient à telle ou telle classes
@param nuage nuage[i], c'est le point i
@param classes classes [i] est la classe associée au point i
@param image voir la fonction précédente
"""
import matplotlib.pyplot as plt
x = {}
y = {}
for i in range (0, len (nuage)) :
cl = classes [i]
if cl not in x :
x [cl] = []
y [cl] = []
x [cl].append ( nuage [i][0] )
y [cl].append ( nuage [i][1] )
plt.clf ()
fig = plt.figure()
ax = fig.add_subplot(111)
for cl in x :
ax.plot (x [cl], y [cl], "+")
if image == None : plt.show ()
else : plt.savefig (image)
def sous_nuage (nb, x, y) :
"""retourne un ensemble de points tirés aléatoirement selon
une loi normale centrée autour du point x,y
@param nb nombre de points
@param x abscisse du centre
@param y ordonnée du centre
@return une liste de points ou matrice de deux colonnes
- la première correspond aux abscisses,
- la seconde aux ordonnées
"""
res = []
for i in xrange (0, nb) :
xx = random.gauss (0,1)
yy = random.gauss (0,1)
res.append ( [x+xx, y+yy] )
return res
def n_sous_nuages (nb_class, nb_point) :
"""crée un nuage de points aléatoires
@param nb_class nombre de sous nuages
@param nb_point nombre de points dans chaque sous nuage
@return une liste de points ou matrice de deux colonnes
- la première correspond aux abscisses,
- la seconde aux ordonnées"""
res = []
for c in xrange (0, nb_class) :
x = random.gauss (0,1) * 5
y = random.gauss (0,1) * 5
res += sous_nuage (nb_point, x,y)
return res
def random_class ( nuage, n) :
"""choisis aléatoirement un entier pour chaque point du nuage
@param nuage un nuage de points (matrice de deux colonnes)
@param n nombre de classes
@return une liste d'entiers
"""
res = [ ]
for p in nuage :
c = random.randint (0, n-1)
res.append (c)
return res
def proche_barycentre (point, barycentres) :
"""détermine le barycentre le plus d'un point
@param point liste de 2 réels : [x,y]
@param barycentres liste de n points = matrice de deux colonnes,
chaque ligne correspond à un barycentre
@return un entier qui correspond à l'index
du barycentre le plus proche"""
dmax = 1e6
for i in range (0, len (barycentres)) :
b = barycentres [i]
dx = point [0] - b [0]
dy = point [1] - b [1]
d = (dx**2 + dy**2) ** 0.5
if d < dmax :
dmax = d
m = i
return m
def association_barycentre (points, barycentres) :
"""détermine pour chaque point le barycentre le plus proche
@param points nuage (matrice de deux colonnes)
@param barycentres c'est aussi une matrice de deux colonnes mais
avec moins de lignes
@return liste d'entiers, chaque entier
correspond à la classe du point points[i],
c'est-à-dire l'index du barycentre le plus proche
ici:
point: points [i]
classe: res[i]
barycentre: barycentres[ res[i] ]
"""
res = []
for p in nuage :
m = proche_barycentre (p, barycentres)
res.append (m)
return res
def barycentre_classe (points, classes, numero_class) :
"""calcule le barycentre d'une classe
@param points ensemble de points (matrice de deux colonnes)
@param classes liste d'entiers de même longueur,
chaque élément classes[i] est la classe de point[i]
@param numero_class classe pour laquelle on doit calculer le barycentre
@return résultat barycentre x,y
dans cette fonction, on doit calculer le barycentre d'une classe
c'est-à-dire le barycentre des points points[i]
pour lesquelles classes[i] == numero_class
"""
mx,my = 0.0,0.0
nb = 0
for i in range (0, len (points)) :
p = points [i]
c = classes [i]
if c != numero_class : continue
nb += 1
mx += p [0]
my += p [1]
return mx/nb, my/nb
def tous_barycentres (points, classes) :
"""calcule les barycentres pour toutes les classes
@param points points, nuage, matrice de deux colonnes
@param classes liste d'entiers
@return liste de barycentre = matrice de deux colonnes
"""
mx = max (classes)+1
barycentre = []
for m in range (0,mx) :
b = barycentre_classe (points, classes, m)
barycentre.append (b)
return barycentre
def numpy_tous_barycentres (points, classes) :
"""écriture de barycentre_classe et tous_barycentres
en une seule fonction avec numpy
"""
nbcl = max (classes)+1
mat = numpy.matrix (points)
vec = numpy.array ( classes )
clas = numpy.zeros ( (len (points), nbcl) )
for i in range (0, nbcl) :
clas [ vec == i, i ] = 1.0
nb = clas.sum (axis = 0)
for i in range (0, nbcl) :
clas [ vec == i, i ] = 1.0 / nb [i]
ba = mat.transpose () * clas
ba = ba.transpose ()
ba = ba.tolist ()
barycentre = [ b for b in ba ]
return barycentre
def numpy_tous_barycentres2 (points, classes) :
"""écriture de barycentre_classe et tous_barycentres
en une seule fonction avec numpy
"""
nbcl = max (classes)+1
mat = numpy.matrix (points)
matt = mat.transpose ()
matcl = numpy.matrix (classes).transpose ()
barycentre = []
for c in xrange (0, nbcl) :
w = numpy.matrix (matcl)
w [matcl==c] = 1
w [matcl!=c] = 0
wt = w.transpose ()
r = matt * w
n = wt * w
r /= n [0,0]
barycentre += [ [ r [0,0], r [1,0] ] ]
return barycentre
def nuees_dynamiques (points, nbcl) :
"""algorithme des nuées dynamiques
@param points ensemble points = matrice de deux colonnes
@param nbcl nombre de classes demandées
@return un tableau incluant la liste d'entiers
"""
classes = random_class (points, nbcl)
# on a le choix entre la version sans numpy
for i in range (0,10) :
print "iteration",i, max (classes)+1
barycentres = tous_barycentres (points, classes) # ou l'un
classes = association_barycentre (points, barycentres)
cl1 = classes
# ou la première version avec numpy
for i in range (0,10) :
print "iteration",i, max (classes)+1
barycentres = numpy_tous_barycentres (points, classes) # ou l'autre
classes = association_barycentre (points, barycentres)
cl2 = classes
# ou la seconde version avec numpy
for i in range (0,10) :
print "iteration",i, max (classes)+1
barycentres = numpy_tous_barycentres2 (points, classes) # ou l'autre
classes = association_barycentre (points, barycentres)
cl3 = classes
# on doit trouver cl1 == cl2 == cl3
if cl1 != cl2 or cl1 != cl3 :
print "erreur de calculs dans l'une des trois fonctions"
return classes
# début du programme : on construit un nuage de points
nuage = n_sous_nuages (3, 50)
# on appelle l'algorithme
classes = nuees_dynamiques (nuage, 3)
# on dessine le résultat
dessin_classes (nuage, classes)