# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     name: python3
# ---

# + [markdown] id="rscAyIxioesU"
# # MOML - Clustering
#
# ---

# + [markdown] id="eyDmtuJZxbHu"
# ### Import de tous les modules nécessaires

# + id="cbAlquKoomVW"
# %matplotlib inline
import plotly.graph_objects as go
import plotly.express as px
import matplotlib.pyplot as plt
from scipy.spatial import distance
from scipy.spatial.distance import pdist, squareform 
from sklearn.cluster import KMeans
from scipy.io import arff
import pandas as pd
import networkx as nx
import numpy as np
from numpy import linalg as LA

# + [markdown] id="gbDkSOTUpB80"
# ### Chargement et pré-traitement de la base de donées

# + [markdown] id="f8FliIm6pQMJ"
# Pour pouvoir utiliser la base de données, il nous faut en retirer:
#
#
# *   Les lignes contenant des missing values
# *   Les features inadaptées aux calculs (```"fruit", "daf", "site"```)
#
# On transforme également la colonne cible depuis son format de chaîne de charactères vers un format entier.

# + colab={"base_uri": "https://localhost:8080/", "height": 215} id="N5gO1gko_jgQ" outputId="d7b3a541-60d8-45d1-c100-48a47d845b93"
data, meta = arff.loadarff("Squash.arff") #remplacer Squash.arff par le chemin du fichier qui contient la database sur votre machine

df = pd.DataFrame(data)
# on retire les rows avec des missing values
df.dropna(inplace=True)

# on retire les colonnes non numériques, dont on ne va pas se servir
del df["site"]
del df["daf"]
del df["fruit"]

# excellent : 0, ok : 1, not_acceptable : 2
df["Acceptability"] = df["Acceptability"].replace([b"excellent", b"ok", b"not_acceptable"], [0, 1, 2])

df.head() #premières valeurs pour avoir une idée des données

# + [markdown] id="IsF-qVZRM1E-"
# # Clustering par KMeans
#

# + id="ytdCebzhrK8z"
k = 3 # Nombre de clusters
model = KMeans(n_clusters=k)
model.fit(df)

#On stocke les prédictions dans une nouvelle colonne de la dataframe
df["km_label"] = model.labels_

# + [markdown] id="dvrCSLktr9x0"
# Pour plot les données, on choisit deux features arbitraires : le poids et la saveur.

# + colab={"base_uri": "https://localhost:8080/", "height": 350} id="YycHs8ONbllJ" outputId="832e1dc6-fdfd-44aa-b374-5e2271a448c8"
fig = plt.figure(figsize=(16,5))

# Plot du clustering cible
plt.subplot(121)
plt.scatter(df["weight"], df["flavour"], c=df["Acceptability"])
plt.xlabel("Poids")
plt.ylabel("Saveur")
plt.title("Clustering cible")

# Plot du clustering donné par KMeans
plt.subplot(122)
plt.scatter(df["weight"], df["flavour"], c=df["km_label"])
plt.xlabel("Poids")
plt.ylabel("Saveur")
plt.title("Clustering par KMeans")

plt.show()

# + colab={"base_uri": "https://localhost:8080/"} id="JRtr3tPTvhvI" outputId="4d3290f2-53ac-4f52-f371-5ff4e8bbdb31"
# Calcul du taux de prédictions correctes

n = df.shape[0]
corrects = df.apply(lambda x: (x["Acceptability"] == x["km_label"]), axis=1)
n_correct = len(corrects[corrects == True].index)
print("Précision :", n_correct/n)


# + [markdown] id="GyA8Wc04Nw_-"
# # Matrices d'adjacence et de similarité

# + id="NI6qpb02N-VH"
def dist_sq(x, y):
  """
  fonction qui calcule la distance au carré entre 2 points 
  
  x et y sont 2 vecteurs (1 x n) 
  """
  
  square_root_distance = distance.euclidean(x,y) #calcul la distance euclidienne sans mettre au carré
  resu = square_root_distance**2 # on met au carré
  return resu


