基于三维空间面积划分的轨迹相似性度量算法

doi:10.11772/j.issn.1001-9081.2023010077

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (1): 318-323.DOI: 10.11772/j.issn.1001-9081.2023010077

• 前沿与综合应用 • 上一篇

基于三维空间面积划分的轨迹相似性度量算法

徐凯¹, 高琦凯²(), 殷明¹, 谭京京³

^1.上海国际航运研究中心(上海海事大学), 上海 200082
^2.上海海事大学交通运输学院, 上海 201306
^3.上海汲致航运发展有限公司, 上海 200082

收稿日期:2023-01-31 修回日期:2023-05-11 接受日期:2023-05-12 发布日期:2023-06-06 出版日期:2024-01-10
通讯作者: 高琦凯
作者简介:徐凯（1983—），男，上海人，高级工程师，博士，CCF会员，主要研究方向：港航相关的大数据、互联网+、物联网、信息化、区块链；
殷明（1979—），男，上海人，教授，博士，主要研究方向：国际航运管理、港口管理、港航政策、航运实务与法规；
谭京京（1989—），男，重庆人，硕士，主要研究方向：港航大数据处理、机器学习。
第一联系人：高琦凯（1999—），男，山东临沂人，硕士研究生，主要研究方向：港航大数据、轨迹分析；
基金资助:
国家社会科学基金资助项目(20BJY177)

Trajectory similarity measurement algorithm based on three-dimensional space area division

Kai XU¹, Qikai GAO²(), Ming YIN¹, Jingjing TAN³

^1.Shanghai International Shipping Institute （Shanghai Maritime University），Shanghai 200082，China
^2.College of Transport and Communications，Shanghai Maritime University，Shanghai 201306，China
^3.Shanghai Jizhi Shipping Development Company Limited，Shanghai 200082，China

Received:2023-01-31 Revised:2023-05-11 Accepted:2023-05-12 Online:2023-06-06 Published:2024-01-10
Contact: Qikai GAO
About author:XU Kai， born in 1983， Ph. D.， senior engineer. His research interests include port-related big data， Internet+， internet of things， informationization， blockchain.
YIN Ming， born in 1979， Ph. D.， professor. His research interests include international shipping management， port management， port and shipping policies.
TAN Jingjing， born in 1989， M. S. His research interests include port and shipping big data processing， machine learning.
Supported by:
National Social Science Foundation of China(20BJY177)

摘要/Abstract

摘要：

针对大部分轨迹相似性度量算法无法区分方向相反轨迹的问题，提出了一种基于三维空间面积划分的三维三角分割（3TD）算法。首先，按照3TD算法的时间转换规则将轨迹集的绝对时间序列转变为相对时间序列；然后，在由经度、纬度以及时间三要素构成的三维空间坐标系中，通过划分规则将轨迹间面积分割成若干互不重叠的三角形，累加三角形面积并计算轨迹相似度；最后，在从船舶自动识别系统（AIS）收集的随机采样轨迹数据集上，与最长公共子序列（LCSS）算法和三角分割（TD）算法等进行了对比实验。实验结果表明：3TD算法对实验数据集中异向轨迹识别精确度达到100%；同时该算法面对海量数据集以及轨迹点部分缺失的数据集时，也能维持准确的度量结果以及较高的运算效率，能更好地适应异向轨迹相似度量工作。

关键词: 时空轨迹, 三维空间, 面积划分, 相似性度量, 轨迹方向

Abstract:

Aiming at the problem that most trajectory similarity measurement algorithms cannot distinguish the trajectories with opposite directions， a three-dimensional Triangulation Division （3TD） algorithm based on three-dimensional space area division was proposed. Firstly， the absolute time series of the trajectory set was transformed into the relative time series according to the time conversion rules of the 3TD algorithm. Then， in the three-dimensional space coordinate system composed of three elements of longitude， latitude， and time， the area between trajectories were divided into several non-overlapping triangles by partitioning rules， and the areas of the triangles were accumulated and the trajectory similarity was calculated. Finally， the proposed algorithm was compared with the Longest Common SubSequence （LCSS） algorithm and Triangle Division （TD） algorithm on the randomly sampled trajectory dataset collected from the ship Automatic Identification System （AIS）. Experimental results show that the accuracy of the 3TD algorithm reaches 100%. At the same time， the proposed algorithm can also maintain accurate measurement results and high operation efficiency on massive datasets and datasets with partial missing trajectory points， which can better adapt to the similarity measurement of divergent trajectories.

