随着信息技术的发展以及移动通信设备等记录GPS轨迹数据的工具的普及，更为细致和丰富的出行轨迹信息被大量记录下来。将人们的出行GPS轨迹数据进行采集、处理并根据停留点特征深入挖掘轨迹的语义信息，是了解个体轨迹特征的重要方式，能够帮助了解人们的出行需求及行为方式，发现城市居民的出行动态，发掘人的移动性规律，指导以人为本的城市交通建设，因此具有重要的研究意义。但是，GPS轨迹数据的增多、用户的出行方式多样化以及出行目的复杂性使得对于出行轨迹数据的识别存在困难，已有的识别方法在面对当前轨迹数据的复杂性与多维性的时候越来越难以实现既定的目的。因此，需要更为准确的停留点识别方法，以进一步挖掘轨迹数据所蕴含的深层语义信息，为更为丰富的上层应用提供支撑。

目前，停留点识别的方法分为3类：基于聚类策略的方法、基于概率策略的方法和基于区分策略的方法。

基于聚类策略的方法方面，吕志娟^[1]提出的个人轨迹模式挖掘算法能够获得细腻的轨迹数据信息，但是这要花费更多的时间，并且还会引入更高比例的噪声。Jiang等^[2]提出的两步法能够有效的聚集并合成接近真实的语义数据，效率高但准确性有待提高。张文元等^[3]的算法简单高效，但不适应于密度分布不均的数据集。杨震等^[4]的方法提高了预测准确率的同时也具有良好的普适性与多步预测性能。石陆魁等^[5]提出的基于时空模式的轨迹数据聚类算法因同时兼顾了轨迹的空间和时间特征，因此在轨迹时空聚类中有更好的描述，但因为加入了时间度量使得聚类的效率有所降低。Fu ^[6]等提出的两步聚类算法能够大大降低GPS信号丢失和数据漂移的影响，并识别独特的位置。算法的搜索速度快但不是自动的，并且需要一些先验参数。Xiang ^[7]等提出的基于序列方式的聚类算法考虑了轨迹的连续性和持续时间，聚类抗噪声能力强，但仅限序列合并数据。此外，Lei Gong^[8]在2015年提出的算法C-DBSCAN对停留点的识别准确率达到90%，但是算法的约束条件方向变化约束存在极大缺陷，即可能适用于识别数据点频率较高的连续GPS轨迹数据，然而只要轨迹点停止或变化较小，算法约束条件就无法有效进行识别。Lei Gong在2018年的改进算法利用到熵^[10]的原理。因此预测精度有一定提升，但是该约束也有一定缺陷，即停止的轨迹点或者移速较慢的轨迹点不一定是活动点，它们可能是等车或者是交通道路堵塞的点。

基于概率策略的方法方面，张鹏^[11]提出的数据挖掘算法能够获得一定的用户出行行为特征，但模型的网络资源利用率还需要有效提高。向隆刚等^[12]提出的核密度算法兼顾停留的识别完整性和准确性，可以有效识别复杂多样的轨迹数据，识别准确率高但抗噪声能力不强。Liao 等^[13]提出的条件随机场算法考虑轨迹的前后信息，能够获得重要的出行轨迹数据。该算法考虑的地方较多，因此预测结果会产生很多不可预估的问题。

基于区分策略方法方面，李毓瑞等^[14]提出的基于密度的停留点识别方法能够很好地找到特定的停留点，但是这种方法并不能找到所有的停留点。杜润强^[15]提出的停驻点识别方法有效的避免了常规停留点的识别错误，使得停驻点的识别更合理，但这种仿真式的识别算法在处理轨迹数据噪声上存在一定的问题。HERDER等^[16]提出的旅游推荐算法能够获得用户的访问信息并且及时给予用户一定的推荐，但该技术并没有发展成熟。

时空语义^[17-18]为停留点的识别提供了新的思路，但是，现有的基于时空语义的轨迹点识别方法以经纬度加上时间戳直接进行聚类分段，聚类后的轨迹段虽然考虑了时间的特征，但是时间戳的差异导致轨迹段的细散化，使得轨迹段的特征不明显，不利于后续的识别。

因此，本文从停留点的识别出发，基于时空约束密度聚类的停留点识别算法对个体出行轨迹进行停留点的识别。针对方法中采用了轨迹的间接时空表示：两点间的距离和平均速度，这既保留了轨迹的时空特征，又减少了轨迹段的分散程度，能够保留停留点和移动点的特征差异。在轨迹段的识别阶段，因为考虑了轨迹点的速度和距离等特征，同时也提出了3种约束方法，使得轨迹点的识别更加细腻化，提高了识别性能的同时还能够挖掘更多更深层次的轨迹信息。

