A density-based approach for detecting network-constrained clusters in spatial point events

ABSTRACT

Existing spatial clustering methods primarily focus on points distributed in planar space. However, occurrence locations and background processes of most human mobility events within cities are constrained by the road network space. Here we describe a density-based clustering approach for objectively detecting clusters in network-constrained point events. First, the network-constrained Delaunay triangulation is constructed to facilitate the measurement of network distances between points. Then, a combination of network kernel density estimation and potential entropy is executed to determine the optimal neighbourhood size. Furthermore, all network-constrained events are tested under a null hypothesis to statistically identify core points with significantly high densities. Finally, spatial clusters can be formed by expanding from the identified core points. Experimental comparisons performed on the origin and destination points of taxis in Beijing demonstrate that the proposed method can ascertain network-constrained clusters precisely and significantly. The resulting time-dependent patterns of clusters will be informative for taxi route selections in the future.

KEYWORDS:

• Spatial point events
• network-constrained clusters
• density-based clustering
• statistical tests

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [41730105, 41601424, 41471385, 41771492]; National Key Research and Development Foundation of China [2017YFB0503601, 2017YFB0503700]; the China Postdoctoral Science Foundation [2017M610486].

Notes on contributors

Min Deng

Min Deng is currently a professor at Central South University and Dean of Geo-informatics department. His research interests are map generalization, spatio-temporal data analysis and mining.

Xuexi Yang

Xuexi Yang is a Ph.D. student at Central South University and his research interests focus on spatio-temporal clustering and anomaly detection.

Yan Shi

Yan Shi is currently a lecturer at Central South University and his research interests include spatio-temporal clustering, anomaly detection and association rules mining.

Jianya Gong

Jianya Gong is currently a professor at Wuhan University and Dean of Remote Sensing and Information Engineering department. He majors in the research of geographic information theory and geographic information service.

Yang Liu

Yang Liu receives the master’s degree in Central South University and works in the area of spatio-temporal anomaly detection.

Huimin Liu

Huimin Liu is an associate professor at Central South University and works in the area of map generalization and multiple representation.