EN中文

地球信息科学学报 >

2019 , Vol. 21 >Issue 11: 1669 - 1678

DOI: https://doi.org/10.12082/dqxxkx.2019.190375

地球信息科学理论与方法

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

  • 孙勇 1 ,
  • 王会蒙 2, 3 ,
  • 靳奉祥 4 ,
  • 杜云艳 , 2, 3, * ,
  • 季民 1 ,
  • 易嘉伟 2, 3
展开
  • 1. 山东科技大学测绘科学与工程学院,青岛266590
  • 2. 中国科学院地理科学与资源研究所 资源与环境信息系统国家重点实验室,北京 100101
  • 3. 中国科学院大学,北京100049
  • 4. 山东建筑大学,济南 250101
杜云艳（1973-）,女,河南南阳人,博士,研究员,研究方向为时空建模与推理。E-mail:

孙 勇（1986-）,男,江西吉安人,博士生,研究方向为地理信息系统开发与应用,数据挖掘。 E-mail: ttsunyong@163.com

收稿日期: 2019-07-15

  要求修回日期: 2019-08-12

  网络出版日期: 2019-12-11

基金资助

国家自然科学基金项目(No.41671445)

国家自然科学基金项目(No.41471330)

版权

版权所有，未经授权，不得转载、摘编本刊文章，不得使用本刊的版式设计。
收起

Complex Trajectory Clustering based on a Spatial-Topological Similarity Measurement

  • SUN Yong 1 ,
  • WANG Huimeng 2, 3 ,
  • JIN Fengxiang 4 ,
  • DU Yunyan , 2, 3, * ,
  • JI Min 1 ,
  • YI Jiawei 2, 3
Expand
  • 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
DU Yunyan, E-mail:

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

Copyright reserved © 2016
Fold

摘要

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

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

本文引用格式

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

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

1 引言

近年来,随着无线通信、GPS定位、无线传感器技术的广泛应用,轨迹分析已成为地理信息科学中的一个重要研究课题[1,2,3]。轨迹相似性计算和聚类模式挖掘是轨迹研究的热点,可用于识别运动中的特定模式和规律[2,3,4]。基于相似性度量的轨迹聚类是通过相似性度量来确定轨迹之间的关系,再对轨迹进行聚类分析。使最终得到的结果簇内相似度尽可能大,簇间相似度尽可能小[4,5]。然而,大多数的轨迹模式挖掘仅限于简单的刚体运动,即运动物体本身的结构,如人、车辆和动物,不随时间和空间而变化。它们的轨迹是线性的,没有分支,可以称为简单轨迹。事实上,正如Wang等[6]提出的,自然界也存在着一种复杂的动态现象,其移动对象随时空位置变化其自身结构同时发生分裂或者合并,如海洋涡旋、环流和降雨过程等,这类复杂动态现象的轨迹称之为复杂轨迹[6,7]。复杂轨迹具有典型的非线性拓扑结构特征,时间和轨迹点存在一对多的时空特性。对这类具有分支结构的轨迹进行空间聚类、分类、异常模式等分析,最关键的问题是定义复杂轨迹之间的相似性度量[8]。
传统的轨迹相似性方法可分为3类：空间相似性、时空相似性、属性相似性。空间相似性只考虑点的位置来测量轨迹的形状。它主要包括欧氏距离、Hausdorff distance、Fréchet Distance[9]。时空相似性则是按照时间序列比较轨迹数据点,包括动态时间规整Dynamic Time Warping[10]、最长公共子序列[11]。基于属性的相似性计算主要考虑运动参数如速度、加速度、方向等,以编辑距离（Edit distance）方法为主[12]。然而,Euclidean距离需要2个比较轨迹具有相同数量的点集,Hausdorff距离不考虑点时间顺序。Fréchet Distance 和Dynamic Time Warping方法应用条件为运动时刻和轨迹点必须是一对一的关系,而复杂轨迹有不同的分支结构,其运动时刻和相应的轨迹点不仅存在一对一,还存在一对多的关系。正是由于这种特性,把具有分支结构的复杂轨迹转化成线性字符串又是一大难题,相应的最长公共子序列和编辑距离同样不能直接应用。针对复杂轨迹的分支结构特征,可以将复杂轨迹用带有节点和边的图结构表达,然后计算2条复杂轨迹构成的图的结构的相似性。
图的相似性度量方法在很多领域都有应用,尤其是图同构[13,14]。图同构比较典型算法是VF2算法[14],VF2具有高效性适合各类图结构,但VF2只能找到图同构和子图同构,在轨迹的实际应用中更多的是需要找到2个图结构的所有的最大公共子结构。虽然,Wang等[6]的已有研究对VF2算法进行扩展,提出了新的拓扑结构相似性算法CSM（Comprehensive Structure Matching）,该算法不仅能够找到图同构、子图同构,还能找到部分同构,并通过大量的模拟实验和方法对比,验证了方法的有效性,同时在实际应用中能够针对某一特殊轨迹,挖掘相似的轨迹结构,发现新知。但CSM算法忽略了空间距离这一重要信息,一个完整的相似性算法应该包括空间相似性[15]。
因此,本文从复杂轨迹的拓扑结构和空间特征出发,创新性地提出复杂轨迹的空间-拓扑结构相似性度量算法（Spatial-Topological Similarity Measurement, STSM）,STSM算法将复杂轨迹用带有节点和边的图结构表达,并将空间信息融入图结构的节点属性中,通过匹配2条复杂轨迹所有的最大公共子结构,找到匹配结构中节点之间一一对应的关系,利用欧式距离度量复杂轨迹的相似性。然后基于STSM相似性算法进行层次聚类分析,旨在挖掘复杂轨迹的拓扑结构在空间上的聚集模式。最后,通过1993-2016年长时间序列的南海冷涡复杂轨迹的应用实例分析,挖掘南海冷涡复杂轨迹的拓扑结构聚集模式和有意义的地理新知。

