基于NB和DTW组合模型的稀疏浮动车数据填充

许伦辉，陈凯勋，郭雅婷

(华南理工大学土木与交通学院，广东 广州 510641)

浮动车数据(floating car data)是指从安装了GPS模块和无线通信模块的出租车、公交车等车辆接收到的数据，数据可包括时间、经纬度、车辆编号、运营状态、速度等信息。浮动车在20世纪90年代初开始投入使用，至今已经被广泛应用于交通领域。浮动车具有安装使用方便、维护成本低、覆盖面广、数据量大、精度高且实时性强的特点。文献[1]以浮动车数据为单一数据来源，提出了基于广义自适应平滑方法(GASM)的在线交通流速度估计模型。文献[2]引入置信点，提出了基于浮动车大数据的城市道路复杂度分析方法，并将该方法应用于广州市路网的复杂度分析。文献[3]提出了基于浮动车数据的城市不同等级道路通行能力评估方法，以较低的成本全面掌握城市交通状态在空间和时间上的不同特征。文献[4]利用道路实测数据建立了面向其应用的轻型车尾气排放实时测算模型，反映相同平均速度下的排放变化。文献[5]提出一种基于HMM(Hid-den Markov model)的地图匹配模型，并有效应用于海量浮动车数据地图匹配。但，以上研究多基于完善的浮动车数据，所提出的模型在浮动车数据缺失的情况下并不适用。近年来，各国学者也提出了一些解决浮动车数据稀疏问题的方法。文献[6]对比了PPCA和KPPCA方法，在适当考虑时空相关性的前提下，证明了KPPCA方法显著减少了对缺失数据估算的误差。文献[7]将季节性ARIMA交通流预测模型用于计算交通流数据的缺失，改善了对稀疏数据的不适应性。文献[8]将数据丢失事件看作是严重堵塞的情况下防止浮动车进入拥堵区域的状况，以此建立了一种基于新的交通流运行指标的时间序列相似性测量方法，并将此方法作为定义动态交通网络瓶颈的基础。文献[9]提出了一种估计和修正方法对行程时间进行估计与修正，得到了比改进的内插值法更接近实际的估计值。文献[10]建立了一个微仿真模型，该模型考虑了多个误差因素，通过对已有的稀疏浮动车数据驱动进行增强来估计交叉路口的信号相位和时间。文献[11]提出了一个三层神经网络模型，从浮动车的历史数据中获取各路段的时空特性，以时空特性作为输入，建立路段间的关联关系来估计稀疏路段的行程时间。文献[12]提出了一个朴素贝叶斯估计模型对缺失的路网交通流速度数据进行估计，在一定程度上缓解了数据稀疏带来的影响。

上述研究将偶然性和多发性的缺失统一为单一缺失状态进行填充，在实际的应用中会出现对特殊缺失情况的不适应，从而导致填补效率降低。例如：文献[12]所提出的模型在以时间维度的参数进行估计时，会因某个时段历史数据的大量缺失而对估计效果产生很大影响，导致模型不再适用于此类型缺失情况。基于对真实数据缺失情况的分析，本文将数据缺失类型归纳为偶然性缺失和多发性缺失，并针对两种数据缺失类型分别提出了基于NB和基于DTW的方法对路网交通流速度进行估计，以增强缺失数据的填充效果以及模型在实际应用中的适用性，降低路网浮动车数据缺失对实际应用和理论研究带来的影响。

1 稀疏数据填补方法

1.1 数据处理

将地图转化为路网并链接浮动车数据，选择适合区域进行数据提取和分析。对于实时交通系统，5 min是常用的信息发布时间间隔，本文以5 min作为数据采集间隔，将一天分为288个时段进行采集与处理分析。以一条浮动车数据为例，其数据格式为：

由表1可知，若该路段某一时段的浮动车数据丢失，速度数据也必然随之丢失。以缺失速度数据的路段ID代替交通流速度作为索引对数据进行实时监测，可简化缺失数据的查找过程且不影响数据的估计和填补工作，转化过程可用式(1)表示。

(1)

表1 浮动车数据格式Table 1 Format of floating car data