1 基于DBSCAN算法的停留点识别方法

本节对密度聚类算法DBSCAN(density-based spatial clustering of applications with noise)进行介绍，在DBSCAN算法的基础上详细说明改进的ST_DBSCAN算法，实验将根据ST_DBSCAN算法聚类得到的轨迹段进行约束与识别，最终识别停留点和移动点。

1.1 DBSCAN算法

DBSCAN引入了密度可达和密度相连的概念，将密度大于给定阈值的点作为核心点，所有相互可达的点作为一个聚类，不属于任何一个类的点作为噪声数据，因此可以将一个基于密度的簇看作是密度相连的点的最大集合。算法的优点在于可以识别形状复杂的聚类，不受噪声的干扰，而且聚类的结果不受数据输入顺序的影响。缺点是对于定义的参数Eps和MinPts敏感，而且通常很难准确的确定该聚类参数，因此不适于高维数据集。DBSCAN定义如下：

Ε邻域：给定对象半径为Ε内的区域称为该对象的Ε邻域。

核心对象：如果给定对象Ε邻域内的样本点数大于等于MinPts，则称该对象为核心对象。

直接密度可达：对于样本集合D，如果样本点q在p的Ε邻域内，并且p为核心对象，那么对象q从对象p直接密度可达。

密度可达：对于样本集合D，给定一串样本点p₁,p₂,···,p_n,p=p₁,q=p_n，假如对象p_i从p_i−1直接密度可达，那么对象q从对象p密度可达。

密度相连：存在样本集合D中的一点o，如果对象o到对象p和对象q都是密度可达的，那么p和q密度相联。

1.2 ST_DBSCAN算法

为了表达某些时空序列的时间特征，在DBSCAN算法基础上加入了时间维度，让一个点仅考虑它设定一定时间长度内的点，因此能够识别一些来回移动且密度比较大的簇；输入的数据不再是经纬度转换的空间距离特征，而是一个点到下一点的距离以及平均速度特征，这比仅考虑点与点之间的空间距离特征，有更好的特征选择。因此，相对于原始的DBSCAN算法，在特征的种类上有更多的选择。时空约束的聚类算法公式如下：

$ C = \mathop \sum \nolimits_1^n \left( {E_1\left( {v,d} \right) \& E_2\left( t \right) \& M\left( p \right)} \right) $

式中：C为改进的密度聚类算法得到的簇，E₁为空间邻域，v是输入数据速度，d为输入数据距离，v和d是经纬度与时间转换后得到的数据；&为逻辑门与，E₂为时间邻域；M为聚类点的最少点个数。

1.3 基于ST_DBSCAN算法的轨迹点聚类

在传统的轨迹点识别方面，停留点的识别主要以经纬度加上时间戳直接进行聚类分段，聚类后的簇虽然考虑了时间的特征，但是时间戳的差异导致轨迹段的细散化，使得轨迹段的特征不明显，不利于后续的识别。因此采用了轨迹的间接时空表示：两点间的距离和平均速度，这既保留了轨迹的时空特征，又减少了簇的分散程度，所以能够保留停留点和移动点的特征差异。图1根据ST_DBSCAN算法对轨迹点进行聚类分段，最后利用约束条件识别出停留点和移动点。

ST_DBSCAN聚类算法描述

输入　GPS轨迹数据集D，空间领域约束E₁，时间领域约束E₂，聚类点最少点个数M。其中： $D = \left\{ {T,v,d} \right\} = \left\{ {\left( {{t_1},{t_2}, \cdots ,{t_n}} \right),\left( {{v_1},{v_2}, \cdots ,{v_n}} \right),\left( {{d_1},{d_2}, \cdots ,{d_n}} \right)} \right\}$ ，T是时间戳，v是速度，d是距离。

输出　聚类后得到簇C与噪声N。其中：

$\begin{array}{c} C = \left\{ {{C_1},{C_2}, \cdots ,{C_n}}\right\}= \\ \left\{\!\!\! {\begin{array}{*{20}{c}} {\left[ {\left( {{t_1},{t_2}, \cdots ,{t_i}} \right),\left( {{v_1},{v_2}, \cdots ,{v_i}} \right),\left( {{d_1},{d_2}, \cdots ,{d_i}} \right)} \right],}\\ {\left[ {\left( {{t_i}, \cdots ,{t_j}} \right),\left( {{v_i}, \cdots ,{v_j}} \right),\left( {{d_i}, \cdots ,{d_j}} \right)} \right],}\\ \vdots\\ {\left[ {\left( {{t_k}, \cdots ,{t_n}} \right),\left( {{v_k}, \cdots ,{v_n}} \right),\left( {{d_k}, \cdots ,{d_n}} \right)} \right]} \end{array}} \!\!\!\right\} \end{array} $

