EN中文

地球信息科学学报 >

2023 , Vol. 25 >Issue 7: 1363 - 1377

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

融合多特征的轨迹数据自适应聚类方法

  • 刘敬一 , 1 ,
  • 彭举 , 2, * ,
  • 唐建波 2 ,
  • 胡致远 2 ,
  • 郭琦 1 ,
  • 姚晨 1 ,
  • 陈金勇 1
展开
  • 1.中国电子科技集团公司第五十四研究所，石家庄 050081
  • 2.中南大学地理信息系，长沙 410083
*彭 举（1997—），女，安徽宿州人，博士生，主要从事时空大数据挖掘研究。E-mail:

刘敬一（1992—），女，河北石家庄人，博士，主要从事时空大数据挖掘与智能应用研究。E-mail:

收稿日期: 2023-02-15

  修回日期: 2023-04-07

  网络出版日期: 2023-06-30

基金资助

中国博士后科学基金项目(2021M703021)

湖南省自然科学基金项目(2021JJ40727)

河北省人才择优自主基金项目(B2021003031)

湖南省自然资源厅科研项目(2013-17)

湖南省自然资源厅科研项目(2014-12)

湖南省自然资源厅科研项目(2015-09)

湖南省自然资源厅科研项目(2017-15)

收起

An Automatic Trajectory Clustering Method Integrating Multiple Features

  • LIU Jingyi , 1 ,
  • PENG Ju , 2, * ,
  • TANG Jianbo 2 ,
  • HU Zhiyuan 2 ,
  • GUO Qi 1 ,
  • YAO Chen 1 ,
  • CHEN Jinyong 1
Expand
  • 1. The 54th Research Institute of China Electronics Technology Group Corporation, Shijiazhuang 050081, China
  • 2. Department of Geo informatics, Central South University, Changsha 410083, China
*PENG Ju, E-mail:

Received date: 2023-02-15

  Revised date: 2023-04-07

  Online published: 2023-06-30

Supported by

China Postdoctoral Science Foundation(2021M703021)

Hunan Provincial Natural Science Foundation of China(2021JJ40727)

Hebei Provincial Independent Fund for Talent Selection(B2021003031)

The Scientific Research Project of Natural Resources Department of Hunan Province(2013-17)

The Scientific Research Project of Natural Resources Department of Hunan Province(2014-12)

The Scientific Research Project of Natural Resources Department of Hunan Province(2015-09)

The Scientific Research Project of Natural Resources Department of Hunan Province(2017-15)

Fold

摘要

轨迹聚类是空间数据挖掘领域的一个研究热点，对城市交通规划、路网结构提取与更新等具有重要意义。轨迹聚类包括轨迹相似性度量和聚类参数设置2个核心问题。然而，由于轨迹的形态结构特征复杂，现有轨迹相似性度量指标存在对噪声敏感或未充分考虑轨迹运动方向一致性的问题，且大多数聚类算法仍需人为设置参数，聚类挖掘结果的质量受到用户主观经验的影响。针对上述问题，本文提出了一种融合多特征的移动轨迹自适应聚类方法。首先，通过融合轨迹的空间邻近性和运动方向特征定义了一种对噪声鲁棒的轨迹相似性度量指标—DSPD距离；在此基础上，通过扩展Ward层次聚类方法提出了一种基于中心轨迹概念的空间层次聚类算法，该算法使用DSPD距离作为相似性度量指标，利用聚类特征曲线自动确定最佳聚类参数。以11组模拟轨迹数据和武汉市真实轨迹数据为例进行实验与分析，结果表明，本文方法在顾及空间邻近性的基础上，可以有效区分不同移动方向的轨迹簇，同时，利用轨迹数据特征自动确定聚类参数，降低了挖掘结果的主观性。

关键词： 轨迹聚类; 相似性度量; 空间邻近性; 方向一致性; 聚类参数; 数据挖掘; 多特征

本文引用格式

刘敬一 , 彭举 , 唐建波 , 胡致远 , 郭琦 , 姚晨 , 陈金勇 . 融合多特征的轨迹数据自适应聚类方法[J]. 地球信息科学学报, 2023 , 25(7) : 1363 -1377 . DOI: 10.12082/dqxxkx.2023.230066

Abstract

Trajectory clustering is a hot research topic in the field of spatial data mining, which is of great significance to many applications such as urban traffic control, road network construction and update. Trajectory clustering involves grouping similar trajectories into clusters where trajectory similarity measurement and clustering parameter setting are two core issues in the process of clustering. However, due to the complex morphological and structural characteristics of trajectories, the existing trajectory similarity measures are sensitive to noise or do not fully consider the consistency of trajectory motion direction. In addition, most clustering algorithms still need to manually set parameters, and the quality of clustering results is affected by the subjective experience of users. To address the above problems, this paper proposes an adaptive trajectory clustering algorithm. The proposed algorithm has two main components: a new trajectory similarity measure called Directed Segment-Path Distance (DSPD) and an improved hierarchical clustering algorithm based on the concept of central trajectory. The DSPD metric is a fusion of the spatial proximity and motion direction features of trajectories, providing a robust similarity measure. The enhanced hierarchical clustering algorithm extends the Ward hierarchical clustering algorithm by defining central trajectories and use the DSPD metric as the trajectory similarity measure. In addition, the proposed algorithm also utilizes the clustering characteristic curve to determine the optimal clustering parameters automatically. This eliminates the need for manual parameter tuning and reduces the subjectivity of clustering results. To evaluate the effectiveness of the proposed algorithm, experiments were conducted on both the simulated datasets and real-world trajectories of Wuhan. We first compared the effect of the DSPD with other commonly used trajectory similarity measures (i.e., Hausdorff distance, Fréchet distance, DTW distance, and LCSS distance) using the same clustering algorithm on the 11 sets of simulated datasets. The evaluation was based on the Adjusted Rand Index (ARI). Then we conducted another comparative analysis to access the effectiveness of the improved clustering algorithm in contrast to an average link-based hierarchical clustering algorithm. Finally, to verify the practicability of the proposed algorithm, we applied it to the process of road network updating. The experimental results show that the proposed DSPD measure outperforms alternative distance metrics on the ARI evaluation indicator. It can effectively distinguish moving trajectory clusters in different directions while considering the spatial proximity of trajectories, thus enhancing the accuracy and effect of the trajectory clustering. Furthermore, the proposed algorithm can significantly reduce the subjectivity of clustering results and provide suggestions for practical applications such as urban road network extraction and update.

Key words： trajectory clustering; similarity measure; spatial proximity; directional consistency; clustering parameters; data mining; multi-features

1 引言

