SNN_flow: a shared nearest-neighbor-based clustering method for inhomogeneous origin-destination flows

ABSTRACT

Identifying clusters from individual origin–destination (OD) flows is vital for investigating spatial interactions and flow mapping. However, detecting arbitrarily-shaped and non-uniform flow clusters from network-constrained OD flows continues to be a challenge. This study proposes a shared nearest-neighbor-based clustering method (SNN_flow) for inhomogeneous OD flows constrained by a road network. To reveal clusters of varying shapes and densities, a normalized density for each OD flow is defined based on the concept of shared nearest-neighbor, and flow clusters are constructed using the density-connectivity mechanism. To handle large amounts of disaggregated OD flows, an efficient method for searching the network-constrained k-nearest flows is developed based on a local road node distance matrix. The parameters of SNN_flow are statistically determined: the density threshold is modeled as a significance level of a significance test, and the number of nearest neighbors is estimated based on the variance of the kth nearest distance. SNN_flow is compared with three state-of-the-art methods using taxicab trip data in Beijing. The results show that SNN_flow outperforms existing methods in identifying flow clusters with irregular shapes and inhomogeneous distributions. The clusters identified by SNN_flow can reveal human mobility patterns in Beijing.

KEYWORDS:

• Origin–destination flow
• shared nearest-neighbor
• inhomogeneous distribution
• clustering
• human mobility

Acknowledgments

The authors gratefully acknowledge the comments from the editor and the reviewers.

Data and codes availability statement

The data and codes that support the findings of this study are available on ‘figshare.com’, with the identifier at the private link: https://doi.org/10.6084/m9.figshare.14123960

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the National Key Research and Development Foundation of China [2017YFB0503601]; National Natural Science Foundation of China (NSFC) [41971353, 41730105, 42071435]; Natural Science Foundation of Hunan Province [2020JJ40669].

Notes on contributors

Qiliang Liu

Qiliang Liu received the Ph.D. degree in geographical information science from The Hong Kong Polytechnic University. He is currently an associate professor at Central South University, Hunan, China. His research interests focus on multi-scale spatio-temporal data mining and spatiotemporal statistics. He has published more than 30 peer-reviewed journal articles in these areas.

Jie Yang

Jie Yang is currently a Ph.D. candidate at Central South University and his research interests focus on spatio-temporal clustering and association rule mining.

Min Deng

Min Deng is currently a professor at Central South University and the associate dean of School of Geosciences and info-physics. His research interests are map generalization, spatio-temporal data analysis and mining.

Ci Song

Ci Song is an associate professor at the Institute of Geographical Sciences and Natural Resources Research, CAS. His research interests include spatial data mining, spatial analysis, and geographic information science.

Wenkai Liu

Wenkai Liu is currently a Ph.D. candidate at Central South University and his research interests focus on spatio-temporal clustering and association rule mining.