基于最小覆盖圆时空聚类算法的出行轨迹停驻点识别

张小佳， 孙然然， 李晓璐， 赵 晖， 张 彭， 朱广宇*

(1.北京交通大学综合交通运输大数据应用技术交通运输行业重点实验室， 北京 100044；2.北京交通发展研究院，北京 100073； 3.交通运输部规划研究院， 北京 100028)

对居民出行行为的研究有助于提取居民出行规律、分析交通问题成因、确定合理的规划方案。20世纪90年代以来，GPS轨迹数据在居民出行行为分析中得到广泛应用[1-2]。基于GPS数据的出行行为研究包括出行路径选择建模[3]、出行方式选择建模[4]、目的地选择建模[5]、地理兴趣点挖掘[6]等诸多方面。 GPS轨迹点具有位置精度高、时间信息准确、数据量丰富等优点，但由于其并不直接包含用户出行方式和出行目的信息，在出行行为分析前，需从GPS 点数据中识别出行方式和出行目的。GPS轨迹点数据通常记录用户至多一天的完整出行链信息，基于GPS轨迹点数据进行用户出行方式与出行目的推断的一个重要前提是将出行链分段为多个单次出行[2]。根据出行者运动状态，轨迹数据可划分为出行段与停留段，每一完整出行信息由起始停留段、出行段与终止停留段构成，由于停留段通常具有速度趋近于0、轨迹点分布集中、停驻时间较长等特征，因此可通过确定停留段完成出行链划分。通过出行段轨迹速度、加速度、出行路径等数据并结合出行者社会属性、地理信息数据库可推断出行方式[7-10]。对停留段轨迹结合周围土地利用信息、POI(point of interest)信息、出行者社会属性等可推断用户出行目的[9, 11-12]。因此，停留段识别已成为出行方式与出行目的推断的重要基础。由于用户在停留段位置较固定，因此使用停留段轨迹中心点表示停留位置，称之为停驻点。

现有研究已提出多种停驻点识别算法。针对车载GPS设备采集到的轨迹点，通常使用速度阈值和停驻时间阈值识别停驻点[13-15]。在基于手持GPS设备(包括含有GPS采集功能的智能手机)的研究中，由于用户停驻点多位于室内，GPS信号弱导致的轨迹点漂移、轨迹点缺失现象使得基于速度阈值的判断方法难以有效识别停驻点，研究多采用聚类算法进行停驻点识别。文献[16]提出基于速度的时间聚类法与基于速度的速度聚类法两种方法进行停驻点识别，其中基于速度的速度聚类法适用于因出入室内建筑或其他原因引起轨迹点采样频率不等、数据缺失较严重的轨迹数据。文献[17]提出了一种同时考虑时空特性的交互式聚类方法用于停驻点识别，该方法能够有效识别因GPS信号弱所引起的轨迹点漂移条件下可能被隐藏的停驻点。文献[18]提出了一种时空聚类算法用于手机信令数据中停驻点识别，该算法首先根据轨迹点密度确定核心点，邻近核心点形成初始类簇。随后将邻近类簇进一步合并，最后根据最小驻留时间过滤掉伪停驻点，剩余类簇中心点为所推断停驻点。相较于其他基于密度的聚类算法，该时空聚类算法具有计算效率高、准确性高、对异常轨迹点不敏感等优点，并能解决传统基于密度聚类中的轨迹重叠问题。

时空聚类停驻点识别算法的核心步骤为初始类簇的确定，在文献[18] 中研究基础上，提出了一种基于最小覆盖圆的时空聚类算法，用于手持GPS设备采集数据的停驻点识别。通过停驻区域范围阈值、停驻时间阈值、近邻类簇最大间隔时间、近邻类簇最大间隔距离四个参数进行停驻点识别算法调优。针对停驻点识别效果评价，提出了基于停驻点识别精度的查全率与查准率指标。

1 数据采集及预处理

1.1 GPS数据采集

