Abstract
Urban computing relies heavily on understanding city-wide mobility, yet raw taxi GPS data often lacks status labels (occupied, cruising, or parked). This report details a hybrid machine learning framework developed by Microsoft Research Asia to fill this data gap. By integrating a local Decision Tree classifier with a global Hidden Semi-Markov Model (HSMM), the system effectively infers taxi status from low-frequency GPS sampling (e.g., one point per minute). The approach incorporates road network data, points of interest (POIs), and historical travel patterns to achieve significantly higher accuracy than standard sequence models.
Introduction
Transportation engineers and urban planners utilize taxi trajectories to model traffic flow and city dynamics. However, most taxi fleets do not link their meters to GPS systems, resulting in "blind" trajectories. A taxi moving slowly could be stuck in a traffic jam while carrying a passenger, or it could be crawling along a curb searching for a fare. Distinguishing these states is challenging due to low sampling rates, data sparsity, and the inherent uncertainty of driver behavior.
Methodology
The proposed framework operates in three distinct phases:
1. Parking Detection
Before analyzing movement, the system identifies "parked" states. It employs a density-based clustering algorithm to locate areas where a taxi lingers. To distinguish actual parking from traffic stops (e.g., red lights or congestion), a supervised filter is applied. A key feature in this phase is the Minimum Bounding Ratio (MBR), which compares the area of the GPS cluster to the area of the nearest road segment.
2. Local Probabilistic Classification
For moving segments, 26 features are extracted, including trajectory patterns, road types, nearby POIs (like hotels or malls), and historical occupancy rates for specific road segments. A C4.5 Decision Tree is used to generate a probability of occupancy for each point. Interestingly, the Decision Tree outperformed more complex models like Conditional Random Fields (CRFs) due to its superior ability to find non-linear thresholds in features like road level and distance.
3. Global Smoothing via HSMM
The core innovation is the use of a Hidden Semi-Markov Model (HSMM) for global inference. Unlike standard HMMs that only consider point-to-point transitions, the HSMM explicitly models the duration of a state. Since taxi trips and cruising periods have characteristic temporal rhythms (e.g., trips often last ~10 minutes), the HSMM prevents unrealistic "flickering" between states and provides a more coherent global trajectory.
Experimental Evaluation
The model was validated using a massive dataset from Beijing, comprising 8,000 taxis. A subset of 600 taxis over 1.5 months (161,349 trajectories) provided the ground truth via meter-linked GPS data.
Key Results: * Parking Accuracy: The parking detection algorithm achieved an F1-measure of 0.858, successfully filtering out congestion-related stops. * Model Performance: The DT+HSMM combination consistently outperformed HMM and CRF baselines. The model's accuracy stabilized when the maximum duration parameter was set to $\ge 20$ minutes, confirming the importance of long-term temporal modeling. * Overall Accuracy: Despite the sparse 1-minute sampling rate, the system achieved an overall accuracy of approximately 72.1% across the three statuses (Occupied, Non-Occupied, Parked).
Conclusion
This research demonstrates that taxi status can be accurately inferred from sparse GPS data by combining local feature engineering with global duration-aware sequence modeling. By leveraging urban context—such as road levels and POIs—the framework provides a scalable solution for enriching "blind" taxi datasets. Future work will focus on handling irregular sampling frequencies and mining more granular driver activities, such as distinguishing between searching for passengers and personal breaks.
Summary updated