2 研究方法

2.1 复杂轨迹概念

为了更好地描述本文提出的复杂轨迹相似性算法STSM,需要对复杂轨迹的概念及其相关属性进行形式化描述。Wang等[6]已经定义了什么是复杂轨迹,在此进一步说明复杂轨迹与简单轨迹的具体区别。
简单轨迹正如郑宇等[5]定义的,轨迹是由一系列按时间顺序排列的点表示的。如下所示：
Tr = P 1 , x 1 , y 1 , t 1 ; P 2 , x 2 , y 2 , t 2 ; ⋯
式中：P表示轨迹点的ID;x、y表示轨迹点的运动位置如经度、纬度;t表示轨迹点的运动时刻,简单轨迹的结构是线性的（图1（a））,运动时刻和轨迹点是一对一的关系。
图1 简单轨迹与复杂轨迹示意

Fig. 1 Schematic diagrams of simple trajectory and complex trajectory

本文提出的复杂轨迹是具有分支结构的轨迹,是指运动的个体在某一时刻分裂为多个个体或者多个个体合并为一个个体,从而使轨迹分裂为多个分支结构或者由多个分支结构合并为线性结构（图1（b））。复杂轨迹可以表示为：
CTr = P 1 , x 1 , y 1 , t 1 , ptype ; P 2 , x 2 , y 2 , t 2 , ptype ; ⋯
式中：P、x、y与简单轨迹的一致;ptype表示复杂轨迹点的类型,不同于线性结构的简单轨迹。
复杂轨迹的结构是非线性的,具有以下特性：
（1）除了开始点（O）、结束点（D）,复杂轨迹中还包括分裂点（S）、合并点(M)等特征点。如图1（b）中,开始点为P1,结束点为P10和P11;分裂点为P3、P9,合并点为P8。
（2）运动时刻与轨迹点不仅存在一对一的关系,还有一对多的关系。
（3）本文用复杂度η度量复杂轨迹的复杂程度,η表示复杂轨迹中参与分裂点的个数（Ns）与合并点的个数（Nm）之和与轨迹点总数（Np）的比值,不做重复计数。如图1（b）所示,参与分裂的点包括P3、P4、P5、P9、P10、P11,参与合并的点包括P6、P7、P8,重复的点只做一次计数,那么这条复杂轨迹的复杂度为0.818。
η = N s + N m N p ( 0 < η ≤ 1 )

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