式中，Vt为路网交通流速度矩阵；vrc为道路r在c时段的交通流速度数据；Mt为路网各路段ID矩阵；mrc为道路r在c时段的路段ID，若数据缺失，则路段ID为0。

1.2 偶然性缺失填补方法

某一路段某一时刻的数据缺失具有偶然性，即历史数据中该路段这一时段的数据较为完整或仅有少量缺失，实时查找出的缺失是偶然发生的，这样的缺失多发生于较高等级的道路上。朴素贝叶斯分类方法简单、快速，对于此类数据缺失有较好的填充效果。

1.2.1 朴素贝叶斯模型 本文采用朴素贝叶斯方法对缺失数据进行估计，以平衡浮动车数据在空间分布不均的问题。此方法中，速度数据从0 km/h开始每5 km/h为一组分为20个速度组，大于100 km/h的计入第20组，将速度转化为20个离散值。用同一路段历史交通流速度vH(同一时段数据平均值)和同一路段上一时段交通流速度vS作为朴素贝叶斯分类方法的两个输入参数，估计当前时段当前路段的交通流速度v，公式如下：

(2)

式中，v为研究路段某时段的估计平均交通流速度；vH为同一路段历史交通流速度；vS为同一路段上一时段交通流速度；P(v)为研究路段某时段的估计平均交通流速度为v时的概率；P(v|vH,vS)为研究路段历史交通流速度为vH且上一时段交通流速度为vS的情况下，该路段当前时段估计平均交通流速度为v的概率；P(vH,vS|v)为研究路段估计平均交通流速度为v的情况下同一路段历史交通流速度为vH，且同一路段上一时段交通流速度为vS的概率。

由于两个引入的参数相互独立，即其上一时段交通流速度与历史交通流速度无直接联系，而上式中的分母∑v∈VP(vH,vS|v)P(v)对所有的v都相同，在比较后验概率时可以省略其进行计算，仅比较分子大小即可，所以在某时段缺失路段的交通流速度估计公式如下：

(3)

式中，P(vH|v)为研究路段估计平均交通流速度为v的情况下同一路段历史交通流速度为vH的概率；P(vS|v)为研究路段估计平均交通流速度为v的情况下同一路段上一时段交通流速度为vS的概率。各参数的计算过程如式(4)～(6)所示。

(4)

式(4)中，N为前30天内用于研究的所有速度数据量(第一个时段无vS，此时仅使用vH作为模型参数)；I(vi=v)为判断vi=v的布尔值，若vi=v则I(vi=v)=1，否则为0；I(vS,vi=v)为判断vi=v时vS单个统计量的布尔值，若vi=v时存在vS则I(vS,vi=v)=1，否则为0。

(5)

式(5)中，N为一天内用于研究的所有时段；I(vi=v)为判断vi=v的布尔值，若vi=v则I(vi=v)=1，否则为0；I(vH,vi=v)为判断vi=v时vH单个统计量的布尔值，若vi=v时存在vH则I(vH,vi=v)=1，否则为0。

(6)

式(6)中，N为前30天内用于研究的所有速度数据量；I(vi=v)为判断vi=v的布尔值，若vi=v则I(vi=v)=1，否则为0。将式(3)中的参数逐一计算后，代回式(3)中关联并遍历，可得到最终的估计结果。

1.2.2 朴素贝叶斯模型修正 假设选用参数vH、vS与速度v为正相关关系，并在模型可行性分析部分进行验证，此正相关关系使得速度相差较大的范围会出现P(vH|v)=0或P(vS|v)=0。为了避免出现概率值为0而影响最终估计结果的适应性和准确性，本文采用拉普拉斯修正(laplace correcting)对存在条件概率进行修正处理，如下式(7)～(9)所示。

(7)

(8)

(9)

式中，M为速度取值数量。

1.3 多发性缺失填补方法

