应用Hausdorff距离的时空轨迹相似性度量方法  

Measuring Similarity of Spatio-Temporal Trajectory Using Hausdorff Distance

作　　者：王培[1] 江南[1] 万幼[2] 王玉晶 Wang Pei;Jiang Nan;Wan You;Wang Yujing(School of Geospatial Information, Information Engineering University, Zhengzhou 450052;School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079)

机构地区：[1]信息工程大学地理空间信息学院,郑州450052 [2]武汉大学资源与环境科学学院,武汉430079

出　　处：《计算机辅助设计与图形学学报》2019年第4期647-658,共12页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家重点研发计划(2016YFB0502300);国家自然科学基金(41471336;41471327)

摘　　要：相似性度量方法的选取和稳健性对时空轨迹聚类结果的有效性是至关重要的.针对时空轨迹数据复杂的多重维度信息,选取空间维和时间维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.

关 键 词：时空轨迹 HAUSDORFF距离 时间相似性 空间相似性 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]