基于交通流数据修复的GA-RF方法研究

2021-07-14邵毅明甘元艺侯雨彤

重庆理工大学学报(自然科学) 2021年6期

邵毅明，甘元艺，侯雨彤，钟颖

（重庆交通大学交通运输学院，重庆 400074）

准确、可靠的交通流预测信息可以直接应用于先进的交通管理系统和信息服务系统，为出行者提供实时有效的交通运行信息［1］。同时，可靠的交通流预测是交通管理部门采取交通控制和诱导措施的重要依据。通过对短时交通流的预测，可以提前调整交通管理控制手段，从而提高交通运行效率［2－4］。交通流数据是时间序列数据，数据质量直接影响交通流预测结果的精度。在实际道路交通系统中，由于检测设备、传输设备等出现故障的原因，使采集的交通流数据或多或少存在缺失［5－6］。虽然缺失数据的数量随着信息技术的发展有逐渐变少的趋势，但是为了保证交通流预测结果的准确性，在少量数据缺失的情况下，依然有必要对交通流数据修复方法进行研究。

目前，交通流缺失数据时间相关性修复方法多是采用历史均值法、历史相邻加权法以及预测修复3种［7］。历史均值法采用前n天当前时间点的对应数据均值并填充［8］，历史相邻加权法获取前一天同一时刻的历史数据和当天前一时刻的实测值进行加权平均来修复缺失数据［9］。历史均值法、历史相邻加权法属于基于历史数据的缺失数据修复，这两类方法简单易行，能够解决时间序列修复对连续异常数据修复能力不足的问题，但存在不能反映交通流真实变化的情况。交通流数据从本质上而言属于时间序列数据，所以基于时间序列的各种缺失值修复方法都适合交通流缺失数据的修复，预测修复就是典型［10］。预测修复主要将待修复变量作为目标变量，与其相关的变量作为特征向量，构建预测模型，实现对缺失数据的预测修复。已有研究采用RBF神经网络方法［10］、LSSVM的组合阈值修复方法［11］、SVR方法［12］、偏最小二乘法［13］等进行预测修复。

RF集成了bagging和随机选择特征分裂等方法的特点，不仅对噪声和异常值具有较好的容忍度，且相较于AdaBoost、SVM等方法，具有运行速度快、精度高、参数调节方便等优点，现阶段RF算法主要应用于交通流预测方面，有学者通过实例验证了RF预测城市短时交通流具有合理性和高效性［14－15］。RF预测结果与模型参数的优化密切相关，当前研究多是探讨RF模型在预测中的应用，未探索优化方式。GA是通过模拟生物在自然环境中的遗传和进化过程形成的自适应全局优化搜索算法，可用于不同领域的参数寻优、路径规划等［16］。结合以上情况，在考虑交通流时间序列相关性的基础上利用优化的RF算法对存在少量数据缺失的交通流数据修复进行研究：用GA优化RF模型的重要参数，以修复误差最小为主要目标，提出GA-RF的交通流缺失数据修复方法。采用重庆市南岸区某路段的交通流数据进行模型实证，并与其他数据修复方法进行对比，结果显示GA-RF模型在少量交通流数据缺失情况下，修复误差低于历史均值法及历史相邻加权法，修复精度更高，具有更好的修复性能。

1 随机森林算法

RF模型简单、容易实现、计算开销小，被誉为“代表集成学习技术水平的方法”［17］，能同时解决分类与回归问题。RF的“森林”体现在模型是由一定数量的决策树构成，而“随机”则体现在样本的随机性和特征的随机性。设训练数据组共有N条数据，要构建的决策树个数，即森林的大小为M，每个数据点有P维特征，则RF的执行过程如图1所示。

图1 随机森林算法示意图

其中，training＿data为N行P列的样本数据集，从该样本集中有放回采样M次形成M个不完全相同的子数据集bootstrap（i），分别在M个子数据上训练单一决策树模型，形成含有M棵树的“森林”，给定一个新的待识别对象，随机森林中每一棵树会根据该对象的属性给出各自的预测结果，最后依据每一棵树的预测结果得出整个随机森林的预测结果。而根据问题类型的不同，给出的结果或为离散值，或为连续值。当结果为离散值时，表明当前问题为分类问题，遵从“少数服从多数”原则，采用投票法决定最终预测类别；反之，当为连续值时，表明为回归问题，则通过对各单一决策树的预测结果进行加权平均得到最终的预测值。随机森林是一种非线性建模工具，精度高且具备一定的容忍度，不易出现过拟合［18］。

2 交通流缺失值修复的GA-RF模型

RF模型含有许多重要参数，参数的不同取值组合可以产生不一样的结果。为得到更好的预测精确度，需对模型的重要参数进行调参操作。现有的学习曲线调参步骤复杂、训练时间长，因此提出GA-RF模型，在搜索空间内利用GA算法对RF模型的重要参数寻优，使RF的调参过程更加高效、便捷。

2.1 模型预测修复流程

GA-RF交通流缺失值修复模型的修复流程如图2所示，包括数据处理模块、参数调优模块和预测修复模块。