针对复杂轨迹的拓扑结构特征,将复杂轨迹用带有节点和边的有向无环的图结构表达,并为图结构的节点添加空间属性,提出这类复杂轨迹的空间-拓扑结构相似性算法STSM（Spatial-Topological Similarity Measurement）。该算法主要包括2个部分,即复杂轨迹拓扑结构匹配算法和复杂轨迹相似性计算。复杂轨迹拓扑结构匹配算法挖掘轨迹之间的完全同构、子轨迹同构、部分子轨迹同构,复杂轨迹相似性计算是基于已匹配的结构部分,利用加权的欧式距离计算复杂轨迹匹配点对之间的空间距离。最后,将这种相似性算法应用于层次聚类模式挖掘中,旨在发现相似的轨迹结构在空间的聚集类簇。
2.2.1 空间-拓扑结构相似性计算
将复杂轨迹用带有节点和边的有向无环图DAG（Directed Acyclic Graph）表示,同时对于每一个节点都标注相应的空间位置属性的标签,如图2所示。
图2 复杂轨迹转为有向无环图

Fig. 2 Complex trajectory represented by directed acyclic graph

针对复杂轨迹构成的有向无环图,本文以图匹配为切入点,利用改进的VF2算法CSM匹配复杂轨迹之间的所有最大同构部分[6]。VF2算法是Cordella等[14]提出的精确图匹配算法,直到现在其仍然是非常常用的高效子图同构算法。VF2算法既可以做图同构（2个图的结构完全相同,如图3（a））,也可以做子图同构（一个图是另一个图的一部分,如图3（b））。但在复杂轨迹中,更多的情况是一个轨迹的部分分支结构与另一条轨迹的部分分支结构相同（图3（c））。借鉴VF2算法的优点[14],Wang等[6]对VF2算法扩展,提出了拓扑结构相似性算法CSM来挖掘2个复杂轨迹的所有最大同构部分,通过与VF2、图编辑方法对比验证了方法的有效性。
图3 结构匹配中的图同构、子图同构、部分同构

Fig. 3 Graph Isomorphism, Subgraph Isomorphism and Partial Isomorphism in the structural matching

但是,拓扑结构相似性算法CSM仅仅是度量复杂轨迹演化结构的相似性,一个完整的相似性还应该包括空间相似性。因此,提出拓扑结构-空间相似性算法STSM来更好地度量复杂轨迹的相似性。STSM算法主要包括2个步骤：拓扑结构匹配和空间距离计算。
（1）拓扑结构匹配是为了最大化找到2个复杂轨迹的所有最大公共结构。其中,结构匹配算法流程如图4所示,对于给定的2个复杂轨迹A和B,其有向图结构为GA和GB,分别设定目标图和查询图的角色,节点数目依次为|GA|和|GB|。①判断2个图结构是否图同构、子图同构、部分同构,并计算目标图A和查询图B之间结构匹配的最大节点数（t1）以及对应的匹配点对集合M1。②由于2个图具有不对称性,交换目标图和查询图的角色,重复上述步骤,输出匹配节点的最大数目（t2）以及对应的匹配点对集合M2。③在图同构情况下,2个复杂轨迹图的节点数目相同即|GA|=|GB|,最大匹配节点数目m为图A或者图B的节点数目,并且t1=t2;在子图同构情况下,即查询图是目标图结构的一部分,最大匹配节点数目m为查询图的节点数目。在部分同构的情况下,最大匹配节点数目m为较大的t1和t2值,并输出相应的最大匹配点对集合M1或者M2。
图4 复杂轨迹结构匹配流程

Fig. 4 Flowchart of complex trajectory structure matching

