论文研究-GPS轨迹中活动停留点识别的多层分割算法 .pdf

所需积分/C币:16 2019-08-27 14:28:07 1.38MB .PDF
收藏 收藏
举报

GPS轨迹中活动停留点识别的多层分割算法,张治华,季民河,个人移动通讯和位置感知设备的广泛使用产生了大量可用于信息服务的出行轨迹数据。从轨迹数据挖掘出行信息的关键在于停留识别和语
山武花论文在丝 http://www.paper.edu.cn GPS轨迹数据缺失现象相关普遍,使用该方法会产生较大误差。 CB-SMo'算法:将 DBSCAN中邻域的设定方法从点计数改为时间阈值,解决了之前 等时距假设存在的问题,可以处理带有缺失的数据。但该方法在处理邻域时采用相邻点之间 的距离累加,GPS轨迹中的漂移现象对其影响较大,尤其是停留时产生的较远的漂移对该 方法的精度会产生致命的影响。基于 DBSCAN思路的DJ- Cluster算法的抗噪能力比K中值 算法有所增强,但因采用邻域的距离累加,不可避免长距离漂移的干扰,将单个停餾割裂为 多个,识别精度仍然有限。 从计算效率上看,无论哪种密度算法均趋于偏低。由于引入邻近多点,对每点的计算需 遍历其他点,训算复杂度为O(n),即使用空间索引机制仍有O(n*logn),内存开销也较大。 本文根据状态的连续性特征,提出了种自下而上逐层合并的轨迹分割思路(Bott0nUp Trajectory Segmentation,BUTS),旨在提高识别精度和改善计算效率。传统的轨迹分割把研 究焦点放在停留与移动的静态特征差异上。而实际上,轨迹中的移动作为停留的相对过程, 也可为停留标志提倛有用信息。停留和移动在本质上同属移动状态,其持续一定时间或跨越 定距离的特点是一种状态区别于另一种状态的基本表征。因此对状态连续和变化的区别, 也可以作为停留和移动划分的基本依据。而另一方面,由于人类活动具有多尺度特征,对不 同层次的活动和应用,界定停留和行程的准则可以有所不同。例如在大尺度上的停留,本身 也许包含有小尺度的移动和停留(图1)。多尺度分割算法的日的就在于通过时间或距离阙 值设定,实现对不同尺度活动的探测与合并。 Putuo 秋林阁 普陀区 静女区 中L 长宁 停车场 徐汇区 地美昌x工 七主填 s124 华东师大中山北路校区 本科公寓一 文 江销 闵一 中一闵 阅行校区 华东师大闵行校D 图1人的活动地点的多尺度征示意图:校区之间的出行与校区内部的出行比较。 Fig. 1 Example of human activities at multiple scales: inter-campus versus intra-campus travels. 2研究方法 21相关概念定义 定义1.轨迹( Trajectory):按时间顺序有向相连的时空点集,表达为, 其中→表示有向,x,y表示位置,t表示时间,代表组成轨迹的点个数。 定义2.停留(Stop):为轨迹T的子轨迹( Sub-trajectory),表示为: 山武花论文在丝 http://www.paper.edu.cn S=psI(x,y)nC, Im-t >tresh,ie/ (2) 式中C是由组成S的轨迹点共同定义的空间范围,tm为停留轨迹末点时间,t为首点时 间, thresh为预先设定的时间阈值。定义表明S中的任一点必须落在C之内,且S的首末点 时间差必须大于teh。此外,轨迹的起点和终点也定义为停留。 定义3.移动(Move):相邻两个停留之间的子轨迹,其轨迹点位置自外于Cs。表为: M=P: P: eS, max( (S1)<k,< min(S,), je J, keIl (3) 式中,S和S1为任意两个相邻的停留,S)为停留内轨迹点的时间集,J为子轨迹的总点数 定义4.数据缺失( Missing Link):在GPS轨迹等时记录的情况下,如果任一对相邻 点之间的时间差大于给定阈值T,则认定为一个数据缺失。表达为 ML=Pk, Pk-iItk-tk->T (4) 定义5.数据漂移( Drift):由于数据接收质量等问题造成GPS轨迹点偏离超过一定距 离阈值D,即构成数据漂移。表为 DF=PE distance(Pk, pk. me)> (5) 漂移属轨迹中的暎音,对停留点识别产生很大干扰。漂移鸴与数据缺失相混杂,无法在 颀处理中通过简单的速度阈值去除,只能在停留识别的冋时予以去除。漂移使待一次停留被 割裂成多次缺失和多次假的移动,并且对人工判读停留建立训练样木造成较大十扰。 定义6.岀行或行程(Trip):在从GPS轨迹中提取出行信息时,可以用轨迹中的停留 和移动对出行加以定义。如果一段移动同时满足如下条件,则可以视为一次出行 (1)移动的距离超过给定阈值d; (2)移动前后相连的停留具有特定的活动目的。 在居民出行调查中,距离阈值d一般取400米或500米,本文中考虑到方法的扩展性, 比如研究人的行为特征,则采用更为精细的值,为200米。 定义7.行程端点( Trip End):行程两端的停留。因此,停留包括行程端点和无日的 停留。前者是受访者发生活动的时间和地点,只有目的性;后者是无活动目的的暂停,比如 交通堵塞、站台候车、熟人路上偶遇驻足交谈等,时间一般较短,两者之间多可以通过停留 时间进行区分。 定义8.活动场所( Activity Location):指行程端点所在的语义位置,比如“家”。活 动场所是一个空间概念,而行程端点是一个时空概念。因此,在一个活动场所可以有多个行 程端点,比如在受访者连续三天的出行轨迹中,“家”这个活动场所到访了三次,就有三个 活动端点。 2.,2GPS轨迹的多尺度分割算法(BUTS) GPS轨迹中因为噪声的存在,表现为移动中有静止,静止中有移动。很多情况卜移动 和静止被对方所割裂,无法衣现出应有的特征。因此,本文的多尺度分割思路为,先将整休 的轨迹分割为基本单元的轨迹段,通过速度阈值设置对轨迹段进行动静状态标记,然后采用 较小的时间阈值对相邻同态的轨迹段做连续性合并以形成较高级的状态段,最后根据状态段 的其他属性特征进行语义合),得到最终的停留识别结果(图2)。 山武花论文在丝 http://www.paper.edu.cn 速度 速度 静止部分 时间 平均速度、最大速度等 返动事分推证 汇总属性 小尺一人 速度、加速 度、方向等单 点厢性 图2GPS轨迹的多尺度分割概念图 a-从点基到段基的停留点探测以及不同尺度轨迹段综合;b-静止段与移动段的相互推证关系 Fig. 2 The conceptual diagram of multi-scale giPs trajectory segmentation a-conversion of point-based to segment-based stop detection and segment assembly at different b-supplementary reasoning of dwell segments and move segments for stop identiticalop calesi (1)基木轨迹段生成 在出行调查中,观察对象的运动状态(移动和静止)体现在相邻点连接形成的基本轨迹 段上,而不在离散的轨迹点本身。因此本文使用轨迹段为分析的基本单元 对于某移动对象轨迹,T={},将相邻的轨迹点链接成为轨迹段,则有 S=(P2,P+1),∈[,n (6) 其中n为轨迹点个数。每一个轨迹段如图1所示的两点之间的连线。 每个原始轨迹点衣示的是即时位置。转化为段之后,就可以给每个段赋予时长 ( duration)、距离( length)、平均速度( velocity)、方向( direction)等各项属性,使之 有更加明确的意义,可在后续处理中做进一步的合并。 (2)确定轨迹段状态 计算每条轨迹段s的平均速度S, S; length (7) s. duration 其中, 河engh=√万x-x)2+(y-1y) sduration= pil.time-P time 半均速度低于速度阈值vms的轨迹段s分为静止段,否则分为移动段: 0、s.< S, type (8) 1,s res 其中Ⅷ取步行速度的下限,0代表静止,1代表移动。 山武花论文在丝 http://www.paper.edu.cn 静止段 运动段 轨迹点轨迹段 状态段 小尺度合并后 大尺度合并后 图3轨迹逐级合并示意图 Fig 3. Multi-scale segmentation of a GPs trajectory (3)基于连续性的合并 轨迹分割后形成的每个轨迹段s;都被赋予移动状态(即移动或静止)。将相邻同向的同 状态轨迹段合并在一起便构成了状态段 S,={55∈7,pe=c} (9) c取值0或1。当c=0时,状态段S为静止段:当c=1时,状态段S为移动段。如图 3所示“状态段”中的虚线段和实线段。状态段的相应属性通过合并计算岷值。 连续性体现在静止段和移动段都应该持续一定的时长,低」阈值的应视作为另一状态的 噪声,转化为另状态: 0, when S, type=1nS,dur< durivesl type (10) l1, when S, type=onS,dur< dur (4)基」属性特征的停留段和移动段提取 经过连续性合并得到的状态段已具有了定语义。比如某段S的状态是静止,持续时 间30分钟,则该段实际上代表一个停留(即活动地点)。状态段的其他属性如:平均速度 方向、直线距离、路径距窝,绕路指数等各种统计特征,均可作为停留/移动区分的进一步 依据。另一方面,由于人类活动具有多尺度特征,对不同层次的活动和应用,界定停留和移 动的准则可以有所不同。多尺度分割算法的优势体现在这一阶段:通过不同时间或距离阈值 的设定,实现对不同尺度活动的探测与轨迹段合并。 23效率和精度评价 从计算效率上看,本算法只需对数据做若干单循环遍历,因此计算复杂度只有O(n)。 而对停留点精度的评价比较复杂。定义2给出的停留概念是一组连续冇向、在空间上相对聚 集的轨迹点,因具有一定空间覆盖范围,不适于停留点的精度评价。因此本文取停留子轨迹 的中位点为停留点代表,记为Pc,计算其相对真实停留点的位置误差。由于停留点是具 有持续时段的空间点,因此评价时不仅要求位置相近,而且要求时段相近,开始时刻和结束 时刻都要在一定阈值之内,即同时满足如下条件: distance(a, paeriwedi)<△d Prealstart time- Derived.start time< at resin (12) 6 山武花论文在丝 http://www.paper.edu.cn tine- derived. end- time<△ (13) 停留精度的评价指标采用了 Zhou et al2的查准率和查全率。设识别出的停留为D ( Dcrivcd stops),真实停留为R( Rcal stops),识别停留中包含真实停留的个数为RD(RnD) 则有 查准率-所有识别出来的停留(D)中真实停留(RD)所占的比例: PI-RD 100% (14) 查全率-是真实停留(R)中被识别出来的比例: P2- RD 100% R 3实验与结果 31数据来源 实证分析使用了本研究在上海市小范围居民出行GPS调查实验中收集的轨迹数据。实 验招募了11位受访者携带GPS数据收集模块记录一天出行,记录密度为每秒一个轨迹点, 样本共含352,837个轨迹点。调查获得的GPS轨迹经过简化处珥被叠加在 Google地图上, 供受访者通过提示回忆出行过程在轨迹上互动式标注停留。标注结果共得到160次真实停 留。图4为研究区域背景和出行轨迹分布情况。表1为经归一化整理后的受访者标注的真实 停留表一音。 图4上海市区小范围GPS出行调查实验数据分布 Fig 4 Distribution of GPS trajectories collected from a small-scale personal travel survey in Shanghai 表1受访者自我报告的真实停留存表格式 Tab. I Formatted records of rcal stops sclf-rcportcd by the gps survcy respondents 日期:20090821始发时间:1303 始发地点:天等路430卉 行程序号 交通方式 到达时间 到达地点 出行目的 步行 13:08 华轻购物商城 购物 步行 13:31 石头记 购物 步行 13:42 凌云路50路车站 换乘 公交 14:10 天钥桥路徐家汇站 购物 步行 15:47 市四中学前车站 换乘 公交 16:44 虹梅南路729车站 上学 7 山武花论文在丝 http://www.paper.edu.cn 32行程识别结果 行稈识別分为数据预处理和轨迹段分类两阶段进行。轨迹数据预处理步骤包括:通过数 据库査询剔除定位不准确(即卫星颗数少于3颗,PD○P>5)的轨迹点,把轨迹点逐点记录 柊式转化为邻点相连的轨迹段格式,并计算每段的时长、距离和平均速度(图5)。 PID 时刻 经度维度 StartIn Endl时长距离均速 120093-2215:524712140143531.226678 0.190.23 22009-3-2215:524812140143331226683 0.000.00 32009-3-2215524912140143031.226687 40290.07 , ,, 2009-3-2218:16:54121.3996931.227851 1.150.35 图5GPS数据预处理后获得的轨迹点至轨迹段转换和存表示例 Fig 5 Point-to-segment conversion: sample trajectory segments after GPS data preprocessing 在轨迹段分类阶段,先通过速度阈值设置对所有轨迹段做状态标记,即静止或移动。速 度阈值取步行速度的下限。人正常步行的速度在3-6km/h之间,下限约为0.8m/s。实际划分 中考虑到GPS定位随机性,通常取更低的速度下限(如Du与 Aultman -hall使用0.51m/s)。 本文在初步试验的基础上取与其相近的值,为0.6ms。随后使用时长标准对相邻轨迹段做连 续性合并,时长阈值通过优化选择(详见3.3),移动段的连续下限取10s,静止段的连续下限 取30s。图6的左表展示了连续性合并的结果,包括了重新计算的相关统计特征,并增加了 状态段的绕路指数(路径长度和行程端点间的直线距离之比),作为下阶段分类的基础。 在停留点识别阶段,首先通过真实活动和GPS轨迹对比观察,得出如下停留判别规则 (1)真实出行中连续移动的直线距离不小于200米; (2)真实出行中单个静止的持续时间不小于120秒; (3)真实出行中单个行程的绕路指数不大于5。 Start End移动轨段直线绕路 Start End移动轨段直线中位 中位 PDPD状态时长距离指数PDPD状态时长距离经度纬度 15842静49025.686 115374静790215612140143131226646 58425861动2611714→584215743动408117121401395312429 58615862静 12.6 586115825静20012612140158431230343 4279642822动27116114279642822动272116121.39931291 佟6经过合并形成的状态段存表小例(左),以及最终判别获得的轨迹停留标记和指钅(右)。 (时长=秒,距离=米,速度=米/秒,经纬度=段中位点丛标。) Fig. 6 Sample state segments after initial low-level coinbination (left)and stops and their pointers to the raw GPs trajectory data after the duration-based assembling process 停留判別的最后结果同样记录成表(图6右),其中未满足规则的状态段判定为相反状 态。最终从轨迹中识别出211个停留,而160个真实停留点中未被识别11个。根据式(14) 和(15)计算得出查准率和查全率分别为71%和93%与 Zhou et al.中的K中值和 DJ-Cluster算法的结果相对比(前者的查准率和查仝率分别为24%和28%,后者为71%和 83%),本文方法精度有较大改善,但査准水半仍不能令人满意。究其原因,可能是过高估 计了受访者自报活动时间的精度。通过对th的优化(详见3.3)可以确定对木案例的合适 阈值。图7(3)表明,查准率在trsh达在120秒之后呈上升趋势,直至180秒之后基本持平。 在180秒阈值点识别出190个停留点,木识别出的貞实停留点有16个,查准率和查全率分 别为76%和90%,较之120秒的结果更为合宜。另外通过个案分析,发现导致査准误差的 山武花论文在丝 http://www.paper.edu.cn 原因主要有如卜类型: (1)停留吋间低于设定阈值。如在小尺度活动情况下,受访者步行至单位大门传达室取 信,仅停留了67秒,低于180秒的阈值,故未能标记为停留。这是活动本身的性质 所决定,需要引入其他信息来处理。 (2)实际停留段屮的轨迹点漂移过大。较大的信号漂移因时间和距离均超过停留阈值 导致停留被误判为移动(行程)。这一问题与预处理中对数据漂移和缺尖未做处理 或处理失当有关。GPS数据漂移处理至今仍是业内技术难题,需要进一步研究 在180秒阈值识别出的虚假停留共计46个。造成虚假停留的原因除了之前所述的漂移 问题外,大部分是由于交通控制(红绿灯、交通堵塞等)和换乘。其中交通控制引起的有8 例,换乘问题引起的有19例。其他几例是由缺失处理不当、小行程未识别而导致停留不能 完全匹配、起点修正等原因造成的。 33阈值优化 本文算法需要设定数个阈值,包括(a)区分静止段与移动段的速度阙值;(b)初步合并 时移动段的持续时长;(c)初步合并时静止段的持续时长:(d)属性合并时静止段的时长 硏究分别对四项阈值的敏感度进行了测试,通过固定其他三项阚值而测试剩余项,即可获得 查准率和査仝率对受调阈值的敏感情况 E4% ∈的 ∈D C72% % 0304050.50.730911.11.21.3141.5 59131721 (a)区介静止段与多动段的诔度值(米/秒 b)初护合并时移动段的持续时长(秒) 89% 82% 61% 54% 40% 40% 5913172125293337414545357 391113151192102025027290 (c)初步合并时静止段的持续时长(秒) (d)属性合并时静止段的时长(秒) 图7阈值敏感性测试结果(黑色-杳羍率,灰色-査准率,磺丛标-相应阈值,纵丛标-精度百分比) Fig. 7. The results of threshold sensitivity tests(black-completeness, gray-correctness, x-axis-threshold y-axis-accuracy level) 敏感度测试结果见图7。阈值a和c调整时查准率和查全率同向变化,可以取得最优阈 值,分别为0.6米秒和27-35秒;阈值b几乎不敏感;而阈值d的査准率和査全率相对反向 变化,沿时长增加而趋于一致,故可根据精度要求在二者之间权衡 9 山武花论文在丝 http://www.paper.edu.cn 4结论 多层次轨迹分割算法可以较好的处理带有数据缺失和信号漂栘的GPS轨迹,不依赖于 事先定义的活动场所,可根据轨迹自身的时空特征产生只有一定语义信息的停留和移动(彳 程),准确率较之现有的其他方法有所改善。而且可以通过阈值的取值不同,解析出不同尺 度的活动。本文仅表述了研究的初步成果,目前还存在如卜问题: (1)对薮据缺失和信号漂移仅能达到‘定限度。过大的信号漂移仍难以处理。 (2)对阈值有较强的依颧性。本方法的合并过程需要定义时间和距离阈值,合并后识 别停留点时也需要定义时间阈值,阈值的设定目前还需要人为经验的参与 针对当前存在的问题,可以考虑从如下方面进行改进 (1)交可式的语义信息建立。停留点识别是一个逐步深入的过程,因此在算法设计上 应该具备逐步深化的能力。比如在初步停留之后,较长时间和较为确切的停留点可以自动设 定较大的阈值。 (2)减少阈值设定的武断性。通过阈值之间的联动关系,减少需要设置的阈值数据; 根据数据的内生关系,自动化或半自动化的设定阈值 此外,本研究受访人在自我报告中没有区分各自活动的空间尺度,也对分层分割的结果 验证造成·定困难。在某个阈值尺度上显著的活动,在另·尺度上可能受到抑制,反之亦然 这一问题在图7d中非常明显。设计不同层次活动的问卷调查比较复杂且投入更大,但也是 值得深入探索的问题之 参考文献]( References) [1] WIEHE S E, HOCH S C, LIU G C, et al. Adolescent travel patterns: pilot data indicating distance froin home varies by time of day and day of week[J]. Journal of Adolescent Health, 2008, 42: 418--420 [21 ELGETHUN K, FENSKERA, YOST M G, et al. Time-location analysis for exposure assessment studies of children using a novel global positioning system instrument[]. Environmental Ilealth Perspectives, 2003, 111 115~122 [3 SPACCAPIETRA S, PARENT C, DAMIANI M L, et al. A conceptual view on trajectories[]. Data Knowledge engineering. 2008, 65: 126-146 [4] STOPHER, P R Collecting and processing data from mobile technologies[A]. International Conference on Survcy Mcthods in Transport[C]. Annccy, France. 3lst May 2008 [5 HAGERSTRAND T. What about people in regional science? [ J] Regional Science, 1970. 24: 6-21 [6]GiOULIAS K, JANELLE D GiPS Tracking and Time-Gieography: Applications for Activity Modeling and Microsimulation[R]. Final report of FHWA-sponsored Peer Exchange and Csiss Specialist meeting, Santa barbara. USA.10-11 October 2005 [7] ALVARES LO, BOGORNY V, KUIJPERS B, et al. A model for enriching trajectories with semantic geographical information[A. Proceedings of the 15th annual ACM international sy mposium on Advances in geographic information systcms[C]. Scattlc, USA, 07-09 Novcmbcr, 200 8] ALEGRE B. ST-DMQL: A Semantic Trajectory Data Mining Query Language[J]. International Journal of Geographical Information Science, 2009, 23: 1245-1276 [9] SCHUESSLER N, AXHAUSEN K W. Processing Raw data from Global Positioning Systems without additional information[]. Journal of the Transportation Research Board, 2009, 2105: 28-36 DU J, AULTMAN-HALL L Increasing the accuracy of trip rate information from passive multi-day GPs travel datasets: Automatic trip end identification issues]. Transportation Research Part A, 2007, 41 220-232. [I1]STOPHER PR, JIANG Q, FITZGERALD C Processing gPs data from travel surveys [A]. 2nd International Colloquium on the behavioral Foundations of Integrated L and-use and Transportation Models: frameworks Models and Applications[C]. Toronto, Canada, 1 5th June 2005 12]WOLF J, GUENSLER R, BACHMAN W. Elimination of the travel diary: Experiment to derive trip purpose from global positioning system travel data[J] Journal of the Transportation Research board, 2001, 1768 [13MARMASSE N, SCHMANDT C. Location-awarc information dclivcry with commotion[A]. Procccdings of the 2nd international symposium on Handheld and Ubiquitous Computing[Cl, Bristol, UK, 25-27 September, 200,p.361~3 [14]SCHUESSLER N, AXHAUSEN K W. Processing Raw Data from Global Positioning Systems without Additional Information[J] Journal of the Transportation Research Board, 2009, 2105: 28-36 -10-

...展开详情
试读 11P 论文研究-GPS轨迹中活动停留点识别的多层分割算法 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-GPS轨迹中活动停留点识别的多层分割算法 .pdf 16积分/C币 立即下载
    1/11
    论文研究-GPS轨迹中活动停留点识别的多层分割算法 .pdf第1页
    论文研究-GPS轨迹中活动停留点识别的多层分割算法 .pdf第2页
    论文研究-GPS轨迹中活动停留点识别的多层分割算法 .pdf第3页
    论文研究-GPS轨迹中活动停留点识别的多层分割算法 .pdf第4页

    试读已结束,剩余7页未读...

    16积分/C币 立即下载 >