User Tools

Site Tools


mourany_alexandre:solution_homework2

Correction

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

B.P. : Bien !

Compte-rendu

Implémentation de l'algorithme CURE

Binome : Alexandre Mourany - Claire Pennarun

Pour cet exercice nous avons choisi de chercher un potentiel lien entre le prix de vente des voitures, et le poids de celles-ci. Pour cela nous avons commencé par uniformiser les données que nous avions. Le script de cette opération peut être trouvé ici.

Implémentation avec les distances Euclidiennes

Nous avons tout d’abord choisi d’implémenter l’algorithme sans utiliser de kd-tree mais en utiliser les distances euclidiennes pour calculer la proximité entre deux clusters.

Cette version de notre algorithme est fonctionnelle et nous permet bien de trouver K clusters à la fin de son exécution, mais il est relativement gourmand en terme de temps d’exécution (plusieurs minutes d’exécution pour trouver 4 clusters sur le jeu de données à notre disposition).

Difficultés d'implémentation avec le KD-Tree

Pour palier ce problème nous avons essayé d'implémenter une structure de KD-Tree.

Cependant, même si les KD-Tree construits par notre implémentation sont corrects, nous ne sommes pas arrivés à implémenter l'algorithme de recherche du plus proche voisin. Nous avons fait deux versions récursives, la première a l'air de donner des résultats corrects mais finit par boucler, et la deuxième termine mais les résultats sont clairement faux.

Nous pensons que la raison de nos difficultés vient du fait que les points dont nous cherchons le plus proche voisin dans l'arbre sont déjà des nœuds de l'arbre, et ainsi il est difficile d'appliquer l'algorithme que nous avions trouvé.

Une façon de contourner le problème serait de supprimer le point à rechercher de l'arbre, de rééquilibrer la structure et de faire la recherche, mais cela demande du temps de calcul et l'implémentation de l'algorithme de rééquilibrage.

Une autre structure de données, par exemple un arbre binaire de recherche où les points du graphe seraient représentés dans les feuilles, pourrait être plus adaptée au problème.

Interprétation des résultats

Après avoir fait tourner notre algorithme sur notre jeu de données, nous nous sommes rendu compte que l’on pouvait distinguer 3 catégories de voitures.

  • Les voitures bas de gamme, ces voitures sont les moins chères de notre jeu de données. Nous avons remarqué qu’elles ont toutes un poids relativement proche.
  • Les voitures milieu de gamme, ces voitures sont plus chères que les précédentes. Mais nous pouvons remarquer que ce sont elles qui ont la plus grande variance de poids.
  • Les voitures haut de gamme, c’est voitures sont beaucoup plus chères que les précédentes, mais leur nombre est très restreint par rapport aux catégories précédentes.
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/mourany_alexandre/solution_homework2.txt · Last modified: 2014/01/08 18:58 by bpinaud