# + id="kwDA4uVOrBun"
def weight(x, y):
  """
  fonction qui calcule le poids entre 2 points connectés
  """
  d = dist_sq(x, y) # appel de la fonction qui calcule la distance entre 2 points
  resu = np.exp(-d/2) # calcul du poids avec la distance d'après la formule de similarité du cours (NB : ici on posera sigma = 1)
  return resu


# + id="XpJ550uxOCIo"
def distance_matrix(data):
  """
  fonction qui calcule la matrice de distance entre les différents points, rend une matrice symétrique
  """
  return squareform(pdist(data.iloc[:], lambda x, y : dist_sq(x, y)))


# + id="t8jHG17NRhg8"
def simil_no_epsilon(data):
  """
  fonction qui calcule la matrice de similarité sans critère epsilon,
  pour une utilisation par le spectral clustering

  Cette fonction implémente une normalisation des distances pour éviter 
  que l'exponentielle dans weight(x, y) n'écrase toutes les grandes distances sur 0
  """
  dist = distance_matrix(data)
  max_dist = np.amax(dist)
  dist = np.array([elem/max_dist for elem in dist])
  return squareform(pdist(dist, lambda x, y: weight(x, y)))


# + id="eNHXdhO7OL1X"
def adjacency_and_similarity_matrix(data, epsilon, bypass=False) : 
    """
    fonction qui définit si 2 points sont connectés ou non sur la base de leur distance ou de leur similarité,
    retourne les matrices d'adjacence et de similarité

    epsilon : seuil arbitraire pour savoir si 2 point sont connectés ou non sur la base de leur distance
    bypass = si True, néglige le seuil epsilon (deprecated, utiliser le simil_no_epsilon)
    """
    mat_dist = distance_matrix(data) # appel fonction qui calcule la matrice de distance entre chaque points
    n= mat_dist.shape[0] # nombre de ligne de la data frame , i.e : nombre de points
    adja= np.zeros((n,n)) #défintion de la matrice d'adjacence , qui contiendra des 0 ou des 1 
    simi = np.zeros((n,n))# définition de la matrice de similarité , qui contiendra des poids entre 0 et 1 
    
    for i in range (0,n):
        for j in range (i,n):
          if ( mat_dist[i,j] < epsilon) or bypass:  # critère de connectivité 
            adja[i, j] = 1
            adja[j, i] = 1
            vec_i = data.iloc[[i],:]
            vec_j = data.iloc[[j],:]
            simi[i, j] = weight(vec_i,vec_j)
            simi[j, i] = simi[i, j]
    return adja, simi 


# + colab={"base_uri": "https://localhost:8080/", "height": 335} id="4mZgbqQ1PMPt" outputId="fc19fc43-988d-492a-eb71-de4f44713201"
#Graph
epsilon = 200000
adja,simi = adjacency_and_similarity_matrix(df,epsilon)
n = simi.shape[0]
G = nx.Graph()
for i in range(0,n):
  G.add_nodes_from([i])

for i in range(0,n):
  for j in range(0,n):
    if adja[i,j]==1 :
      G.add_edge(i, j, weight = simi[i,j])

nx.draw(G, with_labels=True, font_weight='bold')
plt.title(f"Graphe de connnectivité pour epsilon = {epsilon}")
plt.show()


# + [markdown] id="GSGlvqwolu8P"
# # Spectral clustering

# + id="SD6T-dFv3KAM"
def Ls(W):
  '''Construction de la matrice de Laplace 
  et de la matrice de Laplace normalisée
  '''
  D = np.sum(W, axis=1)             # degrés
  D_ = np.diag(np.power(D, -1/2))             # D^(-1/2)
  L = np.diag(D) - W                  # Matrice de Laplace
  L_norm = np.dot(D_, np.dot(L, D_))  # L normalisée

  return L_norm


# + id="W5IxhVqQmROP"
def spectral_clustering(W, nbCluster) :
  """
  Fonction de la methode du spectral clustering.
  Entrées : W = matrice de similarité / nbCluster = nombre de clusters souhaité
  Sortie : Renvoie une liste d'array comportant les indices des pts du même cluster.

  """
  #On construit la matrice laplacienne
  L_norm = Ls(W)

  #Trier les vecteurs propres dans l'ordre croissant des val. propres
  eigenValues, eigenVectors = LA.eigh(L_norm)  
  indice = eigenValues.argsort() 
  eigenValues, eigenVectors = eigenValues[indice], eigenVectors[:,indice]
  V = eigenVectors[:,:nbCluster]


  #On applique la méthode kmean sur les lignes de V
  model = KMeans(n_clusters=nbCluster).fit(V)
  return model.labels_ 


