一种基于轨迹特征划分的交通轨迹数据分析方法

赵庶旭，屈睿涛，刘昌荣

(兰州交通大学电子与信息工程学院，甘肃 兰州 730070)

当前各类数据都处于极其膨胀的状态，衍生出众多的数据分析方法，且大都有较为成熟的结果，而在这些成熟结果的背后，数据划分作为一个重要步骤，为其做出了很大的贡献。

很多情况下，车辆的轨迹数据都是通过车载GPS装置采集获得，导致这些数据的空间位置任意分布。因此，要想对这些数据进行快速准确的研究，就需要先对数据空间进行划分。面对交通轨迹数据划分问题，出发点大都从其属性方面进行研究，即从加速度、时间、转角、起始位置点、经纬度等这些明显特征点方面入手，并没有考虑将特征点划分与空间划分相结合。因此，轨迹数据划分效果还存在较大的优化空间。

基于特征点的交通轨迹数据划分方法现已有多种，最终可归为两大类：轨迹点划分、轨迹段划分。而对于交通轨迹数据基于空间的划分方法包括以下几个：按屏幕像素划分、按均匀网格划分、按行政区域划分和按照数据本身的属性进行划分[1]。文献[2—6]主要描述了基于轨迹段的划分。其中，文献[2]按照最小描述逻辑对复杂的轨迹数据进行划分，将轨迹划分为轨迹段的形式，但造成了轨迹局部特征丢失的现象。文献[4]借鉴文献[3]提出的拐点检测算法对文献[2]进行了改进，从转角方面入手，对轨迹数据进行了划分，将整段轨迹划分成更小片段来处理，同时也提高了轨迹聚类的精度，但未考虑轨迹数据的空间属性。文献[5—6]利用轨迹数据的位置与几何特性对轨迹进行了切分，考虑了轨迹数据分布的空间属性，但特征点较为单一，划分效果并不理想。文献[7—13]主要描述了基于轨迹点的划分。其中，文献[7—10]提出了基于起始点到终点位置点的轨迹数据分析方法，对城市移动轨迹模式进行了研究，用来揭示城市不同区域间的关系，考虑了区域和轨迹数据分布的联系，提高了数据划分的速度，但划分点单一，遇到道路情况较为复杂时，划分效果不明显。文献[11—13]将位置信息、时间信息、速度、加速度特征运用到轨迹数据划分中，把这些特征归为点来处理，形成簇，然后以可视化的形式展现出来。本文方法与其略有相似，但在特征点的寻找及点群的组建方面要优于以上方法。

基于此，本文充分考虑了轨迹数据分布的空间任意性，结合轨迹数据的位置关系，提出基于轨迹数据特征点与空间划分相结合的划分方法。将某一时间段内的轨迹数据与相应的道路路网进行匹配[14]，然后利用高效的α-Shapes去噪方法进行轨迹数据去噪，得到多个车辆轨迹关键点。在基于点的划分方面，除轨迹数据原因特征点外，再提取车辆行驶轨迹的其他特征点，与其组成点群。在空间划分方面，将道路缓冲区视为轨迹数据分布的空间，采用Voronoi方法对轨迹数据进行划分。该方法提高了基于轨迹段划分时因数据特征点单一，且未考虑轨迹数据的空间属性而导致效果不明显的缺陷，改善了空间划分时，由于信息采样不足而导致的信息不具代表性问题。将其应用于交通拥堵、交通规划、出行方式建议等方面，收到了良好的效果。

1 轨迹数据预处理

1.1 道路信息获取

交通轨迹数据维度较高，但是采集的原始的基于GPS的数据在一般情况下缺乏道路信息，需要通过一定的处理方法，获取到原始GPS数据中的道路信息。

对于得到的原始数据，首先要根据已有的经纬度信息建立缓冲区，其次将原始数据与本文所建立的缓冲区进行相交，得到所在道路的信息。如图1所示，本文利用淄博市张店区的鲁山大道、鲁泰大道和309国道在16：00—17：00时间段内的GPS数据，建立该路段的缓冲区后利用地图匹配算法，把3条道路交汇处(由于交汇区域采集到的GPS数据较丰富，具有代表性)GPS点和路网数据匹配，从而得到图1所示的GPS点在3条道路交汇处的分布结果，方便了后续工作的开展。

