PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistical Significance for Hierarchical Clustering

Patrick K. Kimes, Yufeng Liu, D. Neil Hayes, J. S. Marron

arXiv:1411.5259v1stat.ME

TL;DR

Hierarchical clustering makes nested structure visible, but determining which clusters are statistically meaningful is complicated by the tree and multiple testing. The paper introduces SHC, a Monte Carlo sequential testing procedure for hierarchical clustering. Theoretical results show valid null p-values and family-wise error-rate control, while the method detects separated Gaussian-mixture structure asymptotically.

  • Problem

    Researchers need statistically grounded ways to distinguish meaningful hierarchical clusters from sampling variation, but existing significance testing is limited by nested tree structure and multiple testing.

  • Method

    SHC performs Monte Carlo hypothesis tests at dendrogram nodes using subtree-specific null Gaussians and a sequential procedure for family-wise error-rate control.

  • Results

    Under the null, the SHC empirical p-value follows U(0, 1), while under the stated Gaussian-mixture conditions it tends to 0 and the FWER cutoff procedure controls the desired level α.

  • Takeaways & Limitations

    SHC provides a statistically justified approach for assessing significance along hierarchical partitions, including in high-dimension low-sample-size settings.

  • Takeaways & Limitations

    SHC requires estimating each subtree’s null Gaussian and assumes a factor-analysis covariance model, which is motivated by the difficulty of covariance estimation in HDLSS data.

Abstract

from arXiv · show

Cluster analysis has proved to be an invaluable tool for the exploratory and unsupervised analysis of high dimensional datasets. Among methods for clustering, hierarchical approaches have enjoyed substantial popularity in genomics and other fields for their ability to simultaneously uncover multiple layers of clustering structure. A critical and challenging question in cluster analysis is whether the identified clusters represent important underlying structure or are artifacts of natural sampling variation. Few approaches have been proposed for addressing this problem in the context of hierarchical clustering, for which the problem is further complicated by the natural tree structure of the partition, and the multiplicity of tests required to parse the layers of nested clusters. In this paper, we propose a Monte Carlo based approach for testing statistical significance in hierarchical clustering which addresses these issues. The approach is implemented as a sequential testing procedure guaranteeing control of the family-wise error rate. Theoretical justification is provided for our approach, and its power to detect true clustering structure is illustrated through several simulation studies and applications to two cancer gene expression datasets.

1 INTRODUCTION

Hierarchical clustering reveals nested relationships without pre-specifying the number of clusters, but researchers still need statistically grounded ways to identify meaningful partitions. SHC addresses this gap with Monte Carlo node-wise tests designed for nested hierarchies and high-dimensional, low-sample-size data.

  • Hierarchical clustering produces a nested hierarchy from which a partition can be obtained for any feasible number of clusters.
  • Dendrograms provide an informative binary-tree visualization, but researchers must still decide which partitions represent biologically important subpopulation differences.
  • SHC uses Monte Carlo hypothesis tests and the ordered, nested tree structure to assess clustering significance through a sequence of tests.
  • SHC is formulated for application in high-dimension low-sample-size settings, where the number of variables greatly exceeds the number of observations.
  • The paper provides theoretical justification, simulation evaluations, and applications to two cancer gene expression datasets.

2 CLUSTERING AND SIGNIFICANCE

Hierarchical clustering constructs a binary-tree hierarchy through sequentially joining similar clusters, while significance testing evaluates whether observed clustering is stronger than expected under a single-Gaussian null. SigClust addresses non-hierarchical significance testing but relies on a factor-analysis covariance assumption in HDLSS settings.

  • Hierarchical clustering: Agglomerative hierarchical clustering starts with singleton clusters and repeatedly joins the two most similar clusters until all observations form one cluster.
  • Hierarchical clustering: Dissimilarity and linkage choices, including Euclidean distance and Ward’s, single, complete, or average linkage, strongly influence the resulting clusters.
  • Hierarchical clustering: A dendrogram represents the hierarchy as a binary tree, with linkage values marking merges and tree cuts recovering alternative clustering solutions.
  • Statistical significance: SigClust tests whether data follow a single Gaussian distribution versus a non-Gaussian distribution using a 2-means cluster index and simulated null distributions.
  • Statistical significance: Smaller 2-means cluster-index values indicate tighter clusters and stronger evidence of clustering, with empirical p-values based on simulated null indices below the observed value.
  • Statistical significance: In HDLSS settings, SigClust reduces covariance estimation to a factor-analysis model with low-rank signal and background noise.

