基于轨迹点聚类的航路发现方法

doi:10.11772/j.issn.1001-9081.2021030425

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (3): 890-894.DOI: 10.11772/j.issn.1001-9081.2021030425

• 数据科学与技术 • 上一篇

基于轨迹点聚类的航路发现方法

刘海杨, 孟令航, 林仲航, 谷源涛()

清华大学电子工程系，北京 100084

收稿日期:2021-03-22 修回日期:2021-07-05 接受日期:2021-07-05 发布日期:2022-04-09 出版日期:2022-03-10
通讯作者: 谷源涛
作者简介:刘海杨（1990—），男（满族），吉林和龙人，硕士研究生，主要研究方向：数据挖掘
孟令航（1995—），男，河北邢台人，博士研究生，主要研究方向：机器学习
林仲航（1998—），男，福建莆田人，硕士研究生，主要研究方向：数据挖掘；

Route discovery method based on trajectory point clustering

Haiyang LIU, Linghang MENG, Zhonghang LIN, Yuantao GU()

Department of Electronic Engineering，Tsinghua University，Beijing 100084，China

Received:2021-03-22 Revised:2021-07-05 Accepted:2021-07-05 Online:2022-04-09 Published:2022-03-10
Contact: Yuantao GU
About author:LIU Haiyang， born in 1990， M. S. candidate. His research interests include data mining.
MENG Linghang， born in 1995， Ph. D. candidate. His research interests include machine learning.
LIN Zhonghang， born in 1998， M. S. candidate. His research interests include data mining.

摘要/Abstract

摘要：

为了加强对局部空域航路的掌握和管理，提出一种基于轨迹点聚类的航路发现方法。首先，针对根据真实数据的分布特点生成的仿真数据，采用预处理模块对轨迹数据的噪声进行削弱和剔除；其次，提出一种包括孤立点剔除、轨迹重采样、轨迹点聚类、聚类中心修正和连接聚类中心五个部分的航路发现方法，对航路进行提取；最后，对航路提取结果进行了可视化输出，并使用民航数据对该方法进行了验证。在仿真数据上的实验结果表明，在噪声强度为0.1°、缓冲区为30 km的条件下，所提方法的节点覆盖率和长度覆盖率分别为99%和94%；与栅格化方法相比，该方法具有较高准确性，能够对航路进行更有效的提取，达到了提取飞行器常见航路的目的。

关键词: 航路发现, 轨迹点聚类, 机器学习, 轨迹预处理, 轨迹数据

Abstract:

To strengthen the control and management of local airspace routes， a route discovery method based on trajectory point clustering was proposed. Firstly， for the simulation data generated according to the distribution characteristics of the real data， the pre-processing module was used to weaken and remove the noise of the trajectory data. Secondly， a route discovery method including outlier elimination， trajectory resampling， trajectory point clustering， clustering center correction， and connecting clustering centers was proposed to extract the routes. Finally， the result of route extraction was visualized and the proposed method was validated using civil aviation data. The experimental results on the simulated data show that the node coverage and the length coverage of the proposed method is 99% and 94% respectively， under the noise intensity of 0.1° and the buffer area of 30 km. Compared with the rasterization method， the proposed method has higher accuracy and can extract the routes more effectively， achieving the purpose of extracting the common routes of aircraft.

Key words: route discovery, trajectory point clustering, machine learning, trajectory pre-processing, trajectory data

中图分类号:

TP391.4

刘海杨, 孟令航, 林仲航, 谷源涛. 基于轨迹点聚类的航路发现方法[J]. 计算机应用, 2022, 42(3): 890-894.

Haiyang LIU, Linghang MENG, Zhonghang LIN, Yuantao GU. Route discovery method based on trajectory point clustering[J]. Journal of Computer Applications, 2022, 42(3): 890-894.

图/表 9

图1 孤立点示意图

Fig.1 Schematic diagram of isolated point

图2 航路节点修正示意图

Fig. 2 Schematic diagram of route node amendment

图3 实验数据集

