一种基于空间-拓扑结构相似性的复杂轨迹聚类算法

doi:10.12082/dqxxkx.2019.190375

地球信息科学学报 ›› 2019, Vol. 21 ›› Issue (11): 1669-1678.doi: 10.12082/dqxxkx.2019.190375

• 地球信息科学理论与方法 • 上一篇下一篇

一种基于空间-拓扑结构相似性的复杂轨迹聚类算法

孙勇¹, 王会蒙^2,³, 靳奉祥⁴, 杜云艳^2,^3,^*(), 季民¹, 易嘉伟^2,³

1. 山东科技大学测绘科学与工程学院,青岛266590
2. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京 100101
3. 中国科学院大学,北京100049
4. 山东建筑大学,济南 250101

收稿日期:2019-07-15 修回日期:2019-08-12 出版日期:2019-10-25 发布日期:2019-12-11
作者简介:孙勇（1986-）,男,江西吉安人,博士生,研究方向为地理信息系统开发与应用,数据挖掘。 E-mail: ttsunyong@163.com
基金资助:
国家自然科学基金项目(No.41671445);国家自然科学基金项目(No.41471330)

Complex Trajectory Clustering based on a Spatial-Topological Similarity Measurement

SUN Yong¹, WANG Huimeng^2,³, JIN Fengxiang⁴, DU Yunyan^2,^3,^*(), JI Min¹, YI Jiawei^2,³

1. College of Geomatics, Shandong University of Science and Technology, Qingdao 266590, China
2. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences, Beijing 100101, China
3. University of Chinese Academy of Sciences, Beijing 100049, China
4. Shandong Jianzhu University, Ji'nan 250101, China

Received:2019-07-15 Revised:2019-08-12 Online:2019-10-25 Published:2019-12-11
Contact: DU Yunyan
Supported by:
National Science Foundation of China(No.41671445);National Science Foundation of China(No.41471330)

摘要/Abstract

摘要：

复杂的面状空间实体如海洋涡旋、环流和降雨过程在运动过程中会产生更复杂的轨迹,即具有分支结构的复杂轨迹。为了挖掘这类复杂轨迹的运动模式特征,本文从复杂轨迹的拓扑结构和空间特征出发,创新性地提出复杂轨迹的空间-拓扑结构相似性度量算法（Spatial-Topological Similarity Measurement, STSM）,该算法是基于图同构算法VF2改进的。首先STSM算法将复杂轨迹用带有节点和边的图结构表达,并将空间信息融入图结构的节点属性中,通过匹配复杂轨迹之间所有最大公共子结构,找到匹配结构中节点之间一一对应的关系,利用加权的欧式距离计算复杂轨迹匹配结构中点对之间的空间距离。然后,基于STSM相似性算法进行层次聚类分析,旨在发现复杂轨迹之间相似的拓扑结构在空间上的聚集模式。最后,利用1993-2016年长时间序列的中国南海冷涡复杂轨迹验证方法的有效性,并对比分析复杂轨迹拓扑结构相似性算法CSM。结果表明：单纯用拓扑结构相似性算法CSM进行聚类分析,不能充分挖掘空间的聚集模式,因为不同空间位置也存在拓扑结构相似的轨迹。而本文提出的STSM算法将南海冷涡复杂轨迹分为5类,第一类分布在南海北部、第二类分布在南海中部、其他三类交错在南海南部。这种聚集模式在一定程度上反映了冷涡的生成和演化过程在南海北部、中部、南部的差异性,同时也表明了冷涡移动在南海南部存在更为复杂的异质性。因此,本文提出的方法可以有效地从复杂轨迹数据中发现其演化过程的潜在聚集模式,为认识这类复杂动态现象的时空演化特征提供了一种新的方法。

关键词: 复杂轨迹, 相似性, 拓扑结构, 聚类, 图匹配, 南海, 冷涡

Abstract:

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.

Key words: complex trajectory, similarity, topological structure, clustering, graph matching, South China Sea, cyclonic Eddies

孙勇, 王会蒙, 靳奉祥, 杜云艳, 季民, 易嘉伟. 一种基于空间-拓扑结构相似性的复杂轨迹聚类算法[J]. 地球信息科学学报, 2019, 21(11): 1669-1678.DOI:10.12082/dqxxkx.2019.190375

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

