基于弱监督学习的低采样率GPS 轨迹旅行时间分布建模

随着物联网（IoT）技术的迅猛发展，许多在线网络应用程序（如谷歌地图和 优步）开始利用移动设备收集的轨迹数据来估算人们的出行时间。然而，由于网络 通信和手机电量等限制因素的存在，轨迹数据通常以较低的采样率进行收集。因 此，本研究旨在解决在这种稀疏环境中的旅行时间估计（TTE）和路线恢复问题。 在稀疏采样的情况下，连续采样的GPS 点之间的旅行时间和路线标签往往是不确 定的。我们将此问题视为一个不精确的监督问题，其中训练数据具有粗粒度标签， 并使用EM 算法来解决旅行时间估计和路径恢复的任务。我们认为这两个任务在 模型学习过程中是互补的：更精确的旅行时间估计可以带来更准确的路线推断，反 过来，更准确的路线推断也可以带来更好的旅行时间估计。基于这一观点，我们提 出了一个基于弱监督学习行程时间估计方法。该方法通过EM 算法的E 步骤，利 用弱监督来估计推断路线的旅行时间，并在M 步骤中根据稀疏轨迹来检索路线。 在验证了弱监督学习在稀疏环境中的有效性之后，我们进一步在只给定起点 和终点（Origin-Destination）的更具挑战性的场景中进行了验证。为了解决这个问 题，我们进一步提出了一个结合路网的弱监督算法，用于估算起点到终点的旅行 时间。具体来说，我们提出了一个旅行时间估计的多任务弱监督学习框架，用于推 断路段之间的转移概率，并同时推断路段和交叉路口的旅行时间。给定一个起点 和终点，转移概率被用于恢复最可能的路线。然后，旅行时间的输出等于该路径中 所有路段和交叉路口的旅行时间之和。我们提出了一种新的路径恢复函数，用于 迭代地最大化当前路径的共现概率，并最小化路径概率分布与路径估计损失的逆 分布之间的差异。此外，基于弱监督框架的期望对数似然函数被用于同时优化路 段和交叉路口的旅行时间。我们在西安和成都的大量真实滴滴出租车数据集上进 行了实验，实验结果证实了我们的方法在路线恢复和旅行时间估计方面的有效性。