随着导航定位系统、互联网以及传感器等技术的快速发展，各类车载导航仪、GNSS移动终端等得到了广泛应用，从而积累了海量的移动目标（行人、车辆等）运动轨迹数据。这些移动轨迹数据蕴含着丰富的人类出行模式[1-2]和城市道路网络结构及交通状态信息[3-4]，为人地关系建模、城市智能交通管理、路网精细结构提取及实时更新等应用提供了重要的数据源[4⇓⇓⇓-8]。移动轨迹聚类是挖掘海量轨迹数据中蕴含的潜在信息和模式的一类重要分析方法，可以发现具有共同运动特征和时空分布规律的移动对象集合，已经受到国内外学者的广泛关注[9⇓⇓-12]。例如，在交通规划与管理方面，移动轨迹聚类分析已经被成功应用于热点路径识别、最佳出行线路推荐和异常轨迹检测 [13⇓⇓-16]；在地理学与地图制图学领域，移动轨迹聚类分析也已经被应用于居民出行模式分析、用户画像和城市路网结构提取与地图数据的更新[17⇓⇓⇓-21]。
当前，移动轨迹聚类方法多是在空间点聚类方法的基础上，考虑轨迹的空间邻近性和几何形态相似性等特征扩展而来，主要可以分为：① 基于模型的轨迹聚类方法，该方法将轨迹视为由模型（如混合多项式模型）在特定参数下生成的序列样本，通过对整个或部分轨迹进行建模，采用模型的拟合参数来表征轨迹的特征，进而将取得相似拟合参数的轨迹归为同一个聚类[22⇓⇓-25]。但该类方法在确定回归模型以及估计模型参数时较为困难，尤其是针对人类活动轨迹，难以建立简单的模型对轨迹数据进行有效表达；② 基于距离的轨迹聚类方法，该方法将整条轨迹视为一个独立序列，选择常用的序列距离度量指标（如欧氏距离、Hausdorff距离、Fréchet距离、Dynamic Time Warping（DTW）距离、最长公共子序列（LCSS）距离和编辑距离等）计算轨迹间的相似性[26-27]，最后通过K-means/FCM、层次聚类和谱聚类等实现对轨迹的分类[28⇓⇓-31]。基于距离的轨迹聚类方法易于理解和实现，是目前最为常用的一类轨迹聚类方法，但由于轨迹的复杂特征，聚类参数（如簇的数目）选择较为困难。当前针对序列的距离度量指标（如Hausdorff距离、Fréchet距离）对轨迹中存在的噪声点敏感，或不适用于长度不一致的轨迹聚类（如DTW距离）。最长公共子序列距离对噪声具有一定的鲁棒性，且适用于不同长度的轨迹聚类，但该距离指标需要人为设置轨迹点匹配阈值[32-33]； ③ 基于密度的轨迹聚类方法，主要采用密度聚类思想对轨迹数据进行分析，其在密度聚类方法（如DBSCAN、OPTICS算法等）的基础上，通过定义轨迹的空间邻域和密度概念，实现轨迹分布中高密度区域的识别[16,29,34⇓-36]。显然，基于密度的轨迹聚类可以发现复杂形状的聚集模式，但是该类方法亦继承了基于密度的聚类方法的缺陷，即聚类结果对人为参数设置较敏感[37]，较小的参数差异可能导致完全不同的聚类结果。
通过上述分析可以发现，现有轨迹相似性度量指标存在对噪声敏感或未充分考虑轨迹运动方向一致性的问题，且大多数聚类算法仍需人为设置参数，而由于真实轨迹数据分布的复杂性及其隐含模式先验知识的缺失，用户凭借主观经验往往难以选择合适的参数，由此获得的挖掘结果多存在较大的主观性。为了解决上述问题，本文提出了一种融合多特征的轨迹自动聚类方法。首先，提出了融合空间邻近性和方向一致性特征的轨迹相似性度量指标——方向约束的分段路径距离（Directed Segment-Path Distance，DSPD），相比于现有的轨迹相似性度量指标（如Hausdorff距离、Fréchet距离、DTW距离），DSPD距离考虑了轨迹的空间邻近性和运动方向相似性特征，对噪声具有一定的鲁棒性；进一步，基于DSPD距离，提出了一种基于中心轨迹概念的空间层次聚类算法，该方法能够根据轨迹数据的分布特征，自动确定最佳聚类数目，减少人为参数设置的主观性。

2 融合多特征的轨迹相似性度量方法

2.1 轨迹空间邻近性度量

地理学第一定律指出“距离越邻近的事物越相似”[38]。空间邻近性是度量移动轨迹相似性的主要依据。由于移动轨迹的几何形态复杂且轨迹长度存在不一致性，欧式距离无法直接应用于移动轨迹空间邻近性度量，而目前常用的移动轨迹相似性度量指标，如Hausdorff距离、DTW距离、Fréchet距离等存在对噪声数据、轨迹长度差异敏感等问题，无法准确度量移动轨迹间的相似性。为此，本文首先提出了一种改进的轨迹空间邻近性度量指标。为了便于描述，首先给出以下定义。
定义1：点到轨迹的投影距离（Projected Distance，PD）。点到轨迹的投影距离是指一个点到一条轨迹的最短距离[33]，计算公式如下：
d P D ( p , T ) = m i n s i ∈ T d m i n ( p , s i )
式中：p表示一个轨迹点；T表示一条轨迹；si表示T中的子轨迹段；dmin(·)表示点到线段的最短距离。如图1（a）所示，红色线段表示轨迹点pi到T2的投影距离，其中qi为pi在T2上的投影点。
图1 轨迹点投影距离和轨迹分段路径距离

Fig. 1 Illustration of projected distance, segment-path distance

定义2：分段路径距离（Segment-Path Distance，SPD）。分段路径距离是指一条轨迹上各轨迹点到另一条轨迹的投影距离的平均值[33]，具体表达如下：
d S P D ( T 1 , T 2 ) = 1 n 1 ∑ p i ∈ T 1 d P D p i , T 2
式中：T1和T2表示2条轨迹；pi表示轨迹T1中的轨迹点，n1表示轨迹T1中轨迹点的总数目；dPD(pi,T2)表示T1上的轨迹pi到轨迹T2的投影距离。图1（b）显示了分段路径距离的计算示例。
根据以上定义可知，分段路径距离SPD采用轨迹点到另一条轨迹的投影距离的均值度量轨迹距离，一定程度上削弱了噪声点的影响。但由于分段路径距离SPD是一种非对称距离度量，故本文在SPD距离定义的基础上，考虑到轨迹长度可能存在的不一致性，以2条轨迹间SPD距离的最小值作为2条轨迹间空间邻近性的度量指标，具体定义如下：
D s ( T 1 , T 2 ) = m i n { d S P D ( T 1 , T 2 ) , d S P D ( T 2 , T 1 ) }
式中：dSPD(T1,T2)表示轨迹T1到T2的分段路径距离，dSPD(T2,T1)表示轨迹T2到T1的分段路径距离
从式(3)可知，Ds距离满足对称性，且当一条轨迹是另一条轨迹的子轨迹时，Ds=0。如图2所示，对于在同一条路径上共同运动了一段时间的2条轨迹，其长度可能不同（长度不对齐），对于主要关注相似子轨迹或者发现在同一条路径上所有轨迹的研究来说，这2条轨迹应该是相似的。而本文在对度量轨迹间的空间邻近性时，能够较好的顾及存在相似子轨迹的情形，对于诸如移动目标聚集模式挖掘、热点旅游路径提取和最佳出行线路推荐等研究具有重要意义[39⇓-41]。
图2 轨迹T1和子轨迹T2示例

