A method for efficient clustering of spatial data in network space
Authors:
- 21 June 2021
- journal article
- research article
- Published by SAGE Publications in Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology
- Vol. 40 (6) , 11653-11670
Abstract
Spatial clustering is one of the main techniques for spatial data mining and spatial data analysis. However, existing spatial clustering methods primarily focus on points distributed in planar space with the Euclidean distance measurement. Recently, NS-DBSCAN has been developed to perform clustering of spatial point events in Network Space based on a well-known clustering algorithm, named Density-Based Spatial Clustering of Applications with Noise (DBSCAN). The NS-DBSCAN algorithm has efficiently solved the problem of clustering network constrained spatial points. When compared to the NC_DT (Network-Constraint Delaunay Triangulation) clustering algorithm, the NS-DBSCAN algorithm efficiently solves the problem of clustering network constrained spatial points by visualizing the intrinsic clustering structure of spatial data by constructing density ordering charts. However, the main drawback of this algorithm is when the data are processed, objects that are not specifically categorized into types of clusters cannot be removed, which is undeniably a waste of time, particularly when the dataset is large. In an attempt to have this algorithm work with great efficiency, we thus recommend removing edges that are longer than the threshold and eliminating low-density points from the density ordering table when forming clusters and also take other effective techniques into consideration. In this paper, we develop a theorem to determine the maximum length of an edge in a road segment. Based on this theorem, an algorithm is proposed to greatly improve the performance of the density-based clustering algorithm in network space (NS-DBSCAN). Experiments using our proposed algorithm carried out in collaboration with Ho Chi Minh City, Vietnam yield the same results but shows an advantage of it over NS-DBSCAN in execution time.Keywords
This publication has 22 references indexed in Scilit:
- Essentials of the self-organizing mapNeural Networks, 2013
- A density-based spatial clustering algorithm considering both spatial proximity and attribute similarityComputers & Geosciences, 2012
- How Good is Volunteered Geographical Information? A Comparative Study of OpenStreetMap and Ordnance Survey DatasetsEnvironment and Planning B: Planning and Design, 2010
- A simple and fast algorithm for K-medoids clusteringExpert Systems with Applications, 2009
- ST-DBSCAN: An algorithm for clustering spatial–temporal dataData & Knowledge Engineering, 2007
- CLARANS: a method for clustering objects for spatial data miningIEEE Transactions on Knowledge and Data Engineering, 2002
- WaveCluster: a wavelet-based clustering approach for spatial data in very large databasesThe VLDB Journal, 2000
- OPTICSACM SIGMOD Record, 1999
- The expectation-maximization algorithmIEEE Signal Processing Magazine, 1996
- BIRCHACM SIGMOD Record, 1996