User Tools

Site Tools


chicoutimi_2016:focus_context_clustering_de_van_ham_van_wijk

Visual Analytics Course

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

Chicoutimi Summer 2016 roadmap / Session by session cutdown

DOA -- van Ham & van WIjk

Leur point de départ est un clustering du graphe qui repose sur un “bon” dessin du graphe (Noack) séparant bien les clusters qu'il contient.

  • On suppose disposer d'un graphe , et
  • d'un arbre binaire dont les feuilles sont les éléments de

La relation sommet parent - sommet enfant dans correspond à l'imbrication des clusters induit par l'algorithme de clustering hiérarchique ascendant (ou descendant).

On suppose aussi disposer sur les sommets de de la distance entre les clusters fils (0.0 pour les feuilles). On stocke aussi le barycentre du cluster (tlp.Coord). A noter que la mesure va croissant des feuilles vers la racine – c'est un ingrédient important de l'approche. C'est aussi le cas pour la valeur et calculée par Furnas sur les arbres. On note le sommet parent de , et la racine de l'arbre .

Abstraction du graphe de départ

van Ham & van Wijk utilisent ensuite l'arbre du clustering (hiérarchique ascendant) pour induire une visualisation d'une abstraction du graphe de départ. Cette abstraction est plus ou moins fine en fonction de la valeur d'un indice , soit totale lorsque (un seul “gros” sommet représentant la totalité du graphe), soit absente lorsque (autant de groupes que de sommets du graphe).

L'abstraction correspond à afficher des clusters choisis dans l'arbre et formant une antichaîne maximale (une “coupe”): tout sommet est couvert par l'antichaîne ou se trouve au-dessus de l'un de ses sommets, et deux sommets de l'antichaîne ne sont pas en relation ancêtre-descendant.

L'antichaîne qui suit du choix de l'indice est obtenu en sélectionnant les clusters satisfaisant:

Le graphe d'origine, dessiné à l'aide de l'algorithme LinLog de Noack.L'abstraction du graphe construit à partir des clusters.

DOA, contexte et détails

L'indice DOA revient donc à poser un seuil sur la mesure de distances associées au sommets de l'arbre. Pour donner une visualisation contextuelle d'un sommet, on peut appliquer ce seuil non pas de manière uniforme à tous les sommets de l'arbre, mais en fonction d'un sommet (ou de la position de la souris sur l'écran) du graphe de départ.

Intuitivement, il s'agit d'utiliser un indice plus petit (moins abstrait) pour les sommets/clusters qui sont à proximité du point d'intérêt , et un indice plus grand dès lors qu'on s'en éloigne.

L'indice est donc cette fois une fonction qui varie en fonction de la distance ( étant fixé).

Les sommets/clusters à proximité du point d'intérêt sont affichés plus finement.La fonction DOA est croissante mais bornée au niveau d'abstraction le plus élevé.

La condition à satisfaire, pour afficher un cluster devient donc:

La seule condition imposée sur la fonction DOA est sa croissance sur . On peut prendre une fonction croissante et linéaire par morceaux, ou quadratique, cubique, etc. —

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/focus_context_clustering_de_van_ham_van_wijk.txt · Last modified: 2016/05/24 16:37 by melancon