Key words: space-time trajectory, three-dimensional space, area division, similarity measurement, trajectory direction

中图分类号:

TP391

徐凯, 高琦凯, 殷明, 谭京京. 基于三维空间面积划分的轨迹相似性度量算法[J]. 计算机应用, 2024, 44(1): 318-323.

Kai XU, Qikai GAO, Ming YIN, Jingjing TAN. Trajectory similarity measurement algorithm based on three-dimensional space area division[J]. Journal of Computer Applications, 2024, 44(1): 318-323.

图/表 8

图1 TD算法度量轨迹间相似性

Fig. 1 TD algorithm to measure similarity between trajectories

图2 3TD算法度量轨迹间相似性

Fig. 2 3TD algorithm to measure similarity between trajectories

图3 港区对流轨迹

Fig. 3 Convective trajectories in port area

表1 港区对流轨迹相似度度量结果

Tab. 1 Results of similarity measurement of convective trajectories in port area

实验对象	不同轨迹相似性度量算法得到的相似度数值/%
实验对象	3TD算法	TD算法	LCSS算法
$P 1$ 与 $P 2$	95.61	95.77	95.87
$P 1$ 与 $P 3$	61.59	93.34	95.78

表1 港区对流轨迹相似度度量结果

Tab. 1 Results of similarity measurement of convective trajectories in port area

实验对象	不同轨迹相似性度量算法得到的相似度数值/%
实验对象	3TD算法	TD算法	LCSS算法
$P 1$ 与 $P 2$	95.61	95.77	95.87
$P 1$ 与 $P 3$	61.59	93.34	95.78

图4 轨迹点随机缺失的轨迹相似度变化

Fig. 4 Trajectory similarity changing with random missing trajectory points

表2 不同算法综合运行时间对比

Tab. 2 Comparison of comprehensive running time among different algorithms

实验类型	不同相似性算法运行时间/s
实验类型	3TD算法	TD算法	LCSS算法
鲁棒性检验	0.019 0	0.016 5	0.745 0
异向轨迹识别检验	0.020 0	0.019 0	0.753 0

图5 港区内复杂异向轨迹示意图

Fig. 5 Schematic diagram of complex divergent trajectories in port area

表3 复杂异向轨迹相似度度量结果

Tab. 3 Results of similarity measurement of complex divergent trajectories

实验对象	不同轨迹相似性度量算法得到的相似度数值/%
实验对象	3TD算法	TD算法	LCSS算法
$P 4$ 与 $P 7$	56.34	95.96	96.75
$P 5$ 与 $P 7$	75.65	97.16	97.77
$P 6$ 与 $P 7$	67.94	92.12	91.94

表3 复杂异向轨迹相似度度量结果

Tab. 3 Results of similarity measurement of complex divergent trajectories

实验对象	不同轨迹相似性度量算法得到的相似度数值/%
实验对象	3TD算法	TD算法	LCSS算法
$P 4$ 与 $P 7$	56.34	95.96	96.75
$P 5$ 与 $P 7$	75.65	97.16	97.77
$P 6$ 与 $P 7$	67.94	92.12	91.94

参考文献 20

1	章永来，周耀鉴.聚类算法综述［J］.计算机应用， 2019， 39（7）： 1869-1882. 10.11772/j.issn.1001-9081.2019010174
	ZHANG Y L， ZHOU Y J. Review of clustering algorithms ［J］. Journal of Computer Applications， 2019， 39（7）： 1869-1882. 10.11772/j.issn.1001-9081.2019010174
2	杨威，龙华，邵玉斌，等.基于切比雪夫距离的密度计算与K-means的聚类方法研究［J］.通信技术， 2019， 52（4）： 833-838. 10.3969/j.issn.1002-0802.2019.04.010
	YANG W， LONG H， SHAO Y B， et al. Chebyshev distance-based density calculation and K-means clustering algorithm ［J］. Communications Technology， 2019， 52（4）： 833-838. 10.3969/j.issn.1002-0802.2019.04.010
