A mean shift algorithm incorporating reachable distance for spatial clustering

• Published in: Information sciences 2025-01, Vol.689, p.121456, Article 121456
• Main Authors: Peng, Youwei, Luo, Yalan, Zhang, Qiongbing, Xie, Chengwang
• Format: Article
• Language: English
• Subjects: Cluster center iteration mechanism; Geographical accessibility; Mean shift algorithm; Spatial clustering
• ISSN: 0020-0255
• DOI: 10.1016/j.ins.2024.121456

Spatial clustering is a widely used technique in spatial analysis that groups similar objects together based on their proximity in space. However, traditional clustering algorithms often fail to ensure the accessibility of cluster centers, which limits their validity in practical applications such as facility location problems. To address this issue, this article introduces a novel Mean Shift algorithm that incorporates reachable distance and an iterative mechanism to accurately locate cluster centers. The proposed algorithm initially labels clustering elements with road network coordinates to facilitate the calculation of reachable distance and the cluster center iterative mechanism. Subsequently, the mean shift vector function is modified to employ reachable distance as the measure of geographic reachable similarity. Unlike existing algorithms, our approach allows for cluster centers to be positioned independently of the clustering elements, guaranteeing geographical accessibility. Through simulation experiments, we demonstrate that our proposed algorithm not only outperforms existing methods in terms of solution quality, but also effectively addresses the limitations of disregarding geographical obstacles and unreachable cluster centers.