基于GPS轨迹的移动用户特征挖掘算法

方英兰+杨勇

摘要：通过对移动用户的出行方式的识别，可以挖掘出用户的移动特征。目前识别移动用户的出行方式的方法在多种出行方式交替出现时，识别的准确度并不高，在特殊情况下，甚至很低。针对以上问题，提出了基于速度和转角相结合的轨迹划分的识别方法，首先利用速度小于固定速度阈值和转角小于固定转角阈值的位置点将原始GPS轨迹划分为交通方式单一的子轨迹段，然后使用相同的方法对子轨迹段进行划分。实现结果表明，提出的算法能够有效识别不同出行方式，效果较一般更好。

关键词：出行方式；轨迹划分

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2017）01-0211-04

1 引言

过去研究者通过参与者填写问卷调查和电话采访的形式，来收集出行方式的信息，这通常会导致遗漏短途旅行和不准确的数据[1-2]。然而随着全球定位系统（GPS）的迅速发展，因其覆盖范围广、定位速度快、定位精度高等特点，被普遍应用于大多数移动终端上。[3]而装有GPS的移动终端使位置点的采集变得容易，这给轨迹数据挖掘研究提供了便利。[4]拥有GPS功能的智能手機可以快速地定位和保存用户的空间位置和定位时间，获取大量移动用户的轨迹数据。移动用户轨迹可由位置点按照时间排序得到，分析移动用户轨迹，可以挖掘移动用户出行特征，了解用户的出行规律，活动规律，为解决交通拥堵，对城市交通进行科学规划和合理调度。

文献[5]利用速度小于某一阈值的数据点将原始GPS轨迹划分为交通方式单一的子轨迹段，然后对子轨迹段分别抽取特征，采用监督式学习方法建立推断模型对不同子轨迹的交通方式进行识别。文献[6]利用手持GPS设备记录的GPS定位轨迹，选取方式段长度，平均速度、速度均值、速度协方差等、最大的三个加速度、最大的三个速度等统计值，分别利用决策树、贝叶斯网、支持向量机、条件随机场等模式识别方法，对出行者采用的交通方式进行了识别。文献[7]提出了一种通过追踪AGPS手机中的定位数据来识别交通流中的乘客所采用的交通方式的方法，通过Weka软件建立起BP神经网络来对AGPS定位数据进行交通方式的识别。文献[8]根据转角将轨迹划分成若干轨迹段，然后通过计算轨迹段的结构相似度来判断轨迹的匹配程度，进而完成轨迹聚类。文献[9]提出了三种基于统一时间轨迹分段的算法，充分考虑了移动对象在轨迹片段上的地理空间、时间的结构，并运用了基于时间序列的距离方法将轨迹划分为许多空间和时间均匀的小片段，最后使用了最大移动速度来检测基于统一时间的空间异常点。文献[10]将一段包含多种交通方式的轨迹分割成交通模式单一的片段，通过检测两种不同交通方式之间的潜在转换点来自动识别交通方式，具有相同交通方式的相邻片段被合并在识别过程中。并引入交通模式的层次概念来对划分的片段进行交通模式识别。

根据以上分析可知，本文提出一种基于轨迹段划分和贝叶斯网络相结合的方式来识别移动用户的出行方式。该方法首先通过计算速度和转角分别小于各自阈值的转折点，将GPS轨迹进行划分，由此可以获得多种出行方式其中之一的子轨迹段，再从子轨迹段中提取不同的出行特征。建立贝叶斯网络，优化贝叶斯网络推断模型，对分段过程中形成的每段子轨迹进行出行方式识别。

2 出行方式识别

2.1 相关定义

为了更好的描述本文所提出的方法，首先介绍一些所使用的基本定义来对轨迹和相关属性进行形式化描述。

