User Tools

Site Tools


dayris_melius:thibault_dayris_jonathan_melius

Visual Analytics Course

Bordeaux roadmap 2013- 2014 / Thibault Dayris & Jonathan Melius's corner

Rappel du sujet

Visual feedback from MDS projection Thibault Dayris & Jonathan Melius

« This project consists in reading, understanding and implementing Aupetit's paper providing visual feedback on an MDS projection of high-dimensional data. Their idea is actually quite simple. Suppose an MDS projection is given, and select a point v in the projection. One can then compute whether the distances of the other points to v are faithful using a diverging colormap (as suggested by the ColorBrewer, for instance) so users can evaluate how much distortion there is in the MDS projection.

The project assumes you will use this technique to compare various projection algorithm. A projection can be computed using classical MDS, or using a nearest graph laid out with a force-directed algorithm, for instance.

Deliverables: code implementing the computation of the distortion index, as well as the different projections (MDS, force-directed, etc.). You are expected to reproduce the results found in papers, show the benefits and limitations of the work, discuss the technique in a report and oral presentation. »

/!\ Attention /!\

L'article initialement fournit dans le wiki n'est pas celui qui nous a été finalement délivré. Veuillez trouver ci-dessous la DOI de l'article :

doi:10.1016/j.neucom.2006.11.018

Compte rendu

Introduction

La visualisation des données est un des moyens d'en discerner les motifs et/ou comportements globaux. La visualisation de données à grand nombre de dimensions pose d'évidents problèmes de représentation graphique. Ainsi, diverses méthodes permettent de réduire ces jeux de données à des dimensions - généralement R² - qui peuvent être prises en charge par les logiciels courants. Pourtant, les méthodes de projection de données se font forcément via la modification - et la perte - d'information.

Dans l'article proposé en sujet, les auteurs ont choisi la PCA (Pricipal Component Analysis) et la CCA (Cruvilinear Component Analysis) pour réduire le nombre de dimensions de leur données. Ces méthodes se basent sur la minimisation de la distance entre tous les points et l'axe/plan/hyperplan de projection pour une perte minimale d'information. Dans l'exercice proposé, nous utiliserons la MDS (Multidimensionnal Scaling) qui se base sur des matrices de similarités pour positionner les points depuis leur espace de dimension originel jusque dans R² ou R³ pour les représenter dans un graphe ou en plot3D.

La question qui se pose alors est de savoir quelles sont les conséquences de telles projections ? Le rendu final, dans R², permet-il de venir aux mêmes conclusions que si les données avaient été visualisées dans leur espace de dimensions initial ?

Pour répondre à cette question, les auteurs de cet article proposent d'étudier les points, segments ou aires sur la visualisation dans l'espace projeté R³. Il convient selon eux de définir deux situations : si les points sont bien placés les uns par rapport aux autres ou non. C'est-à-dire : est-ce que les distances entre les points dans l'espace de dimension originel sont comparables à la distance entre ces mêmes points dans l'espace projeté R² ? Dans l'optique de caractériser les déformations, les auteurs proposent de définir deux types de déformations : les compressions et les étirements.

Dans l'optique de reproduire les résultats obtenus dans l'article de Michaël Auptit tout en respectant le sujet, nous allons créer un jeu de données tridimensionnel aléatoire selon une loi normale. À partir de ces données, nous effectuerons une MDS pour pouvoir les tracer sur un graphe puis étudierons les déformations issues de la projection. Tous les travaux présentés pour ce projet étudiant ont été réalisés en Python 2.7 sous Tulip.

Projection des données : MDS

Deux méthodes ont été utilisées pour projeter les données depuis leur espace de dimension originel R³ jusque dans un espace R² qu'il est possible de visualiser sur un graphe : le MDS et la PCA.

La MDS propose de transformer les matrices de distances en similarités avant de passer par une méthode proche de la PCA. Cette dernière, quant à elle, utilise les éléments propres d'une matrice (vecteur et valeur propre). En ça, les deux méthodes sont concrètement très proches dans un espace euclidien.

Calculs des compressions & des étirements

L'ensemble des calculs présentés ici sont disponibles en partie 2 & 3 de l'article de Michaël Aupetit.