并且i<j<k<n。C_n是聚类得到的具有相似特征的簇。

$\begin{split} \;\\ N = \left\{ {{N_1},{N_2} ,\cdots ,{N_l}, \cdots ,{N_m}, \cdots ,{N_n}} \right\} \end{split}$

其中l<m<n，噪声N程碎片化，并且噪声之间的特征不明显，所以噪声N不参与下一步识别。

1.4 ST_DBSCAN算法约束条件

根据上一部分ST_DBSCAN聚类算法得到的簇C，利用恰当的约束条件来识别停留点和移动点。

约束算法如下：

输入　簇C。其中，C={C₁,C₂,···,C_n}。

输出　停留点序列P_s和移动点序列P_m。其中P_s={P_s1,P_s2,···,P_sn}，P_m={P_m1,P_m2,···,P_mn}。

约束算法：

1）判断各簇C₁~C_n是否含有静止的点，没有则进行：

2）如果簇C的所有速度特征V₁的和的平均值v_avg=4 m/s大于设定阈值则标记为移动点，不符合的进行约束1和约束2：

约束1　设置一个速度阈值V₂=0.6 m/s，T_2为在簇中轨迹点速度特征大于V₂所占的百分比。

约束2　设置一个速度V₃=1.5 m/s的阈值，在约束1的基础上，并且簇的平均速度小于V₃的标记为移动点，其他的标记为停留点。

3）有静止的点，则进行约束3：

约束3　计算簇里面速度为0的点的百分比D(若百分比D比接近1说明它是越有可能是交通堵塞的点)以及如果簇的D符合并且上一个簇是移动点，同时上一个簇的点的移动速度大于V₄=6 m/s则标记为移动点。

4）否则标记为停留点。

1.5 时间复杂度

本文算法聚类阶段的时间复杂度是O(n×i)，n是点的个数，i是找出Eps领域中的点所需要的时间，最大的时间复杂度是O(n²)；约束阶段的时间复杂度是O(m×j)，m是轨迹段个数，j是找出停留点和移动点的时间，最大的时间复杂度是O(m²)。因此本文算法的时间复杂度为O(n²+m²)，算法最大时间复杂度为 O(2n²)。

2 实验结果与分析

为了验证本文提出的基于ST_DBSCAN聚类算法与约束条件的停留点识别性能，在Windows7系统下利用Python3.6版本软件编写算法和约束条件。实验共测试3种聚类算法：ST_DBSCAN算法、C_DBSCAN算法^[8]和DBSCAN_TE算法^[9]。每种方法的输入数据相同，采用均方根误差(RMSE)来度量算法精度，公式为

${\rm{RMSE}} = \sqrt {\frac{1}{N}\sum\limits_{i = 1}^n {{{\left( {{X_{{\rm{real}},i}} - {X_{{\rm{pre}},i}}} \right)}^2}} } $

实验分3步进行，数据预处理，参数选择以及评估ST_DBSCAN算法的性能。

2.1 数据预处理

实验数据来源于Ubicomp 2018-SHL挑战赛的华为数据集 (Sussex-Huawei locomotion dataset) ^[19]，用户的出行轨迹可视化图如图2。

表1给出了数据的原始标签类型，本文根据原始标签的特点进行数据的再次标注，给出2种数据标签：停留点和移动点以及相应的依据。

此外，由于数据带有一定噪声，例如经纬度的漂移，部分轨迹点的标签有一定的缺失。因此，对数据进行过滤噪声^[20]处理，如表2。

此部分的数据标签的特征是按照正常情况下设定的，例如，car与bus因为交通拥堵而导致的停留将会出现速度为0的点，即用户在交通道路上等待的部分将在轨迹段识别里的约束部分进行识别。

2.2 ST_DBSCAN算法中的参数选择

