基于改进KNN算法的交通流异常数据修复方法

，，， ，

(上海工程技术大学 汽车工程学院，上海 201620)

0 引言

交通数据是智能交通系统(intelligent transportation system, ITS)中主要的数据支撑，可以直接反映交通的运行状态，能够为交通规划、管理和决策提供重要的信息[1]。交通流数据质量的高低直接影响着交通流状态分析的准确度。交通数据在实际获取中，由于受到检测器自身异常、传输网络异常及环境因素等的影响，采集到的交通流数据难免会出现数据缺失、数据错误等质量问题[2]，对交通流数据分析以及交通管控精准性造成影响。因此，进行异常数据修复，提高交通流检测数据的质量，是交通状态辨识、交通管理及控制等工作正常进行的必然要求。

交通流异常数据修复方面的研究通常是基于历史数据构建数据修复模型[3]。目前，对交通流异常数据修复方法的研究大致可以分为三类：一类是传统数学模型，包括历史趋势法[4]、移动平均法[5]、插值法[6-7]、灰色残差模型[8]等；第二类是智能修复方法，包括非参数回归[9]、神经网络[10]等；第三类是组合模型[11-12]，是指两种或两种以上的数据处理方法进行组合的方法。智能修复方法主要是采用机器学习算法对异常数据进行识别和修复，该方法是目前普遍采用的数据修复方式[13]。

K最近邻(K-Nearest Neighbor，KNN)算法模型属于非参数回归方法，是一个理论上比较成熟的方法，也是最基本的机器学习算法之一。在交通领域中，KNN算法模型早期一般用于交通流预测。Davis和Nihan[14]率先运用k近邻法的非参数理论方法对高速路交通流量进行预测。随着KNN模型在交通领域的引入，有研究者针对如何提升k近邻运算速度的问题进行了一系列探索[15-16]。随后，于滨等[17]分析了k近邻算法的时间和空间参数，提出4种状态向量组合的k近邻模型，通过优化算法参数来提高数据处理精度。谢海红等[18]分析了原有的短时交通流预测的k近邻算法，用模式距离搜索方法代替原有的欧氏距离搜索方法，引入多元统计回归模型，建立了一种改进的k近邻算法，结果表明，改进的k近邻算法应用效果比原有k近邻算法要好。Habtemichael F.G.[19]通过采用加权欧氏距离作为相似性度量标准，采用指数权重作为近邻值权重，提出了非参数和数据驱动的短期交通流预测方法，结果证明其方法能有效提高预测精度。

目前KNN算法模型主要应用于交通流预测方面，在交通数据修复方面的应用和研究较少。因此，本文在对KNN算法特性分析的基础上，通过对k值、修复状态向量以及近邻值权重等模型主要相关要素的优选和改进，进而构建基于改进KNN算法的交通流异常数据修复模型。研究结果旨在为交通流数据修复方法提供一种新的思路，为交通管控提供准确的基础数据支持。

1 KNN异常数据修复模型

1.1 KNN基础算法

KNN算法主要以数据为驱动，通过搜索历史数据库中与当前数据相似的状态向量数据来进行数据修复。模型的基本流程如下：首先，构建具有较大容量且有代表性的历史数据库。其次，设定模型的相关要素，包括近邻个数k，状态向量，距离度量方式和修复算法等，其中近邻个数k、状态向量和距离度量方式组成了模型的搜索机制。最后，根据输入的异常数据状态向量和搜索机制，从历史数据库中找到与异常数据状态向量相匹配的近邻，利用修复算法得到修复后的交通数据值。

模型的运算速度和修复精度主要与4个要素密切相关：近邻个数、状态向量、距离度量方式、算法实施。模型性能的优劣很大程度上取决于这4个要素的选取。近邻数k表示从历史数据库中选取与当前数据相似的数据组数，k值的选取主要与历史数据库有关。状态向量作为当前数据与历史数据库实施匹配的一个匹配标准，表征了历史数据库中的数据特征。距离度量方式用于计算异常数据状态向量与历史数据库中各个状态向量之间的距离。修复算法构造了采用k组近邻数据集修复异常数据值的方案。

1.2 改进KNN算法

异常数据修复是交通管控有效实施的基础，采用KNN算法能够实现在众多的历史数据组群中匹配到异常数据相似组群，进而实现对异常数据的修复。因此，本文提出基于改进KNN算法的异常数据修复方法。KNN异常数据修复模型实施过程如图1所示。

