Spatial clustering in the presence of obstacles

TLDR

Clustering in spatial data mining groups similar objects by distance, connectivity, or density, but real‑world obstacles such as rivers, lakes, and highways can substantially alter results, and the COD problem can be viewed as a modified distance function that existing algorithms could handle. The authors aim to address clustering with obstacles by defining the COD problem and proposing the scalable COD‑CLARANS algorithm. COD‑CLARANS is a scalable clustering algorithm that incorporates pre‑processed obstacle information and a pruning function E′ to improve efficiency. Performance studies demonstrate that COD‑CLARANS is both efficient and effective, achieving greater optimization through its pruning function E′ compared to abstracting obstacles at the distance‑function level.

Abstract

Clustering in spatial data mining is to group similar objects based on their distance, connectivity, or their relative density in space. In the real world there exist many physical obstacles such as rivers, lakes and highways, and their presence may affect the result of clustering substantially. We study the problem of clustering in the presence of obstacles and define it as a COD (Clustering with Obstructed Distance) problem. As a solution to this problem, we propose a scalable clustering algorithm, called COD-CLARANS. We discuss various forms of pre-processed information that could enhance the efficiency of COD-CLARANS. In the strictest sense, the COD problem can be treated as a change in distance function and thus could be handled by current clustering algorithms by changing the distance function. However, we show that by pushing the task of handling obstacles into COD-CLARANS instead of abstracting it at the distance function level, more optimization can be done in the form of a pruning function E'. We conduct various performance studies to show that COD-CLARANS is both efficient and effective.