图/表 9

图1

图2

图3

图4

图5

图6

表1

图7

图8

参考文献 31

[1]	李婷, 裴稻, 袁烨城 , 等. 人类活动轨迹的分类、模式和应用研究综述[J]. 地理科学进展, 2014,33(7):938-948. doi: 10.11820/dlkxjz.2014.07.009
	[ Li T, Pei Tao, Yuan Y C , et al. A review on the classification, patterns and applied research of human mobility trajectory[J]. Progress in Geography, 2014,33(7):938-948. ] doi: 10.11820/dlkxjz.2014.07.009
[2]	刘瑜, 康朝贵, 王法辉 . 大数据驱动的人类移动模式和模型研究[J]. 武汉大学学报·信息科学版, 2014,39(6):660-666.
	[ Liu Y, Kang C G, Wang F H . Towards big data-driven human mobility patterns and models[J]. Geomatics and Information Science of Wuhan University, 2014,39(6):660-666. ]
[3]	宋辞, 裴韬 . 北京市多尺度中心特征识别与群聚模式发现[J]. 地球信息科学学报, 2019,21(3):384-397. doi: 10.12082/dqxxkx.2019.180608
	[ Song C, Pei T . Exploring polycentric characteristic and residential cluster patterns of urban city from big data[J]. Journal of Geo-information Science, 2019,21(3):384-397. ] doi: 10.12082/dqxxkx.2019.180608
[4]	龚玺, 裴韬, 孙嘉 , 等. 时空轨迹聚类方法研究进展[J]. 地理科学进展, 2011,30(5):522-534. doi: 10.11820/dlkxjz.2011.05.002
	[ Gong X, Pei T, Sun J , et al. Review of the research progresses in trajectory clustering methods[J]. Progress in Geography, 2011,30(5):522-534. ] doi: 10.11820/dlkxjz.2011.05.002
[5]	郑宇 . 城市计算概述[J]. 武汉大学学报·信息科学版, 2015,40(1):1-12.
	[ Zheng Y . Introduction to urban computing[J]. Geomatics and Information Science of Wuhan University, 2015,40(1):1-12. ]
[6]	Wang H M, Du Y Y, Yi J W , et al. A new method for measuring topological structure similarity between complex trajectories[J]. IEEE Transactions on Knowledge and Data Engineering, 2018,31(10):1836-1848. doi: 10.1109/TKDE.69
[7]	Qiu X, Mao Q, Tang Y . Reversed graph embedding resolves complex single-cell trajectories[J]. Nature Methods, 2017,14(10):979-982. doi: 10.1038/nmeth.4402 pmid: 28825705
[8]	牟乃夏, 徐玉静, 张恒才 , 等. 移动轨迹聚类方法研究综述[J].测绘通报, 2018(1):1-7.
	[ Mou N X, Xu Y J, Zhang H C . A Review of the mobile trajectory clustering methods[J]. Bulletin of Surveying and Mapping, 2018(1):1-7. ]
[9]	UrKa D, Kevin B, Francesca C , et al. Analysis and visualisation of movement: An interdisciplinary review[J]. Movement Ecology, 2015,3(1):5. doi: 10.1186/s40462-015-0032-y pmid: 25874114
[10]	Vaughan N, Gabrys B . Comparing and combining time series trajectories using dynamic time warping[J]. Procedia Computer Science, 2016,96:465-474. doi: 10.1016/j.procs.2016.08.106
[11]	Buchin K, Buchin M, Kreveld M V . Finding long and similar parts of trajectories[J]. Computational Geometry Theory & Ap-plications, 2011,44(9):465-476. doi: 10.1016/j.jinorgbio.2019.110953 pmid: 31816442
[12]	Pelekis N, Andrienko G, Andrienko N , et al. Visually exploring movement data via similarity-based analysis[J]. Journal of Intelligent Information Systems, 2012,38(2):343-391. doi: 10.1007/s10844-011-0159-2
[13]	Bunke H, Shearer K . A graph distance metric based on the maximal common subgraph[J]. Pattern Recognition Letters, 1998,( 3-4):255-259.
[14]	Cordella L P . A (Sub)graph isomorphism algorithm for Matching large graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004,26(10):1367-1372. doi: 10.1109/TPAMI.2004.75 pmid: 15641723
[15]	郭文月, 刘海砚, 孙群 , 等. 面向区域增量更新的等高线群混合相似性度量模型[J]. 地球信息科学学报, 2019,21(2):147-156. doi: 10.12082/dqxxkx.2019.180298
	[ Guo W Y, Liu H Y, Sun Q , et al. A Contour group mixed similarity measurement model for region incremental updating[J]. Journal of Geo-information Science, 2019,21(2):147-156. ] doi: 10.12082/dqxxkx.2019.180298
