Research On Location Prediction Based On Hybrid Multi-Step Markov Model

In recent years, with mobile localization technology maturing and popular, location-based service (LBS) receives extensive attention. Location prediction is an important part of LBS, which is widely applied. At present, there are a lot of researches to predict location based on Markov Model, in which many problems exist. For example, regions are not partitioned reasonably, users’characteristics are not considered, and the prediction is only based on current locations. So, further research on Markov Model for location prediction is extremely urgent.The thesis solves the existing problems by designing a novel scheme on the basis of traditional location prediction theory based on Markov Model. The scheme consists of off-line data processing, model training and on-line location predication, which has higher accuracy as well as a wider application range. The main contributions of this thesis are summarized as follows.First, the thesis proposes a location prediction scheme only based on GPS data, which are acquired more easily. The scheme is more practical and useful.Second, to solve the problems existing in map-partitioning by grid of traditional location prediction, the thesis puts forward a new map-partitioning scheme which abstracts points of interest (POIs) from GPS data. The map can be partitioned more reasonably based on POIs.Third, to solve the problem that users’characteristics are not considered exiting in traditional Markov prediction model, the thesis proposes a clustering algorithm, which divides users into various user groups to establish independent prediction model for each group. Experimental results show that the prediction accuracy rate has been effectively improved.Finally, the thesis establishes a hybrid k-step Markov Model for location prediction which is based on users’multiple location histories and provides the weight of each location.In addition, users’moving activities are not necessarily in accordance with their usual moving behaviors. Therefore, the Bayes method has been used to select the most suitable model for location prediction on the basis of the current trajectory. Meanwhile, it also makes the location prediction method work well for new users or users with less historical trajectory data.It has been proved by theoretical analysis and experimental evaluation that location prediction method based on the hybrid k-step Markov Model is theoretically feasible and technically practical.