{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"K-means.ipynb","version":"0.3.2","provenance":[],"collapsed_sections":[]},"kernelspec":{"name":"python3","display_name":"Python 3"}},"cells":[{"cell_type":"markdown","metadata":{"id":"7wkECHCemnoB","colab_type":"text"},"source":["# Clustering - K-means \n","\n","**Sommaire**\n","1. Introduction\n","2. Programmation de l'algorithme\n","3. Création des données\n","4. Graphiques et fonctionnement\n","\n","# Introduction\n","L'algorithme K-means est un algorithme de clustering **non-supervisé**.</br>\n","On choisit K points aléatoirement et on les choisit comme barycentres. Puis pour chaque point, on l'assigne au cluster du barycentre le plus proche. Puis on recalcule les barycentres de temps en temps jusqu'à convergence.\n"]},{"cell_type":"code","metadata":{"id":"7ymGTI5dawE5","colab_type":"code","colab":{}},"source":["# Importation des librairies\n","import numpy as np\n","import matplotlib.pyplot as plt\n","from random import randint,shuffle"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"duPFDeAVBlx2","colab_type":"text"},"source":["Avant de nous lancer dans l'écriture de l'algorithme, il faut prendre en compte un autre paramètre de K-Means : **La distance choisie**.</br>\n","Le choix de la distance aura des conséquences sur les résultats. Dans un premier temps nous utiliserons la distance euclidienne, mais il sera intéressant par la suite de comparer les résultats pour différentes distances.</br>\n","**Distance euclidienne**\n","C'est celle qu'on utilise de manière usuelle, et que nous utilisions précédement, je remet donc le résultat:</br>\n","d(a,b) = √((xa-xb)²+(ya-yb))\n","\n","**Distance de Manhattan**\n","Elle découle de la valeur absolue: </br>\n","d(a, b) = |xb – xa| + |yb – ya|</br>\n","\n","**Distance aux échecs**\n","Elle découle elle aussi de la valeur absolue, mais prend en compte le maximum.</br>\n","d(a, b) = max(|xb – xa|, |yb – ya|)</br>\n","\n"]},{"cell_type":"code","metadata":{"id":"e9Wm2rY7BmNF","colab_type":"code","colab":{}},"source":["# Les distances\n","\n","def distance_quadratique(pt1,pt2): # Distance quadratique/euclidienne\n","  return sum((pt1-pt2)**2)**(1/2)\n","\n","def distance_manhattan(pt1,pt2):   # Distance de Manhattan (utilisant la valeur absolue)\n","  return sum(abs(pt1-pt2))\n","\n","def distance_echecs(pt1,pt2):      # Distance des échecs (le maximum, c'est la norme infinie)\n","  return max(abs(pt1-pt2))\n"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"4n7W2yLOmX_B","colab_type":"text"},"source":["# Programmation de l'algorithme\n","Nous allons pouvoir programmer l'algorithme.</br>\n","Nous allons stocker les clusters comme une liste de K listes, correspondant aux K clusters.</br>\n","Chaque liste (de cluster) contiendra les indices des points (plutôt que le point en lui même)."]},{"cell_type":"code","metadata":{"colab_type":"code","cellView":"code","id":"ZPEllpF9R3C3","colab":{}},"source":["def kMeans(K,points,N=5,distance=distance_quadratique):\n","  \n","  clusters = [[] for i in range(K)]\n","  barycentres = [0 for i in range(K)]\n","  visites = []\n","  \n","  for i in range(K):\n","    indice = randint(0,len(points)-1)\n","    if indice not in visites:\n","      clusters[i].append(indice)\n","      visites.append(indice)\n","  \n","  N=0\n","  while N<13:\n","    for j in range(K):\n","          bary = sum([points[indice] for indice in clusters[j]])/len(clusters[j])\n","          barycentres[j] = bary\n","\n","    for i_point in range(len(points)):\n","\n","      dmin = distance(points[i_point],barycentres[0])\n","      imin = 0\n","      for i_cluster in range(1,K):\n","        d = distance(points[i_point],barycentres[i_cluster])\n","        if d<dmin:\n","          dmin = d\n","          imin = i_cluster\n","      clusters[imin].append(i_point)\n","    N+=1\n","    \n","  return clusters,barycentres\n","        \n","    \n","  "],"execution_count":0,"outputs":[]},{"cell_type":"code","metadata":{"id":"70Vs6TIbSPpb","colab_type":"code","colab":{}},"source":["# Pour tester s'il n'y a pas d'erreur dans l'algorithme, nous vérifierons par la suite si cela semble fonctionner\n","a,b = kMeans(2,[np.array([2,1]),np.array([0,0]),np.array([5,5])])"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"IJenYjy-fwIN","colab_type":"text"},"source":["Maintenant que l'algorithme a été écrit, il va falloir le tester. Et pour le tester, il va nous falloir des données."]},{"cell_type":"markdown","metadata":{"id":"zXy9iecjDFgt","colab_type":"text"},"source":["# Création des données\n","Maintenant que nous avons codé l'algorithme, il nous faut un moyen de le tester. Pour cela nous utiliserons une base de données assez simple que nous allons créer. Cette base de données sera utilisée dans d'autres fichier Jupyters.</br>\n","Les données d'origine peuvent être de tout type (Des tailles, des couleurs, des dates, ...), et il est généralement nécessaire d'effectuer des transformations pour les mettre sous la meilleure forme pour utiliser un algorithme de classification.</br>\n","Cette partie ne sera pas traitée, on supposera donc que nos données ont été traitées et qu'elles sont sous forme de vecteur dans un espace de dimension variable (ici pour simplifier on se placera en dimension 2, facilement visualisable).</br></br>\n","\n","Dans notre cas, nous allons générer des données avec une répartition normale autour de certaines zones."]},{"cell_type":"code","metadata":{"id":"z9jLmwaKnf7C","colab_type":"code","cellView":"both","colab":{}},"source":["\n","# Les paramètres importants\n","nbr_clusters=4\n","nbr_initialisation=100\n","nbr_evalutation=200\n","\n","# Les listes\n","init_points=[]\n","init_labels=[]\n","eval_points=[]\n","eval_labels=[]\n","\n","\n","donnees_initialisation=[[] for i in range(nbr_clusters)]  #Tableau avec les données que l'on donnera pour l'initialisation de l'algorithme\n","\n","centres_generation=[np.array([0.8,0.8]),np.array([0.8,-0.8]),np.array([-0.8,-0.8]),np.array([-0.8,0.8])] \n","\n","# Création des données d'initialisation\n","for i in range(nbr_initialisation):\n","  indice=np.random.randint(0,nbr_clusters)\n","  point=centres_generation[indice]+np.random.normal(scale=0.2,size=2) # Répartition normale autour d'un barycentre\n","  init_points.append(point)\n","  init_labels.append(indice)\n","  donnees_initialisation[indice].append(point)\n","\n","# Création des données de test\n","for i in range(nbr_evalutation):\n","  indice=np.random.randint(0,nbr_clusters)\n","  point=centres_generation[indice]+np.random.normal(scale=0.2,size=2) # Répartition normale autour d'un barycentre\n","  eval_points.append(point)\n","  eval_labels.append(indice)\n","  \n","print('Les données ont été générées !')\n","print('Nombre de clusters: {}'.format(nbr_clusters))\n","print('Nombre de points pour l\\'initialisation: {}'.format(nbr_initialisation))\n","print('Nombre de points pour l\\'évaluation: {}'.format(nbr_evalutation))"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"94af0pGB-hCB","colab_type":"text"},"source":["Maintenant que nous avons créé les données, je vous propose de les visualiser pour mieux comprendre ce que nous avons généré."]},{"cell_type":"code","metadata":{"id":"lCqbHokl-8hE","colab_type":"code","colab":{}},"source":["# On définit les limites du graphique\n","lim=1.5\n","plt.xlim([-lim,lim])\n","plt.ylim([-lim,lim])\n","\n","for i in range(nbr_initialisation):\n","  point=init_points[i]\n","  label=init_labels[i]\n","  plt.plot(point[0],point[1],color=\"b\",marker=\"+\") # On affiche chaque point avec la couleur de son cluster\n","  \n","plt.show()"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"XccD4ZIxjoWz","colab_type":"text"},"source":["# Efficacité de l'algorithme\n","Maintenant que nous avons créé notre algorithme, nous allons pouvoir le tester sur un plus grand nombre d'échantillons, pour vérifier si l'algorithme fonctionne correctement (ie que les résultats semblent corrects)</br>\n","Le raisonnement statistique (sur un grand nombre d'éléments) nous permet de voir si de manière générale, l'algorithme sort des résultats cohérents."]},{"cell_type":"code","metadata":{"id":"s3bJvXt9jx5J","colab_type":"code","colab":{}},"source":["K = 4\n","\n","clusters,barycentres = kMeans(K,init_points,distance=distance_quadratique)\n","\n","\n","plt.figure()\n","couleurs=['r','g','b','y']\n","for n,cluster in enumerate(clusters):\n","  for pt in cluster:\n","    plt.plot(init_points[pt][0],init_points[pt][1],color=couleurs[n],marker=\"o\")\n","plt.show()\n"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"lnmQb7NLmNbJ","colab_type":"text"},"source":["# Pour aller plus loin\n","\n","Nous avons donc vu l'algorithme K-Means dans sa forme la plus simple, mais il est tout à fait possible d'aller plus loin dans son élaboration.\n","\n","\n"]},{"cell_type":"markdown","metadata":{"id":"43ZAR2ZHDjGQ","colab_type":"text"},"source":["## Test des distances\n","\n","Cherchons à savoir exactement ce que nous donne notre algorithme. Je vous propose donc d'afficher les sorties de l'algorithme.\n","Les entrées sont les coordonnées d'un point, ici donc les coordonnées sont liées aux pixels.</br>\n","La sortie est le cluster choisi, que l'on représente par la couleur du pixel (en fonction du cluster).</br>\n","Voici ce que cela donne dans ce cas ici présent.</br></br>\n","Note: Ce type de représentation est très pratique pour identifier l'efficacité d'un algorithme 'au nez'.\n"]},{"cell_type":"code","metadata":{"id":"mAYmG1PhpQhd","colab_type":"code","colab":{}},"source":["# Un affichage plus recherché\n","plt.figure(figsize=(20,10))\n","lim=1.5\n","plt.xlim([-lim,lim])\n","plt.ylim([-lim,lim])\n","\n","#Couleurs\n","couleurs=['r','g','b','y']\n","couleurs_graph=[[1,0,0],[0,1,0],[0,0,1],[0,1,1]]\n","\n","K = 4\n","\n","clusters,barycentres = kMeans(K,init_points,distance=distance_quadratique)\n","\n","plt.title(\"Affichage des données d'initialisation\")\n","plt.subplot(221)\n","plt.axis('equal')\n","for n,cluster in enumerate(clusters):\n","  for pt in cluster:\n","    plt.plot(init_points[pt][0],init_points[pt][1],color=couleurs[n],marker=\"o\")\n","\n","\n","# On affiche les représentations des sorties de ces algos selon les distances utilisées\n","\n","\n","types_distances=[distance_quadratique,distance_manhattan,distance_echecs]\n","nom_distances=['distance Quadratique/Euclidienne','distance de Manhattan','distance des échecs']\n","for k in range(len(types_distances)):\n","  if k==0: plt.subplot(222)\n","  if k==1: plt.subplot(223)\n","  if k==2: plt.subplot(224)\n","    \n","  dist=types_distances[k]\n","\n","  width=50\n"," \n","  image=np.zeros((width,width,3))\n","  points = []\n","  for i in range(width):\n","    for j in range(width):\n","      x=(i/width-0.5)*2*lim\n","      y=(j/width-0.5)*2*lim\n","      point=np.array([x,y])\n","      \n","      dmin = dist(point,barycentres[0])\n","      imin = 0\n","      for i_cluster in range(1,K):\n","        d = dist(point,barycentres[i_cluster])\n","        if d<dmin:\n","          dmin = d\n","          imin = i_cluster\n","      \n","      image[width-1-j,i]=couleurs_graph[imin]\n","  plt.title('Avec la '+nom_distances[k])\n","  plt.imshow(image) \n"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"684_vpzMXhXC","colab_type":"text"},"source":["On peut remarquer que les résultats sont différents en fonction de la distance employée.</br>\n","Néanmoins, les données qui sont en entrée sont suffisament claires pour que pour ces distances, le résultat reste globalement le même.</br>\n"]},{"cell_type":"markdown","metadata":{"id":"erM0aLWfYYEn","colab_type":"text"},"source":["## Choix de la valeur de K\n","\n","La valeur de K est également difficile à trouver, surtout quand on a peu d'informations sur les données en entrée.</br>\n","Dans ce cas là, plusieurs méthodes existent:</br>\n","\n","La méthode du \"Gap Statistic\":</br>\n","https://statweb.stanford.edu/~gwalther/gap\n","\n","La méthode de l'Indice de Davies-Boulding:</br> https://en.wikipedia.org/wiki/Davies%E2%80%93Bouldin_index</br>\n","https://openclassrooms.com/en/courses/4379436-explorez-vos-donnees-avec-des-algorithmes-non-supervises/4379556-definissez-les-criteres-que-doit-satisfaire-votre-clustering</br>\n","\n","La méthode de la silhouette:</br>\n","https://openclassrooms.com/en/courses/4379436-explorez-vos-donnees-avec-des-algorithmes-non-supervises/4379556-definissez-les-criteres-que-doit-satisfaire-votre-clustering</br>"]}]}