Quantitative Performance Evaluation of Trajectory Data Cleansing

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：28

、訪客IP：3.21.100.34

姓名

蔡博汶(Po-Wen Tsai) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(Quantitative Performance Evaluation of Trajectory Data Cleansing)

相關論文

★ 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) 收集到的車輛軌跡資料，受到 GPS 的限制或較低的取樣率影響，常常不夠準確。因此，如何清理並校正收集到的軌跡資料是一個重要的問題。而相較於其他的軌跡清理的研究，基於 HMM 的軌跡清理方式似乎較有希望達到效果。在此研究中，我們提出了使用三種不同的量測值來評估基於 HMM 的軌跡清理效能，分別是：Hausdorff 距離，Fréchet 距離以及 Average Fréchet 距離。在我們的實驗中，使用基於 HMM 的軌跡清理，並利用前面提出的三個量測值來找出對於這個基於 HMM 的軌跡清理最好的參數設定。

摘要(英)

The vehicle trajectories are required in many vehicle safety applications, such as Left Turn Assist (LTA) and Front Collision Warning (FCW). Unfortunately, the vehicle trajectories collected by Global Positioning System are often inaccurate due to the limitation of GPS or low sampling rate. How to cleanse and calibrate the collected trajectory is therefore an important issue. The HMM based trajectory data cleansing seems to be promising among different research works of trajectory cleansing, but it does not provide adquate quantitative analysis to evaluate its performance. In this research, we propose to use three different distance measurements: Hausdorff distance, Fréchet distance, and Average Fréchet distance, to evaluate the performance of HMM based trajectory cleansing. In our HMM-based trajectory cleansing experiments, the three propose measurements are used to identify the best parameter settings for the HMM-based trajectory cleansing.

關鍵字(中)

★ HMM
★ trajectory data cleansing
★ Hausdorff distance
★ Fréchet distance

關鍵字(英)

★ HMM
★ trajectory data cleansing
★ Hausdorff distance
★ Fréchet distance

論文目次

1 Introduction 1
2 Related Work 4
2.1 The Ratio of Exactly Match . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Similarities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Preliminary 7
3.1 OpenStreetMap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
3.2 HMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
3.3 HMM on Trajectory Data Cleansing . . . . . . . . . . . . . . . . . . . . . 9
3.4 Hausdorff Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10
3.5 Fréchet Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12
3.6 Average Fréchet Distance . . . . . . . . . . . . . . . . . . . . . . . . .13
4 Design 14
4.1 Trajectory Data Cleansing . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1.1 Noise Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15
4.1.2 HMM Map Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . .17
4.1.3 A* Route Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 Measurement Implementation . . . . . . . . . . . . . . . . . . . . . . . .23
4.2.1 Hausdorff Distance Measuring . . . . . . . . . . . . . . . . . . . . . .25
4.2.2 Fréchet Distance Measuring . . . . . . . . . . . . . . . . . . . . . . .27
4.2.3 Average Fréchet Distance Measuring . . . . . . . . . . . . . . . . . . .29
5 Performance 30
5.1 Data Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.2 Studied Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . .30
5.3 Cleansing Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
6 Conclusion 38
Reference 39

參考文獻