某一路段某一时刻的数据缺失具有多发性，即历史数据中该路段这一时段的数据同样存在大量的缺失，这样的缺失多发生于低等级的道路上。这种情况下历史数据的估计价值不高，估计结果也有较大偏差甚至无法进行估计，朴素贝叶斯分类方法不再适用于这种缺失类型。近年来，已有学者将相似性度量的方法应用于信息补全、短时预测等研究。文献[13]提出了一种基于时间序列相似性搜索的短时交通流量预测方法，并以高速公路交通流量数据证明该方法的预测性能优于传统方法。在相似性度量中，DTW算法已在语音识别等领域得到广泛应用，此算法支持不同长度的时间序列的相似性度量，定义了序列间的对齐匹配关系[14]。

本文提出了基于DTW的相似度算法，求解匹配时累计差值最小的两路段所对应的规整函数，以寻找最相似路段，并对多发性的数据缺失进行填充。在寻找相似路段前，使用Daubechies(db4)小波获取用于比对的低频基波，4是小波的阶数，假设观测数据由2部分组成：

x(t)=s(t)+n(t)

(10)

式中，x(t)为观测值；s(t) 为真实值；n(t)为噪声，即n(t)=N(0,δ2)。

在小波分解后的低频信号中调取源路段，并标记为序列Q=q1,q2,…,qi,…,qn，其中n为调取到的该路段交通流速度数据总量。依次调取研究范围内其他所有路段的低频信号，记为CLINKID=c1,c2,…,cj,…,cm。其中，LINKID为当前调取的路段ID，m为调取到的其他路段的交通流数据总量。要计算每个搜寻路段与源路段序列的累计差值，首先要对序列实时匹配差值进行计算，具体公式如下：

(11)

式中，D[i,j]为序列匹配至qi，cj时的累计差值；d(qi-cj)为两数据点间的欧氏距离。当计算过程执行到序列的最后一个样本时，可得搜寻路段与源路段序列的累计差值：

DTW(Q,C)=D[n,m]

(12)

使用27°-45°-63°的局部路径约束，最佳的DTW路径会跳过序列中的离群点[15]，使得在计算时省掉了一些不需要计算的部分，如图1所示。计算完成后，比较累计差值可得出源路段的相似路段，相似路段的低频信号和随机噪声信号最终组成源路段的缺失时段数据，并可将估计的速度转化为对应的分组数值，填充入数据缺失部分。

图1 离群点示意Fig.1 Diagram of outliers

2 试验分析

选择深圳市南山区南海大道、滨海大道、创业路及后滨海路所框定的范围作为研究区域，如图2所示。所选区域覆盖了各等级道路包括快速路、主干路、次干路、支路。调取的浮动车样本数据均来自深圳市城市交通规划设计研究中心，数据时间范围为2018年5月1日至5月31日，样本总量约400万条，采样间隔为5 min。在Matlab平台下，对朴素贝叶斯算法的参数相关性和DTW算法的相似性进行评价，并对组合模型的效率和准确性进行了验证，并将最终的数据填充效果通过地图匹配展示到TransCAD、GIS等软件的路网分布图中。

图2 研究区域路网Fig.2 Network of study area

2.1 模型可行性分析

2.1.1 朴素贝叶斯参数评价 以选定范围内快速路的实时交通流速度v所处分组为横坐标，同一路段前一时段的交通流速度vS所处分组为纵坐标做相关性分析，结果如图3(a)所示。图3(a)中，两个变量呈现出高度的正相关性，说明相邻时段的速度相近甚至相等是大概率事件，用相邻时间段的路网交通流速度数据作为估计缺失数据的一个条件参数是有效且可行的。

图3 条件参数与交通流实时速度的相关性Fig.3 Relationship between vS /vH and v

以选定范围内快速路的实时交通流速度v所处分组为横坐标，同一时间段的历史速度vH所处分组为纵坐标做相关性分析，结果如图3(b)所示。图3(b)中，高概率色格仍然更多集中于对角线附近，虽与图3(a)相比更为分散，但仍能看出其正相关性。造成概率集中度不高的原因主要是历史数据提取量有限，仅引入前30天的历史数据进行相关条件的概率计算，对结果产生了轻度的干扰。扩大样本容量进行处理分析，可得出分布更加集中，更加接近正相关的图形。从图3(c)可以看出：同一路段前一时段的交通流速度vS与同一时间段的历史速度vH相互独立，没有相关关系。

