KNN在短时交通流预测上的应用与研究

林罗杰，殷锋，袁平

（1.四川大学计算机学院，成都 610065；2.西南民族大学计算机科学与技术学院，成都 610041；3.重庆第二师范学院数学与信息工程学院，重庆 400067）

0 引言

智能交通系统（Intelligent Transportation System，ITS）的目标是尽可能提高交通资源的利用率，并对其进行有效的控制和管理。为了达到这个目的，ITS需要对现有的交通状态做出合适的响应，除此之外，利用历史数据和当前状态对未来的交通状况做出及时、准确的预测也是十分重要的一环，这将更好地帮助系统做出正确的决策。

针对交通流预测的研究和模型众多，大致可以分为两类：①基于统计学理论、②基于数据驱动。基于统计学理论的方法一般基于某种特定的假设，例如时间序列分析中被广泛应用的ARIMA(自回归积分移动平均)模型就建立在时间序列平稳的基础假设之上，在满足条件的情况下才能进行后续的模型识别以及参数确定。除了时间序列分析之外，常见的基于统计学理论的预测方法还有历史平均法、局部线性回归法、卡尔曼滤波法等。该类方法大多比较简单，计算方便，但是不能很好地应对交通流的随机特性，更适合做一些粗略的估计[1]。基于数据驱动的方法虽然研究时间起步较晚，但是随着数据的增长以及机器学习的兴起，近年来受到的关注也越来越多[2]。基于数据驱动的方法往往直接从数据中学习经验，不需要严格的先验知识也能达到较好的预测效果，常见的模型有SVR（支持向量回归）模型，KNN模型和基于神经网络的模型等，其中KNN模型作为一种简单有效的数据驱动方法，已经被广泛运用于各种交通流预测研究之中。

1 理论基础

1.1 短时交通流预测

交通流预测可以看作是一个指定兴趣区域和时间间隔，并根据当前交通状态和历史数据对下一个时间间隔的交通量进行预测的过程，常见的交通量有流量、速度、密度和旅行时间等。所谓短时交通流是相对长时交通流而言的，二者的区别体现在时间间隔上，前者的时间间隔一般不超过一个小时，一般用于对交通状况实时地进行预测和管理；而后者的研究目标通常是一整天或更长时间，一般用于对特定交通区域进行长期的预测和规划。

从时间序列分析的角度来看，可以把预测问题定义为已知历史交通流序列X=[X1，X2,…,Xi,…,XT-1]和当前交通量XT，求下一时刻的交通量XT+1。其中T是当前时段，T+1是要预测的下一时段，Xi对应第i段时间间隔中采集的交通量数值，X1是历史数据集的起始参照点。

1.2 KNN 方法

KNN方法本质上是一种模式识别的方法，该方法通过某种相似性度量函数计算历史状态与当前状态的相似程度，如果能找到与当前状态最相似的K个历史状态（也称作状态向量），那么这K个历史状态就成为了的K个“近邻”，“近邻”的相关特性可用于评估当下的状态。

在交通流预测领域中，KNN方法最简单的应用方式就是将历史时序数据“切片”构建成样本库（每一个时间片就是一个状态向量），当有预测需求时，将当前时间片与样本库中的时间片进行比对，选出最相似的K个时间片，然后对这K个时间片各自对应的下一时间间隔的交通量进行累加求平均，方可求得预测值。

KNN方法的四个核心问题分别是：①如何选择合适的状态向量；②如何衡量状态向量之间的相似性；③如何确定K的大小；④如何根据K个近邻进行预测。上述过程只是简单地利用了顺序时序数据并使用累加求平均的方式获得预测值，实际情况中往往需要考虑更多的因素，采取更复杂的算法，才能取得较好的预测效果。

2 相关应用与发展

Smith团队[3]早在1996年就提出了使用“非参数回归模型”对高速公路流量进行预测，此处“非参数回归模型”的核心就是KNN方法，该研究指出在构建状态向量时除了利用历史时间序列之外，引入历史平均值可以取得更优的预测精度。另外，相较于传统的建模方法只能预测未来最近的一个时间段而言，KNN方法可以一次性预测即将到来的多个时间段，实验证明“多步预测”的预测效果与预测时间点有关，但总体效果在可以接受的范围内。1997年，该团队[4]发现KNN方法在同一数据集上的预测效果要优于HA（历史平均）模型，ARIMA模型和神经网络模型，通过在两个测试站点上的对比实验，证明KNN方法的误差分布情况最好，且不需要根据数据的变化而调整模型本身，泛化能力较好。2016年，Filmon等人[5]对传统的KNN方法进行了多个方面的改进，包括引入加权的欧氏距离，使用缩尾处理（winsorization）抑制占主导地位的“近邻”和LOESS（局部估计散点平滑）技术，使平均绝对误差相较于其他对照模型降低了25%以上。