基于时空约束的密度聚类算法中，需要选择合适的参数。空间阈值eps1与MinPts要与对比算法保持一致，所以参数选择与对比算法一样。时间阈值eps2由于考虑的是连续轨迹点临近的关系，如图3，在eps2=5的时候识别率都达到饱和(user是用户，user1、user2、user3是3个用户，user1/1是第1个用户第1天记录的数据集，user3/3是第3个用户第3天记录的数据集)，因而经过调试选取的时间邻域值eps2为5。D是判断一个簇中轨迹点速度为零的百分比，百分比越高越能够说明这段簇是因为等车或堵车所造成的停留，如图4，D在达到0.2之后识别率达到饱和，说明数据集里面因为等车或堵车所造成的停留并没有对整体识别率产生决定性的影响，此外，还有可能是数据集里面根本没有等车或堵车所造成的停留。因而经过一段时间的调试之后，得到比较优秀的结果的参数是空间域eps1=4，时间域eps2=5，MinPts=4，D=0.2。因为实验包含9组轨迹数据集，此外，由于still、walking outside 和walking inside是本文识别轨迹点的算法所关注的重点，因而对于不同的轨迹数据集来说参数t_2是不一样的，同时精确度变化也是最大的。

如图5，每份数据的识别精度在参数t_2的调整下变化都特别大而且识别精度变化差异特别的明显，这说明每个轨迹数据文件因为自身的数据特征不一样，因而最佳参数也不一样。因此，本文在识别轨迹数据的时候，选用的是各自轨迹数据的最佳参数，而记录数据的时候是记录最优参数所识别的精度。如图6，在与其他算法对比的时候将选用最优的参数识别的精度进行对比。

2.3 ST-DBSCAN算法性能评估

为了评估本文方法的性能，选取了同样基于聚类策略的C_DBSCAN算法^[8]以及DBSCAN_TE算法^[9]。此外，本文算法的创新点在于聚类输入数据的不同，为了验证这一策略的有效性，在ST_DBSCAN算法的基础上，将在聚类阶段输入的数据改为经度和纬度，并记为ST_DBSCAN_GPS；在聚类阶段输入的数据为速度和距离的记为ST_DBSCAN。本文将ST_DBSCAN＿GPS也作为对比方法，以验证本文算法的性能。为了达到相同的测试条件，本文在进行识别之前对3种算法进行了相同的预处理，在最优参数与最优准确率选择方面，3个算法的思路是一样的，实验结果均选取了3种方法识别停留点的最优准确率。实验结果如表3、图7和图8所示。

图7是3种算法的识别精度对比。由图7可知，在本文所列举的数据集上，ST_DBSCAN算法基本上是最优的，ST_DBSCAN算法识别精度明显优于DBSCAN_TE算法和C_DBSCAN。与DBSCAN_TE和C_DBSCAN算法相比在所有用户的每条轨迹的停留点识别精度上均有大幅提升。其原因在于本文的ST_DBSCAN算法的约束针对数据集进行了设计，因而该算法有一定的针对性，所以识别精度很高。因此，在新的数据集上的测试任务需要进行一定的参数调整，以适应新的轨迹数据，但3种约束的设计思想保持不变，仅需对约束的参数进行一定的调整。此外，由于每个数据的特征不一样，因而识别误差也有所不同。C_DBSCAN算法的均方根误差为19.79%，DBSCAN_TE算法的均方根误差为12.00%，ST_DBSCAN_GPS的均方根误差为5.73%，ST_DBSCAN的均方根误差为3.93%。因此，ST_DBSCAN算法对于停留点的识别是有效的。

由图8可知，ST_DBSCAN的运行时间相对其他两种算法和ST_DBSCAN_GPS运行时间最少，同时，ST_DBSCAN的识别率显著优于ST_DBSCAN_GPS，说明了本文所提供的以速度与距离为聚类条件的可行性。

但是，ST_DBSCAN方法仍存在一定的识别错误，其原因在于：部分停留点和移动点的簇的特征特别相似。如人在特定状态时的不移动(属于停留点)与等车、等红绿灯和堵车(属于移动点)的特征非常相近，因而在建立约束条件的时候无法有效识别。

3 结束语

本文采用基于时空约束的密度聚类算法对GPS轨迹数据进行识别，首先对数据轨迹进行聚类分段，然后利用约束条件来获得停留点和移动点。实验结果表明本文的算法是有效的。本文还有许多需要提高的地方，比如在识别非常相似的簇时需要获得更有识别率的特征；在提高算法的泛化能力方面，可进一步优化识别方法的约束条件，减少约束参数。同时，实验结果也表明轨迹数据特征的不足，以后需要加入更多维度的特征，此外，约束条件还会考虑其他的特征，如加速度、方向角和方向变化率等，这些为本文的未来研究方向。