I am working with a dataset that includes the trajectories of various car trips and would like to be able to predict their destinations using only a subset of the trip trajectory. For instance, if in the training data the car starts at A and goes to B and C before ending up at D, I want to be able to predict that they would end up at D, knowing A, B, and C. I have many instances to use for training, with variable length trajectory lines.

My thought is that this is a kind of higher order Markov chain, since what the driver does most likely depends on what happened a few points earlier, not just on the current state.

Because the data come as coordinates (latitude and longitude), in order to predict the output (from any kind of algorithm) I would want a regressor capable of emitting two dependent variables. Doing this analysis twice with each variable separately isn't really a good idea given how the variables are extremely correlated with each other.

Does anyone know of a way to use a variable amount of "time-like" sequence data (sequence of xy coordinates) with an HMM regressor to predict a continuous, multivariate output?

The ideal answer would show how to fit a k-order HMM to each instance of the training data and somehow store those results in a matrix. Ideally the fit itself could also be influenced by other features besides the trajectory, such as time of departure, weekend or weekday, etc. Once this matrix is built from the training data, you could just feed in the test samples and use some kind of similarity algorithm to find the "best fit" through the training matrix and then use the values from best-fit HMM to predict the destination (continuous valued, xy coordinates). I know this is not trivial.

I am aware of some of the work primarily in biological sequence comparison and annotation that attempts similar things, but these are often very difficult to implement and understand. In addition, they make use of data very specific to that field.

Additional suggestions are very welcome. Thank you!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.