[1] Muhammad Alam, Joaquim Ferreira, and Jose Fonseca. Introduction to Intelligent Transportation Systems, pages 1-17. Springer International Publishing, Cham, 2016.
[2] Essam Algizawy, Tetsuji Ogawa, and Ahmed El-Mahdy. Real-time large-scale map matching using mobile phone data. ACM Trans. Knowl. Discov. Data, 11(4):52:1-52:38, July 2017.
[3] Helmut Alt and Michael Godau. Computing the frechet distance between two polygonal curves. Int. J. Comput. Geometry Appl., 5:75-91, 1995.
[4] Heba Aly and Moustafa Youssef. semmatch: Road semantics-based accurate map matching for challenging positioning data. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL ′15, pages
5:1-5:10, New York, NY, USA, 2015. ACM.
[5] Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. In Proceedings of the 31st International Conference on Very Large Data Bases, pages 853{864. VLDB Endowment, 2005.
[6] OpenStreetMap contributors. Openstreetmap, 2016. [Online; accessed 16-March-2017].
[7] A. El-Rabbany. Introduction to GPS: The Global Positioning System. Artech House mobile communications series. Artech House, 2002.
[8] R. Elliott, L. Aggoun, and J. Moore. Hidden Markov models: estimation and control. Springer, 1995.
[9] M. Maurice Frechet. Sur quelques points du calcul fonctionnel. Rendiconti del Circolo Matematico di Palermo, 22(1):1-72, Dec 1906.
[10] F. Hausdor. Grundzuge der Mengenlehre. Leipzig Viet, 1914.
[11] Z. He, S. Xi-wei, L. Zhuang, and P. Nie. On-line map-matching framework for oating car data with low sampling rate in urban road networks. IET Intelligent Transport Systems, 7(4):404-414, December 2013.
[12] id, 2013. [Online; accessed 26-May-2019].
[13] Dirk Stocker Immanuel Scholz and other contributors. Josm, 2014. [Online; accessed 26-March-2019].
[14] Rahul Kala. 4 - advanced driver assistance systems. In Rahul Kala, editor, On-Road Intelligent Vehicles, pages 59-82. Butterworth-Heinemann, 2016.
[15] Sinn Kim and Jong-Hwan Kim. Adaptive fuzzy-network-based c-measure map-matching algorithm for car navigation system. IEEE Transactions on Industrial Electronics, 48(2):432-441, 2001.
[16] Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, and Yan Huang. Map-matching for low-sampling-rate gps trajectories. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS ′09, pages 352-361, New York, NY, USA, 2009. ACM.
[17] Maps.me, 2011. [Online; accessed 26-March-2019].
[18] Paul Newson and John Krumm. Hidden markov map matching through noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 336-343. ACM, 2009.
[19] Thomas Plotz and Gernot A. Fink. Markov models for oine handwriting recognition: A survey. Int. J. Doc. Anal. Recognit., 12(4):269-298, November 2009.
[20] L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257-286, Feb 1989.
[21] Peter J. Rousseeuw and Christophe Croux. Alternatives to the median absolute deviation. Journal of the American Statistical Association, pages 1273-1283, 1993.
[22] Helmut Schmid and Florian Laws. Estimation of conditional probabilities with decision trees and an application to ne-grained pos tagging. In Proceedings of the 22Nd International Conference on Computational Linguistics - Volume 1, COLING ′08, pages 777-784, Stroudsburg, PA, USA, 2008. Association for Computational Linguistics.
[23] F. Van Diggelen. Gnss accuracy: Lies, damn lies and statistics. GPS World, pages 26-32, 2007.
[24] Q. Wang, M. Sun, and K. Sakai. Trajectory data cleansing using hmm. In 2017 46th International Conference on Parallel Processing Workshops (ICPPW), pages 8-15, Aug 2017.
[25] Hong Wei, Yin Wang, George Forman, and Yanmin Zhu. Map matching: Comparison of approaches using sparse and noisy data. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL′13, pages 444-447, New York, NY, USA, 2013. ACM.
[26] Yifang Yin, Rajiv Ratn Shah, Guanfeng Wang, and Roger Zimmermann. Feature-based map matching for low-sampling-rate gps trajectories. ACM Trans. Spatial Algorithms Syst., 4(2):4:1-4:24, August 2018.
[27] 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.
[28] Ling Yuan, Dan Li, and Song Hu. A map-matching algorithm with low-frequency foating car data based on matching path. Eurasip Journal on Wireless Communications and Networking, 2018(1):146, 2018.
[29] 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.
[30] Yu Zheng. Trajectory data mining: An overview. ACM Trans. Intell. Syst. Technol., pages 29:1-29:41, 2015.

指導教授

孫敏德

審核日期

2019-8-7

推文