A clustering procedure based on the comparison between the k nearest neighbors graph and the mininial 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, G(k), and the minimal spanning tree, MST. Our key statistic is the random quantity (k) over tilde := the smallest k such that G(k) Contains the MST. Under regularity assumptions, we show that for i.i.d. data from a density on R-d with compact support having one connected component, (k) over tilde = O-Pr(log n), 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. (C) 2003 Elsevier Science B.V. All rights reserved.