Fig. 2 Illustration of trajectory T1 and sub-trajectory T2

2.2 轨迹方向相似性度量

运动方向是轨迹除空间、时间属性外的另一重要特征，轨迹运动方向一致性对移动轨迹相似性判断具有重要作用。本文在空间邻近性度量的基础上，通过考虑轨迹点的运动方向特征，提出了一种轨迹方向相似性度量方法。该方法的主要思想是：在轨迹空间邻近性度量的基础上，每个轨迹点（如图3中的pi）都可以找到与之相对应的投影点（如图3中的qi），通过计算轨迹点与其对应投影点间运动方向的一致性来度量轨迹整体方向的相似性。本文将各轨迹点的运动方向通过相邻2个轨迹点间的矢量方向近似表示，对于一条含有n个轨迹点的移动轨迹T={(x1, y1), (x2, y2), …, (xn, yn)}，第i个轨迹点pi的运动方向表示为 (δxi, δyi)，计算方式如式（4）所示：
δ x i = ( x i + 1 - x i ) / [ ( x i + 1 - x i ) 2 + ( y i + 1 - y i ) 2 ] 1 / 2 δ y i = ( y i + 1 - y i ) / [ ( x i + 1 - x i ) 2 + ( y i + 1 - y i ) 2 ] 1 / 2     ∀ i < n δ x i = δ x i - 1 ,       δ y i = δ y i - 1     i = n
式中：δxi表示轨迹点(xi, yi)在x轴上的运动方向分量，δyi表示轨迹点(xi, yi)在y轴上的运动方向分量。则轨迹T的运动方向可以表示为序列{(δx1, δy1), (δx2, δy2),…, (δxn, δyn)}。
图3 轨迹点方向计算示例

Fig. 3 Illustration of trajectory point direction calculation

在此基础上，轨迹间的方向相似性度量具体描述如下：
（1）如图3所示，给定2条轨迹T1和T2，设pi为T1上的一个轨迹点，依据式（4）计算轨迹点pi的运动方向(δxi, δyi)，以qi表示轨迹点pi在T2上的投影点，如果qi是T2上的轨迹点，则按照式（4）计算qi的运动方向(δx(i), δy(i))，如果qi不是T2上的轨迹点，则以qi所在轨迹段的矢量方向表示qi的运动方向；
（2）对于轨迹T1上的每个轨迹点pi，计算pi=(xi, yi)与其在轨迹T2上的投影点qi=(xi, yi)运行方向的差异性，具体计算公式如下：
d P R ( p i , T 2 ) = 1 - δ x i δ x ( i ) + δ y i δ y ( i ) δ x i 2 + δ y i 2 δ x ( i ) 2 + δ y ( i ) 2
式中：dPR(pi, T2)表示T1上的轨迹点pi与轨迹T2的运动方向差异性。
进而，计算轨迹T1相对于T2的方向差异性：
d T R ( T 1 , T 2 ) = 1 n 1 ∑ p i ∈ T 1 d P R ( p i , T 2 )
式中：n1表示轨迹T1中轨迹点的总数目。依据上述步骤可计算出T2相对于T1的方向差异性dTR(T2, T1)；
（3）计算2条轨迹T1和T2间移动方向的整体差异性（或相似性）：
D r ( T 1 , T 2 ) = m i n { d T R ( T 1 , T 2 ) , d T R ( T 2 , T 1 ) }
式中：dTP(T1, T2)表示轨迹T1相对于T2的方向差异性；dTP(T2, T1)表示轨迹T2相对于T1的方向差异性；Dr的取值范围为0到2，Dr取值越小表示轨迹T1和T2的运动方向越相似。

2.3 轨迹相似性度量——DSPD距离

空间邻近性和运动方向是移动目标轨迹相似性度量时需要考虑的2个重要特征，考虑到空间邻近性是描述轨迹相似性的主导因素，因此，本文将方向相似性度量作为权值附加到轨迹的空间邻近性度量上，提出了一种顾及方向特征的轨迹相似性度量（Directed Segment-Path Distance，DSPD），具体表达如式（8）所示。
D S P D ( T 1 , T 2 ) = 2 2 - D r ( T 1 , T 2 ) ∙ D s ( T 1 , T 2 )
式中：DSPD(T1, T2)表示轨迹T1和T2间的DSPD距离；Ds表示轨迹间的空间邻近性度量；Dr表示轨迹间的方向相似性度量。其中，Dr的取值范围为0到2，2/(2-Dr(T1,T2))表示轨迹T1和T2之间的方向相似性对空间邻近性的修正权值，该权值随着Dr的增加（方向的不一致性增大）而单调递减。若2条轨迹的运动方向完全相同，即Dr=0，该权值达到最小值1，能够保持轨迹间的空间邻近性；若2条轨迹的运动方向完全相反，即Dr=2，该权值趋向于无穷大，能够最大程度上区分空间邻近但方向不同的移动轨迹。相比于现有的轨迹相似性度量指标[27,42]（如Hausdorff距离、DTW距离、Fréchet距离），DSPD距离同时考虑了轨迹空间邻近性和运动方向特征，且对噪声具有一定的鲁棒性。如图4所示，针对图中所设计的4种类型的模拟轨迹对数据，分别采用Hausdorff距离、DTW距离、Fréchet距离、考虑方向的LCSS距离[43]以及本文提出的DSPD距离度量轨迹间的相似度，结果表明DSPD距离具有较好的鲁棒性，可以有效区分不同方向的轨迹，减少噪声轨迹点对轨迹相似性的影响，在无需设置额外参数的情况下，具有与LCSS距离相似的优点，对噪声不敏感，能够度量轨迹及其子轨迹间的相似性。
图4 不同类型的轨迹对及其相似性度量结果

Fig 4. Illustration of the robustness of the proposed trajectory similarity measurement

3 基于中心轨迹概念的轨迹自适应 聚类

