基于隐马尔科夫模型和动态规划的手机数据移动轨迹匹配

Hidden Markov Model and Dynamic Programming Based Map Matching Method for Mobile Trajectories Using Mobile Phone Data

针对手机数据属性信息少、时空采样率较低、采样不均匀、定位精度低的特点,该文提出了一种基于隐马尔科夫模型和动态规划的移动轨迹匹配方法(HMM-DP4MT)。该方法通过设定搜索半径以提高计算效率;结合轨迹距离和方向信息计算发射概率,基于不同搜索半径和定位标准差的匹配结果确定参数最优值;利用Manhattan距离代替欧氏距离,建立了融合最短路径距离和道路等级的转移概率模型,分析了道路等级约束对匹配结果的影响;基于动态规划搜索移动轨迹在拓扑路网中的全局最大似然匹配路径。利用同步采集的手机数据和GPS轨迹数据进行验证,结果表明,模型在简单路网区域和较复杂路网区域的精确率和召回率均高于85%,在极端复杂路网的精确率和召回率略低,但仍高于75%,能够满足交通应用对用户移动路径精确度的需求。

Matching the mobile trajectories of mobile phone users to road networks has been increasingly discovered in the traffic planning and management field.Considering incomplete attributes,sparse and irregular space-time sampling interval of mobile phone data,an approach based on hidden Markov model and dynamic programming is proposed to reconstruct high precision mobile paths using low precision mobile trajectories.First,search radius is applied to improve the computation performance,and the heading of trajectory is introduced to model the emission probability.The optimal radius and positioning standard error are well determined based on the F1 values of matching results using different combination of them.Then,Manhattan distance rather than Euclidean distance is used to compute the metric of point distance between two adjacent observations,and the road level is used to construct the state transition probability together with the shortest path distance.The effect of road level constraint is analyzed.A dynamic programming algorithm is followed to determine the best mobile path concerning maximum likelihood and road segment connectivity.The approach was tested using synchronously collected mobile phone data and GPS data,and the statistics show that the F1 score is over 90% in simple road networks area and the precision is more than 85% for simple routes and the precision for complex routes in complex road networks area is over 75%.The results show that the proposed model has a potential in traffic applications.