Premium
Polygonal Clustering Analysis Using Multilevel Graph‐Partition
Author(s) -
Wang Wanyi,
Du Shihong,
Guo Zhou,
Luo Liqun
Publication year - 2015
Publication title -
transactions in gis
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.721
H-Index - 63
eISSN - 1467-9671
pISSN - 1361-1682
DOI - 10.1111/tgis.12124
Subject(s) - cluster analysis , complete linkage clustering , similarity (geometry) , partition (number theory) , hierarchical clustering , pattern recognition (psychology) , polygon mesh , single linkage clustering , graph partition , mathematics , graph , computer science , cluster (spacecraft) , correlation clustering , artificial intelligence , data mining , combinatorics , cure data clustering algorithm , geometry , image (mathematics) , programming language
Existing methods of spatial data clustering have focused on point data, whose similarity can be easily defined. Due to the complex shapes and alignments of polygons, the similarity between non‐overlapping polygons is important to cluster polygons. This study attempts to present an efficient method to discover clustering patterns of polygons by incorporating spatial cognition principles and multilevel graph partition. Based on spatial cognition on spatial similarity of polygons, four new similarity criteria (i.e. the distance, connectivity, size and shape) are developed to measure the similarity between polygons, and used to visually distinguish those polygons belonging to the same clusters from those to different clusters. The clustering method with multilevel graph‐partition first coarsens the graph of polygons at multiple levels, using the four defined similarities to find clusters with maximum similarity among polygons in the same clusters, then refines the obtained clusters by keeping minimum similarity between different clusters. The presented method is a general algorithm for discovering clustering patterns of polygons and can satisfy various demands by changing the weights of distance, connectivity, size and shape in spatial similarity. The presented method is tested by clustering residential areas and buildings, and the results demonstrate its usefulness and universality.