Page 98 - 《软件学报》2020年第12期

3764 Journal of Software 软件学报 Vol.31, No.12, December 2020

Bajwa 等人 [88] 使用 k-NN 模型预测行程时间.该模型对相似模式的行程时间进行提取和清洗,然后取均值作
为最终预测行程时间.实验的均方根误差低于 12.5%.由于该模型假设交通状况是周期性的,因此在交通状况突
变时,无法准确预测行程时间.Lim 等人 [89] 使用 k-NN 方法,结合点检测系统和区间检测系统来预测交通参数,估
计行程时间.点检测系统代表了实时交通状态,用于将时间平均速度转换为空间平均速度;区间检测系统反映了
动态交通状态,用于直接测量路段的行程时间.实验结果表明,预测时间范围为 5min~30min 的平均绝对百分比
误差为 4.3%~14.8%.Wang 等人 [90] 开发了一个带有阈值和线性回归的改进的 1-NN 模型,用于推导真实行程时间
和不同数据源收集到的交通数据间的关系,以找出行程时间日变化或周变化的潜在趋势,从而预测近期交通状
况.实验数据显示:该模型的平均绝对百分比误差低于 8.6%,平均百分比误差低于 16.2%.Tak 等人 [91] 提出了实时
行程时间预测的多层 k-NN(multilayer k-nearest neighbor,简称 Mk-NN)框架 [91] .该框架使用多个层次模式匹配,
即分类匹配、全局匹配和局部匹配,下一层次的匹配过程从上一层匹配的数据集中选取数据.这种多层匹配减
少了搜索空间和计算量,缩短了预测时间.预测结果是多个匹配数据的加权平均和,权重由遗传算法(GA)进行优
化.实验结果表明:Mk-NN 模型比传统 k-NN 快了 8 倍,且平均绝对百分比误差和均方根误差都小于 3.5%.
(4) 集成学习
集成学习方法是一种提升分类准确率的机器学习方法,它的主要思想是:将多个分类算法聚集在一起,根据
多个分类器的投票结果进行预测.集成学习方法可以处理不同类型的变量,适应复杂的非线性关系.集成学习方
法已被用于解决许多交通领域问题.
Hamner 等人 [92] 应用上下文依赖的随机森林方法(random forests,简称 RF)来预测行程时间.RF 是多个决策
树的组合,每棵树都是某种特征的分类或回归专家,最终结果是所有树的投票结果,优于单个分类器 [93] .模拟实
[9]
验使用道路上 1%车辆的 GPS 数据,均方根误差值低于 7.5%.Zhang 等人 采用梯度提升方法(gradient boosting,
简称 GB)预测高速公路的行程时间.该模型能处理急剧的不连续性,这是对交通状况突变进行建模的重要特征.
结果显示,GB 模型的性能相对 RF 有略微提升.这是因为 RF 的训练集是随机选择的;而 GB 在生成新树时更加
注重错误预测的训练样本,因而能生成分类能力更强的树.预测范围为 5min~30min 时,高峰期平均绝对百分比
误差不超过 18.4%;非高峰期不超过 14.8%.Yu 等人 [94] 使用基于近邻的随机森林方法(random forests based on
near neighbors,简称 RFNN)预测公交行程时间.该方法使用 k-NN 对 RF 的训练集进行预选,因为相似的样本可能
具有相似的模式或交通状况,从而具有相似的行程时间.k-NN 方法的使用能提高训练集的质量,有助于提高 RF
的性能.实验使用沈阳市两条公交线路的行程时间数据,结果显示,平均绝对百分比误差低于 14.3%.Gupta 等人
[95] 用 RF 和 GB 模型预测出租车行程时间.实验使用波尔图市的出租车数据,RF 和 GB 的平均相对误差都不超
过 30%.通过分析实验结果发现:GB 比 RF 性能更好,而 RF 能采取并行训练方式所以训练速度更快.

4 开放问题
虽然现有行程时间预测方法中已经具有较好的性能,但是仍然存在一些问题.

4.1 数据预处理
用于行程时间预测的交通数据来源有很多,这些数据具有异构和高维特性.此外,数据可能会缺失或出错,
因此有必要进行数据预处理.Wu 等人 [96] 将数据清洗与数据分析融合,提出了一种噪声感知的数据挖掘算法检
测和消除噪声.Qu 等人 [97] 提出了基于概率主成分分析的缺失数据插补算法.其他类似的数据插补研究还有文献
[98,99].现有的数据插补算法大都假设噪声是某种已知的形式,而现实中数据噪声通常是随机的,难以用一个明
确定义的概率分布函数来表征 [96] .因此,研究新的数据插补算法或者消除算法的假设是一个研究方向.此外,高
维的交通数据可能存在维度诅咒问题.因此,需要研发有效的数据降维方法,如考虑张量分解算法的改进方案
等.过多数据可能会导致模型(如 k-NN)的计算量过大,实时性要求难以满足.使用聚类方法挑选高质量的数据是
一个可行方法.
根据上面的分析,我们提出了一种新的数据预处理框架,如图 4 所示.该框架分为在线和离线处理两部分.
• 离线处理主要有两步:1) 日期分类,即从原始交通数据库中提取相关交通数据,并按照工作日、周末、