Adaptive Spatial Clustering Methods For Multi-type Points And Multi-type Flows

Spatial clustering methods for multi-type points/flows aim to discover the spatial distributions of the spatial relationships among different types of points/flows.Discovery of multi-type points/flows clusters could support a better understanding of relationships between different geographical phenomena from the perspective of spatial location and spatial interaction.Because of spatial heterogeneity,challenges remain in adaptively detection of multi-type points/flows clusters with arbitrary shapes and different densities.Specifically,it is difficult to construct spatial neighborhood relationships adaptively,to identify spatial clusters adaptively and to determine the significance of clusters effectively.To fill this gap,adaptive spatial clustering methods for multitype points/flows were developed in this dissertation.First,the influence of spatial heterogeneity on neighborhood relationship construction and cluster detection was adaptively modeled using spatial statistical methods.Then,clusters with different shapes and densities were adaptively identified based on the idea of combinatorial optimization.Finally,fast Monte Carlo methods for evaluating the statistical significance of spatial clusters were developed with the help of road topological relations and data statistical characteristics.The proposed methods in this dissertation were applied in urban crime analysis,spatial structure analysis,human movement pattern analysis and urban public transport supply and demand analysis.The main research work of this dissertation can be summarized as follows:(1)When spatial points are distributed unevenly,the neighboring relationships cannot be constructed appropriately and clusters cannot be detected adaptively.To solve these problems,a natural neighborhood based adaptive clustering method for multi-type points was proposed.Firstly,the neighborhood relationships,called ‘natural neighborhoods’,were constructed adaptively based on the formation mechanism of cooccurrence relationships and the local-distribution characteristics of spatial points.Using the natural neighborhoods,a multi-level approach for identifying clusters was proposed.Compared with the three state-ofthe-art methods,experiments on simulated datasets showed that the proposed method can discover clusters from unevenly distributed spatial points completely and accurately.Case studies using crime and facilities datasets demonstrated that the clusters identified by the proposed method can reveal the inductive relationship among different types of crimes and the impact of urban facilities on crimes.The discovered clusters can make a positive contribution to crime prevention.(2)Existing spatial clustering methods for multi-type points usually do not consider constraints of road networks,and cannot make statistical inference on the clustering results effectively.To solve these problems,an adaptive clustering method for network-constrained multi-type points was proposed in this dissertation.Firstly,a rapid network-constrained knearest neighbor method was used to adaptively construct neighboring relationships among different multi-type points.Then,the discovery of clusters was modeled as a combinational optimization problem.A new prevalence measure was defined based on the likelihood ratio statistic,and a two-phase expansion method was proposed to discover clusters without a brute-force search.Finally,a monte Carlo simulation method was used to evaluate the statistical significance of the identified clusters.Experiments using simulated datasets showed that the proposed method outperforms three state-of-the-art methods.The proposed method was also used to reveal spatial structure of urban functions,which could provide a reference for urban planning.(3)Existing spatial clustering methods are hard to evaluate the statistical significance of irregularly-shaped and inhomogeneous clusters in large datasets.To overcome these limitations,an adaptive clustering method for network-constrained multi-type flows was proposed.Firstly,a new network-constrained flow density was defined based on the concept of the shared nearest neighbor.Then,a fast Monte Carlo simulation method was developed to statistically identify high-density flows for each type of flow.Finally,clusters were adaptively identified using the density-connectivity mechanism.Experiments on simulated datasets shows that the proposed method outperforms two state-of-the-art methods in identifying inhomogeneous clusters.The proposed method was also applied to taxi and ride-hailing service datasets.The identified clusters can reveal competition patterns between taxi and ride-hailing services,which can provide references for transportation optimization.(4)Existing multi-layer network community detection methods usually ignore the differences of spatial distributions of different types of flows,and cannot evaluate the statistical significance of identified communities.To solve these problems,an adaptive clustering method for multi-layer network was proposed.Firstly,the interaction intensity of interlayer was calculated based on the differences of flow distributions of different types.Then,the Poisson model and normal distribution modelbased scan statistics was employed to detect multi-layer network communities.Finally,an adaptive clustering method based on particle swarm optimization was developed.Experiments using extensive simulated datasets showed that the proposed method is superior to two state-of-art methods.The proposed method was also applied to bus line and smart card datasets.The identified multi-layer communities are useful for transportation plan optimization.A clustering prototype system for multi-type points and multi-type flows was implemented using B/S architecture.The parallel versions of clustering algorithms were implemented based on Geo Spark.The visualization of clustering results was implemented based on Leaflet.This prototype system can provide convenient cluster analysis and visual analysis functions for users.Finally,the main contributions and innovations of this dissertation were summarized,and the further research directions are outlined.This paper contains 67 Figures,10 tables,177 references.