A Generalized Single Linkage Method for Estimating the Cluster Tree of a Density

The goal of clustering is to detect the presence of distinct groups in a dataset and assign group labels to the observations. Nonparametric clustering is based on the premise that the observations may be regarded as a sample from some underlying density in feature space and that groups correspond to modes of this density. The goal then is to find the modes and assign each observation to the domain of attraction of a mode. The modal structure of a density is summarized by its cluster tree; modes of the density correspond to leaves of the cluster tree. Estimating the cluster tree is the primary goal of nonparametric cluster analysis. We adopt a plug-in approach to cluster tree estimation: estimate the cluster tree of the feature density by the cluster tree of a density estimate. For some density estimates the cluster tree can be computed exactly; for others we have to be content with an approximation. We present a graph-based method that can approximate the cluster tree of any density estimate. Density estimates tend to have spurious modes caused by sampling variability, leading to spurious branches in the graph cluster tree. We propose excess mass as a measure for the size of a branch, reflecting the height of the corresponding peak of the density above the surrounding valley floor as well as its spatial extent. Excess mass can be used as a guide for pruning the graph cluster tree. We point out mathematical and algorithmic connections to single linkage clustering and illustrate our approach on several examples. Supplemental materials for the article, including an R package implementing generalized single linkage clustering, all datasets used in the examples, and R code producing the figures and numerical results, are available online.

• Publication year

  2010

• Venue

  Journal of Computational and Graphical Statistics

• Publication date

  2010-01-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1198/jcgs.2009.07049
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On Potts Model Clustering, Kernel K-Means and Density Estimation

  2008cited by this paper
• MCLUST Version 3 for R: Normal Mixture Modeling and Model-Based Clustering †

  2007cited by this paper
• Algorithms for estimating the cluster tree of a density

  2006influential reference
• MCLUST Version 3: An R Package for Normal Mixture Modeling and Model-Based Clustering

  2006cited by this paper
• Algorithms for manipulation of level sets of nonparametric density estimates

  2005cited by this paper
• Visualization of Multivariate Density Estimates With Level Set Trees

  2004cited by this paper
• Estimating the Cluster Tree of a Density by Analyzing the Minimal Spanning Tree of a Sample

  2003influential reference
• Classification, subtype discovery, and prediction of outcome in pediatric acute lymphoblastic leukemia by gene expression profiling.

  2002cited by this paper
• Cluster analysis: a further approach based on density estimation

  2001cited by this paper
• Estimating the number of clusters

  2000influential reference
• Finite Mixture Models

  2000cited by this paper
• OPTICS: ordering points to identify the clustering structure

  1999cited by this paper
• MCLUST: Software for Model-Based Cluster Analysis

  1999cited by this paper
• How Many Clusters? Which Clustering Method? Answers Via Model-Based Cluster Analysis

  1998cited by this paper
• The jackknife and bootstrap

  1996cited by this paper
• A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise

  1996cited by this paper
• Exploratory Projection Pursuit

  1995cited by this paper
• Measuring Mass Concentrations and Estimating Density Contour Clusters-An Excess Mass Approach

  1995cited by this paper
• The runt test for multimodality

  1992cited by this paper
• Excess Mass Estimates and Tests for Multimodality

  1991cited by this paper
• Density Estimation for Statistics and Data Analysis

  1987influential reference
• Estimation of a Convex Density Contour in Two Dimensions

  1987cited by this paper
• PROJECTION PURSUIT DENSITY ESTIMATION

  1984cited by this paper
• Consistency of Single Linkage for High-Density Clusters

  1981cited by this paper
• Clustering Algorithms

  1975cited by this paper
• FINDING NATURAL CLUSTERS

  1968cited by this paper

• Generalization of single-linkage with higher-order interactions

  2026cites this paper
• GeoAI-driven analysis of urban activity shifts using geotagged social media data across the COVID-19 pandemic

  2025cites this paper
• A Multi-Stage Clustering Framework for Track-to-Track-Association

  2025cites this paper
• Robust Automated Operational Modal Analysis Framework Based on Enhanced Stabilization Diagram and Hierarchical Density Estimation

  2025cites this paper
• Modal Clustering for Categorical Data

  2025cites this paper
