User Tools

Site Tools


chicoutimi_2016:masses_ressorts_donnees_multidimensionnelles

Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

Chicoutimi Summer 2016 roadmap / May 3, 3pm course

Modèle masses ressorts, données multi-dimensionnelles et dissimilarités

Nous évoquions tout à l'heure,

qu'on peut mesurer la qualité d'une représentation dans de données multidimensionnelles (dans ) à l'aide du stress.

Reste donc à préciser comment on peut calculer une représentation d'un ensemble de données multidimensionnelles . On supposera que ces données sont équipées d'une matrice de dissimilarités:

  • Souvent, les valeurs sont les distances euclidiennes entre les éléments de l'espace de dimension .
  • On peut aussi penser à des dissimilarités calculer comme la distance cosinus entre documents textes – eux-mêmes vu comme des vecteurs de mots.

Masses-ressorts Une idée, qu'on peut attribuer à Matthew Chalmers:

  • Chalmers, M. (1996). A Linear Iteration Time Layout Algorithm for Visualizing High-Dimensional Data. IEEE Symposium on Information Visualization, San Francisco, USA, IEEE Computer Society, 127-132.

plus tard revue et améliorée:

  • Morrison, A. and M. Chalmers (2003). Improving Hybrid MDS with Pivot-Based Searching. IEEE Symposium on Information Visualization, Seattle, USA, IEEE Computer Society, 85-90.
  • Morrison, A., G. Ross, et al. (2002). A Hybrid Layout Algorithm for Sub-Quadratic Multidimensional Scaling. IEEE Symposium on Information Visualization, Boston, USA, IEEE Computer Society, 152-158.

est d'utiliser un algorithme à base de masses et de ressorts sur les éléments . Si le ressort est comprimé en deça de la longueur idéale , on fait agir une force de répulsion; si le ressort est étiré (au-delà de la longueur ), on fait agir une force d'attraction.

Le modèle de base présenté dans le cours est particulièrement adapté à cette situation. En effet, la force calculé pour les sommets incidents (connectés par une arête) agit soit comme une force d'attraction, soit comme une force de répulsion selon la distance entre les points associée aux éléments .

En d'autres mots, il suffit de considérer l'ensemble de données comme un graphe complet et de faire tourner l'algorithme. Cela dit, il faut ici considérer des longueurs idéales distinctes pour toutes les paires de sommets.

  • Dans le cas d'un graphe, les critères esthétiques recherchées nous avait incité à fixer la longueur idéale d'une arête de manière uniforme sur tout le graphe.
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/masses_ressorts_donnees_multidimensionnelles.txt · Last modified: 2016/05/12 17:39 by melancon