一种距离误差可控的DPTS-SP-Prac改进算法

董天放　孟庆彬　舒　奎

1(大连东软信息学院　辽宁 大连 116023)2(大连工业大学信息科学与工程学院　辽宁 大连 116034)

0　引　言

伴随着经济的发展和科技的进步，各种具备定位功能的设备和智能移动终端触手可及，这些设备每天会产生大量的轨迹数据。这些轨迹数据中隐藏了很多有价值的知识模式，个人的出行轨迹可以反映出一个人的职业特征，通过对城市群体的轨迹进行分析，可以发现城市的热点区域和对城市的功能区域进行识别[1]。但随着用户规模不断增大，轨迹数据的数量几乎呈指数趋势进行增长。据2012年的一篇文献中的数据表明，以北京市的67 000 辆出租车为例，如果这些出租车以2～3 s频率向数据中心发送GPS定位数据，仅这些出租车每天就能产生高达60 TB的轨迹数据[2]。海量的轨迹数据给基于位置服务的应用带来了很多挑战：(1)这些数据会占据大量的存储空间；(2)对于在线的应用，传输这些数据会消耗大量的网络流量；(3)当在浏览器上展示这些数据时，会给浏览器带来很大的负担，每绘制1 000个轨迹点就需要约1 s的时间[3]；(4)当轨迹数据的量较大时，会使得轨迹数据的查询和分析变得困难。因此，在使用轨迹数据前对数据进行压缩处理就显得尤为必要。

轨迹压缩的主要思想是减少轨迹中定位点的数量，同时确保最小化的信息丢失。传统的轨迹压缩算，如Douglas-Peucker算法[4]、基于Douglas-Peucker改进的TD-TR算法[5]、最优化的轨迹压缩算法[6-9]、近似最优化的轨迹压缩算法[10-11]、基于开放窗口的OPW-TR算法[6]、SQUISH算法[12]以及 SQUISH-E[13]算法仅关注于捕捉轨迹的位置信息，因此在使用这些算法进行轨迹压缩时易造成轨迹方向信息的丢失。然而，轨迹的方向信息对于描述轨迹的语义起着至关重要的作用，移动对象运动方向的改变暗示了用户的行为(例如，停留、拍照等)[14]。此外，很多基于位置服务的应用都使了用轨迹的方向信息，例如：地图匹配[15]、轨迹聚类[16]、轨迹分类[17]以及孤立点检测[18]。DPTS-SP-Prac算法[19]是一种基于方向保持的轨迹压缩算法，能够有效地控制轨迹的方向误差。由于该算法考虑到了轨迹的方向信息，故相比于传统的基于位置的轨迹压缩算法，该算法具有更加广泛的应用范围，支持的应用更多。

DPTS-SP-Prac算法虽然能够有效地捕捉轨迹的方向信息，但该算法的理论最大距离误差是与压缩后的轨迹段是相关的，是不可控的。对于某些轨迹进行压缩后，产生的最大距离误差可能很大，可能是用户不能接受的。为了解决这个问题，提高算法的可用性，本文提出了一种距离误差可控的DPTS-SP-Prac改进算法，这种改进提高了DPTS-SP-Prac的可用性，减小了压缩误差，提高了精度，使得轨迹压缩变得更加准确。

1　轨迹压缩的相关定义

定义1轨迹：一条长度为n的轨迹T是一系列以时间为顺序的定位点的集合，即T={P1,P2,…,Pn-1,Pn}。T中的每一个定位点Pi均由一个三元组组成，其中(xi，yi)为移动对象在ti时刻的位置坐标。

定义2轨迹压缩：给定一条轨迹T={P1,P2,…,Pn-1,Pn}，轨迹压缩就是要寻找一系列以时间为顺序的定位点的集合T′(T的子集)，即T′={Pc1,Pc2,…,Pc(m-1),Pcm}，其中1=c1

