海量地铁乘客轨迹相似性连接方法:以深圳地铁为例.pdf
《海量地铁乘客轨迹相似性连接方法:以深圳地铁为例.pdf》由会员分享,可在线阅读,更多相关《海量地铁乘客轨迹相似性连接方法:以深圳地铁为例.pdf(10页珍藏版)》请在咨信网上搜索。
1、 海量地铁乘客轨迹相似性连接方法:以深圳地铁为例*王星苏1,熊 文1,张 瑞2(1.云南师范大学信息学院,云南 昆明 6 5 0 5 0 0;2.深圳北斗应用技术研究院有限公司,广东 深圳 5 1 8 0 0 0)摘 要:当前主要的轨迹相似性连接方法都以G P S轨迹为研究对象。针对G P S轨迹的优化方法无法直接用于解决地铁乘客轨迹相似性连接的问题,充分利用地铁乘客轨迹的时空特征,借助轨迹的重复性和对称性,将轨迹从点序列转化为O D序列。以O D序列为基础的轨迹,长度是原轨迹的一半,对应的索引空间变小,后续的计算量也随之减少。着重研究了基于P P J o i n+的轨迹连接算法在S p a
2、r k平台上的设计与实现。在一个1 3结点S p a r k集群和一个包含5 0 0万个乘客轨迹集合(5.6亿条刷卡记录)的超大规模数据集上验证了该算法的有效性。实验结果显示,基于O D序列的P P J o i n+算法的执行时间为1 4.0 m i n,比默认的点序列轨迹连接算法的节约了6 2.5%,比D i m a连接算法的节约了7 8.2%,并表现出了良好的可扩展性。关键词:轨迹相似性;地铁系统;P P J o i n+;S p a r k中图分类号:T P 3 9文献标志码:Ad o i:1 0.3 9 6 9/j.i s s n.1 0 0 7-1 3 0 X.2 0 2 3.0 8
3、.0 0 7A m a s s i v e s u b w a y p a s s e n g e r t r a j e c t o r y s i m i l a r i t y c o n n e c t i o n m e t h o d:A c a s e s t u d y o f S h e n z h e n m e t r o WANG X i n g-s u1,X I ONG W e n1,Z HANG R u i2(1.S c h o o l o f I n f o r m a t i o n S c i e n c e a n d T e c h n o l o g y
4、,Y u n n a n N o r m a l U n i v e r s i t y,K u n m i n g 6 5 0 5 0 0;2.S h e n z h e n I n s t i t u t e o f B e i d o u A p p l i e d T e c h n o l o g y,S h e n z h e n 5 1 8 0 0 0,C h i n a)A b s t r a c t:T h e c u r r e n t m a i n t r a j e c t o r y s i m i l a r i t y c o n n e c t i o n m
5、 e t h o d s a r e b a s e d o n G P S t r a j e c t o r i e s.O p t i m i z a t i o n m e t h o d s f o r G P S t r a j e c t o r i e s c a n n o t b e d i r e c t l y a p p l i e d t o t h e p r o b l e m o f c o n n e c t i n g s u b-w a y p a s s e n g e r t r a j e c t o r i e s.B y f u l l y u
6、 t i l i z i n g t h e s p a t i o t e m p o r a l c h a r a c t e r i s t i c s o f s u b w a y p a s s e n g e r t r a-j e c t o r i e s a n d l e v e r a g i n g t h e t r a j e c t o r y s r e p e t i t i v e n e s s a n d s y mm e t r y,t h e t r a j e c t o r y i s t r a n s f o r m e d f r o
7、m a p o i n t s e q u e n c e t o a n O D s e q u e n c e t o r e d u c e t h e t r a j e c t o r y l e n g t h a n d s a v e s t o r a g e s p a c e.T h i s p a p e r f o c u s e s o n t h e d e s i g n a n d i m p l e m e n t a t i o n o f t h e t r a j e c t o r y c o n n e c t i o n a l g o r i
8、t h m b a s e d o n P P J o i n+o n t h e S p a r k p l a t f o r m.T h e m e t h o d i s v a l i d a t e d o n a 1 3-n o d e S p a r k c l u s t e r a n d a l a r g e-s c a l e d a t a s e t c o n t a i n-i n g 5 m i l l i o n p a s s e n g e r t r a j e c t o r i e s(5 6 0 m i l l i o n t a p r e
9、c o r d s c o l l e c t e d i n t w o c o n s e c u t i v e m o n t h s).T h e e x p e r i m e n t a l r e s u l t s s h o w t h a t t h e P P J o i n+a l g o r i t h m b a s e d o n O D s e q u e n c e o n l y t a k e s 1 4.0 m i n u t e s,w h i c h s a v e s 6 2.5%o f t h e e x e c u t i o n t i m
10、 e c o m p a r e d t o t h e d e f a u l t p o i n t s e q u e n c e t r a j e c t o r y c o n n e c t i o n a l g o r i t h m a n d 7 8.2%o f t h e e x e c u t i o n t i m e c o m p a r e d t o t h e D i m a c o n n e c t i o n a l g o r i t h m,a n d e x h i b i t s g o o d s c a l a b i l i t y.K
11、 e y w o r d s:t r a j e c t o r y s i m i l a r i t y;m e t r o s y s t e m;P P J o i n+;S p a r k*收稿日期:2 0 2 2-0 6-0 9;修回日期:2 0 2 2-0 9-2 3基金项目:国家自然科学基金(6 1 8 6 2 0 6 6)通信作者:熊文(w e n.x i o n g h o t m a i l.c o m)通信地址:6 5 0 5 0 0 云南省昆明市云南师范大学信息学院A d d r e s s:S c h o o l o f I n f o r m a t i o n
12、S c i e n c e a n d T e c h n o l o g y,Y u n n a n N o r m a l U n i v e r s i t y,K u n m i n g 6 5 0 5 0 0,Y u n n a n,P.R.C h i n a C N 4 3-1 2 5 8/T PI S S N 1 0 0 7-1 3 0 X 计算机工程与科学C o m p u t e r E n g i n e e r i n g&S c i e n c e第4 5卷第8期2 0 2 3年8月 V o l.4 5,N o.8,A u g.2 0 2 3 文章编号:1 0 0 7-
13、1 3 0 X(2 0 2 3)0 8-1 3 8 3-1 01 引言轨道交通系统凭借高速、舒适、准时等特点,已经成为城市居民出行的主要方式。随着城市人口不断增加和路网规模不断扩大,轨道交通系统客流量不断增加。以深圳地铁2 0 1 8年9月的数据为例,自动售检票系统A F C(A u t o F a r e C o l l e c t i o n)检票口每天平均采集到5 0 0万人次的刷卡记录。每张智能卡的刷卡记录按时间排序就形成了乘客的历史轨迹。如何理解百万级别乘客的出行需求和时空特征是轨道交通精细化运营的前提,而海量轨迹相似性计算方法是乘客时空特征分析和挖掘的基础。现有研究围绕基于阈值、基
14、于t o p-k和基于距离 的 轨 迹 连 接T S-J o i n(T r a j e c t o r y S i m i l a r i t y J o i n)问题进行了大量的探索和实践。轨迹连接涉及2方面的问题,分别是轨迹相似性度量的选择和大规模轨迹相似性计算的优化。常用的轨迹相似性度量有动态时间规整距离(D y n a m i c T i m e W r a p p i n g)1、最 长 公 共 子 序 列(L o n g e s t C o mm o n S u b s e q u e n c e)2、实际编辑距离(E d i t D i s t a n c e o n R e
15、a l s e q u e n c e)3和真实惩罚编辑距离(E d i t D i s t a n c e w i t h R e a l P e n a l t y)4等。杰卡德相似性度量及其考虑时空属性扩展的方法5也可以用来衡量轨迹的相似性。大规模轨迹相似性连接的计算过程主要涉及2类优化措施。第1类是基于集合属性的优化技术,第2类是基于时空属性的优化技术。第1类方法主要有P P J o i n+(P o s i t i o n a l f i l t e r i n g w i t h t h e P r e f i x f i l t e r i n g-b a s e d J o i
16、 n)6、E d-J o i n(E d i t J o i n)7和A d a p t J o i n8等。这类方法的特点是采用倒排索引、长度过滤、前缀过滤等作为优化措施。第2类方法主要有D I T A(D i s t r i b u t e d I n-m e m o r y T r a j e c t o r y A n a l y t i c s)9、D I S ON(D i s t r i b u t e d I n-m e m o r y t r a j e c t o r y s i m i l a r i t y S e a r c h a n d j o i n O n r
17、o a d N e t w o r k)1 0和J U S T-J o i n1 1等。这类方法的特点是利用轨迹时空属性构建二级索引机制来进行优化。现有的T S-J o i n方法主要针对来自手机终端和地面车辆的G P S轨迹数据。这些针对G P S轨迹时空特征的优化措施,无法直接应用在轨道交通乘客轨迹的相似性连接问题中。以轨道交通乘客的刷卡记录形成的地铁轨迹为例,其与G P S轨迹相比有以下4个不同特征:(1)空间固定性。地铁乘客轨迹空间维度单元的站点是固定不变的,而G P S轨迹点的地理位置通常具有随机性。(2)高度稀疏性。刷卡轨迹记录的一次行程只有起点站和终点站2个“点”,而地面车辆一次
18、行程对应的轨迹包含很多密集的G P S时空点。(3)O D(O r i g i n t o D e s t i n a t i o n)拓扑特征。乘客的一次行程一定包含“进站”和“出站”2条刷卡记录。一组时间上连续的进 站-出 站 组 合 即 认 为 是 一 个 轨 迹 段O D。(4)对称重复性。地铁乘客的出行规律会导致轨迹出现一定的对称重复性。以某位通勤乘客1天的上下班行程为例,早上A站进B站出,傍晚B站进A站出,且1个月内有2 0次相同的行程。由于地铁乘客轨迹时空特征与G P S轨迹时空特征明显不同,上述针对G P S轨迹的相似性连接方法很难直接用于解决地铁乘客轨迹的相似性连接问题。所以
19、,本文尝试借助集合相似性连接方法来实现地铁乘客轨迹的相似性连接。这些方法的对比研究中,文献1 2 的实验结果表明,P P J o i n+在杰卡德距离上可以达到最好的实验效果,同时该算法也支持重叠相似度(O v e r l a p S i m i l a r i t y)、编辑距离(E d i t D i s t a n c e)和余弦相似度(C o s i n e S i m i-l a r i t y)等相似性度量方法。因此,本文使用P P J o i n+算法来解决地铁轨迹乘客的相似性连接问题。目前,还没有公开发表的文献讨论地铁乘客轨迹相似性连接的问题。本文充分探索地铁乘客轨迹的时空特征
20、,在S p a r k平台上实现了基于P P J o i n+的地铁乘客轨迹相似性连接算法。该算法的核心是借助地铁乘客轨迹的拓扑特征,将轨迹从点序列转换为O D序列,缩短了轨迹长度;然后,借助轨迹的集合属性,进行长度过滤、前缀过滤等剪枝方法缩小轨迹对的候选集;最后,与在S p a r k上实现的相似性查询处理系统D i m a1 3进行对比。具体来讲,本文的主要工作有如下3点:(1)提出了一种基于O D的地铁乘客轨迹相似性度量方法,基于地铁乘客轨迹的拓扑特征,将原始轨迹从点序列转化为O D序列,缩短了轨迹长度,进一步减少了后续计算过程中轨迹占用的存储空间和计算量。(2)在S p a r k平台
21、上实现了P P J o i n+算法来解决地铁乘客轨迹集合的相似性连接问题。借助轨迹的集合属性,利用倒排索引、长度过滤和前缀过滤等剪枝方法生成记录的自索引和相似索引,以加速地铁乘客轨迹的相似性连接。(3)在一个超大规模真实数据集和一个1 3结4831C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 3,4 5(8)点的S p a r k集群上验证了该方法。实验结果表明,对5 0 0万条轨迹进行相似性连接,执行时间只需要1 4 m i n,与默认算法的相比节约了6 2.5%,与D i-m a的相比平均节约了7 8
22、.2%。并且,本文提出的方法在大规模数据环境下表现出了良好的可扩展性。2 背景和动机2.1 轨道交通大数据平台随着城市居民数量不断增长和地铁路网的不断扩张,传统的信息化设施已经不能满足地铁精细化运营的需求。因此,运营管理者开始构建新一代信息化基础设施 轨道交通大数据平台,尝试系统地使用大数据、物联网和人工智能等相关技术,充分利用数据资源来提升地铁的运营水平。以深圳地铁集团轨道交通大数据平台为例,大数据平台分为4个部分。最底层为数据采集层,是由多个不同传感网络构成的数据采集传输系统,这些典型的数据有动态的A F C刷卡记录和传感器数据、静态的列车调度和排班到站信息。第2层为数据仓库层,是以多源异
23、构数据为基础构建的不同主题库。第3层为算法层,提供了一系列通用的大规模数据处理、数据挖掘算法,例如轨迹聚类算法。最上层为应用层,主要负责提供实时监控、地铁运营、车辆调度、应急管理、智慧警务和公共服务等功能。2.2 乘客群体移动时空特征轨道交通系统每天高速运转,为城市居民出行服务。深入理解数以百万计乘客的出行需求和时空特征是地铁路网规划、区间车调度、应急管理、智慧警务的基础。海量的历史和增量A F C刷卡记录既包含了个体移动的时空特征,也包含了城市居民群体移动的规律,隐藏着巨大的价值。例如,通过轨迹相似性分析可以了解城市居民职住地和日常通勤时空特征,以进一步指导地铁线网规划;在智慧警务领域,可以
24、根据轨迹相似性判断犯罪嫌疑人的团伙,为警察断案提供决策依据。因此,对海量乘客的轨迹进行深入细致的挖掘和分析显得尤为迫切。但是,百万级轨迹的相似性连接面临着算法和算力2方面的挑战。因为已有的轨迹相似性连接方法都以地面G P S轨迹为研究对象,一系列优化方法不能直接运用于地铁轨迹的相似性计算。传统的数据库技术和单结点的计算资源也无法满足实际计算需求。因此,本文借助S p a r k大数据计算引擎和经典的P P J o i n+算法来实现百万级轨迹的相似性连接。3 问题定义地铁乘客轨迹的相似性连接研究的目的是找出具有相似特征的轨迹集合,挖掘乘客的伴随状态。地铁刷卡记录的行程轨迹具有独特的时空特征。具
25、体来讲,一组时间上连续的进出站即可认为是一次行程,一次行程包含一个起点站和一个终点站。本文充分利用地铁轨迹独特的时空特征,在分布式计算引擎S p a r k上实现了百万级别乘客地铁轨迹相似性连接算法。整个过程包含一系列数据预处理和计算过程,例如对刷卡记录的分组排序、切割、合并;轨迹对过滤;相似性计算等。为了更精确地描述整个数据处理过程,首先给出以下4个定义:定义1(乘客轨迹点)乘客轨迹点是具有卡号i d、检票时间t i m e、检票站点s t a t i o n及检票类型t y p e 4个属性的时空点。定义乘客迹点P如式(1)所示:P=i d,t i m e,s t a t i o n,t
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 海量 地铁 乘客 轨迹 相似性 连接 方法 深圳
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。