SCMDOT: Spatial Clustering with Multiple Density-Ordered Trees
Open Access
- 13 July 2017
- journal article
- research article
- Published by MDPI AG in ISPRS International Journal of Geo-Information
- Vol. 6 (7) , 217
Abstract
With the rapid explosion of information based on location, spatial clustering plays an increasingly significant role in this day and age as an important technique in geographical data analysis. Most existing spatial clustering algorithms are limited by complicated spatial patterns, which have difficulty in discovering clusters with arbitrary shapes and uneven density. In order to overcome such limitations, we propose a novel clustering method called Spatial Clustering with Multiple Density-Ordered Trees (SCMDOT). Motivated by the idea of the Density-Ordered Tree (DOT), we firstly represent the original dataset by the means of constructing Multiple Density-Ordered Trees (MDOT). In the constructing process, we impose additional constraints to control the growth of each Density-Ordered Tree, ensuring that they all have high spatial similarity. Furthermore, a series of MDOT can be successively generated from regions of sparse areas to the dense areas, where each Density-Ordered Tree, also treated as a sub-tree, represents a cluster. In the merging process, the final clusters are obtained by repeatedly merging a suitable pair of clusters until they satisfy the expected clustering result. In addition, a heuristic strategy is applied during the process of our algorithm for suitability for special applications. The experiments on synthetic and real-world spatial databases are utilised to demonstrate the performance of our proposed method.Keywords
This publication has 26 references indexed in Scilit:
- Minimum spanning tree based split-and-merge: A hierarchical clustering methodInformation Sciences, 2011
- Automatic Region Building for Spatial AnalysisTransactions in GIS, 2011
- Data clustering by minimizing disconnectivityInformation Sciences, 2011
- A graph-theoretical clustering method based on two rounds of minimum spanning treesPattern Recognition, 2010
- Robust path-based spectral clusteringPattern Recognition, 2008
- Clustering by Passing Messages Between Data PointsScience, 2007
- Rock: A robust clustering algorithm for categorical attributesInformation Systems, 2000
- Data clusteringACM Computing Surveys, 1999
- Chameleon: hierarchical clustering using dynamic modelingComputer, 1999
- Objective Criteria for the Evaluation of Clustering MethodsJournal of the American Statistical Association, 1971