[1] ARIDOR M, HANNAN L A. Traffic jam: a compendium of human diseases that affect intracellulartransport processes[J]. Traffic, 2000, 1(11): 836-851.
[2] COLEMAN D A. Replacement migration, or why everyone is going to have to live in Korea: afable for our times from the United Nations[J]. Philosophical Transactions of the Royal Societyof London. Series B: Biological Sciences, 2002, 357(1420): 583-598.
[3] ANTONIOU C, BALAKRISHNA R, KOUTSOPOULOS H N. A synthesis of emerging datacollection technologies and their impact on traffic management applications[J]. EuropeanTransport Research Review, 2011, 3: 139-148.
[4] LI Y, GUNOPULOS D, LU C, et al. Urban travel time prediction using a small number ofGPS floating cars[C]//Proceedings of the 25th ACM SIGSPATIAL International Conference onAdvances in Geographic Information Systems. 2017: 1-10.
[5] LEE W H, TSENG S S, TSAI S H. A knowledge based real-time travel time prediction systemfor urban network[J]. Expert systems with Applications, 2009, 36(3): 4239-4247.
[6] CHU L, OH S, RECKER W. Adaptive Kalman filter based freeway travel time estimation[C]//84th TRB Annual Meeting, Washington DC. 2005.
[7] MASIERO L P, CASANOVA M A, DE CARVALHO M T M. Travel time prediction usingmachine learning[C]//Proceedings of the 4th ACM SIGSPATIAL International Workshop onComputational Transportation Science. 2011: 34-38.
[8] SIRIPANPORNCHANA C, PANICHPAPIBOON S, CHAOVALIT P. Travel-time predictionwith deep learning[C]//2016 ieee region 10 conference (tencon). IEEE, 2016: 1859-1862.
[9] 陈立玮, 冯岩松, 赵东岩. 基于弱监督学习的海量网络数据关系抽取[J]. 计算机研究与发展, 2013, 50(9): 1825-1835.
[10] 伍星, 何中市, 黄永文. 基于弱监督学习的产品特征抽取[J]. 计算机工程, 2009, 35(13):199-201.
[11] 杨辉, 权冀川, 梁新宇, 等. 基于弱监督学习的目标检测研究进展[J]. 计算机工程与应用,2021, 57(16): 40-49.
[12] 孙美君, 吕超章, 韩亚洪, 等. 弱监督学习下的融合注意力机制的表面缺陷检测[J]. 计算机辅助设计与图形学学报, 2021, 33(6): 920-928.
[13] CHEN Y, BI J, WANG J Z. MILES: Multiple-instance learning via embedded instance selection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(12): 1931-1947.
[14] ZHOU Z H, SUN Y Y, LI Y F. Multi-instance learning by treating instances as non-iid samples[C]//Proceedings of the 26th annual international conference on machine learning. 2009: 1249-1256.
[15] CHEN L C, PAPANDREOU G, KOKKINOS I, et al. Deeplab: Semantic image segmentationwith deep convolutional nets, atrous convolution, and fully connected crfs[J]. IEEE transactionson pattern analysis and machine intelligence, 2017, 40(4): 834-848.
[16] FAN H, SU H, GUIBAS L J. A point set generation network for 3d object reconstructionfrom a single image[C]//Proceedings of the IEEE conference on computer vision and patternrecognition. 2017: 605-613.
[17] 李瑞敏, 陈熙怡. 多源数据融合的道路旅行时间估计方法研究[J]. 公路交通科技, 2014, 31(2): 99-103.
[18] 沈旅欧, 庄岩浩, 刘伟铭, 等. 基于修正算法的高速公路路段旅行时间估计[J]. 华南理工大学学报: 自然科学版, 2015(4): 20-27.
[19] 沙云飞, 曹瑾鑫, 史其信. 基于GPS 的路段旅行时间和速度估计算法研究[J]. ITS 通讯,2006, 8(1): 46-48.
[20] TIESYTE D, JENSEN C S. Similarity-based prediction of travel times for vehicles travelingon known routes[C]//Proceedings of the 16th ACM SIGSPATIAL international conference onAdvances in geographic information systems. 2008: 1-10.
[21] IDÉ T, SUGIYAMA M. Trajectory regression on road networks[C]//Proceedings of the AAAIConference on Artificial Intelligence: volume 25. 2011.
[22] HUNTER T, HOFLEITNER A, REILLY J, et al. Arriving on time: estimating travel timedistributions on large-scale road networks[A]. 2013.
[23] WU H, MAO J, SUN W, et al. Probabilistic robust route recovery with spatio-temporal dynamics[C]//Proceedings of the 22nd ACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining. 2016: 1915-1924.
[24] GANTI R, SRIVATSA M, ABDELZAHER T. On limits of travel time predictions: Insightsfrom a new york city case study[C]//2014 IEEE 34th International Conference on DistributedComputing Systems. IEEE, 2014: 166-175.
[25] WANG Y, ZHENG Y, XUE Y. Travel time estimation of a path using sparse trajectories[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery anddata mining. 2014: 25-34.
[26] WANG D, ZHANG J, CAO W, et al. When will you arrive? estimating travel time based ondeep neural networks[C]//Thirty-Second AAAI Conference on Artificial Intelligence. 2018.
[27] WANG Z, FU K, YE J. Learning to estimate the travel time[C]//Proceedings of the 24th ACMSIGKDD International Conference on Knowledge Discovery & Data Mining. 2018: 858-866.
[28] YANG T, TANG X, LIU R. Dual temporal gated multi-graph convolution network for taxidemand prediction[J]. Neural Computing and Applications, 2021: 1-16.
[29] PENG W, HONG X, CHEN H, et al. Learning graph convolutional network for skeleton-basedhuman action recognition by neural searching[C]//Proceedings of the AAAI Conference on ArtificialIntelligence: volume 34. 2020: 2669-2676.
[30] WU Z, PAN S, LONG G, et al. Connecting the dots: Multivariate time series forecasting withgraph neural networks[C]//Proceedings of the 26th ACM SIGKDD International Conference onKnowledge Discovery & Data Mining. 2020: 753-763.
[31] JAIN A, ZAMIR A R, SAVARESE S, et al. Structural-rnn: Deep learning on spatio-temporalgraphs[C]//Proceedings of the ieee conference on computer vision and pattern recognition.2016: 5308-5317.
[32] YAN S, XIONG Y, LIN D. Spatial temporal graph convolutional networks for skeleton-basedaction recognition[C]//Thirty-second AAAI conference on artificial intelligence. 2018.
[33] LI Y, YU R, SHAHABI C, et al. Diffusion convolutional recurrent neural network: Data-driventraffic forecasting[A]. 2017.
[34] SEO Y, DEFFERRARD M, VANDERGHEYNST P, et al. Structured sequence modeling withgraph convolutional recurrent networks[C]//International Conference on Neural InformationProcessing. Springer, 2018: 362-373.
[35] YU B, YIN H, ZHU Z. Spatio-temporal graph convolutional networks: A deep learning frameworkfor traffic forecasting[A]. 2017.
[36] ZHANG J, SHI X, XIE J, et al. Gaan: Gated attention networks for learning on large andspatiotemporal graphs[A]. 2018.
[37] GUO S, LIN Y, FENG N, et al. Attention based spatial-temporal graph convolutional networksfor traffic flow forecasting[C]//Proceedings of the AAAI Conference on Artificial Intelligence:volume 33. 2019: 922-929.
[38] BAI L, YAO L, LI C, et al. Adaptive graph convolutional recurrent network for traffic forecasting[J]. Advances in neural information processing systems, 2020, 33: 17804-17815.
[39] LIN H, GAO Z, XU Y, et al. Conditional local convolution for spatio-temporal meteorologicalforecasting[A]. 2021: arXiv-2101.
[40] 王楠, 王勇峰, 刘积仁. 一个基于位置点匹配的地图匹配算法[J]. 东北大学学报(自然科学版), 1999, 20(4): 344.
[41] 李清泉, 黄练. 基于GPS 轨迹数据的地图匹配算法[J]. 测绘学报, 2010, 39(2): 0.
[42] 苏洁, 周东方, 岳春生. GPS 车辆导航中的实时地图匹配算法[J]. 测绘学报, 2001, 30(3):252-256.
[43] 王美玲, 程林. 浮动车地图匹配算法研究[J]. 测绘学报, 2012, 41(1): 133.
[44] RAHMANI M, KOUTSOPOULOS H N. Path inference of low-frequency GPS probes for urbannetworks[C]//2012 15th International IEEE Conference on Intelligent Transportation Systems.IEEE, 2012: 1698-1701.
[45] RAHMANI M, KOUTSOPOULOS H N. Path inference from sparse floating car data for urbannetworks[J]. Transportation Research Part C: Emerging Technologies, 2013, 30: 41-54.
[46] ZHENG Y, QUDDUS M A. Weight-based shortest-path aided map-matching algorithm forlow-frequency positioning data[R]. 2011.
[47] LOU Y, ZHANG C, ZHENG Y, et al. Map-matching for low-sampling-rate GPS trajectories[C]//Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographicinformation systems. 2009: 352-361.
[48] JAGADEESH G R, SRIKANTHAN T. Robust real-time route inference from sparse vehicleposition data[C]//17th International IEEE Conference on Intelligent Transportation Systems(ITSC). IEEE, 2014: 296-301.
[49] LIAO C, LU J, CHEN H. Synthesizing routes for low sampling trajectories with absorbingMarkov chains[C]//International Conference on Web-Age Information Management. Springer,2011: 614-626.
[50] SU H, ZHENG K, HUANG J, et al. Calibrating trajectory data for spatio-temporal similarityanalysis[J]. The VLDB Journal, 2015, 24(1): 93-116.
[51] ZHENG K, ZHENG Y, XIE X, et al. Reducing uncertainty of low-sampling-rate trajectories[C]//2012 IEEE 28th international conference on data engineering. IEEE, 2012: 1144-1155.
[52] REN H, RUAN S, LI Y, et al. MTrajRec: Map-Constrained Trajectory Recovery via Seq2SeqMulti-task Learning[C]//Proceedings of the 27th ACM SIGKDD Conference on KnowledgeDiscovery & Data Mining. 2021: 1410-1419.
[53] SHAO K, WANG K, CHEN L, et al. Estimation of Urban Travel Time with Sparse TrafficSurveillance Data[C]//Proceedings of the 2020 4th High Performance Computing and ClusterTechnologies Conference & 2020 3rd International Conference on Big Data and Artificial Intelligence.2020: 218-223.
[54] MIL S, PIANTANAKULCHAI M. Modified Bayesian data fusion model for travel time estimationconsidering spurious data and traffic conditions[J]. Applied Soft Computing, 2018, 72:65-78.
[55] ZHANG Y, CHAROENPHAKDEE N, WU Z, et al. Learning from aggregate observations[A].2020.
[56] DUFRESNE D. Sums of lognormals[C]//Actuarial Research Conference. 2008: 1-6.
[57] CORDONNIER J B, LOUKAS A. Extrapolating paths with graph neural networks[A]. 2019.
[58] ZHOU Z H. A brief introduction to weakly supervised learning[J]. National science review,2018, 5(1): 44-53.
[59] DIETTERICH T G, LATHROP R H, LOZANO-PÉREZ T. Solving the multiple instance problemwith axis-parallel rectangles[J]. Artificial intelligence, 1997, 89(1-2): 31-71.
[60] RICHARDSON A, TAYLOR M. Travel time variability on commuter journeys[J]. High SpeedGround Transportation Journal, 1978, 12(1).
[61] RAKHA H A, EL-SHAWARBY I, ARAFEH M, et al. Estimating path travel-time reliability[C]//2006 IEEE Intelligent Transportation Systems Conference. IEEE, 2006: 236-241.
[62] AREZOUMANDI M. Estimation of travel time reliability for freeways using mean and standarddeviation of travel time[J]. Journal of Transportation Systems Engineering and InformationTechnology, 2011, 11(6): 74-84.
[63] CARBONNEAU M A, CHEPLYGINA V, GRANGER E, et al. Multiple instance learning: Asurvey of problem characteristics and applications[J]. Pattern Recognition, 2018, 77: 329-353.
[64] YEN J Y. An algorithm for finding shortest routes from all source nodes to a given destinationin general networks[J]. Quarterly of applied mathematics, 1970, 27(4): 526-530.
[65] LI X, CONG G, SUN A, et al. Learning travel time distributions with deep generative model[M]//The World Wide Web Conference. 2019: 1017-1027.
[66] LIU Z, WU Z, WANG M, et al. Multi-View Spatial-Temporal Model for Travel Time Estimation[C]//Proceedings of the 29th International Conference on Advances in Geographic InformationSystems. 2021: 646-649.
[67] LI Y, FU K, WANG Z, et al. Multi-task representation learning for travel time estimation[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery &Data Mining. 2018: 1695-1704.
[68] FANG X, HUANG J, WANG F, et al. Constgat: Contextual spatial-temporal graph attentionnetwork for travel time estimation at baidu maps[C]//Proceedings of the 26th ACM SIGKDDInternational Conference on Knowledge Discovery & Data Mining. 2020: 2697-2705.
[69] ZHAO L, SONG Y, ZHANG C, et al. T-gcn: A temporal graph convolutional network fortraffic prediction[J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 21(9):3848-3858.
[70] KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[A]. 2016.
[71] VELIČKOVIĆ P, CUCURULL G, CASANOVA A, et al. Graph attention networks[A]. 2017.
[72] YUN S, JEONG M, KIM R, et al. Graph transformer networks[J]. Advances in Neural InformationProcessing Systems, 2019, 32: 11983-11993.
[73] JIN G, YAN H, LI F, et al. Spatial-Temporal Dual Graph Neural Networks for Travel TimeEstimation[A]. 2021.
[74] JAMES J. Citywide Estimation of Travel Time Distributions with Bayesian Deep Graph Learning[J]. IEEE Transactions on Knowledge and Data Engineering, 2021.
[75] GAL Y, GHAHRAMANI Z. A theoretically grounded application of dropout in recurrent neuralnetworks[J]. Advances in neural information processing systems, 2016, 29.
[76] HAKLAY M, WEBER P. Openstreetmap: User-generated street maps[J]. IEEE Pervasivecomputing, 2008, 7(4): 12-18.
[77] YANG C, GIDOFALVI G. Fast map matching, an algorithm integrating hidden Markov modelwith precomputation[J]. International Journal of Geographical Information Science, 2018, 32(3): 547-570.
[78] WANG H, TANG X, KUO Y H, et al. A simple baseline for travel time estimation using largescaletrip data[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2019, 10(2): 1-22.
[79] FRIEDMAN J H. Greedy function approximation: a gradient boosting machine[J]. Annals ofstatistics, 2001: 1189-1232.
[80] JINDAL I, CHEN X, NOKLEBY M, et al. A unified neural network approach for estimatingtravel time and distance for a taxi trip[A]. 2017.
[81] LI M, AHMED A, SMOLA A J. Inferring movement trajectories from GPS snippets[C]//Proceedings of the Eighth ACM International Conference on Web Search and Data Mining.2015: 325-334.