Paper detail

Stability of Density-Based Clustering

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 $λ\geq 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{\cal{T}}$ 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{\cal{T}}$ as a function of $h$, and investigate the theoretical properties of these instability measures.