A Method for Clustering Ship Trajectory through Extracting Multiple Feature Points
-
摘要: 轨迹聚类在船舶行为分析与海事监管等领域发挥着重要作用。船舶轨迹存在长度与采样率不一致、结构差异明显等特点，在大范围水域难以实现大量船舶轨迹的高精度与快速聚类。针对该问题，在利用船舶自动识别系统获取海量船舶历史航行数据的基础上，提取与船舶航行行为、船舶交通密度相关的位置特征点，进而提出了多特征点驱动的船舶轨迹聚类方法。针对船舶航行时在大多数情形下具有保向、保速的特点，采用数据压缩的方法捕获船舶航行状态以及船舶航向发生显著变化的轨迹点，作为船舶轨迹结构特征点；针对目标水域中某些特定区域常存在船舶交叉会遇的情形，利用概率密度估计法分析船舶交通流的空间分布特点，并提取船舶会遇局面下的轨迹点，作为船舶交通流特征点；为剔除2类特征点中的异常值，采用密度聚类算法对特征点进行聚类，进一步提高特征点提取的可靠性，并将聚类结果中每类特征点的中心作为代表性特征点；统计途经代表性特征点的船舶轨迹分布情况，将具有相似分布的船舶轨迹视为同一类。实验结果表明：相比于常用的K-medoids聚类、层次聚类、谱聚类和DBSCAN等方法，提出的轨迹聚类方法在成山头水域、长江口南槽水域及舟山水域等典型区域均可获得优异的聚类结果；在上述典型水域，平均轮廓系数分别提升约53%，71%，63%和41%，戴维森堡丁指数分别降低约57%，67%，63%和45%；同时，此方法可平均降低约56%的聚类时间，显著提升了船舶轨迹数据聚类分析的效率。Abstract: Trajectory clustering plays a significant role in the fields of ship behavior analysis and maritime regulation. Due to the inconsistent length and sampling rate of ship trajectories, as well as significant structural differences, it is difficult to achieve a high accuracy and efficient clustering for large numbers of ship trajectories in wide water areas. To address these problems, we propose to first take full advantage of the massive ship historical voyage data collected from the automatic identification system (AIS), and then extract the positional features related to the ship navigation behavior and traffic density. An efficient ship trajectory clustering method is finally presented by exploiting the multi-feature points. Moving ships, in general, have the characteristics of maintaining a similar direction and speed in most cases, the data compression method can thus be used to capture the trajectory points with significant changes in the navigation process and then extract them as the ship trajectory structure feature points. When ships come across encounters, a method for estimating the probability density is used to analyze the spatial distribution characteristics of ship traffic flow and extract their trajectory points as traffic flow feature points. To remove outliers in these two classes of feature points, a density clustering algorithm is employed to cluster the high-quality feature points, which further improves the reliability of feature points. The center of each class in the clusters is then used as the representative feature points. The distribution of ship trajectories passing through representative feature points is counted, considering ship trajectories with similar distribution as the same class. Numerous experiments have been carried out based on real-world AIS data, collected from the Chengshantou waters, the southern trough of the Yangtze River estuary, and the Zhoushan waters, to compare our proposed model with four typic clustering methods, i.e., the K-medoids clustering, the hierarchical clustering, the spectral clustering, and the density-based spatial clustering of applications with noise (DBSCAN). In the above-mentioned typical waters, the average silhouette coefficient is improved by approximately 53%, 71%, 63% and 41% and the Davies-Bouldin index is decreased by approximately 57%, 67%, 63% and 45%, respectively. At the same time, the method can reduce the clustering time by about 56% on average, which significantly improves the efficiency of ship trajectory clustering.
-
图 1 多特征点驱动的船舶轨迹聚类方法研究流程
Figure 1. Research process of ship trajectory clustering method through extracting multiple feature point
图 2 DP算法中距离阈值对轨迹保留点数的影响
Figure 2. The effect of distance thresholds on trajectory reserve points in DP compression algorithm
图 5 成山头水域船舶轨迹聚类结果
Figure 5. Clustering results of ship trajectories in Chengshantou waters
图 6 长江口南槽水域船舶轨迹聚类结果
Figure 6. Clustering results of ship trajectories in Yangtze River estuary
图 8 成山头水域船舶轨迹聚类结果评价
Figure 8. Evaluation of ship trajectories clustering results in Chengshantou waters
图 9 长江口南槽水域船舶轨迹聚类结果评价
Figure 9. Evaluation of ship trajectories clustering results in Yangtze River estuary waters
图 10 舟山水域船舶轨迹聚类结果评价
Figure 10. Evaluation of ship trajectories clustering results in Zhoushan waters
图 11 成山头水域船舶轨迹聚类结果对比
Figure 11. Comparison of vessel trajectory clustering results in Chengshantou waters
图 12 长江口南槽水域船舶轨迹聚类结果对比
Figure 12. Comparison of vessel trajectory clustering results in the southern trough of the Yangtze River estuary
图 13 舟山水域船舶轨迹聚类结果对比
Figure 13. Comparison of vessel trajectory clustering results in Zhoushan waters
表 1 船舶轨迹统计信息
Table 1. Statistics of ship trajectories
水域 时间范围 轨迹数/条 轨迹点数/个 经度范围/（°） 纬度范围/（°） 成山头 2018-01 1 630 1 973 914 121.5~123.1 37.1~37.7 长江口南槽 2017-08 2 836 3 335 937 121.3~121.9 31.1~31.5 舟山 2018-01 16 937 7 184 618 121.9~122.3 29.7~30.0 
下载: 导出CSV
表 2 不同置信度下的聚类评价结果
Table 2. Cluster evaluation results under different confidence levels
水域 置信度 SC DBI 成山头 0.95 0.783 0.247 0.99 0.336 1.734 长江口南槽 0.95 0.712 0.285 0.99 0.681 0.334 舟山 0.95 0.436 1.035 0.99 0.594 0.830
下载: 导出CSV
表 3 最优分类数下聚类评价结果
Table 3. Clustering evaluation results under optimal number of classifications
水域 评价指标 本文方法 K-medoids 层次聚类 谱聚类 DBSCAN 成山头 SC 0.856 0.581 0.546 0.548 0.846 DBI 0.214 0.499 0.556 0.461 0.216 长江口南槽 SC 0.745 0.435 0.614 0.337 0.543 DBI 0.322 1.247 0.683 1.308 0.849 舟山 SC 0.681 0.380 0.561 0.356 0.364 DBI 0.544 2.139 0.850 2.455 2.257
下载: 导出CSV
表 4 不同水域下各聚类算法运行时间
Table 4. Running time of each clustering algorithm in different waters
单位: s 水域 本文方法 K-medoids 层次聚类 谱聚类 DBSCAN 成山头 1 000 4 031 3 944 3 902 3 962 长江口南槽 5 410 10 112 10 033 10 442 10 165 舟山 11 600 22 790 21 039 21 467 21 065
下载: 导出CSV
-
[1] 马文耀, 吴兆麟, 李伟峰. 船舶异常行为的一致性检测算法[J]. 交通运输工程学报, 2017, 17(5): 149-158. doi: 10.3969/j.issn.1671-1637.2017.05.014MA W Y, WU Z L, LI W F. Conformal detection algorithm of anomalous behaviors of vessel[J]. Journal of Traffic and Transportation Engineering, 2017, 17(5): 149-158. (in Chinese) doi: 10.3969/j.issn.1671-1637.2017.05.014 [2] 计科峰, 赵和鹏, 邢相薇, 等. 小卫星载AIS海洋监视技术研究进展[J]. 雷达科学与技术, 2013, 11(1): 9-15. doi: 10.3969/j.issn.1672-2337.2013.01.002JI K F, ZHAO H P, XING X W, et al. Review and assessment of maritime surveillance based on small satellite-based AIS[J]. Radar Science and Technology, 2013, 11(1): 9-15. (in Chinese) doi: 10.3969/j.issn.1672-2337.2013.01.002 [3] 陈影玉, 杨神化, 索永峰. 船舶行为异常检测研究进展[J]. 交通信息与安全, 2020, 38(5): 1-11. doi: 10.3963/j.jssn.1674-4861.2020.05.001CHEN Y Y, YANG S H, SUO Y F. Research progress of ship behavior anomaly detection[J]. Journal of Transport Information and Safety, 2020, 38(5): 1-11. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2020.05.001 [4] MURRAY B, PERERA L P. Ship behavior prediction via trajectory extraction-based clustering for maritime situation awareness[J]. Journal of Ocean Engineering and Science, 2022, 7(1): 1-13. doi: 10.1016/j.joes.2021.03.001 [5] 王天真, 刘萍, 汤天浩, 等. 一种基于k-means聚类的航运信息孤立点分析算法[J]. 上海海事大学学报, 2011, 32(3): 54-57. doi: 10.3969/j.issn.1672-9498.2011.03.011WANG T Z, LIU P, TANG T H, et al. Outlier detection algorithm for maritime information based on k-means clustering[J]. Journal of Shanghai Maritime University, 2011, 32 (3): 54-57. (in Chinese) doi: 10.3969/j.issn.1672-9498.2011.03.011 [6] 陈德军, 刘冬, 郭南彬, 等. 基于层次聚类自动巡航的港区船舶碰撞危险识别方法研究[J]. 武汉理工大学学报(交通科学与工程版), 2017, 41(1): 12-16. doi: 10.3963/j.issn.2095-3844.2017.01.003CHEN D J, LIU D, GUO N B, et al. Research on ship collision risk identification in port area based on AGNES automatic patrol[J]. Journal of Wuhan University of Technology (Transportation Science & Engineering), 2017, 41(1): 12-16. (in Chinese) doi: 10.3963/j.issn.2095-3844.2017.01.003 [7] 周世波, 徐维祥. 密度峰值快速搜索与聚类算法及其在船舶位置数据分析中的应用[J]. 仪器仪表学报, 2018, 39(7): 152-163. https://www.cnki.com.cn/Article/CJFDTOTAL-YQXB201807019.htmZHOU S B, XU W X. Clustering by fast search and find of density peaks and its application in ship location data analysis[J]. Chinese Journal of Scientific Instrument, 2018, 39(7): 152-163. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YQXB201807019.htm [8] SHENG K, Liu Z, Zhou D C, et al. Research on ship classification based on trajectory features[J]. Journal of Navigation 1-17, 2018, 71(1): 100-116. doi: 10.1017/S0373463317000546 [9] 刘磊, 初秀民, 蒋仲廉, 等. 基于KNN的船舶轨迹分类算法[J]. 大连海事大学学报, 2018, 44(3): 15-21.LIU L, CHU X M, JIANG Z L, et al. Ship trajectory classification algorithm based on KNN[J]. Journal of Dalian Maritime University, 2018, 44(3): 15-21. (in Chinese) [10] 马文耀, 吴兆麟, 杨家轩, 等. 基于单向距离的谱聚类船舶运动模式辨识[J]. 重庆交通大学学报(自然科学版), 2015, 34(5): 130-134. https://www.cnki.com.cn/Article/CJFDTOTAL-CQJT201505026.htmMA W Y, WU Z L, YANG J X, et al. Vessel motion pattern recognition based on one-way distance spectral clustering algorithm[J]. Journal of Chongqing Jiaotong University(Natural Science), 2015, 34(5): 130-134. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-CQJT201505026.htm [11] LI H H, LIU J X, Liu W, et al. A dimensionality reduction-based multi-step clustering method for robust vessel trajectory analysis[J]. Sensors, 2017, 17(8): 1792. doi: 10.3390/s17081792 [12] ZHAO L B, SHI G Y. A novel similarity measure for clustering vessel trajectories based on dynamic time warping[J]. The Journal of Navigation, 2019, 72(2): 290-306. doi: 10.1017/S0373463318000723 [13] 牟军敏, 陈鹏飞, 贺益雄, 等. 船舶AIS轨迹快速自适应谱聚类算法[J]. 哈尔滨工程大学学报, 2018, 39(3): 438-433.MOU J M, CHEN P F, HE Y X, et al. Fast self-tuning spectral clustering algorithm for AIS ship trajectory[J]. Journal of Harbin Engineering University, 2018, 39(3): 438-433. (in Chinese) [14] 赵梁滨, 史国友, 杨家轩. 基于DBSCAN算法的船舶轨迹自适应层次聚类[J]. 中国航海, 2018, 41(3): 53-58. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH201803011.htmZHAO L B, SHI G Y, YANG J X. Adaptive hierarchical clustering of ship trajectory with DBSCAN algorithm[J]. Navigation of China, 2018, 41(3): 54-58. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH201803011.htm [15] SHENG P, YIN J B. Extracting shipping route patterns by trajectory clustering model based on automatic identification system data[J]. Sustainability, 2018, 10(7): 2327. [16] 彭祥文, 高曙, 初秀民, 等. 基于Spark的船舶航行轨迹聚类方法[J]. 中国航海, 2017, 40(3): 49-53+68. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH201703011.htmPENG X W, GAO S, CHU X M, et al. Clustering method of ship's navigation trajectory set based on Spark[J]. Navigation of China, 2017, 40(3): 49-53+68. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH201703011.htm [17] YAO D, ZHANG C, ZHU Z H, et al. Learning deep representation for trajectory clustering[J]. Expert Systems, 2018, 35(2): e12252. [18] 甄荣, 邵哲平, 潘家财. 基于AIS数据的船舶行为特征挖掘与预测: 研究进展与展望[J]. 地球信息科学学报, 2021, 23(12): 2111-2127. https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX202112002.htmZHEN 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. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX202112002.htm [19] 江玉玲, 熊振南, 唐基宏. 基于轨迹段DBSCAN的船舶轨迹聚类算法[J]. 中国航海, 2019, 42(3): 1-5. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH201903001.htmJIANG Y L, XIONG Z N, TANG J H. Ship trajectory clustering algorithm based on DBSCAN[J]. Navigation of China, 2019, 42(3): 1-5. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH201903001.htm [20] 郭昊. 基于AIS数据的轨迹段聚类方法研究[D]. 南京: 南京信息工程大学, 2021.GUO H. Research on clustering method of trajectory segment based on AIS data[D]. Nanjing: Nanjing University of Information Technology, 2021. (in Chinese) [21] 李雨潇, 吴传生, 刘文, 等. 仿射传播和谱聚类的船舶轨迹聚类[J]. 河南科技大学学报(自然科学版), 2018, 39(1): 35-40+6. https://www.cnki.com.cn/Article/CJFDTOTAL-LYGX201801007.htmLI Y X, WU C S, LIU W, et al. Trajectory clustering based on affine propagation and spectral clustering[J]. Journal of Henan University of Science and Technology(Natural Science), 2018, 39(1): 35-40+6. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-LYGX201801007.htm [22] ZHAO L B, SHI G Y. A trajectory clustering method based on Douglas-Peucker compression and density for marine traffic pattern recognition[J]. Ocean Engineering, 2019, 172: 456-467. [23] 王太正. 基于卷积自编码器的船舶AIS轨迹聚类[D]. 海口: 海南大学, 2020.WANG T Z. Ship AIS trajectory clustering based on convolutional autoencoder[D]. Haikou: Hainan University, 2020. (in Chinese) [24] ZHAO L B, SHI G Y, YANG J X. Ship trajectories pre-processing based on AIS data[J]. The Journal of Navigation, 2018, 71(5): 1210-1230. [25] 周世波, 熊振南. 基于局部密度的成山角船舶交通流特征分析[J]. 大连海事大学报, 2019, 45(3): 100-105.ZHOU S B, XIONG Z N. Characteristic analysis of ship traffic flow at Chengshanjiao based on local density[J]. Journal of Dalian Maritime University, 2019, 45(3): 100-105. (in Chinese) [26] 朱连江, 马炳先, 赵学泉. 基于轮廓系数的聚类有效性分析[J]. 计算机应用, 2010, 30(2): 139-141+198.ZHU L J, MA B X, ZHAO X Q. Clustering validity analysis based on silhouette coefficient[J]. Journal of Computer Applications, 2010, 30(2): 139-141+198. (in Chinese) [27] 朱秋圳, 邬群勇, 姚铖鑫, 孙豪宇. 基于DBI和稀疏轨迹数据的交通状态精细划分与识别[J]. 地球信息科学学报, 2022, 24(3): 458-468.ZHU Q Z, WU Q Y, YAO C X, SUN H Y. Fine classification and identification of traffic states based on DBI and sparse trajectory data[J]. Journal of Geo-information Science, 2022, 24(3): 458-468. (in Chinese) -
点击查看大图
计量
- 文章访问数: 1071
- HTML全文浏览量: 318
- PDF下载量: 66
- 被引次数: 0