轨迹聚类的另一核心问题是聚类数目的设置，为了解决现有轨迹聚类方法参数设置困难的问题，本文提出了一种基于中心轨迹概念的层次聚类算法，并根据轨迹数据的分布特征自动估计最优的聚类参数。

3.1 基于中心轨迹概念的层次聚类方法

基于Ward距离的层次聚类算法被证明在离散点数据上具有很好的聚类效果[44]，但由于无法计算移动轨迹簇的质心，所以无法直接将该算法应用于轨迹聚类[32-33]。因此，本文借鉴K-mediods聚类算法中定义簇代表点的思想，首先定义中心轨迹的概念，然后扩展Ward层次聚类方法使其适应于移动轨迹聚类。基于此，本文首先给出中心轨迹的定义。
定义3：中心轨迹。给定一个轨迹簇TC = {T1, T2, …, Tm}，中心轨迹mTC是指轨迹簇TC中距离其他轨迹的距离总和最小的轨迹。
m T C = T i | m i n T i ∈ T C ∑ j = 1 , j ≠ i m d ( T i , T j )
式中：m表示轨迹簇TC中的轨迹个数；d(Ti, Tj)表示轨迹Ti和Tj之间的DSPD距离。
基于中心轨迹的概念， 2个轨迹簇间的最小方差距离（Ward距离）定义如下：
D ( T C 1 , T C 2 ) = N 1 N 2 N 1 + N 2 d ( m T C 1 , m T C 2 )
式中：TC1、TC2分别表示2个轨迹簇；N1、N2分别表示2个轨迹簇内的轨迹数目；mTC1、mTC2表示2个轨迹簇的中心轨迹；d()为本文提出的DSPD距离度量指标。
基于上述定义，给定包含N条移动轨迹的数据集S和聚类数目k，基于中心轨迹概念的层次聚类算法流程如算法1所示。
算法1 基于中心轨迹概念的层次聚类算法
Input：
（a）移动轨迹数据集S
（b）聚类数目k
Output：轨迹簇TC1, TC2, …, TCk
1. 将S中的每个轨迹作为单独的簇，记为TC1, TC2, …, TCN，其中N为当前轨迹簇的数目；
2. 根据式（9）计算每个轨迹簇的中心轨迹；
3. 基于各簇的中心轨迹，根据式（10）计算轨迹簇间的Ward距离D(TCi, TCj)（1 ≤ i ≤ N，1 ≤ j ≤ N， j ≠ i）；
4. 合并Ward距离最小的2个轨迹簇，如{TCi, TCj}=TCi（i < j），并删除TCj，使轨迹簇的数目N减1；
5. 重复执行2、3、4步骤，直到当前轨迹簇的数目N为k时停止；
6. 返回最后生成的k个轨迹簇，记为TC1, TC2, …, TCk，算法结束。
该轨迹聚类算法采用DSPD距离作为轨迹间的相似性度量指标，相比于其他轨迹距离度量同时考虑了轨迹的空间邻近性和方向相似性。需要注意的是，虽然该算法最终返回k个轨迹簇，但是由于采取的是自底向上的凝聚聚类策略，所以在聚类的过程中，可以生成聚类数目为k到N的多层次聚类结果。本文轨迹聚类方法的时间复杂度主要包含2部分：① 计算轨迹间的DSPD距离，其时间复杂度约为O(n2)（n为轨迹采样点的平均数目）； ②基于中心轨迹的扩展Ward层次聚类，其时间复杂度约为O(N2logN)[45]（N为轨迹数据中轨迹的总数目）。针对本文提出的基于中心轨迹概念的层次聚类算法，每次迭代时需要重新计算每个簇的中心轨迹，即计算簇中两两轨迹间的距离（轨迹距离相似性矩阵），综合可知，本文提出的基于中心轨迹概念的层次聚类算法的总体时间复杂度约为O(n2N2logN)。

3.2 最优聚类参数估计

层次聚类算法中需要输入聚类数目k作为参数。在层次聚类合并的过程中，最小方差距离具有单调递增的特征，由于相似的实体或子簇之间的距离一般较小，当合并相似的实体或子簇时，最小方差距离增加比较缓慢；当聚类过程中合并了2个不相似的实体或子簇时，合并的代价（即最小方差距离）就会显著增加。因此，通过分析层次聚类过程中最小方差距离的变化特征可为估计最优的聚类参数（聚类数目k）提供重要的参考。
如图5所示，显示了Cross、I5和I5SIM 3个模拟数据分别采用上述的层次聚类算法进行聚类时，最小方差距离（D）与聚类数目（k）之间的关系曲线（以下简称为聚类特征曲线）。
图5 最小方差距离（D）与聚类数目（k）关系曲线

Fig. 5 Relationship curve between minimum variance distance (D) and cluster number (k)

从图5中可以看出，当聚类数目超过数据中真实聚类数目（图中红色圆圈所示位置）时，最小方差距离显著增大，形成一个明显的拐点。为了自动识别聚类特征曲线的拐点，本文采用了Salvador等提出的L-method方法[46]。L-method方法采用2个回归直线段来拟合一条曲线， 2个最优拟合直线段交点的位置记为曲线拐点所在的位置。对于一条特征曲线f = {(x1, y1), (x2, y2), …, (xn, yn)}， L-method方法在点(xi, yi)（2≤i≤n-1）处将曲线分为左右2个部分Lleft = {(x1, y1), (x2, y2), …, (xi, yi)}和Lright = {(xi+1, yi+1), (xi+2, yi+2), …, (xn, yn)}，并分别针对Lleft和Lright进行直线拟合，并计算总的拟合误差：
E ( i ) = i n R M S E ( L l e f t ) + n - i n R M S E ( L r i g h t )
式中：n为拟合曲线的点个数；RMSE(Lleft)表示对Lleft进行直线拟合时的均方根误差；RMSE(Lright)表示对Lright进行直线拟合时的均方根误差。
曲线f上使E(i)取最小值的点(xi, yi)即为曲线的拐点。图6显示了L-method对模拟曲线上拐点的自动识别结果，模拟曲线上的第6个点为曲线的拐点，通过式（11）计算的拟合误差分布如图6（c）所示并在第6个点处取得最小值。
图6 L-method方法识别曲线拐点示例

Fig. 6 Illustration of L-method for identifying curve inflection points

通过L-method方法识别出聚类特征曲线的拐点可初步确定层次聚类参数k的取值（记为k0）。由于最优聚类数目并不一定刚好为k0，而是其附近的取值。为此，本文进一步对聚类数目从（k0-3）（k0-3≥2）到（k0+3）参数下的聚类结果进行有效性评价，结合这些聚类结果的轮廓系数[47]，选择其中轮廓系数最大的聚类结果所对应的聚类数目作为聚类参数k的估计。本文方法根据在层次聚类过程中计算得到的Ward距离，构建Ward距离随聚类数目变化的特征变化曲线，进而使用L-method自动识别曲线中变化显著的拐点，进而自动确定最优的聚类参数，相比于用户通过主观经验来目视判别特征曲线的拐点或聚类评价指标的极值点，该方法能够一定程度上降低聚类结果的主观性和算法参数选择对用户交互的依赖。

