时空约束下的热点路径空间分布检测算法

段 炼，李 峙，胡宝清

（1.武汉大学 测绘遥感信息工程国家重点实验室，湖北 武汉430079；2.广西师范学院 北部湾环境演变与资源利用教育部重点实验室，广西 南宁530001；3.广西师范学院 资源环境科学学院，广西南宁530001；4.广西师范学院 广西地表过程与智能模拟重点实验室，广西 南宁530001；5.广西红树林研究中心广西红树林保护与利用重点实验室，广西 北海536000）

0 引 言

时空轨迹是移动对象随时间推移的位置序列。随着移动互联网、定位系统等技术的快速发展，在交通、物流等应用领域，人们通过智能移动终端采集了大量时空轨迹数据。热点路径通常是指多个移动对象频繁经过的路径，能反映出路径上移动对象的个体或群体运动模式［1］，可辅助城市规划、交通管理、用户调查等领域的决策分析［2］。从时空轨迹数据（Trajectory）中获取热点路径的通用方法是以聚类方式，通过对轨迹内部运动模式和特征信息的分析，确定轨迹间的相似量度，然后将相似程度较高的轨迹归为一类［3］，每一类反映了移动对象的某种运动和行为模式，从而发现时空轨迹数据中的语义相似性与异常特征，进而探测到城市热点道路的时空分布。

目前，许多著名的聚类算法如K－MEANS、BIRCH，DBSCAN、OPTICS、STING 等［4］被用于轨迹聚类。KREVELD 等［5］首次将时间依赖关系引入到轨迹分析中。HAN 等［6］对轨迹分段，并将速度等要素引入轨迹段间的相似度计算。LEE［4］等采用Hausdorff距离，将轨迹划分成若干t－partition进行聚类。Chen等［7］提出了路网空间下基于密度的轨迹聚类方法。Kim 等［8］基于重叠路段长度的相似度进行轨迹聚类。Xia等［9］提出了在路网约束下综合考虑时间和空间约束的轨迹相似性度量的轨迹聚类方法。然而，这些方法大多是基于轨迹的全局空间信息进行聚类，没有考虑轨迹的局部时空特征。已有的轨迹聚类方法也考虑了轨迹的时间特征，但对轨迹运动语义特征利用不足，而轨迹运动语义特征如方向、转角、速度等更能体现路径内在、外在的异同。此外，一些轨迹聚类方法尽管考虑是速度等运动语义特征和轨迹的局部特征，但却忽略了时间要素。

据此，本文提出了基于时空轨迹聚类的热点路径分布检测方法。将该模型计算轨迹断点，依据断点将轨迹划分成若干轨迹段，基于轨迹段之间的位置、时间、速度和方向相似度对轨迹段聚类。对聚类结果中的非显著簇进行适当处理，或者将其并入其它邻接的显著簇，或者作为噪音删除。将各显著簇内邻近的断点融合成停留斑点，停留斑点所承载轨迹段数量得到斑点热度，基于DENCLUE（DENsity－based CLUstEring）算法［10］获取热点路径的空间分布。实验结果表明，本文的方法可对大规模轨迹进行高效聚类，并有效发现城市热点路径分布。

1 轨迹时空聚类

1.1 基本概念

定义1 轨迹：三维空间中的有序点集称为轨迹。轨迹TRi定义：TRi＝｛p1，p2，…，pk｝，其中pk＝｛xk，yk，tk｝，他们分别代表该点的二维空间坐标和采用时间。不同轨迹长度可能不一样。

定义2 轨迹段：为TRi内连续的部分三维点集，如：SubTrajectorys＝｛p1，…，pk｝（1≤s≤k），k 为该轨迹段所属轨迹的采样点总数。

定义3 Hausdorff距离：是描述两组点集之间相似程度的一种度量，也是集合之间距离的一种定义形式。相关定义请参见文献［11］。

定义4 轨迹段速度：轨迹段上移动对象在每个采样点位置瞬时速度的集合。对描述某段时间内该轨迹所在路径的通达程度具有十分重要的意义。由于实验数据集缺失采样点的速度，因此，通过如下公式得到每个采样点速度

式中：p－——p 点之前的相邻采样点，p＋——p点之后的相邻采样点，tp－、tp＋——p－、p＋的采样时间，该计算公式利用移动对象在3个连续采用点的平均速度作为当前点的速度。轨迹段的速度通过该轨迹段中的最小速度、最大速度和平均速度来衡量

