Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2020, Vol. 47 Issue (1): 27-35    DOI: 10.3785/j.issn.1008-9497.2020.01.004
人工智能与可视计算     
基于排名学习和多源信息的地图匹配方法
卢家品1, 罗月童1, 黄兆嵩2, 张延孔1, 陈为2
1.合肥工业大学 计算机与信息学院, 安徽合肥 230601
2.浙江大学 计算机科学与技术学院, 浙江杭州 310058
An information fusion map matching method based on ranking learning
LU Jiapin1, LUO Yuetong1, HUANG Zhaosong2, ZHANG Yankong1, CHEN Wei2
1.School of Computer Science and Information Technology, Hefei University of Technology, Hefei 230601, China
2.College of Computer Science and Technology, Zhejiang University, Hangzhou 310058, China
 全文: PDF(1743 KB)   HTML  
摘要： 融合多源信息能有效提高地图匹配的准确率。已有的地图匹配方法依赖于数学模型,当引入新类型的数据时, 需要重新设计数学模型或调整模型参数。为解决该问题,提出了一种端到端的数据驱动地图匹配方法。该方法不需要建立具体的数学模型，只需从匹配结果已知的数据中学习候选道路的评分函数：选出某GPS点的候选道路，利用评分函数对所有候选道路进行打分，选择分数最高的道路作为地图匹配结果。实验结果表明,该方法能直接利用新类型的数据提高地图匹配的准确率，能在数据缺失时避免准确率急剧降低。此外，具有与基于HMM方法相近的准确率和与基于夹角特征和距离特征方法相当的速度。
关键词： 地图匹配;  轨迹数据预处理;  排名学习;  深度神经网络;  地理信息系统    
Abstract: Fusion of multi-source information can effectively improve the accuracy of map matching results. Existing map matching methods rely on mathematical models. When new types of data are introduced, it is necessary to design a new mathematical model or adjust the complex parameters of those model in order to obtain the best map matching results. To solve the problem, this paper proposes an end-to-end data-driven map matching method. Instead of establishing a specific mathematical model, our method uses a neural network to learn a scoring function of the candidate roads from the data with the matching results by the ranking learning method. During matching, the method first selects all the roads near the GPS point as candidate roads; then uses the scoring function to score and sort all the candidate roads; finally selects the road with highest score as the map matching result. The experimental results demonstrate that the proposed method can effectively use new types of data and adapt to data missing conditions so as to achieve improvement or avoid sharp drop in accuracy. On the other hand, with the accuracy close to the HMM-based method, and the run time close to the angle- and distances-feature-based method.
Key words: map matching    trajectory data preprocessing    ranking learning    deep neural networks    geographic information system
收稿日期: 2019-08-29 出版日期: 2020-01-25
CLC:  TP391.41  
基金资助: 国家自然科学基金资助项目 (61602146 );安徽省科技强警项目（1704d0802177）.
通讯作者: ORCID:http://orcid.org/0000-0002-4684-0350，E-mail:ytluo@hfut.edu.cn.   
作者简介: 卢家品(1994—),ORCID:http://orcid.org/0000-0001-5566-438X,男,硕士研究生,主要从事机器学习研究.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
卢家品
罗月童
黄兆嵩
张延孔
陈为

引用本文:

卢家品, 罗月童, 黄兆嵩, 张延孔, 陈为. 基于排名学习和多源信息的地图匹配方法[J]. 浙江大学学报（理学版）, 2020, 47(1): 27-35.

LU Jiapin, LUO Yuetong, HUANG Zhaosong, ZHANG Yankong, CHEN Wei. An information fusion map matching method based on ranking learning. Journal of Zhejiang University (Science Edition), 2020, 47(1): 27-35.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2020.01.004    或    https://www.zjujournals.com/sci/CN/Y2020/V47/I1/27

