(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 CN 110211375 A(43)申请公布日 2019.09.06
(21)申请号 201910432785.2(22)申请日 2019.05.23
(71)申请人 浙江大学
地址 310058 浙江省杭州市西湖区余杭塘
路866号(72)发明人 马东方 盛博文
(74)专利代理机构 杭州求是专利事务所有限公
司 33200
代理人 忻明年(51)Int.Cl.
G08G 1/01(2006.01)G08G 1/065(2006.01)G06Q 10/04(2012.01)G06Q 50/26(2012.01)
权利要求书2页 说明书5页 附图2页
(54)发明名称
基于改进时空关联KNN算法的交通流量预测方法
(57)摘要
本发明提供了一种基于改进时空关联K-Nearest Neighbor(KNN)算法的短时交通流预测方法。本发明核心思想是先构建能体现交通流量变化趋势的状态向量，进一步从历史状态向量的时间域，空间域两个维度中寻找K个与目标检测器当前时段的最接近的状态向量，解析K个状态向量的权重分配，并预测下一时刻流量值。本发明可将路口短时间的流量序列进行良好预测，为提高流量预测的智能性与科学性、提升交叉口交通流的运行效率提供技术支持，属于交通控制研究领域。CN 110211375 ACN 110211375 A
权 利 要 求 书
1/2页
1.基于改进时空关联KNN算法的交通流量预测方法，该方法包括以下步骤：步骤c1状态向量构建，具体是：c11、令xi(t-j)表示第i天中，在第t-j个时间间隔内的交通流量值，i＝1,2,…,n,j＝1,2,…,m，交通状态向量构建方式为Mi(t)为：
Mi(t):[xi(t-1),xi(t-2),…,xi(t-m)] (1)Mi(t)表示第i天中第t个时段的状态向量；
c12、令
表示第i天第t-j与第t-j-1个时间间隔内的交通流量差值：
对式(1)引入趋势项进行更新，更新后的状态向量为：
步骤c2历史状态向量选择，具体是：
c21:对目标检测器S某天中第t个时间间隔内的交通流量值xi(t)进行预测时，KNN算法需要寻找到与该时间间隔的状态向量Mi(t)最为接近的K个历史状态向量，先构建一个历史状态向量组，进一步再在组内进行状态向量选择；
历史状态向量组成：
由目标检测器所有历史天中在第t个间隔的状态向量组
c22:对状态向量组进行时间维度和空间维度两个维度的更新，在时间维
令τ＝1，在空间维度上更新后的历史状态向量组
度上设置时间延迟参数τ，增加τ个史状态向量组处增加上游历史状态组为Mhistory(t)：
和下游历史状态组
步骤c3相似性计算，具体是：
c31:采用加权的标准化欧氏距离计算待预测状态向量与历史状态向量组中每一个状态向量的相似性；
2
CN 110211375 A
权 利 要 求 书
2/2页
式中w(a)和w(b)分别表示向量M中第a个元素和第b个元素，(a)为所有状态向量的第a个元素组成的序列的标准差，δ(b)为所有状态向量的第b个元素组成的序列的标准差；
步骤c4 K值选择并计算预测值，具体是：c41:针对目标检测器S，从近期历史交通流量数据中选择最优K值，K值的初始候选范围设置为1-15；
c42:通过相似性计算以及K值确定出，最为相似的K个状态向量，按照相似性从大到小排列：
通过K个近似的状态向量找到对应的K个流量值：
c43:设置K个流量值的权重Wk
式中rk表示第k个候选值的位置，z表示权值分散度；c44:令待预测值为
则：
3
CN 110211375 A
说 明 书
基于改进时空关联KNN算法的交通流量预测方法
1/5页
技术领域
[0001]本发明提出了一种基于改进时空关联K-Nearest Neighbor(KNN)算法的短时交通流量预测方法，对交通路网中目标检测器下一个时段内通过的车流量进行预测，支撑交通管理及信号控制策略制定与方案优化，属于智能交通研究领域。背景技术
[0002]KNN算法作为一种数据驱动方法，不需要建立复杂的数学模型，也不需要知道先验知识。由于该方法的灵活性，它在非参数方法中得到了广泛的应用。传统的KNN算法基本思想是从所有历史交通流序列中，找到与目标检测器当前时段所处的交通模式最接近的K个序列，进一步获得K个序列下一时刻的流量值并根据相似度对K个流量值进行权重分配，最终得到目标检测器的预测结果。[0003]近年来，研究者们对基础的KNN算法进行了改进，提高了短期交通流量预测在各种实际应用中的性能。然而，现有的方法大多只考虑时间域，只利用目标检测器当前时段和历史时段交通流数据预测下一个时段的交通流，但是在同一时段内，目标路段会与其上下游路段相互影响，所以通过增加交通流的空间相关性来改进KNN算法是一种可行的方法。另外在构造状态向量方面，传统的方式只采用交通流量值作为衡量对象计算相似度，忽视了交通流的趋势变化，所以在构造状态向量时要充分考虑流量的变化趋势，这对于预测精度的增加具有重要意义。
发明内容
[0004]本发明的目的在于提出一种基于时空关联KNN算法的短时交通流量预测方法。该方法的核心思想是先构建能体现交通流量变化趋势的状态向量，进一步从历史状态向量的时间域，空间域两个维度中寻找K个与目标检测器当前时段的最接近的状态向量，解析K个状态向量的权重分配，并预测下一时刻流量值。[0005]为实现上述目标，本发明提出的一种基于时空关联KNN算法的短时交通流量预测方法包括：状态向量构建，历史向量组选择，相似性计算，K值选择，权重分配及计算预测值。[0006]本发明包括以下步骤：[0007]c1、状态向量构建[0008]c2、历史状态向量选择[0009]c3、相似性计算[0010]c4、K值选择，权重分配以及计算预测值[0011]步骤c1包括：[0012]c11、令xi(t-j)表示第i天中，在第t-j个时间间隔内的交通流量值，i＝1，2，…，n，j＝1，2，…，m，传统的交通状态向量构建方式为Mi(t)为：[0013]Mi(t)：[xi(t-1)，xi(t-2)，…，xi(t-m)] (1)[0014]Mi(t)表示第i天中第t个时段的状态向量，这种状态向量实际上是对该时段交通
4
CN 110211375 A
说 明 书
2/5页
模式的描述，传统方式用它之前m个时间间隔的流量值描述当前所处的交通模式。
[0015]
c12、令表示第i天第t-j与第t-j-1个时间间隔内的交通流量差值i＝
1，2，…，n，j＝1，2，…，m，它可以表示该时间间隔内的趋势变化：
[0016][0017]
那么对传统的交通状态向量引入趋势项进行更新，更新后的状态向量
为：
[0018]
步骤c2的过程包括：[0020]c21：
[0021]对目标检测器S某天中第t个时间间隔内的交通流量值xi(t)进行预测时，KNN算法需要寻找到与该时间间隔的状态向量Mi(t)最为接近的K个历史状态向量，如果与所有的历史状态向量进行近似计算会大大增加计算量，通常是先构建一个历史状态向量组，进一步再在组内进行状态向量选择。传统的历史状态向量组历史天中在第t个间隔的状态向量组成：
[0022][0023][0024]
[0019]
通常由目标检测器所有
c22：
对传统的状态向量组
进行时间维度和空间维度两个维度的更新，在
令τ＝1，在空更新后的历史状
时间维度上设置时间延迟参数τ，增加τ个历史状态向量组间维度上处增加上游历史状态组态向量组为Mhistory(t)：
[0025][0026]
和下游历史状态组
步骤c3的过程包括：[0027]c31:
[0028]在状态向量中不只包括流量值还包括流量差值，流量差值具有更小的均值和方差，本方法采用加权的标准化欧氏距离计算待预测状态向量与历史状态向量组中每一个状态向量的相似性。
5
CN 110211375 A
说 明 书
3/5页
[0029]
[0030]
[0031]
式中w(a)和w(b)分别表示向量M中第a个元素和第b个元素，流量值的权重和差值
的权重分开进行计算，距离目标时段越近的值给予越大的权重值,δ(a)为所有状态向量的第a个元素组成的序列的标准差，δ(b)为所有状态向量的第b个元素组成的序列的标准差。[0033]步骤c4的过程包括：[0034]c41:
[0035]针对目标检测器S，需要通过实验的方式从近期(三个月)历史交通流量数据中选择最优K值，本方案采取多折交叉验证，K值的初始候选范围设置为1-15，以MAPE作为准确性的衡量指标，最终通过投票法确认K。
[0036]
[0032]
[0037]式中T＝288，表示该次试验第t个时间间隔的预测值，O(t)表示该时刻的真
实值。
[0038][0039]
c42：
通过相似性计算以及K值确定出，最为相似的K个状态向量，按照相似性从大到小
排列：
[0040][0041][0042][0043][0044][0045][0046][0047]
通过K个近似的状态向量找到对应的K个流量值：
c43：
设置K个流量值的权重Wk
式中rk表示第k个候选值的位置，z表示权值分散度，一般取为2。c44：
6
CN 110211375 A[0048][0049][0050]
说 明 书
4/5页
令待预测值为
本发明的有益效果：本发明通过增加交通流的空间相关性来改进KNN算法，在构造
状态向量方面，充分考虑流量的变化趋势。本发明在对交通流量序列进行预测时表现出准确度高、复杂度低，实时性好的优点。
附图说明
[0051]图1算法实现过程流程图；[0052]图2K值选择图；[0053]图3预测折线图。
具体实施方式
[0054]以某城市某路口90天的流量序列为例，将85天交通流量数据作为历史数据集，将第86-90天的交通流量数据作为待预测序列，对连续5天6:00-21:00内的交通流量数据进行预测，具体实现流程见图1，在这之前需要对90天的流量数据进行预处理包括采用拉格朗日插值法对缺失值填补，异常值滤除以及最大值最小值归一化。下文以第86天第13个时间间隔(t＝13)为例进行交通流量预测。[0055]1.状态向量构建。
[0056]1)以5min为一个时间间隔，则一天中一共有288个间隔(24*60/5)，令m＝12[0057]Mi(13)：[xi(12)，xi(11)，…，xi(1)]1≤i≤86[0058]2)更新后的状态向量：
[0059][0060][0061][0062][0063][00][0065][0066]
以为例进行说明：
2.历史状态向量选择
1)传统的历史状态向量组：
2)增加时空维度的历史状态向量组：
[0067][0068][0069]
3.相似性计算：
状态向量的前12项为流量值，权重为w(a)，后11项为流量差值，权重为w(b):
7
CN 110211375 A
说 明 书
5/5页
[0070][0071][0072][0073][0074]
1≤a≤12
1≤b≤11
加权的标准欧氏距离为：
[0075]
4.K值选择及计算预测值：
[0077]1)对目标检测器85天的历史数据进行十七折交叉验证来选择最优K值(将85天分成17份，每次选择一份即5天作为预测天，剩下十六份即80天作为历史天，每次验证不同K下的预测精确度，并记录下该次的最优K值，最终采用投票法选择十七次结果中的最优K值)，以MAPE作为衡量标准表示一天的预测精度，图2展示其中一次的K值选择与预测精度图。最终投票法得到K＝10。
[0078]2)按照相似度从大到小排序10个历史状态向量，并找到对应的流量值。
[0079][0080][0081][0082][0083][0084]
[0076]
3)分别计算十个流量值的权重Wk，Wk共同组成权重向量Wk。
4)待预测值为：
重复以上四步预测第87-90天的交通流量。[0086]误差计算及比较：以MAPE作为衡量标准，将改进时空关联KNN方法，传统KNN方法，ARIMA方法、LSTM方法进行比较，MAPE分别为7.68，9.51，11.19，8.25。图3展示了四种方法对第86天6:00-21:00的预测结果，从图中看到本方案设计方法预测精度最高。[0087]综上，基于改进时空关联KNN算法的短时交通流量的预测方法能得到较为精准的预测结果。本发明涉及一种交通流量序列的预测方法，具备预测误差小、计算复杂度较低，具有时效性的特点。本发明可将某路口短时间内的交通流量序列进行良好预测，为提高流量预测的智能性与科学性、提升路口交通流的运行效率提供技术支持。
[0085]
8
CN 110211375 A
说 明 书 附 图
1/2页
图1
图2
9
CN 110211375 A
说 明 书 附 图
2/2页
图3
10