La projection réalisée, l'enjeu principal des travaux présentés dans cet article est le calcul des distorsions créées par le passage de l'espace de dimension originel R³ à l'espace de projection R².

Les auteurs commencent donc par définir les compressions et étirement de points (partie 3.1 de l'article). Il s'agit, pour chaque point, de normaliser la distorsion à laquelle ses coordonnées sont soumises. On calcule donc ces distorsions en utilisant les différences des matrices de similarités dans les deux espaces originels et projeté.

Les distorsions de segments sont à appliquer les arrêtes d'un graphe de Delaunay. Ce graphe peut être aisément obtenu dans Tulip en utilisant le plugin du même nom. Dans le même raisonnement qu'avec les points, il va s'agir de normaliser les distorsions entre deux points par rapport à celles du graphe entier - notamment les maxima et les minima.

Les triangles définies entre ces segments par le graphe de Delaunay peuvent également être soumis aux mesures de distorsions. Le même raisonnement que précédemment est appliqué, à ceci près que l'on ne compare plus des distances entre des points, mais dais aires dans les espaces de dimensions originel et projeté.

Les mesures proposées par l'article permettent d'obtenir des valeurs de compression et d'étirement comprises entre 0 - aucun étirement/compression - et 1 - très fort étirement/compression. De même, s'il y a compression, il n'y a pas de valeur de compression. Ces mesures ne sont donc pas arithmétiques et n'admettent pas de résultat négatif. En effet, dans la totalité des cas, une valeur négative est considérée par ses auteurs comme étant nulle.

Trois scripts Python sont disponibles pour réaliser les calculs de chacune de ces distorsions : PointDistortion.py, SegmentDistortion.py et TriangleDistortion.py. Réalisés en Python 2.7, leur seule dépendance revient à la bibliothèque numpy. Ils ne contiennent que les fonctions destinées aux calculs des distorsions dont ils sont responsables. Attention, l'article propose régulièrement des notations identiques pour des concepts différents et inversement. Les notations strictes de l'article ont été conservées.

Visualisation des compressions et des étirements

Les calculs de distorsions réalisés, il devient nécessaire de les visualiser.

Afin de représenter au mieux la projection et ses distorsions, nous procédons en trois étapes. Premièrement, le positionnement des points dans un repère orthonormé dans R² qui est réalisé dans Tulip après la MDS. Secondement, le dessin des segments sur lesquels nous allons calculer l'étirement et la compression, qui sont réalisés via le plugin du graphe de Delaunay dans Tulip. Enfin, l'application des jeux de couleurs en fonction des distorsions calculées.

Nous l'avons vu dans la partie précédente, les résultats des calculs de compression nous retournent une valeur comprise entre 0 et 1. Concrètement, on multiplie respectivement les canaux rouges et verts par la valeur de compression et d'étirement. Un gradient de couleur permet donc d'évaluer visuellement les mesures : vert clair → vert foncé → noir → rouge foncé → rouge clair, du plus étiré au plus compressé.

Conclusion & Discussion

En conclusion à ce projet, nous pouvons mettre en avant que la coloration proposée permet une meilleure appréhension des projections des jeux de données, d'un point de vue qualitatif. Il permet de mettre en avant des outliers dûs à une mauvaise projection et à prévenir certaines erreurs d'interprétations qui pourraient en découler.

Les auteurs font également remarquer que, le seuil à partir duquel une distorsion devient problématique pour une interprétation correcte du graphe obtenu par projection, est une valeur attribuée de manière arbitraire.

On peut mettre en avant le fait que seule la PCA, une projection linéaire des données a été utilisée pour réduire en dimension les données initiales. L'utilisation de méthodes complémentaires comme des projections non linéaires pourrait apporter des informations complémentaires et des résultats de distortions différents. Avec la méthode présentée, il serait possible, en comparant un « taux de distorsion », de décider si une projection est meilleure d'une autre.

Veillez trouver ci-joint, l'archive contenant le projet ainsi que l'ensemble des dépendances. projet_biovisu_dayris_melius.tar.bz2

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/dayris_melius/thibault_dayris_jonathan_melius.txt · Last modified: 2014/01/17 12:49 by jmelius