Research On Location Prediction Based On GPS Trajectory Data

In recent years,with the development of commucation and location sensing technologies,the need for the Location-Based Service(LBS)is increasing.Location prediction,which is a part of LBS,has important applications in many fields such as advertising service and position navigation.The existing location prediction methods are mainly based on frequent pattern mining and Markov model.These methods can be better applied to GPS trajectory data.However,the order of the Markov model is difficult to determine.Besides,most existing methods are based on the spatial feature and the temporal feature of trajectory data,without further mining the semantics hidden in trajectories.Thus,the performance of location prediction is bad.For these problems,this dissertation studies on location prediction from two aspects.First,for the prolems existing in Markov model based location prediction methods,this dissertation proposes some improved methods;Second,while considering the spatial feature and the temoral feature,the semantic feature of trajectories is considered in location prediction,and the location prediction method based on multiple trajectory features is studied.The main contributions of the dissertation are as follows:(1)In order to solve the problems existing in traditional methods,a method of forming regions based on the traffic hub and the Voronoi graph is proposed,and the map is divided into meaningful regions centered around traffic hubs.It provides data support for subsequent model construction and prediction,and enhances the practicability of location prediction.(2)In the course of the clustering based on the mobile characteristic similarity of users,facing the characteristics of trajectory data,a similarity measure method of user mobile characteristics based on region vector and transition probability matrix is proposed,which considers both the region visiting characteristics of users and the region transferring characteristics of users simultaneously.On this basis,users are clustered according to their mobile characteristic similarity.Thus,the problem of data sparseness,which is caused by modeling based on the trajectories of single user,is solved.Meanwhile,the performance of location prediction is improved due to considering the region visiting characteristics and the region transferring characteristics.(3)In order to solve the problems existing in the traditional Markov model based location prediction,a multi-step-fusion Markov location prediction model is proposed,which solves the problem that the 1-order Markov model does not utilize trajectory information fully so that the performance of prediction is bad,and the problem that the state space of multi-order Markov model expands sharply.In order to improve the fusion effect of various models,in the process of establishing the multi-step-fusion Markov location prediction model,a generation and optimization method of fusion weights of models is proposed based on the Adaboost framework and the differential evolution algorithm.(4)On the basis of the establishment of user clusters and the multi-step-fusion Markov location prediction model,a multi-step-fusion Markov location prediction method based on clustering according to the mobile characteristic similarity is proposed.By establishing the corresponding multi-step-fusion Markov model for each user cluster generated by clustering,and selecting the user cluster model suitable for the characteristics of the current trajectory,the problems of the data sparseness of single user and the state space expansion are solved.And the accuracy of location prediction is improved without increasing the state space of Markov model.(5)In the process of multiple trajectory features based location prediction,according to the characteristics of trajectory data,the method solving longest common subsequence is improved,and the semantic sequence similarity calculation method is proposed based on the semantic feature and the temporal feature of trajectories.On this basis,the hierarchical trajectory clustering method which can set the similarity threshold adaptively by defining the clustering evaluation index is proposed,and the clustering effect is improved.Trajectory clustering not only solves the problem of data sparseness,but also effectively solves the problem that the new behaviors of users can not be predicted.(6)In order to improve the accuracy of location prediction,making full use of the temporal feature and the semantic feature of trajectories,a method of constructing semantic prediction model is proposed by clustering trajectories and establishing the semantic tree structure for each cluster.On this basis,combined with the spatial prediction model,which considers the spatial feature of trajectories,a location prediction method based on multiple features of trajectories including the spatial feature,the temporal feature and the semantic feature is proposed.The prediction results not only consider the regions of users' activities,but also users' behavior semantics,which improves the accuracy and practicability of the location prediction.Through the analysis and the experiments on real dataset,it is proved that the methods of location prediction proposed in this dissertation are feasible and effective.