（2）根据最终输出的匹配点对集合M和最大匹配节点数目m,利用式（3）计算复杂轨迹之间的空间距离,距离越大相似性越小,反之,距离越小相似性越大。即通过各个匹配结构的权重,计算其加权平均值来度量复杂轨迹之间的相似性,某一匹配结构占比越大,这个结构越具有代表性。
对于复杂轨迹A和B,假设有k个匹配的结构W1、W2、W3、…、Wk,一共匹配上了m个节点,sum（W1）、sum（W2）、…sum（Wk）分别表示各个匹配结构中节点之间的欧式距离之和,vi表示第i个匹配结构内的节点个数,则复杂轨迹之间的空间距离为：
dis A , B = sum w 1 v 1 m + sum w 2 v 2 m + … + sum wk vk m m = ∑ i = 1 k sum ( wi ) × vi m 2
对于A、B两条复杂轨迹的第i个匹配上的公共结构,该结构中共有vi个匹配点对,那么该匹配结构中节点之间的欧式距离之和 sum ( wi ) 为：
sum wi = ∑ j = 1 vi d ( A j , B j )
式中： A j 、 B j 分别代表2个复杂轨迹A和B中第i个匹配结构中第j对轨迹点对。
特别地,无论是图同构、子图同构、部分同构,当最大匹配节点数目确定时,相应的匹配点对集合M1或者M2如果存在多个匹配点对结果,那么选择平均欧式距离最小的点对作为最终的匹配结果。
针对本文提出的STSM算法,进一步分析了算法的复杂度。STSM算法源自于VF2算法,虽然进行了节点之间的距离计算,但主要复杂度计算在于节点的匹配过程。假设,2个复杂轨迹的节点总数一致,均为N。VF2的复杂度[14]最好是O（N2）,最差是O（N!N）;本方法的复杂度最好的情况发生在2个图同构,此时复杂度和VF2最好的情况一致,为O（N2）;最差的情况是每次都只能匹配上2个,需要比较N/2次才能把所有的节点匹配完,每匹配一次则减少2个节点,每次匹配时的节点个数为N-2i（i从0开始）,匹配的复杂度为 2 × （N-2i）!。那么,最差复杂度计算为：
N ! × N + N ! × 2 + N - 2 ! × 2 … + 2 ! × 2 = N ! × N + 2 ∑ i = 0 n 2 - 1 N - 2 i ! ≤ N ! × N + 4 N !
因此,STSM算法的最好复杂度是O（N2）,最差复杂度是O（N!（N+4））。
2.2.2 复杂轨迹聚类分析方法
轨迹相似性是轨迹聚类的基础和重要组成部分,基于轨迹相似性的聚类分析可以用于发现动态实体在空间上的聚集模式。本文将提出的复杂轨迹相似性算法STSM应用于层次聚类分析,挖掘复杂轨迹相似的拓扑结构在空间的聚集模式。① 将每一条复杂轨迹当做单独的一个类别cluster,基于本文提出的STSM算法,计算复杂轨迹之间的相异度矩阵。② 利用average-linkage[4]从下而上地合并类簇,即计算2个类簇各自轨迹的两两距离的平均值,反复迭代这一过程,直到所有类合并成一类。average-linkage相比于其他合并方式如：single-linkage/complete-linkage能够考虑类内数据的整体特点,减少局部偏离样本对结果的干扰。③ 利用轮廓系数来评价聚类结果的有效性[16],轮廓系数方法结合了凝聚度和分离度,它衡量的是某个点和所在类点的相似度与其他类点的相似度的比较。将其应用于复杂轨迹聚类结果评价中,在一次聚类结果中,某个复杂轨迹i的轮廓系数定义为：
S i = CTb i - CTa ( i ) max CTa i , CTb i
式中： CTa ( i ) 为复杂轨迹i到同一簇内其他轨迹距离（不相似度）的平均值; CTb i 为复杂轨迹i到其他簇的平均距离（不相似程度）的最小值。这里的距离即STSM算法计算得到的。然后将所有轨迹的轮廓系数求平均,就是该聚类结果总的轮廓系数。轮廓系数的值是介于[-1, 1],越趋近于1代表内聚度和分离度都相对较优。根据轮廓系数找到聚类的合理结果即回答最佳聚类数目是多少的问题。

3 南海冷涡复杂轨迹聚类应用分析

3.1 南海冷涡复杂轨迹数据