[16]	Rousseeuw P J . Silhouettes: A graphical aid to the interpretation and validation of cluster analysis[J]. Journal of Computational& Applied Mathematics. 1987,20:53-65. doi: 10.1016/j.cgh.2019.11.058 pmid: 31816445
[17]	Pujol M I, Faugère Y, Taburet , et al. DUACS DT2014: the new multi-mission altimeter data set reprocessed over 20 years[J]. Ocean Science, 2016,12(5):1067-1090. doi: 10.5194/os-12-1067-2016
[18]	Yi J W, DuY Y, Liang F Y . A representation framework for studying spatiotemporal changes and interactions of dynamic geographic phenomena[J]. International Journal of Geographical Information Science, 2014,28:1010-1027. doi: 10.1080/13658816.2014.890201
[19]	Yi J W, DuY Y, Liang F Y . An auto-tracking algorithm for mesoscale eddies using global nearest neighbor filter[J]. Limnology & Oceanography Methods, 2017,15(3):276-290. doi: 10.1111/jfb.14224 pmid: 31814124
[20]	Fang F, Morrow R . Evolution, movement and decay of warm-core Leeuwin Current eddies[J]. Deep-Sea Research Part II, 2003,50(12):2245-2261. doi: 10.1016/S0967-0645(03)00055-9
[21]	Rodríguez R, Viudez A, Ruiz S . Vortex merger in oceanic tripoles[J]. Journal of Physical Oceanography, 2011,6:1239-1251. doi: 10.1175/2011JPO4582.1
[22]	Liu W, Li X, Rahn D A . Storm event representation and analysis based on a directed spatiotemporal graph model[J]. International Journal of Geographical Information Science, 2016,30(5):948-969. doi: 10.1080/13658816.2015.1081910
[23]	Chen G X, Hou Y, Chu X . Mesoscale eddies in the South China Sea: Mean properties, spatiotemporal variability, and impact on thermohaline structure[J]. Journal of Geophysical Research, 2011,116:1-20.
[24]	Yang S, Xing J, Chen D . A modelling study of eddy-splitting by an Island/Seamount[J]. Ocean Science, 2017,13:1-25. doi: 10.5194/os-13-1-2017
[25]	Chi P C, Chen Y, Lu S . Wind-driven South China Sea deep basin warm-core/cool-core eddies[J]. Journal of Oceanography, 1998,54(4):347-360. doi: 10.1007/BF02742619
[26]	Zhang Z, Zhao W, Tian J . A mesoscale eddy pair southwest of Taiwan and its influence on deep circulation[J]. Journal of Geophysical Research: Oceans, 2013,118(12):6479-6494. doi: 10.1002/2013JC008994
[27]	Zhang Z, Zhao W, Qiu B . Anticyclonic eddy sheddings from Kuroshio loop and the accompanying cyclonic eddy in the northeastern South China Sea[J]. Journal of Physical Oceanography, 2017,47(6):1243-1259. doi: 10.1175/JPO-D-16-0185.1
[28]	Chen G X, Hou Y, Zhang Q , et al. The eddy pair off eastern Vietnam: Interannual variability and impact on thermohaline structure[J]. Continental Shelf Research, 2010,30(7):715-723. doi: 10.1016/j.csr.2009.11.013
[29]	Wang G, Su J, Chu P C . Mesoscale eddies in the South China Sea observed with altimeter data[J]. Geophysical Research Letters, 2003,30, 2121. doi: 10.1029/2003GL018532
[30]	吴笛, 杜云艳, 易嘉伟 , 等. 基于密度的轨迹时空聚类分析[J]. 地球信息科学学报, 2015,17(10):1162-1171. doi: 10.3724/SP.J.1047.2015.01162
	[ Wu D, Du Y Y, Yi J W , et al. Density-based spatiotemporal clustering analysis of trajectories[J]. Journal of Geo-information Science, 2015,17(10):1162-1171. ] doi: 10.3724/SP.J.1047.2015.01162
