What if we could predict the short-term movement of millions of people in near real-time?
Predicting large-scale human mobility is a at the basis of many important applications: schedule-free public transport, mobility management, emergency response, to mention a few. The question can be formulated as follows: how to predict the the short-term mobility of an entire population (e.g. city, region) based on the past mobility of its members? The interest here is never on the individual mobility, but on the large scale collective result of thousands of millions of individual choices.
Until recently this problem was virtually unsolvable because of lack of data and computational difficulties. This has all changed, and there are dozens of sources that directly or indirectly measure individual and collective mobility behavior (social media, handset traces, credit card transactions, navigation traces). This paves the way to a range of methods and tools which leverage this new data to derive large-scale mobility predictions.
The most common way to predict one's movement is to extrapolate from movement history. Algorithms such as Markov models extrapolate the future location of a user only on the basis of the user’s past movement (by assessing at every step the probably of ending up in specific future location from the current one). For regular movement and long histories these methods work well and are totally data driven (no assumptions: history tells everything that is needed). However, they do not predict well when the trace of movement is short or it has an erratic pattern.
Our collective mobility, however, is constrained in many ways and so is our individual mobility: research shows predictability up to 90%. The question is: how can we use this collective "regularity" to improve predictions?
There are two main observations on this. The first is that it is extremely likely that many other users in the past have made the same time-space transition that a user is about to make. This implies that by looking at patterns of behavior of similar users in the past we can possibly improve single and then collective predictability. The second is that predicting human movement is a special case of sequential predictions, when space is discretized into a set of places (1 km x km squares, or municipalities, or Points of Interest).
We developed a generic algorithm that predicts the next element in a sequence. This has many applications, such as:
The algorithm - called Exponential Weight Forecaster (EWF) - predicts the next event in a sequence based on the sequence characteristics but also on the unfolding of all other sequences in the system, which serves to validate and improve individual predictions. When deployed with massive datasets of millions of sequences, it has significant advantages:
EWF applied to human mobility leverages the time-space traces of all users in the same system - millions of users - to improve the predictability of each individual user. EWF exploits this collective wisdom to improve individual predictions and, at every step, compares predictions with outcomes in a continuous learning and improvement.
We have tested EWF to predict the short term mobility of tourists (short sequences, bursts of data). EWF predicts systematically better than the state of the art prediction algorithms for human movement. The average predictability reached 81% for a one-hour period in the future at the resolution of a few hundred meters in urban areas and a few kilometers in rural areas.
Details of EWF and its application to mobility can be found in the paper: Collective Prediction of Individual Mobility Traces with Exponential Weights ( see page footer) .
The clip below shows the predicted movements of tourists that are in Milano on a specific day (in this case, 20 June, 2013). The predictions are very accurate for a few hours and then tend to revert to the average movement of tourists as the prediction time extends to several hours or days.