本文采用1993-2016年的中国南海冷涡（Cyclonic Eddies, CE）复杂轨迹数据来验证方法的实际应用价值。同时应用了南海涡旋的暖涡和冷涡。但是研究发现暖涡的复杂轨迹的拓扑结构在空间上几乎没有显著的聚集模式,所以重点分析冷涡的聚类结果。涡旋的数据源自海表面高度异常SLA（Sea Level Anomaly）数据集,该数据集的时间分辨率为1 d,空间分辨率为1/3°×1/3°[17]。通过开发和改进的涡旋识别方法和涡旋追踪方法提取复杂轨迹,提取的数据集是经过验证和精度评价的,保证了数据的可靠性[18,19]。
涡旋的分裂可导致涡流变形、物质分散和随后的能量衰减,影响海洋生态系统中的温度、盐度、水体和微生物[20]。涡旋的合并增强不同区域的海水相互作用,在湍流中能量和熵的跨尺度传递中起着重要作用[21]。其他类似的复杂动态现象,如风暴、降雨、溢油事件,它们在空间内移动时,也会发生类似的分裂和合并活动[18,19,20,21,22],可能会产生与海洋涡旋非常相似的复杂轨迹。因此,真实的涡旋复杂轨迹是一个非常恰当的实例来验证方法的实际应用价值。

3.2 南海冷涡聚类结果分析

为了检验基于复杂轨迹相似性计算方法的有效性,本文选择了南海区域冷涡活动周期为28 d以上的730条复杂轨迹展开聚类分析研究（已有研究表明南海中尺度涡旋应该是生命周期在28 d或以上的演化过程[22]）。分别用Wang等[5]提出的拓扑结构相似性算法CSM和本文提出的拓扑结构-空间相似性算法STSM做层次聚类分析,探索冷涡的复杂演化过程在空间的聚集模式。根据轮廓系数评价方法,当CSM、STSM方法的轮廓系数为0.43和0.48时,聚类效果相对其他聚类数目较好,按照轮廓系数剪切层次聚类树状图如图5（a）、5（b）所示,CSM方法和STSM方法分别将730条冷涡复杂轨迹聚成了4类和5类。它们的聚类结果在空间的分布如图6（a）、图6（b）所示。
图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

图6 基于复杂轨迹相似性算法CSM和STSM的聚类结果

Fig. 6 Clustering results based on the two complex trajectory similarity algorithms: CSM versus STSM

