User Tools

Site Tools


rocher_tatiana:solution_homework2

projet_cure_bio_info.rar

Implémentation de l'algorithme Cure :

J'ai fait ce devoir en binôme avec Paul Maribon-Ferret.

Nous avons commencé par définir les fonctions permettant de calculer la normalisation, la moyenne, l'écart type et les valeurs des points. Puis nous avons créé les classes Barycentre et Cluster. La classe Barycentre est un simple point. La classe cluster possède un id, un barycentre, les listes des points du clusters et de ses représentants ainsi que l'id du cluster étant le plus proche et la distance qui les sépare.

Nous avons commencé par faire une version un peu éloignée de l'algorithme de Cure, qui séparait très bien les points en cluster, mais cette version avait une complexité très mauvaise car nous calculions trop de fois les distances entre clusters. Ensuite nous avons développé une nouvelle version qui se rapprochait plus de l'algorithme de Cure avec une meilleure complexité. Pour celle-ci, nous avons intégré une liste qui classe à chaque étape les clusters par rapport aux distances entre les clusters. Nous avons eu du mal à la mettre à jour lorsque nous regroupions deux clusters ensemble. Nous devions parcourir tous les éléments de la liste tout en la modifiant. Nous avons alors décidé de garder en mémoire les changements puis de tous les effectuer à la fin du parcours de la liste. Ceci a été le problème majeur sur lequel nous avons buté.

Pour lancer l'algorithme il faut juste rentrer le nombre de clusters que nous voulons obtenir. Nous avons choisi comme paramètre des noeuds Hwy_MPG et City_MGP. Une variable nbCluster est initialisée au début de l'algorithme afin de faire les valeurs de test, il suffit d'y mettre le nombre de noeuds que nous voulons gérer, pas défaut, tous les noeuds sont gérés.

Finalement l'algorithme tourne en 40 minutes environ pour 100 points sur une machine virtuelle.

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/rocher_tatiana/solution_homework2.txt · Last modified: 2013/11/08 00:09 by trocher