Research On Location Prediction Over Sparse Trajectory Data

With the development of location based services, location prediction has become a necessary task. For example, by predicting user’s destination, tourist spots can be recommended to the users, and some discount information of supermarkets and shopping malls can be released, etc. Location prediction is to infer the user’s next position based on users’ history data. With the influence of some practical factors, for example, data packets lost, the sampling interval is too long, and location updating is not in time, the position updating of the moving object may be miss some parts of path information. So, there is a problem in the GPS dataset, namely data sparseness problem. The existing researches are not suitable for sparse data. If the mining is done on sparse data directly, prediction accuracy will be low. Therefore, in view of sparse data, this thesis puts forward a prediction scheme. In order to enhance the prediction accuracy, the thesis takes the effect of time factor on prediction into account in the course of pattern mining, emphasizing the influence of trajectories at closer time on mobile patterns. Meanwhile, The IDs of the trajectories containing frequent trajectory patterns are stored in a list to avoid scanning the original dataset, improving the efficiency of mining.The main contributions of this thesis are as follows:Firstly, in view of the sparse data, this thesis proposes a method to deal with the sparse trajectory data, solving the problem of low accuracy caused by sparse data.Secondly, because of the effect of old trajectory on prediction accuracy, this thesis proposes a new method computing support based on fresh degree, which considers the time factor during pattern mining and improves the precision of prediction.Thirdly, in view of the pattern mining problem, this thesis links trajectory pattern and network topology, figures the visiting area with a weighted directed graph and proposes the concept of trajectory identification list to decrease the number of candidate patterns and avoid scanning the original data set repeatedly, improving the efficiency of the algorithm.Finally, this thesis proposes an clustering algorithm to mine similar users, using the similar users’ data to predict to alleviate the data sparseness problem. At the same time, this thesis puts forward a matching strategy to improve the prediction precision, which can achieve full matching and partial matching.The theoretical analysis and experimental evaluations show that the location prediction methods proposed by the thesis on sparse trajectory data are feasible and effective.