User Tools

Site Tools


Visual Analytics Course

Level of details navigation of hierarchical clusterings

There is a clear consensus about Ben Shneiderman's mantra: 'Overview first, zoom and filter, then details-on-demand'. It makes sense and proves to be an efficient approach. The mantra itself may call for some refinement, but the overall philosophy it promotes is the right one.

Clustering is our answer to building an overview of a dataset. You downsize it, compute chunks of data and decide how these chunks relate to one another. That's what you show the user. He/She then decides on what part of the data is worth diving into. But how abstract must the overview be?

This is what we will be discussing here.

Furnas' DOI

The set of ideas we'll be exploring stem from George Furnas' seminal work:

Furnas, G. W. (1986). Generalized Fisheye Views. Human Factors in Computing Systems CHI '86, ACM Press, 16-23.

Furnas had a very clever idea applied to the visualization and edition of code. Because code is organized into a hierarchy of blocks, why not only show the headings of a block while the user is not interested in having a detailed look at the details of that block. For instance, only showing the name and signature of a function might be enough, showing the first line of a loop might be sufficient to indicate what the loop is performing at that location in the code.

The left figure show a portion of a file. The right figure show the same file where some blocks have been shrunk to a single line. (Click on the images to access an enlarged view.) So the problem we need to solve is to decide what blocks should be shrunk or not. Observe also that blocks residing within a shrunked blocks will not be shown at all.

Now, we may assume the blocks to form a hierarchy, that is they implicitly defined a tree structure . We may also assume the tree implicitly defines the a priori importance of a node in the tree. That is, a leaf node corresponding to a single instruction is of a lesser importance than an ancestor node corresponding to the function containing this line, for instance. As a consequence, the root node has the greatest a priori importance value.

This leads to define the a priori importance function:

so the a priori importance of a node equals minus its distance to the root in the tree.

Now, suppose the user is editing a particular line in the file. This translate into the fact that a node of the tree momentarily becomes a node of interest. Given a node of interest , we call the focus node, we may compute the distance from any other node to this focus node .

The combination of these two functions may now be used to define what is called the degree of interest of a node (with respect to a focus node ):

Observe how the values distribute in the tree. Nodes with higher values either are closer to the focus node, or have relatively high a priori importance.

Next, we need to threshold the DOI values to obtain a partial view of the tree with more details around the focus node.

van Ham and van Wijk' DOA

Furnas' ideas were elegantly extended to work with a hierarchy of clusters for a graph (it may work just as well with a hierarchy of clusters of high-dimensional data). In this tiaution, we are given a tree of clusters where this time nodes of the tree correspond to clusters of a graph . That is, we may think of as a subset of with the additional condition that when is an ancestor of .

Now, we need to compute a value for each node of the tree reflecting its a priori importance. We may think of leaf nodes (elements of ) as having the least a priori importance. What we need is to compute the a priori importance of a cluster obtained from merging sub-clusters. Looking at the whole tree of clusters. What we need is a function that grows along a path going towards the root of the tree. For reasons that will become clear, we require the function to be positive.

  • Recall the Huygens theory we have exposed when looking at high-dimensional data. A good example of what the a priori importance may be is the internal inertia of a cluster. We then have an increasing a priori importance towards the root in virtue of the Huygens theorem.
  • Another example could be to take , as a priori importance of a cluster , the average distance between the two clusters that were merge to obtain .

van Ham and van Wijk define things a bit differently from Furnas, in that they don't directly threshold the values associated with nodes of the tree. They instead define what they call a : degree of abstraction. When selecting a degree of abstraction , what we should get is a total abstraction, that is a single metanode corresponding to the whole dataset. That is indeed, the most abstract view we may have on the dataset. Conversely, when setting we should get the least abstract view possible, that is we should have a view with points on the screen that correspond to data elements themselves. The core procedure is to decide how to vary the selection of clusters when goes from 0 to 1.

The criterion they define to decide whether to show a cluster is the following. Denote as the root node of the tree. They select clusters , with father cluster from the cluster tree whenever we have:

That is, we select clusters whose a priori importance is right above the fraction of the root's a priori importance, but whose father cluster is far too abstract (with respect to the selected threshold).

Varying $DOA$ according to a focus node

Just as with Furnas, we may adapt the previous calculations to select nodes according to their 'distance' to a focus cluster node . The idea is relatively simple, and consists in taking an increasing function instead of a constant and feeding it with the distance to the focal node – measured in whatever appropriate manner. Obviously, we need to require that . Different candidate function are possible:

  • Linear bounded above by 1, that is for and when .
  • Any other non linear function will do, like when and when .

The condition for showing a cluster then becomes the conjunction of two distinct conditions: and . So the selection of clusters depend on the chosen focus point, as well as the way the function deals with distances.

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/level_of_details_navigation_of_hierarchical_clusterings.txt · Last modified: 2012/11/23 13:44 by melancon