图2 基于GA-RF模型的交通流缺失值修复框架图

首先，数据处理模块先剔除异常数据，用剔除异常数据后的历史交通流数据构造样本训练集及测试集；然后参数调优模块采用遗传算法对RF中树模型的数量（n＿estimators）、最大深度（max＿depth）、节点分支后每个子节点最少包含的训练样本（min＿sample＿leaf）、1个节点能进行分支的最少训练样本（min＿samples＿split）4个参数在搜索空间进行优化，确定参数的最佳组合；预测修复模块利用构造好的训练集以及寻优后的参数组合对RF模型进行训练，形成GA-RF模型，最后将测试数据输入GA-RF模型中进行预测修复，对修复值与真实值进行误差分析并输出。

2.2 训练集及测试集的构造

基于随机森林算法对交通流缺失数据进行修复的基本原理为：将剔除异常数据后的历史交通流数据分为样本训练集及测试集，利用训练集数据训练模型，测试集数据判断模型预测精度；然后将路段的真实待修复数据集中的缺失数据列作为待预测对象，利用训练好的模型对其进行预测修复。假设目标路段在某段时间内的平均速度的数据集为X＿data，观测时间间隔为5 min，X＿data共有M行，每行有N维特征，则数据集X＿data可表示为：

式中：Y为目标变量标签列，X为Y的特征向量矩阵，从交通流时间序列相关性出发构造特征向量，即令xt为t时刻目标路段交通流，xt－n为t时刻前第n个时刻的交通流，则交通流时间序列相关性可表示为：

式（2）表明，当前时刻路段交通流与其前n个时段交通流相关，其中xt相当于式（1）中的目标变量标签列Y，xt－1至xt－n则相当于式（1）中的特征向量X，则从初始时刻到t时刻，样本数据集中的特征向量矩阵X如式（3）所示，目标向量Y如式（4）所示：

由于交通流时间序列数据存在缺失值，因此，考虑时间序列相关性构造的特征向量也存在缺失数据，而用于模型训练的数据应是完整数据集，故从构建好的X＿data数据集中提取各特征均不包含nan值的数据行特征集合作为最终的训练集，按一定比例将其划分为训练数据集（X＿train，Y＿train）、验证集（X＿val，Y＿val），其中训练数据集用于模型的训练，验证集则用于模型的调参。为明确模型的修复精度，选择交通流数据较为完整的某天数据作为测试集，人为随机构造缺失值，利用训练好的模型对缺失数据进行预测修复，比较修复值与真实值的误差，对模型预测修复精度进行评价。最后，提取Y为nan的数据行作为路段的真实待修复数据集合，利用构建好的GA-RF模型修复路段交通流中的缺失数据。

2.3 参数调优

RF的重要参数及其含义如表1所示。

表1 随机森林模型重要参数

以平均绝对误差（MAE）作为评价指标，参数调优过程就是通过不断迭代，寻求以上4个重要参数的最佳组合，使基于该参数组合的模型具有最低的MAE。整个过程是一个全局寻优问题，在众多参数组合中寻找最优参数组合。

遗传算法是通过模拟生物在自然环境中的遗传和进化过程形成的自适应全局优化搜索算法，可用于不同领域的参数寻优、路径规划等，其运算过程主要包含初始种群的产生、个体适应度的计算、根据适应度值对种群中的个体进行选择、交叉以及变异、产生新种群，以此循环，迭代直至满足条件后终止［19－20］。GA优化RF主要采用GA对RF模型参数进行寻优，使模型预测性能在一定程度上达到最优。采用GA对RF的n＿estimators、max＿depth、min＿samples＿leaf、min＿samples＿split进行调优，获取搜索空间的最优参数组合，构成GARF模型。参数调优具体步骤如下：①种群初始化并进行编码；②将RF模型的MAE作为适应度函数；③将解的个体进行选择交叉变异操作，进行解码；④获得适应度目标值和最佳参数；⑤计算基于最佳参数的MAE；⑥终止条件判断，若未达到迭代次数，则返回③继续计算；若达到迭代次数，则停止计算，输出调优参数的最佳组合。

2.4 缺失值预测修复

GA-RF数据修复方法的最后一步为利用构造好的训练集（X＿train，Y＿train）以及寻优后的参数组合对GA-RF模型进行训练，然后利用训练好的模型对缺失数据测试集进行预测修复，选定评价指标对修复结果进行评价。设时间窗窗口长度为5，即假定待修复时刻交通流与其前5个时刻的交通流数据相关，则待修复缺失数据集数据结构如表2所示。

如表2所示，某时段内存在待修复缺失数据，取缺失数据所在时刻的前5个时刻的平均速度数据作为特征矩阵，对缺失数据进行预测修复。由于5个特征向量是由目标变量标签列衍生的，故特征向量中也存在缺失值，且该缺失值来自于当前待修复时刻的先前时刻。因此，只要第1个缺失数据的前5个数据不存在nan，即可通过构造特征向量、提取待修复缺失数据、预测修复的循环操作实现对缺失数据的全部填充，缺失数据修复具体步骤如下：

