2. 中国科学院遥感与数字地球研究所, 北京 100101
2. Institute of Remote Sensing and Digital Earth, Chinese Academy of Sciences, Beijing 100101, China
随着城市快速发展,出行需求急剧增加,交通拥堵成为北京、上海等大都市发展所面临的主要挑战之一。先进的城市交通流诱导是防止和减轻交通阻塞的有效手段,而交通状况实时信息采集是交通诱导系统的基础[1]。基于感应线圈、摄像头等固定传感器的静态交通流监测网络因其建设和维护成本高,难以覆盖整个城市路网[2]。近年来,浮动车数据(floating car data,FCD)以采集成本低、覆盖范围广等优点,逐渐成为一种重要的交通流信息来源。轨迹地图匹配[3-8]等数据预处理技术的发展,也为基于海量浮动车数据的交通流状态监测与分析创造了基础条件。
道路交通流包括流量、密度和平均速度等参数,它们之间密切相关,已有学者基于FCD对各种交通流参数的估计方法进行了研究[9-10]。其中,交通流平均速度是最常用的参数,包括时间平均速度(time mean speed,TMS)和空间平均速度(space mean speed,SMS)两种计算方式[11],基于FCD的交通流速度估计包括曲线拟合、轨迹追踪[12-13]以及基于流体动力学和排队理论的估计[14-15]等方法。
浮动车渗透率是影响交通流估计精度的主要因素之一,它代表车流中浮动车的比例,渗透率越高,基于浮动车数据的交通流估计精度越高,国内外学者针对不同类型道路探讨了保障估计精度情况下的最低渗透率[16-20]。
除了交通流估计方法和样本渗透率,若要将浮动车数据应用于全局城市路网的交通流检测,还需考虑由样本分布不均导致的时空稀疏性问题。目前,针对浮动车数据稀疏性问题的讨论较少,文献[21]通过历史数据估计缺失交通流状态,但这只考虑了交通流的周期性特征;文献[9]根据路网拓扑结构分析路段间交通流关系,从而估计未被传感器覆盖路段的交通流状况;文献[22]验证了交通流量数据在经过K-SVD方法训练过的字典上能够实现稀疏表达,文献[23]提出了一种基于压缩感知的估计算法,对交通流速度稀疏矩阵中的缺失项进行估计,然而该算法是基于全局时空范围的交通状况进行内部结构分析,只适用于离线应用。
为解决基于浮动车数据稀疏性问题,本文通过分析路网交通流速度时空特征,构建一种基于朴素贝叶斯法的估计模型,对路网中未被样本覆盖路段交通流速度进行估计。时间特征包括两个方面,一是路网交通状况随时间周期变化的特点,二是道路交通状况相邻时段间的转变特点。空间特征主要根据路段间的交通流空间关系进行分析,由于影响城市道路交通的因素复杂多元,路段间的交通流空间关系难以采用传统欧氏距离或拓扑关系的方式度量,因此,本文以大量动态数据为基础,实时地提取路段间交通流空间关系,也称作路段间交通流相似关系。
1 缺失交通流速度估计 1.1 路网交通流速度矩阵本文主要考虑交通流速度参数,时空维度上的城市路网交通通过一个交通流速度矩阵表示
式中,连续时间被间隔Δt划分为t个离散的时间片段(简称“时段”);vrt表示路段r在t时段的交通流速度。由于本文主要关注样本缺失路段的交通流速度估计,为简化计算,直接经过目标路段浮动车的平均速度作为路段交通流速度,路段r在t时段的交通流速度通过式(2)计算
式中,为便于分析,vrt取值为1~100 km/h间的整数,当vrt超过100 km/h时,按100 km/h计算;vi为第i个样本速度;M为样本量,当M为0时,路段交通流速度缺失。本文主要目的就是对路网中缺失的交通流速度进行实时估计。
1.2 路网交通流速度特征 1.2.1 时间特征由于城市基础设施、出行需求等因素一定时期内相对稳定,城市路网交通流速度表现出较强的周期性特点,如图 1所示,工作日期间城市路网整体交通流平均速度曲线大致相同。数据统计显示,对于路段r,t时段路段速度取值为v的概率P(vt)以及相邻时段的速度转移的概率P(vt-1|vt)也存在明显的周期性特点。
1.2.2 路段交通流相似关系
同一时段,路段交通状况的空间特征也是交通流速度估计的重要依据。在一些研究认为路段间交通状况符合邻近性原则,相邻路段的交通状况关系密切[9, 24],然而,通过大量数据分析发现,这种假设并不准确。文献[25]根据路段交通流相似性进行路段划分,为路网交通特征分析提供了一种有效途径。本文在此基础上进行扩展,以大量历史浮动车数据为基础,对各时段路网的交通流进行分析,挖掘频繁出现的交通流相似关系,构建各路段的交通流相似集,用于样本缺失路段的交通流速度估计。所有与路段i的交通流特征相似度较高的路段形成的集合称为路段交通流相似集(简称“相似集”),可以表示为
式中,Si为路段i的相似集;R为路网所有路段集合;sij=1表示路段i和j交通流特征相似。一般可以通过聚类方法获取路网中所有路段的相似集,但城市路段数量庞大,传统聚类方法(例如k-mean聚类、谱聚类等)的矩阵运算开销巨大。为简化计算,本文先采用等量划分的方式对交通流速度进行初步分类,交通流速度所属类型可表示为
式中,vrt为路段r在t时段的交通流速度;Δv为划分间隔,Δv越小,分类越多,Δv最小值设置为1 km/h。由于不同等级的道路速度设计不同,有必要根据道路等级进一步分类,得到路网在t时段的交通流分类集合,并表示为
式中,cij为一个分类集合,其中所有路段的交通流速度满足class(v)=i,且路段所属的道路等级为j。为寻找具有周期性特征的分类集合,选取D个工作日的历史数据进行频繁模式挖掘,所有集合可以通过二维矩阵表示
式中,Cdt表示第d天t时段的分类集合,需要针对每一列进行频繁模式挖掘,得到每个时段的频繁项集。通过一个指示函数表示集合c是否出现在C中
路段集c在D个工作日出现的频度记为freq
式中,CL是矩阵M中的一列,表示多个工作日某一时段的所有分类集合。路段集合c是频繁项集的条件为,freq(c, CL)不小于最小频度freqmin。路段数量较大,不宜采用传统频繁模式挖掘算法(例如Apriori),本文采用一种基于交集运算的算法。假设2个工作日对应的相似集为C1和C2,则两者交集为所有子集的交集所组成的集合
式中,|c|是路段集合c中的路段数量,由于只有单个路段的集合没有实际意义,交集运算中舍弃只含一个元素的集合。基于交集构建获取频繁子集的递归公式
式中,CL是矩阵M中的任意列;C为CL中任意元素;当CL中只有一个元素C1时,Freq(CL)=C1。找出D个工作日中,出现频度大于等于freqmin的频繁项集可以转换为组合问题,从CL中选出i个元素形成组合CLi,所有组合形成一个集合
在交集和组合运算中,频度小的集合一定会包含频度高的集合,因此,在式(11)中,只需要考虑满足最小频繁度的最小元素个数[D·freqmin],则CL的频繁项集可以通过式(12)求得
对矩阵M的所有列,进行频繁集运算,得到每个时段的频繁项集合F={Ft|t=1,2,…,T},遍历F得到每个路段在每个时段的相似集,Srt表示路段r在t时段的相似集。根据观察,虽然Δv越小,目标路段与相似集中路段的交通状况相似度越高,但部分路段可能无法找到相似集。因此,本文采用不同的划分间隔Δv,为每个路段提供多个相似集,Srt(Δv)为路段r在t时段的相似集,当路段无法找到较小Δv对应的相似集时,则采用较大Δv对应的相似集。
1.3 估计模型将样本缺失路段的交通流速度估计看作多类分类问题,采用一种基于朴素贝叶斯法的估计模型。朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法[26]。将1.2节讨论的路网交通特征应用于模型的特征变量设计,输入特征包括前一时段路段交通流速度vp和当前时段目标路段相似集中路段的平均交通流速度vs,输出特征为路段当前时段的交通流速度v,3个速度特征取值为1~100 km/h间的整数,取值集合记为V。对路网每个时段的交通流相似关系都进行独立分析,当前时段的相似集与目标路段前一时段的交通流速度没有直接联系,因此,可以假设两个特征条件独立,则t时段特征间的条件概率公式为
朴素贝叶斯法分类时,给定输入(vp, vs),计算后验概率分布Pt(v|vp, vs),将后验概率最大的类作为(vp, vs)的类输出。后验概率计算根据贝叶斯定理进行
将式(13)代入式(14),有
由于式(15)中分母对所有v都是相同的,所以t时段交通流速度的估计公式可以表示为
在初始时段,即t=1时,无法获取vp,此时假设模型只有一个输入特征vs,则最终的估计公式为
对于参数学习,贝叶斯估计对极大似然估计进行改进,避免估计的概率值为0的情况。条件概率的贝叶斯估计为
式中,Nt为t时段的样本总量;当第i条路段交通流速度vi=v,且其对应的相似集中路段的平均交通流速度为vs时,指示函数I(vs, vi=v)=1,否则,I(vs, vi=v)=0;当第i条路段交通流速度vi=v时,指示函数I(vi=v)=1,否则,I(vi=v)=0;当第i条路段交通流速度vi=v,且其对应的前一时段路段交通流速度为vp时,指示函数I(vp, vi=v)=1,否则,I(vp, vi=v)=0;|V|为速度取值数量;λ≥0,常取λ=1,这时λ称为拉普拉斯平滑。同样,先验概率的贝叶斯估计为
研究空间范围为北京市六环以内区域,覆盖路段约12万条,包括快速路、主干路、次干路和支路等。时间区间为6:00-24:00,被Δt=10 min划分为108个时段。浮动车样本采用北京市2012年出租车轨迹数据,记录了约1.2万辆出租车一个月内的运行状态,包括时间、位置、航向角、车速等信息,样本总量约8亿条,采样间隔为1~120 s。设路段样本覆盖率为x/108,其中,x为目标路段被样本覆盖的时段数,统计结果显示,快速路样本覆盖率为42.57%,主干路样本覆盖率为57.26%,次干路样本覆盖率为34.77%,而支路和街坊路的样本覆盖率不足10%(如图 2所示)。由此可见,样本稀疏性是基于浮动车数据进行路网交通流速度估计亟待解决的难题。
2.2 模型实现
模型实现包括相似集挖掘和参数估计两部分,为方便观察,从路网中筛选出样本覆盖情况较好的16 469路段,确保每天的样本分类都能找到所有的路段。选取5个连续工作日的历史数据进行模型学习,频繁项的最小频度freqmin设置为80%。为平衡相似集精度与覆盖率之间的关系,进行分类和频繁模式挖掘时,采取5个分类策略,Δv分别设置为1~5 km/h的整数。分类时划分间隔Δv越小,分类精度越高,但分类对于路段的覆盖率越低,如图 3所示,采用1 km/h进行分类时,相似集路段覆盖率在13.58%~25.89%之间,而采用5 km/h,覆盖率在88.96%~100%之间,这5种分类策略的协同应用基本满足模型的需求。
根据式(19)对各时段路段交通流速度的概率Pt(v)进行计算,结果如图 4所示,绝大多数交通流速度在80 km/h以下,速度概率在时间上呈“带状”分布,与城市路网整体交通流速度情况相符,例如早晚高峰时段,路段的交通流速度主要分布在10~30 km/h。速度概率分布“带”越窄,亮度越高,说明交通特征越明显,而在图 4中,虽然高概率分布“带”特征明显,但仍然存在一个低概率分布“带”,可能会影响估计的精度。
根据式(18)计算特征条件概率Pt(vp|v),结果如图 5所示,概率分布特征明显,高概率主要集中在对角线上,说明多数情况下相邻时段间的交通流速度相近,前一时段的交通流速度对当前时段交通流速度的估计有较大参考价值。
根据式(18)计算特征条件概率Pt(vs|v),结果如图 6所示,相对Pt(vp|v)分布,Pt(vs|v)沿对角线分布的特点更加明显,高概率分布更加集中,这主要是因为vs与v是完全的相似关系,而vp与v除了时间相邻,还存在状态转移关系。
2.3 模型应用效果
筛选部分路段进行试验,按照2.1节的方式统计,目标路段集合的整体样本覆盖率为58.78%,每个路段的有效样本覆盖率分布情况如图 7所示。
估计结果显示,模型能估计出92.55%的缺失状态,使路网交通状况覆盖率达到96.93%,每个路段的覆盖率分布情况如图 8所示,绝大多数路段交通状况覆盖率达到90%以上。
将估计前和估计后的交通流速度分布图(图 9、10)对比观察,估计前,路网中大量路段没有被样本覆盖,估计后,路网交通流状况分布图能够反映出清晰的实时交通流速度,只存在极少数状态缺失的路段,能更好地应用于交通系统。
排除原样本缺失情况,以有效样本为基础,从中随机剔除部分样本,形成覆盖率为10%~90%的多个试验用例。对比估计前后交通状况覆盖率,结果如图 11所示,当原始样本覆盖率只有40%时,估计后的交通状况覆盖率还能达到90%以上,说明模型能有效地估计出样本缺失路段的交通流速度。
试验对两种模型对比分析,模型1为2.3节提出的模型,模型2采用路段间的拓扑关系设计特征变量,将模型1中的vs替换为目标路段相邻路段集合对应的平均交通流速度va,va根据加权平均计算
式中,N为被样本覆盖的相邻路段数量;vi为第i个相邻路段的交通流速度;ri为第i个相邻路段交通流速度与目标路段交通流速度之间的相关系数。通过误差累计分布F(e)观察两个模型的估计精度,F(e)是误差小于或则等于e的估计值个数与总估计值个数的比值,误差e为估计值与观测值差的绝对值。如图 12所示,对于各样本覆盖率(20%、50%、80%),模型1的估计精度都远高于模型2,进一步说明,采用相似关系表达路网交通流特征更加有效。
基于朴素贝叶斯法的交通估计算法时间复杂度为O(|V|·n),其中n为被估计的状态数量,|V|=100,是速度可能的取值数量。试验中,模型基于Java平台实现,运行于四核CPU 2.2 GHz、内存8 GB的普通PC机上,其计算速度可以达到为每秒10 803次估计,由此判断,模型运算效率足以满足大都市(例如北京、上海等)实时路网交通监测的需求。
3 结 论浮动车数据各路段各时段的样本分布不均,有较强的时空稀疏性,在实际应用中需要对样本缺失路段的交通流状况进行估计。本文构建了基于朴素贝叶斯法的交通估计模型,实现对样本缺失路段交通流速度的实时估计,模型参数设计主要依据路网交通流速度的时间特征以及路段间交通流相似关系。试验结果表明,模型能有效地估计出样本缺失路段的交通流速度,在样本覆盖率只有40%的情况下,还能使估计结果中的交通状况覆盖率达到90%;在与基于拓扑关系的估计算法对比中,基于交通流相似关系的模型估计精度较高,进一步说明,相对传统的欧氏距离和拓扑关系,基于海量数据挖掘的路网交通流相似关系能更准确地表达路段间交通流空间关系;另外,基于朴素贝叶斯法的估计模型算法复杂度较低,运算效率较高,适用于实时交通应用。
[1] | 孙棣华, 董均宇, 廖孝勇. 基于GPS探测车的道路交通状态估计技术[J]. 计算机应用研究 , 2007 (2) : 243–245, 248. SUN Dihua, DONG Junyu, LIAO Xiaoyong. Traffic Parameter Estimation Based on GPS Equipped Probe Vehicles[J]. Application Research of Computers , 2007 (2) : 243 –245, 248. |
[2] | HERRERA J C, BAYEN A M. Traffic Flow Reconstruction Using Mobile Sensors and Loop Detector Data[C]//Proceedings of the TRB 87th Annual Meeting Compendium of Papers DVD. Washington, DC:Transportation Research Board, 2007. |
[3] | 王美玲, 程林. 浮动车地图匹配算法研究[J]. 测绘学报 , 2012, 41 (1) : 133–138. WANG Meiling, CHENG Lin. Study on Map-matching Algorithm for Floating Car[J]. Acta Geodaetica et Cartographica Sinica , 2012, 41 (1) : 133 –138. |
[4] | 唐进君, 刘芳. 基于路径预测的不确定性推理组合地图匹配算法[J]. 测绘学报 , 2010, 39 (5) : 546–550. TANG Jinjun, LIU Fang. A Driver Route Prediction Based Map-matching Algorithm Integrating Uncertain Reasoning[J]. Acta Geodaetica et Cartographica Sinica , 2010, 39 (5) : 546 –550. |
[5] | 李清泉, 黄练. 基于GPS轨迹数据的地图匹配算法[J]. 测绘学报 , 2010, 39 (2) : 207–212. LI Qingquan, HUANG Lian. A Map Matching Algorithm for GPS Tracking Data[J]. Acta Geodaetica et Cartographica Sinica , 2010, 39 (2) : 207 –212. |
[6] | 唐进君, 曹凯. 一种自适应轨迹曲线地图匹配算法[J]. 测绘学报 , 2008, 37 (3) : 308–315. TANG Jinjun, CAO Kai. An Adaptive Trajectory Curves Map-matching Algorithm[J]. Acta Geodaetica et Cartographica Sinica , 2008, 37 (3) : 308 –315. |
[7] | 苏洁, 周东方, 岳春生. GPS车辆导航中的实时地图匹配算法[J]. 测绘学报 , 2001, 30 (3) : 252–256. SU Jie, ZHOU Dongfang, YUE Chunsheng. Real-time Map-matching Algorithm in GPS Navigation System for Vehicles[J]. Acta Geodaetica et Cartographica Sinica , 2001, 30 (3) : 252 –256. |
[8] | 王晓蒙, 池天河, 林晖, 等. 一种面向海量浮动车数据的地图匹配方法[J]. 地球信息科学学报 , 2015, 17 (10) : 1143–1151. WANG Xiaomeng, CHI Tianhe, LIN Hui, et al. A Research of Map-matching Method for Massive Floating Car Data[J]. Journal of Geo-information Science , 2015, 17 (10) : 1143 –1151. |
[9] | FOWE A J, CHAN Yupo. A Microstate Spatial-inference Model for Network-traffic Estimation[J]. Transportation Research Part C:Emerging Technologies , 2013, 36 : 245 –260. DOI:10.1016/j.trc.2013.08.011 |
[10] | DARWISH T, ABU BAKAR K. Traffic Density Estimation in Vehicular ad Hoc Networks:A Review[J]. Ad Hoc Networks , 2015, 24 : 337 –351. DOI:10.1016/j.adhoc.2014.09.007 |
[11] | VAN LINT J W C. Reliable Travel Time Prediction for Freeways[D]. Delft:Delft University of Technology, 2004. |
[12] | KONG Qingjie, ZHAO Qiankun, WEI Chao, et al. Efficient Traffic State Estimation for Large-scale Urban Road Networks[J]. IEEE Transactions on Intelligent Transportation Systems , 2013, 14 (1) : 398 –407. DOI:10.1109/TITS.2012.2218237 |
[13] | BEJAN A I, GIBBENS R J. Evaluation of Velocity Fields via Sparse Bus Probe Data in Urban Areas[C]//Proceedings of the 201114th International IEEE Conference on Intelligent Transportation Systems (ITSC). Washington, DC:IEEE, 2011:746-753. |
[14] | HIRIBARREN G, HERRERA J C. Real Time Traffic States Estimation on Arterials Based on Trajectory Data[J]. Transportation Research Part B:Methodological , 2014, 69 : 19 –30. DOI:10.1016/j.trb.2014.07.003 |
[15] | CAO Peng, MIWA T, MORIKAWA T. Use of Probe Vehicle Data to Determine Joint Probability Distributions of Vehicle Location and Speed on an Arterial Road[J]. Transportation Research Record , 2014, 2421 : 103 –114. DOI:10.3141/2421-12 |
[16] | HERRERA J C, WORK D B, HERRING R, et al. Evaluation of Traffic Data Obtained via GPS-enabled Mobile Phones:The Mobile Century Field Experiment[J]. Transportation Research Part C:Emerging Technologies , 2010, 18 (4) : 568 –583. DOI:10.1016/j.trc.2009.10.006 |
[17] | DE FABRITⅡS C, RAGONA R, VALENTI G. Traffic Estimation and Prediction Based on Real Time Floating Car Data[C]//Proceedings of the 2008 11th International IEEE Conference on Intelligent Transportation Systems. Beijing:IEEE, 2008:197-203. |
[18] | BAR-GERA H. Evaluation of a Cellular Phone-based System for Measurements of Traffic Speeds and Travel Times:A Case Study from Israel[J]. Transportation Research Part C:Emerging Technologies , 2007, 15 (6) : 380 –391. DOI:10.1016/j.trc.2007.06.003 |
[19] | BREITENBERGER S, GRUEBER B, NEUHERZ M, et al. Traffic Information Potential and Necessary Penetration Rates[J]. Traffic Engineering & Control , 2004, 45 (11) : 396 –401. |
[20] | WANG Handong, YUE Yang, LI Qingquan. How Many Probe Vehicles Are Enough for Identifying Traffic Congestion?-A Study from a Streaming Data Perspective[J]. Frontiers of Earth Science , 2013, 7 (1) : 34 –42. DOI:10.1007/s11707-012-0343-x |
[21] | WANG Jiawei, WANG Yinsong, YUN Meiping, et al. Development of Urban Road Network Traffic State Dynamic Estimation Method[J]. Mathematical Problems in Engineering , 2015, 2015 : 714149 . |
[22] | 李清泉, 周尧, 乐阳, 等. 基于压缩传感的交通流量数据压缩方法[J]. 交通运输工程学报 , 2012, 12 (3) : 113–119, 126. LI Qingquan, ZHOU Yao, YUE Yang, et al. Compression Method of Traffic Flow Data Based on Compressed Sensing[J]. Journal of Traffic and Transportation Engineering , 2012, 12 (3) : 113 –119, 126. |
[23] | ZHU Yanmin, LI Zhi, ZHU Hongzi, et al. A Compressive Sensing Approach to Urban Traffic Estimation with Probe Vehicles[J]. IEEE Transactions on Mobile Computing , 2013, 12 (11) : 2289 –2302. DOI:10.1109/TMC.2012.205 |
[24] | HOFLEITNER A, HERRING R, ABBEEL P, et al. Learning the Dynamics of Arterial Traffic from Probe Data Using a Dynamic Bayesian Network[J]. IEEE Transactions on Intelligent Transportation Systems , 2012, 13 (4) : 1679 –1693. DOI:10.1109/TITS.2012.2200474 |
[25] | 张心哲, 关伟. 基于聚类分析的城市交通路段划分研究[J]. 交通运输系统工程与信息 , 2009, 9 (3) : 36–42. ZHANG Xinzhe, GUAN Wei. Division of Urban Traffic Road Section Based on Clustering Analysis[J]. Journal of Transportation Systems Engineering and Information Technology , 2009, 9 (3) : 36 –42. |
[26] | 李航. 统计学习方法[M]. 北京: 清华大学出版社, 2012 : 47 -53. LI Hang. Statistical Learning Method[M]. Beijing: Tsinghua University Press, 2012 : 47 -53. |