Clustertree

Clustertree, or cluster tree, is a tree-structured representation of clusterings that captures the nested relationships among groups of data points across multiple scales. It is commonly used to summarize the results of hierarchical clustering and to support exploratory analysis of how clusters emerge and merge as the resolution changes.

A clustertree can be derived from a dendrogram produced by hierarchical clustering, interpreting each node as a cluster at a given cut level and linking clusters to their subclusters as children. Leaves typically correspond to individual data points, while the root represents the full dataset at the coarsest granularity. Alternatively, in density-based or topological approaches, clustertrees are formed by tracking the connected components of sublevel sets of a density function as the threshold varies, yielding a merge tree that encodes how components appear and join across densities.

Structure and attributes of a clustertree vary by construction but often include in each node the cluster size, a representative statistic (such as a centroid or medoid), and the threshold or level at which the cluster is formed. Edges reflect parent–child or merge relationships, enabling navigation from coarse clusters to finer subclusters. The tree provides a compact summary of hierarchical structure and supports efficient queries about cluster membership and ancestry.

Applications include data exploration and visualization, indexing and fast membership checks, stability analysis of clusters, and informing downstream tasks such as classification or anomaly detection. Related concepts include dendrograms and merge trees; in some settings a clustertree is functionally equivalent to a dendrogram, while in others it emphasizes the topological or multi-scale aspects of clustering.

Limitations involve sensitivity to distance metrics and scaling, potential noise impact, and growth in size for large datasets. Practical use often involves pruning, summarization, or selecting representative subtrees to maintain interpretability.