定义1 GPS轨迹（GPS Trajectory，GPSTR）由一系列不断变化的GPS特征点（GPS Trajectory Points）构成，而这些点会随着时间的推移、位置在空间上的变化而变化。这些GPS特征点包含大量的信息，其中最重要的就是位置信息和时间信息，它通常以经纬度的形式来表示。GPSTR={GPSTR1，GPSTR2，…，GPSTR?，…，GPSTRn}，GPSTR?={，，…，}，P?n={Latin，Lon?n}，i=1，2，3，…，n，t?1

定义2 GPS子轨迹（GPS SubTrajectory）一段完整轨迹所包含的部分轨迹，它是由转折点划分出来的，包含连续相对紧密的数据点，每段子轨迹代表一种出行方式，不同的子轨迹中相邻数据点间的间隔不同。GPSTR={SubTR1，SubTR2，…，SubTR?，…，SubTRn}，其中子轨迹SubTR?表示第i个子轨迹，SubTR?={，，…，}，P?j={Lat?j，Lon?j}，1

定义3 转折点，运动实体在特定区域内，速度保持较低状态、停留时间超过一定阈值，且转角超过一定阈值位置点。

2.2 基于转折点的轨迹划分

人们在出租车站台或路边乘坐出租车时，在等车的过程中，人总是在原地或周边徘徊，此时人的速度总是保持几乎静止。可能由于各种情况，这种状态可能会持续好久，导致其产生大量轨迹段，而这些轨迹段之间的转角一般变化比较小。利用转折点将便可以对GPS轨迹进行划分，每一段称为子轨迹，现假设每一个子轨迹段都只有一种出行方式。如图1所示，假设用户轨迹由12个位置点组成，这些点是按时间序列排序的，其中点a1，a2，a3，a4为转折点，转折点将轨迹段划分为几段出行方式不同的子轨迹段。

现实生活中由于交通事故、上班高峰时期等原因导致交通拥堵，此时转折点的识别可能会出现两种不同的情况，正常状况指交通顺畅，无拥堵且用户只有在改变出行方式时才会发生短暂的停留或徘徊。此时轨迹中每个位置点的速度和方向是不同的，分别计算其速度和转角，寻找速度值小于某一阈值，转角值小于另一阈值的点，这时包含多个位置点的轨迹便被这些转折点划分为一个个独立的子轨迹段，每段子轨迹段代表一种出行方式，如图2所示，寻找出的转折点即为速度小于阈值且转角小于阈值的点。

当城市出现交通拥堵时，人们乘坐的出行工具会不间断的发生变化，如时快时慢，时停时走，此时一段轨迹内可能会出现速度和转角小于各自閾值的转折点，这些点将这出行方式相同的轨迹段划分为又划分为距离更近的子轨迹段。如图3所示。在公交车和乘坐出租车时，出现了多个速度和转角小于阈值的点或停留点，如点p1，p2，p3，它们将一种出行方式下的子轨迹段又划分成多个子轨迹段，如tr1，tr2。

针对轨迹段出行方式已知，但有多个转折点时，可能轨迹段的出行方式有多种。为了能精准地找到转折点，需要分别计算这些转折点前后子轨迹段的平均速度和平均转角，如果这两个平均速度和平均转角值相近或相等，则将这两个识别有误的转折点合并，表明此时并没有发生出行方式的改变。否则不进行合并。如图4所示，在乘坐公交车子轨迹段中，出现了四个转折点a2，a3，p1，p2.分别计算a2和p1，p1和p2、p2和a3间的速度v1、v2、v3，转角θ1、θ2。如果v1、v2、v3相近或相等且θ1、θ2相近或相等，则说明没有发生出行方式的转换，此时将p1和p2合并，在乘坐公交车的子轨迹段中，只有a2和a3两个转折点。

算法1描述了如何识别转折点的详细步骤，第3行计算位置点的速度，第4、5行计算位置点的转角，第6行寻找待转折点，第7～13为判断待转折点是否为转折点的过程，其中第7～8行为交通顺畅时识别待转折点为转折点的方法，其中10～13行为交通出现堵塞时转折点的识别步骤，第10、11行为计算平均速度和平均转角，其中Li、Ti、SPi、θi分别表示子轨迹段的长度、时间、平均速度和转角。第12行为判断平均速度和转角是否相等或接近，如果符合要求则合并中间的待转折点，将子轨迹头尾待转折点识别为转折点。

