基于优化随机森林算法的浮动车GPS数据插补模型

吕勤学，郭杜杜，李心，赵亮

(新疆大学机械工程学院，乌鲁木齐 830046)

随着数字化城市建设，推动了大数据在城市交通的应用[1-2]，浮动车全球定位系统(global positioning system,GPS)数据因具有高精度，全天候和易收集等特点，被广泛应用于智能交通领域。但原始浮动车GPS数据易受建筑物、林荫遮挡和信号干扰等因素影响造成数据缺失[3]，导致数据特征量减少、特征提取存在偏差[4]，影响了浮动车GPS数据在路网状态分析[5-6]、交通流预测以及出行方式判别[7-8]等领域的研究与应用，因此，研究浮动车GPS数据插补具有重要意义。

目前针对浮动车GPS数据缺失研究，主要集中于利用道路匹配算法进行插补。盛彩英等[9]利用空间几何、路网拓扑关系，实现轨迹点插补；Yuan等[10]在路网拓扑关系基础上，通过路段分割法插补缺失数据点；黄振锋等[11]利用曲线拟合算法和评价函数找到最佳道路匹配结果补齐缺失数据；Ersan等[12]利用卡尔曼滤波算法降低浮动车GPS数据与路网之间的偏差率补齐缺失数据；邵天浩等[13]利用哈希函数和路网边权修正方法搜索路网信息对缺失数据点进行修复；谷远利等[14]引入遗传算法迭代出最佳空间相似度和最短路径进行数据点插补。

上述研究从优化算法和空间关联性出发，实现了浮动车GPS缺失数据的有效插补，但这些研究过度依赖路网信息的精准性和完整性，且需要与路网信息进行复杂比对，影响插补精度的提升。由文献[15-16]表明随机森林算法可对地面检测器检测的交通流缺失数据和事件进行有效插补，但尚未运用在浮动车GPS数据插补中。因随机森林算法的随机性，导致预测结果易产生波动，影响算法预测性能，故结合浮动车GPS数据点在道路上呈线形分布的空间特点，挖掘浮动车GPS数据点与交通流状态之间的时间变化规律，提出基于优化随机森林算法的插补模型。该模型将线性回归算法融入随机森林算法的结果输出部分，并利用序列插补思想，依次插补缺失数据点。以浮动车GPS数据点出发，实现对缺失的浮动车GPS数据进行稳定的高精度插补，为后续研究与应用提供数据基础。

1 基于优化随机森林算法的GPS插补模型设计

本实验模型利用随机森林算法建立浮动车GPS数据点与速度、加速度和位移之间的关联性，同时考虑到道路线形的特点，将线性回归算法融入随机森林算法的结果中进行优化，提升预测精度。

1.1 优化随机森林算法

随机森林算法是Bagging集成算法和决策树算法的融合[17]，属于Bagging算法的一种拓展。考虑到决策树在生成的过程中容易出现过拟合问题，针对这一问题一般处理方法是通过限制最大生长层数和叶子结点个数的方式进行优化，但其噪声依然存在，影响模型的精度，于是融合Bagging集成算法[18]，将样本中的数据进行有放回的随机抽样，即随机抽取n组样本作为训练集，建立n个并行独立弱评估器。建立过程中，决策树在节点处进行分枝以平均绝对误差最小为原则，即对于任意一个需要分枝的变量A，对应的任意父节点s，其两个子节点U1和U2，需要求出使得U1和U2平均绝对误差最小，且U1和U2的平均绝对误差值之和最小时所对应的变量和父节点,其表达式为

(1)

(2)

式(2)中：L为残差平方和函数。

训练出相应权重后，采用序列插补思想，逐一对预测点进行拟合，当第i+1个点拟合出后将作为拟合第i+2点的输入，同时第1个点将被剔除依次进行预测至缺失点的个数n次后，生成n个最佳权重矩阵后输出插补点Dn。其结构示意图如图1所示。