4 实验分析与应用

4.1 模拟试验与分析

本节首先采用11组模拟数据集对本文提出的DSPD距离和聚集模式挖掘方法的有效性进行实验分析与验证。实验采用的11组轨迹数据集如图7所示，其中Cross、I5、I5SIM数据集为轨迹相似性度量有效性评价的公开标准数据集[29]， Cross数据集模拟了道路交叉口处的车辆轨迹， I5数据集模拟了不同车道的轨迹数据， I5SIM数据集模拟了含有噪声的轨迹数据；T1、T2、T3、T4数据集是选取的武汉市2015年5月1日出租车的真实轨迹数据（平均采样间隔48 s）； I5-direct、I5SIM-direct、T1-direct、T2-direct数据集是在I5、I5SIM、T1、T2数据集的基础上模拟了包含不同移动方向的轨迹数据。图中不同的颜色表示不同的轨迹簇。
图7 模拟轨迹数据

Fig. 7 Simulated trajectory datasets with different clusters in different colors

首先，为了验证本文提出的DSPD距离的有效性，采用层次聚类（Average-linkage算法）[48]和相同的聚类参数（簇数目）对11组模拟数据进行聚类，分别以Hausdorff距离[49]、Fréchet距离[50]、DTW距离[51]、LCSS距离[52]和本文提出的DSPD距离作为相似性度量指标，计算基于不同相似性度量指标得到的聚类结果的ARI指数[53]，结果如表1所示。其中，由于基于LCSS距离的聚类时需要设置距离相似阈值ε，本文在实验时ε分别取2、5、10、15、20、25、30 m，然后从中选取最优的聚类结果。
表1 不同相似性度量指标下模拟轨迹数据的聚类结果的有效性评价

Tab. 1 Validity evaluation of cluster results for simulated trajectory datasets under different similarity metrics

簇数/个 Hausdorff Fréchet DTW LCSS DSPD
Cross 19 0.993 0.996 0.939 0.841 0.896
I5 8 0.387 0.388 0.669 0.962 0.987
I5SIM 8 1.000 1.000 1.000 1.000 1.000
T1 7 0.466 0.575 0.575 0.948 0.885
T2 5 0.578 0.775 0.747 0.983 1.000
T3 10 0.621 0.665 0.809 0.953 0.960
T4 10 0.831 0.679 0.712 0.833 0.993
I5-direct 11 0.194 0.297 0.460 0.814 0.839
I5SIM-direct 12 0.874 1.000 1.000 1.000 1.000
T1-direct 10 0.545 0.589 0.651 0.988 0.957
T2-direct 9 0.602 0.660 0.570 0.963 0.975
平均精度 - 0.645 0.693 0.739 0.935 0.954
观察表1中采用不同相似性度量指标对模拟数据的聚类结果的ARI指数可知，在相同的聚类算法和聚类参数下，采用本文提出的DSPD距离作为轨迹相似性度量指标时，聚类结果的总体精度优于Hausdorff距离、Fréchet距离、DTW距离和LCSS距离。其中，基于LCSS距离的T1和T1-direct轨迹数据聚类结果优于本文基于DSPD距离的聚类结果，主要原因是T1和T1-direct轨迹数据中存在两个轨迹簇（图中绿色轨迹簇和黑色轨迹簇）在几何形态、空间位置和运动方向上都具有相似性，且其中大部分轨迹存在相互重叠，仅在局部区域不一致，因此基于DSPD距离的聚类将T1和T1-direct数据集中的2个轨迹簇识别为了一个簇，而基于LCSS距离的聚类结果是在多个阈值参数ε下选取了最优的聚类结果，且当ε设置不合理（如ε<5 m时），T1和T1-direct数据集中即使属于同一簇内的轨迹，其相似性也很低。
进一步，为了验证本文提出的基于中心轨迹的层次聚类算法的有效性，以DSPD距离为相似性度量指标，采用本文所提的方法对11组模拟数据进行聚类，聚类结果如图8所示，可以看出本文方向能够有效识别11组模拟数据集中的移动簇。另外，采用ARI指数[53]定量评价各组模拟数据聚类结果的有效性，聚类参数k基于前文提出的最优聚类参数估计方法进行设置，结果如表2所示。
图8 模拟数据的聚类结果

Fig. 8 Clustering results by the proposed method with different clusters in different colors

表2 模拟轨迹数据聚类结果的有效性评价

Tab. 2 Validity evaluation of cluster results for simulated trajectory datasets

模拟数据 簇数/个 聚类参数k估计值 ARI 模拟数据 簇数/个 聚类参数k估计值 ARI
Cross 19 16 0.852 T4 10 10 0.993
I5 8 8 0.993 I5-direct 11 10 0.961
I5SIM 8 8 1.000 I5SIM-direct 12 12 1.000
T1 7 7 0.912 T1-direct 8 8 0.861
T2 5 5 1.000 T2-direct 9 8 0.965
T3 10 11 0.982
通过表2所示的结果可知，与基于平均连接法的层次聚类结果相比（表1最后一列），本文所提的基于中心轨迹的层次聚类算法的ARI值相对更高，具有更好的聚类效果。其中，Cross数据集的聚类精度相比其他数据较低，主要原因是本文方法低估了数据中真实聚类的数目，导致聚类中部分轨迹簇被错误合并。进一步观察Cross数据集中被错误合并的轨迹簇，如图9所示，可以发现，这些被错误合并的轨迹簇在几何形态、空间位置和运动方向上都具有很高的相似性，且其中一部分轨迹存在相互重叠的情况，因此在合并这些轨迹簇时，最小方差距离未出现显著的增加，导致低估了数据中真实簇的个数。对于Cross数据集，在聚类数目正确估计的前提下（k=19），本文提出的基于中心轨迹概念的层次聚类算法的聚类精度为0.970，优于基于平均连接的层次聚类算法（0.896）。
图9 Cross数据集中被错误合并的轨迹簇

Fig. 9 Incorrectly merged trajectory clusters in Cross dataset

4.2 实际应用与分析