算法1 find_TurnPoint（N，speedThreshold，cornerThreshold，trafficCondition）

输入：GPS位置点N，一个速度阈值speedThreshold，一个转角阈值cornerThreshold，交通顺畅、交通堵塞两种情况

输出：一组转折点集合TPCollection

1. i=0；pointNum=|N|；

2. While i

3. speed=length/time；

4. α=arccos（（length2+lengthi+12-hypotlength2）/2lengthi*lengthi+1）；

5. θ=|π-α|；

6. if speed

7. if trafficCondition is normal then

8. TPCollection.Add（pi）；

9. else

10. SPi=aveSpeed（Li，Ti）；

11. θi=aveθ（θi，θi+1）；

12. if SPi≈SPi+1 || θi≈θi+1then

13. TPCollection.Add（p1，pn）；

14. break；

15. i++；

16. return TPCollection；

2.3 特征提取

移动用户出行时方式各异，导致出行速度和转角又各有不同。公交车沿着固定的线路行驶，其速度一般变化不大，在一段路程上其转角变化很小甚至没有任何变化。出租车由于所在用户的不同，道路情况不同，其具有一定的不确定性，所以其速度和转角一般变化较大。因此我们可以通过计算移动用户的速度和转角来识别其出行方式，找出其出行规律。本文考虑的因素有速度，平均速度，夹角，转角，平均转角，相关定义如下：

1）速度：运动实体从起始位置到终点位置单位时间内位置变化大小程度，用Vi=Li/ti表示，i=1，2，3，…，n.

2）平均速度：运动实体在时间段内其位置变化大小的平均程度。用V=（Vi+Vi+1+…+Vj）/n表示，其中1≦i≦n，1≦j≦n，n表示当前子轨迹段内位置点的数目，Vi表示位置点i处的速度。

3）夹角：运动实体在某点相邻两个轨迹段之间的夹角，它反映了运动实体的运动趋势，用αi=arccos（（a2+b2-c2）/2a*b）表示，a，b分别表示位置点i处相邻轨迹段的长度，c表示位置点i的斜边长度，其中1≦i≦n。

4）转角：运动实体在某点相邻两个轨迹段之间方向偏移量。规定外向转角为正值，内向转角为负值，用θi=|π-αi|，其中1≦i≦n。

5）平均转角：一段时间内运动实体的子轨迹段之间的平均偏移程度。用θ=（θi+θi+1+…+θj）/n表示，其中1≦i≦n，1≦j≦n，n表示子轨迹上位置点的数目，θi表示位置点i处的转角。

如图5一段轨迹包括3个位置点，如a1，a2，a3，位置点a1，a2之间的距离为L1，时间间隔为T1，a2和a3之间的距离为L2，时间间隔为T2，以及a1和a3的距离L3，可以应用式（1）、（2）和式（3），计算a1的速度，轨迹段Tra1a2和Tra2a3之间夹角，转角。

2.4 模型识别

本文使用贝叶斯网络对出行方式进行自动识别。首先计算轨迹中位置点的速度和相邻轨迹段之间的转角，识别速度小于速度阈值和转角小于转角阈值的转折点，划分GPS轨迹为多个子轨迹段，再计算子轨迹段的平均速度和平均转角，对子轨迹段进行转折点判断，最终识别移动用户的出行方式。利用移动用户速度，平均速度和转角、平均转角来建立出行方式贝叶斯网络，再使用测试集对该贝叶斯网络进行优化。最终使用建立的贝叶斯网络自动识别轨迹段的出行方式。

3 实验结果分析

