User Tools

Site Tools


dufau_bastien:solution_homework2

Correction

Critères & points attribués (/10)
Rappel du contexte 6
Résultats 7
Qualité du code (commentaires, structures utilisées, …) 7
Animation et visualisation 6
Explication en dehors du code 6
Total (/50) 32

B.P. : Bonnes explications sur la structure du code mais pas d'analyse des résultats.

Compte-rendu

Codes sources (ajouté B. Pinaud) : archives

Algorithme Cure


Travail fait par Bastien Dufau et Paul-Emile Boutoille

Afin de réaliser l'algorithme Cure, nous avons d'abord décidé de la structure d'une classe. Nous avons ensuite implémenter des fonctions permettant d'accéder, de modifier et d'effectuer des opérations sur ces mêmes classes. Avant cela, il nous fallait des données essentiel pour cet algorithme , nous avons donc définis plusieurs variables “globale” au module .

Les variables définies

Pour réaliser cet algorithme, nous avons rassemblé des données dans nos variables, celles ci sont :

  • all_vertices : liste de tous les points du graphe avec leur coordonnées .
  • verticesToClasses : correspondance entre le point et son numéro de classe .
  • classes : liste de toutes les classes .
  • distances : liste des distances entre les points .

Les classes

Structure

L'objet s'appelle CClasse et il est composé de la manière suivante :

  • xBar : coordonnée x du barycentre de la classe .
  • xBar : coordonnée x du barycentre de la classe .
  • yBar : coordonnée y du barycentre de la classe .
  • repre : liste des représentant de la classe .
  • vertices : liste de tous les points de la classes .

Accession et modification des classes

On peut accéder aux éléments de la classes via ces fonctions :

  • getRepre() : renvoi la liste des représentant .
  • getVertices(): renvoi la liste des éléments de la classe .
  • afficherClasse ( c ) : affichage de la classe c .

On peut les modifier grâces a ces fonctions :

  • addVertices(self, newVertices) : ajout de “newVertices” à la liste déjà présente dans la classe .
  • deleteVertices(self) : suppression de toute la listes .
  • refreshBarr(self,all_vertices ): calcul du nouveau barycentre de la classe .
  • refreshRepre(self,all_v) : calcul des nouveaux représentants de la classe .
  • fusionClasses (all_vertices,classes,verticesToClasses,a,b) : fusion de deux classes a et b . La fusion ce fait dans la classe qui possède le plus petit indice dans la liste des classes. On ajoute les points d'une classe à l'autre, dans laquelle on recalcul le barycentre ainsi que les représentant. La classe qu'on ne désire plus voit sa liste de points rendu vide .

Enfin, on a une fonction qui nous permet de connaître la distance entre deux classe:

  • distClasses(all_vertices,a,b) : renvoi la distance entre la classe a et b .

Implémentation de l'algorithme Cure

Appel

L'algorithme s'appelle de la manière suivant : cure(val_x, val_y, nb_classes_min, k_repre, ret = False).

  • val_x,val_y : Liste des coordonnées qui vont servir pour calculer les classes.
  • nb_classes_min : nombre de classes que l'on veut après éxecution .
  • k_repre : nombre de représentant pour chaque classes .
  • ret : choix d'une valeur de retour ou non.

Initialisation

Avant toute chose, on initialises les variables que l'on à définie précédemment à savoir : all_vertices, verticesToClasses avec une boucle qui parcours tous les sommets du graphe puis :

  • initAllClasses(all_vertices,k_repre) : pour initialiser le tableau des classes.
  • initDistances(all_vertices,classes,taille_max) : pour initialiser le tableau des distances entre les sommets.

Pour le premier pas de l'algorithme, chaque points du graphe est une classes, on à donc autant de classes que de points, chacune ayant un barycentre et k représentant ( ici k fois le même points ).

Déroulement

Dans une boucle, tant que le nombre de classes n'est pas égales aux nombres de classes finales, on suit plusieurs étapes :

  1. Recalcul des distances entre les points si nécessaire.
  2. Trouve les deux classes les plus proches via la distance entre les représentants.
  3. Si les classes ne sont pas les même alors on les fusionnes.
  4. On diminue le nombre de classes.
  5. On retourne au début de la boucle.

Coloration et dessin

Une fois l'algorithme fini, on parcours le tableau des classes et si celles-ci n'est pas vide, on dessine ces sommets de maniere horizontale. On se décale ensuite sur le plan vertical pour dessiner les autres classes. Entre chaque classe, on prend soin de modifier la couleur des points afin de bien las distinguer.

Exemple: Application de cure avec 3classes en minimum. (Avant : a gauche | Aprés:a droite )












Travail fait par Bastien Dufau et Paul-Emile Boutoille

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/dufau_bastien/solution_homework2.txt · Last modified: 2014/01/09 13:00 by bpinaud