轨迹数据是移动对象在城市道路上移动留下的历史记录，可实时感知城市路网的结构与变化信息，为城市路网变化检测与动态更新提供了重要数据源。在基于轨迹数据的路网结构提取与变化更新应用中，移动轨迹聚类是从轨迹数据中提取路网结构进而进行路网更新的一个重要步骤。为进一步验证本文提出的轨迹聚类算法的实用性和有效性，以武汉市青山城郊附近的一个开发区为研究区域开展应用分析，如图10（a）所示。实验数据采用该区域2015年5月1日出租车轨迹数据和2013年OpenStreetMap（OSM）下载的矢量路网数据，轨迹数据采样间隔为30~180 s，共包含10 662条轨迹，原始路网数据共包含295条主干道。通过车辆轨迹数据（2015年）对该区域路网数据（2013年）的变化信息进行提取与更新。
图10 研究区域和实验数据

Fig. 10 Study area and experimental data

由于信号遮挡等原因，原始轨迹数据中包含了大量的异常轨迹点。根据轨迹长度、车辆运动状态特征等建立下列规则对原始轨迹数据中的异常轨迹进行剔除： ①删除轨迹长度小于100 m的轨迹； ② 删除轨迹数据中速度小于5 km/h或者大于 100 km/h的轨迹点；③ 删除连续转向超过45度的轨迹（频繁掉头的轨迹），经过清理后的轨迹数据如图10（b）所示。
进一步，将轨迹数据与已有路网数据进行地图匹配识别城市路网中的变化区域，其中未匹配的轨迹即为道路发生变化的区域。本文轨迹与路网匹配采用文献[54]中介绍的HMM地图匹配算法。针对未匹配的轨迹，计算未匹配轨迹的最小外接矩形（图11（a）所示），将最小外接矩形具有重叠区域的未匹配轨迹进行合并，作为同一个待更新区域，如图11（b）所示。进而，针对不同的待更新区域内的未匹配轨迹，采用本文提出的轨迹聚集模式自动挖掘方法进行轨迹聚类，得到轨迹聚类结果如图11（c）所示。从图中可以看出，路网中新增（或变化）的道路以轨迹簇的形式很好地被识别，针对同一区域内存在多条道路变化的情况，通过本文聚类方法可以很好地将属于不同道路和不同通行方向上的轨迹进行划分。
图11 轨迹聚集模式挖掘结果

Fig. 11 Results of the detected trajectory clusters

进一步，针对识别的每个轨迹簇，采用主曲线拟合算法[55]提取道路中心线，并将提取的变化道路中心线与原始路网进行叠加、融合，最终研究区域的路网更新结果如图12（a）所示，其中蓝色线条表示更新的道路。图12（b）和（c）分布显示了目前常用的基于车辆轨迹数据的路网更新方法（即基于栅格化的方法[56]和基于PAM聚类的局部更新方法[57]的道路变化识别结果。通过对比遥感图像与人眼识别结果发现，本方法能够有效识别出研究区域内的新增（或变化）道路；基于栅格化的方法虽然能够识别大部分的道路变化，但其提取的道路结构较粗糙，且存在较多毛刺；基于PAM聚类的局部更新方法可以很好地提取单条变化道路，但当区域内存在多条变化道路的情形时，该方法无法准确构建完整路网结构。
图12 研究区域内路网更新结果

Fig. 12 Road network update results in the study area

5 结论