非车载GPS轨迹数据的采集目前主要包括手持式GPS设备和安装特定采集软件并支持GPS模块的智能手机两种方式。基于智能手机的采集方式具有成本低、携带方便等优点，但同时也存在续航时间短、精度较低等缺点，手持式GPS设备具有采样频率设置多元化、数据采集导出便捷、精度高等优点[2]。表1所示为GPS轨迹点基本格式，其中PDOP(position dilution of precision)为位置精度因子，因采集设备差异，导出数据中部分字段可能并不一致。为验证研究方法的有效性，除GPS轨迹数据外，通常需要出行者在完成一天出行后借助出行轨迹地图来回忆并填写出行日志。出行日志包括出行起止时间、出行方式以及出行目的，其基本格式如表2所示。

1.2 GPS数据预处理

GPS数据位置精度高，但受冷启动、温启动以及树木、建筑物遮挡等因素可能造成信号缺失和信号噪声现象，从而导致在设备开机启动阶段、出行起始阶段及停驻阶段的位置点缺失、位置点漂移[2]。针对位置点漂移问题，可通过过滤卫星数量小于3或HDOP(horizontal dilution of precision)大于5的位置点进行位置点过滤[19]。对于位置点缺失问题，可通过插值方式进行填充，但应注意到若缺失时间较长，则插值得到的位置点可信度较低[18-19]。

表1 部分原始GPS数据

表2 出行日志部分数据

2 基于最小覆盖圆时空聚类算法的停驻点识别

针对手持GPS设备采集轨迹数据，基于已有研究，提出最小覆盖圆时空聚类算法用于停驻点识别。该算法可有效处理聚类过程中轨迹重合度高、轨迹漂移等问题。

2.1 定义

定义1轨迹：由包含时空信息的位置点按时序排列构成的位置序列数据P={pi}(i=1,2,…,n)。每一位置点包括经纬度坐标及时间戳三个基本信息，记作pi=(loni,lati,ti) 。后文算法描述中，轨迹也称为轨迹点类簇。

定义3轨迹范围：对于一系列轨迹点构成的轨迹tra={pi}(i=k,k+1,…,k+m)，轨迹范围取包含所有轨迹点的近似最小覆盖圆，近似最小覆盖圆Sc为以轨迹中心为圆心，半径r=max{dis(center,ps)}(s∈{k,k+1,…,k+m}),其中dis( )为两点空间距离计算函数。

定义4近邻轨迹：对于两条轨迹：tra1={pi}(i=k,k+1,…,k+m，tra2={pj},j=k+l,k+l+1,…,k+l+s;l>m)、若两轨迹中心距离dis(center1,center2) 小于距离阈值mdist且轨迹时间间隔tk+l-tk+m小于时间阈值mdura,则轨迹tra1、tra2互为近邻。

定义5停驻轨迹：受信号噪声影响，用户在停留时段位置并非固定在同一位置点，而是围绕在某位置中心附近分布，停留时段位置点构成的轨迹称之为停驻轨迹。

定义6停驻点：为确定停留时段具体停驻位置点，使用停驻轨迹中心估计用户实际停驻位置，称该位置点为停驻点。

2.2 使用最小覆盖圆时空聚类算法识别停驻点

基于最小覆盖圆时空聚类算法的停驻点识别流程如下：

(1)基于给定圆形停驻区域范围阈值将完整轨迹切分为连续的轨迹点类簇，使得每一轨迹类簇范围最大且半径不超过范围阈值。若上一轨迹类簇点为Pi={pr,pr+1,…,ps}，对于当前类簇Pi+1={ps+1,ps+2,…,ps+k}，其类簇范围对应半径小于范围阈值，且类簇P′i+1={ps+1,ps+2,…,ps+k+1}范围对应的半径大于范围阈值，则类簇Pi+1={ps+1,ps+2,…,ps+k}范围达到最大。

(2)基于停驻时间阈值对类簇进行初步过滤，仅保留停驻时长大于1/2停驻时间阈值的轨迹类簇。

(3)递归合并邻近类簇。若两相邻类簇间隔时间小于间隔时间阈值且间隔距离小于间隔距离阈值，则进行类簇合并，合并后类簇由相邻类簇所有轨迹点组成。

(4)基于停驻时间阈值过滤合并后类簇，仅保留停驻时长大于停驻时间阈值的轨迹类簇。

2.3 算法参数调整

最小覆盖圆时空聚类算法共包括4个可调整参数，分别为停驻区域范围阈值Tdist、停驻时间阈值Tdura、近邻类簇最大间隔距离mdist、近邻类簇最大间隔时间mdura。4个参数相互关联，共同决定停驻点识别结果。

