一种非参数回归短时交通流预测中状态向量的选取方法

摘要

本发明公开了一种非参数回归短时交通流预测中状态向量的选取方法，涉及短时交通流预测技术领域，通过在高峰时段、平峰时段、低峰时段和全天候四种情况下采用本发明提供的方法提高了预测精度、稳定性、速度和可移植性，缩短了运行时间，验证了本发明提供的方法的有效性和必要性。

说明书

技术领域

本发明涉及短时交通流预测技术领域，特别涉及一种非参数回归短时交通流预测中状态向量的选取方法。

背景技术

目前国内外许多研究者都将非参数回归方法应用到短时交通流预测研究当中，并根据实际问题的需要对非参数回归方法进行必要的改进。1991年，Davis和Nihan真正将非参数回归的方法应用到交通预测中，虽然避免了选取模型和参数设置等问题，但该方法需要一个庞大的具有代表性的历史数据库并且方法运行所消耗的时间较长。1995年，Smith将非参数回归方法应用于单点短时交通流预测，实验结果取得了相比历史平均和神经网络更好的效果，但同样存在搜索速度太慢的问题。针对搜索速度太慢的问题，Oswald等人从KD树着手建立模糊最近邻的方法，从而改进了非参数回归方法中历史数据结构模式和近邻搜索方法，提高了方法的运行效率。张晓利提出了一种基于平衡二叉树的K-邻域非参数的短时交通流预测方法，采用聚类方法和平衡二叉树结构建立案例数据库，从而提高了预测精度并满足了实时性要求。这些主要是从历史数据库的存储模式和近邻搜索方法进行改进。

然而，对描述上游路段和待测路段流量因果关系的状态向量的选取主要有主成分分析法、相关系数法和自相关系数等，这些方法都是从统计的角度进行分析，把与待测路段流量较相关的因素作为状态向量的分量，而对是否选取了状态向量及是否改进了预测效果缺乏研究。值得注意的是，通过改进历史数据库的存储模式和近邻搜索方法之后即使缩短了方法的运行时间，但是如果状态向量的选取不足以描述上游路段和待测路段的流量因果关系，那么最终的预测效果也不足以让人满意。

发明内容

为了解决上述问题，提高预测精度、缩短运行时间，满足实际应用中的需要，本发明提供了一种非参数回归短时交通流预测中状态向量的选取方法，所述方法包括以下步骤：

(1)根据第一预设准则判断和待测路段相关的上游路段是否在上游路段集合中，如果是，执行步骤(2)；如果否，所述上游路段不在上游路段集合中；

(2)通过预设数据获取待测路段方圆L范围内车流的平均速度；

(3)根据所述平均速度、预测周期获取历史追溯最大周期数m；

(4)根据所述上游路段集合和所述历史追溯最大周期数m获取初始状态向量；

(5)根据所述初始状态向量的维数M确定粒子的编码长度；

(6)设定粒子数为Z，随机产生Z个粒子；

(7)定义适应度函数，根据所述适应度函数获取Z个粒子的适应度；

(8)根据所述Z个粒子的适应度获取粒子的个体极值和全局极值；

(9)将Z个粒子的编码分别与所述个体极值的编码、所述全局极值的编码进行交叉操作、根据预设概率进行变异操作，获取全局最优粒子；

(10)判断是否达到预设次数，如果是，输出所述全局最优粒子；如果否，重新执行步骤(7)；

(11)将所述全局最优粒子和所述初始状态向量做点乘运算获取状态向量。

步骤(1)中所述第一预设准则具体为：

$\underset{i,j}{\Sigma }\mathrm{dis}(p_i^{\mathrm{upstream}},p_j^{\mathrm{inter}\sec \mathrm{tion}})\le L$

其中，表示上游路段中的第i条路段中点的坐标位置，表示上游路段第j个交叉路口中心的坐标位置，表示上游路段中的第i条路段中点的坐标位置和上游路段第j个交叉路口中心的坐标位置之间的距离。

步骤(3)中所述历史追溯最大周期数m具体为：

C表示预测周期，表示平均速度。

步骤(5)中所述初始状态向量的维数M具体为：

M＝(s+1)(m+1)，s表示上游路段号集合中的元素个数。

步骤(7)中所述适应度函数具体为：

F(VAR，ARE，PER，EC)＝λ₁EV+λ₂ARE+λ₃/PER+λ₄/EC，EV表示预测误差的方差，ARE表示平均相对误差，PER表示预测相对误差在区间[0，α]之间的百分数，EC表示均等系数，λ₁表示EV的权重，λ₂表示ARE的权重，λ₃表示PER的权重，λ₄表示EC的权重，α表示预测相对误差。