3	周星星，吉根林，张书亮.时空轨迹相似性度量方法综述［J］.地理信息世界， 2018， 25（4）： 11-18. 10.3969/j.issn.1672-1586.2018.04.003
	ZHOU X X， JI G L， ZHANG S L. Overview of the similarity measurement methods for spatial-temporal trajectory ［J］. Geomatics World， 2018， 25（4）： 11-18. 10.3969/j.issn.1672-1586.2018.04.003
4	ZHOU C， LIU G， HUANG L， et al. Spatiotemporal Companion Pattern （STCP） mining of ships based on trajectory features ［J］. Journal of Marine Science and Engineering， 2023， 11（3）： No.528. 10.3390/jmse11030528
5	WANG X， XIAO Y. A deep learning model for ship trajectory prediction using Automatic Identification System （AIS） data ［J］. Information， 2023， 14（4）： No.212. 10.3390/info14040212
6	甄荣，邵哲平，潘家财.基于AIS数据的船舶行为特征挖掘与预测：研究进展与展望［J］.地球信息科学学报， 2021， 23（12）： 2111-2127. 10.12082/dqxxkx.2021.210495
	ZHEN R， SHAO Z P， PAN J C. Advance in character mining and prediction of ship behavior based on AIS data ［J］. Journal of Geo-Information Science， 2021， 23（12）： 2111-2127. 10.12082/dqxxkx.2021.210495
7	BIFARETTI A， PAVAN E， GRIGIONI G. Consumer attitudes and concerns about beef consumption in Argentina and other south American countries ［J］. Agriculture， 2023， 13（3）： No.560. 10.3390/agriculture13030560
8	WANG J， LIU X， JIANG L. Algorithm for automatic parting of injection mold based on solid parting method ［J］. The International Journal of Advanced Manufacturing Technology， 2023， 124（7/8）： 2059-2077. 10.1007/s00170-022-10599-0
9	ZHANG Q， ZHANG C， CUI L， et al. A method for measuring similarity of time series based on series decomposition and dynamic time warping ［J］. Applied Intelligence， 2023， 53（6）： 6448-6463. 10.1007/s10489-022-03716-9
10	ZHAO L， SHI G. A novel similarity measure for clustering vessel trajectories based on dynamic time warping ［J］. The Journal of Navigation， 2019， 72（2）： 290-306. 10.1017/s0373463318000723
11	SÁNCHEZ-HERE L F. Simplification and event identification for ais trajectories： the equivalent passage plan method ［J］. The Journal of Navigation， 2019， 72（2）： 307-320. 10.1017/s037346331800067x
12	吕一可，徐凯，黄振强.基于面积划分的轨迹相似性度量方法［J］.计算机应用， 2020， 40（2）： 578-583.
	LYU Y K， XU K， HUANG Z Q. Trajectory similarity measurement method based on area division ［J］. Journal of Computer Applications， 2020， 40（2）： 578-583.
13	ZHEN R， JIN Y， HU Q， et al. Maritime anomaly detection within coastal waters based on vessel trajectory clustering and Naïve Bayes classifier ［J］. The Journal of Navigation， 2017， 70（3）： 648-670. 10.1017/s0373463316000850
14	SHEN H， TANG H， YIN Y. A novel method for ship trajectory clustering ［J］. International Journal of Naval Architecture and Ocean Engineering， 2022， 14： No.100474. 10.1016/j.ijnaoe.2022.100474
15	WEI Z， XIE X， ZHANG X. AIS trajectory simplification algorithm considering ship behaviours ［J］. Ocean Engineering， 2020， 216： No.108086. 10.1016/j.oceaneng.2020.108086
16	包磊.基于聚类距离计算的船舶轨迹异常检测方法［J］.舰船电子工程， 2020， 40（9）： 56-61. 10.3969/j.issn.1672-9730.2020.09.014
	BAO L. A trajectory data anomaly detection method based on trajectory cluster distance ［J］. Ship Electronic Engineering， 2020， 40（9）： 56-61. 10.3969/j.issn.1672-9730.2020.09.014