表2 待修复缺失数据集数据结构

步骤1 考虑交通流时间序列相关性对含缺失数据的M个交通流数据进行N维特征向量提取，形成M行N＋1列数据矩阵row＿data；

步骤2提取row＿data中标签列为nan的数据行，构成待修复缺失数据集missing＿data；

步骤3判断第1个缺失数据所有特征列是否含有nan，有转步骤4，无则转步骤5；

步骤4采用缺失值所在时段的均值对nan进行修复，并实时更新row＿data；

步骤5 提取missing＿data中特征列完整的数据行，调用构建好的模型对缺失数据进行预测修复，并用修复后的缺失数据实时更新row＿data中对应的缺失数据，然后转回步骤2，反复进行，直至missing＿data行数等于0，则所有缺失数据修复完毕。

3 GA-RF模型实证

为了验证所提出的GA-RF模型的可行性，选用重庆市南岸区某路段的交通流数据展开GA-RF模型实证：在测试数据集中随机构造少量缺失数据，以MAE为主要评价指标，均方根误差（RMSE）、均方误差（MSE）、平均绝对百分比误差（MAPE）评价指标作为辅助，以主要评价指标最小为目标，对缺失数据修复的有效性进行评价，并在同等缺失比例下将GA-RF的修复效果与RF方法、历史均值法及历史相邻加权法修复效果进行对比实验。

3.1 实验环境

全部代码均通过Python程序语言实现，Anacond包中的spyder4.1.3版本作为集成开发环境，Windows 10（64位）操作系统、Intel（R）Core（TM）i5－10210U CPU＠2.11 GHz处理器、16GB内存等作为硬件支撑平台。

3.2 实验数据处理

以重庆市南岸区某路段的历史交通流平均速度数据作为实验数据，用于GA-RF的交通流缺失数据修复实验。实验采集了该路段从2018.07.21—2019.06.26的交通流平均速度，由于本次研究只针对工作日，故提取数据集中的工作日数据，构建从0∶00－24∶00、以5 min为增长梯度的完整时间序列。数据集的平均速度分布如图3所示，横坐标表示时段分布，纵坐标表示该时段的平均速度，图中数据集应包含62 784个交通流数据，对数据集进行分析，部分数据存在缺失和异常。

图3 数据集平均速度分布

将构造后的时间序列与原始时间序列进行笛卡尔积，挖掘原始样本中的缺失数据，共计1 284条，并以nan进行标识，则以天为计量单位的路段交通流缺失数据分布情况如图4所示。

图4 以天为计量单位的缺失数据分布

异常值分析是保证数据质量的前提，找出数据的异常值，有利于最终得出的模型的稳定性。利用箱型图剔除异常值获取离群数据（包含离群数据1 834条），剔除离群数据后缺失数据分布如图5所示。

图5 剔除异常值后的缺失数据分布

图4、5横坐标表示第n个工作日，纵坐标为缺失数据个数。由图5可知，2018.07.21—2019.06.26期间，该路段每天的缺失和异常数据大多稳定在5～25，缺失比例在2%～9%，只有个别工作日的缺失值个数超过10%。

3.3 GA-RF的缺失值修复

交通流预测时间窗口为5，即利用待修复时刻的前5个时刻的交通流数据作为特征列对模型进行训练、预测，然后利用预测结果对缺失数据进行修复。将2019年6月14日之前的工作日数据作为训练数据集，用GA对RF的n＿estimators、max＿depth、min＿samples＿leaf以及min＿samples＿split4个参数进行联合寻优，以MAE作为目标函数返回值，衡量在每种参数组合下模型在未知数据上的准确率，误差越大，表明模型的预测效果越不好，因此，全局优化是一个求最小值的过程，设置初始种群中个体NIND为10，迭代次数为200，交叉概率pc为0.7，变异概率pm为0.1。

在利用遗传算法确定最佳参数组合的200次迭代中，各参数搜索空间如表3所示。

表3 待优化参数搜索空间

经过训练，训练结果如图6所示，横坐标代表迭代次数，纵坐标代表MAE，在GA-RF模型中，随迭代次数的增加，模型在验证集上最优解的MAE越来越小，最终呈现为平行于x轴的一条直线（如图7所示），找到搜索空间的最优解，得到最佳参数。

图6 GA-RF模型训练曲线

图7 GA-RF预测模型收敛曲线

为评价模型的修复精度，在测试数据集中，选6月24日交通流数据作为测试数据，构造3%、6%缺失比例的随机缺失数据，利用GA-RF模型分别对2种比例缺失的数据进行预测修复实验，并将GA-RF模型预测修复结果与RF预测修复、历史均值修复、历史相邻加权法结果进行对比。图8、图9给出了3%和6%的缺失比例下，采用RF、GA-RF、历史均值法以及历史相邻加权法4种修复方法的修复结果与真实值的对比曲线，每一个marker为一缺失数据。由图8、9可看出，GA-RF模型的预测修复结果曲线较其他几种方式更贴近原始数据曲线。