图6（a）表明,按照拓扑结构相似性,冷涡的复杂轨迹在南海区域交错叠加,没有显著的聚集模式。而图6（b）表明同时考虑复杂轨迹拓扑结构相似性和空间相似性的聚类结果能够在空间上呈现一定的聚集模式,这一结果表明了单纯用拓扑结构相似性算法CSM进行聚类分析,不能充分挖掘空间的聚集模式,因为不同空间位置也存在拓扑结构相似的轨迹,而本文提出的STSM方法能够有效地发现拓扑结构相似同时在空间聚集的类簇。
本文提出的STSM算法将南海冷涡复杂轨迹分为了5类拓扑结构模式,第一类分布在南海北部（吕宋海峡以西,蓝色轨迹）、第二类分布在南海中部（吕宋岛以西14°N-18°N,绿色轨迹）、其他三类交错在南海南部（越南外海以东,紫色、青色、橘色轨迹）,但南部主要以第三类（紫色）为主。该结果说明南海南部的轨迹演化结构的空间聚集模式相对南海北部和中部更为复杂,表明了南海南部的冷涡移动存在复杂的异质性特征。
为了进一步挖掘丛聚中隐含的时空模式和地理新知,本文从复杂轨迹的拓扑结构模式、活动参数（如冷涡演化过程的活动范围、活动天数、复杂度）、周期模式、移动方向等方面对STSM的聚类结果（图6（b））展开统计分析。
（1）拓扑结构模式和活动特征
首先,探究每个类别中复杂轨迹的拓扑结构模式及其平均活动参数,用字母v、m、s来抽象表达复杂轨迹的结构变化（并不代表具体复杂轨迹过程）。其中v表示普通轨迹点;m表示合并轨迹点; s表示分裂轨迹点,多个连续的普通轨迹点用一个v来表示。那么STSM聚类结果（图6（b））中的各类别的拓扑结构模式及平均活动参数的统计结果如表1所示。
表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
从冷涡的演化结构来看,南海北部（吕宋海峡以西）和南部（越南东南区域）的冷涡以先合并后分裂为主要演化模式,而南海中部则以先分裂后合并为主,这和南海涡旋的产生机制以及地形的变化有关。已有研究表明南海北部和越南以东区域是涡旋的高发区域[23],这2个区域也是涡旋交互最为频繁的区域,而涡旋的频繁交互更容易导致涡旋发生合并。涡旋的分裂通常受地形起伏变化的影响较大,例如Yang等[24]通过建模研究岛屿和海山对涡旋分裂的影响。冷涡在南海中部发生先分裂后合并的模式,这可能与吕宋岛以西的黄岩岛、南海中央海盆、中沙群岛、西沙群岛的复杂地形有关。
从冷涡的复杂轨迹活动参数来看,南海中部（第二类）的复杂轨迹的活动范围最远;南海南部的第四类复杂轨迹活动范围最小,活动时间最短,并且复杂度也较低;南海南部的第五类复杂轨迹的活动时间最长并且复杂度相对较高。这也进一步说明了南海南部的冷涡移动存在复杂移动规律和模式。
（2）时间特征
1993-2016年冷涡在南海北部（第一类）、中部（第二类）、越南以东区域（第三类）均周期性地逐年产生复杂轨迹,这三类平均每年产生7、15、7条冷涡复杂轨迹。从冷涡复杂轨迹逐月出现的数量来看（图7（b））,南海北部（第一类）、南海中部（第二类）在秋、冬季节产生的数量较多,而南海南部（第三类、第四类、第五类）没有显著的季节性特征。南海季风主要因海陆热力差异产生,可分为东北季风期（10月-次年4月）和西南季风期（5月-9月）。由于受到地形影响和狭管效应[25],台湾以南和吕宋岛西北风力相对其他区域较大,尤其是东北季风时期,风应力显著增加。风应力与地形的相互作用可能进一步增强了这些区域的涡流分裂和合并过程。
图7 南海冷涡聚类结果中复杂轨迹逐年、逐月出现数量

Fig. 7 Number of complex trajectory appearance in the clustering results of cyclonic eddies in the South China Sea: by year versus by month

（3）冷涡复杂轨迹的移动特征
本文进一步统计分析了每个类别中冷涡复杂轨迹的主要移动方向,即通过统计每个类别中的每个轨迹点瞬时移动的8个方向（北N、西北NW、东E、东南ES、南S、西南SW、西W、西北NW）来分析每种类别的主要移动趋势。结果如图8所示,南海北部（第一类）主要趋势是西向移动,南海中部（第二类）主要趋势是西南方向移动,南海南部（第三类和第四类）主要趋势是西向移动,但南海南部（第五类）的主要移动趋势是南北方向,其中,南向更为显著。已有研究表明大部分区域的涡旋受β效应的影响西向传播占绝对优势[26],但南海由于地形复杂,如陆架坡、南海中央盆地、中沙群岛、西沙群岛、南沙群岛等,同时,吕宋岛西北和台湾岛西南又受到黑潮入侵的影响[27],越南外海东向急流的不稳定性[28],这些因素会导致不同区域的冷涡移动方向有所差别。本文的结果和已有研究[26,27,28]一致,也进一步揭示了不同区域的冷涡移动特征的差异性。
图8 不同类别的冷涡移动方向统计

Fig. 8 Eight moving directions' statistics of cyclonic eddies per category

4 结论与讨论

4.1 结论

