Visualization of cluster hierarchies
Bjoern Heckel, Bernd Hamann · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1998
Clustering is a powerful analysis technique used to detect structures in data sets. The output of a clustering process can be very large. However, if presented in a textual form, the amount of information that can be understood is limited. An alternative approach is to display the data in a graphical way. An advantage of visualization is that a larger amount of information can be perceived. Supporting user interaction and manipulation of the object space enables exploration of large data sets. We present a technique for the visualization of cluster hierarchies. The input to our technique is a finite set of n-dimensional points. All points are initially placed in one cluster, which is recursively split, creating a hierarchy of clusters. Principal component analysis is used to determine how to optimally bisect a cluster. After splitting a cluster, a local reclassification scheme based on the Gabriel graph is applied to improve the quality of the classification. As a byproduct of the generation of the cluster hierarchy, we compute and store the eigendirections, eigenvalues and local centers for each cluster at each level of the hierarchy. For the visualization of the cluster hierarchy, the user has to specify the three dimensions that are used for the rendering process. The local coordinate systems (centroids, eigenvalues, and eigendirections) of each cluster induce a local metric that can be utilized to define 'density functions.' These functions describe hyperellipsoids that we render in two different ways: (1) we generate a set of (transparent) contour surfaces (each cluster would appear as a translucent surface) or (2) we apply 'ray casting' to simulate the behavior of X-rays penetrating the density fields implied by the clusters. In order to show the different levels in the hierarchy, one can either render only those clusters belonging to the same level or, alternatively, use transparency to abe able to see through the 'outer shell' of a cluster and see the finer, more detailed structures inside.