• Nested Gaussian mixture model: clustering data from generalized mixture distributions

  2025cites this paper
• Persistent Multiscale Density-based Clustering

  2025cites this paper
• Model-free Estimation of Latent Structure via Multiscale Nonparametric Maximum Likelihood

  2024cites this paper
• A fresh look at mean-shift based modal clustering

  2023cites this paper
• Beta-trees: Multivariate histograms with confidence statements

  2023cites this paper
• Directional density-based clustering

  2023influential citation
• DFSP: A fast and automatic distance field-based stem-leaf segmentation pipeline for point cloud of maize shoot

  2023cites this paper
• A divisive hierarchical clustering methodology for enhancing the ensemble prediction power in large scale population studies: the ATHLOS project

  2022cites this paper
• Fitting a Multi-modal Density by Dynamic Programming

  2022cites this paper
• Skeleton Clustering: Graph-Based Approach for Dimension-Free Density-Aided Clustering

  2022cites this paper
• Locally Adaptive Hierarchical Cluster Termination With Application To Individual Tree Delineation

  2022cites this paper
• Modal Clustering Using Semiparametric Mixtures and Mode Flattening

  2021cites this paper
• An Asymptotic Equivalence between the Mean-Shift Algorithm and the Cluster Tree

  2021cites this paper
• Level Sets or Gradient Lines? A Unifying View of Modal Clustering

  2021cites this paper
• An empirically sound telemedicine taxonomy – applying the CAFE methodology

  2021influential citation
• Determinantal consensus clustering

  2021cites this paper
• Mapping Chemical Structure–Glass Transition Temperature Relationship through Artificial Intelligence

  2021cites this paper
• Skeleton Clustering: Dimension-Free Density-Aided Clustering

  2021cites this paper
• Skeleton Clustering: Dimension-Free Density-based Clustering

  2021cites this paper
• An Effective Clustering Method Based on Shared Nearest Neighbors and Graph

  2021cites this paper
• A Hybrid Machine Learning Framework for Enhancing the Prediction Power in Large Scale Population Studies: TheATHLOS Project

  2021cites this paper
• Moving Up the Cluster Tree with the Gradient Flow

  2021cites this paper
• Locally Persistent Categories And Metric Properties Of Interleaving Distances

  2020cites this paper
• Nonparametric estimation of directional highest density regions

  2020cites this paper
• Tree based credible set estimation

  2020cites this paper
• Stable and consistent density-based clustering

  2020cites this paper
• KMD clustering: robust general-purpose clustering of biological data

  2020cites this paper
• Stable and consistent density-based clustering via multiparameter persistence

  2020influential citation
• Nonparametric density estimation for high‐dimensional data—Algorithms and applications

  2019cites this paper
• Nonparametric clustering for image segmentation

  2019cites this paper
• Hierarchical Density-Based Clustering Using MapReduce

  2019cites this paper
• PPCI: an R Package for Cluster Identification using Projection Pursuit

  2019cites this paper
• Characterizing Flaring from Unconventional Oil and Gas Operations in South Texas Using Satellite Observations.

  2019cites this paper
• Clustering Large Datasets by Merging K-Means Solutions

  2019cites this paper
• Similarity of Continuous Optimization Problems from the Algorithm Performance Perspective

  2019cites this paper
• Vegetable Production Efficiency of Smallholders’ Farmer in West Shewa Zone of Oromia National Regional State, Ethiopia

  2019cites this paper
• Three-dimensional Radial Visualization of High-dimensional Continuous or Discrete Data

  2019cites this paper
• Level set tree methods

  2018cites this paper
• Heart Disease Diagnosis via Nonparametric Mixture Models

  2018cites this paper
• Low-Density Cluster Separators for Large, High-Dimensional, Mixed and Non-Linearly Separable Data.

  2018cites this paper
• Kernel-estimated Nonparametric Overlap-Based Syncytial Clustering

  2018influential citation
• Overcoming the Curse of Dimensionality When Clustering Multivariate Volume Data

  2018cites this paper
• A geodesic distance‐based approach for shape‐independent data clustering using coalitional game

  2018cites this paper
• Building cancer prognosis systems with survival function clusters

  2018influential citation
• Upsampling for Improved Multidimensional Attribute Space Clustering of Multifield Data

  2018cites this paper
