Machine learning algorithm to predict next user's destination

Question

I'm searching for a way to formulate my problem as a machine learning problem.

Suppose I have a history of user's locations, and I want to predict his next location, similar to how Google Now does it for Home/Work locations.

The problem is that I need to somehow encode user's current location, and the space of possible locations can be different. One way to approach this is to encode topK most frequent locations and use them as binary features, but then the model have to be rebuilt when topK locations change.

So I was thinking is there a better way to approach such problem?

UPDATE: Specifically, the set of locations is discrete (locations are public transport stations).

Answer 1

Your problem can be profitably solved with a Markov model; estimate the distribution of the next location by the previous $k$ places. Relevant papers include:

• Prediction in wireless networks by Markov chains
• A Comparison of First- and Second-Order HMMs in the Task of Predicting the Next Locations of Mobile Individuals
• Predicting Future Locations with Hidden Markov Models
• Learning and detecting activities from movement trajectories using the hierarchical hidden Markov model
• Growing Hidden Markov Models: An Incremental Tool for Learning and Predicting Human and Vehicle Motion or Incremental Learning of Statistical Motion Patterns With Growing Hidden Markov Models

If you need inspiration for extracting the places from the mobility trace, see

• Extracting places from traces of locations
• Extracting Places and Activities from GPS Traces Using Hierarchical Conditional Random Fields
• Discovering Personally Meaningful Places: An Interactive Clustering Approach
• Using GPS to Learn Significant Locations and Predict Movement Across Multiple Users
• A Clustering-Based Approach for Discovering Interesting Places in Trajectories
• Scalable Analysis of Movement Data for Extracting and Exploring Significant Places
• Identifying Meaningful Places: The Non-parametric Way
• Supervised semantic labeling of places using information extracted from sensor data
• Eigenplaces: Segmenting Space through Digital Signatures
• The Places of Our Lives: Visiting Patterns and Automatic Labeling from Longitudinal Smartphone Data

It's basically a spatio-temporal clustering problem. Let me know if you get stuck on any of the papers.