臺灣博碩士論文加值系統

車輛的軌跡數據集通常受到GPS誤差跟低樣本比率影響。因此，在將其用於任何研究或應用之前，必須清理軌跡數據集。在本文中，我們提出了一個基於HMM的系統來清理軌跡數據集和重建車輛的缺失行駛路線。考慮到每筆資料的可能的道路是會改變的，並提出了一組轉移概率和觀察概率的公式。實驗使用OpenStreetMap的北京圖資和Microsoft Research Lab, Asia收集的計程車軌跡數據集，證實了我們提出的系統顯著提高了數據集的質量。

The vehicle trajectory dataset is often contaminated by GPS errors and low sampling rate. Consequently, it is important to cleanse the trajectory dataset before it can be used for any research or application. In this paper, we propose a HMM based system to cleanse and rebuild the missing traveling routes of vehicles in a given trajectory dataset. Considering the candidates of each entry as variables, a set of formulae for the transition probability and observation probability are proposed. The experiments using the OpenStreetMap of Beijing and the taxi trajectory dataset collected by Microsoft Research Lab, Asia confirm that our proposed system significantly improves the quality of the dataset.

Contents
1 Introduction 1
2 Related work 4
2.1 Map Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Best Route . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Preliminary 9
3.1 OpenStreetMap . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 The Hidden Markov Model . . . . . . . . . . . . . . . . . . . . 10
3.3 Optimal Route Search algorithm . . . . . . . . . . . . . . . . . 15
4 Cleansing and map matching 18
4.1 System Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 Noise Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3 HMM Map Matching . . . . . . . . . . . . . . . . . . . . . . . 20
5 Experiment 25
5.1 Experiment Conguration . . . . . . . . . . . . . . . . . . . . 25
5.2 Performance Metrics . . . . . . . . . . . . . . . . . . . . . . . 27
5.3 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . 28
6 Conclusion 32
Reference 33

[1] Ahmed El-Rabbany. Introduction to GPS: The Global Positioning Sys-
tem. 2002.
[2] OpenStreetMap contributors. Openstreetmap, 2016. [Online; accessed
16--2017].
[3] Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie,
Guangzhong Sun, and Yan Huang. T-drive: Driving directions based on
taxi trajectories. In Proceedings of the 18th SIGSPATIAL International
Conference on Advances in Geographic Information Systems, pages 99{
108. ACM, 2010.
[4] Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun. Driving with
knowledge from the physical world. In Proceedings of the 17th ACM
SIGKDD International Conference on Knowledge Discovery and Data
Mining, pages 316{324. ACM, 2011.
[5] Sinn Kim and Jong-Hwan Kim. Adaptive fuzzy-network-based cmeasure
map-matching algorithm for car navigation system. IEEE
Transactions on Industrial Electronics, 48(2):432{441, 2001.
[6] Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, and Yan
33
Huang. Map-matching for low-sampling-rate gps trajectories. In ACM
SIGSPATIAL GIS 2009. ACM SIGSPATIAL GIS 2009, November 2009.
[7] Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and CarolaWenk. On
map-matching vehicle tracking data. In Proceedings of the 31st Inter-
national Conference on Very Large Data Bases, pages 853{864. VLDB
Endowment, 2005.
[8] Helmut Alt, Alon Efrat, Gunter Rote, and Carola Wenk. Matching
planar maps. J. Algorithms, 49(2):262{283, 2003.
[9] John Krumm. A markov model for driver turn prediction. Society of
Automotive Engineers (SAE) 2008 World Congress, April 2008.
[10] P. Lamb and S. Thiebaux. Avoiding explicit map-matching in vehicle location.
In 6th World Conference on Intelligent Transportation Systems,
1999.
[11] B. Hummel. Map Matching for Vehicle Guidance. CRC Press: Florida,
2006.
[12] Siyuan Liu, Ce Liu, Qiong Luo, Lionel M. Ni, and Ramayya Krishnan.
Calibrating large scale vehicle trajectory data. In 2012 IEEE 13th Inter-
national Conference on Mobile Data Management, pages 222{231. IEEE
Computer Society, 2012.
34
[13] Yong Ge, Hui Xiong, Alexander Tuzhilin, Keli Xiao, Marco Gruteser,
and Michael Pazzani. An energy-ecient mobile recommender system.
In Proceedings of the 16th ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, pages 899{908. ACM, 2010.
[14] Haoran Hu, Zhiang Wu, Bo Mao, Yi Zhuang, Jie Cao, and Jingui Pan.
Pick-up tree based route recommendation from taxi trajectory, pages 471{
483. Springer Berlin Heidelberg, 2012.
[15] S. Qian, Y. Zhu, and M. Li. Smart recommendation by mining largescale
gps traces. In 2012 IEEE Wireless Communications and Network-
ing Conference (WCNC), pages 3267{3272. IEEE, 2012.
[16] Wikipedia. Plagiarism | Wikipedia, the free encyclopedia, 2004. [Online;
accessed 22-July-2004].
[17] R. Elliott, L. Aggoun, and J. Moore. Hidden Markov models: estimation
and control. Springer, 1995.
[18] Gernot A. Fink. Markov Models for Pattern Recognition: From Theory
to Applications. Springer-Verlag New York, Inc., 2007.
[19] W. Zeng and R. L. Church. Finding shortest paths on real road networks:
The case for a*. Int. J. Geogr. Inf. Sci., pages 531{543, 2009.
35
[20] Yu Zheng. Trajectory data mining: An overview. ACM Trans. Intell.
Syst. Technol., pages 29:1{29:41, 2015.
[21] F. Van Diggelen. GNSS Accuracy: Lies, Damn Lies and Statistics. GPS
World, pages 26{32, 2007.
[22] Peter J. Rousseeuw and Christophe Croux. Alternatives to the median
absolute deviation. Journal of the American Statistical Association,
pages 1273{1283, 1993.
[23] Paul Newson and John Krumm. Hidden markov map matching through
noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL In-
ternational Conference on Advances in