2.3.1 停驻区域范围阈值

停驻区域范围阈值决定初始类簇的划分粒度。较小的范围阈值能够更精准地确定停驻起始时刻，但也容易导致一个完整的停留时段被割裂为多个停留时段。当停驻范围过大时，最终识别得到的停驻时段通常包含更多的非停留时段轨迹点。

2.3.2 停驻时间阈值

由于用户在停驻时段内速度减缓且运动方向多变，因此轨迹点范围大小相同的多个类簇，包含停驻时段的类簇其持续时间通常要大于不包含停驻时段的类簇。因此，可基于停驻时间阈值对类簇进行过滤。最小覆盖圆时空算法中包含两次基于时间阈值的类簇过滤。第一次使用停驻时间阈值的1/2大小进行初步过滤，第二次使用停驻时间阈值对合并后类簇进行最终过滤，确定停驻点。停驻时间阈值的选择通常要考虑到停驻区域范围阈值的大小，当增大停驻区域范围阈值时，要合理增加停驻时间阈值来有效过滤不包含停驻时段的类簇。考虑当停驻区域范围阈值为120 m(圆形范围半径)，停驻时间阈值设置为300 s。若增大停驻区域范围阈值为500 m，则停驻时间阈值也应合理增加，否则部分非停驻时段轨迹点类簇可能无法被成功过滤。

2.3.3 近邻类簇最大间隔距离

在类簇划分时，因信号原因产生的异常轨迹点可能会偏移正常轨迹点较远距离，导致一个连续的停驻时段被切分为多个类簇。因此在类簇切分并完成初步过滤后，需进行类簇合并。近邻类簇最大间隔距离越大，多个相邻类簇更可能被合并为一个类簇。

2.3.4 近邻类簇最大间隔时间

类簇合并不仅需满足空间间隔，同样需考虑时间间隔。考虑如下场景，某学生从宿舍出发绕校园跑步随后返回宿舍，此过程包含两个停驻点，均为其宿舍。当完成类簇划分及初步过滤后，两个停驻时段对应的类簇被保留下来，此时若仅依据最大间隔距离进行类簇合并，则两个类簇可能被错误合并为一个类簇，若进一步判断类簇间隔时间，间隔时间大于最大间隔时间，则不进行类簇合并，此时可正确识别两个停驻时段。

2.4 停驻点识别评价指标

为验证所设计停驻点识别算法有效性，需确定合适的计算指标对识别结果进行检验。停驻点识别算法有效性通常采用查全率和查准率进行衡量[20-21]。查全率与查准率指标主要应用在类别预测研究中，若样本预测类别与其真实类别相同，则预测正确，反之预测错误。在停驻点识别研究中，使用0～1变量无法反映当前停驻点识别结果的有效精度，因此本文提出停驻点识别精度指标(0～1连续变量)，使用基于停驻点识别精度的查全率与查准率指标评价算法有效性。

对识别停驻时段tra={pi,pi+1,…,pi+k}，其对应识别停驻点为pstop，为计算其识别精度，首先选择起始时刻与当前识别停驻时段起始时刻最接近的真实停驻时段作为其对应的真实停驻时段，记为tra′={pj,pj+1,…,pj+s}，其停驻点记为p′stop。若当前停驻点pstop落入轨迹tra′范围内，则记当前识别停驻时段tra为正确识别停驻时段，反之为错误识别停驻时段。若当前识别停驻段时段为错误识别停驻时段，其精确度记为0；反之，其精确度为起止时刻精确度ptime-diff与停驻点精确度pdist平均值，计算公式为

(1)

(2)

(3)

式中：Mtime-diff、Mdist分别为最大距离偏差与最大时刻偏差，其值可根据多次算法识别结果进行取值。基于每一识别停驻时段的精确度，当前识别结果的查全率R(recall)与查准率P(precision)计算公式为

(4)

(5)

式中：Np、Nr分别代表识别停驻时段个数与真实停驻时段个数。

3 实例分析

3.1 数据介绍

