User Tools

Site Tools


brout_marie:solution_homework2

Correction

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

B.P. : Pourquoi avoir changé de dataset ? Travail incomplet.

Compte-rendu

Implémentation de l'Algorithme Cure


Dossier contenant l'implémentation de l'algorithme de Cure : algocure_-_brout_marie.zip

A) Les données utilisées :

Il me semblait intéréssant de regarder si il pouvait exister un quelconque lien entre le sucre et les calories des céréales : de regarder si les céréales le splus sucrées sont également les plus caloriques. On pouvait également faire la comparaison entre les calories et le graisses ou les proteines, car les résultats pourraient ne pas correspondre avec les slogans nutritionnelles effectués dans les publicités de céréales ( exemple : les céréales sans sucre ou 0% de matières grasse sont peu calorique, etc).

Le CSV est d'ailleurs disponible en téléchargement ici : http://www.idvbook.com/teaching-aid/data-sets/the-breakfast-cereal-data-set/

Il fallait donc tout d'abord commencer par “normaliser” les données sur lesquelles l'algorythme allait être appliqué (cf dans le dossier , le fichier data_set).


B) Ce qui a pu être réalisé :

L’algorithme de Cure que j'ai partiellement implémenté permet de clusteriser les données et utilise la distance euclidiennes pour calculer la proximité entre deux clusters.

Malheureusement l'algorithme algoCure ne fonctionne pas sur les données normalisées. En effet il semblerait qu'en parcourant la liste des points représentants, pour calculer la distance euclidienne, il y est un objet 'list' à la place d'un point d'où le message d'erreur : 'list' object has no attribute 'x. Il y a donc sûrement un problème lors de l'appellation de la fonction algocure, avec le parametre inputpoints ou sans doute avec le script de normalisation.

Néanmoins l'algorithme fonctionne sur les données non normalisées. L'implémentation de l'algorithme de Cure que j'ai réalisée est donc en partie fonctionnelle (sur les données non-normalisées) puisque l'on arrive, au final, au nombre voulu k de clusters. Néanmoins l'implémentation n'est pas optimale.

En effet l'implémentation que j'ai effectué n'utilise pas de Kd-Tree ce qui a engendre une augmentation considérable du temps d'execution.


C) Ce qui reste à réaliser :

Il reste donc à implementer un Kd-Tree (arbre de recherche binaire) qui stockerais les points représentatifs des clusters et permettrait de faire des recherches plus rapidement, notamment lors du calcul du cluster voisin le plus proche après la fusion, qu'en parcourant linéairement un tableau de points.

Par manque de temps (car il a fallut que je prenne en main le langage python qui m'étais inconnu) je n'ais pas pu le faire mais j'ai commencé à étudier des pseudo-codes existants notamment celui de wikipédia qui propose une implémentation simplifiée et en python accessible ici : http://en.wikipedia.org/wiki/Kd-tree

Ainsi qu'une implémentation plus complexe qui aurait pu être utilisable dans mon algorithme si j'avais eu le temps de l'adapter : http://en.sharejs.com/python/11968

Marie Brout 2013/11/11 20:10

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/brout_marie/solution_homework2.txt · Last modified: 2014/01/08 11:57 by bpinaud