英语原文共 8 页

一种基于AVL和AKNN技术的两级短时交通流预测方法

摘要：

短期交通流量预测是智能交通系统中的重要问题之一。我们提出了一种结合了先进k-最近邻域（AKNN）方法和平衡二叉树数据结构（AVL）以提高预测精度的新的两阶交通流量预测方法：AKNN-AVL法。AKNN方法在一次识别过程中使用两次模式搜索，其中考虑了以前的流量序列来预测未来的流量状态。采用聚类方法和平衡二叉树技术建立案例数据库，减少了搜索时间。为了说明这些发展的影响，对AKNN-AVL法和AKNN法的准确度以及对自回归法和移动平均法进行了比较。这些方法由在正常和事故的交通条件下的北京北3环公路附近的高速公路交通探测器提供的实时数据校准和计算。比较表明，最优邻域和模式尺寸的AKNN-AVL法的性能优于KNN法和在正常及事故交通条件下的ARMA方法。此外，聚类方法与均衡的组合二叉树技术对预测方法的应用可以提高搜索速度，对案例数据库的波动作出快速响应。

关键词：交通运输系统工程；短期交通流量预测；高级k-最近邻域方法；模式识别；平衡二叉树技术

1导言

短期交通预测显示，随着人们对智能交通系统（its）的兴趣的增加，近年来的研究越来越受到重视。随着交通传感器的大规模应用，每天都可以很容易地获得大量的实时交通数据，如流量、速度和占用率。通过精确的短期交通流量预测，拥有先进旅客信息系统（atis）设备的旅客可以合理地安排自己的活动，而交通管理者可以有效地调整交通管理策略[1minus;4]。

在短期交通流量的研究中，已经有广泛而优雅的预测方法发表。现有的预测方法是在正常流量下以多种方式分类，如参数方法和非参数方法[5]状态方法和异常交通条件下的方法[6]、数据驱动方法和基于模型的方法[7]。本文介绍了郭等人提出的重要分类方法，概述了现有的短期交通预测研究成果。他们将这些方法分为三种：基于交通模型的方法、统计方法和基于数据地雷的方法。一份简短但有代表性的审查报告概述如下：

基于交通模型并使用基本交通流量模型预测交通流量演变规律的方法。交通变量，如交通速度、流量和从宏观和微观两个角度来描述交通流量的密度已经受到了相当的重视。宏观模型集中在基于流体和气体动力学的车辆交通流模拟的交通流预测[8minus;9]。微观模型考虑了车辆的大长度行为，并考虑了网络中车辆之间的相互作用[10]。

统计方法训练数据集，以选择拟合过程中的最佳参数。典型的统计方法已经被提出并应用了多年，如局部线性回归模型[11]，自回归和移动平均（arma）[12]，以及季节性自回归综合移动平均（sarima）[13minus;15]。统计方法由于其简单实用的特点，经常被用来比较新提出的方法的输出。

基于数据挖掘的方法最多作为一种智能方法，近年来得到了广泛的应用，用于探索历史数据的发展趋势。支持向量回归(svr)[16minus;17],k-最近邻居(knn)[18minus;19],神经方法[20minus;22]是最常用的方法,将历史数据与当前条件的相似性进行匹配，以预测未来的状态。

从申请经验来看，基于流量模型的方法和统计方法大多适用于静止时间序列。基于数据的方法具有明显的广泛使用的优点，但不受任何特定的数据类型的影响。每种方法都有优点和缺点，每种方法都适合解决具体问题。

KNN方法，这是一种典型的基于数据挖掘的方法，被发现是一种有效和准确的短期交通流预测方法。实例数据库基础和搜索速度是KNN方法在应用中的两个核心问题。作为一种非参数回归方法，KNN本质上是一种基于模式识别的智能方法。因此，预测性能在很大程度上取决于案例数据库中流量类型的完整性和代表性。然而，即使是一个小案子，流量数据库也是巨大的。例如，汉普顿公路交通便利中心（hrstc）记录了来自弗吉尼亚州203处的634个交通传感器的30公里公路交通数据。该数据库的容量超过18GB，并以每月650mb的速度增长。这些从真实网络收集的流量数据包含不同类型的抽样和非抽样误差[23]。传统的没有预处理的历史数据库，显然包含了太多的冗余来处理。最近的几项研究报告说，适当的预处理程序可以压缩历史数据库，并提高预测性能[24minus;25]。

在KNN方法中与适用《公约》有关的另一个困难是搜索速度。传统的数据库是线性结构，不能满足短期预测的要求[26minus;27]。另一方面，为了提高搜索速度，操作和维护复杂的数据结构是很费钱的。因此，最有意义的方法就是改进现有数据结构的搜索方法。在本文中，我们将平衡二叉树技术（也称为AVL树）与一种名为AKNN-AVL法的先进的KNN方法相结合，提出了一种新的短期交通预测方法。详细的过程将在下一节讨论。

