Measurement And Application On User Trajectory Similarity Based On Spatio-temporal Data

As the rapid development of wireless communication technology,video surveillance technology and GPS satellite positioning technology,the number of spatio-temporal trajectory data of moving objects is increasing rapidly.The trajectory data contains time and position information,which can reflect the behavior characteristics and movement regulation of the observation objects.Therefore,how to analyze and mine massive spatio-temporal trajectory data has become a research hotspot.Among them,measuring the similarity between trajectories is an important premise for analyzing and mining trajectory data.Therefore,this paper studies the similarity of the spatio-temporal trajectory data collected from traffic checkpoint and applies the similarity into different scenes.The main work is as follows:Firstly,this paper introduces the spatio-temporal trajectory data which collected by traffic checkpoint.Then the experimental data are preprocessed,including data cleaning,trajectory splicing,trajectory segmenting and other processes.In the process of trajectory cleaning,we use map matching method to identify the trajectory offset data and delete it.In the process of trajectory segmenting,considering the uneven distribution of trajectory data in time dimension and sparse distribution of trajectory data in space dimension,this paper proposes to select an appropriate segmentation threshold from time and space dimensions to segment user trajectories.The segmented trajectories provide a good data support for similarity research.Considering that the length of these preprocessed user trajectories is inconsistent,we propose to use Dynamic Time Warping algorithm or Accelerated Dynamic Time Warping algorithm to measure the similarity between different trajectories.The two algorithms make the length of two trajectories equal by scaling the trajectory sequences partially on time dimension,which is conducive to measure the similarity between two trajectories.In order to choose the most suitable measurement method for the experimental data,this paper uses simulation experiments to compare the speed and accuracy of the two algorithms.Finally,according to the results of experiment and the characteristics of experimental data,the Dynamic Time Warping algorithm was chosen to measure the similarity between trajectories.Apply the similarity of trajectories into trajectory retrieval and trajectory clustering.In order to retrieve the adjoint trajectories,the Dynamic Time Warping algorithm is used to measure the similarity between the experimental trajectories and the target trajectory,and the top ten trajectories which are most similar to the target trajectory are output as adjoint trajectories.As for trajectory clustering,we select the OPTICS algorithm to cluster trajectories,clustering similar trajectories into the same cluster and clustering dissimilar trajectories into different clusters.Based on this algorithm,this paper proposes two innovations:(1)transform the clustering way from points to points into trajectory segment to trajectory segment;(2)use the Dynamic Time Warping algorithm to measure the similarity between trajectories instead of using Euclidean function to measure the distance between samples.Finally,use the Davies-Bounldin Index(DBI)and the Dunn Index(Dunn)to evaluate the clustering effect.The experimental results prove that the OPTICS algorithm based on the similarity of spatio-temporal trajectory is good.