• A Novel Hierarchical Clustering Algorithm Based on Density Peaks for Complex Datasets

  2018cites this paper
• Selective Clustering Annotated using Modes of Projections

  2018cites this paper
• Cardiorespiratory instability in monitored step-down unit patients: using cluster analysis to identify patterns of change

  2018cites this paper
• A Modularity-Based Measure for Cluster Selection from Clustering Hierarchies

  2018cites this paper
• DBSCAN: Optimal Rates For Density Based Clustering

  2017cites this paper
• Optimal Rates for Cluster Tree Estimation using Kernel Density Estimators

  2017cites this paper
• Estimation of level set trees using adaptive partitions

  2017influential citation
• Measuring Sustainable Competitiveness in Contemporary Economies—Insights from European Economy

  2017cites this paper
• Merging K‐means with hierarchical clustering for identifying general‐shaped groups

  2017influential citation
• Density Level Set Estimation on Manifolds with DBSCAN

  2017cites this paper
• Distance and density based clustering algorithm using Gaussian kernel

  2017cites this paper
• Accelerated Hierarchical Density Based Clustering

  2017cites this paper
• Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph

  2017cites this paper
• Some contributions to k-means clustering problems

  2017cites this paper
• DBSCAN: Optimal Rates For Density-Based Cluster Estimation

  2017cites this paper
• Intrinsic Metrics: Exact Equality between a Geodesic Metric and a Graph metric

  2017cites this paper
• Adaptive Clustering Using Kernel Density Estimators

  2017cites this paper
• Machine Learning using Principal Manifolds and Mode Seeking

  2016cites this paper
• Statistical Inference for Cluster Trees

  2016cites this paper
• Estimation of level set trees using adaptive partitions

  2016cites this paper
• Tools and Techniques in Plant Ecology-A review

  2016cites this paper
• densityCut: an efficient and versatile topological approach for automatic clustering of biological data

  2016cites this paper
• Density-based clustering with non-continuous data

  2016cites this paper
• A Review on Modal Clustering

  2016influential citation
• Projection methods for clustering and semi-supervised classification

  2016influential citation
• Modal-set estimation with an application to clustering

  2016cites this paper
• Identifying connected components in Gaussian finite mixture models for clustering

  2016cites this paper
• Divisive clustering of high dimensional data streams

  2015cites this paper
• Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection

  2015cites this paper
• 1-2012 Stability of Density-Based Clustering

  2015cites this paper
• Minimum Density Hyperplane: An Unsupervised and Semi-Supervised Classifier

  2015cites this paper
• Some Insights About the Small Ball Probability Factorization for Hilbert Random Elements

  2015cites this paper
• Minimum Density Hyperplanes

  2015cites this paper
• Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering

  2015cites this paper
• TOBAE: A Density-based Agglomerative Clustering Algorithm

  2015cites this paper
• A simple statistics-based nearest neighbor cluster detection algorithm

  2015cites this paper
• Density Level Sets: Asymptotics, Inference, and Visualization

  2015cites this paper
• Recent Developments in Model-Based Clustering with Applications

  2015cites this paper
• A clustering method for Hilbert functional data based on the Small Ball Probability

  2015cites this paper
• Fully Adaptive Density-Based Clustering

  2014cites this paper
• The Conditional-Potts Clustering Model

  2014cites this paper
• The functional mean-shift algorithm for mode hunting and clustering in infinite dimensions

  2014cites this paper
• Approximating Hierarchical MV-sets for Hierarchical Clustering

  2014influential citation
• Hierarchical unsupervised nonparametric classification of polarimetric SAR time series data

  2014cites this paper
• Consistent Procedures for Cluster Tree Estimation and Pruning

  2014cites this paper
• Statistical Inference for Topological Data Analysis

  2014cites this paper
• Comparison of similarity coefficients and clustering methods with amplified fragment length polymorphism markers in Colletotrichum gloeosporioides isolates from yam Ojurongbe

  2014cites this paper
• Analysis of forensic DNA mixtures with artefacts

  2013cites this paper
• A framework for semi-supervised and unsupervised optimal extraction of clusters from hierarchies

  2013influential citation
• Clustering via Nonparametric Density Estimation: The R Package pdfCluster

  2013cites this paper