A clustering procedure based on the comparison between the k nearest neighbors graph and the minimal spanning tree

We present a procedure for the identification of clusters in multivariate data sets, based on the comparison between the k nearest neighbors graph, Gk, and the minimal spanning tree, MST. Our key statistic is the random quantity the smallest k such that Gk contains the MST. Under regularity assumptions, we show that for i.i.d. data from a density on with compact support having one connected component, , where n denotes sample size, a bound that seems to be sharp, according to simulations. This leads to a consistent test for the identification of crisp clusters. We illustrate the use of our procedure with an example.