Abstract: With the development and widespread use of mobile communication technology and global positioning system,location-based service (LBS) receives extensive attention.Location prediction technology is an important part of LBS,and has wide application.In practical application,GPS trajectories are often sparse due to the sampling points lost or a new user appearing,which makes the accuracy of location prediction based on data of a single user low.To solve this problem,this paper proposed a novel Markov location prediction approach based on similarity of moving behavior and clustering of users.Firstly,in order to endow the locations with physical meaning,this paper proposed a region partitioning method based on Voronoi diagram.Then,the paper transformed the GPS trajectories into region trajectories and predicted the locations over region trajectories.Secondly,this paper put forward a new approach to measure the simi-larity of users’ moving behavior by considering users’ transfer features and regional features.Thirdly,based on the similarity of moving behavior,this paper divided users into various groups and applied the first-order Markov model on the groups for location prediction,which improves the accuracy of location prediction.The experiments over real GPS trajectory dataset indicate that the proposed method is effective for location prediction.

Key words: Location prediction, Moving behavior similarity, Region vector, Transition probability matrix