Fig. 3 Experimental data set

图4 轨迹预处理前后对比

Fig.4 Comparison of trajectories before and after preprocessing

图5 孤立点剔除效果

Fig. 5 Visualization of isolated point removal

图6 两种方法航路发现结果对比

Fig. 6 Comparison of results of two route discovery methods

图7 本文方法与栅格化方法的节点覆盖率对比

Fig. 7 Comparison of node coverage between two methods

图8 本文方法与栅格化方法的长度覆盖率对比

Fig. 8 Comparison of length coverage between two methods

图9 民航轨迹数据实验结果

Fig. 9 result of civil aviation data set

参考文献 16

1	EDELKAMP S， SCHRÖDL S. Route planning and map inference with global positioning traces［J］. Computer Science in Perspective， 2003，2598（1）： 128-151. 10.1007/3-540-36477-3_10
2	SCHROEDL S， WAGSTAFF K， ROGERS S， et al. Mining GPS traces for map refinement［J］. Data Mining and Knowledge Discovery， 2004，9：59-87. 10.1023/b:dami.0000026904.74892.89
3	WORRALL S， NEBOT E. Automated process for generating digitised maps through GPS data compression ［C］// Proceedings of the 2007 Australasian Conference on Robotics & Automation. New York： ACM， 2007：106-111. 10.1109/robot.2007.363837
4	米春蕾，彭玲，姚晓婧，等.基于浮动车轨迹数据的路网快速提取［J］.地理与地理信息科学，2019，35（1）：12-19. 10.3969/j.issn.1672-0504.2019.01.003
	MI C L， PENG L， YAO X J， et al. Rapid extraction of road network based on floating vehicle trajectory data［J］. Geography and Geo-information Science， 2019， 35（1）： 12-19. 10.3969/j.issn.1672-0504.2019.01.003
5	王冬，张焱，姜俊奎.基于浮动车轨迹数据的城市路网提取［J］.中国科技论文，2019，14（2）：226-231. 10.3969/j.issn.2095-2783.2019.02.019
	WANG D， ZHANG Y， JIANG J K. Urban road network extraction based on floating car data［J］. China Sciencepaper， 2019， 14（2）： 226-231. 10.3969/j.issn.2095-2783.2019.02.019
6	杨伟，艾廷华.基于众源轨迹数据的道路中心线提取［J］.地理与地理信息科学，2016，32（3）：1-7. 10.3969/j.issn.1672-0504.2016.03.001
	YANG W， AI T H. Road centerline extraction from crowdsourcing trajectory data［J］. Geography and Geo-information Science， 2016， 32（3）： 1-7. 10.3969/j.issn.1672-0504.2016.03.001
7	唐炉亮，刘章，杨雪，等.符合认知规律的时空轨迹融合与路网生成方法［J］.测绘学报，2015，44（11）：1271-1276. 10.11947/j.AGCS.2015.20140591
	TANG L L， LIU Z， YANG X， et al. A method of spatio-temporal trajectory fusion and road network generation based on cognitive law［J］. Acta Geodaetica et Cartographica Sinica， 2015， 44（11）： 1271-1276. 10.11947/j.AGCS.2015.20140591
8	SHI W H， SHEN S H， LIU Y C. Automatic generation of road network map from massive GPS vehicle trajectories［C］// Proceedings of the 2009 12th International IEEE Conference on Intelligent Transportation Systems. Piscataway： IEEE， 2009： 1-6. 10.1109/itsc.2009.5309871
9	李俊杰，刘鹏程，顿玉多吉.基于步行轨迹的复杂道路中心线提取方法［J］.华中师范大学学报（自然科学版），2020，54（1）：89-95. 10.19603/j.cnki.1000-1190.2020.01.015
	LI J J， LIU P C， DONYU D. Method to extract the center line of a complex road based on walking trajectory ［J］. Journal of Central China Normal University （Natural Sciences）， 2020， 54（1）： 89-95. 10.19603/j.cnki.1000-1190.2020.01.015