式中：ωm＋ωa≤1，vmin——轨迹段中速度最低值，vmax——轨迹段中速度最高值，i、j——该轨迹段采样点的下标。对于一条轨迹段多个采样点，其速度都是不相同的，因此，这里要综合考虑速度的各种因素，以将具有相似速度结构的轨迹段聚集在一块。

定义5 轨迹段方向：轨迹段始末采样点之间形成的角度。尽管道路上两条轨迹段在每个采样位置的移动方向差异可能较大，但在道路网的约束下往往这些采样点的总体移动方向是相同的，如果采用已有轨迹聚类方法比较每个采样点之间的角度差异，在轨迹聚类算法执行过程中，不仅会因为比较两个轨迹段间每个采样点在不同时刻、不同位置的角度变化而影响算法效率，还会有可能将总体上位移方向一致、行为目的一致的轨迹段划分到不同聚类中。因此，轨迹段的总体移动方向能表达他们之间主要方向差别。采用如下公式表达轨迹段的运动方向角

式中：（xs，ys）轨迹段起点，（xe，ye）为轨迹段终点。

定义6 ξ邻域：设轨迹段为Li的ξ邻域为Nξ（Li）：Nξ（Li）＝｛Lj∈D｜d（Li，Lj）≤ξ｝。其中，D 为所有轨迹段数据集合，d（Lj，Lj）为轨迹段，Lj和Lj在时间、位置、速度、方向上的相似度。邻域用以在轨迹密度聚类中，判断每个轨迹段的当前空间密度，进而将空间密度高于阈值的轨迹段聚为同一簇。

1.2 轨迹分割

城市中，浮动车辆的行动受道路网约束，其轨迹空间结构不会类似动物路径或风暴路径那样在角度和速度上经常出现剧烈变化。因此已有依据每个采样点的角度变化进行轨迹分割的方法不适合城市空间中的轨迹段划分。而受到交叉路口红灯、交通拥塞、工作、休闲和生活场所的影响，城市中的移动对象常常在这些位置停留，这些停留位置更全面地表达移动对象的运动和行为语义状态，具有相同停留位置而不是相同较大拐角的轨迹段，能反映移动对象在目的和行为上的相似性。因此，通过采样点在某个时间段内的速度变化来分割轨迹，而往往这些位置有较明显的速度差异。

定义7 断点：假设存在一轨迹段，位于该轨迹段上的任何两点之间的距离不超过阈值ε，并且这段子轨迹的采样点数s大于阈值Ε，则我们将这段子轨迹中的第［s／2］个点设置为断点。本文的轨迹是每5s记录一次采样点，因此ε设置为10，Ε设置为3，即只要车辆在超过15s的时间内行驶不超过10m，我们就认为存在断点。

为保证轨迹的完整性，将位于该段子轨迹上其余的点删除，这时，如果一条轨迹上有t个断点，则该轨迹被分割为t＋1个轨迹段。

1.3 轨迹段相似性比较

轨迹段之间的相似性通过轨迹段之间的差异度获取，该计算包括4方面：空间差异度、时间差异度、方向差异度和速度差异度。其中，空间差异度与时间差异度采用Hausdorff距离计算得到，方向差异度和速度差异度直接采用属性差值绝对值表示即可。将他们结合得到一个统一的表达轨迹段相似性公式

式中：spatialDis、tempoDis、OrientDis和velocityDis——轨迹段之间的空间差异度、时间差异度、方向差异度和速度差异度。轨迹段相似性公式为

式中：tanh（subDis）——三角函数归一化公式。

1.4 基于DBSCAN 的轨迹聚类算法

对轨迹进行分割后，再利用DBSCAN 密度算法，采用式 （5），进行轨迹段聚类。与DBSCAN 不同，这里还需考虑轨迹段与原始轨迹的关系。设聚类簇C 中包含的轨迹数目为簇基数ncb，簇基数ncb与该聚类中轨迹段数目nc之比为簇显著度ncs，给定阈值τ和γ，我们进行如下定义：

定义8 显著簇：Csig＝｛C｜C∈O ∩ncb＞τ ∩ncs＞γ｝，其中，O 为第一次聚类的结果集。即簇基数nb高于τ且簇显著度ns高于γ聚类称为显著簇。

