Stability of Density-Based Clustering

2010/11/11 by Alessandro Rinaldo, Rinaldo, Alessandro, Aarti Singh +5 · 2 citations
Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Statistics Theory (math.ST) #math.ST #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.1011.2771

arxiv created 2010/11/11 · arxiv updated 2010/11/15

Abstract

High density clusters can be characterized by the connected components of a level set L(λ) = \x: p(x)>λ\ of the underlying probability density function p generating the data, at some appropriate level λ≥ 0. The complete hierarchical clustering can be characterized by a cluster tree \cal T= \bigcup_λ L(λ). In this paper, we study the behavior of a density level set estimate \widehat L(λ) and cluster tree estimate \widehat\calT based on a kernel density estimator with kernel bandwidth h. We define two notions of instability to measure the variability of \widehat L(λ) and \widehat\calT as a function of h, and investigate the theoretical properties of these instability measures.

Cited by

• Why does Greedy Search produce Optimal Clustering Outcomes? A Fixed-Core Assignment Theory
• Adaptive Geometric Regression for High-Dimensional Structured Data

Related

• Adaptive Clustering Using Kernel Density Estimators
• Consistent procedures for cluster tree estimation and pruning
• DBSCAN: Optimal Rates For Density Based Clustering
• Clustering with Confidence: Finding Clusters with Statistical Guarantees
• Estimating the Number of Clusters via Normalized Cluster Instability