10	BIAGIONI J， ERIKSSON J. Map inference in the face of noise and disparity ［C］// Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York： ACM， 2012： 79-88. 10.1145/2424321.2424333
11	ZHANG T， SUEN C. A fast parallel algorithm for thinning digital patterns［J］. Communications of the ACM，1984， 27（3）： 236-239. 10.1145/357994.358023
12	ZHANG L J， THIEMANN F， SESTER M. Integration of GPS traces with road map ［C］// Proceedings of the 2nd International Workshop on Computational Transportation Science. New York： ACM， 2010：17-22. 10.1145/1899441.1899447
13	BRUNTRUP R， EDELKAMP S， JABBAR S， et al. Incremental map generation with GPS traces［C］// Proceedings of 2005 IEEE Intelligent Transportation Systems. Piscataway： IEEE， 2005： 574-579.
14	CAO L， KRUMM J. From GPS traces to a routable map ［C］// Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM， 2009：3-12. 10.1145/1653771.1653776
15	WINDEN K VAN， BILJECKI F， STEFAN V D S. Automatic update of road attributes by mining GPS tracks ［J］. Transactions in GIS， 2016，20（5）：664-683. 10.1111/tgis.12186
16	MARTIN E， HANS-PETER K， JÖRG S， et al. A density-based algorithm for discovering clusters in large spatial databases with noise［C］// Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Cham： Springer， 1996：226-231.

[1]	许仁杰, 刘宝弟, 张凯, 刘伟锋. 基于贝叶斯权函数的模型无关元学习算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 708-712.
[2]	陈露, 张晓霞, 于洪. 基于先验知识的非负矩阵半可解释三因子分解算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 671-675.
[3]	谢鑫, 张贤勇, 王旋晔, 唐鹏飞. 变精度邻域等价粒的邻域决策树构造算法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 382-388.
[4]	毛铭泽, 曹芮浩, 闫春钢. 基于权值多样性的半监督分类算法[J]. 计算机应用, 2021, 41(9): 2473-2480.
[5]	郭棉, 张锦友. 移动边缘计算环境中面向机器学习的计算迁移策略[J]. 计算机应用, 2021, 41(9): 2639-2645.
[6]	康军, 黄山, 段宗涛, 李宜修. 时空轨迹序列模式挖掘方法综述[J]. 《计算机应用》唯一官方网站, 2021, 41(8): 2379-2385.
[7]	秦斌斌, 彭良康, 卢向明, 钱江波. 司机分心驾驶检测研究进展[J]. 计算机应用, 2021, 41(8): 2330-2337.
[8]	秦静, 左长青, 汪祖民, 季长清, 王宝凤. 基于堆叠分类器的心电异常监测模型设计[J]. 计算机应用, 2021, 41(3): 887-890.
[9]	姜倩玉, 王凤英, 贾立鹏. 基于感知哈希算法和特征融合的恶意代码检测方法[J]. 计算机应用, 2021, 41(3): 780-785.
[10]	孟祥瑞, 杨文忠, 王婷. 基于图文融合的情感分析研究综述[J]. 《计算机应用》唯一官方网站, 2021, 41(2): 307-317.
[11]	王梅, 许传海, 刘勇. 基于神经正切核的多核学习方法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3462-3467.
[12]	成科扬, 孟春运, 王文杉, 师文喜, 詹永照. 解耦表征学习研究进展[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3409-3418.
[13]	邹复民, 罗思杰, 陈志辉, 廖律超. 基于轨迹数据的出租车交接班时空分布识别方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3376-3384.
[14]	刘晓龙, 王士同. 渐进式分离的开放集模糊域自适应算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3127-3131.
[15]	楼豪杰, 郑元林, 廖开阳, 雷浩, 李佳. 基于Siamese-YOLOv4的印刷品缺陷目标检测[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3206-3212.

基于轨迹点聚类的航路发现方法

Route discovery method based on trajectory point clustering

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 16

相关文章 15

编辑推荐

Metrics