#Le programme présenté ici est en dimension n.
#Si on prend n=2, on se retrouve dans R^2, comme l illustration du cours


import numpy as np
import matplotlib.pyplot as plt
import random as rd
import time #pour faire des pauses dans l'affichage

###############################################################################
###############################################################################
# Première partie "facile": affichage dun nuage de points et de centres choisis au hasard


#génération d'un nuage de points
def points_random(n,p):
    '''retourne une liste de p points de R^n, de coordnonnées aléatoires entre 0 et 100'''
    liste=[] 
    for i in range(p):
        point=[rd.randint(0,100) for j in range(n)] #génère n coordonnées du point
        liste.append(point)
    return liste

#tracé de ce nuage
n=2   #on se place en dimension 2
p=300  #on va prendre 300 points
liste_points=points_random(n,p)  
listeX=[liste_points[i][0] for i in range(p)]  #on récupère les abscisses
listeY=[liste_points[i][1] for i in range(p)]  #on récupère les ordonnées
plt.plot(listeX,listeY,'ob')
plt.show()

#choix de k centres au hasard
def debut(liste,k):
    '''choisit au hasard k points distincts parmi la liste'''
    #attention rd.choices(liste,k=k) ne fonctionne pas car il peut y avoir des répétions
    choix=[]
    while len(choix)<k:
        x=rd.choice(liste)
        if x not in choix:
            choix.append(x)
    return choix

#tracé des centres en plus du nuage
n=2   #on se place en dimension 2
p=300  #on va prendre 300 points
liste_points=points_random(n,p)  
listeX=[liste_points[i][0] for i in range(p)]  #on récupère les abscisses
listeY=[liste_points[i][1] for i in range(p)]  #on récupère les ordonnées
plt.plot(listeX,listeY,'ob')

liste_centres=debut(liste_points,3) #on va faire 3 classes
listecX=[liste_centres[i][0] for i in range(3)]  #on récupère les abscisses
listecY=[liste_centres[i][1] for i in range(3)]  #on récupère les ordonnées
plt.plot(listecX,listecY,'*r')
plt.show()

###############################################################################
###############################################################################
# Programmation de l algorithme des k moyennes

def distance(A,B):
    '''distance euclidienne entre deux points
    A et B sont deux couples si on est dans R^2(les coordonnées des deux points)'''
    d=0
    for i in range(len(A)):
        d+=(A[i]-B[i])**2
    return np.sqrt(d)
        
def centre(liste):
    '''calcule l'isobarycentre d'une liste de points'''
    p=len(liste) #le nombre de points
    #p ne pourra pas être nul car il y aura toujours au moins le centre
    n=len(liste[0]) #la dimension de nos points
    
    c=[] #pour stocker les coordonnées du centre
    for i in range(n):#calcul de la ième coordonnée du centre
        s=0
        for point in liste:
            s+=point[i]
        c.append(s/p)
    return c



def clusters(Lc,Lp):
    '''Lc est la liste des centres, Lp la liste des points,retourne la liste des clusters'''
    k=len(Lc) #le nombre de clusters
    liste_clusters=[[] for i in range(k)] #toutes les listes sont vides au début
    for point in Lp: #on va affecter chaque point à un cluster
        i_min=0
        d_min=+np.inf
        for i in range(k):
            d=distance(point,Lc[i])
            if d<d_min:
                i_min=i
                d_min=d
        liste_clusters[i_min].append(point)
    return liste_clusters

def arret(Lc_old,Lc_new,epsilon):
    '''retourne False si certains centres de classe ont bougé de plus de epsilon
    retourne True sinon, dans ce cas on arretera le programme'''
    k=len(Lc_old)
    test=True
    for i in range(k):
        if distance(Lc_old[i],Lc_new[i])>epsilon:
            test=False
    #le test sera encore True si toutes les distances ont été plus petites que epsilon
    return test
    
  

def kmeans(Lp,k,epsilon):
    '''à partir d'une liste de points Lp, va retourner une liste de k centres
    une liste de k clusters, et un compteur indiquant le nombre d'iterations'''
    Lc=debut(Lp,k) #on initialise aléatoirement les centres
    test=False
    compteur=0 #pour savoir combien d'itérations seront nécessaires
    while test==False: 
        compteur+=1
        liste_clusters=clusters(Lc,Lp) #la liste des clusters
        
        #on va recalculer tous les centres
        Lc_new=[]
        for liste in liste_clusters:
            Lc_new.append(centre(liste))
        
        test=arret(Lc,Lc_new,epsilon)
        
        Lc=Lc_new #on actualise les centres
        
    return Lc,liste_clusters,compteur
   

def kmeans_tracé(Lp,k,epsilon):
    numéro=0 #pour numéroter les figures sauvegardées
    
    #un choix de k couleurs au hasard
    liste_couleurs = [[rd.random(),rd.random(),rd.random()] for i in range(k)]
    
    Lc=debut(Lp,k) #on initialise aléatoirement les centres
    
    #tracé de tous les individus et des premiers centres
    liste_x=[coord[0] for coord in Lp]
    liste_y=[coord[1] for coord in Lp]
    plt.plot(liste_x,liste_y,'ob')
    listec_x=[coord[0] for coord in Lc]
    listec_y=[coord[1] for coord in Lc]
    plt.scatter(listec_x,listec_y,s=300,marker='*',color='red')
    plt.savefig('étape'+str(numéro)+'.png')
    plt.show()
    time.sleep(3) #pause de 2 secondes
    numéro+=1
    
    test=False
    compteur=0 #pour savoir combien d'itérations seront nécessaires
    while test==False and compteur<3: 
       
        compteur+=1
        liste_clusters=clusters(Lc,Lp) #la liste des clusters
        
        #le tracé
        i=0
        for liste in liste_clusters:
            couleur=liste_couleurs[i]
            liste_x=[coord[0] for coord in liste]
            liste_y=[coord[1] for coord in liste]
            plt.plot(liste_x,liste_y,'o',color=couleur)
            i+=1
        listec_x=[coord[0] for coord in Lc]
        listec_y=[coord[1] for coord in Lc]
        plt.scatter(listec_x,listec_y,s=300,marker='*',color='red')
        plt.savefig('étape'+str(numéro)+'.png')
        plt.show()
        time.sleep(2) #pause de 2 secondes
        numéro+=1
        
        #on va recalculer tous les centres
        Lc_new=[]
        for liste in liste_clusters:
            Lc_new.append(centre(liste))
            
               
        test=arret(Lc,Lc_new,epsilon)
        
        Lc=Lc_new #on actualise les centres
        
        #le tracé
        i=0
        for liste in liste_clusters:
            couleur=liste_couleurs[i]
            liste_x=[coord[0] for coord in liste]
            liste_y=[coord[1] for coord in liste]
            plt.plot(liste_x,liste_y,'o',color=couleur)
            i+=1
        listec_x=[coord[0] for coord in Lc]
        listec_y=[coord[1] for coord in Lc]
        plt.scatter(listec_x,listec_y,s=300,marker='*',color='red')
        plt.savefig('étape'+str(numéro)+'.png')
        plt.show()
        time.sleep(2) #pause de 2 secondes
        numéro+=1
        
    print(compteur)
    
#éxécution de notre programme
n=2   #on se place en dimension 2
p=300  #on va prendre 300 points
liste_points=points_random(n,p) 

kmeans_tracé(liste_points,3,0.0001)