# + id="QZQXxxHqKXbp"
df["sc_label"] = spectral_clustering(simil_no_epsilon(df), 3)

# + colab={"base_uri": "https://localhost:8080/", "height": 350} id="TxCaIHHCk7jV" outputId="120fceac-ac52-4987-861c-5610c678602e"
fig = plt.figure(figsize=(16,5))

# Plot du clustering cible
plt.subplot(121)
plt.scatter(df["weight"], df["flavour"], c=df["Acceptability"])
plt.xlabel("Poids")
plt.ylabel("Saveur")
plt.title("Clustering cible")

# Plot du clustering donné par KMeans
plt.subplot(122)
plt.scatter(df["weight"], df["flavour"], c=df["sc_label"])
plt.xlabel("Poids")
plt.ylabel("Saveur")
plt.title("Clustering par Spectral Clustering")

plt.show()

# + colab={"base_uri": "https://localhost:8080/"} id="v--tG6lJl6L7" outputId="92962dba-4918-40d1-f8a7-e6beeec352d1"
# Calcul du taux de prédictions correctes

n = df.shape[0]
corrects = df.apply(lambda x: (x["Acceptability"] == x["sc_label"]), axis=1)
n_correct = len(corrects[corrects == True].index)
print("Précision :", n_correct/n)


# + [markdown] id="vvc9tN5YtYMw"
# # Unsupervised learning: Méthodes pour choisir le nombre de clusters

# + [markdown] id="JDYeMiUbLUor"
# ## Eigengap method

# + id="W0UjcY3FLXeK"
def eigengap(Ls):
  """méthode qui renvoie l'indice du plus grand écart
  entre les valeurs propres de la matrice de laplace
  
  Cet indice est cense etre le meilleur nombre de clusters
    
  Arguments:
      Ls {numpy array} -- [matrice de laplace]
  """
  w, _ = LA.eigh(Ls) # Les valeurs propres de la matrice de laplace
  w = np.sort(w) # triees dans l'ordre croissant

  #calcul des écarts en valeur absolue 
  gaps = np.zeros((len(w))) 
  for i in range(len(w) - 1):
    gaps[i] = abs(w[i]-w[i+1])
  
  n_vals = 20 #nb des premieres valeurs propres à plot
  fig = plt.figure(figsize=(10,5))
  plt.plot(np.arange(n_vals), w[:n_vals], "x")
  plt.xticks(np.arange(n_vals))
  plt.xlabel("Indice de la valeur propre")
  plt.ylabel("Valeur propre")
  plt.title("Eigengaps")
  
  #indice du plus grand écart (+1 pour le nb de clusters)
  return np.argmax(gaps)+1


# + colab={"base_uri": "https://localhost:8080/", "height": 367} id="mQOKVCWKFee_" outputId="7b150cf4-f54e-4ab2-9d17-7573b38cc507"
print("k qui maximise l'eigengap: ",eigengap(Ls(simil_no_epsilon(df))))


# + [markdown] id="XI7BjaYKIi2N"
# ## Méthode Elbow

# + id="KYEByjgiIomD"
def elbow(data):
  """méthode qui plot les variances d'un clustering en Kmeans
    pour des valeurs de k allant de 1 à 10
    
    L'elbow method prescrit de choisir le k qui correspond à un "coude" dans le plot
    
    Arguments:
        data {[DataFrame} -- [les données sur lesquelles effectuer Kmeans]
    """
  vars = []
  for k in range(1, 10):
    model = KMeans(n_clusters=k)
    model.fit(data)
    vars.append(model.inertia_) # variances
  plt.figure(figsize=(8,4))
  plt.plot(np.arange(1, 10), vars)
  plt.xlabel("Nombre de clusters")
  plt.ylabel("Variance")
  plt.title("Méthode Elbow")
  plt.show()


