Robust distance-based clustering with applications to spatial data mining

In this paper we present a method for clustering gee-referenced data suitab le for applications in spatial data mining, based on the medoid method. The medoid method is related to k-MEANS, With the restriction that cluster rep resentatives be chosen from among the data elements. Although the medoid me thod in general produces clusters of high quality, especially in the presen ce of noise, it is often criticized for the Omega (n(2)) time that it requi res. Our method incorporates both proximity and density information to achieve h igh-quality clusters in sub-quadratic time; it does not require that the us er specify the number of clusters in advance. The time bound is achieved by means of a fast approximation to the medoid objective function, using Dela unay triangulations to store proximity information.