针对当前轨迹相似性度量指标与轨迹聚类方法对噪声敏感、聚类参数选择困难等不足，本文提出了一种融合多特征的轨迹自动聚类算法。首先，通过融合轨迹的空间邻近性和方向特征，提出了一种对噪声鲁棒的轨迹相似性度量指标——DSPD距离；在此基础上，通过扩展Ward层次聚类方法提出了一种基于中心轨迹概念的层次聚类方法，聚类过程中采用DSPD距离度量轨迹间的相似性；最后，通过识别最小方差距离与聚类数目的特征关系曲线中拐点的位置自动地确定最优聚类数目。在11组模拟数据集和真实武汉轨迹数据上的实验表明，在相同的聚类算法条件下，使用本文提出的DSPD距离得到的ARI精度优于使用其他距离得到的聚类结果，且能够有效区分不同运动方向的移动轨迹。同时，在使用相同的轨迹相似性度量指标（DSPD距离）的条件下，本文提出的聚类算法得到的ARI精度优于基于平均连接距离的层次聚类算法的聚类结果，具有良好的聚类效果。该算法通过轨迹数据特征自动确定聚类参数，减少了人为设置聚类参数对聚类结果的主观影响，可为城市路网结构提取与变化更新、运动模式挖掘等应用提供有益参考。此外，本文提出的轨迹聚类方法除了在基于轨迹数据的城市路网结构提取与更新方面具有应用价值外，还可以与其他算法进行结合，应用于人群移动模式挖掘（如热点路径识别、异常轨迹探测等）。
本研究仍存在以下2个方面的不足：① 本文在度量移动轨迹相似性时主要考虑了轨迹的空间位置和运动方向特征，没有考虑移动目标运动的时间特征和语义特征； ②在应用于大规模轨迹数据聚类时，需要进一步提高算法的运行效率。针对上述不足，未来进一步的研究工作将主要包括： ① 考虑移动目标轨迹在时间维度和语义层面上的特征，挖掘移动目标在空间上邻近、时间上同现、语义上相似的聚集模式； ② 在计算轨迹簇的距离相似性矩阵时，采用分布式计算提高算法的运行效率，使其能够有效应用于大规模移动轨迹数据聚类。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Huang Y R, Xiao Z, Wang D, et al. Exploring individual travel patterns across private car trajectory data[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(12):5036-5050. DOI:10.1109/TITS.2019.2948188

DOI

[2]
Liu B J, Deng M, Yang J Y, et al. Detecting anomalous spatial interaction patterns by maximizing urban population carrying capacity[J]. Computers, Environment and Urban Systems, 2021, 87:101616. DOI:10.1016/j.compenvurbsys.2021.101616

DOI

[3]
Yuan J, Zheng Y, Zhang C Y, et al. T-drive: Driving directions based on taxi trajectories[C]// Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2010:99-108. DOI:10.1145/1869790.1869807

DOI

[4]
Yang X, Tang L L, Stewart K, et al. Automatic change detection in lane-level road networks using GPS trajectories[J]. International Journal of Geographical Information Science, 2018, 32(3):601-621. DOI:10.1080/13658816.2017.1402913

DOI

[5]
郑宇. 城市计算概述[J]. 武汉大学学报·信息科学版, 2015, 40(1):1-13.

[Zheng Y. Introduction to urban computing[J]. Geomatics and Information Science of Wuhan University, 2015, 40(1):1-13.] DOI:10.13203/j.whugis20140718

DOI

[6]
Mazimpaka J D, Timpf S. Trajectory data mining: A review of methods and applications[J]. Journal of Spatial Information Science, 2016, 2016(13):61-99. DOI:10.5311/josis.2016.13.263

DOI

[7]
刘瑜, 康朝贵, 王法辉. 大数据驱动的人类移动模式和模型研究[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.] DOI:10.13203/j.whugis20140149

DOI

[8]
Tang J B, Deng M, Huang J C, et al. An automatic method for detection and update of additive changes in road network with GPS trajectory data[J]. ISPRS International Journal of Geo-Information, 2019, 8(9):411. DOI:10.3390/ijgi8090411

DOI

[9]
Yuan G, Sun P H, Zhao J, et al. A review of moving object trajectory clustering algorithms[J]. Artificial Intelligence Review, 2017, 47(1):123-144. DOI:10.1007/s10462-016-9477-7

DOI

[10]
Wang S, Bao Z F, Culpepper J S, et al. A survey on trajectory data management, analytics, and learning[J]. ACM Computing Surveys, 2022, 54(2):1-36. DOI:10.1145/344 0207

DOI

[11]
Ansari M Y, Mainuddin, Ahmad A, et al. Spatiotemporal trajectory clustering: A clustering algorithm for spatiotemporal data[J]. Expert Systems with Applications, 2021, 178:115048. DOI:10.1016/j.eswa.2021.115048

DOI

[12]
牟乃夏, 徐玉静, 张恒才, 等. 移动轨迹聚类方法研究综述[J]. 测绘通报, 2018, 0(1):1-7.

DOI

[Mou N X, Xu Y J, Zhang H C, et al. A review of the mobile trajectory clustering methods[J]. Bulletin of Surveying and Mapping, 2018, 10(1):1-7.] DOI:10.13474/j.cnki.11-2246.2018.0001

DOI

[13]
Chen Z B, Shen H T, Zhou X F. Discovering popular routes from trajectories[C]// 2011 IEEE 27th International Conference on Data Engineering. IEEE, 2011:900-911. DOI:10.1109/ICDE.2011.5767890

DOI

[14]
Qu B T, Yang W X, Cui G, et al. Profitable taxi travel route recommendation based on big taxi trajectory data[J]. IEEE Transactions on Intelligent Systems, 20 Transportation 20, 21(2):653-668. DOI:10.1109/TITS.2019.2897776

DOI

[15]
朱燕, 李宏伟, 樊超, 等. 基于聚类的出租车异常轨迹检测[J]. 计算机工程, 2017, 43(2):16-20.

[ Zhu Y, Li H W, Fan C, et al. Clustering-based taxi trajectory outlier detection[J]. Computer Engineering, 2017, 43(2):16-20.] DOI: 10.3969/j.issn.1000-3428.2017.02.003

DOI

[16]
Shi Y, Wang D, Tang J B, et al. Detecting spatiotemporal extents of traffic congestion: A density-based moving object clustering approach[J]. International Journal of Geographical Information Science, 2021, 35(7):1449-1473. DOI: 10.1080/13658816.2021.1905820

DOI

[17]
代维秀, 陈占龙, 谢鹏. 居民出行与轨迹行为交互模式挖掘与关联技术[J]. 测绘学报, 2021, 50(4):532-543.

DOI

[Dai W X, Chen Z L, Xie P. Research on the interactive mode of residents' behavior based on trajectory data mining[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(4):532-543.] DOI:10.11947/j.AGCS.2021.20200072

DOI

[18]
Shen J N, Cheng T. A framework for identifying activity groups from individual space-time profiles[J]. International Journal of Geographical Information Science, 2016, 30(9):1785-1805. DOI:10.1080/13658816.2016.1139119

DOI

[19]
杨伟, 艾廷华. 运用约束Delaunay三角网从众源轨迹线提取道路边界[J]. 测绘学报, 2017, 46(2):237-245.

DOI

[ Yang W, Ai T H. The extraction of road boundary from crowdsourcing trajectory using constrained delaunay triangulation. Acta Geodaetica et Cartographica Sinica, 2017, 46(2):237-245.] DOI:10.11947/j.AGCS.2017.20160233

DOI

[20]
李渊, 郭晶, 陈一平. 基于多源数据的旅游者视觉行为模式与感知评估方法[J]. 地球信息科学学报, 2022, 24(10):2004-2020.

DOI

[Li Y, Guo J, Chen Y P. A new approach for tourists' visual behavior patterns and perception evaluation based on multi-source data[J]. Journal of Geo-Information Science, 2022, 24(10):2004-2020.] DOI:10.12082/dqxxkx.2022.210840

DOI

[21]
杨伟, 艾廷华. 基于车辆轨迹大数据的道路网更新方法研究[J]. 计算机研究与发展, 2016, 53(12):2681-2693.

[Yang W, Ai T H. A method for road network updating based on vehicle trajectory big data[J]. Journal of Computer Research and Development, 2016, 53(12):2681-2693.] DOI: 10.7544/issn1000-1239.2016.20160610

DOI

[22]
Gaffney S, Smyth P. Trajectory clustering with mixtures of regression models[C]// Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining. New York: ACM, 1999:63-72. DOI: 10.1145/312129.312198

DOI

[23]
Chamroukhi F, Mohammed S, Trabelsi D, et al. Joint segmentation of multivariate time series with hidden process regression for human activity recognition[J]. Neurocomputing, 2013, 120:633-644. DOI:10.1016/j.neucom.2013.04.003

DOI

[24]
Thrun M C. The exploitation of distance distributions for clustering[J]. International Journal of Computational Intelligence and Applications, 2021, 20(3):2150016. DOI: 10.1142/s1469026821500164

DOI

[25]
Hu W M, Li X, Tian G D, et al. An incremental DPMM-based method for trajectory clustering, modeling, and retrieval[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(5):1051-1065. DOI:10.1109/TPAMI.2012.188

DOI PMID

[26]
Zhang Z, Huang K Q, Tan T N. Comparison of similarity measures for trajectory clustering in outdoor surveillance scenes[C]// 18th International Conference on Pattern Recognition (ICPR'06). IEEE, 2006, 3:1135-1138. DOI: 10.1109/ICPR.2006.392

DOI

[27]
Toohey K, Duckham M. Trajectory similarity measures[J]. SIGSPATIAL Special, 2015, 7(1):43-50. DOI:10.1145/2782759.2782767

DOI

[28]
Atev S, Miller G, Papanikolopoulos N P. Clustering of vehicle trajectories[J]. IEEE Transactions on Intelligent Transportation Systems, 2010, 11(3):647-657. DOI:10.1109/TITS.2010.2048101

DOI

[29]
Wang L H, Chen P F, Chen L Y, et al. Ship AIS trajectory clustering: An HDBSCAN-based approach[J]. Journal of Marine Science and Engineering, 2021, 9(6):566. DOI: 10.3390/jmse9060566

DOI

[30]
Ossama O, Mokhtar H M O, El-Sharkawi M E. An extended k-means technique for clustering moving objects[J]. Egyptian Informatics Journal, 2011, 12(1):45-51. DOI:10.1016/j.eij.2011.02.007

DOI

[31]
Pelekis N, Kopanakis I, Kotsifakos E E, et al. Clustering uncertain trajectories[J]. Knowledge and Information Systems, 2011, 28(1):117-147. DOI:10.1007/s10115-010-0316-x

DOI

[32]
Morris B, Trivedi M. Learning trajectory patterns by clustering: Experimental studies and comparative evaluation[C]// 2009 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2009:312-319. DOI:10.1109/CVPR.2009.5206559

DOI

[33]
Besse P C, Guillouet B, Loubes J M, et al. Review and perspective for distance-based clustering of vehicle trajectories[J]. IEEE Transactions on Intelligent Transportation Systems, 2016, 17(11):3306-3317. DOI:10.1109/TITS.2016.2547641

DOI

[34]
Nanni M, Pedreschi D. Time-focused clustering of trajectories of moving objects[J]. Journal of Intelligent Information Systems, 2006, 27(3):267-289. DOI:10.1007/s10844-006-9953-7

DOI

[35]
Liu Q L, Deng M, Shi Y, et al. A density-based spatial clustering algorithm considering both spatial proximity and attribute similarity[J]. Computers & Geosciences, 2012, 46:296-309. DOI:10.1016/j.cageo.2011.12.017

DOI

[36]
Deng Z, Hu Y Y, Zhu M, et al. A scalable and fast OPTICS for clustering trajectory big data[J]. Cluster Computing, 2015, 18(2):549-562. DOI:10.1007/s10586-014-0413-9

DOI

[37]
Izakian Z, Saadi Mesgari M, Abraham A. Automated clustering of trajectory data using a particle swarm optimization[J]. Computers, Environment and Urban Systems, 2016, 55:55-65. DOI:10.1016/j.compenvurbsys.2015.10.009

DOI

[38]
Tobler W R. A computer movie simulating urban growth in the Detroit region[J]. Economic Geography, 1970, 46:234-240. DOI:10.2307/143141

DOI

[39]
Lee J G, Han J W, Whang K Y. Trajectory clustering: A partition-and-group framework[C]// Proceedings of the 2007 ACM SIGMOD international conference on Management of data. New York: ACM, 2007:593-604. DOI: 10.1145/1247480.1247546

DOI

[40]
Zheng K, Zheng Y, Yuan N J, et al. Online discovery of gathering patterns over trajectories[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8):1974-1988. DOI:10.1109/TKDE.2013.160

DOI

[41]
Gao M, Shi G Y. Ship-handling behavior pattern recognition using AIS sub-trajectory clustering analysis based on the T-SNE and spectral clustering algorithms[J]. Ocean Engineering, 2020, 205:106919. DOI:10.1016/j.oceaneng.2020.106919

DOI

[42]
Tao Y G, Both A, Silveira R I, et al. A comparative analysis of trajectory similarity measures[J]. GIScience & Remote Sensing, 2021, 58(5):643-669. DOI:10.1080/1548 1603.2021.1908927

DOI

[43]
Deng M, Huang J C, Zhang Y F, et al. Generating urban road intersection models from low-frequency GPS trajectory data[J]. International Journal of Geographical Information Science, 2018, 32(12):2337-2361. DOI:10.1080/13658816.2018.1510124

DOI

[44]
Guo D S, Wang H. Automatic region building for spatial analysis[J]. Transactions in GIS, 2011, 15:29-45. DOI: 10.1111/j.1467-9671.2011.01269.x

DOI

[45]
Vijaya, SharmaS,Batra N. Comparative study of single linkage, complete linkage, and ward method of agglomerative clustering[C]// 2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COMITCon). IEEE, 2019:568-573. DOI:10.1109/COMITCon.2019.8862232

DOI

[46]
Salvador S, Chan P. Determining the number of clusters/segments in hierarchical clustering/segmentation algorithms[C]// 16th IEEE International Conference on Tools with Artificial Intelligence. IEEE, 2004:576-584. DOI: 10.1109/ICTAI.2004.50

DOI

[47]
Rousseeuw P J. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis[J]. Journal of Computational and Applied Mathematics, 1987, 20:53-65. DOI:10.1016/0377-0427(87)90125-7

DOI

[48]
Cohen-addad V, Kanade V, Mallmann-trenn F, et al. Hierarchical clustering: Objective functions and algorithms[J]. Journal of the ACM, 2019, 66(4):1-42. DOI:10.1145/3321386

DOI

[49]
Chen J Y, Wang R D, Liu L X, et al. Clustering of trajectories based on Hausdorff distance[C]// 2011 International Conference on Electronics, Communications and Control (ICECC). IEEE, 2011:1940-1944. DOI:10.1109/ICECC.2011.6066483

DOI

[50]
Alt H, Godau M. Computing the Fréchet distance between two polygonal curves[J]. International Journal of Computational Geometry & Applications, 1995, 5(01n02):75-91. DOI:10.1142/s0218195995000064

DOI

[51]
Vlachos M, Kollios G, Gunopulos D. Discovering similar multidimensional trajectories[C]// Proceedings 18th International Conference on Data Engineering. IEEE, 2002:673-684. DOI:10.1109/ICDE.2002.994784

DOI

[52]
Berndt D J, Clifford J. Using dynamic time warping to find patterns in time series[C]// KDD workshop. 1994, 10:359-370. DOI:10.5555/3000850.3000887

DOI

[53]
Hubert L, Arabie P. Comparing partitions[J]. Journal of Classification, 1985, 2(1):193-218. DOI:10.1007/BF01908075

DOI

[54]
吴涛, 向隆刚, 龚健雅. 路网更新的轨迹-地图匹配方法[J]. 测绘学报, 2017, 46(4):507-515.

DOI

[Wu T, Xiang L G, Gong J Y. Renewal of road networks using map-matching technique of trajectories[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(4):507-515.] DOI:10.11947/j.AGCS.2017.20150479

DOI

[55]
Hastie T, Stuetzle W. Principal curves[J]. Journal of the American Statistical Association, 1989, 84(406):502-516. DOI: 10.1080/01621459.1989.10478797

DOI

[56]
Zhao Y, Liu J, Chen R Q, et al. A new method of road network updating based on floating car data[C]// 2011 IEEE International Geoscience and Remote Sensing Symposium. IEEE, 2011:1878-1881. DOI:10.1109/IGARSS.2011.6049490

DOI

[57]
Wu T, Xiang L G, Gong J Y. Updating road networks by local renewal from GPS trajectories[J]. ISPRS International Journal of Geo-Information, 2016, 5(9):163. DOI: 10.3390/ijgi5090163

DOI

Options
文章导航

/

〈 〉