步骤(7)中所述根据适应度函数获取Z个粒子的适应度具体包括：

定义当前预测周期流量状态模式；

对粒子的编码和所述当前预测周期流量状态模式做点乘运算，获取当前流量状态模式；

对粒子的编码和历史数据库流量状态模式做点乘运算，获取当前历史数据库流量状态模式；

根据所述当前流量状态模式和所述当前历史数据库流量状态模式通过K近邻匹配和等权重预测对当前预测周期的下一周期流量进行预测，获取第一预测误差，以所述第一预测误差作为当前粒子的适应度。

本发明提供的技术方案的有益效果是：

本发明实施例提供了一种非参数回归短时交通流预测中状态向量的选取方法，在高峰时段、平峰时段、低峰时段和全天候四种情况下采用本发明提供的方法提高了预测精度、稳定性、速度和可移植性，缩短了运行时间，验证了本发明提供的方法的有效性和必要性。

附图说明

图1为本发明提供的非参数回归的流程图；

图2为本发明提供的距离法示意图；

图3为本发明提供的非参数回归短时交通流预测中状态向量的选取方法的流程图；

图4为本发明提供的根据适应度函数F获取Z个粒子的适应度的示意图；

图5为本发明提供的高峰时段预测结果比较图；

图6为本发明提供的平峰时段预测结果比较图；

图7为本发明提供的低峰时段预测结果比较图；

图8为本发明提供的全天候预测结果比较图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明实施方式作进一步地详细描述。

为了解决上述问题，提高预测精度、缩短运行时间，满足实际应用中的需要，本发明实施例提供了一种非参数回归短时交通流预测中状态向量的选取方法。

参见图1，非参数回归是一种数据驱动的启发式预测机制，通过搜索历史数据库中与当前观测值相似的数据来预测未来值。通常可以将其划分为五个组成部分：历史数据的选择、样本数据库的生成、数据相似性的定义、K近邻匹配和预测方法。采用非参数回归预测短时交通流时，首先要构建历史数据库，如果将交通流数据不加区别地全部保存到数据库中，势必会带来无法承受的数据库规模、匹配数据时产生“维数灾难”等问题。因此，选择的交通流数据应该是与被测路段的流量密切程度最高的具有完备性和典型性的流量或流量组合。同时，样本数据库是非参数回归的核心，它的结构(包括逻辑结构和物理结构)和搜索数据算法的时空效率对非参数回归性能的优劣起到决定性的作用。因此，本发明实施例的研究重点就是如何合理地选择样本数据库的组织模式(即状态向量)使之既能描述上游路段和待测路段流量因果关系又能节省存储空间并加快搜索效率。样本数据库生成后就可以进行数据相似性的定义、K近邻匹配和预测。设置好非参数回归模型的相关要素之后就可以从历史数据库中找到与当前实时观测数据K近邻匹配，最后，利用预测就能得到当前时刻的下一时刻的交通流预测量。将当前交通流观测数据和交通流历史数据库进行比较时，需要一个比较标准，状态向量就是这个标准的描述。诸如道路占有率、行车速度和天气状况等都会影响本路段下一时刻流量。即使是与之最密切的相邻时刻，相邻路段的交通流量数据也涉及到取相邻几个时间间隔和相邻几个路段的问题。状态向量的合理与否，直接关系到预测精度。目前，对状态向量的选取并没有统一的标准，把尽可能多的因素考虑到状态向量中并不能提高预测的精度，反而会导致较长的运行时间；然而，如果选取的状态向量不足以描述上下游路段流量的主要因果关系，同样也达不到较好的预测效果。K近邻匹配中的近邻点K值的选取是非常重要的，K值的过大或过小都会影响预测的精度。如果选取的K值等于历史数据库模式的数量，那么非参数回归就毫无准确可言了。但是，K值的选取也不能太少，太少的话就会增加偶然因素的成分，影响预测的精度。此外，一些异常的时间内，某些路段流量明显降低而其他路段流量突然增大，K可以取较小值，如果取较大值时，会削弱信息，从而导致预测误差较大。因而，在流量异常大或低流量区间的情况下，K值可以设置较小或者用一个预测区间进行预测。但是，具体到短时交通预测中时，并没有统一的范式来确定精确的K值，这就需要根据不同系列的样本数据参与离线预测检验，通过分析预测误差与K值的曲线图来选取最佳K值。由于一天中不同时段上游路段和待测路段的流量因果关系不一样，当在线滚动预测时，首先应该利用本发明实施例提供的方法和对应时段的历史数据进行必要的离线检测分析，得到描述流量因果关系的状态向量，然后利用状态向量对待测路段的相应时段进行实时在线预测。平峰时段和全天候两种情况下，由于会出现流量较低甚至为0的情况，从而导致预测的平均修正的相对误差较高。为了提高预测的实用性和可操作性，可以选取两个不同的K值来构造预测区间，只要预测值在对应的预测区间内都是可以接受的，从而在一定程度上改进了非参数回归预测结果的平均修正相对误差。假设，实时的交通流数据模式为：

