1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
| import matplotlib.pyplot as plt
import numpy as np #Import numpy locally in variable np
import sys
import math as m
import seaborn as sns; sns.set()
import matplotlib.cm as cmx
import matplotlib.colors as colors
from numpy import linalg as LA
#Fonction read_data permet de lire les données d'un fichier formaté et de resortir un array des éléments du fichier
def read_data(file_name):
data_file = open(file_name, 'r')
dat = (data_file.read()).split("\n")
data_file.close()
dat.pop()
dataread =[]
for d in dat:
esp = d.find(' ')
x = d[:esp]
y = d[esp+1:]
dataread.append((int(x), int(y)))
del dat
return np.asarray(dataread)
#Fonction init_centroids ressort k centroids aléatoire
def init_centroids (datas, k):
centroids_create = datas.copy()
np.random.shuffle(centroids_create)
return np.asarray9centroids_create[:k])
'''Fonction close_centroid nous permet de calculer pour chaque élément le centroides qui lui est le plus proche et le ressort sous forme
de array'''
def close_centroid(datas, centds):
pproche = []
for ind in datas:
normes = []
for cen in centds:
normes.append(m.sqrt((cen[0]-ind[0])**2 + (cen[1]-ind[1])**2))
pproche.append(normes.index(min(normes)))
return np.asarray(pproche)
'''Fonction movmnt_centroids calcul la moyenne des vecteurs de chaque points par rapport à son centroide le plus proche
qui le déplace ensuite par rapport à ce vecteur moyen'''
def movmnt_centroids(dat, pclose, cent):
for i in range(len(cent)):
indices = np.where(pclose == i)
sumx = 0
sumy = 0
for j in indices:
sumx += dat[j][0]
sumy += dat[j][1]
card = len(indices)
cent[i][0] = sumx//card
cent[i][1] = sumy//card
return cent
#Fonction qui affecte les nouvelles positions des centroids
def ite_movmt_centro(data,centr):
done = False
epsi = 0.000000000000001
def ecart (copie,origin,index):
ex = abs(ccentre[index][0] - centr[index][0])
ey = abs(ccentre[index][1] - centr[index][1])
return True if (ex <= epsi and ey <= epsi) else False
while (not done):
ccentre = centr.copy
pp = close_centroid(data,centr)
centr = movmnt_centroids(data, pp, centr)
for i in range(len(ccentre)):
if ecart(ccentre,centr,i):
if (i == (len(ccentre)-1)):
done = False
else:
pass
else:
break
return centr
#get_cmap permet de créer un array avec N couleurs différente
def get_cmap(N):
color_norm = colors.Normalize(vmin=0, vmax=N-1)
scalar_map = cmx.ScalarMappable(norm=color_norm,cmap='hsv')
def map_index_to_rgb_color(index):
return scalar_map.to_rgba(index)
return map_index_to_rgb_color
'''Fonction kmeans, est la fonction principale qui appelle toute les fonctions ci-dessus. Elle sort un array avec les
coordonnées de chaque centroide après que les centroides convergent et affiche dans une figure le grpahique de chaque
chaque points avant et après application de kmeans'''
def kmeans(data, k):
plt.subplot(121)
centroids = init_centroids(data, k)
cmap = get_cmap(k+1)
ccentroids = close_centroid(data, centroids)
for i in range(len(ccentroids)):
plt.scatter(data[i, 0], data[i, 1], c=cmap(ccentroids[i]))
plt.scatter(centroids[:, 0], centroids[:, 1], s=20, c='black')
plt.title('Avant mouvement des centroïdes')
plt.grid(False)
plt.axis('off')
plt.subplot(122)
centroids = ite_movmt_centro(data,centroids)
ccentroids = close_centroid(data, centroids)
for i in range(len(ccentroids) - 1):
plt.scatter(data[i, 0], data[i, 1], c=cmap(ccentroids[i]))
plt.scatter(centroids[:, 0], centroids[:, 1], s=20, c='black')
plt.title('Après mouvement des centroïdes')
plt.grid(False)
plt.axis('off')
fig = plt.gcf()
fig.canvas.set_window_title('Algorirthme K-Means')
print("Coordonnée des centroides :")
plt.show()
return centroids
#Fonction kmeans_rand appelle kmean avec des données aléatoire
def kmeans_rand(min,max,n,k):
return kmeans(np.random.randint(min, max, size=(n, 2)), k)
#Fonction kmeans_file appelle kmean avec des données pris d'un fichier
def kmeans_file(file_n,k):
return kmeans(np.array(read_data(file_n)), k) |
Partager