图1 GPS点与道路缓冲区

1.2 数据去噪

由于从GPS装置上获取到的数据存在一定数量的噪声，通过地图匹配后，许多数据不一定会落到道路缓冲区内，因此在进行研究前要对这些数据进行去噪，避免造成误差。本文采用α-Shapes算法对轨迹数据进行噪声过滤[15-17]。

车辆在行驶过程中，时常出现变道、转弯、超车等驾驶行为，同时，一些道路枢纽、立交桥、盘旋路及道路交叉口的路况大多为圆形，这些情况就造成车辆行驶路线多为弯曲路线，而α-Shapes算法去噪的原理主要是通过半径圆的滚动来提取边缘轮廓，能很好地适应以上描述的车辆行驶路线。因此在交通轨迹数据分析中，将α-Shapes算法应用在道路上的轨迹数据噪声过滤问题上较为合适。

α-Shapes原理：一般情况下，设有一个离散的点集S，将一个半径为α的圆在点集外滚动，α取合适的值时，这个圆所围成的边界线内的数据即为去噪后的数据，边界外数据为剔除的数据(噪声数据)。α-Shapes算法运算速度快，具有一定的自适应性，通过α值的调节可实现一定的过滤功能，可以将数据噪声和部分小目标过滤掉。

在轨迹数据去噪中，对于边界的确定，是由GPS点集S和α决定的。对于S，设其由n个GPS点组成，可以连接成n(n-1)/2条线，笔者在S中任意选取2个点P1、P2，绘制半径为α的圆，圆心的确定根据测绘学中的求交法得到[18]。

令P1和P2的坐标分别为(x1,y1)、(x2,y2)，求圆心(x,y)，如下

(1)

对于α的取值，需要通过多次试验，最终确定一个合适的值。当α足够小时，每一个点就可以大致认为是边界；而α足够大时，则是S的凸包。笔者对α的取值进行了多次试验，确定对于相对笔直路段，0.33 m较为符合，对于转弯路段及道路交叉口，0.1 m较为理想，如图2所示。

图2 α-Shapes算法去噪对比

2 基于轨迹特征划分的数据分析

2.1 轨迹特征点提取

轨迹的特征点包括起点和终点、明显转弯点和显著停止点(运动停顿点)等。若轨迹是一条长直线段，则只需获取其部分特征点。由于以上所述的特征点对于解决本文描述的问题还存在不足，因此，本文提出了较为全面的获取轨迹特征点的方法，以更好地适应轨迹数据分布的空间任意性问题。一些轨迹的明显特征点如图3所示。

图3 轨迹明显特征点

2.1.1 轨迹特征点描述

轨迹T=(xi,yi,ti)，1≤i≤n，n≥2，其中xi和yi为空间坐标，ti为时间，则还需提取的轨迹特征如下。

(1) 最小转角点：连续轨迹段的方向之间的最小角度，如图4所示。

图4 轨迹最小转角

(2) 最短停留时间点：在大致相同的位置花费的最短停留时间，被视为重要的停留。

(3) 最短距离点：两者连续的点，之间的距离连续低于其他连续点之间的距离，这两个点被视为这条轨迹的最短距离点。

图5 轨迹最短距离点

(4) 最大距离点：两者连续的点，之间的距离连续大于其他连续点之间的距离，这两个点被视为这条轨迹的最大距离点。

2.1.2 算法描述

编程采用Java语言，令C为轨迹特征点的集合，提取轨迹特征点的相关步骤算法描述如下：

step1 定义C={(x1，y1，t1)}；inti=1。

step2 intj=i+1。

step3 如果j>n，执行第九步；

否则结束。

step4 计算两点间的空间距离。

step5 判断两点间空间距离是否大于最大距离，则令C=C∪{(xj,yj,tj)}，并执行第2步，否则结束。

step6 执行k=j+1循环，并判断两点间的空间距离是否大于最小距离，是则执行第2步；否则结束循环，进行第9步。

step7 计算最短停留时间。

step8 计算最小转角。

step9 添加所得点到C集合，令C=C∪{(xj,yj,tj)}。

step10 返回C。