定义9 非显著簇：Cunsig＝｛C｜C∈O ∩COsig｝，其中，Osig为显著簇集合。即显著簇之外的聚类都为非显著簇。

一旦某聚类中簇基数少于τ，则说明该聚类中抑或包含了较多属于同一条轨迹的轨迹段，抑或仅仅包含了较少的移动对象，同样，如果某聚类中的显著度小于γ，则说明该聚类中的轨迹数量相对于轨迹段来说过少，这两者均无法反映全局上的该聚类所覆盖路径的重要性。因此，将第一次聚类中非显著簇删除，同时将其包含的轨迹段归并到离其最近距离小于阈值μ且包含同一条轨迹的聚类中。

显著簇判断和轨迹段归并算法伪代码如下：

（1）从聚类集合O 中获取下一个簇C；

（2）设簇C 的簇基数ncb，簇显著度ncs，如果nc＞τ，并且ncs＞γ，则将C 放入显著簇集合Osig，直至遍历完O，将所有没有放入Osig的簇放入Ounsig；

（3）从Ounsig取出下一个非显著簇C’，从C’依次取出各轨迹段，判断各轨迹段距离其最近且包含有相同轨迹标示的显著簇，如果轨迹段距离其最近显著簇的距离大于μ，则将其作为噪音抛弃，否则将其加入该最近显著簇；

（4）重复（3）直至遍历完所有的非显著簇。

该方法能较好地在全局空间上体现重要聚类的影响范围，而传统轨迹密度聚类方法无法做到这一点。

2 热点路径分布探测

热点路径分布探测的目的是发现那些承载大量浮动车辆运行的城市道路分布区域。常规热点道路检测往往是直接依据道路上轨迹数量或断点的数量判断路径上的车流集中程度。然而，一些道路上尽管车流量大，但造成车辆停留的位置少，表明该道路上的商业网点或提供社会服务的区域少，如城市外环道路；一些道路上的轨迹断点数量较多，但其主要分散在道路两端，如通往旅游景区的道路，因此，常规方法无法准确反映城市热点路径的分布。本文基本思路是在显著簇中将邻近断点融合成停留斑点，基于停留斑点所承载轨迹段数量得到斑点热度，最后利用点值密度聚类获取热点路径的空间分布。

定义10 停留斑点：显著簇中各轨迹段始末点（也就是断点）构成的、最小外接圆半径小于阈值α区域。

停留斑点反映了道路中某种社会功能集聚或某种交通路况发生的区域，从而也反映了这一区域附近道路的重要程度。而车流量的大小往往与道路断点集中处的车流集中程度紧密相关，如道路上的拥塞往往是道路始末点的十字路口或某个商业区的车流停滞造成的。因此，这些热点停留斑的发现能集中体现移动对象运动模式发生根源，其与相应的轨迹聚类结果相结合既能发现热点路径，又能有助于发现热点路径的产生原因。

停留斑点的获取也就是断点的融合过程。计算要求停留斑点尽可能覆盖更多的断点，不允许存在单个断点作为停留斑点。其获取算法如下：

（1）从聚类集合中获取下一个显著簇C，将C 中所有轨迹段的始末点抽取为断点集D；

（2）随机从D 中取出一个断点p，将其它断点依次与p 合并，构成一个不断扩大的点集A，如果新加入的点p｀造成A 的最小外接圆半径大于阈值α，则从A 中删除该点p｀；

（3）当D 中所有的点都已遍历完，如果A 包含的断点数量高于阈值ρ，则A 为停留斑点；

（4）重复（2）直至生成完C 中所有的候选停留斑点；

（5）重复（1）直至遍历完所有的显著簇。

以上停留斑点的计算结果会因为断点的计算顺序而不同，即某个断点会因为被取出顺序的不同而被划分到不同停留斑点中。实验表明，从总体上看，无论断点的计算顺序如何变化，最终得到的停留斑点变化极为细微，不会造成所探测到的热点路径有明显变化。停留斑点中，当较多断点属于同一轨迹时，则说明该区域上所经过的移动对象较少，因此，如果该停留斑点包含的断点很大，但实际上热点较低。为了体现这种现象，设hspot为停留斑点热度，nsubtraj为停留斑点包含的轨迹段数量，ntra为停留斑点包含轨迹数量，β为系数，实验中β＝ntra／2，采用如下公式表达停留斑热度