1 CHEN W , GUO F , WANG F Y . A Survey of Traffic Data Visualization[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(6):2970-2984. DOI:10.1109/TITS.2015.2436897
2 AN Q , FENG Z , CHEN S , et al . A Green self-adaptive approach for online map matching[J]. IEEE Access, 2018, 6: 51456-51469.DOI:10.1109/access.2018.2869852
3 PFOSER D , JENSEN C S . Capturing the uncertainty of moving-object representations[C]// Proc Int Symposium on Advances in Spatial Databases.Berlin:Springer, 1999. DOI:10.1007/3-540-48482-5_9
4 ZHENG Y . Trajectory data mining: an overview[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2015, 6(3): 29.DOI:10.1145/2743025
5 QUDDUS M A , OCHIENG W Y , NOLAND R B . Current map-matching algorithms for transport applications: State-of-the art and future research directions[J]. Trans-portation Research Part C Emerging Technologies, 2007, 15(5):312-328.DOI:10.1016/j.trc.2007.05.002
6 SCHULZE G , HORN C , KERN R . Map-matching cell phone trajectories of low spatial and temporal accuracy[C]// IEEE International Conference on Intelligent Transportation Systems. Las Palmas:IEEE, 2015. DOI:10.1109/ITSC.2015.435
7 RACKO J , BRIDA P , PERTTULA A , et al . Pedestrian dead reckoning with particle filter for handheld smartphone[C]// International Conference on Indoor Positioning & Indoor Navigation. Alcala de Henares: IEEE, 2016. DOI:10.1109/IPIN.2016.7743608
8 HÉBER S , COSTA C M , SOUSA I , et al . Map-matching algorithms for robot self-localization: a comparison between perfect match, iterative closest point and normal distributions transform[J]. Journal of Intelligent & Robotic Systems, 2018(2):1-14.DOI:10.1007/s10846-017-0765-5
9 WHITE C E , BERNSTEIN D , KORNHAUSER A L . Some map matching algorithms for personal navigation assistants[J]. Transportation Research Part C (Emerging Technologies), 2000, 8(1-6):91-108. DOI:10.1016/s0968-090x(00)00026-7
10 CHEN D , DRIEMEL A , GUIBAS L , et al . Approximate map matching with respect to the fréchet distance[C]// Work-shop on Algorithm Engineering & Experiments. San Francisco: Society for Industrial and Applied Mathematics, 2011. DOI:10.1137/1.9781611972917.8
11 SEYBOLD M P . Robust map matching for heterogeneous data via dominance decompositions[C]//Proceedings of the 2017 SIAM International Conference on Data Mining. Houston: Society for Industrial and Applied Mathematics, 2017: 813-821. DOI:10.1137/1.9781611974973.91
12 TAGUCHI S , KOIDE S , YOSHIMURA T . Online map matching with route prediction[J]. IEEE Transactions on Intelligent Transportation Systems, 2018:20(1):338-347.DOI:10.1109/TITS.2018.2812147
13 NEWSON P , KRUMM J . Hidden Markov map matching through noise and sparseness[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle:ACM, 2009: 336-343. DOI:10.1145/1653771.1653818
14 HU G , SHAO J , LIU F , et al . If-matching: Towards accurate map-matching with information fusion[J]. IEEE Transactions on Knowledge and Data Engineering, 2016,29(1):114-127. DOI:10.1109/TKDE.2016.2617326
15 GONG Y J , CHEN E , ZHANG X , et al . AntMapper: An ant colony-based map matching approach for trajectory-based applications[J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(2): 390-401.DOI:10.1109/TITS.2017.2697439
16 REN M , KARIMI H A . A fuzzy logic map matching for wheelchair navigation[J]. GPS Solutions, 2012, 16(3):273-282. DOI:10.1007/s10291-011-0229-5
17 JAGADEESH G R , SRIKANTHAN T . Online map-matching of noisy and sparse location data with hidden Markov and route choice models[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 18(9): 2423-2434.DOI:10.1109/TITS.2017.2647967
18 JAGADEESH G R , SRIKANTHAN T . Heuristic optimizations for high-speed low-latency online map matching with probabilistic sequence models[C]//2016 IEEE 19th International Conference on Intelligent Transportation Systems (ITSC). Rio de Janeiro: IEEE, 2016: 2565-2570. DOI：10.1109/ITSC.2016.7795968
19 TAGUCHI S , KOIDE S , YOSHIMURA T . Online map matching with route prediction[J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 20(1): 338-347.DOI:10.1109/TITS.2018.2812147
20 ZHENG K , ZHENG Y , XIE X , et al . Reducing uncertainty of low-sampling-rate trajectories[C]//2012 IEEE 28th International Conference on Data Engineering. Washington: IEEE, 2012: 1144-1155. DOI:10.1109/icde.2012.42
21 GOH C Y, DAUWELS J , MITROVIC N , et al . Online map-matching based on hidden markov model for real-time traffic sensing applications[C]//2012 15th International IEEE Conference on Intelligent Transportation Systems. Anchorage: IEEE, 2012: 776-781. DOI:10.1109/ITSC.2012.6338627
22 LECUN Y , BENGIO Y , HINTON G . Deep learning[J]. Nature, 2015, 521(7553):436.
23 LI P , WU Q , BURGES C J . Mcrank: Learning to rank using multiple classification and gradient boosting[C]//Advances in Neural Information Processing Systems. Vancouver:NIPS, 2008: 897-904. DOI:http://dx.doi.org/
24 BURGES C , SHAKED T , RENSHAW E , et al . Learning to rank using gradient descent[C]//Proceedings of the 22nd International Conference on Machine Learning (ICML-05). Bonn:IMLS,2005: 89-96. DOI:10.1145/1102351.1102363
25 CAO Z , QIN T , LIU T Y , et al . Learning to rank: From pairwise approach to listwise approach[C]//Proceedings of the 24th International Conference on Machine Learning. Corvallis:IMLS, 2007: 129-136. DOI:10.1145/1273496.1273513
26 CAKIR F , HE K , XIA X , et al . Deep metric learning to rank[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Long Beach:IEEE, 2019: 1861-1870.
27 ROBUSTO C C . The cosine-haversine formula[J]. The American Mathematical Monthly, 1957, 64(1): 38-40. DOI:10.2307/2309088
28 HE K , ZHANG X , REN S , et al . Deep residual learning for image recognition[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas:IEEE, 2016: 770-778. DOI:10.1109/CVPR.2016.90
29 ULYANOV D , VEDALDI A , LEMPITSKY V . Improved texture networks: Maximizing quality and diversity in feed-forward stylization and texture synthesis[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Honolulu:IEEE, 2017: 6924-6932. DOI:10.1109/CVPR.2017.437
30 GLOROT X , BORDES A , BENGIO Y . Deep sparse rectifier neural networks[C]// Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS). Fort Lauderdale: AISTATS,2011:315-323.
31 IOFFE S , SZEGEDY C .Batch normalization: accelerating deep network training by reducing internal covariate shift[C]//International Conference on International Conference on Machine Learning. Lille:IMLS,2015:448-456.
32 KUBIČKA M , CELA A , MOULIN P , et al . Dataset for testing and training of map-matching algorithms[C]//2015 IEEE Intelligent Vehicles Symposium (IV). Seoul:IEEE, 2015: 1088-1093. DOI:10.1109/IVS.2015.7225829
33 ZEILER M D . Adadelta: An adaptive learning rate Method[J]. CORR,2012,abs/ 1212.5701(1):1-6.
[1] 吴郁文, 林杰. 融合遥感与社会感知数据的城市土地利用分类方法[J]. 浙江大学学报（理学版）, 2023, 50(1): 83-95.