Modeling HMM Map Matching Using Multi-label Classification

Main Article Content

Atichart Sinsongsuk
Thapana Boonchoo
Wanida Putthividhya

บทคัดย่อ

Map matching deals with matching GPS coordinates to corresponding points or segments on a road network map. The work has various applications in both vehicle navigating and tracking domains. Traditional rule-based approach for solving the Map matching problem yielded great matching results. However, its performance depends on the underlying algorithm and Mathematical/Statistical models employed in the approach. For example, HMM Map Matching yielded O(N2) time complexity, where N is the number of states in the underlying Hidden Markov Model. Map matching techniques with large order of time complexity are impractical for providing services, especially within time-sensitive applications. This is due to their slow responsiveness and the critical amount of computing power required to obtain the results. This paper proposed a novel data-driven approach for projecting GPS trajectory onto a road network. We constructed a supervised-learning classifier using the Multi-Label Classification (MLC) technique and HMM Map Matching results. Analytically, our approach yields O(N) time complexity, suggesting that the approach has a better running performance when applied to the Map matching-based applications in which the response time is the major concern. In addition, our experimental results indicated that we could achieve Jaccard Similarity index of 0.30 and Overlap Coefficient of 0.70.

Article Details

บท
บทความวิจัย

References

P. Newson and J. Krumm, “Hidden markov map matching through noise and sparseness,” in Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems, pp. 336–343, 2009.

C. Yang and G. Gidofalvi, “Fast map matching, an algorithm integrating hidden markov model with precomputation,” International Journal of Geographical Information Science, pp. 1–24, 2017.

X. Fu, J. Zhang, and Y. Zhang, “An online map matching algorithm based on second-order hidden markov model,” Journal of Advanced Transportation, vol. 2021, p. 9993860, 2021.

C. I. U. of Madrid.Carlos III University of Madrid, “Precision of gps in cities improved by 90 percent,” ScienceDaily: Your source for the latest research news, 2013.

M. Hashemi and H. A. Karimi, “A machine learning approach to improve the accuracy of gps-based mapmatching algorithms (invited paper),” in 2016 IEEE 17th International Conference on Information Reuse and Integration (IRI), pp. 77–86, 2016.

M. Hashemi, “Reusability of the output of map-matching algorithms across space and time through machine learning,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 11, pp. 3017–3026, 2017.

D. Dua and C. Graff. (4 December 2021) UCI machine learning repository: Taxi service trajectory - prediction challenge, ecml pkdd 2015 data set, 2017. [Online]. Available: http://archive.ics.uci.edu/ml

J. Brownlee. (4 December 2021). One-vs-rest and one-vs-one for multi-class classification. [Online]. Available: https://machinelearningmastery.com/one-vsrest-and-one-vs-one-for-multi-class-classification/

F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, (4 Deccember 2021) Scikit-learn: Machine learning in Python,” Journal of Machine Learning Research, vol. 12, pp. 2825–2830, 2011. [Online]. Available: https://scikitlearn.org/stable/modules/generated/sklearn.svm.OneClassSVM.html

M. K. Vijaymeena and K. Kavitha, “A survey on similarity measures in text mining,” (PDF). Machine Learning and Applications. 3, vol. 3, 2016.

Neo4j, (4 December 2021) - The World’s Leading Graph Database, Std.,. [Online]. Available: http://neo4j.org/

Wikipedia. (16 December 2021). “Jaccard index — Wikipedia, the free encyclopedia,” Online]. Available: http://en.wikipedia.org/w/index.php?title=Jaccard%20index&oldid=1040991564

Wikipedia. (16 December 2021) “Overlap coefficient — Wikipedia, the free encyclopedia,” [Online].Available: http://en.wikipedia.org/w/index.php?title=Overlap%20coefficient&oldid=1022016130