A Collaborative Filtering Approach to Citywide Human Mobility Completion from Sparse Call Records

Zipei Fan, Ayumi Arai, Xuan Song, Apichon Witayangkurn, Hiroshi Kanasugi, Ryosuke ShibasakiIJCAI 2016

Introduction: The Challenge of Sparse Mobility Data

While mobile phone data offers unprecedented insights into urban dynamics, it is inherently "holey." Call Detail Records (CDRs) are active recordings; a data point is generated only when a user initiates a call or text. Consequently, individual trajectories often contain only a few records per day, leaving vast temporal gaps.

Standard techniques like linear interpolation are physically unrealistic for human movement, often assuming a constant, slow drift between distant points over several hours. In reality, human movement is governed by routines—staying at home to sleep and then commuting quickly to work. This research aims to "complete" these trajectories by learning and applying these underlying behavioral patterns.

Methodology: Collaborative Filtering and Path Smoothing

The proposed framework addresses mobility completion through a two-stage process that treats location prediction as a recommendation problem.

Overview of the mobility completion framework, transitioning from sparse call records to a completed trajectory using collaborative filtering and HMM smoothing.

1. Spatio-temporal Collaborative Filtering via LDA

The researchers model a user’s daily movements as a "document" where locations and time-slots serve as "words." A modified Latent Dirichlet Allocation (LDA) model discovers latent "topics"—common mobility patterns such as "home" (dominant at night) or "work" (peaking during office hours). The model leverages "collaborative" data, using a user's historical patterns and the behaviors of similar users to infer likely locations for missing time slots.

2. HMM-based Path Completion

To ensure physical consistency and prevent "teleportation," the LDA-derived probability distributions are integrated into a Hidden Markov Model (HMM).

  • Emission Probability: Represents the likelihood of a user being at a specific antenna based on the LDA's temporal topic distributions.
  • Transition Matrix: Encodes spatial constraints, favoring transitions to nearby antennas or remaining stationary.
  • Viterbi Algorithm: Determines the most probable sequence of locations connecting the sparse "anchor" records.

Key Insights: Mobility as a Routine Topic

The core innovation lies in treating human movement as a composition of recurring topics. The model successfully identified distinct patterns for different demographic groups and temporal cycles.

Topic distribution over a 31-day period. The dramatic shift around day 9 illustrates the "Festival Effect" during Eid al-Fitr, where standard routines are replaced by holiday-specific behaviors.

A notable finding is the "Festival Effect." During the Eid al-Fitr holiday, the model detected a complete breakdown of typical "work" and "home" distributions, replaced by a unique "festival" pattern. While simple interpolation would fail to account for such collective behavioral shifts, the collaborative filtering approach successfully learned these citywide anomalies.

Experimental Results

The model was evaluated using a massive real-world dataset from a leading telecommunications provider in Bangladesh, covering 10 million users over four months. By holding out 10% of known records as ground truth, the researchers compared their method against Linear and Nearest Record Interpolation.

  • Accuracy: The proposed model achieved an average error of 1.122 km, a significant improvement over Linear (3.909 km) and Nearest (3.595 km) interpolation.
  • Precision: Nearly 79% of the completions were within 100 meters of the actual location, compared to ~60-64% for baseline methods.
  • Application: The framework enabled the creation of a "Dynamic Census," visualizing how different populations (e.g., housewives vs. workers) move through the city in real-time.

Conclusion and Future Directions

This collaborative filtering approach demonstrates that sparse, active-sensing data can be transformed into high-fidelity trajectories by leveraging collective human routines. While the current model relies on straight-line distances, future work aims to incorporate road network constraints and Points of Interest (POIs) to further refine transition probabilities. Additionally, integrating official census data could help mitigate "owner bias" inherent in mobile phone datasets.

Summary updated

BibTeX
@inproceedings{fan2016collaborative,
  author = {Zipei Fan and Ayumi Arai and Xuan Song and Apichon Witayangkurn and Hiroshi Kanasugi and Ryosuke Shibasaki},
  title = {{A Collaborative Filtering Approach to Citywide Human Mobility Completion from Sparse Call Records}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure