Abstract: GPS trajectories are often sparse due to the sampling points lost or new users appearing， which makes the accuracy of location prediction low based on the data of a single user. To solve this problem， a novel Markov location prediction approach was proposed based on user mobile behavior similarity and user clustering. First， the map was partitioned into various regions based on Voronoi diagram and original GPS trajectories. And then locations were predicted over region trajectories. Second， a new approach was proposed to measure the similarity of users’ mobile behaviors by considering users’ transferring features and regional features. Third，based on the mobile behavior similarity， users were divided into various groups and the first-order Markov model was applied on the groups to predict users’ locations. Therefore， the accuracy of location prediction was improved. The experiments over real GPS trajectory dataset indicate that the proposed method is effective for location prediction.

Key words: mobile behavior similarity, transition probability matrix, region vector, clustering probability vector, location prediction