由此，我们获取到了各显著簇中所有停留斑点的热点。依据停留斑点热点的空间分布利用DENCLUE 算法获得停留斑点的热点分布。热点路径分布检测算法见表1。

轨迹聚类算法的ExpandCluster（）方法中涉及的概念如核心轨迹段、直接密度可达、密度可达、密度相连、密度相连集合的定义与DBSCAN 中定义相同。我们采用空间四叉树存储轨迹段，以提高邻接轨迹段、最近邻接显著簇和停留斑点融合的计算。

3 实验与分析

3.1 实验数据与运行环境

为了验证本文提出的聚类算法，开发了轨迹聚类分析系统。轨迹数据存储在MySQL 数据库中。实验的软硬件环境包括：64 位的Windows 7，Visual Studio 2010，CPU（CORE 2DUO 2.8GH），内存8GB。采用武汉市武昌区2010年2 月至4 月的出租车数据集作为实验数据，共10835条轨迹，每条轨迹的采样点包括了经纬度坐标、采样时间。通过计算断点，最终得到52934个轨迹段。

3.2 实验分析

3.2.1 不同聚类算法效果对比

本文提出的轨迹时空聚类算法TTC（trajectory temporal－spaito clustering）与DBSCAN进行比较。TTC 和DBSCA 的参数调优以最大程度体现城市主干要道、最低程度减少非主干道的出现为准，其中，DBSCAN 方法基于速度和方向进行轨迹分割，依据轨迹段的空间位置计算轨迹段相似性。

图1中，TTC能表现出较明显的主干路径分布，发现的聚类更能体现城市交通特征。而图2中的DBSCAN 聚类空间形态表现出了大量旁支路径，不能明显表现出主干要道的分布。从表2 中可以看出，TTC 算法具有较高的聚类速度，聚类数量适中（共58个聚类），而DBSCAN 的聚类效率较低，聚类个数过多（208个聚类）。以上结果主要有以下原因：①TTC以方向和速度特征为依据，容易区分开那些路径相同但移动属性不同隐蔽轨迹群；②TTC 通过过滤掉大量非显著簇，表现了总体上轨迹运动模式和趋势；③TTC采用了空间四叉树存储轨迹段，提高了邻接轨迹段的搜索效率。

表2 聚类效果比较

图1 TTC聚类效果 （58个聚类）

图2 DBSCAN 聚类效果 （204个聚类）

3.2.2 热点路径空间分布

图3显示了停留斑点在不同城市要道上的分布密度，其中，每个点代表一个停留斑点。图中可发现，尽管显著簇所覆盖道路的轨迹密度高，但在不同显著簇上的停留斑点密度有较大不同，长江附近显著簇的停留斑点密度明显高于其它显著簇。

图4 带有热度信息的停留斑点分布

图4显示了带有热度信息的停留斑点空间分布，表现了对停留斑点进行热点聚类后的效果，其中，颜色越黑，代表该位置的热度越大，反之，热度小。图中可发现高热度的停留斑点具有集聚效应，在较靠近长江一桥的区域中形成了较为明显的高热度聚类，即随着与长江距离的接近，区域的路径热点逐渐增大，在沿江区域的热点达到顶峰；而越趋向城市外围，区域的路径热度越低。图中清晰表达了城市热点路径主要集中在武昌沿江地区，这与实际中该区域分布着众多商业网点，同时也是武昌和汉口、汉阳交汇处相吻合。在一些主干道上聚集着大量停留斑点的分布，这是因为由于红绿灯造成车辆停留较久，从而形成了大量断点。

图5通过热点密度聚类，得到了热点路径的空间分布，其中，黑色表示该热度聚集区，浅色表示地热度聚集区。图5中可清晰表现车流在城市中的最为主要的停留区域分布在靠近长江的区域，不仅说明这些道路上车流集聚，也说明了这些道路两旁覆盖了大量社会服务设施。此外，路径热度沿着城市主干道随着远离长江而衰减，从侧面体现了城市主要功能区靠近长江。图5中颜色较浅区域同样也是车流集中的区域，然而这些区域的城市功能相对于长江沿岸区域来说较弱，因此停留斑点较少。可见，本文提出的热点路径分布方法能较为准确的反映路径热点的分布和城市功能集聚分异。

