# Créé par eclermont, le 21/02/2023 en Python 3.7


#Q1
def dist( x, y ):
    """ dist(x : list, y : list)-> float
        entrees : x, y, 2 listes (vecteurs) de flottants dont on veut calculer la distance euclidienne
        sortie : s, flottant, la distance entre les  vecteur x et y
    """
    s = 0.
    for i in range( len(x) ):
        s+= (x[i] - y[i])**2
    return s**.5
#Q2
def plus_proche( x , lesCentres ):
    """ plus_proche( x : list , lesCentres : list )-> int
        entrees : x, liste, vecteur dont on veut connaitre le centre le plus proche
                : lesCentres, liste des centres
        sortie : imin, entier, indice du centre le plus proche
    """
    imin = 0
    for i in range(len(lesCentres)):
        if dist( x, lesCentres[i] ) < dist( x, lesCentres[imin] ):
            imin = i
    return imin
#Q3
def calculer_classes( X, lesCentres, k ):
    """ calculer_classes( X:list, centres:list , k:int)->list
        entrees : X, liste, liste des entrées
                : lesCentres, liste des centres
                : k, entier, nombre de classes
        sortie : classes, liste de listes des points de chaque classe
    """
    classes = [ [] for i in range(k) ]
    for x in X:
        indPlusProche = plus_proche(x, lesCentres)  # indice du centre le plus proche
        classes[ indPlusProche ].append(x) # ajout de x à la classe possedant cet indice
    return classes

#Q4
def centre( X ):
    """ centre( X )
        determination du barycentre d'un ensemble X de vecteurs
        entree : X, liste, liste des donnees
        sortie : c, liste(vecteur) du barycentre de X
    """
    dim=0
    if len(X) != 0:
        dim = len(X[0])
    c = [0.]*dim
    for x in X:
        for i in range(len(x)): # pour chaque caracteristique
            c[i] = c[i] + x[i]
    if len(X) == 0 :
        return c
    for i in range(len(c)):
        c[i] = round( c[i] /len(X) , 3) #arrondi à 3 decimales
    return c

#Q5
def calculer_centres( classes, k ):
    """ calculer_centres(classes : lst , k : int) -> list
        entrees : classes, liste, représentant les classes
                :  k, entier, nombre de classes  à générer
        sortie : centres, liste (de listes) des centres générés
    """
    centres = []
    for i in range(k):
        centrei = centre( classes[i] )
        centres.append( centrei )
    return centres

#Q6
def kmeans(X, k, lesCentres):
    """ kmeans(X, k, lesCentres)->list
        entrees : X, liste, liste des entrées
                : lesCentres, liste des centres
                : k, entier, nombre de classes
        sortie : classes, liste des points de chaque classe apres traitement du kmeans
    """
    centres2 =  []
    while  ( (sorted(lesCentres)) != (sorted(centres2)) ) : #tri sur les listes pour pouvoir utiliser ==
    # while not (  np.array( sorted(lesCentres)==sorted(centres2) ).all() ):
        centres2 = lesCentres
        classes = calculer_classes( X, centres2, k )
        lesCentres = calculer_centres( classes, k)
    return classes

#Q7
def inertie( classes, centres, k ):
    s = 0.
    for i in range(k):
        for x in classes[i]:
            s += dist(x, centres[i])**2
    return s

#________________ Test _____________________________
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap

from sklearn.datasets import load_iris
import numpy as np
import random
#Chargement du jeu de données
iris = load_iris()

k= 3
X= iris.data
X = X[ : , :2 ] # extraction des 2 1eres colonnes de la matrice des iris => uniquement les 2 1eres caracteristiques

# détermination aléatoire des centres
lesCentres = []
for i in range(k):
  ind = random.randint(0,len(X)-1)
  lesCentres.append(X[ind].tolist())


# affichage
plt.scatter([x[0] for x in X], [x[1] for x in X]) # affichage des points pour les iris
plt.scatter([x[0] for x in lesCentres], [x[1] for x in lesCentres], marker='x', s=100, c='g') #affichage des centres
plt.show()
 #plt.closeAll()


classes = kmeans(X, k, lesCentres) # test de kmeans
cmap = ListedColormap(['g', 'r', 'b', 'purple'])
centres = calculer_centres( classes, k )

plt.scatter([x[0] for x in X], [x[1] for x in X], c=[plus_proche(x, centres) for x in X], cmap=cmap)
plt.scatter([x[0] for x in centres], [x[1] for x in centres], marker='x', s=100, c=range(k), cmap=cmap)
plt.title("Inertie = " + str(inertie( classes, centres,k )))
plt.show()