定义3压缩率：给定原始轨迹T={P1,P2, …,Pn-1,Pn}及其压缩后的轨迹T′={Pc1,Pc2,…,Pc(m-1),Pcm}。压缩率CR的定义如公式所示：

(1)

定义4垂直距离误差：给定原始轨迹T及其压缩后的轨迹T′，T中的定位点Pi相对于T′的垂直距离误差可表示为Pi与Pi的估计点Pi′之间的距离。如果T′中包含Pi，则Pi′ =Pi。否则Pi′为Pi与直线predT′ (Pi)succT′(Pi)的垂点，其中predT′ (Pi) 与succT′(Pi)分别表示T′中离Pi最近的前驱和后继。

图1用轨迹T={P1,P2,…,P6}及其压缩后的轨迹T′={P1,P4,P6}阐述了垂直距离误差。如图1所示，轨迹T中定位点P1、P4、P6对应于T′的垂直距离误差为零。P2的垂直距离误差为P2到直线P1P4的垂直距离。

图1　垂直距离误差

定义5方向误差：给定原始轨迹T及其压缩后的轨迹T′，轨迹T中Pi点对应于T′的方向误差可表示为DirectionChange(h1,h2)，其中h1为Pi点的方向，h2为T′中由定位点PsPe构成的射线方向，Ps=predT′(Pi+1)，Pe=succT′ (Pi)。方向变化函数DirectionChange及方向函数Direction的定义如下。

(2)

(3)

(4)

2　距离误差可控的DPTS-SP-Prac改进算法

2.1　算法描述