现有的轨迹聚类方法主要是针对没有分支结构的简单轨迹,直接利用轨迹空间相似性或者结合空间距离和运动属性的相似性挖掘轨迹的聚集模式[2,3,4,5],不能满足对具有分支结构的复杂轨迹的聚类模式挖掘。为此,本文针对这类复杂轨迹提出了基于空间-拓扑结构相似性的聚类方法,创新性地融合了复杂轨迹的拓扑结构相似性和空间邻近性,最大限度地挖掘复杂轨迹之间的相似性,并将其应用于层次聚类分析中挖掘拓扑结构相似的轨迹在空间上的聚集模式。实验利用1993-2016年南海冷涡复杂轨迹数据验证了方法的有效性,发现了南海冷涡的复杂演化结构在空间上的一些新的空间分异特征和时空模式。从冷涡的空间演化结构来看,南海北部（吕宋海峡以西）和南部（越南东南区域）的冷涡以先合并后分裂为主要演化模式,而南海中部则以先分裂后合并为主。从时间特征来看,南海北部（第一类）和中部（第二类）的涡旋相比其他区域在秋、冬季节数量更为显著。特别地,从移动特征来看,大部分区域的涡旋受β效应的影响西向传播占绝对优势,而冷涡在越南外海的东南区域（第五类）的南向移动方向的比重最大约占30%,相比南海其他区域,这里的冷涡的移动周期最长（平均值在90天及以上）,演化结构的复杂度也最高（平均值在0.51及以上）,这表明了越南外海的东南区域的冷涡移动存在更为复杂的异质性特征。
虽然已有研究也针对涡旋在南海的移动模式有了一些成果和发现,但是这些研究结果基本上从涡旋的产生位置[29]、涡旋的简单演化轨迹[30]（不考虑分支结构）、涡旋的瞬时移动网络[31]的角度挖掘涡旋产生或简单轨迹的聚集模式,不能有效地发现涡旋的复杂演化过程的移动规律。因此,与现有的南海涡旋的研究成果对比,本文的研究结果更能反映冷涡的复杂演化结构在南海北部、中部、南部区域的聚集模式的差异和新知,如冷涡在南海不同区域的拓扑结构的模式的差异性和在越南外海东南区域的复杂移动特征。由此表明,本文提出的方法可以有效地帮助我们从复杂轨迹数据中发现这类复杂对象的演化活动潜在的聚集特征,为进一步认识这类复杂地理动态现象的时空演化特征与演化机理提供一种新的研究方法。

4.2 讨论

利用本文提出的基于空间-拓扑结构相似性的复杂轨迹聚类方法虽然能够在实际应用中挖掘地理新知,但是也存在一定问题。本文提出的基于空间-拓扑结构相似性的复杂轨迹聚类方法没有融入时间要素,对海洋涡旋等复杂动态现象而言,其活动受到季节性因素的影响,不同的时间可能存在不同的类簇和移动特征,因此在探讨这类复杂动态现象的聚集模式和移动规律时,还需要进一步扩展,在轨迹聚类过程中需要同时考虑物体的拓扑结构、空间位置特征和时间特征。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
李婷, 裴稻, 袁烨城 , 等. 人类活动轨迹的分类、模式和应用研究综述[J]. 地理科学进展, 2014,33(7):938-948.

DOI

[ 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. ]

[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

[ 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. ]

[4]
龚玺, 裴韬, 孙嘉 , 等. 时空轨迹聚类方法研究进展[J]. 地理科学进展, 2011,30(5):522-534.

DOI

[ 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. ]

[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

[7]
Qiu X, Mao Q, Tang Y . Reversed graph embedding resolves complex single-cell trajectories[J]. Nature Methods, 2017,14(10):979-982.

DOI PMID

[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 PMID

[10]
Vaughan N, Gabrys B . Comparing and combining time series trajectories using dynamic time warping[J]. Procedia Computer Science, 2016,96:465-474.

DOI

[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 PMID

[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

[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 PMID

[15]
郭文月, 刘海砚, 孙群 , 等. 面向区域增量更新的等高线群混合相似性度量模型[J]. 地球信息科学学报, 2019,21(2):147-156.

DOI

[ 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. ]

[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 PMID

[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

[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

[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 PMID

[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

[21]
Rodríguez R, Viudez A, Ruiz S . Vortex merger in oceanic tripoles[J]. Journal of Physical Oceanography, 2011,6:1239-1251.

DOI

[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

[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

[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

[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

[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

[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

[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

[30]
吴笛, 杜云艳, 易嘉伟 , 等. 基于密度的轨迹时空聚类分析[J]. 地球信息科学学报, 2015,17(10):1162-1171.

DOI

[ 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. ]

[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. ]

Options
文章导航

/

〈 〉