Discovering and Visualizing Hierarchy in Multivariate Data

Kun Yang, Wing Hung WongarXiv 2014 · DOI · arXiv

Abstract

How to extract useful insights from data is always a challenge, especially if the data is multidimensional. Often, the data can be organized according to certain hierarchical structure that are stemmed either from data collection process or from the information and phenomena carried by the data itself. The current study attempts to discover and visualize these underlying hierarchies. By regarding each observation in the data as a draw from a (hypothetical) multidimensional joint density, our first goal is to approximate this unknown density with a piecewise constant function via binary partition, our non-parametric approach makes no assumptions on the form of the density. Given the piecewise constant density function and its corresponding binary partition, our second goal is to construct a connected graph and build up a tree representation of the data by level sets. To demonstrate that our method is a general data mining and visualization tool which can provide "multi-resolution" summaries and reveal different levels of information of the data, we apply it to two real data sets from Flow Cytometry and Social Network.

Introduction

As datasets grow in dimensionality and complexity, traditional visualization and clustering methods often struggle to capture inherent hierarchical structures. For instance, biological data may represent a lineage of cell differentiation, while social data organizes from individual interactions to broad communities.

Existing techniques like Kernel Density Estimation (KDE) frequently suffer from "local bumps"—minor fluctuations in density that create a noisy, overly complex representation. Furthermore, many clustering algorithms require users to pre-specify the number of clusters or fail when dealing with highly asymmetric populations. This research introduces a non-parametric framework designed to uncover these hidden hierarchies efficiently while remaining robust to noise.

Methodology

The proposed framework utilizes a two-step approach to transform raw multivariate data into a structured hierarchy.

1. Binary Partition by Discrepancy

Instead of assuming a specific distribution (such as Gaussian), the method divides the multidimensional space into hypercubes. Using a "discrepancy" criterion borrowed from Quasi-Monte Carlo methods, the algorithm tests if data points within a cube are uniformly distributed. If they are not, the cube is split at the location of the largest "gap." This process results in a piecewise constant density estimate, where density is defined as the number of points in a sub-cube divided by its volume.

Comparison of raw data distribution (left) and the resulting piecewise constant density estimate via binary partitioning (right).

2. Level-Set Trees

Once the density is estimated, the hierarchy is revealed through "level sets"—regions where the density exceeds a specific threshold $\eta$. As this threshold is gradually lowered, distinct dense regions (modes) begin to merge. This merging process naturally defines a tree structure representing the data's hierarchy. By using a piecewise constant approach, the method effectively "smooths" minor fluctuations, producing a cleaner tree that captures the core structural features rather than sampling noise.

Conceptual illustration of level-set tree construction: horizontal thresholds (A-E) identify modes and their hierarchical merging points.

Applications and Key Results

The researchers validated the method across diverse domains, including simulated Gaussian mixtures and real-world social and biological networks:

  • Flow Cytometry: In a dataset of ~380,000 mouse bone marrow cells, the algorithm successfully identified 13 sub-populations. It correctly mapped their biological hierarchy, such as initial splits based on the CD11b marker followed by B220 and TCR-$\beta$ differentiation.
  • Social Network Analysis: When applied to the classic dolphin social network, the method identified primary communities and highlighted specific individuals (e.g., dolphin "SN100") as critical transitional nodes between groups.
  • Computational Efficiency: With a complexity of $O(l \cdot n \log^{d-1} n)$, the algorithm remains tractable for large-scale datasets that often overwhelm more complex topological methods.

Conclusion

This non-parametric framework provides a robust "multi-resolution" summary of high-dimensional data. By bridging the gap between density estimation and network analysis, it offers a powerful tool for feature extraction and structural discovery. Future work may extend this mode-seeking logic to image segmentation, where hierarchical trees could represent varying levels of visual detail.

Summary updated

Abstract

How to extract useful insights from data is always a challenge, especially if the data is multidimensional. Often, the data can be organized according to certain hierarchical structure that are stemmed either from data collection process or from the information and phenomena carried by the data itself. The current study attempts to discover and visualize these underlying hierarchies. By regarding each observation in the data as a draw from a (hypothetical) multidimensional joint density, our first goal is to approximate this unknown density with a piecewise constant function via binary partition, our non-parametric approach makes no assumptions on the form of the density. Given the piecewise constant density function and its corresponding binary partition, our second goal is to construct a connected graph and build up a tree representation of the data by level sets. To demonstrate that our method is a general data mining and visualization tool which can provide "multi-resolution" summaries and reveal different levels of information of the data, we apply it to two real data sets from Flow Cytometry and Social Network.
BibTeX
@misc{yang2014discovering,
  author = {Kun Yang and Wing Hung Wong},
  title = {{Discovering and Visualizing Hierarchy in Multivariate Data}},
  year = {2014},
  eprint = {1403.4370},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1403.4370},
}
Figure