针对本文提出的结合速度和转角来进行轨迹划分的出行方式识别方法，，以北方工業大学数据库实验室开发的移动互联资源管理平台的手机端手机的数据作为实验数据，本数据集记录了338个用户在3年之内的移动行为，每个用户持有一个安装有开发的易划APP的智能手机来将各自的位置数据回传到服务器的数据库保存，通过挖掘这些位置数据，可以得到用户个人的出行方式。选择该数据集中的部分数据作为训练集，剩余数据作为测试集，来验证该方法。

3.1 分段方法精确度

为了突出本文提出的速度和转角相结合的转折点划分方法的准确性，分别选择基于单一速度的分段方法[4]和基于参考时间的分段方法[9]与之进行对比。基于单一速度的分段方法只利用速度来进行轨迹分段，基于参考时间的分段方法利用相同时间间隔将轨迹分段。本文选择速度区间0.4～4m/s来测试基于单一速度的分段方法不同数据集的精确度，选择时间区间40～280s来测试参考时间的分段方法不同数据集的精确度，而对于基于速度和转角相结合的分段方法，选择速度区间0.5～5m/s和转角区间4°～40°测试不同数据集的精确度。如图6、图7和图8所示，三种方法在不同数据集时大体都是呈先上升达到最高点后下降趋势，只是在单一时间划分方法时略微不同，此方法时在数据集1和数据集3时中间有少许下降。整体来看速度和转角相结合的方法的精确度明显高于单一速度划分方法和统一时间划分方法。由于本文所提方法考虑了两种因素，且这两个因素对于出行方式的识别具有关键作用，且在现实生活中符合用户的出行特点，所以本方法识别的精确度更高。

4 结语

本文提出了一种将速度和转角相结合的轨迹段拆分方法，并利用建立决定出行方式的贝叶斯网络，最终识别出各个分段的出行方式。首先计算各个分段的速度和转角，识别出转折点。然后再对子轨迹段进行平均速度和平均转角，根据平均速度和平均转角来识别子轨迹段上的出行方式。根据训练集得到的结果建立速度、平均速度和转角、平均转角决定的贝叶斯网络，并使用测试集来验证建立的贝叶斯网络的正确性，并做调整。本方法将速度和转角相结合，相比之前的方法[4][9]，识别的出行方式更契合移动用户，也符合现实生活。但由于转角的计算难道大，计算的转角又不那么准确，增加了计算的时间，且识别时考虑的因素相对来说比较不完整。下一步找到快速、准确的计算转角方法，并考虑其他因素，如移动用户的出行喜好，移动用户所在区域的交通状况等，来提高出行方式识别的精确度。

参考文献：

[1] S.Bricka and C.Bhat.Comparative Analysis of Global Positioning System-Based and Travel Survey-Based Data[J].Transportation Research Record：Journal of the Transportation Research Board，1972：9-20，Jan 2006.

[2] G.Draijer，N.Kalfs，and J.Perdok.Global Positioning System as Data Collection Method for Travel Research[J].Transportation Research Record：Journal of the Transportation Research Board，1719：147-153，Jan 2000.

[3] Jianwei Han，Micheline Kamber，Jian Pei.数据挖掘：概念与技术[M].北京：机械工业出版社，2012.7.

[4] 李海.基于GPS轨迹的周期模式发现[J].电子设计工程.2015，21（23）：24-27.

[5] 肖艳丽，张振宇，杨文忠.基于GPS轨迹的用户移动行为挖掘算法[J].计算机应用与软件.2015.11（32）：83-87.

[6] 袁华，钱宇，杨锐.基于GPS轨迹的用户兴趣点及频繁路径挖掘研究[J].系统工程理论与实践.2015.5（35）：1276-1282.

[7] 袁冠，夏士雄，张磊，周勇.基于结构相识度的轨迹聚类算法[J].通信学报.2011，9（32）：103-110.

[8] Yoon H，Shahabi C.Robust Time-Referenced Segmentation of Moving Object Trajectories[C]/ /ICDM，2008：1121-1126.