以运动方向为主导的轨迹相似性度量方法

doi:10.19678/j.issn.1000-3428.0053022

计算机工程 ›› 2019, Vol. 45 ›› Issue (11): 37-46. doi: 10.19678/j.issn.1000-3428.0053022

以运动方向为主导的轨迹相似性度量方法

王海起, 翟文龙, 闫滨, 费涛, 李学伟, 陈海波, 李建

中国石油大学(华东) 地球科学与技术学院, 山东青岛 266580

收稿日期:2018-10-30 修回日期:2018-12-27 发布日期:2019-11-12
作者简介:王海起(1972-),男,副教授,主研方向为地理信息系统、轨迹数据挖掘;翟文龙(通信作者)、闫滨、费涛、李学伟、陈海波、李建,硕士研究生。
基金资助:
国家自然科学基金（41471322）；山东省自然科学基金（ZR2012DM010）。

Motion Direction Dominated Trajectory Similarity Measurement Method

WANG Haiqi, ZHAI Wenlong, YAN Bin, FEI Tao, LI Xuewei, CHEN Haibo, LI Jian

School of Geosciences, China University of Petroleum(East China), Qingdao, Shandong 266580, China

Received:2018-10-30 Revised:2018-12-27 Published:2019-11-12

摘要/Abstract

摘要： 考虑到移动对象的行为趋势体现在行驶距离与前进方向上，提出以运动方向为主导并兼顾形态距离特征的轨迹相似性度量方法。形态距离特征采用包围面积进行度量，运动方向特征分别采用真实平均方向、线性平均方向、最长公共方向序列3种形式进行度量，选取形态距离和运动方向的最优组合作为轨迹相似性度量的最终形式。北京市出租车GPS载客轨迹数据上的聚类应用结果表明，该相似性度量方法能够有效区分移动对象的趋势方向，且聚类准确率优于最长公共子序列方法。

关键词: GPS轨迹, 方向角度, 包围面积, 最优组合, 相似性度量

Abstract: As the moving trend of an object is reflected by its driving distance and forward motion direction,this paper proposes a trajectory similarity measurement method based on motion direction.The features of motion direction are measured with actual average direction,linear average direction and longest common direction sequence.The method also considers the features of the shape and moving distance,which are measured with the area of regions bounded by trajectories.The optimal combination of the shape,moving distance and motion direction are taken as the final form of trajectory similarity measurement.The method is applied to GPS trajectory data clustering of occupied taxis in Beijing,and results show that the similarity measurement method can effectively distinguish moving trends and directions of objects with a higher clustering accuracy rate than the longest common subsequence method.

Key words: GPS trajectory, direction angle, bounded area, optimal combination, similarity measurement

中图分类号:

TP391.4

王海起, 翟文龙, 闫滨, 费涛, 李学伟, 陈海波, 李建. 以运动方向为主导的轨迹相似性度量方法[J]. 计算机工程, 2019, 45(11): 37-46.

WANG Haiqi, ZHAI Wenlong, YAN Bin, FEI Tao, LI Xuewei, CHEN Haibo, LI Jian. Motion Direction Dominated Trajectory Similarity Measurement Method[J]. Computer Engineering, 2019, 45(11): 37-46.

http://www.ecice06.com/CN/Y2019/V45/I11/37

图/表 24

20191118164259

20191118164301

20191118164304

20191118164307

20191118164309

20191118164312

20191118164315

20191118164317

20191118164323

20191118164326

20191118164329

20191118164333

20191118164336

20191118164339

20191118164341

20191118164345

20191118164349

20191118164352

20191118164356

20191118164359

20191118164403

20191118164406

20191118164410

20191118164413

参考文献