为验证所提算法有效性，使用实际轨迹点数据及出行日志数据对算法进行检验。研究共招募15名志愿者，每位志愿者携带GPS设备UniStrong G120-BD进行了为期3～5 d不等的调查。每位志愿者活动范围在其所在居住点周围20 km范围内，每个人1 d的出行轨迹包含大约10 000个位置点。除通过随身携带GPS采集器采集每日的出行轨迹外，参与者需依靠GPS设备的路径显示功能，填写其实际出行日志，用于检验后续停驻点识别算法效果。实验采集GPS数据格式和出行日志数据格式见表1和表2。

3.2 停驻点识别

为展示停驻点识别具体结果，选择某一轨迹进行详细说明。该轨迹点为2019年3月29日生成，共包含9 923个轨迹点，轨迹信息如图1所示，表3为该条轨迹对应出行日志信息。分析表3出行日志信息可以发现，在G-H段等候公交车时间较短，J时刻步行结束后直接乘坐出租车出发，因此在这两个换乘过程中不包含停驻点。该轨迹共对应3个停驻时段，分别为B-C段在公寓楼停驻、D-E段在图书馆停驻以及F-G段在食堂停驻。使用最小覆盖圆时空聚类算法对该轨迹中停驻点进行识别，对停驻点范围半径、停驻时间阈值、近邻类簇间隔距离、近邻类簇间隔时间参数取值进行多次调优，结果发现，在一系列参数取值组合中，当参数取值分别为60 m、600 s、100 m、800 s时，识别准确率最佳，最终识别结果见图2。图2中绿色圆形为停驻轨迹近似最小覆盖圆，位置图标对应停驻轨迹中心，红色圆圈为轨迹点。点击交互式地图中的位置图标，可弹出该停驻时段起始时刻，点击最小覆盖圆，弹出该圆半径及圆心位置。表4列出了当前识别停驻时段相关信息。计算当前识别结果精确度，Mtime-diff、Mdist取值确定为2 500 s与500 m。由于识别停驻点个数与真实停驻点个数相同，因此当前识别结果的查准率和查全率相等，其值为0.82。

表3 2019-03-29出行日志

对识别结果进行分析发现，三个真实停驻点都得到了有效识别，除第2个停驻点外，其余两个停驻点起始终止时刻识别误差较小。对出行轨迹点进行分析发现，造成第2个轨迹点识别误差较大的主要原因在于室内信号差，轨迹点缺失导致。其中在17:27左右连续4条轨迹信息的时间戳分别为17:27:50、17:27:52、18:01:53、18:01:55。由于轨迹点缺失间隔过长，因此未对该缺失时段轨迹点进行插值。图3操场西侧建筑区域为图书馆，图3中显示当用户18:01:53离开图书馆后，其位置点信息立即被采集到，由于此时该轨迹点偏离其在图书馆停驻中心较远，因此其未被聚类到图书馆停驻时段中，导致图书馆停驻时段终止时刻与实际终止时刻相差较大。整体而言，本文所提出的最小覆盖圆时空聚类算法能够很好地识别用户GPS轨迹中的停驻点及停驻时段。

图1 2019-03-29轨迹Fig.1 Trajectory of 2019-03-29

图2 2019-03-29轨迹停驻点识别结果Fig.2 Identified stop points in the trajectory of 2019-03-29

图3 GPS信号缺失引起轨迹中断Fig.3 Trajectory disconnected due to GPS signal missing

表4 2019-03-29轨迹识别停驻时段

4 结论

(1)提出了一种可用于GPS轨迹停驻点识别的最小覆盖圆时空聚类算法。该算法计算量小，能够很好地处理轨迹重合度高、异常轨迹点等情形。对某条包含9 923个位置点轨迹进行识别，所有停驻点均能够被正确识别，除因信号缺失时段较长引起某一停驻时段终止时刻与实际相差较大外，其余停驻时段起始、终止时刻均与实际接近，验证了该算法的有效性。

(2)最小覆盖圆时空聚类算法能够很好地确定用户停驻活动起止时刻，但由于建筑物附近位置轨迹点偏移，其对于实际停驻点位置的确定存在一定偏差。后续研究可考虑进一步结合位置点信息、出行者社会属性及出行历史记录对停驻点位置进行纠偏。

(3)最小覆盖圆时空聚类算法可很好地适用于数据量较少的情形，若存在大量出行轨迹可供研究，可考虑从轨迹数据中提取高频停驻点、挖掘用户出行规律，作为停驻点识别的先验信息，提高停驻点识别精确度。