KNN方法存在的一个问题是随着数据库的增大，搜索“邻居”的时间也会随之增加。数据的多样性和完整性是KNN有效运行的前提，这要求历史数据库必须包含尽量多的交通状态，如何减少搜索时间成为了保证算法实时性的关键。2015年，Marcin等人[6]发现最近的“邻居”总是出现在一个相对较窄的时间段内，于是提出了一种数据分割的方法，该方法可以通过“软计算分析”从历史时间序列中分割出对预测算法最有用的片段，这样可以缩减匹配的规模，从而提升计算速度。同年，Meng等人[7]针对KNN搜索时间优化的问题，提出应该用平衡二叉树（AVL）结构取代传统的线性结构。首先采用聚类方法和AVL技术对数据库进行更新，然后通过改良的KNN来预测未来的交通流，并在搜索的过程中两次使用模式识别分别确定邻居和模式的大小，实验证明该方法可以有效提高实时搜索速度。

近年来，仅仅研究时间依赖对交通流的影响已经不能满足需求，越来越多的学者发现交通网络中的空间依赖也会对预测产生影响。2016年，Yu等人[8]将预测站点的上下游链路信息考虑到预测算法中，并建立了四种不同的空间相关性KNN预测模型，发现考虑了空间因素的预测模型要优于只考虑时间依赖的传统模型，除此之外实验数据还表明下游链路信息相对于上游链路信息而言更加重要。2018年，Unsok等人[9]认为现有的研究没有全面地利用预测点周边的空间信息，提出了一种利用互信息（Mutual Information）评价时空相关性的方法，该方法可以从多个与预测点相关的路段中挖掘出最相关和路段和滞后时延，并通过贪婪选择算法构建交通状态向量，其效果优于传统KNN方法和普通时空模型。

3 分析展望

KNN方法的优点是简单，易于部署和泛化能力好。并且相对于传统方法中需要对数据进行平滑处理和历史平均等情况，KNN方法的比较对象往往是更加真实的数据，因此也更有可能捕捉到一些不常见的交通状况，例如车辆突增、交通事故等。在实际应用中，这些非典型的交通状况更加需要被及时地发现，从而进行有效地管理，从这个层面来看KNN是一个很有潜力的预测方法。

数据库的质量对KNN方法的预测效果有很大的影响，理想的样本数据库应该具有代表性，即能够利用更少的数据覆盖更多的交通状况。另外，由于数据收集过程中难免出现设备损坏，统计错误等问题，异常数据和缺失数据对预测结果的影响也是不可忽视的。解决此类问题的方法通常是对应用数据进行预处理，包括线性插值、阈值去噪等。从预测模型的角度来思考，如何设计出一种更加先进的KNN模型，使其对数据缺失和异常点的敏感度降低，提高算法的鲁棒性也是值得研究的分支。针对时空关系的挖掘，无论是通过人工指定还是特定算法分析，大量的研究都发现空间依赖的引入的确可以提高预测的性能。但是如何科学地说明交通网络中空间关系，怎样利用空间依赖构建合适的状态向量，可能是下一步需要努力的方向。

无论是基于统计学理论的方法还是基于数据驱动的方法，现有的研究都没有明确地指出某一方绝对优于另一方。每种方法都有自己特定的适用场景，应该根据具体的问题和需求选择合适的方法。除此之外，如何将两种甚至多种预测方法整合起来，发挥各自的优势以在更短的时间内取得更优的预测效果，这种混合模型也是当下研究的主流之一。

4 结语

本文立足于KNN方法在交通流预测上的研究和应用，介绍了该领域的基本任务以及KNN方法的原理和发展过程，并对KNN方法的优劣和未来研究方向进行了简单的分析。由于篇幅有限，本文没有对现存的所有预测模型进行综述，但我们有理由相信随着各种科学理论和计算模型的不断进步，今后会有越来越多优秀的预测方法被应用到该领域中来。