Sparse Trajectory Prediction Methods Based On Entropy Estimation

With the rapid development of Global Positioning System(GPS)technology and mobile communication technology,the trajectory data of moving objects has an explosive growth.Massive trajectory data urgently demands for storage,processing and further mining.Trajectory prediction of moving objects has become one of the most important issues in trajectory data mining field.Trajectory prediction of moving object has important significance to alleviate the traffic pressure,location based services(LBSs)and applications,privacy protection,etc.This thesis focuses on sparse trajectory prediction.In conclusion,this thesis consists of the following achievements.(1)Sparse trajectory prediction method based on iterative grid partition and entropy estimationTrajectory prediction of moving objects has become one of the most important issues in trajectory data mining field.Trajectory prediction method of moving objects is only based on historical trajectory dataset now.However,this approach cannot solve the “data sparsity” problem of trajectory prediction effectively,i.e.,the available historical trajectories are far from enough to cover all possible query trajectories that can obtain predicted destinations.In order to solve the above problem,this paper proposed a sparse trajectory prediction method based on iterative grid partition and entropy estimation(TPDS-SIGP&EE).Firstly,TPDS-SIGP&EE uses Spatial Iterative Grid Partition algorithm and the method of generating trajectory sequence.Secondly,an L-Z entropy estimator is used to calculate the entropy value of trajectory sequence,and a method of trajectory synthesis based on trajectory entropy is given.At last combining with the Trajectory Prediction by Sub-Trajectory Synthesis(TP-SubSyn),we proposed a novel method named sparse trajectory prediction based on iterative grid partition and entropy estimation.The experiments show the proposed method could make an effective prediction for the sparse trajectory.Compared with the existing methods,our method needs smaller trajectory space,while provids much wider predicting ranges,faster predicting speed and better predicting accuracy.(2)Sparse trajectory prediction method based on multiple entropy measuresTime factor plays a part in trajectory prediction,and this paper introduces L-Z Entropy,Location Entropy,Time Entropy and Transition Entropy to evaluate the regularities of the whole trajectory,the time,the location and the transition of locations.These entropy measures can improve the accuracy of trajectory prediction.So we propose a Sparsity Trajectory Prediction Algorithm based on Multiple Entropy Measures(STP-ME)to address the data sparsity problem.Firstly,the moving region is divided into a two-dimensional plane grid graph iteratively,and each trajectory represents a grid sequence with temporal information.Secondly,Trajectory Entropy is used to evaluate trajectory's regularity,and the L-Z entropy estimator is implemented to calculate Trajectory Entropy,and a new trajectory space is generated through trajectory synthesis.We define Location Entropy and Time Entropy to measure the popularity of locations and timeslots.Finally,a 2nd-Order Markov Model that contains temporal dimension(2-TMM)is adopted to perform sparse trajectory prediction.The experiments show when trip completed percentage increases towards 90%,the coverage of the Baseline algorithm decreases to almost 25%,while the STP-ME algorithm copes with it as expected with only an unnoticeable drop in coverage successfully,and can constantly answer almost 100% of query trajectories.It is found that the STP-ME algorithm improves the prediction accuracy generally by as much as 8%,3% and 4% compared to the Baseline algorithm,2-MM and SubSyn algorithm respectively.At the same time,the prediction time of STP-ME algorithm is negligible(10 ms),greatly outperforming the Baseline algorithm(100 ms).