Trajectory Data Cleansing Using HMM

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：84

、訪客IP：3.135.184.255

姓名

王勤(Qin Wang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(Trajectory Data Cleansing Using HMM)

相關論文

★ Dynamic Overlay Construction for Mobile Target Detection in Wireless Sensor Networks	★ 車輛導航的簡易繞路策略
★ 使用傳送端電壓改善定位	★ 利用車輛分類建構車載網路上的虛擬骨幹
★ Why Topology-based Broadcast Algorithms Do Not Work Well in Heterogeneous Wireless Networks?	★ 針對移動性目標物的有效率無線感測網路
★ 適用於無線隨意網路中以關節點為基礎的分散式拓樸控制方法	★ A Review of Existing Web Frameworks
★ 將感測網路切割成貪婪區塊的分散式演算法	★ 無線網路上Range-free的距離測量
★ Inferring Floor Plan from Trajectories	★ An Indoor Collaborative Pedestrian Dead Reckoning System
★ Dynamic Content Adjustment In Mobile Ad Hoc Networks	★ 以影像為基礎的定位系統
★ 大範圍無線感測網路下分散式資料壓縮收集演算法	★ 車用WiFi網路中的碰撞分析

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

車輛的軌跡數據集通常受到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.

關鍵字(中)

★ Hidden Markov model
★ HMM
★ trajectory data cleansing

關鍵字(英)

★ Hidden Markov model
★ HMM
★ trajectory data cleansing

論文目次

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

指導教授

孫敏德(Min-Te Sun)

審核日期

2017-6-28

推文