[31]	杜云艳, 莫洋, 王会蒙 , 等. 基于复杂网络的海洋涡旋移动特征研究[J]. 海洋学报, 2017,39(7):110-123.
	[ Du Y Y, Mo Y, Wang H M , et al. Exploring the propagation characteristics of ocean eddies from the perspective of complex networks: A case study in the South China Sea[J]. Haiyang Xuebao, 2017,39(7):110-123. ]

类别	所在区域及轨迹颜色（图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

一种基于空间-拓扑结构相似性的复杂轨迹聚类算法

Complex Trajectory Clustering based on a Spatial-Topological Similarity Measurement

RichHTML

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 31

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	冯耀伟, 屈永华. 结合光照信息的多尺度K-均值植被几何光学四分量提取算法[J]. 地球信息科学学报, 2023, 25(5): 1037-1049.
[2]	王玉竹, 闫浩文, 禄小敏. 面向路网匹配的层次化语义相似性度量模型[J]. 地球信息科学学报, 2023, 25(4): 714-725.
[3]	王鹏洲, 赵志远, 姚伟, 吴升, 汪艳霞, 方莉娜, 邬群勇. 基于地理流空间的巡游车与网约车人群出行模式研究[J]. 地球信息科学学报, 2023, 25(4): 726-740.
[4]	邝嘉恒, 邬群勇. 接驳地铁站的共享单车时空均衡性分析与吸引区域优化[J]. 地球信息科学学报, 2022, 24(7): 1337-1348.
[5]	郭逸飞, 吴田军, 骆剑承, 石含宁, 郜丽静. 基于不确定性迭代优化的山地植被遥感制图[J]. 地球信息科学学报, 2022, 24(7): 1406-1419.
[6]	姜晓, 白璐斌, 楼夏寅, 李梅, 刘晖. 基于多尺度时空聚类的共享单车潮汐特征挖掘与需求预测研究[J]. 地球信息科学学报, 2022, 24(6): 1047-1060.
[7]	初晨, 张恒才, 陆锋. 大型商场顾客消费行为轨迹推断[J]. 地球信息科学学报, 2022, 24(6): 1034-1046.
[8]	魏海涛, 杜云艳, 张佳丽, 孙璐瑶. 基于CNN的空间数据自适应切分算法[J]. 地球信息科学学报, 2022, 24(6): 1099-1106.
[9]	何阳, 闫浩文, 王卓, 王小龙. 面向微地图的地标提取方法及个性化寻路应用[J]. 地球信息科学学报, 2022, 24(5): 827-836.
[10]	张晗, 邬群勇. 基于LDA和优化蚁群的OD流向时空语义聚类算法[J]. 地球信息科学学报, 2022, 24(5): 837-850.
[11]	朱秋圳, 邬群勇, 姚铖鑫, 孙豪宇. 基于DBI和稀疏轨迹数据的交通状态精细划分与识别[J]. 地球信息科学学报, 2022, 24(3): 458-468.
[12]	邓雅文, 侯鹏, 蒋卫国, 彭凯锋, 荔琢, 邓越. 基于多特征指标和层次聚类分析的河源区范围自动划分方法研究[J]. 地球信息科学学报, 2022, 24(3): 469-482.
[13]	邵攀, 范红梅, 高梓昂. 基于自适应半监督模糊C均值的遥感变化检测[J]. 地球信息科学学报, 2022, 24(3): 508-521.
[14]	王琳, 钟泓文, 许章华, 王武林. Luojia-01夜光数据和“点轴发育”理论支持下的夜间经济集聚区定量识别与分类方法[J]. 地球信息科学学报, 2022, 24(11): 2141-2152.
[15]	刘贺, 郭黎, 李豪, 张婉晨, 白翔天. 面实体匹配的集成学习CatBoost方法[J]. 地球信息科学学报, 2022, 24(11): 2198-2211.