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).

  • 2
    $\begingroup$ I can recommend numerous papers once I determine your problem setting and assumptions. Do you want the destination to be a known "place"; i.e., a discrete location like "home", or "work", or can it be an arbitrary physical location? How far ahead do you want to predict; seconds, minutes, hours, days, or further still? Do you the user's historical mobility data? $\endgroup$
    – Emre
    Nov 24, 2014 at 19:25
  • $\begingroup$ Thank you very much! Please see my update regarding the set of locations. As for the "ahead" prediction, I just want to predict the next location based on current time (i.e, time is one of the features). $\endgroup$
    – dragoon
    Nov 24, 2014 at 19:41

1 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.

  • $\begingroup$ Thank you, the papers sound very interesting, I'll look into them. $\endgroup$
    – dragoon
    Nov 24, 2014 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.