[1] 李正欣,张凤鸣,李克武,等.一种支持DTW距离的多元时间序列索引结构[J].软件学报,2014,25(3):560-575.
[2] SKOUMAS G,SKOUTAS D,VLACHAKI A.Efficient identification and approximation of k-nearest moving neighbors[C]//Proceedings of ACM Sigspatial International Conference on Advances in Geographic Information Systems.New York,USA:ACM Press,2013:264-273.
[3] 袁正午,袁松彪.流聚类模型及其统一表示[J].计算机工程,2009,35(16):76-77,80.
[4] 龚玺,裴韬,孙嘉,等.时空轨迹聚类方法研究进展[J].地理科学进展,2011,30(5):522-534.
[5] KEOGH E,PALPANAS T,ZORDAN V,et al.Indexing large human-motion databases[C]//Proceedings of the 13th International Conference on Very Large Data Bases.New York,USA:ACM Press,2004:780-791.
[6] ZHENG Yu,ZHOU Xiaofang.Computing with spatial trajectories[M].Berlin,Germany:Springer,2011.
[7] CHEN L,ÖZSU M,ORIA V.Robust and fast similarity search for moving object trajectories[C]//Proceedings of 2005 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2005:491-502.
[8] VLACHOS M,GUNOPULOS D,DAS G.Rotation invariant distance measures for trajectories[C]//Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2004:707-712.
[9] HERMES C,WOHLER C,SCHENK K,et al.Long-term vehicle motion prediction[C]//Proceedings of 2009 IEEE Intelligent Vehicles Symposium.Washington D.C.,USA:IEEE Press,2009:652-657.
[10] SAKURAI Y,YOSHIKAWA M,FALOUTSOS C.FTW:fast similarity search under the time warping distance[C]//Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.New York,USA:ACM Press,2005:326-337.
[11] KIM J,MAHMASSANI H S.Spatial and temporal characterization of travel patterns in a traffic network using vehicle trajectories[J].Transportation Research Part C:Emerging Technologies,2015,9:375-390.
[12] 曾万聃,周敏奇,刘云翔.轨迹大数据的比较算法研究[J].吉林大学学报(信息科学版),2016,34(6):792-799.
[13] AGRAWAL R,FALOUTSOS C,SWAMI A.Efficient similarity search in sequence databases[C]//Proceedings of International Conference on Foundations of Data Organization and Algorithms.Berlin,Germany:Springer,1993:69-84.
[14] LEE J G,HAN J,WHANG K Y.Trajectory clustering:a partition-and-group framework[C]//Proceedings of 2007 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2007:593-604.
[15] LIU Jinpeng,ZHANG Yanling,LIU Gang.Partition and density-based clustering for moving objects trajectories[C]//Proceedings of the 3rd International Conference on Computer Science and Education.Washington D.C.,USA:IEEE Press,2008:182-187.
[16] NANNI M,PEDRESCHI D.Time-focused clustering of trajectories of moving objects[J].Journal of Intelligent Information Systems,2006,27(3):267-289.
[17] LI Yifan,HAN Jiawei,YANG Jiong.Clustering moving objects[C]//Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2004:617-622.
[18] BEREZANSKY M,GREENSPAN H,COHEN-OR D,et al.Segmentation and tracking of human sperm cells using spatio-temporal representation and clustering[J].Proceedings of SPIE,2007,6512:1-12.
[19] GAO Yunjun,ZHENG Baihua,CHEN Gencai,et al.Algorithms for constrained K-nearest neighbor queries over moving object trajectories[J].Geoinformatica,2010,14(2):241-276.
[20] LIN Bin,SU Jianwen.One way distance:for shape based similarity search of moving object trajectories[J].Geoinformatica,2008,12(2):117-142.
[21] PERNG C S,WANG H,ZHANG S R,et al.Landmarks:a new model for similarity-based pattern querying in time series databases[C]//Proceedings of the 16th International Conference on Data Engineering.New York,USA:ACM Press,2000:33-42.
[22] Trajectory analysis datasets[EB/OL].[2018-09-18].http://cvrr.ucsd.edu/bmorris/datasets/dataset_trajectory_analysis.html.

选择文件类型/文献管理软件名称

选择包含的内容

以运动方向为主导的轨迹相似性度量方法

Motion Direction Dominated Trajectory Similarity Measurement Method

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 24

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	汤卫芬, 高翠芳. 极值点自适应加权的动态时间规整算法[J]. 计算机工程, 2023, 49(7): 150-160.
[2]	陆怡, 王鹏, 汪卫. 基于子序列相似性的时间序列语义挖掘算法[J]. 计算机工程, 2022, 48(10): 88-94.
[3]	刘苗苗, 周从华, 张婷. 基于分段特征及自适应加权的DTW相似性度量[J]. 计算机工程, 2021, 47(8): 62-68,77.
[4]	夏寒松, 张力生, 桑春艳. 基于LDTW的动态时间规整改进算法[J]. 计算机工程, 2021, 47(11): 108-120.
[5]	许光宇,林玉娥,石文兵. 基于局部结构张量的图像三边滤波器[J]. 计算机工程, 2017, 43(4): 269-276.
[6]	王刘涛,黄淼,王建玺,马飞. 交叉分辨率自适应字典学习的单帧超分辨率算法[J]. 计算机工程, 2016, 42(8): 206-210,219.
[7]	张娜,刘辉,尚振宏,邹滨益. 改进权重函数的非局部均值图像去噪算法[J]. 计算机工程, 2016, 42(12): 254-261.
[8]	孙雅,李志华. 基于区域极值点的时间序列聚类算法[J]. 计算机工程, 2015, 41(5): 33-37.
[9]	王小龙,沈新宁,杜建洪. 一种基于区域综合特征的图像检索算法[J]. 计算机工程, 2014, 40(11): 229-232,254.
[10]	李斌,孙怀江. 基于半监督距离学习的运动相似性度量算法[J]. 计算机工程, 2014, 40(11): 178-182.
[11]	周芳燕, 唐建, 何劲松. 基于分块的自适应多特征融合目标跟踪[J]. 计算机工程, 2013, 39(4): 239-242.
[12]	练仕榴, 郑刚, 牟善玲. 用于心电波形分析的相似性度量策略[J]. 计算机工程, 2011, 37(9): 263-265.
[13]	金标, 胡文龙. 基于边缘相似性的背景差鬼影判别方法[J]. 计算机工程, 2011, 37(11): 1-3.
[14]	黄旭, 吕强, 钱培德. 蛋白质结构预测聚类算法的评估[J]. 计算机工程, 2011, 37(01): 24-27.
[15]	毛红保;张凤鸣;冯卉;吕慧刚. 基于参数重要度的多元时间序列相似性查询[J]. 计算机工程, 2009, 35(24): 54-56.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

以运动方向为主导的轨迹相似性度量方法

Motion Direction Dominated Trajectory Similarity Measurement Method

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 24

参考文献

相关文章 15

编辑推荐

Metrics

本文评价