Similarity-based human mobility prediction across 225K+ users and 4 cities using DTW, GMM blending, and interpretable pattern transfer
A production-grade trajectory prediction algorithm for the SIGSPATIAL GISCup 2025 challenge. The algorithm finds users with similar movement patterns and blends their behaviors with Gaussian Mixture Models to predict where an individual moves next. It reaches competitive GEO-BLEU scores and stays interpretable.
Problem
Predict individual trajectory sequences for 225K+ users across four metropolitan areas in Japan from 60 days of historical mobility data. Users with sparse or incomplete trajectories need predictions from limited context, and the algorithm must generalize across cities with different urban structures and mobility patterns.
Approach
Similarity-based prediction on the principle that users exhibiting similar past movement patterns will exhibit similar future behaviors. The algorithm has four phases: (1) candidate selection via random sampling and DTW-based similarity scoring with adaptive termination; (2) pattern extraction from similar users, capturing relative displacement sequences; (3) pattern blending using Gaussian Mixture Models to preserve multimodal behavior distributions; (4) trajectory generation by sampling from the blended model and applying displacements sequentially.
Architecture
Python with scikit-learn for GMM fitting, pandas and numpy for trajectory manipulation, Parquet columnar storage for efficient random access to the 225K+ user pool. DTW (Dynamic Time Warping) computes similarity scores with semantic alignment. Parallelizable design: each user's prediction is computed independently without inter-user dependencies, enabling multi-process execution across CPU cores.
Outcome
The algorithm reached a GEO-BLEU score of 0.02764 across all four cities (City C: 0.03575, City D: 0.03454) in the competition evaluation. It showed cross-city generalization without city-specific model retraining. Random sampling keeps prediction latency in check even with large candidate pools. The interpretable design names which similar users inform each prediction, which deep learning approaches cannot, and holds competitive accuracy.
Problem context: mobility prediction at scale
Human mobility prediction serves urban planning, transportation optimization, disaster response, and public health. Predicting where an individual moves from incomplete trajectory history is hard. Deep learning approaches (RNNs, LSTMs, Transformers) reach high accuracy but operate as black boxes. This project took a similarity-based approach that trades some accuracy for interpretability. The algorithm reports which users' patterns informed each prediction.
The four-phase algorithm
Phase 1: Candidate Selection with Adaptive Search
Rather than compute DTW distance against all 225K+ candidates (prohibitively expensive), the algorithm uses random sampling with two quality thresholds:
- High-quality threshold (τ₁ = 500): DTW scores below this indicate excellent similarity matches. Finding 2+ high-quality candidates triggers early termination.
- Acceptable threshold (τ₂ = 1000): Weaker but usable candidates. Accumulating 3 acceptable candidates also triggers termination.
- 30-second timeout: Ensures computational feasibility even for users with sparse matches in the pool.
This adaptive strategy balances prediction quality (don't settle for weak candidates if good ones exist) with computational efficiency (don't search forever).
Phase 2: Movement Pattern Extraction
For each selected similar user, the algorithm partitions their historical trajectory into a base period (corresponding to the target user's training data) and an extension period (corresponding to the target user's prediction window). Relative displacement vectors are computed from the similar user's extension period trajectory, anchored to their base period endpoint:
def extract_patterns(similar_user_trajectory, base_end, ext_start, ext_end):
# Partition into base and extension periods
base_traj = similar_user_trajectory[:base_end]
ext_traj = similar_user_trajectory[ext_start:ext_end]
# Get anchor point from end of base period
anchor = base_traj[-1] # last observed position in base
# Compute relative displacements: how the user moved during extension
displacements = []
for pos in ext_traj:
dx = pos.x - anchor.x
dy = pos.y - anchor.y
displacements.append((dx, dy))
return np.array(displacements)
The relative representation lets patterns transfer across absolute spatial contexts. A pattern of "move 10 units west then 5 north" stays meaningful no matter where the target user starts.
User-level similarity heatmap (User 17) showing GEO-BLEU similarity scores to all other users in the dataset
Phase 3: Gaussian Mixture Model Blending
Simple averaging of similar users' patterns collapses multimodal behavior into a single mean, losing important variance. Instead, the algorithm fits a 2-component Gaussian Mixture Model to the concatenated displacement vectors from all similar users:
from sklearn.mixture import GaussianMixture
# Collect all displacements from all similar users
all_displacements = np.vstack([extract_patterns(su) for su in similar_users])
# Fit GMM with 2 components
gmm = GaussianMixture(n_components=2)
gmm.fit(all_displacements)
# GMM captures: (1) primary movement modes (commuting, routine) and
# (2) secondary behaviors (exploration, visits to secondary centers)
The two-component model captures both primary movement tendencies (regular commuting routes) and behavioral variance (exploratory movement, visits to secondary activity centers). It preserves the multimodality of human mobility instead of collapsing it.
GMM fitting showing how the two-component mixture captures multimodal displacement distributions
Phase 4: Trajectory Generation
The blended GMM distribution then drives prediction. For each time step in the prediction period, the algorithm draws a displacement from the GMM and applies it to the current position, building the predicted trajectory step by step:
def generate_trajectory(current_pos, gmm, num_steps):
trajectory = []
pos = current_pos
for _ in range(num_steps):
# Sample displacement from blend distribution
displacement = gmm.sample(n_samples=1)[0]
dx, dy = displacement
# Apply and clip to valid bounds
new_x = np.clip(pos.x + dx, min_x, max_x)
new_y = np.clip(pos.y + dy, min_y, max_y)
pos = (new_x, new_y)
trajectory.append(pos)
return trajectory
The step-by-step generation captures temporal dependencies, since each position depends on the previous one, without an explicit sequence model.
Computational efficiency and scalability
The random sampling strategy with adaptive termination keeps computational burden tractable:
- Candidate Selection: O(s · |T|²) where s is the number of candidates sampled (typically 10–50, far less than 225K). DTW computation is O(|T|²) in trajectory length.
- Pattern Extraction: O(k · |T_pred|) where k is the number of similar users (typically 2–3).
- GMM Blending: O(k · |T_pred| · n_components · EM_iterations) handled efficiently by scikit-learn.
- Trajectory Generation: O(|T_pred|) linear in prediction horizon.
Independent per-user computation enables parallel execution across multiple CPU cores without coordination overhead. In practice, predictions for all target users can be computed in parallel batches by dividing the user pool across processes.
Cross-city generalization
The algorithm made no city-specific adaptations across four metropolitan areas with different urban structures, densities, and mobility patterns. It relied on the similarity principle: within each city's user pool, find users with similar patterns and blend their behaviors. City-specific traits (grid vs. organic layout, public transit, density) show up through the patterns of real users instead of explicit modeling.
Evaluation and results
The competition's primary metric, GEO-BLEU, measures spatial n-gram similarity between predicted and actual trajectories with geometric mean aggregation:
GEO-BLEU similarity heatmap showing user trajectory similarity patterns on day 1 of the baseline period
| City | GEO-BLEU Score |
|---|---|
| City C | 0.03575 |
| City D | 0.03454 |
| City B | 0.02319 |
| City A | 0.01710 |
Performance variance across cities reflects differences in urban structure and data completeness. The algorithm demonstrated robust generalization without city-specific retraining, achieving comparable scores across all four metropolitan areas.
GEO-BLEU heatmap from day 41 (prediction period) showing similarity evolution during the target period
Interpretability
Unlike deep learning approaches where prediction provenance is opaque, this algorithm explicitly reports:
- Which similar users were selected and their DTW similarity scores
- The quality of the candidate selection (did we find high-quality matches or only weak ones?)
- The fitted GMM parameters (means and covariances of the mixture components)
- Which mixture component each time step's sample was drawn from
This transparency supports diagnostics and debugging. If predictions are poor, you can check whether the cause is weak candidate selection, poor pattern quality, or the generation step.