2.1.2 DTW相似性评价 在使用DTW算法前，先调取所有路段前30天的历史交通流速度数据并对其进行小波滤波分析[16]，采用Db小波的4阶函数进行小波分解，将噪声部分表示为4组高频信号，对主流低频变化信号以及高频噪声信号进行重构，得到如图4所示的原始序列、低频序列、噪声序列。

图4 基于Db4小波函数的信号分解结果Fig.4 Signal decomposition result based on Db4 wavelet function

图4中，原始序列是低频序列和高频噪声序列叠加产生的信号图形。小波分解可看作一个信号滤波的去噪过程[17]，图中的高频信号在应用中可视为主要噪声源，其噪声序列由不相关的随机变量构成，具有很强的随机性。在去噪后，低频序列仍保留了原始序列的周期、振幅、变化趋势等特征，因此使用低频序列进行DTW的计算可以有效降低噪声干扰，得到更加平稳且符合实际规律的样本数据[18]。利用低频基波进行相似路段的比对，最终查找到与源路段相似的路段，取源路段和相似路段一周内速度变化进行对比分析，结果如图5所示。

图5 源路段与相似路段速度变化对比Fig.5 Comparison of the speed of the original and similar sections

图5(a)中，虚线表示源路段，实线表示源路段的相似路段。截取了历史数据中一周的数据进行对比分析，可以看出相似路段的变化趋势、振幅、周期等特性与源路段契合，但相似路段的可靠程度需将两路段的实时偏差、偏差的峰值、波动范围等特性进行进一步比对才能得到验证。图5(b)中以两路段对应样本的差值组成序列，从这个序列中可以看出两路段的相似程度较高，对应点位的偏差峰值不超过+8和-5，其他差值多在更小的固定范围内波动，得到稳定小范围差值的原因是在执行DTW算法时，超出指定范围的样本已在路径约束中作为离群点被剔除，因此以此方法筛选出的相似路段具有一定的可靠性。将研究范围全部源路段与相似路段进行比对，对应点位的偏差峰值不超过+10和-8，偏差峰值在+5和-5之间的点位占比83.67%。

2.2 模型评价

2.2.1 数据缺失程度划分 为量化偶然性缺失和多发性缺失的定义对模型的准确性及数据填补率的影响，本文将偶然性缺失分别定义为数据缺失程度小于10%、20%、30%、40%、50%，不满足偶然性缺失条件的则为多发性缺失。对定义后的缺失进行分别处理，用67.54%的低完整率源数据进行验证，考量模型使用后估计结果的效果以确定数据缺失性质的量化区分，具体对比如下图6所示。

图6 数据缺失定义对模型影响Fig.6 The impact of data loss definition on the model

图6(a)中，经过二次填充后路网交通流数据的完整程度均能达到90%以上，但第一次填充率的增大将会抑制第二次填充的效果。因为第一次填充越多，第二次填充的样本容量将会减小，找到相似路段的几率也会随之减小。由图6(b)可知，将过多数据定义为偶然缺失，使用朴素贝叶斯法或过度使用DTW法都会使模型的偏差值增大，即准确度降低。这是因为：朴素贝叶斯法采用过度缺失的历史数据作为条件参数，将会影响估计精度；而，DTW算法查找相似路段的方法采用欧氏距离，对噪声较为敏感，若对计算过程产生过度影响，可能会造成噪声干扰路段与非相似路段的混淆，导致计算结果产生偏差。以同样的方式对76.33%和85.10%完整率的源数据进行验证，结果表明：在数据修复的完整程度上各分组均表现良好；但，阈值定义为30%时，偏差值可维持在2.2 km/h ～ 2.5 km/h。因此，本文选择将数据缺失程度小于30%作为偶然性缺失的定义，在保证模型填充效率的同时提升模型估计结果的准确性。

2.2.2 模型对比 对三种模型进行对比分析。模型一采用文献[10]中的方法，仅使用朴素贝叶斯分类，以同路段的历史交通流速度和前一时刻交通流速度作为输入参数对缺失数据进行估计填充；模型二中路网数据缺失情况不做区分，统一采用DTW方法对偶然性缺失和多发性缺失同时进行填充；模型三为本文所采用的方法，先将数据缺失情况进行划分，再配合使用朴素贝叶斯方法和DTW方法分别对偶然性缺失和多发性缺失分别进行估计填充。

