{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"DBSCAN.ipynb","version":"0.3.2","provenance":[],"collapsed_sections":[]},"kernelspec":{"name":"python3","display_name":"Python 3"}},"cells":[{"cell_type":"markdown","metadata":{"id":"dh1cCGAyww2z","colab_type":"text"},"source":["# DBSCAN - Algorithme non-supervisé\n"," DBSCAN est un algorithme de clustering non-supervisé, c'est à dire qu'il ne prend pas en entrée de données déjà libellelées, il n'y a pas besoin de \"l'entrainer\".</br>\n"," DBSCAN repose sur un principe de densité, il crée des clusters s'il y a suffisament de points regroupés dans une zone, et rajoute tous les voisins qui sont suffisament proches.\n"," \n","## Chargement des données\n"]},{"cell_type":"code","metadata":{"id":"8oBNpMIew9Ie","colab_type":"code","colab":{}},"source":["import numpy as np\n","import matplotlib.pyplot as plt\n","\n","# Les paramètres importants\n","nbr_clusters=4\n","nbr_points=1000\n","\n","\n","# Les listes\n","points=[]\n","labels=[]\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","val=0.7\n","barycentres=[np.array([val,val]),np.array([val,-val]),np.array([-val,-val]),np.array([-val,val])] \n","\n","# Création des données d'initialisation\n","for i in range(nbr_points):\n","  indice=np.random.randint(0,nbr_clusters)\n","  point=barycentres[indice]+np.random.normal(scale=0.2,size=2) # Répartition normale autour d'un barycentre\n","  points.append(point)\n","  labels.append(indice)\n","  donnees_initialisation[indice].append(point)\n","\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: {}'.format(nbr_points))"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"qb4SYTPUxbc1","colab_type":"text"},"source":["## Création de l'algorithme\n","\n","Nous allons donc créer cet algorithme en 3 étapes, en suivant le pseudo-code suivant (vous pouvez le retrouver sur Wikipédia) :</br>\n","\n","```\n","DBSCAN(D, eps, MinPts)\n","   C = 0\n","   pour chaque point P non visité des données D\n","      marquer P comme visité\n","      PtsVoisins = epsilonVoisinage(D, P, eps)\n","      si tailleDe(PtsVoisins) < MinPts\n","         marquer P comme BRUIT\n","      sinon\n","         C++\n","         etendreCluster(D, P, PtsVoisins, C, eps, MinPts)\n","          \n","etendreCluster(D, P, PtsVoisins, C, eps, MinPts)\n","   ajouter P au cluster C\n","   pour chaque point P' de PtsVoisins \n","      si P' n'a pas été visité\n","         marquer P' comme visité\n","         PtsVoisins' = epsilonVoisinage(D, P', eps)\n","         si tailleDe(PtsVoisins') >= MinPts\n","            PtsVoisins = PtsVoisins U PtsVoisins'\n","      si P' n'est membre d'aucun cluster\n","         ajouter P' au cluster C\n","          \n","epsilonVoisinage(D, P, eps)\n","   retourner tous les points de D qui sont à une distance inférieure à epsilon de P\n","```\n","\n","### La fonction principale de DBSCAN\n"," Nous allons coder la fonction principale de DBSCAN, elle sera appelée au début et retournera les clusters créés.\n","</br>\n","\n","```\n","DBSCAN(D, eps, MinPts)\n","   C = 0\n","   pour chaque point P non visité des données D\n","      marquer P comme visité\n","      PtsVoisins = epsilonVoisinage(D, P, eps)\n","      si tailleDe(PtsVoisins) < MinPts\n","         marquer P comme BRUIT\n","      sinon\n","         C++\n","         etendreCluster(D, P, PtsVoisins, C, eps, MinPts)\n","\n","```\n","\n"]},{"cell_type":"code","metadata":{"id":"02F1QADpar3J","colab_type":"code","colab":{}},"source":["def dbscan(points,eps,minPts,distance):\n","  \"\"\"\n","  Fonction DBCSAN qui génére des clusters\n","  Il prend les points en entrée et donne en sortie les clusters\n","  sous forme de listes de listes des indices des points\n","  \"\"\"\n","  \n","  for i in range(len(points)):\n","      if visites[i]==False:\n","        \n","          point=points[i]\n","          ptsVoisins=epsilonVoisinage(points,i,eps)    ### CETTE LIGNE SERA A COMPLETER\n","          \n","          if len(ptsVoisins)<minPts: \n","          # Il n'a pas assez de points voisins, on considère le point comme du bruit\n","              bruit.append(i)\n","          else:\n","          # On peut créé un cluster car il y a assez de points\n","              clusters.append([])\n","              etendreCluster(points,i,clusters,ptsVoisins,eps,minPts)\n","              \n","  return clusters"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"Y0ZCkSpQboIq","colab_type":"text"},"source":["### epsilon_voisinage()\n","\n","\n","```\n","epsilonVoisinage(D, P, eps)\n","   retourner tous les points de D qui sont à une distance inférieure à epsilon de P\n","```\n","\n"]},{"cell_type":"code","metadata":{"id":"98uXbUd1bu_a","colab_type":"code","colab":{}},"source":["def epsilonVoisinage(points,i,eps):\n","  \"\"\"\n","  Fonction qui crée la liste des points à une distance inférieure à eps (epsilon)\n","  du point i\n","  \"\"\"\n","  \n","  liste=[]\n","  point=points[i]\n","  for j in range(len(points)):\n","    \n","      if i==j: continue # Pour éviter que cela corresponde au même point\n","      d=distance(points[j],point)    ### CETTE LIGNE SERA A COMPLETER\n","      if d<eps: \n","          liste.append(j)\n","  return liste"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"5WMs4KdOcT-u","colab_type":"text"},"source":["### etendre_cluster()\n","\n","\n","```\n","etendreCluster(D, P, PtsVoisins, C, eps, MinPts)\n","   ajouter P au cluster C\n","   pour chaque point P' de PtsVoisins \n","      si P' n'a pas été visité\n","         marquer P' comme visité\n","         PtsVoisins' = epsilonVoisinage(D, P', eps)\n","         si tailleDe(PtsVoisins') >= MinPts\n","            PtsVoisins = PtsVoisins U PtsVoisins'\n","      si P' n'est membre d'aucun cluster\n","         ajouter P' au cluster C\n","```\n","\n"]},{"cell_type":"code","metadata":{"id":"XVupAb_FcbaJ","colab_type":"code","colab":{}},"source":["def etendreCluster(points,i,clusters,ptsVoisins,eps,minPts):\n","  \"\"\"\n","  Fonction qui va étendre le dernier cluster de la liste généré avec le\n","  point i\n","  \"\"\"\n","  \n","  clusters[-1].append(i)\n","  \n","  for j in ptsVoisins:\n","    if visites[j]==False: # Si le point n'a pas été déjà visité\n","      \n","      visites[j]=True\n","      nouveauxPtsVoisins=epsilonVoisinage(points,j,eps)\n","      if len(nouveauxPtsVoisins)>=minPts: # si le point a suffisament de points,\n","                                          # on l'ajoute\n","        ptsVoisins=fusionner(ptsVoisins,nouveauxPtsVoisins)   ### CETTE LIGNE SERA A COMPLETER\n","      \n","      # On regarde si le point appartient à l'un des clusters, sinon on l'ajoute \n","      inACluster = bool(sum([j in cluster for cluster in clusters]))\n","      if inACluster==False:\n","        clusters[-1].append(j)\n"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"1VxsUhXtdprT","colab_type":"text"},"source":["Il nous faut encore créer une fonction **fusionner()** qui aura pour but de faire la réunion de 2 listes.</br>\n","On ne peut se contenter ici d'une simple concaténation, car il ne faut pas d'éléments en double dans la liste finale."]},{"cell_type":"code","metadata":{"id":"SN9FA0PYd9fW","colab_type":"code","colab":{}},"source":["def fusionner(L1,L2):\n","  \"\"\"\n","  Fonction qui réalise l'union de 2 listes\n","  \"\"\"\n","  L3=L1[:]\n","  for x in L2:\n","    if not (x in L2):\n","      L3.append(x)\n","  return L3\n"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"DRCU6L8ken7w","colab_type":"text"},"source":["## Test de l'algorithme\n","Nous allons pouvoir tester notre algorithme DBSCAN sur les données que nous avons chargé plus haut.</br>\n"]},{"cell_type":"code","metadata":{"id":"cTaTuGMMeylP","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","plt.axis('equal')\n","\n","# Définition des couleurs des clusters et des barycentres\n","couleurs=['r','g','b','y']\n","\n","for i, point in enumerate(points):\n","  label=labels[i]\n","  plt.plot(point[0],point[1],color=couleurs[label],marker=\"+\") # On affiche chaque point avec la couleur de son cluster\n","\n","plt.show()"],"execution_count":0,"outputs":[]},{"cell_type":"code","metadata":{"id":"_XZOA-rMfLGS","colab_type":"code","colab":{}},"source":["# Paramètres\n","epsilon = 1\n","min_pts = 3\n","def distance(pt1,pt2):\n","  return sum((pt1-pt2)**2)**(1/2)\n","\n","eval_labels = []\n","\n","clusters=[]\n","bruit=[]\n","visites=[False for i in range(len(points))]\n","\n","resultat = dbscan(points, epsilon, min_pts, distance)\n","\n","# On crée juste une liste de liste de points correspondants, cela sera pratique dans la suite\n","donnees_dbscan = []\n","for i in range(len(resultat)):\n","  donnees_dbscan.append([])\n","  for j in range(len(resultat[i])):\n","    donnees_dbscan[i].append(points[resultat[i][j]])\n","\n","    \n","print('=== Résultats avec DBSCAN ===')\n","print('Nombre de clusters: {} pour {} points'.format(len(clusters),len(points)))\n","for i in range(len(clusters)):\n","  print('  Cluster {} : {} points'.format(i+1,len(resultat[i])))"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"h-M2HfSE8d9R","colab_type":"text"},"source":["D'après ce que l'on vont, cela semble bien fonctionner avec les données que nous avons, mais il est plus simple d'afficher le résultat final sous forme de graphique.\n"]},{"cell_type":"code","metadata":{"id":"oRLM9GAA8zkt","colab_type":"code","colab":{}},"source":["coloriage=['#990000','#009900','#000099','#000000','#666666']\n","\n","plt.figure(figsize=(20,10))\n","plt.xlim([-lim,lim])\n","plt.ylim([-lim,lim])\n","\n","\n","for i,cluster in enumerate(resultat):\n","  for indice in cluster:\n","    point=points[indice]\n","    plt.plot(point[0],point[1],color=couleurs[i],marker='+')\n","    "],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"--bnw84Wb1c_","colab_type":"text"},"source":["### Une fonction d'évaluation\n","\n","Nous allons essayer d'avoir une estimation de l'efficacité de l'algorithme. D'après les graphiques ci dessus, cela semble être correct et bien correspondre à ce que l'on espère.</br>\n","Mais nous allons essayer de faire correspondre à chaque cluster généré par DBSCAN un des 4 clusters de départ.</br>\n","Le nombre résultant n'est pas forcément très pertinent, car si l'algorithme forme énormément de clusters, cela nous donnera une efficacité proche de 100%. Mais cela permet de donner un indicateur de l'efficacité de l'algorithme.</br>\n","Mais cela traduit ce que nous pouvons voir ci-dessus, c'est à dire à quel point cela peut correspondre à ce qui était \"attendu\"."]},{"cell_type":"code","metadata":{"id":"N98ewzA3ecHx","colab_type":"code","colab":{}},"source":["def evaluerEfficaciteAlgo(clusters_dbscan,clusters_donnee): \n","  \"\"\"\n","  Fonction qui va essayer de \"matcher\" chaque cluster créé par DBSCAN \n","  avec les clusters créés lors de la génération des points.\n","    clusters_dbscan : Ce sont les clusters générés par DBSCAN\n","    cluster_donnee  : Ce sont les clusters créés lors de la génération des points\n","    (les clusters sont sous la forme : liste de liste de points)\n","    \n","    \n","  Elle retourne un score (pourcentage) total et également la liste des labels\n","  des points si on faisait la correspondance entre les clusters \n","  (cela peut etre utile pour faire de l'affichage).\n","  \"\"\"\n","  def evaluerCluster(clusters_dbscan,cluster_donnee):\n","        \"\"\"\n","        Cette sous-fonction va donner le nombre de points de cluster_evaluer\n","        qui sont dans cluster_donnee.\n","        \"\"\"\n","        nbr=0\n","        for x in clusters_dbscan:\n","            for y in cluster_donnee:\n","                if distance(x,y)<10**(-10):\n","                    nbr+=1\n","        return nbr\n","     \n","  success=0\n","  labels=[]\n","  \n","  for cluster_dbscan in clusters_dbscan:\n","      # On calcule la corrélation (nombre de points communs) pour tous les clusters\n","      # qui ont été créés lors de la génération des points\n","      # Ensuite on considère que celui qui en a le plus est celui qui correspond\n","      # Donc on update le success (nombre de points correspondant total)\n","      resultat=[]\n","      for cluster_donnee in clusters_donnee:\n","          resultat.append(evaluerCluster(cluster_dbscan,cluster_donnee))\n","      success+=max(resultat)     ###  CETTE LIGNE SERA A COMPLETER\n","      \n","      labels.append(resultat.index(max(resultat)))\n","      \n","  return success/sum([len(x) for x in clusters_donnee])*100,labels\n","\n","\n","efficacite = evaluerEfficaciteAlgo(donnees_dbscan,donnees_initialisation)[0]\n","\n","\n","print('Efficacité de l\\'algorithme : {}'.format(efficacite))"],"execution_count":0,"outputs":[]}]}