{v_i(t-m)，V_i(t-m+1)，L，V_i(t)}，i∈U+{f}，其中，U为相关上游路段号集合，上游路段号集合U中的元素个数设为s，f为待测路段号，{f}为待测路段号集合，m为历史追溯的最大周期数，t为预测时间，i为上游路段的标号。历史数据库的交通流数据模式为{V_ih(t-m)，V_ih(t-m+1)，LV_ih(t)}，i∈U+{f}。距离衡量了实时数据和样本数据的匹配程度，然而不同的距离度量准则会搜索到不同的K个近邻，进而影响预测值的精度。本发明实施例采用的距离度量准则如下：

$D=\underset{i\in U+\left\{f\right\},l\in \{\mathrm{0,1},L,m\}}{\max }|V_i(t-m+l)-V_{\mathrm{ih}}(t-m+l)|$

其中，距离度量准则D是(s+1)(m+1)维的，在实时数据和样本数据的(s+1)(m+1)维分量中选择距离最大的分量距离作为匹配的度量准则。此距离度量准则充分考虑了(s+1)(m+1)维的不同距离信息，相当于一个(s+1)(m+1)维的超立方体，其边长即为距离最大的一维，即D，D值越小表示匹配的相似度越高。

通过距离度量准则在历史数据库中选择K个最近的历史状态向量，假设在历史数据库中找到K个近邻，实时数据和这K个近邻的距离分别为D_k(k＝1，2，L，K)，这些近邻对应的待测路段下一预测周期的流量为V_kh(t+1)。

预测方法主要包括带权重预测方法和等权重预测方法。由于交通系统包含确定性和随机性：确定性通过近邻来反映，即当状态向量接近时，预测值和真实值也较接近具有一定必然性；但系统具有随机性，所以不存在“状态向量越接近，预测值与真实值也越接近”的规律。根据世界上不存在两个完全一样的命题可知：当两片树叶95％的特征几乎完全一样时，另外5％的特征存在明显差异的可能性反而高。因此，在本发明实施例中的预测方法采用的是等权重预测方法，表达式如下：

$V(t+1)=\frac{1}{K}\underset{k=1}{\overset{K}{\Sigma }}{V}_{\mathrm{kh}}(t+1)$

参见图2，由距离法可以较粗糙地确定相关上游路段数s和历史追溯的最大周期数m。用黑色菱形标志的路段为待测路段，用黑点标志的是交叉路口中心点，黑色方框标志的路段为待测路段的上游路段。通过经验分析发现，如果到待测路段的城市距离在L范围内的上游路段对待测路段的流量都产生显著影响，那么这些上游路段就组成了状态向量的上游路段集合，其中，上游路段数s和L范围的取值，根据实际应用中的具体应用情况确定，具体实现时，本发明实施例对此不做限制。根据路网特征和距离法得到较粗略的状态向量，然后利用PSO(Particle Swarm Optimization，粒子群优化算法)-GA(Genetic Algorithm，遗传算法)混合智能算法和检验数据对第一预测误差进行优化，从而得到能够描述上游路段和待测路段的流量因果关系的状态向量。最后，就可以利用找到的状态向量进行实时在线的流量预测。参见图3，详细的介绍本发明实施例的具体实现过程：

101：根据第一预设准则判断和待测路段相关的上游路段是否在上游路段集合中，如果是，执行步骤102；如果否，上游路段不在上游路段集合中；

其中，第一预设准则为表示上游路段中的第i条路段中点的坐标位置，表示上游路段第j个交叉路口中心的坐标位置，表示上游路段中的第i条路段中点的坐标位置和上游路段第j个交叉路口中心的坐标位置之间的距离，当满足第一预设准则时，则上游路段在上游路段集合中，即i∈U；当不满足第一预设准则时，则上游路段不在上游路段集合中，即

