Robust and efficient cluster analysis using a shared near neighbours approach
Irving Hofman, R.A. Jarvis · 2002
A nonparametric method for clustering multidimensional data in O(nlogn) time is described. It is based on the shared near neighbours algorithm. It uses adaptive k-d trees combined with various other sophisticated data structures to significantly decrease the computational complexity of the original algorithm which was O(n/sup 2/). The algorithm is suitable for a wide range of data and capable of delineating clusters of varying shape, density, and homogeneity. A comprehensive set of results is presented.