应用Hausdorff距离的时空轨迹相似性度量方法
|
摘要
相似性度量方法的选取和稳健性对时空轨迹聚类结果的有效性是至关重要的.针对时空轨迹数据复杂的多重维度信息,选取空间维和时间维2个维度度量时空轨迹的相似性,提出一种应用Hausdorff距离的时空轨迹相似性度量方法.首先从时空轨迹的3个特性出发,提出面向相似性度量的时空轨迹重组策略;然后将传统的以点为中心进行相似性度量的思路转换为以轨迹段为中心,提出一个考虑时间同步性的时空轨迹段距离度量公式;最后鉴于传统的Hausdorff距离进行时空轨迹相似性度量具有时空轨迹整体形状特征的优点,针对其容易受时空轨迹局部空间分布影响和忽略时间维信息的缺陷,提出一种基于单位时间平均值Hausdorff距离的时空轨迹相似性度量方法.采用微博签到轨迹数据和出租车GPS轨迹数据进行轨迹时空聚类实验,将文中提出的时空轨迹相似性度量方法与已有的其他方法进行比较,实验结果表明,该方法可以有效地计算时空轨迹的相似性,满足时空轨迹聚类的需求.
The selection and robustness of similarity measure method is very important to the validity of the clustering results of spatial-temporal trajectory. In this paper, we propose a method for measuring the similarity of spatio-temporal trajectory using Hausdorff distance. Based on the multidimensional information of spatio-temporal trajectory data, this method selects spatial dimension and time dimension to measure the similarity of spatio-temporal trajectory. Firstly, based on the three characteristics of spatio-temporal trajectory, the spatio-temporal trajectory reconstruction strategy for similarity measurement is presented. Then, we transform the similarity measurement unit from point to trajectory segment, and propose a temporal synchronization distance measurement formula. Finally, considering the advantage of Hausdorff distance used on similarity measurement that takes into account the overall shape of spatio-temporal trajectory and the disadvantage that it is easy to be affected by the spatial distribution of spatio-temporal locus, we propose a measurement method of spatio-temporal trajectory similarity based on the average Hausdorff distance per unit time. The temporal and spatial clustering experiments were carried out using the microblog check-in trajectory data and taxi GPS trajectory data, and the spatio-temporal trajectory similarity measurement method proposed in this paper was compared with other existing methods. The experimental results show that this method can effectively calculate the similarity of space and time trajectories and meet the application needs of spatio-temporal trajectory clustering analysis.
The selection and robustness of similarity measure method is very important to the validity of the clustering results of spatial-temporal trajectory. In this paper, we propose a method for measuring the similarity of spatio-temporal trajectory using Hausdorff distance. Based on the multidimensional information of spatio-temporal trajectory data, this method selects spatial dimension and time dimension to measure the similarity of spatio-temporal trajectory. Firstly, based on the three characteristics of spatio-temporal trajectory, the spatio-temporal trajectory reconstruction strategy for similarity measurement is presented. Then, we transform the similarity measurement unit from point to trajectory segment, and propose a temporal synchronization distance measurement formula. Finally, considering the advantage of Hausdorff distance used on similarity measurement that takes into account the overall shape of spatio-temporal trajectory and the disadvantage that it is easy to be affected by the spatial distribution of spatio-temporal locus, we propose a measurement method of spatio-temporal trajectory similarity based on the average Hausdorff distance per unit time. The temporal and spatial clustering experiments were carried out using the microblog check-in trajectory data and taxi GPS trajectory data, and the spatio-temporal trajectory similarity measurement method proposed in this paper was compared with other existing methods. The experimental results show that this method can effectively calculate the similarity of space and time trajectories and meet the application needs of spatio-temporal trajectory clustering analysis.
引文
[1]Wang Zuchao,Yuan Xiaoru.Visual analysis of trajectory data[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(1):9-25(in Chinese)(王祖超,袁晓如.轨迹数据可视分析研究[J].计算机辅助设计与图形学学报,2015,27(1):9-25)
[2]Gong Xi,Pei Tao,Sun Jia,et al.Review of the research progresses in trajectory clustering methods[J].Progress in Geography,2011,30(5):522-534(in Chinese)(龚玺,裴韬,孙嘉,等.时空轨迹聚类方法研究进展[J].地理科学进展,2011,30(5):522-534)
[3]Zhao Zhujun,Ji Genlin.Research progress of spatial-temporal trajectory classification[J].Journal of Geo-Information Science,2017,19(3):289-297(in Chinese)(赵竹珺,吉根林.时空轨迹分类研究进展[J].地球信息科学学报,2017,19(3):289-297)
[4]Liu Dayou,Chen Huiling,Qi Hong,et al.Advances in spatiotemporal data mining[J].Journal of Computer Research and Development,2013,50(2):225-239(in Chinese)(刘大有,陈慧灵,齐红,等.时空数据挖掘研究进展[J].计算机研究与发展,2013,50(2):225-239)
[5]Lu Shengnan.Vehicle trajectory extraction and behavior analysis in complicated traffic video scene[D].Xi’an:Chang’an University,2016(in Chinese)(卢胜男.复杂交通视频场景中的车辆轨迹提取及行为分析[D].西安:长安大学,2016)
[6]Mao Y C,Zhong H S,Xiao X J,et al.A segment-based trajectory similarity measure in the urban transportation systems[J].Sensors,2017,17(3):Article No.524
[7]Yuan G,Sun P H,Zhao J,et al.A review of moving object trajectory clustering[J].Artificial Intelligence Review,2017,47(1):123-144
[8]Zhou Xingxing,Ji Genlin,Zhang Shuliang.Overview of the similarity measurement methods for spatial-temporal trajectory[J].Geomatics World,2018,25(4):11-18(in Chinese)(周星星,吉根林,张书亮.时空轨迹相似性度量方法综述[J].地理信息世界,2018,25(4):11-18)
[9]Toohey K,Duckham M.Trajectory similarity measures[J].SIGSPATIAL Special,2015,7(1):43-50
[10]Wang X Y,Mueen A,Ding H,et al.Experimental comparison of representation methods and distance measures for time series data[J].Data Mining and Knowledge Discovery,2013,26(2):275-309
[11]Dodge S,Weibel R,Laube P.Trajectory similarity analysis in movement parameter space[C]//Proceedings of the 19th GISResearch UK Annual Conference.Portsmouth:Zurich Open Repository and Archive,2011:270-279
[12]Dodge S,Laube P,Weibel R.Movement similarity assessment using symbolic representation of trajectories[J].International Journal of Geographical Information Science,2012,26(9):1563-1588
[13]Zhu Jin,Hu Bin,Shao Hua.Trajectory similarity measure based on multiple movement features[J].Geomatics and Information Science of Wuhan University,2017,42(12):1703-1710(in Chinese)(朱进,胡斌,邵华.基于多重运动特征的轨迹相似性度量模型[J].武汉大学学报:信息科学版,2017,42(12):1703-1710)
[14]Keogh E,Ratanamahatana C A.Exact indexing of dynamic time warping[J].Knowledge and Information Systems,2005,7(3):358-386
[15]Shao F,Cai S M,Gu J Z.A modified Hausdorff distance based algorithm for 2-dimensional spatial trajectory matching[C]//Proceedings of the 5th International Conference on Computer Science&Education.Los Alamitos:IEEE Computer Society Press,2010:166-171
[16]Xiao Xiaoqi.Research on vehicle sparse trajectory similarity in city traffic[D].Shanghai:Fudan University,2014(in Chinese)(肖啸骐.城市交通中的车辆稀疏轨迹相似性研究[D].上海:复旦大学,2014)
[17]Sun Lu,Zhou Wei,Jiang Baichen,et al.Multi-source trajectories similarity measure model with spatial and temporal constraints[J].Systems Engineering and Electronics,2017,39(11):2405-2413(in Chinese)(孙璐,周伟,姜佰辰,等.一种时空联合约束的多源航迹相似性度量模型[J].系统工程与电子技术,2017,39(11):2405-2413)
[18]Wan Y,Zhou C H,Pei T.Semantic-geographic trajectory pattern mining based on a new similarity measurement[J].ISPRSInternational Journal of Geo-Information,2017,6(7):Article No.212
[19]Wei Longxiang,He Xiaohai,Teng Qizhi,et al.Trajectory classification based on Hausdorff distance and longest common subsequence[J].Journal of Electronics&Information Technology,2013,35(4):784-790(in Chinese)(魏龙翔,何小海,滕奇志,等.结合Hausdorff距离和最长公共子序列的轨迹分类[J].电子与信息学报,2013,35(4):784-790)
[20]Cheng Zhiyuan.Traffic hotspot analysis based on trajectory clustering[D].Chengdu:University of Electronic Science and Technology of China,2018(in Chinese)(程智源.基于轨迹聚类的交通热点分析[D].成都:电子科技大学,2018)
[21]Furtado A S,Kopanaki D,Alvares L O,et al.Multidimensional similarity measuring for semantic trajectories[J].Transactions in GIS,2016,20(2):280-298
[22]Yuan Y H,Raubal M.Measuring similarity of mobile phone user trajectories-a spatio-temporal edit distance method[J].International Journal of Geographical Information Science,2014,28(3):496-520
[23]Zheng Y.Trajectory data mining:an overview[J].ACM Transactions on Intelligent Systems and Technology,2015,6(3):Article No.1
[24]Lu Feng,Liu Kang,Chen Jie.Research on human mobility in big data era[J].Journal of Geo-Information Science,2014,16(5):665-672(in Chinese)(陆锋,刘康,陈洁.大数据时代的人类移动性研究[J].地球信息科学学报,2014,16(5):665-672)
[25]Deng Min,Niu Shulian,Li Zhilin.A generalized Hausdorff distance for spatial objects in GIS[J].Geomatics and Information Science of Wuhan University,2007,32(7):641-645(in Chinese)(邓敏,钮沭联,李志林.GIS空间目标的广义Hausdorff距离模型[J].武汉大学学报:信息科学版,2007,32(7):641-645)
[26]Yuan J,Zheng Y,Xie X,et al.Driving with knowledge from the physical world[C]//Proceedings of the 17th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining.New York:ACM Press,2011:316-324
[2]Gong Xi,Pei Tao,Sun Jia,et al.Review of the research progresses in trajectory clustering methods[J].Progress in Geography,2011,30(5):522-534(in Chinese)(龚玺,裴韬,孙嘉,等.时空轨迹聚类方法研究进展[J].地理科学进展,2011,30(5):522-534)
[3]Zhao Zhujun,Ji Genlin.Research progress of spatial-temporal trajectory classification[J].Journal of Geo-Information Science,2017,19(3):289-297(in Chinese)(赵竹珺,吉根林.时空轨迹分类研究进展[J].地球信息科学学报,2017,19(3):289-297)
[4]Liu Dayou,Chen Huiling,Qi Hong,et al.Advances in spatiotemporal data mining[J].Journal of Computer Research and Development,2013,50(2):225-239(in Chinese)(刘大有,陈慧灵,齐红,等.时空数据挖掘研究进展[J].计算机研究与发展,2013,50(2):225-239)
[5]Lu Shengnan.Vehicle trajectory extraction and behavior analysis in complicated traffic video scene[D].Xi’an:Chang’an University,2016(in Chinese)(卢胜男.复杂交通视频场景中的车辆轨迹提取及行为分析[D].西安:长安大学,2016)
[6]Mao Y C,Zhong H S,Xiao X J,et al.A segment-based trajectory similarity measure in the urban transportation systems[J].Sensors,2017,17(3):Article No.524
[7]Yuan G,Sun P H,Zhao J,et al.A review of moving object trajectory clustering[J].Artificial Intelligence Review,2017,47(1):123-144
[8]Zhou Xingxing,Ji Genlin,Zhang Shuliang.Overview of the similarity measurement methods for spatial-temporal trajectory[J].Geomatics World,2018,25(4):11-18(in Chinese)(周星星,吉根林,张书亮.时空轨迹相似性度量方法综述[J].地理信息世界,2018,25(4):11-18)
[9]Toohey K,Duckham M.Trajectory similarity measures[J].SIGSPATIAL Special,2015,7(1):43-50
[10]Wang X Y,Mueen A,Ding H,et al.Experimental comparison of representation methods and distance measures for time series data[J].Data Mining and Knowledge Discovery,2013,26(2):275-309
[11]Dodge S,Weibel R,Laube P.Trajectory similarity analysis in movement parameter space[C]//Proceedings of the 19th GISResearch UK Annual Conference.Portsmouth:Zurich Open Repository and Archive,2011:270-279
[12]Dodge S,Laube P,Weibel R.Movement similarity assessment using symbolic representation of trajectories[J].International Journal of Geographical Information Science,2012,26(9):1563-1588
[13]Zhu Jin,Hu Bin,Shao Hua.Trajectory similarity measure based on multiple movement features[J].Geomatics and Information Science of Wuhan University,2017,42(12):1703-1710(in Chinese)(朱进,胡斌,邵华.基于多重运动特征的轨迹相似性度量模型[J].武汉大学学报:信息科学版,2017,42(12):1703-1710)
[14]Keogh E,Ratanamahatana C A.Exact indexing of dynamic time warping[J].Knowledge and Information Systems,2005,7(3):358-386
[15]Shao F,Cai S M,Gu J Z.A modified Hausdorff distance based algorithm for 2-dimensional spatial trajectory matching[C]//Proceedings of the 5th International Conference on Computer Science&Education.Los Alamitos:IEEE Computer Society Press,2010:166-171
[16]Xiao Xiaoqi.Research on vehicle sparse trajectory similarity in city traffic[D].Shanghai:Fudan University,2014(in Chinese)(肖啸骐.城市交通中的车辆稀疏轨迹相似性研究[D].上海:复旦大学,2014)
[17]Sun Lu,Zhou Wei,Jiang Baichen,et al.Multi-source trajectories similarity measure model with spatial and temporal constraints[J].Systems Engineering and Electronics,2017,39(11):2405-2413(in Chinese)(孙璐,周伟,姜佰辰,等.一种时空联合约束的多源航迹相似性度量模型[J].系统工程与电子技术,2017,39(11):2405-2413)
[18]Wan Y,Zhou C H,Pei T.Semantic-geographic trajectory pattern mining based on a new similarity measurement[J].ISPRSInternational Journal of Geo-Information,2017,6(7):Article No.212
[19]Wei Longxiang,He Xiaohai,Teng Qizhi,et al.Trajectory classification based on Hausdorff distance and longest common subsequence[J].Journal of Electronics&Information Technology,2013,35(4):784-790(in Chinese)(魏龙翔,何小海,滕奇志,等.结合Hausdorff距离和最长公共子序列的轨迹分类[J].电子与信息学报,2013,35(4):784-790)
[20]Cheng Zhiyuan.Traffic hotspot analysis based on trajectory clustering[D].Chengdu:University of Electronic Science and Technology of China,2018(in Chinese)(程智源.基于轨迹聚类的交通热点分析[D].成都:电子科技大学,2018)
[21]Furtado A S,Kopanaki D,Alvares L O,et al.Multidimensional similarity measuring for semantic trajectories[J].Transactions in GIS,2016,20(2):280-298
[22]Yuan Y H,Raubal M.Measuring similarity of mobile phone user trajectories-a spatio-temporal edit distance method[J].International Journal of Geographical Information Science,2014,28(3):496-520
[23]Zheng Y.Trajectory data mining:an overview[J].ACM Transactions on Intelligent Systems and Technology,2015,6(3):Article No.1
[24]Lu Feng,Liu Kang,Chen Jie.Research on human mobility in big data era[J].Journal of Geo-Information Science,2014,16(5):665-672(in Chinese)(陆锋,刘康,陈洁.大数据时代的人类移动性研究[J].地球信息科学学报,2014,16(5):665-672)
[25]Deng Min,Niu Shulian,Li Zhilin.A generalized Hausdorff distance for spatial objects in GIS[J].Geomatics and Information Science of Wuhan University,2007,32(7):641-645(in Chinese)(邓敏,钮沭联,李志林.GIS空间目标的广义Hausdorff距离模型[J].武汉大学学报:信息科学版,2007,32(7):641-645)
[26]Yuan J,Zheng Y,Xie X,et al.Driving with knowledge from the physical world[C]//Proceedings of the 17th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining.New York:ACM Press,2011:316-324