Journal of Geo-information Science >
Complex Trajectory Clustering based on a Spatial-Topological Similarity Measurement
Received date: 2019-07-15
Request revised date: 2019-08-12
Online published: 2019-12-11
Supported by
National Science Foundation of China(No.41671445)
National Science Foundation of China(No.41471330)
Copyright
Complex spatial entities such as ocean eddies, circulation, and rainfall processes that can move produce much more complex movement data, namely, complex trajectories. Complex trajectories have nonlinear structures and bear at least one split and/or merger branch. To mine the motion pattern of such complex trajectories, this paper proposed a Spatial-Topological Similarity Measurement (STSM) method based on the topological structure and spatial characteristics of complex trajectories. The STSM method was inspired by the graph isomorphism algorithm VF2. Firstly, each complex trajectory was represented by a graph structure with nodes and edges, which integrates the spatial coordinates of trajectory points into node attributes. By matching all maximal common substructures between the complex trajectories, one-to-one correspondence among the nodes in the matching structure was determined, The weighted Euclidean distance was then used to calculate the spatial similarity between points in the matched structure of the complex trajectories. Secondly, the average-linkage agglomerative hierarchical clustering analysis was carried out based on the proposed STSM algorithm, aiming at discovering any spatial clustering pattern of similar topological structures between complex trajectories. Finally, the effectiveness of the proposed method was verified by using the long-time series of the complex trajectories of cyclonic eddies in the South China Sea (SCS) from 1993 to 2016. The topological structure similarity algorithm CSM (Comprehensive Structure Matching) for complex trajectories was also compared and analyzed. Results show that clustering analysis based on the CSM algorithm can not fully mine spatial aggregation patterns of the cyclonic eddy complex trajectories, because complex trajectories with similar topological structures could exist in different regions. The STSM algorithm classified the complex trajectories of cyclonic eddies in the SCS into five clusters. Cluster 1 was in the north of the SCS, cluster 2 was in the central part of the SCS, and the other three clusters were interlaced in the south of the SCS. To a certain extent, this aggregation model not only reflected the differences of the formation and evolution of cyclonic eddies in the northern, central, and southern SCS, but also indicated that the movement of cyclonic eddies in the southern SCS had more complex heterogeneity than other regions of the SCS. Our findings suggest that the proposed method STSM can help discover effectively from the complex trajectory data the potential aggregation patterns of evolution processes, and provide a new method for revealing the spatiotemporal characteristics of such complex dynamic phenomena.
SUN Yong , WANG Huimeng , JIN Fengxiang , DU Yunyan , JI Min , YI Jiawei . Complex Trajectory Clustering based on a Spatial-Topological Similarity Measurement[J]. Journal of Geo-information Science, 2019 , 21(11) : 1669 -1678 . DOI: 10.12082/dqxxkx.2019.190375
图5 基于复杂轨迹相似性算法CSM和STSM的层次聚类树状图注:红色虚线为轮廓系数的剪切线。 Fig. 5 Hierarchical clustering tree maps based on the two complex trajectory similarity algorithms and their shear line based silhouette coefficients (red dashed lines): CSM versus STSM |
表1 基于相似性算法STSM的聚类结果的拓扑结构模式和活动参数统计分析Tab. 1 Topological patterns and corresponding activity parameters of the clustering result based on the STSM similarity algorithm |
类别 | 所在区域及轨迹颜色(图5(b)) | 复杂轨迹数目 | 主要演化结构模式及占比 | 活动范围/km | 活动天数/d | 轨迹复杂度 |
---|---|---|---|---|---|---|
第一类 | 南海北部(蓝色) | 149 | vms(20.13%) | 280.59 | 59 | 0.45 |
第二类 | 南海中部(绿色) | 358 | smsv(25.91%) | 318.86 | 75 | 0.47 |
第三类 | 南海南部(紫色) | 159 | vmsv(33.33%) | 286.93 | 67 | 0.48 |
第四类 | 南海南部(橘色) | 47 | vmsv(52.08%) | 192.04 | 40 | 0.31 |
第五类 | 南海南部(青色) | 17 | vmsmv(64.71%) | 255.18 | 90 | 0.51 |
[1] |
李婷, 裴稻, 袁烨城 , 等. 人类活动轨迹的分类、模式和应用研究综述[J]. 地理科学进展, 2014,33(7):938-948.
[
|
[2] |
刘瑜, 康朝贵, 王法辉 . 大数据驱动的人类移动模式和模型研究[J]. 武汉大学学报·信息科学版, 2014,39(6):660-666.
[
|
[3] |
宋辞, 裴韬 . 北京市多尺度中心特征识别与群聚模式发现[J]. 地球信息科学学报, 2019,21(3):384-397.
[
|
[4] |
龚玺, 裴韬, 孙嘉 , 等. 时空轨迹聚类方法研究进展[J]. 地理科学进展, 2011,30(5):522-534.
[
|
[5] |
郑宇 . 城市计算概述[J]. 武汉大学学报·信息科学版, 2015,40(1):1-12.
[
|
[6] |
|
[7] |
|
[8] |
牟乃夏, 徐玉静, 张恒才 , 等. 移动轨迹聚类方法研究综述[J].测绘通报, 2018(1):1-7.
[
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
郭文月, 刘海砚, 孙群 , 等. 面向区域增量更新的等高线群混合相似性度量模型[J]. 地球信息科学学报, 2019,21(2):147-156.
[
|
[16] |
|
[17] |
|
[18] |
|
[19] |
|
[20] |
|
[21] |
|
[22] |
|
[23] |
|
[24] |
|
[25] |
|
[26] |
|
[27] |
|
[28] |
|
[29] |
|
[30] |
吴笛, 杜云艳, 易嘉伟 , 等. 基于密度的轨迹时空聚类分析[J]. 地球信息科学学报, 2015,17(10):1162-1171.
[
|
[31] |
杜云艳, 莫洋, 王会蒙 , 等. 基于复杂网络的海洋涡旋移动特征研究[J]. 海洋学报, 2017,39(7):110-123.
[
|
/
〈 |
|
〉 |