针对出现异常的交通流数据，运用改进KNN算法对其异常数据进行修复，其实现方法具体步骤如下：

1)选取异常数据出现的同一监测点的正常交通流检测器数据作为数据源，选取连续5个数据为一组，建立历史数据状态向量库Xn。

2)识别异常数据，选取异常数据前后两个时间间隔的正常数据，建立异常数据状态向量X。

3)计算异常数据状态向量X与历史数据状态向量库Xn之间的欧式距离d，对其距离按照由小到大进行排序，记为di。

4)通过数据验证平均相对误差与k值的关系，对近邻值个数k进行优选。

5)选取距离占比的近邻值权重选取方式。

7)对异常值进行删除，并填补修复后的数值。

本文在对KNN基础模型以及交通流数据特性分析的基础上，对KNN基础模型的改进主要体现为三点：一是对k值进行优选；二是考虑异常数据前后时刻的关联数据，建立了状态向量；三是提出了一种新的近邻值权重选取方式。

1)参数k优化选取:

近邻值个数k表示从历史数据库中选取的近邻个数，k值大小是影响算法计算时间和数据修复精度的一个重要因素。一般情况下，k值越大，修复精度越高但其运算时间会相应增加。

由图2可知，随着k值的增大，平均相对误差不断减小，并逐渐趋于平缓。当k值为25时，图形基本收敛，随着k值再增大，平均相对误差已无明显变化。因此本文优选k值为25。

图2 平均相对误差与k值的关系

2)状态向量建立:

分别建立历史数据状态向量库和异常数据状态向量。

目前对交通流异常数据的修复，通常考虑的是利用异常数据的前向数据对其进行修复。图3表示一段时间内交通流速度变化趋势。从图中可以看出，交通流速度随着时间的变化，具有不确定性、波动性和随机时变特性。交通流数据自身具有一定的特征和规律，相邻时间之间的数据具有某种关联性，前一时刻速度大小会影响后一时刻速度大小，数据之间具有很强的连续性和关联性。并且时间距离越近的数据之间关联性越大[20]。

图3 交通流速度数据趋势图

(1)

3)距离度量:

距离度量方式是用于度量异常数据状态向量与历史数据库中各个状态向量之间的相似程度，一般采用欧氏距离作为衡量标准：

(2)

4)修复算法构建:

修复算法构造了采用k组近邻数据集修复异常数据值的方案，即:

(3)

寻找到的k个最近邻中，距离越近，说明此近邻值与当前异常数据状态向量的相似度越大。为了提高其修复精度，采取对其近邻值赋予权重的方式，距离越近的近邻值，赋予的权重越大。

关于近邻值权重的选取，现有的k近邻权重选取方式主要有距离倒数权重和排队指数权重两种，分别定义为权重1、权重2。如式(4)、式(5)。

距离倒数权重：

(4)

排队指数权重：

(5)

在现有权重的基础上，根据KNN算法的基本原理，综合考虑算法复杂度和计算速度，提出距离占比的权重选取方式，定义为权重3，如式(6)。

距离占比权重：

(6)

式中,αi是第i组近邻值；k指近邻值的个数；di是当前异常数据状态向量与历史数据库中第i组状态向量数据之间的欧式距离；di是第i个近邻值的权重。

2 实验验证

2.1 评价指标

本文采用平均相对误差为主要评价指标，均方根误差、相关系数评价指标作为辅助对交通流异常数据修复的有效性进行评价。平均相对误差(MAPE)表示修复值与真实值之间相对误差的均值，其值越小表示修复效果越好。均方根误差(RMSE)表示修复值和真实值之间的偏差，可以反映其修复能力，误差值低表示效果好。计算公式分别为：

(7)

(8)

相关系数r表示修复值和真实值之间的相似程度，其值大小范围为[-1,1]。其绝对值大小代表了数据之间的相关程度，负号表示数据关系为负相关，其绝对值越接近1表示相关性越强。计算公式如下：

(9)

2.2 数据来源与处理

本文选取山东某高速公路监测点获取的实际交通流速度数据作为实验样本数据。为了更好地反映交通流量的运行情况，把交通速度数据合成为5分钟时间间隔的速度数据。选取60天正常交通流速度数据作为实验样本数据，其中90%作为历史数据库样本，10%作为测试数据样本。部分交通流速度数据示例如表1所示。

表1 部分交通流速度数据示例

2.3 结果比较与讨论

2.3.1 不同k值的结果比较