图1 优化随机森林模型示意图

1.2 浮动车GPS数据插补优化随机森林模型构建

本模型构建如图2所示。

MAE为平均绝对误差

1.2.1 数据预处理

考虑到数据在收集的过程中会出现异常的数据点，为了避免对最终的结果造成影响，利用阈值函数法，对不同的特征设置相应的阈值，超过设定值，则认定为异常数据进行剔除。处理后的数据利用速度和时间间隔计算出对应时间段的加速度和位移。为了方便后续试验验证，将选取完整路段数据，并将数据复制为两份。一份用于实验，随机连续删除数据点，并在删除点后数据点的时间间隔列修改其数值为缺失点个数乘以时间间隔来模拟插补段；另一份用于最终的结果验证。

试验采用假阴道法采精，挑选12只3～4岁无繁殖障碍且体况良好的多浪羊盘羊高代杂交公羊，在采精前三个星期进行补饲。试验中将稀释液与采集的精液按照精液密度等温混合，对稀释后的精液进行活率检测，活率达到0. 7以上，将分装的试管放在37 ℃盛有水的烧杯中，水浴在冰箱中1. 5 h降温至0～4 ℃以内，并保存在冰水混合物中。

1.2.2 样本特征和数据集的划分

对数据的时间间隔列进行遍历，记录其数值并除以时间间隔来确定缺失点的个数，同时选取插补段前若干个点作为预测模型预测函数的自变量，其预测函数F表达式见式(3)，其余点作为模型的训练集。

Sn=F(Ln-1,Zn-1,an-1,vn-1,mn-1)

(3)

式(3)中：下标n为预测点；S为经度；L为纬度；Z为高程；a为加速度；v为速度；m为位移。式(3)中，速度、加速度和位移为基础特征，经度，纬度和高程为变化特征，如需要对经度进行预测时纬度和高程将作为训练特征，经度为目标特征，一共5个特征作为建立预测经度的优化随机森林模型。

1.2.3 浮动车GPS数据插补模型构建及训练

在建立优化随机森林模型过程中，最重要的参数是随机森林中决策树的个数nesti和特征属性，的优化随机森林模型进行预测时以MAE为特征属性，其表达式为

(4)

以MAE最小为最优特征属性。决策树的个数则是根据平均绝对误差与决策树个数图MAE-nesti得到，为了避免随机性，对应到每个决策树的平均绝对误差都进行5次交叉验证，取五次结果的平均值为最终结果，当决策树的个数达到某个值时，误差趋于平稳时的值就是最终优化随机森林中决策树的个数。

1.2.4 构建线性方程及更新权重

将线性回归模型融入随机森林模型结果输出中，将结果分别乘以权重ω、α、β构建出线性方程，其表达式为

(5)

式(5)中：ωi、αi、βi分别为第i个点经度、纬度、位移的权重；Si、Li、mi为第i个点的经度、纬度、位移。

再利用最小二乘估计法计算出最佳权重，得出插补段中的经度、纬度和高程等变量。

1.2.5 插补结果判断

为了验证模型可靠度和精度，利用误差距离[式(6)]进行精度测试。将真实值中的经度、纬度、高程和预测出的经度S、纬度L、高程Z放在同一数据集中利用误差距离公式转换为空间坐标系，计算出两者之间的距离来衡量模型的精度，最终得出的误差距离越小，表示模型精度越高。

(6)

2 实验验证

在验证的过程中所用到的实验数据来自招募的6名志愿者21 d的出行轨迹，收集装置设定以4 s为时间间隔，10 m为定位精度，收集的过程中要求志愿者全程保持设备处于正常运行状态，收集结束后的数据导入计算机中，最终得到的原始数据中记录有经度、纬度、高程、时间间隔和速度。选取其中17组原始数据约15 000个数据点，进行预处理后作为实验数据，如表1所示。

