基于K邻近算法的城市道路短时交通预测

为了提高城市道路交通状态预测的准确度，适应交通状态剧烈变化，提出了基于K邻近算法的实时交通预测框架。该框架以路段平均速度的时间序列构建特征向量，提出并应用差分序列考虑交通状态的幅度变化，滚动预测不同道路类型的短时交通状态。实验结果表明，增加差分序列的K邻近算法能准确地实现不同道路类型的短期交通状态预测；对比支持向量与随机森林算法，验证K邻近算法更适应交通状态变化剧烈的次干道交通预测。

交通状态预测解决如何在带有随机性和不确定性的交通变化中，根据多源异构的交通流数据，结合其他影响因素，进行数据的系统分析，找出其中的规律并建立相应的预测方法和模型，以预测未来的交通状态变化[1] [2]。

短时交通状态预测的方法主要包括两类：构建以传统数学与物理方法为基础的预测模型和以现代科学技术与方法(如仿真技术、人工智能、控制理论)为基础的预测[3]。

随着数据挖掘技术的发展与成熟，K 邻近算法(KNN 算法)具有结构简单、计算效率高的特点，获得越来越多的关注与研究[4]。KNN 算法的相合性和收敛性在文献[5]中得到有效验证；文献[6]与[7]利用高速公路收费站的进出口数据， 根据全天不同时段的交通状况特征进行历史数据分段， 采用KNN 算法实现高速公路短期行程时间预测；另一方面，KNN 算法易于与其他算法如核曲线(N-Curve)相结合，实现不同近邻的短时行程时间预测[8]；然而，以上研究路段都是状态平稳的高速公路，缺乏对具有较高随机性与不确定性的城市道路的KNN 算法预测框架的研究与分析。

针对上述问题， 本文提出基于KNN 算法的短期预测框架， 并提出差分向量作为特征向量的扩充以考虑交通状态的急剧变化；结果表明，对比支持向量与随机森林方法， 增加差分序列的KNN 算法适合预测非线性变化的交通流，实现更高精度的城市短时交通状态预测。

2. 基于KNN 算法的预测框架构建 2.1. KNN 算法 KNN 算法是数据挖掘技术中的分类方法之一，基于实例学习的非参数预测思想，通过搜索历史数据库中与待预测特征向量最相似的K 个记录来进行分类。

如果一个样本在特征空间中K 个最相似(即特征空间中最近邻)的样本中的大多数属于某一个类别，则该样本也属于这个类别。换句话说，KNN 算法中所选择的近邻样本都是已经正确分类的对象，并只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。如图1 所示，在某一特征空间存在w1，w2，w3 三个分类，通过计算某一样本X 的所有历史样本的度量距离，寻找K 个最邻近历史样本。图中样本X 的5 个最邻近历史样本中，有3 个从属于分类w1，有2 个从属于分类w3，因此确定样本X 从属于分类w1。