3 METHODOLOGY

SHC tests selected dendrogram nodes by comparing observed cluster strength with Monte Carlo null distributions fitted to each subtree. It then applies a sequential, hierarchy-aware correction that controls the family-wise error rate while requiring significant nodes to remain connected from the root.

  • SHC Hypothesis Test: SHC performs Monte Carlo hypothesis tests at selected dendrogram nodes to assess whether each subtree represents one or two clusters.
  • SHC Hypothesis Test: At each node, SHC compares observed clustering strength with the same hierarchical algorithm applied to datasets simulated from a null Gaussian fitted to that subtree.
  • SHC Hypothesis Test: The node-level p-value uses linkage value and the 2-means cluster index as measures of clustering strength.
  • SHC Hypothesis Test: SHC assumes a factor-analysis covariance model for the null Gaussian in handling the HDLSS setting.
  • SHC Hypothesis Test: Testing requires a minimum subtree size because the null Gaussian is fitted using only observations within the corresponding subtree.
  • Multiple Testing Correction: The sequential correction starts at the root and requires both a node-specific cutoff and rejection of its parent, producing connected significant nodes and increasingly stringent corrections for smaller subtrees.

4 THEORETICAL DEVELOPMENT

Theoretical results characterize SHC under Gaussian null and mixture alternatives, showing calibrated p-values under the null and asymptotic power under stated conditions.

  • The theoretical analysis uses linkage strength, while simulations subsequently justify alternatively using the 2-means cluster index.
  • Under a single Gaussian null with known covariance, the SHC empirical p-value at the root follows U(0, 1).
  • The same null calibration extends to any dendrogram subtree corresponding to a single Gaussian distribution.
  • Combining subtree calibration with the modified cutoff procedure controls the family-wise error rate at the desired level α.
  • For two spherical Gaussian mixture components, conditions are derived under which Ward’s linkage asymptotically separates the components at the root.
  • Under further assumptions, the SHC empirical root p-value converges to 0 as dimension and sample sizes grow.

5 SIMULATIONS

Simulations compare SHC variants with pvclust across null and multi-cluster Gaussian settings, emphasizing node-specific testing and differing evidence requirements for recovering clusters.

  • SHC combines sequential FWER control with simulation-based tests of hierarchical clustering significance at individual nodes.
  • Simulations compare SHC1 and SHC2 against pvclust using Ward’s linkage on Gaussian mixtures.
  • The evaluated settings include K = 1, K = 2, K = 3, and K = 4, with K = 2 omitted from the main text because it is non-nested.
  • SHC p-values use 100 simulated null cluster indices, whereas pvclust uses 1000 bootstrap samples in the simulations.
  • pvclust reports approximately unbiased and bootstrap-probability p-values, tests nodes along the dendrogram, and performs no root-node test.
  • For three clusters, SHC requires rejecting the null at the top two nodes, whereas pvclust requires rejection at three nodes directly above the clusters.

N w v pvAU pvBP SHC1 SHC2L SHC22 pv SHC1 SHC2L SHC22

Simulations evaluate false-positive control under a null and power to recover three- and four-cluster structures. SHC methods are generally conservative under the null, while SHC22 has the strongest power in multi-cluster settings.

  • Null Setting (K = 1): The null simulations report false positives at α = 0.05, mean p-values, and median computation times across 100 replications.SHC1 and SHC2 summaries use root-node p-values, while pvclust summaries use the second and third nodes from the root.
  • Null Setting (K = 1): Under the single-Gaussian null, simulations used N = 50 and 100 observations in p = 1000 dimensions with diagonal covariance and low-dimensional signal.The first w diagonal entries had signal magnitude v > 1.
  • Null Setting (K = 1): All methods were generally conservative, with pvBP most strongly conservative and pvAU, SHC1, and SHC2 consistently conservative across settings.Under the single-Gaussian null, SHC2 root p-values were expected to be approximately uniform on [0, 1].
  • Three Cluster Setting (K = 3): In three-cluster simulations, pvclust methods had substantially lower power than the three proposed approaches, while SHC22 consistently achieved the greatest power.SHC2L versus SHC1 depended on component arrangement and dimension; SHC2L was also fastest computationally.
  • Four Cluster Setting (K = 4): In four-cluster simulations, pvAU and pvBP again had little power, SHC22 had the greatest power, and SHC2L versus SHC1 depended on arrangement and dimension.For tetrahedral arrangements, SHC2L had substantially greater power than SHC1 in both low- and high-dimensional settings.