表1 实验数据

2.1 最优参数调整

将收集到的数据输入模型中，根据平均绝对误差最小的原则，误差越小，代表模型精度越高。以决策树的个数为x轴，平均绝对误差为y轴，依次递增决策树的个数得出平均绝对误差的值，当决策树的个数达到某个值之后误差趋于平稳时即为模型的最优参数。根据实验数据MAE-nesti图(图3)在分别预测经度、纬度和高程时所对应的nesti为150、250和200时为最优参数。

图3 实验数据MAE-nesti图

2.2 预测函数点的选取

根据相邻数据点之间的关联性特点，选取插补段前的点数过多易导致数据间关联性变弱，过少则易造成影响最终精度，因此分别选取插补段前3、5、7、10、13、15个点作为预测函数的自变量，相应的误差为因变量，考虑到误差单位不同，故将经度和纬度变量数值乘100，高程变量乘0.1，位移变量乘0.5。综合其各个预测变量的结果(图4)可知，选取缺失点前5个点作为预测函数输入为最佳。

图4 不同时间间隔误差

2.3 线性方程的权重确定

以28 s插补段为例，选取前5个点作为模型预测函数的输入，相应的得出5个预测点，此5个预测值作为线性模型的输入，依次将构建出五元一次线性方程，以经度为例得出的权重为

(7)

2.4 优化随机森林模型与其他模型的插补结果对比

结果对比是通过删除其中140组连续已知的28 s浮动车GPS数据，再通过上述建立的插补模型进行插补，插补出的数据与删除前的数据做对比，最后得出结果。表2、表3分别为删除前保留部分数据和利用线性回归模型、决策树模型、随机森林模型和优化随机森林模型进行插补后的部分数据，图5为插补数据的误差距离分布曲线。

表2 插补前数据

表3 插补后数据

图5 模型对比结果

表2、表3和图5反映了在不同模型下的误差距离，可以看出，优化随机森林模型插补误差距离较小，统计其17 m以内误差距离占结果样本的79.5%，17～50 m占20.5%。随机森林模型插补得出的误差距离，其误差距离17 m以内占结果样本的48.7%，17～50 m占17.2%，其他大于50 m的占34.1%。决策树模型误差距离17 m以内占结果样本的30.3%，17～50 m占59.2%，其他大于50 m的占10.5%。线性回归模型其误差距离大部分大于50 m且与真实值之间的误差距离波动较大。由此可见，基于优化随机森林模型插补浮动车GPS数据的精确程度相对较高，具有更好的插补精度。

表4为优化随机森林模型与其他模型的误差结果分析，从结果的波动性来看，优化随机森林模型明显优于其他模型，其标准差为7.6 m相较于线性回归模型、决策树模型、随机森林模型分别降低了174.8、23.2、10.9 m。可见优化随机森林模型具有更好的稳定性。

表4 模型结果对比分析

3 结论

为解决浮动车GPS数据收集过程中缺失问题，利用浮动车GPS数据与速度、加速度、位移变量之间的关联性并考虑到道路线形的特点，将随机森林算法和线性回归算法进行融合，建立基于优化随机森林算法的浮动车GPS数据插补模型并与线性回归模型、决策树模型和随机森林模型进行对比分析，得出如下结论。

(1)所提出的优化随机森林模型插补结果平均误差为12.3 m，与随机森林模型、决策树模型和线性回归模型相比，分别减少了14.9、24.3、239.3 m，所提的方法具有更高的精度。

(2)所提出的优化随机森林模型，融入线性回归算法，得出距离误差的标准差为7.6 m相较于随机森林模型减少10.9 m，表明线性回归算法应用到模型中具有较好的效果，并使得模型具有更高的稳定性。

(3)经过浮动车GPS数据插补模型处理结果可为城市交通状态预测、交通规划管理诱导和基于浮动车GPS数据识别出行方式研究等提供可靠的数据基础。