102：通过预设数据获取待测路段方圆L范围内车流的平均速度

其中，预设数据为某一路段在早高峰时段、午高峰时段和晚高峰时段等时间段内的交通流流量，通过对交通流流量的统计和分析，可以获取到待测路段方圆L范围内车流的平均速度

103：根据平均速度、预测周期获取历史追溯最大周期数m；

C表示预测周期，表示平均速度。

其中，预测周期根据实际应用中的具体应用情况设定，可以设定为5min、10min和15min等，具体实现时本发明实施例对此不做限制，本发明实施例以5min为例进行说明。

104：根据上游路段集合U和历史追溯的最大周期数m获取初始状态向量；

{V_i(t-m)，V_i(t-m+1)，L，V_i(t)}，i∈U+{f}

105：根据初始状态向量的维数M确定粒子的编码长度；

其中，初始状态向量的维数M＝(s+1)(m+1)，s表示上游路段号集合中的元素个数。

106：设定粒子数为Z，随机产生Z个粒子；

其中，每个粒子的维数为初始状态向量的维数M。

107：定义适应度函数F，根据适应度函数F获取Z个粒子的适应度；

F(VAR，ARE，PER，EC)＝λ₁EV+λ₂ARE+λ₃/PER+λ₄/EC

其中，EV表示预测误差的方差，表示预测算法的鲁棒性；ARE表示平均相对误差，表示预测算法的整体性能；PER表示预测相对误差在区间[0，α]之间的百分数，表示预测效果的个体性能；EC表示均等系数，表示整体预测效果的好坏；λ₁表示EV的权重、λ₂表示ARE的权重、λ₃表示PER的权重、λ₄表示EC的权重，α表示预测相对误差。λ₁、λ₂、λ₃和λ₄的取值根据实际应用中的情况来确定，通过对λ₁、λ₂、λ₃和λ₄的调节来调整EV、ARE、PER和EC在适应度函数F中所占的比例，α通常的取值范围为20％或30％。

适应度函数F表示粒子的适应度，适应度函数F值越小显示粒子的适应性越强，其优良基因越有可能遗传到下一代。在每一次迭代过程中，每个粒子通过跟踪两个极值来调节自己，从而使得自己越来越适应自己生存的环境，一个是粒子本身所能找到的个体极值，另一个是整个粒子群目前所能找到的全局极值。参见图4，该步骤具体包括以下步骤，详见下文描述：

1、定义当前预测周期流量状态模式CM；

CM＝[V_s(t-m)V_s(t-m+1)LV_s(t)LV_f(t-m)V_f(t-m+1)LV_f(t)]1_×M

2、对粒子的编码和当前预测周期的流量状态模式做点乘运算，获取当前流量状态模式CM^*；

其中，本发明实施例以二进制编码为例进行说明，粒子的二进制编码为particle＝[1 0 L 1 L 1 0 L 0]1_×M，将particle与CM中每条状态模式做点乘运算，获取当前流量状态模式：CM^*＝[V_s(t-m)0LV_s(t)LV_f(t-m)0L0]_1×M。

3、对粒子的编码和历史数据库的流量状态模式HM做点乘运算，获取当前历史数据库流量状态模式HM^*；

HM＝{V_ih(t-m)，V_ih(t-m+1)，LV_ih(t)}_H×M，i∈U+{f}

${\mathrm{HM}}^{*}={\left(\begin{array}{ccccccccc}{V}_{1s}(t-m)& 0& L& V_{1s}\left(t\right)& L& V_{1f}(t-m)& 0& L& 0\\ V_{2s}(t-m)& 0& L& V_{2s}\left(t\right)& L& V_{2f}(t-m)& 0& L& 0\\ M& M& & M& & M& M& & M\\ V_{\mathrm{Hs}}(t-m)& 0& L& V_{\mathrm{Hs}}\left(t\right)& L& V_{\mathrm{Hf}}(t-m)& 0& L& 0\end{array}\right)}_{H\times M}$

其中，H为历史数据库的流量状态模式的条数，h∈[1，H]，将particle与HM中每条状态模式做点乘运算，获取当前历史数据库流量状态模式HM^*。构建的历史数据库容量足够大且具有代表性，即历史数据库中包含了各类交通状态变化趋势和典型规律，当前采集的实时数据模式都能在其中找到与之相似的历史数据模式。

