Line-Segment based Trajectory Similarity Measure using Time Warping Technique

Authors

Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

Abstract

The most important issue with trajectory analysis is calculating similarity between trajectories. In this paper a novel method for measuring similarity between trajectories based on the cost to match a set of trajectories segments was introduced. The similarity between two trajectories is defined as a minimum cost to match a trajectory to the other one.  For this purpose, the segment based distance was introduced to as a cost of matching two trajectories segments. In addition, the dynamic programming technique is used to implement the time warp method. We performed some experiments to compare the proposed similarity measure with the similar approaches in the application of trajectory classification. The empirical quality of the proposed similarity measure was evaluated on 1-nearest neighbor (1-NN) classification task using 13 publicly available data sets. Compared to the other well-known similarity measures, the proposed method proved to be effective in the considered experiments based on the accuracy of classification.

Keywords

References

[1] J. D. Mazimpaka and S. Timpf, "Trajectory data mining: A review of methods and applications," Journal of Spatial Information Science, vol. 2016, no. 13, pp. 61-99, 2016.
[2] حسین خندانی, سید محمد مهدی دهقان و هادی مرادی, «الگوریتم واگذاری هدف متحرک زمینی میان دو پهپاد با قید بیشترین پوشش‌دهی منطقه‌ای», مجله مهندسی برق دانشگاه تبریز, دوره 47، شماره 3، صفحه 999-989، 1396.
[3] مصطفی یحیی‌آبادی و علیرضا صدوقی, «تعیین نواحی با بیش‌ترین احتمال برخورد صاعقه در ساختارهای پیچیده به‌منظور بهینه‌سازی سیستم حفاظت», مجله مهندسی برق دانشگاه تبریز, دوره 46، شماره 2، صفحه 377-369، 1395.
[4] K. Toohey and M. Duckham, "Trajectory similarity measures," SIGSPATIAL Special, vol. 7, no. 1, pp. 43-50, 2015.
[5] N. Magdy, M. A. Sakr, T. Mostafa, and K. El-Bahnasy, "Review on trajectory similarity measures," IEEE Seventh International Conference on Intelligent Computing and Information Systems (ICICIS), pp. 613-619, 2015.
[6] B. Morris and M. Trivedi, "Learning trajectory patterns by clustering: Experimental studies and comparative evaluation," IEEE Conference on Computer Vision and Pattern Recognition(CVPR), pp. 312-319, 2009.
[7] C. Kleist, Time Series Data Mining Methods: A Review, Humboldt-Universität zu Berlin, 2015.
[8] J. Lines and A. Bagnall, "Time series classification with ensembles of elastic distance measures," Data Mining and Knowledge Discovery, vol. 29, no. 3, pp. 565-592, 2015.
[9] U. Mori, A. Mendiburu, and J. A. Lozano, Distance Measures for Time Series in R: The TSdist Package, r-project,2015.
[10] C. Faloutsos, M. Ranganathan, and Y. Manolopoulos, "Fast subsequence matching in time-series databases," ACM, 1994.
[11] J. P. Wu and S. Wei, Time series analysis, Hunan Science and Technology Press,ChangSha, 1989.
[12] L. R. Rabiner and B. H. Juang, Fundamentals of speech recognition, 1993.
[13] D. J. Berndt and J. Clifford, "Using dynamic time warping to find patterns in time series," KDD workshop, vol. 10, no. 16, pp. 359-370, 1994.
[14] M. Vlachos, G. Kollios, and D. Gunopulos, "Discovering similar multidimensional trajectories," 18th International Conference on Data Engineering, pp. 673-684, 2002.
[15] L. Chen and R. Ng, "On the marriage of lp-norms and edit distance," Proceedings of the Thirtieth international conference on Very large data bases, pp. 792-803, 2004.
[16] L. Chen, M. T. Özsu, and V. Oria, "Robust and fast similarity search for moving object trajectories," Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 491-502, 2005.
[17] M. D. Morse and J. M. Patel, "An efficient and accurate method for evaluating time series similarity," Proceedings of the 2007 ACM SIGMOD international conference on Management of data,  pp. 569-580, 2007.
[18] P. F. Marteau, "Time warp edit distance with stiffness adjustment for time series matching," IEEE Trans Pattern Anal Mach Intell, vol. 31, no. 2, pp. 306-18, Feb 2009.
[19] A. Stefan, V. Athitsos, and G. Das, "The move-split-merge metric for time series," IEEE transactions on Knowledge and Data Engineering, vol. 25, no. 6, pp. 1425-1438, 2013.
[20] F. Hausdorff, Mengenlehre. Walter de Gruyter Berlin, 1927.
[21] J. Lou, Q. Liu, T. Tan, and W. Hu, "Semantic interpretation of object activities in a surveillance system," 16th International Conference on Pattern Recognition, 2002. Proceedings, vol. 3, pp. 777-780, 2002.
[22] H. Alt and M. Godau, "Computing the Fréchet distance between two polygonal curves," International Journal of Computational Geometry & Applications, vol. 5, no. 01n02, pp. 75-91, 1995.
[23] T. Eiter and H. Mannila, Computing discrete Fréchet distance, Citeseer, 1994.
[24] P. C. Besse, B. Guillouet, J.-M. Loubes, and F. Royer, "Review and Perspective for Distance-Based Clustering of Vehicle Trajectories," IEEE Transactions on Intelligent Transportation Systems, vol. 17, no. 11, pp. 3306-3317, 2016.
[25] H. Sakoe and S. Chiba, "Dynamic programming algorithm optimization for spoken word recognition," IEEE transactions on acoustics, speech, and signal processing, vol. 26, no. 1, pp. 43-49, 1978.
[26] T. Górecki and M. Łuczak, "Using derivatives in time series classification," Data Mining and Knowledge Discovery, pp. 1-22, 2013.
[27] G. E. Batista, E. J. Keogh, O. M. Tataw, and V. M. De Souza, "CID: an efficient complexity-invariant distance for time series," Data Mining and Knowledge Discovery, vol. 28, no. 3, pp. 634-669, 2014.
[28] J. Chen, M. K. Leung, and Y. Gao, "Noisy logo recognition using line segment Hausdorff distance," Pattern recognition, vol. 36, no. 4, pp. 943-955, 2003.
[29] J.-G. Lee, J. Han, and K.-Y. Whang, "Trajectory clustering: a partition-and-group framework," Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pp. 593-604, 2007.
[30] E. Keogh and S. Kasetty, "On the need for time series data mining benchmarks: a survey and empirical demonstration," Data Mining and knowledge discovery, vol. 7, no. 4, pp. 349-371, 2003.
[31] X. Wang, A. Mueen, H. Ding, G. Trajcevski, P. Scheuermann, and E. Keogh, "Experimental comparison of representation methods and distance measures for time series data," Data Mining and Knowledge Discovery, pp. 1-35, 2013.
[32] A. Bagnall and J. Lines, "An experimental evaluation of nearest neighbour time series classification," arXiv preprint arXiv:1406.4757, 2014.
[33] Z. Zhang, K. Huang, and T. Tan, "Comparison of similarity measures for trajectory clustering in outdoor surveillance scenes," 18th International Conference on Pattern Recognition, vol. 3, pp. 1135-1138, 2006.
[34] W. Kadous, GRASP: Recognition of Australian sign language using Instrumented gloves, 1995.
[35] W. Hu, X. Li, G. Tian, S. Maybank, and Z. Zhang, "An incremental DPMM-based method for trajectory clustering, modeling, and retrieval," IEEE Trans Pattern Anal Mach Intell, vol. 35, no. 5, pp. 1051-65, May 2013.
[36] C. Beyan and R. B. Fisher, "Detection of Abnormal Fish Trajectories Using a Clustering Based Hierarchical Classifier," BMVC, 2013.
[37] R. Ramos-Garijo, S. Martín, A. Marzal, F. Prat, J. M. Vilar, and D. Llorens, "An input panel and recognition engine for on-line handwritten text recognition," Frontiers in Artificial Intelligence and Applications, vol. 163, p. 223, 2007.
[38] R. Kohavi, "A study of cross-validation and bootstrap for accuracy estimation and model selection," Ijcai, vol. 14, no. 2, pp. 1137-1145, 1995.
[39] Y. S. Abu-Mostafa, M. Magdon-Ismail, and H.-T. Lin, Learning from data. AMLBook New York, NY, USA:, 2012.
[40] D. M. Powers, "Evaluation: from precision, recall and F-measure to ROC, informedness, markedness and correlation," 2011.

Files

Share

How to cite

Statistics