基于隐马尔科夫模型和动态规划的手机数据移动轨迹匹配
|
摘要
针对手机数据属性信息少、时空采样率较低、采样不均匀、定位精度低的特点,该文提出了一种基于隐马尔科夫模型和动态规划的移动轨迹匹配方法(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.
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.
引文
[1] LOU Y,ZHANG C,ZHENG Y,et al.Map-matching for low-sampling-rate GPS trajectories[A].Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].New York:ACM,2009.352-361.
[2] REN M,KARIMI H A.A hidden Markov model-based map-matching algorithm for wheelchair navigation[J].Journal of Navigation,2009,62(3):383-395.
[3] 王晓蒙,池天河,林晖,等.一种面向海量浮动车数据的地图匹配方法[J].地球信息科学学报,2015,17(10):1143-1151.
[4] ALY H,YOUSSEF M.SemMatch:Road semantics-based accurate map matching for challenging positioning data[A].Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].New York:ACM,2015.1-10.
[5] HASHEMI M,KARIMI H A.A critical review of real-time map-matching algorithms:Current issues and future directions[J].Computers,Environment and Urban Systems,2014,48:153-165.
[6] 陶华超,马林兵,魏慧丽,等.一种基于格网划分的浮动车数据自适应地图匹配方法研究[J].地理与地理信息科学,2015,31(3):22-25.
[7] ERICSSON.Ericsson Mobility Report[EB/OL].https://www.ericsson.com/assets/local/mobility-report/documents/2017/ericsson- mobility-report-june-2017.pdf,2017-09-01.
[8] GONZALEZ M C,HIDALGO C A,BARABASI A L.Understanding individual human mobility patterns[J].Nature,2008,453(7196):779-782.
[9] SONG C,KOREN T,WANG P,et al.Modelling the scaling properties of human mobility[J].Nature Physics,2010,6(10):818-823.
[10] 吴健生,黄力,刘瑜,等.基于手机基站数据的城市交通流量模拟[J].地理学报,2012,67(12):1657-1665.
[11] CHANG H C,CHEN C H,LIN B Y,et al.Traffic information estimation using periodic location update events[J].International Journal of Innovative Computing,Information and Control,2013,9:2031-2041.
[12] GAO H,LIU F.Estimating freeway traffic measures from mobile phone location data[J].European Journal of Operational Research,2013,229(1):252-260.
[13] WANG J,RAGHAVAN V,SONG X.Estimating traffic speed using cellular phone data[J].International Journal of Geoinformatics,2015,11(3):9-16.
[14] YUAN Y,RAUBAL M.Analyzing the distribution of human activity space from mobile phone usage:An individual and urban-oriented study[J].International Journal of Geographical Information Science,2016,30(8):1594-1621.
[15] ZHAO Z,SHAW S L,XU Y,et al.Understanding the bias of call detail records in human mobility research[J].International Journal of Geographical Information Science,2016,30(9):1738-1762.
[16] LEE S,LIM J,PARK J,et al.Next place prediction based on spatiotemporal pattern mining of mobile device logs[J].Sensors,2016,16(2):145.
[17] 何兆成,陈展球,范秋明,等.基于手机基站数据的混合地图匹配算法研究[J].交通运输系统工程与信息,2014,14(3):34-42.
[18] 万家欢,万玮,陈秀万,等.一种适用于手机基站定位的地图匹配方法[J].测绘科学,2014,39(1):114-116.
[19] TETTAMANTI T,DEMETER H,VARGA I.Route choice estimation based on cellular signaling data[J].Acta Polytechnica Hungarica,2012,9(4):207-220.
[20] SCHULZE G,HORN C,KERN R.Map-matching cell phone trajectories of low spatial and temporal accuracy[A].Proceedings of the 2015 IEEE 18th International Conference on Intelligent Transportation Systems (ITSC)[C].Washington:IEEE Computer Society,2015.2707-2714.
[21] ASGARI F,SULTAN A,XIONG H,et al.CT-Mapper:Mapping sparse multimodal cellular trajectories using a multilayer transportation network[J].Computer Communications,2016,95:69-81.
[22] ALGIZAWY E,OGAWA T,EL-MAHDY A.Real-time large-scale map matching using mobile phone data[J].ACM Trans.Knowl.Discov.Data,2017,11(4):1-38.
[23] 张鹏飞,申彦明.基于手机位置信息的地图匹配算法[J].计算机应用,2015,35(S2):294-297.
[2] REN M,KARIMI H A.A hidden Markov model-based map-matching algorithm for wheelchair navigation[J].Journal of Navigation,2009,62(3):383-395.
[3] 王晓蒙,池天河,林晖,等.一种面向海量浮动车数据的地图匹配方法[J].地球信息科学学报,2015,17(10):1143-1151.
[4] ALY H,YOUSSEF M.SemMatch:Road semantics-based accurate map matching for challenging positioning data[A].Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].New York:ACM,2015.1-10.
[5] HASHEMI M,KARIMI H A.A critical review of real-time map-matching algorithms:Current issues and future directions[J].Computers,Environment and Urban Systems,2014,48:153-165.
[6] 陶华超,马林兵,魏慧丽,等.一种基于格网划分的浮动车数据自适应地图匹配方法研究[J].地理与地理信息科学,2015,31(3):22-25.
[7] ERICSSON.Ericsson Mobility Report[EB/OL].https://www.ericsson.com/assets/local/mobility-report/documents/2017/ericsson- mobility-report-june-2017.pdf,2017-09-01.
[8] GONZALEZ M C,HIDALGO C A,BARABASI A L.Understanding individual human mobility patterns[J].Nature,2008,453(7196):779-782.
[9] SONG C,KOREN T,WANG P,et al.Modelling the scaling properties of human mobility[J].Nature Physics,2010,6(10):818-823.
[10] 吴健生,黄力,刘瑜,等.基于手机基站数据的城市交通流量模拟[J].地理学报,2012,67(12):1657-1665.
[11] CHANG H C,CHEN C H,LIN B Y,et al.Traffic information estimation using periodic location update events[J].International Journal of Innovative Computing,Information and Control,2013,9:2031-2041.
[12] GAO H,LIU F.Estimating freeway traffic measures from mobile phone location data[J].European Journal of Operational Research,2013,229(1):252-260.
[13] WANG J,RAGHAVAN V,SONG X.Estimating traffic speed using cellular phone data[J].International Journal of Geoinformatics,2015,11(3):9-16.
[14] YUAN Y,RAUBAL M.Analyzing the distribution of human activity space from mobile phone usage:An individual and urban-oriented study[J].International Journal of Geographical Information Science,2016,30(8):1594-1621.
[15] ZHAO Z,SHAW S L,XU Y,et al.Understanding the bias of call detail records in human mobility research[J].International Journal of Geographical Information Science,2016,30(9):1738-1762.
[16] LEE S,LIM J,PARK J,et al.Next place prediction based on spatiotemporal pattern mining of mobile device logs[J].Sensors,2016,16(2):145.
[17] 何兆成,陈展球,范秋明,等.基于手机基站数据的混合地图匹配算法研究[J].交通运输系统工程与信息,2014,14(3):34-42.
[18] 万家欢,万玮,陈秀万,等.一种适用于手机基站定位的地图匹配方法[J].测绘科学,2014,39(1):114-116.
[19] TETTAMANTI T,DEMETER H,VARGA I.Route choice estimation based on cellular signaling data[J].Acta Polytechnica Hungarica,2012,9(4):207-220.
[20] SCHULZE G,HORN C,KERN R.Map-matching cell phone trajectories of low spatial and temporal accuracy[A].Proceedings of the 2015 IEEE 18th International Conference on Intelligent Transportation Systems (ITSC)[C].Washington:IEEE Computer Society,2015.2707-2714.
[21] ASGARI F,SULTAN A,XIONG H,et al.CT-Mapper:Mapping sparse multimodal cellular trajectories using a multilayer transportation network[J].Computer Communications,2016,95:69-81.
[22] ALGIZAWY E,OGAWA T,EL-MAHDY A.Real-time large-scale map matching using mobile phone data[J].ACM Trans.Knowl.Discov.Data,2017,11(4):1-38.
[23] 张鹏飞,申彦明.基于手机位置信息的地图匹配算法[J].计算机应用,2015,35(S2):294-297.