17	李爽，史国友，高邈，等.基于改进谱聚类算法的航路辨识［J］.上海海事大学学报， 2019， 40（4）： 1-6.
	LI S， SHI G Y， GAO M， et al. Route identification based on improved spectral clustering algorithm ［J］. Journal of Shanghai Maritime University， 2019， 40（4）： 1-6.
18	张春玮，马杰，牛元淼，等.基于行为特征相似度的船舶轨迹聚类方法［J］.武汉理工大学学报（交通科学与工程版）， 2019， 43（3）： 517-521. 10.3963/j.issn.2095-3844.2019.03.028
	ZHANG C W， MA J， NIU Y M， et al. Clustering method of ship trajectory based on similarity of behavior pattern ［J］. Journal of Wuhan University of Technology （Transportation Science and Engineering）， 2019， 43（3）： 517-521. 10.3963/j.issn.2095-3844.2019.03.028
19	LIAN M， LIU R W， LI S， et al. An unsupervised learning method with convolutional auto-encoder for vessel trajectory similarity computation ［J］. Ocean Engineering， 2021， 225： No.108803. 10.1016/j.oceaneng.2021.108803
20	张萍，李必军，郑玲，等.一种基于改进LCSS的相似轨迹提取方法［J］.武汉大学学报（信息科学版）， 2020， 45（4）： 550-556.
	ZHANG P， LI B J， ZHENG L， et al. A similar trajectory extraction method based on improved LCSS ［J］. Geomatics and Information Science of Wuhan University， 2020， 45（4）： 550-556.

[1]	邱莲鹏, 宋承云. 噪声鲁棒的动态时间规整算法[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1855-1860.
[2]	陈育丹, 高翠芳, 沈莞蔷, 殷萍. 迭代直觉模糊K-modes算法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 375-381.
[3]	康军, 黄山, 段宗涛, 李宜修. 时空轨迹序列模式挖掘方法综述[J]. 《计算机应用》唯一官方网站, 2021, 41(8): 2379-2385.
[4]	杨蒙蒙, 张爱华. 基于灰度共生矩阵和同步正交匹配追踪的分形图像压缩[J]. 计算机应用, 2021, 41(5): 1445-1449.
[5]	胡立华, 左威健, 聂瑶瑶. 基于加权相似性度量的特征匹配方法[J]. 计算机应用, 2021, 41(2): 511-516.
[6]	周玉彬, 肖红, 王涛, 姜文超, 熊梦, 贺忠堂. 基于动作周期退化相似性度量的机械轴健康指标构建与剩余寿命预测[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3192-3199.
[7]	吕一可, 徐凯, 黄振强. 基于面积划分的轨迹相似性度量方法[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 578-583.
[8]	马伟苹, 李文新, 孙晋川, 曹鹏霞. 基于粗精立体匹配的双目视觉目标定位方法[J]. 计算机应用, 2020, 40(1): 227-232.
[9]	姚陆吉, 章立. 基于混合现实技术的中国建筑史教学系统设计与实现[J]. 计算机应用, 2019, 39(9): 2689-2694.
[10]	章永来, 周耀鉴. 聚类算法综述[J]. 计算机应用, 2019, 39(7): 1869-1882.
[11]	姜逸凡, 叶青. 基于孪生神经网络的时间序列相似性度量[J]. 计算机应用, 2019, 39(4): 1041-1045.
[12]	段宗涛, 龚学辉, 唐蕾, 陈柘. 共享交通的时空轨迹检索与群体发现[J]. 计算机应用, 2019, 39(1): 220-226.
[13]	常炳国, 臧虹颖. 基于分段降维和路径修正DTW的时序特征分类器设计[J]. 计算机应用, 2018, 38(7): 1910-1915.
[14]	鲍舒婷, 孙丽萍, 郑孝遥, 郭良敏. 基于共享近邻相似度的密度峰聚类算法[J]. 计算机应用, 2018, 38(6): 1601-1607.
[15]	徐苏, 周颖玥. 基于图像分割的非局部均值去噪算法[J]. 计算机应用, 2017, 37(7): 2078-2083.

基于三维空间面积划分的轨迹相似性度量算法

Trajectory similarity measurement algorithm based on three-dimensional space area division

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 20

相关文章 15

编辑推荐

Metrics