4、根据当前流量状态模式CM^*和当前历史数据库流量状态模式HM^*通过K近邻匹配和等权重预测对当前预测周期的下一周期流量进行预测，获取第一预测误差，以第一预测误差作为当前粒子的适应度。

108：根据Z个粒子的适应度获取粒子的个体极值和全局极值；

其中，每个粒子的适应度最小的值作为每个粒子的个体极值，Z个个体极值中最小的值作为全局极值。

109：将Z个粒子的编码分别与个体极值对应的编码、全局极值对应的编码进行交叉操作、根据预设概率进行变异操作，获取全局最优粒子；

其中，该步骤具体为：定义单点交叉算子，根据定义后的单点交叉算子将Z个粒子的编码分别与个体极值对应的编码、全局极值对应的编码进行交叉操作。将Z个粒子的编码分别与个体极值对应的粒子编码进行交叉操作可以使得每个粒子都能继承自己的较优部分基因。将Z个粒子的编码分别与全局极值对应的粒子编码进行交叉操作可以使得每个粒子都能继承粒子群的最佳部分基因。定义变异算子，2个父代个体的编码进行重组之后可能会存在子个体的变异，子个体以预设概率发生转变。具体实现时，首先在子个体组成的群体中随机选择一个子个体，对于选中的子个体以预设概率随机改变子个体中某一位编码的值。同生物界一样，GA中变异发生的概率很低，通常预设概率取值在0.001-0.01之间，变异为新子个体的产生提供了机会。

粒子的编码方式有多种，可以采用二进制编码、实数编码等，本发明实施例优选采用二进制编码，0代表状态向量分量对预测结果没有显著影响；1代表状态向量分量对预测结果有显著影响，经过PSO-GA混合智能算法迭代后，得到最优的二进制编码个体。其中，根据初始状态向量的维数定义父代个体的位数，随机产生父代个体的交叉点p，交叉点p的范围为[1，M-1]，在交叉点p进行父代个体1的高p位和父代个体2的高p位的交换。例如：初始状态向量的维数M等于9，可以定义父代个体1为101011101；父代个体2为010101010；交叉点p的范围为[1，8]，当交叉点位置p＝5时，在交叉点5进行父代个体1的高5位和父代个体2的高5位的交换，交叉后生成两个子个体，分别为：子个体1：010101101；子个体2：101011010。对于二进制编码的子个体而言，变异意味着某一位上的值发生翻转。对于每个子个体，具体哪一位上编码的值改变是随机的，例如：变异前的子个体为：010101101，若第四位发生了变异，则变异后的子个体为：010001101。为了防止收敛到局部最优解，预设概率需满足是线性递增的，预设概率具体的取值根据实际应用中的具体应用情况设定，具体实现时本发明实施例对此不做限制。

110：判断是否达到预设次数，如果是，输出全局最优粒子；如果否，重新执行步骤107。

其中，预设次数根据实际应用中的情况具体设定，本发明实施例对此不做限制，通常预设次数为2000左右。

111：将全局最优粒子和初始状态向量做点乘获取状态向量。

综上所述，本发明实施例提供了一种非参数回归短时交通流预测中状态向量的选取方法，在高峰时段、平峰时段、低峰时段和全天候四种情况下采用本发明实施例提供的方法提高了预测精度、稳定性、速度和可移植性，验证了本发明实施例提供的方法有效性和必要性。

下面采用一个试验来验证本发明实施例提供的非参数回归短时交通流预测中状态向量的选取方法的可行性，详见下文描述：

本文采用的交通数据来自明尼苏达德卢斯大学(University of Minnesota Duluth，http://www.d.umn.edu/tdrl/traffic/)。为了验证本文提出的PSO-GA算法在离线分析过程中搜寻最优状态向量的有效性和必要性，将预测效果与没有经过PSO-GA算法进行离线分析的预测效果在不同交通状况下进行对比，对比预测效果如表1所示，对比预测结果参见图5、图6、图7和图8。

表1

从表1中的试验数据，可以通过对EV、ARE、PER和EC等数据的分析，验证了本发明实施例的可行性。从图5、图6、图7和图8中对经过本发明实施例提供的方法、现有技术中的方法得到的直接预测结果以及路段实际值三者之间的比较，可以获知本发明实施例提供的一种非参数回归短时交通流预测中状态向量的选取方法的可行性，提高了预测精度，得到了较好的预测效果，满足了实际应用中的需要。

本领域技术人员可以理解附图只是一个优选实施例的示意图，上述本发明实施例序号仅仅为了描述，不代表实施例的优劣。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。