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

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

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

孙勇1, 王会蒙2,3, 靳奉祥4, 杜云艳2,3,*(), 季民1, 易嘉伟2,3   

  1. 1. 山东科技大学测绘科学与工程学院,青岛266590
    2. 中国科学院地理科学与资源研究所 资源与环境信息系统国家重点实验室,北京 100101
    3. 中国科学院大学,北京100049
    4. 山东建筑大学,济南 250101
  • 收稿日期:2019-07-15 修回日期:2019-08-12 出版日期:2019-10-25 发布日期:2019-12-11
  • 通讯作者: 杜云艳 E-mail:duyy@lreis.ac.cn
  • 作者简介:孙 勇(1986-),男,江西吉安人,博士生,研究方向为地理信息系统开发与应用,数据挖掘。 E-mail: ttsunyong@163.com
  • 基金资助:
    国家自然科学基金项目(No.41671445);国家自然科学基金项目(No.41471330)

Complex Trajectory Clustering based on a Spatial-Topological Similarity Measurement

SUN Yong1, WANG Huimeng2,3, JIN Fengxiang4, DU Yunyan2,3,*(), JI Min1, YI Jiawei2,3   

  1. 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 E-mail:duyy@lreis.ac.cn
  • Supported by:
    National Science Foundation of China(No.41671445);National Science Foundation of China(No.41471330)

摘要:

复杂的面状空间实体如海洋涡旋、环流和降雨过程在运动过程中会产生更复杂的轨迹,即具有分支结构的复杂轨迹。为了挖掘这类复杂轨迹的运动模式特征,本文从复杂轨迹的拓扑结构和空间特征出发,创新性地提出复杂轨迹的空间-拓扑结构相似性度量算法(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