给定原始轨迹T={P1,P2,…,Pn-1,Pn}和角度阈值θ，DPTS-SP-Prac算法通过三个步骤实现轨迹压缩：(1) 基于给定的轨迹T和角度阈值限定条件构建一个图，对于任意两个定位点(Pi,Pj)(1≤i

2.2　算法伪代码

为了更简洁地对算法的伪代码进行描述，我们首先给出两个符号Δ(Pi,Pj)和(Pi,Pj)。其中Δ(Pi,Pj)的含义为Pi与Pj之间的定位点与线段PiPj的最大垂直距离。(Pi,Pj)的含义为Pi与Pj之间的定位点与射线之间的最大方向变化。图2给出了距离误差可控的DPTS-SP-Prac改进算法的详细描述。该算法维持了两个集合，集合H用以存储BFS检索过的定位点，集合U用来存储未被访问过的定位点。首先H0的值被设置为{P1}，U的值被设置为{P2,P3,…,Pn}，并初始化l=1。算法的迭代通过Hl-1来计算Hl。对于Hl-1中的每个点Pi,U中的每个点Pj，检查位于PiPj之间的所有定位点是否均满足垂直距离误差条件和方向误差条件，如果满足条件，则进一步判断Pj是否为轨迹T的终点，如果Pj=Pn则返回压缩后的轨迹，算法结束。如果Pj≠Pn，则更新集合U和Hl，继续进行搜索。

距离误差可控的DPTS⁃SP⁃Prac改进算法INPUT：　T={P1，P2，…，Pn}　　　　//原始轨迹　　μ　　　　//垂直距离阈值　　θ　　　//角度阈值1．H0={P1}；U={P2，P3，…，Pn}；l=1；2．while(true){3．　Hl=？4．　for(eachPiinHl-1andeachPjinUwherei

图2距离误差可控的DPTS-SP-Prac改进算法

3　算法评估

为了对改进的算法进行评估，我们使用Scala语言实现了DPTS-SP-Prac算法及其他的一些轨迹压缩算法，并选取了Geolife数据集[20-22]作为实验数据。Geolife 数据集的轨迹数据由182个用户，历时五年收集而来。其中73个用户标记了他们轨迹的交通模式(开车、乘公交、骑自行车、乘地铁、步行等)。Geolife 数据集总共包含了17 621条轨迹，总长度1 292 951 km，累积时间达到50 176 h。这些轨迹数据来自不同的GPS记录器以及智能手机，轨迹的采样周期也不尽相同，其中91.5%的轨迹数据为密集采样(即每隔1～5 s或每隔5～10 m记录一个定位点)。我们在Geolife数据集中选取了两条不同交通模式的轨迹作为实验数据。轨迹1是一条公交车的行驶轨迹，该轨迹包含2 045 个定位点，历时50分钟 (从2008-06-18, 12:33:34 到2008-06-18, 13:23:02)。轨迹2是一条高速公路上出租车的行驶轨迹，其中包含2 167个定位点，历时37 min(从2008-04-04, 07:16:50 到2008-04-04, 07:53:00)。

为了评估轨迹压缩算法压缩的精确程度，我们选取了平均垂直距离误差APDE(Average Perpendicular Distance Error)及平均方向误差ADE(Average Direction Error)对算法进行评估。给定原始轨迹T={P1,P2,…,Pn}及压缩后的轨迹T′，平均垂直距离误差及平均方向误差的定义如下：

(5)

(6)

3.1　相同角度阈值下DPTS-SP-Prac与DPTS-SP-Prac改进算法的比较

图3在相同角度阈值下，就平均垂直距离误差，对DPTS-SP-Prac和DPTS-SP-Prac改进算法进行了对比。从图中可以看出，随着角度阈值的增大，未改进的原DPTS-SP-Prac算法的垂直距离误差急速增大，最大时接近2 km。而平均2 km的误差，在有些情况下是不可接受的，因此一个可控的距离误差对于DPTS-SP-Prac显得尤为重要。而对于本文提出的改进算法而言，由于设置了一个100 m的距离阈值，因此不论多大的角度阈值都不会使得压缩结果产生一个超出预期的距离误差。

(a) 轨迹1公交车行驶轨迹

(b) 轨迹2高速公路上汽车的轨迹图3　平均垂直距离误差

3.2　相同压缩率条件下对DPTS-SP-Prac改进算法评估

为了验证改进后的算法的有效性，我们选取了一些传统的基于位置的轨迹压缩算法与所提出的算法进行对比。如图4所示，在相同压缩率的条件下，想比于原始的DPTS-SP-Prac，本文提出的改进算法有效地降低了压缩的平均垂直距离误差。虽然本文算法的平均垂直距离误差比传统的基于位置的轨迹压缩算法的误差大，但接下来我们将会看到该算法在轨迹方向信息保持方面的优势。

(b) 轨迹2高速公路上汽车的轨迹　　　　　　　图4　平均垂直距离误差

如图5所示，在相同压缩率的条件下，由于传统的基于位置保持的轨迹压缩算法只关注于位置信息的保持，因此这些算法会丢失较多的方向信息。而基于方向保持的DPTS-SP-Prac及其改进算法，则能够较好地保持轨迹的方向信息。对于轨迹1，本文提出的改进算法在压缩率达到30时的平均方向误差，比基于位置保持的轨迹压缩算法在压缩率为5时的误差还小。结合图4和图5可以看出，本文提出的算法在有效地保持轨迹的方向信息的同时有效地降低了平均垂直距离误差，提高了算法的可用性。

(a) 轨迹1公交车行驶轨迹

(b) 轨迹2高速公路上汽车的轨迹图5　平均方向误差

4　结　语

本文提出一种距离误差可控的DPTS-SP-Prac改进算法，其解决了DPTS-SP-Prac算法距离误差不可控的问题，提高了算法的可用性。该算法在原有的算法的基础上，通过增加对距离误差的检查，实现了距离误差的可控。因此，在使用该算法进行压缩时，不会出现超出用户预期、不可预料的距离误差。真实世界数据集下的实验结果验证了这种改进的优越性，相比于原有算法，该改进算法压缩结果更加精确，具有更小的误差和更高的可用性。

[1] 李婷，裴韬，袁烨城. 人类活动轨迹的分类、模式和应用研究综述[J]. 地理科学进展，2014，33(7)：938-948.

[2] 袁晶. 大规模轨迹数据的检索、挖掘和应用[D]. 合肥：中国科学技术大学，2012.

[3] Chen M, Xu M, Fränti P. A fast O(N) multiresolution polygonal approximation algorithm for GPS trajectory simplification[J]. IEEE Transactions on Image Processing, 2012, 21(5):2770-2785.

[4] Douglas D H, Peucker T K. Algorithms for the reduction of the number of points required to represent a line or its caricature[J]. International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122.

[5] Meratnia N, By R A. Spatiotemporal compression techniques for moving point objects[C]// Springer, 9th international conference on extending database technology. Crete: Springer, 2004.

[6] Bellman R. On the approximation of curves by line segments using dynamic programming[J]. Communications of the Association for Computing Machinery, 1961, 4(6): 284-286.

[7] Perez J C, Vidal E. Optimum polygonal approximation of digitized curves[J]. Pattern Recognition Letters, 1994, 15(8): 743-750.

[8] Salotti M. Improvement of perez and vidal algorithm for the decomposition of digitized curves into line segments[C]// IEEE, 15th Conference on pattern recognition. Barcelona: IEEE, 2000.

[9] Salotti M. An efficient algorithm for the optimal polygonal approximation of digitized curves[J]. Pattern Recognition Letters, 2001, 22(2): 215-221.

[10] Kolesnikov A, Fränti P. A fast nearoptimal min-# polygonal approximation of digitized curves[C]// IEEE, 16th International conference on automation. Novosibirsk: IEEE, 2002.

[11] Kolesnikov A, Fränti P. Reduced search dynamic programming for approximation of polygonal curves[J]. Pattern Recognition Letters, 2003, 24(14): 2243-2254.

[12] Muckell J, Hwang J, Patil V, et al. SQUISH: an online approach for GPS trajectory compression[C]// ACM, 2nd international conference on computing for geospatial research and applications. Washington D.C.: ACM, 2011.

[13] Muckell J, Olsen P W, Hwang J H, et al. Compression of trajectory data: a comprehensive evaluation and new approach[J]. GeoInformatica, 2014, 18(3): 435-460.

[14] Chen Y K, Jiang K, Zheng Y, et al. Trajectory simplification method for location-based social networking services[C]// ACM, 2009 International workshop on location based social networks. Seattle: ACM, 2009.

[15] Brakatsoulas S, Pfoser D, Salas R, et al. On map-matching vehicle tracking data[C]// International Conference on Very Large Data Bases. VLDB Endowment, 2005:853-864.

[16] Lee J G, Han J, Whang K Y. Trajectory clustering:a partition-and-group framework[C]// ACM SIGMOD International Conference on Management of Data. ACM, 2007:593-604.

[17] Lee J G, Han J, Li X, et al. TraClass : trajectory classification using hierarchical region-based and trajectory-based clustering[J]. Proceedings of the Vldb Endowment, 2008, 1(1):1081-1094.

[18] Lee J G, Han J, Li X. Trajectory Outlier Detection: A Partition-and-Detect Framework[C]// IEEE, International Conference on Data Engineering. IEEE Computer Society, 2008:140-149.

[19] Long C, Wong C W, Jagadish H V. Direction-preserving trajectory simplification[J]. Proceedings of the Vldb Endowment, 2013, 6(10):949-960.

[20] Zheng Y, Zhang L, Xie X, et al. Mining interesting locations and travel sequences from GPS trajectories[C]// International Conference on World Wide Web. ACM, 2009:791-800.

[21] Zheng Y, Li Q, Chen Y, et al. Understanding mobility based on GPS data[C]// International Conference on Ubiquitous Computing. ACM, 2008:312-321.

[22] Zheng Y, Xie X, Ma W Y. GeoLife: A Collaborative Social Networking Service among User, Location and Trajectory[J]. Bulletin of the Technical Committee on Data Engineering, 2010, 33(2):32-39.