以路网30天内的前20天数据作为训练数据，后10天数据作为测试数据；测试数据将分别被视作缺失样本进行填充，并将真实数据与填充数据差值的绝对值作为本次填充的估计误差；每个测试数据的填充及误差计算过程相互独立互不影响，最终所有测试样本的平均绝对误差(MAD)和均方误差(MSE)的计算如式(13)～(14)所示：

(13)

(14)

式中，n为测试数据的样本总数；obs为真实数据的观测样本；pre为模型填充的估计样本。最终对模型的填充效果和估计准确度进行比较，结果如表2所示。

表2 三种模型效果比较Table 2 Comparison of three models

由上表可知，单独使用DTW算法的模型二的平均绝对误差和均方误差均较大，平均绝对误差超出了速度的一个组值范围；而，模型一和模型三的平均绝对误差均在一个组值的范围内。当误差在可接受范围内时，模型三的填充率比模型一的高出13.08%，填充效果有较显著的提升。因此，本文所提方法在保证估计结果准确性的同时大幅提升了缺失数据的填充率，相比于单一使用朴素贝叶斯方法或DTW方法的模型更为优化。在运行时间方面，DTW方法寻找相似路段的过程耗时较长，但此步骤可提前离线完成，组合模型实时计算的平均时长为15.6 s。

2.3 试验结果分析

以2017年5月31日第96时段(7∶55到8∶00)的数据进行模型的试验。数据填充前，路网交通流速度的原始分布如图7所示，虚线表示该时段路网处在数据缺失的状态，颜色由浅至深表示速度由低到高。对路段ID矩阵M进行统计分析，得到该时段路网的数据覆盖率为62.68%，较高的数据缺失率和数据密度的分布不均给路网的交通流速度分布研究、交通流速度的预测等带来了较大的困难。

使用朴素贝叶斯分类方法对路网缺失数据进行估计，结果如图8(a)所示。处理后，路网的数据覆盖率达到了73.76%，比原始数据提升了17.68%，但路网中仍有部分路段存在数据缺失的现象。这一现象多存在于低等级道路上，说明低等级道路上历史数据缺失大于30%的现象严重，导致朴素贝叶斯方法抛弃对这些路段的估计，进而采用DTW算法查找相似路段对估计结果进行补充，结果如图8(b)所示。经过两个步骤的处理之后，路网的数据覆盖率达到了92.33%，比原始数据提升了47.30%。因此，将两个方法搭配使用的填充效果显著，很好地弥补了朴素贝叶斯方法对于多发性数据缺失估计的不足，也在一定程度上降低了使用DTW方法进行预测带来的误差。

图7 路网交通流数据缺失现状Fig.7 The current situation of data loss of traffic flow

图8 路网交通流速度数据修复对比Fig.8 Comparison of repair of traffic flow velocity data

3 结 论

本文构建了一个稀疏数据的填充模型，将数据缺失的类型分为偶然性和多发性缺失，并配合使用朴素贝叶斯分类方法和DTW算法对缺失数据进行填充。试验结果表明：该模型可以使路网的数据覆盖率得到显著的提升，并且混合模型在填充效果上明显优于仅使用朴素贝叶斯方法进行数据填充；填充数据的准确率相较于仅使用DTW算法也得到了一定程度的提升。填充后的浮动车数据具有连续性强、准确度高和数据密度分布均匀的特点。后续的工作仍需考虑以下情况以提升模型效率：

(1)为减少模型的偶然性偏差，保证填充结果的准确性和稳定性，应尽可能增加历史数据样本量，提升以历史数据作为输入参数之一的模型的估计准确性；

(2)不同路网的数据缺失情况不同，应在模型使用前重新对偶然性缺失和多发性缺失的不同划分情况所造成的影响进行评估，确定划分范围，以确保模型填充效果得到保障；

(3)应进一步考虑路网复杂性对模型效率和准确性带来的影响，寻找样本量、准确性和计算效率之间的平衡点。