User Tools

Site Tools


delestre_clement:solution_homework2

Correction

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

B.P. : C'est bien !!!

Compte-rendu


Exercice : Implémentation de l'algorithme de CURE.
Binome : Cynthia PERIER et Clément DELESTRE ( Bio-informatique )


Organiser et classer des données de manière objective est un domaine complexe. L'algorithme de CURE propose de répondre à cette problématique de manière relativement rapide et pertinente. Après avoir implémenté CURE en utilisant Tulip, nous exposerons ici nos choix d'implémentation, nos solutions de visualisation et notre analyse des résultats.

Choix d'implémentation

Paramètres

L’ensemble des résultats décrit dans ce compte rendu est obtenu avec les paramètres qui suivent.

Les variables testées sont le poids des voitures “Weight” et leur autonomie en ville “City_MPG”. Elles ont été choisies car elles appartiennent à un domaine continu. Il peut être intéressant de savoir si le poids d’une voiture influence sa consommation sur des trajets courts et irréguliers.

Après une série de tests, le nombre de cluster final est 10. Il comprend les éventuels outliers (voir section correspondante) tout en permettant un clustering significatif sur le reste des points.

Le nombre de représentants par cluster est fixé à 5. Les représentants sont ainsi suffisamment nombreux pour recouvrir les extrémités du cluster de façon significative tout en assurant un temps d’exécution convenable. La faible quantité de points dans le graphe ne permet de toute façon pas de trop augmenter ce nombre.

Durant leur agglomération, chaque cluster se voit attribuer une couleur parmi une palette de 10 : compromis entre nombre suffisant et nombre maximal différentiables par l’œil humain.

Le paramètre alpha de réduction des distances est fixé à 0.55. L'article préconisait un alpha compris entre 0.2 et 0.7.

Structures de données

Chaque cluster est représenté par un objet comprenant :

  • une liste de points
  • une liste de représentants
  • un point moyen virtuel (en fait, la moyenne des “Weight” et celle des “City-MPG” des points du cluster)
  • un point le plus proche et leur distance
  • une couleur

L’algorithme utilise ces clusters au moyen de deux structures de données : une liste et un tas.

La liste de clusters permet de parcourir simplement l’ensemble des clusters encore présent, de supprimer les clusters mergés et d’ajouter les nouveaux clusters.

Le tas trie les clusters en fonction de leur distance au plus proche cluster. Il permet de récupérer rapidement celui dont la distance est la plus faible (le premier de la file). Il est implémenté par le module python heapq, qui est en fait un algorithme de file de priorité. Chaque cluster ajouté y est directement trié.

Le kd-tree n’a pas été implémenté car le jeu de données utilisé est suffisamment petit pour s’en passer sans que la vitesse d’exécution en soit affectée.

Visualisation

Types de visualisation

Pseudo histogramme

Exemple de pseudo histogramme Afin de mieux visualiser les clusters, et surtout les points qu'ils contiennent, nous avons décidé de modifier la position des points en fonction du cluster auquel ils appartiennent. Ainsi, chaque point a une abscisse qui dépend du cluster dans lequel il se trouve. Quant à l'ordonnée, elle s'incrémente en fonction du nombre de points composant ce dernier. Cette forme de visualisation ressemble donc à un histogramme (cf figure ci-dessus) cependant, si l'axe des ordonnées correspond au nombre de points, celui des abscisses ne correspond à rien. En effet, on ne peut pas tirer de conclusion sur l'abscisse des colonnes (qui représentent les clusters), contrairement à un vrai histogramme. C'est pour cela que le terme pseudo histogramme a été choisi.

On affiche le pseudo-histogramme à la fin du traitement des clusters.

Scatter Plot

Exemple de scaterplot La limite de la visualisation précédente est qu'on ne peut pas savoir si les clusters ont réellement un sens ou non car les noeuds ne sont pas placés en fonction des variablés étudiées (ici weight et city miles per galon). Pour palier à cette faiblesse, nous pouvons aussi utiliser la Scatter Plot 2d View disponible dans Tulip. Ceci nous permet de dire si les clusters obtenus nous paraissent cohérent ou non. Cependant, cette visualisation possède deux limites :

  1. Il n'est possible d'utiliser que 2 dimensions.
  2. On ne peut pas distinguer les points confondus.

Le scatter plot ne pouvant être modifié en cours de traitement, on simule un scatter plot pendant le déroulement de l'algorithme. Chaque nœud du graphe est positionné en fonction de son poids et de son autonomie. On peut ainsi observer les clusters pendant leur agglomération grâce à la coloration des points.

Outliers

Par défaut, tous les points sont gris. Il a été choisi de colorer les points des clusters uniquement s'ils en contiennent au minimum deux. Ainsi, on peut simplement repérer les outliers. Il faut donc avoir à l'esprit que chaque point gris est un outliers, autrement dit un cluster à part entière qui ne contient qu'un seul point.

Analyse des clusters

On obtient 6 clusters principaux et 4 outliers. Les trois voitures ayant le poids le plus élevé pour l'autonomie la plus faible sont rassemblées dans un cluster (les trois points roses). Ce sont des SUV ou des 4×4. Les autres voitures se répartissent dans des clusters d'autonomie croissante et de poids décroissant. On peut quasiment effectuer une régression linéaire sur les six clusters. On en conclut qu'une voiture lourde consomme plus en ville qu'une voiture légère, ce de façon proportionnelle. On constate également que les clusters “voitures lourdes/gourmandes” sont plutôt de grosses américaines et les “légères/peu gourmandes” sont souvent des citadines japonaises (exemple : cluster rouge.)

En analysant les outliers, on s’aperçoit que les 3 voitures hybrides 1) en font partie (ce sont les trois points les plus à droite du plot). Malgré des poids divers, leur consommation en diesel/essence est extrêmement faible. Il est aisé de comprendre que pour ces dernières la consommation n'a pas vraiment le même sens que pour les autres véhicules. Elles ne sont pas dans le même cluster car leurs caractéristiques restent trop différentes. Le 4ème outlier, proche des trois autres, n'est pas indiqué comme étant hybride. On peut soit supposer que cette précision a été omise, soit qu'il s'agit d'un diesel particulièrement peu gourmand vu son poids.

En conclusion on a pu implémenter l'algorithme de CURE en visualisant nos résultats grâce à Tulip. Il aurait été possible de rajouter des algorithmes de pré-traitement qui permettent de gérer les outliers plus finement comme le random sampling. Le code source est disponible sur le liens suivant : https://www.dropbox.com/s/370pv7ru7qo734k/CURE_Dent.py

1) attention la plus externe se trouve sur l'axe des abscisses
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/delestre_clement/solution_homework2.txt · Last modified: 2014/01/08 11:59 by bpinaud