H-BLOB: a hierarchical visual clustering method using implicit surfaces

Abstract

We present a new hierarchical clustering and visualization algorithm called H-BLOB, which groups and visualizes cluster hierarchies at multiple levels-of-detail. Our method is fundamentally different to conventional clustering algorithms, such as C-means, K-means, or linkage methods that are primarily designed to partition a collection of objects into subsets sharing similar attributes. These approaches usually lack an efficient level-of-detail strategy that breaks down the visual complexity of very large datasets for visualization. In contrast, our method combines grouping and visualization in a two stage process constructing a hierarchical setting. In the first stage a cluster tree is computed making use of an edge contraction operator. Exploiting the inherent hierarchical structure of this tree, a second stage visualizes the clusters by computing a hierarchy of implicit surfaces. We believe that H-BLOB is especially suited for the visualization of very large datasets and for visual decision making in information visualization. The versatility of the algorithm is demonstrated using examples from visual data mining.