这项工作的主要目的是提出一种新型的短时交通流预测方法，基于平衡二叉树技术的高级k-最近邻法。首先，利用聚类方法和平衡二叉树技术对历史数据库进行了更新。其次，提出了一种高级的k-最近邻法（AKNN）来预测未来的交通流量，该方法在搜索过程中两次使用模式识别来确定邻居大小和模式大小。为了说明AKNN-AVL模型的有效性，它被应用于预测真实的交通流量序列，其中交通数据是从靠近北3环公路的高速公路交通探测器获得的。此外，本文还介绍了传统的k-最近邻法和经典的预测方法——自回归法和移动平均法，以供比较。

2 预测模型

2.1KNN

KNN是一种典型的非参数方法，其中原理是选择K训练样本，在距离测量的光线下寻找k-最近的邻居，例如欧几里得距离。然后，这些选择的k最近的邻居决定下一个实例的类别。基本步骤如图1所示:

图1 KNN方法的结构

给定一个n点流量序列V(1),V(2),...,V(N)每2分钟收集一次，目标是在目前状态V(N)的最近邻域的基础上预测未来状态V(N 1)。此外，当前状态V(N)可以扩散到几个连续值v(N)=[V(Nminus;L),lt;UNKgt;,V(Nminus;1),V(N)]，其中L(1le;Lle;Nminus;1)是模式大小，V(N)是当前时间区间N的交通流，V(Nminus;1)是前一个2分钟时间区间的交通流。在接下来的五个步骤中，可以使用KNN方法：

步骤1：提供一个案例数据库，包括数据和当前数据；

步骤2：确定K的初始值；

步骤3：计算欧几里得之间的距离新的输入和所有的训练数据，并按升序排序；

步骤4：根据离机场最小距离为K案件开发数据库输出K最近的邻居；

步骤5：根据预测函数和预测未来状态计算预测值.

最常见的K值确定方法是从实证分析得到的。首先，设定初始K值，然后通过经验结果不断调整，得到最优K值。预测函数完全与当前状态联系起来来预测未来状态，而不考虑与过去状态的关系。实际上，一个交通系统有一些模式是重复的，交通流量在本质上并不是不规则的。未来状态与当前状态和过去序列[28minus;29]密切相关。基于这一假设，发展了基于KNN方法的AKNN方法。下一节将讨论两项改进。

2.2AKNN

KNN方法有很多优点，例如对嘈杂的训练数据的鲁棒性，如果训练数据大，简单，容易达到，可以得到广泛的应用。但它也有一些缺点如下：1）根据经验确定图案尺寸是不科学的。但是大量的数据分析需要大量的时间，而且不适合实时需求。2）KNN处理从给定的特定电流状态的动态演化。未来的预测应该更多地考虑历史状态，KNN的非记忆性质无法克服这个问题。特别是当交通流量从正常状态演变为拥挤状态时，未来的交通状态可能比目前状态下增长得更快。

针对这两个问题，高级的k-最近邻法(AKNN )被提出。对于第一个问题，模式大小将在迭代过程中作为变量处理，与搜索K值的方法相同。最佳模式大小为通过评价指标获得。对于第二个问题，假设交通流不是完全随机的，它的未来状态可能受到历史状态的影响。这个过程可以看作是一个“模式”，即流量状态会被重复。本文通过引入状态模式向量来描述此模式。givenv(I)=[V(Iminus;L),lt;UNKgt;,V(Iminus;1),V(I)](1le;Ile;Nminus;1)是状态向量，其中L(1le;Lle;Nminus;1)是图案大小。为了描述交通流的变化趋势，差向量c(Iminus;1)=[C(Iminus;L),lt;UNKgt;,C(Iminus;2),C(Iminus;1)]被确定为

c(i)=v(i 1)-v(i),1le;ile;n-1 (1)

例如，如果c(i)lt;0，交通流遵循下降趋势.通过编码为minus;1,0,1来定义三元变量e(i)，以映射交通流量序列的差异，那么，模式向量可以给出为e(I)=[E(Iminus;L),hellip;,E(Iminus;1)]。模式向量描述的三种情况，包括增加(1)、减少(minus;1)和时间序列的静态(0).如果当前状态为x(7)=[X(1),X(2),hellip;,X(7)]，如图2所示向量是[1,1,0,minus;1,1,1]。

图2 状态模式向量的例子

他详细说明了AKNN方法的步骤，提出的方法如下：

步骤1：设置最小邻域大小K=Kmin，并且最小图案长度L=Lmin；

步骤2：使用当前状态向量与历史状态向量寻找基本邻域。对于当前状态向量v(N)=[V(Nminus;L),hellip;,V(Nminus;1),V(N)]，查找交通时间序列V(1),V(2),hellip;,V(N)，通过计算得到状态向量的欧几里得距离。其中v(J)是一个历史状态向量。按升序对状态向量的欧氏距离进行排序，并选择顶部K的匹配邻居。每个最近的邻居标记为J′，对应的状态向量为v(J′)=[V(J′minus;L),hellip;,V(Jminus;1),V(J′)]，以及对应的模式向量为e(J′minus;1)=[E(J′minus;L),lt;UNKgt;,E(J′minus;2),E(J′minus;1)]。