# + colab={"base_uri": "https://localhost:8080/", "height": 295} id="pdrLq1rqPVjo" outputId="e32781d0-0361-42cb-91a1-0f3508d7c577"
elbow(df)


# + [markdown] id="ntscXnx3NF9F"
# ## Silhouette method

# + id="fwDfq9QGXVm2"
def compute_Si(point, cluster, non_neighbors, k):
  """Calcul du score de silhouette d'un point donné
  Note: un point dans cluster de taille 1 a toujours un score de 0
  
  Arguments:
    point {DataFrame} -- [le point dont on calcule le score]
    cluster {DataFrame} -- [le cluster auquel appartient le point]
    non_neighbors {DataFrame} -- [tous les points des autres clusters]
    k {int} -- [nb de clusters]
    
  Returns:
    number -- [le score de silhouette de point]
  """
  if cluster.shape[0] == 1:
    ai = 0
  else:
    dists_inter = squareform(pdist(pd.concat([point, cluster])))
    s_inter = np.sum(dists_inter[0,:]) # somme des distances du point à ses collègues de cluster
    ai = s_inter/(cluster.shape[0] - 1) # moyenne, avec /n-1 puisque le point lui-même ne compte pas
    
  dists_exter = []
  for i in range(k):
    if i == point["km_label"].iat[0]:
      # on passe ce tour de boucle,
      # car other_cluster (cf definition ci-dessous) serait vide
      # pour i le label de point
      # puisque non_neighbors ne contient pas les points du cluster de point
      continue
    other_cluster = non_neighbors[non_neighbors["km_label"] == i] # les points du cluster i
    if other_cluster.shape[0] == 1:
      dists_exter_k = ai # si ai s'avere etre le min des distances, Si sera nul
    else:
      # cf le calcul de ai, similaire
      dists_exter_k = np.sum(squareform(pdist(pd.concat([point, other_cluster])))[0,:])
      dists_exter_k = dists_exter_k/other_cluster.shape[0]

    dists_exter.append(dists_exter_k)

  bi = np.amin(np.array(dists_exter))
  if ai == bi:
    return 0
  elif ai < bi:
    return 1 - ai/bi
  return 1 - bi/ai


# + id="EmNU3glhNLfX"
def silhouette(dataframe):
  """Calcule le meilleur score de silhouette
  de différents clustering Kmeans pour k allant de 2 à 10
  
  Plus le score est proche de 1, meilleur est le clustering
  Note: cette fonction plot aussi les valeurs du score
    
  Arguments:
    dataframe {DataFrame} -- [les données pour le clustering]
    
  Returns:
    [int] -- [le meilleur k pour le clustering]
  """
  data = dataframe.copy() # parce que l'on va rajouter/modifier des colonnes
  Sk = [] # liste qui stockera les scores moyens des k-clusterings
  for k in range(2, 11):
    Si= [] # liste qui stockera les scores des points dans le clustering actuel
    model = KMeans(n_clusters=k)
    model.fit(data)
    data["km_label"] = model.labels_ # labels predits
    for ind in range(data.shape[0]):
      point = data.iloc[[ind]]
      label_pt = point["km_label"].iat[0]
      neighbors = data[data["km_label"] == label_pt] # les points du cluster auquel appartient le point
      non_neighbors = data[data["km_label"] != label_pt] # les autres points
            
      Si.append(compute_Si(point, neighbors, non_neighbors, k))

    Sk.append(np.mean(np.array(Si)))     

  plt.plot(np.arange(2, 11), Sk)
  plt.title("Score de silhouette moyen pour k clusters")
  plt.xlabel("k")
  plt.ylabel("Score")
  plt.show()
  return np.argmax(np.array(Sk)) + 2 # +2 car le range va de 2 à 11, et les indices de listes commencent à 0


# + colab={"base_uri": "https://localhost:8080/", "height": 312} id="9weDuSdURa1c" outputId="5cca6c9c-78c5-4ebc-e7bb-d1649850281c"
print("Nombre recommandé de clusters selon la méthode silhouette :", silhouette(df))

StarcoderdataJupyterScriptsDedupFiltered