ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2018, Vol. 55 ›› Issue (5): 908-919.doi: 10.7544/issn1000-1239.2018.20170226

• 人工智能 • 上一篇    下一篇



  1. 1(北京科技大学计算机科学与技术系 北京 100083); 2(中国科学院电子学研究所 北京 100190) (
  • 出版日期: 2018-05-01
  • 基金资助: 

The Algorithm of Ship Rule Path Extraction Based on the Grid Heat Value

Li Jianjiang1, Chen Wei1, Li Ming2, Zhang Kai1,Liu Yajun1   

  1. 1(Department of Computer Science and Technology, University of Science and Technology Beijing, Beijing 100083); 2(Institute of Electrics, Chinese Academy of Sciences, Beijing 100190)
  • Online: 2018-05-01

摘要: 随着无线传感器、卫星、GPS(global positioning system)等移动目标定位技术的发展,产生的移动数据(诸如人类足迹、车辆行驶轨迹和船舶轨迹等)的规模越来越大.而移动目标检测设备只会存储一系列离散点的信息,所以基于离散点来追踪和恢复其完整的轨迹是更加全面掌握移动目标运动规律的必要前提.数据挖掘方法能从移动目标的历史位置信息中挖掘出“规律”路径,其中基于网格的聚类分析方法不仅能有效表达这些轨迹点,还能分析出这些轨迹点之间的关系,是提取规律路径的有效方法.为此,提出了基于网格“热度值”的距离和密度相结合的热度因子相似性度量方法,进而给出了移动目标规律路径提取算法.最后,使用船舶自动识别系统(automatic identification system, AIS)生成的船舶实际动态数据进行测试,来验证该算法的精度和性能.算法分析和实验结果表明:基于网格热度值的规律路径提取算法能有效地发现不同形状的轨迹序列.

关键词: 网格热度值, 路径提取, 数据挖掘, 轨迹聚类, 密度聚类

Abstract: With the development of moving target location technology like GPS, wireless sensor and satellite, a large amount of mobile data such as human walking trajectory, vehicle trajectory, ship trajectory and so on is generated. However, moving target detection device can only store information of a series of discrete points. Therefore, using the aid of discrete points to track and recover the full path is the necessary prerequisite to grasp the rule of moving target. Using the method of date mining can find the regular path from the historical information of moving target, while the clustering method based on the grid can not only effectively express these trajectories, but also analyze the relationship among these points, and it is an effective method for extraction of path. At present, the research of trajectory clustering is mostly from the perspective of space or time,by means of density clustering method to find out hot paths. These paths are often the discrete path fragments, which are not able to effectively express the continuous path of moving target with different shapes. In this paper, the method of heat factor similarity measurement based on the combination of distance and density of grid heat value is proposed. Finally, the actual automatic identification system (AIS) dynamic data is used to verify the accuracy and performance of the algorithm. The algorithm analysis and experimental results show that the regular path extraction algorithm based on grid heat value proposed in this paper can effectively find out different trajectory sequences of different shapes.

Key words: grid heat value, path extraction, data mining, trajectory clustering, density-based clustering