步骤3：e(Nminus;1)是当前状态的模式向量，且e(Jminus;1)是历史状态的模式向量。那么将模式向量的欧氏距离排序为升序。每个最近的邻居都被标记为J，对应的状态向量为v(J)=[V(Jminus;L),hellip;,V(Jminus;1),V(J)]，对应的模式向量为e(Jminus;1)=[E(Jminus;L),hellip;,E(Jminus;2),E(Jminus;1)]，以及对应的差向量是c(Jminus;1)=[C(Jminus;L),hellip;,C(Jminus;2),C(Jminus;1)]。将模式向量从上向下与顶部匹配步骤2中得到的匹配邻居。如果他们在在交通时间序列中的相同位置，然后选择它的位置，直到最好的K匹配被收集。

步骤4：估计值V′(N 1)，即预测V(N 1)，基于K的带有终值的埃伦斯向量的最优邻居。最佳K匹配的状态向量标记为v(J,U)=[V(Jminus;L,U),hellip;,V(Jminus;1,U),V(J,U)], (U=1,2,hellip;,k),和在V(J,U)的旁边的V(J 1,U)

步骤5：在实际值和预测值之间计算根平均平方误差，用于选择邻居大小K和图案大小L。

步骤6：重复步骤2到步骤5，以了解大小模式L=1,2,hellip;,L Max;

步骤7：重复步骤2到步骤6，以了解邻居大小k=1、2、hellip;、kMax；

步骤8：选择最优的L和k对应于最小值；

步骤9：输出最佳预测结果。

2.3 AKNN-AVL的算法框架

如图3所示，用AKNN-AVL方法，使用AKNN方法作为主要预测基于平衡二叉树方法。给与历史的交通传感器收集的数据库，基本流程列出如下。首先，找到聚类中心利用聚类方法建立历史数据库，并提出他们进入了案件数据库。二、立案基于AVL法的数据库。当新的数据在案例数据库中添加了平衡的结构将调整二叉树以保持其平衡。第三，在AKNN的大小写数据库中搜索匹配项方法。所选K的匹配值用于预测未来数据,如果在数据中找不到匹配，则将当前状态向量进入大小写数据库，然后继续回到第二步。

图3 AKNN-AVL的算法框架

最常用的数据结构是线性数据结构，因为计算机的内存是以线性的方式组织,可以方便的进行计算机操作，但这种简单的结构不能满足处理大型数据库时的搜索速度。随着流量数据库的日益庞大，线性数据结构已不能满足实时需要。因此，树木结构被广泛应用于应用程序，用于模拟分层树结构。平衡二叉树(AVL)是自我平衡的二进制搜索树，它可以有效地控制树的高度。在AVL树中，平衡由节点平衡因子决定，其定义为节点在两个子树之间的高度差。每个节点的子树在高度上的差异最多是一个，每个子树都是一个AVL树。因此，所有的AVL中的平衡因子只能是minus;1、0或1；如果不是，这个树必须调整。添加新数据需要要通过一个或多个旋转重新平衡的树。在这里，N是节点数.如果插入是连续执行的，每次插入后，使整个树恢复到规则最多有一种情况需要解决。AVL结构在交通中的应用在下面的实验中比较线性数据结构给出了。

3应用和结果

实验中所有的流量数据是从31003号探测器上获得的，这是一个安装在北京高速公路附近的远程交通微波传感器（rtms）。交通流量数据在24小时内每2分钟回顾一次，并利用日统计算法对缺失数据进行了处理。

3.1参数

两套实验被设计用来校准Aknn-avl法中的参数。在无avl法的前提下计算了第一个实验，确定了aknn过程中的最优邻域大小和模式大小。图5(a)和(b)给出rme不同邻居大小和模式的性能大小。图5选择结果的典型部分显示了rmse的全部变化。从图5(a)改为邻居尺寸K从2增加到10,rmse性能有了显著的提高，但是这个改进大约在K=6点停止。rmse性能将在相同的水平上，当邻居尺寸K继续增加超过K=6。此外，图5(b)显示最佳模式大小为关于L=3.当图案尺寸从3增加到6,rmse逐渐增加。因此，最佳的邻居大小而图案大小为K=6，L=3，用于在此基础上,对该方法进行了实验评价。

图4不同型号邻居的rmse性能以及图案大小

本实验采用三种聚类方法对4000组交通流数据进行聚类;相应的聚类中心编号如表1所示。SC方法的应用效果最好。可见，聚类中心数c随着聚类中心半径r的减小而增大，聚类中心数c在半径0.13 ~ 0.14附近变化最大。

表1聚类中心半径和不同的数字方法

DBSCAN方法除了参数r外，还增加了密度阈值t的参数，CURD方法增加了聚类中心半径r和密度阈值t两个参数。两种方法的参数

资料编号：[5735]