Multi-rank Sparse Hierarchical Clustering

Hongyang Zhang, Ruben H. Zamar

Abstract

There has been a surge in the number of large and flat data sets—data sets containing a large number of features and a relatively small number of observations—due to the growing ability to collect and store information in medical research and other fields. Hierarchical clustering is a widely used clustering tool. In hierarchical clustering, large and flat data sets may allow for a better coverage of clustering features (features that help explain the true underlying clusters) but, such data sets usually include a large fraction of noise features (non-clustering features) that may hide the underlying clusters. Witten and Tibshirani (2010) proposed a sparse hierarchical clustering framework to cluster the observations using an adaptively chosen subset of the features, however, we show that this framework has some limitations when the data sets contain clustering features with complex structure. In this paper, we propose the Multi-rank sparse hierarchical clustering (MrSHC). We show that, using simulation studies and real data examples, MrSHC produces superior feature selection and clustering performance comparing to the classical (of-the-shelf) hierarchical clustering and the existing sparse hierarchical clustering framework.

TL;DR

Researchers have developed Multi-rank Sparse Hierarchical Clustering (MrSHC), a new framework that improves how we find patterns in "large and flat" datasets—those with thousands of features but few observations. By moving beyond simple rank-1 approximations and applying sparse principal component analysis directly to raw data, MrSHC identifies complex cluster structures that previous methods miss, while simultaneously filtering out irrelevant noise.

What Problem Does This Paper Address?

In fields like genomics and medical research, scientists often deal with "large and flat" data: imagine a spreadsheet with 5,000 columns (gene expressions) but only 50 rows (patients). Standard hierarchical clustering (HC) struggles here because most of those 5,000 features are just "noise"—they don't actually help distinguish between different types of diseases. This noise can drown out the true signal, leading to incorrect clusters.

Table illustrating informative clustering features versus noise features across different observation groups.

While previous work (notably Witten and Tibshirani in 2010) introduced "sparse" clustering to pick out only the relevant features, it relied on a "rank-1" approximation. This assumes that the cluster structure can be explained by a single pattern of variation. However, real-world data is often more complex; different groups of features might define different sub-clusters. The authors address this "complexity gap" by allowing the model to look at multiple ranks (multiple patterns of variation) simultaneously.

Methods

MrSHC introduces three significant departures from the previous state-of-the-art:

  1. Direct Application of SPC: Instead of transforming the data into a massive $n^2 \times p$ dissimilarity matrix (which is computationally expensive), MrSHC applies Sparse Principal Component Analysis (SPC) directly to the original data matrix $X$.
  2. Multi-Rank Approximation: Unlike previous methods that only look at the first sparse principal component, MrSHC considers the first $r$ sparse PCs. A feature is selected if it has a non-zero loading in any of these $r$ components. This allows the model to capture multifaceted cluster structures.
  3. Indicator Weights: The method uses "indicator weights" (assigning a weight of 1 to selected features and 0 to others) rather than continuous weights. This makes the results easier to interpret and allows the algorithm to behave like classical hierarchical clustering when no sparsity is required.

The paper also provides automated algorithms to select the optimal number of features ($q$) and the appropriate rank ($r$) using techniques like Gap statistics and silhouette values to measure cluster separation.

Datasets

The authors evaluated MrSHC using both synthetic and real-world high-dimensional data:

  • Simulated Datasets: Two complex simulation scenarios where clusters were defined by specific subsets of features with varying means and variances.
  • Lymphoma Microarray Data (Dettling, 2004): 4,026 gene expression levels for 62 samples across three tumor types.
  • Breast Cancer Microarray Data (Perou et al., 2000): 1,753 features for 62 samples across four tumor groups.
  • Breast Cancer Microarray Data (van’t Veer et al., 2002): 4,751 features for 77 samples, used to predict clinical outcomes.

Key Insights and Ideas

  • The Rank-1 Trap: The "aha moment" of the paper is the demonstration that a single sparse principal component often isn't enough. If Cluster A is defined by Genes 1-10 and Cluster B is defined by Genes 11-20, a rank-1 model might only pick up one set, leading to a messy, mixed-up dendrogram.
  • Efficiency through Sparsity: By applying SPC directly to the data matrix $X$, the authors found that MrSHC is actually more computationally efficient than previous sparse methods as the number of features ($p$) grows very large, because it avoids the quadratic scaling of dissimilarity-based approaches.

Key Results

  • Superior Accuracy: In simulations, MrSHC achieved a Classification Error Rate (CER) as low as 0.009, compared to 0.047 for existing sparse methods and 0.202 for standard hierarchical clustering.
  • Better Feature Recall: MrSHC consistently identified nearly 100% of the "true" clustering features, whereas previous methods often selected several noise features before finding all the relevant ones.
  • Real-World Performance: On the Dettling Lymphoma dataset, MrSHC correctly separated clusters that both standard HC and the 2010 sparse framework mixed together. It achieved better accuracy using a rank-2 approximation, proving that the "multi-rank" approach is necessary for biological data.
Example dendrogram showing the hierarchical grouping of observations achieved through clustering.

Limitations and Future Work

The authors identify a few areas for improvement. The current framework assumes relatively "clean" data and does not yet have built-in mechanisms to handle significant outliers or missing data points. Future directions include endowing MrSHC with the capability of dealing with data contamination, making it more robust for messy, real-world clinical datasets.

Summary updated

Abstract

There has been a surge in the number of large and flat data sets - data sets containing a large number of features and a relatively small number of observations - due to the growing ability to collect and store information in medical research and other fields. Hierarchical clustering is a widely used clustering tool. In hierarchical clustering, large and flat data sets may allow for a better coverage of clustering features (features that help explain the true underlying clusters) but, such data sets usually include a large fraction of noise features (non-clustering features) that may hide the underlying clusters. Witten and Tibshirani (2010) proposed a sparse hierarchical clustering framework to cluster the observations using an adaptively chosen subset of the features, however, we show that this framework has some limitations when the data sets contain clustering features with complex structure. In this paper, we propose the Multi-rank sparse hierarchical clustering (MrSHC). We show that, using simulation studies and real data examples, MrSHC produces superior feature selection and clustering performance comparing to the classical (of-the-shelf) hierarchical clustering and the existing sparse hierarchical clustering framework.
BibTeX
@misc{zhang2014multi,
  author = {Hongyang Zhang and Ruben H. Zamar},
  title = {{Multi-rank Sparse Hierarchical Clustering}},
  year = {2014},
  eprint = {1409.0745},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1409.0745},
}

Loading related content...

Figure