6 REAL DATA ANALYSIS

SHC was applied to cancer gene-expression datasets using Ward’s linkage, 1000 simulations per node, and FWER control at α = 0.05. It detected major cancer and breast-cancer subtype separations while limiting further splits that did not meet corrected significance thresholds.

  • 6.1 Multi-Cancer Gene Expression Dataset: The multi-cancer dataset contained 300 tumor samples from HNSC, LUSC, and LUAD, analyzed with Ward’s linkage and SHC22.The analysis used 1000 simulations at each node and controlled the FWER at α = 0.05.
  • 6.2 BRCA Gene Expression Dataset: For the 337-sample BRCA dataset, SHC identified at least three differentiated clusters corresponding primarily to luminal, basal-like, and remaining subtypes.The dataset included 97 LumA, 54 LumB, 91 basal-like, 47 normal breast-like, and 48 HER2-enriched samples.
  • 6.2 BRCA Gene Expression Dataset: LumA and LumB separated from remaining subtypes with p-value 5.72e−4 at threshold α∗336 = 0.05, but SHC found no significant separation between the two luminal subtypes.The difficulty of clustering LumA and LumB by gene expression had been previously described.
  • 6.2 BRCA Gene Expression Dataset: The basal-like group separated from the remaining observations with p-value 0.0172 at cutoff α∗335 = 0.027, whereas a subsequent node was nonsignificant at p-value 0.0293 against α∗j = 0.0180.This illustrates the difficulty of assessing significance with larger numbers of clusters while controlling multiple testing.

7 DISCUSSION

SHC addresses the limited availability of significance methods for hierarchical partitions through sequential testing with FWER control, showing competitive simulations and biologically meaningful clustering in two gene-expression datasets. Its broader applicability is constrained by linkage and dissimilarity choices, especially in high-dimensional settings where covariance estimation may be difficult.

  • SHC uses sequential testing to assess hierarchical partitions while controlling the family-wise error rate.
  • Simulation studies showed that SHC provides competitive results compared with existing methods.
  • Applications to two gene-expression datasets showed that SHC can identify biologically meaningful clustering.
  • The paper’s theoretical and empirical analysis focused on Ward’s linkage, although SHC may support other linkage and dissimilarity functions satisfying mean shift and rotation invariance.
  • For dissimilarities lacking these invariance properties, complete covariance estimation can be difficult and computationally expensive in HDLSS settings.

Proof of Theorem 1

The proof establishes correct root-node separation by bounding the probabilities of three failure events. Each failure probability tends to zero as dimensionality grows, under conditions on the Ward-linkage thresholds.

  • Correct separation follows when within-component Ward linkages remain below thresholds while between-component linkage remains above them.
  • The proof bounds the joint success probability using the complementary probabilities of three failure events.
  • As p →∞, the first two failure probabilities tend to zero when a1 exceeds twice the corresponding component variance.
  • The third failure probability tends to zero under the stated upper bound on a2 derived from component sizes, variances, and mean separation.
  • Combining the necessary inequalities on a1 and a2 yields the theorem’s stated condition.

Proof of Theorem 2

The proof of Theorem 2 compares observed linkage with linkage simulated under a Gaussian null distribution. Under the stated asymptotic conditions, the resulting empirical p-value converges to zero, establishing power at the root node.

  • The null distribution is modeled by a Gaussian with covariance derived from the theoretical best fit to the mixture distribution.
  • Theorem 1 supplies asymptotic correctness of Ward’s partition for the two mixture components.
  • The event D occurs when a null-simulated linkage value is less than the observed linkage value.
  • Consequently, the empirical p-value tends to 0 as p →∞ under the theorem’s asymptotic setting.
  • The proof shows that the probabilities of the fourth and fifth failure events tend to zero as dimensionality grows.

SUPPLEMENTARY MATERIALS

The supplementary materials report simulation results across null, two-cluster, and geometric multi-cluster settings. They summarize detection accuracy or false positives alongside p-values and computation time where specified.

  • Simulation 5.1 reports false positives at α = 0.05, mean p-value, and median computation time over 100 replications.
  • The K = 2 alternative results report replications identifying the correct number of significant clusters, mean p-value, and median computation time.
  • Simulation 5.2 reports correct significant-cluster counts and median computation time for line, triangle, and square arrangements.
  • Simulation 5.3 reports correct significant-cluster counts and median computation time for tetrahedron, rectangle, and stretched tetrahedron arrangements.
Loading 1411.5259v1…