CLARANS: a method for clustering objects for spatial data mining

TLDR

Spatial data mining discovers implicit relationships and characteristics within spatial databases. The paper presents three contributions: a new clustering method CLARANS, its extension to polygon objects, and two algorithms for mining spatial–nonspatial attribute relationships. CLARANS clusters point and polygon objects, and the authors build two spatial data mining algorithms atop it. Experiments show CLARANS is more efficient and effective than existing methods, the IR‑approximation efficiently clusters convex and nonconvex polygons, and the two algorithms uncover knowledge difficult to find with current techniques.

Abstract

Spatial data mining is the discovery of interesting relationships and characteristics that may exist implicitly in spatial databases. To this end, this paper has three main contributions. First, it proposes a new clustering method called CLARANS, whose aim is to identify spatial structures that may be present in the data. Experimental results indicate that, when compared with existing clustering methods, CLARANS is very efficient and effective. Second, the paper investigates how CLARANS can handle not only point objects, but also polygon objects efficiently. One of the methods considered, called the IR-approximation, is very efficient in clustering convex and nonconvex polygon objects. Third, building on top of CLARANS, the paper develops two spatial data mining algorithms that aim to discover relationships between spatial and nonspatial attributes. Both algorithms can discover knowledge that is difficult to find with existing spatial data mining algorithms.