图5 停留斑点热点密度聚类

4 结束语

热点路径探测在交通、物流等领域有重要应用价值。本文提出了基于轨迹时空聚类的热点路径分布探测方法。通过断点对轨迹分割，引入速度和方向作为轨迹段相似性计算的特征，通过Hausdorff距离度量轨迹段之间在时空上的差异，提取出具有全局显著意义的轨迹簇。之后依据显著簇中停留斑点的热点进行空间密度聚类，获得城市热点路径的空间分布。通过实验验证了该方法能准确发现城市热点路径的集中区域和城市功能集聚区域。下一步工作将研究致力于语义时间信息的引入，探讨不同时段的城市热点路径分布的演变。

［1］XIA Ying，WEN Haiping，ZHANG Xu.Hot route analysis method based on trajectory clustering ［J］.Journal of Chongqing of Posts and Telecommunications（Natural Science Edition），2011，23 （5）：602－606 （in Chinese）. ［夏英，温海平，张旭.基于轨迹聚类的热点路径分析方法 ［J］.重庆邮电大学学报 （自然科学版），2011，23 （5）：602－606.］

［2］LI Xiaolei，HAN Jiawei，LEE Jae Gil，et al.Traffic densitybased discovery of hot routes in road networks ［C］／／Proceedings of the 10th International Symposium on Spatial and Temporal Databases.Boston，MA，USA：Springer，2007：441－ 459.

［3］YUAN Guan，XIA Shixiong，ZHANG Lei，et al.Trajectory clustering algorithmbased on structural similarity ［J］.Journal on Communications，2011，32 （9）：103－110 （in Chinese）.［袁冠，夏士雄，张磊，等.基于结构相似度的轨迹聚类算法［J］.通信学报，2011，32 （9）：103－110.］

［4］Lee J G，Han J W，Whang K Y.Trajectory clustering：A partition－and－group framework ［C］／／Beijing，China：Proceedings of the ACM SIGMOD International Conference on Management of Data，2007：593－604.

［5］Kreveld M V，Luo J.The definition and computation of trajectory and sub－trajectory similarity ［C］／／Seattle，Washington，USA：Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems，2007：324－327.

［6］HAN Chenshou，XIA Shixiong，ZHANG Lei，et al.Subtrajectory clustering algorithm based on speed restriction ［J］.Computer Engineering，2011，37 （7）：219－221 （in Chinese）.［韩陈寿，夏士雄，张磊，等.基于速度约束的分段轨迹聚类算法 ［J］.计算机工程，2011，37 （7）：219－221.］

［7］Chen Ping，Huo Qiuyan，Xu Xuezhou.Clustering networkconstrained uncertain trajectories ［C］／／Eighth International Conference on Fuzzy Systems and Knowledge Discovery，2011：1657－1662.

［8］Kim Sang Wook，Baek Ji Haeng，Lee Junghoon.Trajectory clustering in road network environment ［C］／／Computational Intelligence and Data Mining，2009：299－305.

［9］XIA Ying，WANG Guoyin，ZHANG Xu，et al.Research of Spatio－temporal similarity measure on network constrained trajectory data［G］.LNCS 6401：Proceedings of the 5th International Conference on Rough Set and Knowledge Technology，2010：491－498.

［10］YAN Jun，YUAN Hongyong，SHU Xueming，et al.Optimal clustering algorithm for crime spatial aggregation states analysis［J］.Journal Tsinghua Univ（Sci ＆Tech），2009，49（2）：176－178 （in Chinese）. ［颜峻，袁宏永，疏学明，等.用于犯罪空间聚集态研究的优化聚类算法 ［J］.清华大学学报 （自然科学版），2009，49 （2）：176－178.］

［11］QU Lin，ZHOU Fan，CHEN Yaowu.Trajectory Classification based on Hausdorff distance for visual surveillance system［J］.Journal of Jilin University（Engineering and Technology Edition），2009，39 （6）：1618－1624 （in Chinese）. ［曲琳，周凡，陈耀武.基于Hausdorff距离的视觉监控轨迹分类算法 ［J］.吉林大学学报（工学版），2009，39 （6）：1618－1624.］