通过该方法，可以得到轨迹特征点，将这些特征点与原有轨迹数据特征点相结合，为后续的轨迹数据空间划分作辅助。

2.2 Voronoi划分

2.2.1 轨迹点分类

对得到的轨迹特征点进行一个简单的分类，本文采取的方法是提取点群的质心(平均点)，计算点之间的欧氏距离，距离近的点组成点群，质心点作为Voronoi图细分的生成元。Voronoi图细分是指通过添加三角形的方式对一个网络的三角形进行细分，这些新添加的三角形可以偏移到一个新的位置。本文利用欧氏距离计算方法对轨迹点进行分组

(2)

通过欧氏距离的计算，将距离相近的点分为一组，图6所示为省级道路与乡镇道路上轨迹特征点的分布位置。

图6 特征点分布

2.2.2 Voronoi划分定义

Voronoi图[19-22]是计算几何领域中非常重要的一种结构，由俄罗斯科学家M.G.Voronoi提出，针对平面内n个离散的点，将平面分成多个区域，所得区域就是本文所要划分轨迹数据最近点的集合。

设P={P1,P2,…,Pn}⊂R3为三维欧氏空间内的n个点,d(P,Pi)为P和Pi间的欧氏距离，将由

所给出的对空间的分割称为以P={P1,P2,…,Pn}⊂R3为空间点集的Voronoi图,V(Pi)(i=1,2,…,n)为Voronoi图的晶胞，Pi(i=1,2,…,n)为Voronoi图的母点(生成元)，如图7所示。

图7 Voronoi图

2.2.3 Voronoi划分

进行Voronoi划分之前，本文首先对特征点数据进行处理，找到特征点群的质心点，然后按照质心点的位置进行Voronoi划分，其中圆点为母点，母点四周的多边形为Voronoi划分的区域，即为划分后轨迹数据点的集合。

3 基于GPS数据的实例验证

为进一步说明本文方法，在共同依托项目的城市交通数据可视化平台上进行验证[23]，将前文提出的算法与山东省淄博市的出租车GPS数据相结合，然后在与当地路网数据匹配的基础上，进行实际GPS数据的实例验证。笔者利用张店区的北京路、鲁泰大道、南京路、公园北路、中润大道的主要车辆行驶路段筛选出16：00—17：00点具有代表性的382条出租车运行轨迹，通过特征提取方法得到了6592个特征点数据进行验证。首先得到特征点质心分布效果图，如图8所示。

图8 实际特征质心点

3.1 多特征轨迹数据划分方法的优势

为说明多特征轨迹数据划分方法的优越性，笔者利用淄博市张店区(北京路、鲁泰大道、南京路、公园北路、中润大道)的主要车辆行驶路段筛选出16：00—17：00点的数据，利用其他方法进行了试验，并与本文提出的方法进行了对比，结果见表1。

表1 划分效果对比

注：空间分布适应性是指划分后的匹配数据与原始随机分布数据之间的比例。

从表1中数据可以看出，本文方法在数据划分点上面明显多于其他方法，可以很好地适应数据空间分布随意性的特性。

3.2 实物验证

为更好地说明多特征划分方法在适应空间分布随意性上的优势，本文选择表1中基于转角的数据划分方法进行验证，对青银高速、淄博西枢纽立交、滨莱高速、原山大道、鲁泰大道、中润大道、世纪路，以及周围车辆行驶较多的县道、乡镇道路的16：00—17：00的轨迹数据进行划分，并利用共同依托项目的城市交通数据可视化平台进行验证，如图9所示。

图9 多特征划分下主要路段GPS数据划分

从划分效果图可以看出，多特征划分效果明显优于其他划分的效果，该方法较好地克服了数据空间分布随机性问题。

4 结 语

本文对轨迹数据按照其位置关系进行车辆行驶特征点的提取，利用α-Shapes去噪算法，对提取到的特征点按照其分布的几何相关性，进行简单分组并形成点群，且利用其空间分布的属性，按照Voronoi多边形进行分割，克服了轨迹数据空间分布的任意性缺陷，提高了轨迹数据划分的效率。最后利用山东省淄博市出租车轨迹数据，依托本课题项目城市交通数据可视化平台进行实例验证，取得了良好的效果。后期将会在动态数据分析及可视化方面进行深入研究。