为了检验改进后的KNN数据修复模型的整体修复效果，用实验数据分析了3种KNN模型进行数据修复的平均相对误差和近邻值k的关系，并与常用的数据修复方法移动平均法相对比，结果如图4所示。

图4 平均相对误差与k值的关系

从图4中可以看出：

1)当k值大于6时，带权重2的KNN模型的修复效果优于移动平均法，当k值大于4时，带权重1、3的KNN模型修复效果优于移动平均法。由此可以得出，相比较移动平均法，KNN修复模型的异常数据修复效果明显较好，说明KNN模型适用于数据修复，采取k近邻的思想进行数据修复的方法可行。

2)随着k值的增大，3种KNN数据修复模型的平均相对误差不断降低，并逐渐趋于平缓，权重3的KNN修复模型所得修复结果的平均相对误差值比权重1和权重2修复模型的误差值小，说明改进的KNN数据修复模型的整体修复效果优于另两种权重KNN模型的整体修复效果。

2.3.2 不同模型结果比较

将平均相对误差、均方根误差、相关系数3种指标作为修复算法的误差评估方式对实验结果进行全面评价。将3种KNN数据修复模型和传统移动平均法4种方法的修复结果进行比较，见图5、图6和表2。

图5 平均相对误差

图6 均方根误差

修复方法相关系数rKNN修复模型权重10.72权重20.71权重30.73移动平均法0.66

图5显示了4种修复方法实验结果的平均相对误差(MAPE)结果比较。平均相对误差反映了交通流量数据修复值偏离真实值的程度。其值越小表示修复值与真实值的偏离程度越小，说明两者越相近。

从图5中可以看出，4种修复方法实验结果的平均相对误差值大小依次为9.93%、10.1%、9.88%、10.23%。由误差值大小可以看出，KNN修复模型的误差值大小明显小于移动平均法，权重3修复模型的误差值要小于另两种权重修复模型。

图6显示了4种修复方法实验结果的均方根误差(RMSE)结果比较。表1显示了采用4种方法进行数据修复实验的修复值与真实值之间的相关系数r。相关系数表示修复数据与实际数据之间的相似性，其值越接近1表示修复值与真实值的相关度越高，修复效果越好。

从图6可以看出，4种修复方法实验结果的均方根误差值大小依次为10.88、11.07、10.82、12.23。从表1可以得知，在KNN修复模型中，权重3的KNN修复模型的修复值与真实值的相关系数最大，为0.73，权重1和权重2的KNN修复模型次之，分别为0.72和0.71，移动平均法的相关系数最小，为0.66。

由此可以得出，3种KNN数据修复模型的修复效果明显优于移动平均法的修复效果，权重3的KNN修复模型的修复精度明显高于权重2的修复模型，略高于权重1的修复模型，其平均相对误差大小为9.88%。由此可以说明采用改进后的KNN异常数据修复模型进行数据修复取得了较好的修复效果。

为了更好的体现改进KNN修复模型的优势，本文还分析了各个方法实验结果的相对误差在不同误差范围内所占的比例。图7表示采用4种修复方法实验结果的修复值与真实值的相对误差在[0,20%)、[20%,+∞)内的数据个数所占比例。可以看出，采用KNN修复模型的相对误差小于20%的占比高于移动平均法，大于20%的占比低于移动平均法。在KNN修复模型中，权重3的修复模型，其相对误差值在[0,20%)范围内的占比最大。这说明改进后KNN修复模型的修复效果能够满足数据修复精度需求。

图7 相对误差占比

3 结论

针对目前交通流数据异常和数据质量不高的问题，将k近邻模型引用到数据修复中。对KNN基础模型相关要素进行改进和优化，建立了一种适用于交通流数据修复的KNN异常数据修复模型。通过实际数据验证，可得出以下结论：

1)提出基于改进KNN算法的异常数据修复模型，该修复模型与传统的移动平均修复方法相比，具有更优的修复精度，其平均相对误差值为9.88%，能够满足基本的异常数据修复精度需求。

2)针对KNN算法模型，进行k值和状态向量的优选、提出一种距离占比的近邻值权重选取方式，进而实现对基础模型的改进。结果表明，采用距离占比的近邻值权重方式的KNN数据修复模型能够有效提高数据修复精度，具有更好的数据修复效果。

本文所提出的数据修复方法实施性较强，可有效提升交通流数据质量，其修复思想对交通数据在实际应用方面具有理论指导意义。