基于TAN分类算法的交通事件检测*

凃 强 李大韦 程 琳

(东南大学交通学院 南京 210096)

0 引 言

交通拥堵是全世界大多数城市都面临的难题，它可以分为2类：复发性拥堵和非复发性拥堵。复发性拥堵由过度交通需求产生，短时间内难以改善；而非复发性拥堵通常由道路上的偶发性事件引起，比如交通事故，故障停车等，如果不及时处理，会造成巨大损失。事件管理系统(IMS)能够及时对事件进行处理，减少后续影响，是先进的交通管理系统的重要组成部分。作为事件管理系统的核心技术，事件检测算法是一个十分有价值的研究课题。

事件检测算法根据不同的方法通常被分成5类：比较算法、统计学算法、时间序列及滤波算法、交通理论算法和先进算法。加州算法是比较算法的经典例子，也是首次广泛实现的事件检测算法之一[1]，通常用来作为评估其他算法的基准。统计算法使用标准的统计技术识别交通流参数的突变，包括标准正太偏差算法[2]和贝叶斯算法[3]。时间序列和滤波算法将交通量参数作为时间序列，用时间序列偏差行为来表明事件，其中包括移动平均[4]和平滑指数算法[5]。交通理论的经典算法是McMaster算法，它是基于交通流密度曲线中的位置决定交通状态，然后根据从一个状态到另一个状态的转移来检测事件[6]。先进算法是基于先进的数学模型，如神经网络[7-8]、模糊聚类[9]、支持向量机[10]等方法，这些算法在实验室环境均有良好的表现。

为了满足先进交通管理系统的普遍性需求，贝叶斯网络被用来开发通用算法[11]。测试结果表明，基于贝叶斯的算法具有稳定的性能和很强的可转化性。目前，国内将贝叶斯网络应用于交通事件检测的研究相对较少，采用的方法主要是基于贝叶斯网络或朴素贝叶斯(NB)分类算法[12-14]。但是，基于贝叶斯的算法比较依靠专家经验，比如，它的网络结构需要人为设定。朴素贝叶斯分类算法，作为普通贝叶斯算法的改进，不需要人为设定网络结构，但算法中包含了许多严格的假设，比如，假设所有变量之间是严格独立的。

本文采用了贝叶斯网络的一个特殊形式，树增强朴素贝叶斯分类器，用来作为事件检测算法，它的网络结构和参数均是由数据学习确定的，可以有效减少对专家知识的依赖，同时考虑了变量之间的相关性，相比贝叶斯网络和朴素贝叶斯分类算法具有更好的应用前景。

1 TAN分类器简介

1.1 贝叶斯网络

贝叶斯网络是由随机变量集合组成的联合U={X1,X2,…,Xn}概率分布的编码，形式上是一对二元数组B=(G,θ)。G是有向无环图，其节点对应随机变量X1,X2，…,Xn，有向边代表变量之间的相依性。图的结构G编码了独立性假设：在给定每个节点父节点的条件下，该节点独立于它的非自子孙节点，二元组的第二部分代表这个网络每一个变量条件概率分布的集合，集合中元素为，其中xi⊆Xi, 且Πxi⊆ΠXi表示Xi在G中的父变量集。B在U上定义了唯一的联合概率分布

PB(X1,X2,…,Xn)=

(1)

贝叶斯网络用于事件检测，它必须包含分类变量INC，和属性变量A1,A2，…，An。A1,A2，…，An代表交通流参数，INC=1表示事件发生。在IMS中，实时更新，并用贝叶斯网络对P(INC=1|A1,A2，…，An)进行更新。

因为假设独立，贝叶斯网络用于事件检测时，分类变量INC必须与属性变量建立联系，每个属性变量信息均可以用来更新事件的可能性。由于贝叶斯网络的结构学习本身是1个NP问题，不能搜索整个网络空间，现有研究中，主要依靠专家经验确定其结构。图1(a)展示了1个可能的贝叶斯事网络结构。

图1 贝叶斯网络、朴素贝叶斯和树增强朴素贝叶斯分类器典型结构Fig.1 Typical structures of Bayesian network,NB classifier and TAN classifier

1.2 树增强朴素贝叶斯分类器

为了确定贝叶斯网络的结构，需要解决如何添加属性变量的边。解决这个问题最简单的方法是假设每个属性变量之间都是相互独立的，此时不需要为每对属性变量建立边。这种形式的贝叶斯网络经常用于NB分类器，其结构见图1(b)。

树增强贝叶斯分类器是一类基于NB分类器的网络结构，见图1(c)，分类变量INC没有父节点，每个属性变量含有1个分类变量和至多1个属性变量作为父节点。这表明，概率P(INC|A1,A2,…,An)将所有的属性变量纳入考虑，NB分类器中每个变量相互独立的假设得到松弛，属性变量之间的边可以用训练数据获得。

2 TAN分类算法

2.1 数据预处理

交通系统检测器收集的交通特征参数通常包括：交通流量、占有率和速度等。这些交通数据均是连续的，并且其值域和单位都不相同。此外，驾驶员行为的随机性和检测器的测量误差导致原始交通数据存在一定的随机波动。因此，需要对原始交通数据进行一定预处理，才能应用于检测算法中。对原始数据的预处理流程包含3个部分：数据平滑、标准化和离散化。

1) 数据平滑。数据平滑处理是为了消除原始检测数据的随机波动。现有研究中，采用的方法主要是移动平均的方法，这种方法虽然简单易用，但是在处理交通事件突发的临界区间时过于平滑，会增加平均检测时间。为了克服这一缺点，采用小波去燥的方法对原始数据进行平滑处理，本文直接使用Matlab小波工具箱进行数据的平滑处理。

2) 标准化。小波去噪过后，需要对去噪交通数据进行标准化，将不同单位和值域的交通参数转化到同一量纲区间内，标准化过程主要是为了提高算法的可转让性，其采用公式见式(2)

(2)

式中：a′为标准化交通数据；a为去噪交通数据；Aα和Aβ分别为去噪交通数据的最小值和最大值。

3) 离散化。TAN分类器中的属性变量应为离散变量，因此，需要将连续交通数据进行离散化处理。现有的研究方法，主要是根据专家经验预设分界点，从而将连续的交通数据划分到不同区间进而到达离散化的效果。为了克服对专家经验的依赖，采用基于熵的方法对标准化交通测量值进行离散化处理，本方法选择训练数据集最小熵值作为分界点，进行递归分区以达到分层离散化，具体步骤如下[15]。

步骤1。根据测量值A的属性取值情况，分成m个区间，并给定类信息熵的阈值ξ，第i个区间的区间类信息熵的计算见式(3)。

(3)

式中：pij是区间i中类别为j的概率，可见区间i中包含的类别越小，Entropy(Ai)越小，表示该区间的离散化效果越好。

步骤2。合并所有相邻、区间类信息熵为0且区间属性类别相同的区间，计算所有的相邻区间合并后的区间类信息熵，将区间类信息熵最小和不超过ξ的相邻区间进行闭合，一直重复，直到找不到可以合并的相邻区间；

步骤3。对离散化后的属性值进行数字编号。

2.2 检测算法

通过数据预处理，将交通事件作为0-1分类变量，交通特征参数作为属性变量，从而将交通数据应用到TAN分类算法中。交通事件inc的发生与否采用0-1变量进行表示，inc=0表示“不发生”，inc=1表示“发生”，其向量形式记为INC；类别为i的交通特征参数属性变量为ai，其向量形式为Ai，i∈(1,2,…，n)；训练数据dk可以表示为{a1,…，an,inc}，一共m组数据，相应的训练数据集为D={d1，d2,…,dm}={A1,A2,…，An,INC}。

2.2.1 学习和推理

在1.2中，TAN分类器的网络结构并没有明确给出，它需要通过对训练数据的结构学习和参数学习获得，TAN的网络结构和参数学习过程如下[16-17]。

步骤1。计算交通特征属性变量(Ai,Aj)两两之间的条件相互信息MI(Ai,Aj|INC)。

MI(Ai,Aj|INC)=

(4)

步骤2。对所有交通特征属性变量{A1,A2,…,An}，两两之间建立以Ai-Aj为弧，权重为MI(Ai,Aj|INC)的完全无向图。

步骤3。建立最大权重生成树。

步骤4。选择任一变量作为根节点，设置向外连接方向，将无向树转换为有向树。

步骤5。增加分类变量INC节点和它到每个属性节点的有向连接，构造TAN的网络结构。

步骤6。参数学习，采用极大似然估计算法对参数θ进行估计

(5)

采用联合树算法对后验概率P(INC=1|A1,A2,…,An)进行推理计算，其基本思想是将贝叶斯网络结构图转换为一个连接树，通过信息传递进行计算，信息依次传遍连接树中的所有节点，并最终使连接树满足全局一致性。此处，可以直接使用Matlab中的贝叶斯网络工具箱(BNT)进行相应的推理计算，因此，不再对其过程进行详细说明。

2.3.2 事件发布

在事件管理系统中，实时输入交通特征属性变量{A1,A2…,An}，推理计算得到后验概率，即交通事件发生的概率P(INC=1|A1,…,An)。如果直接将后验概率与预定义的阈值进行比较，会导致误报率(FAR)较高，因此，采用一个平滑的方法，减少误报率[18]。

(6)

3 实验案例

3.1 数据描述

数据集是新加坡艾耶尔国王高速公路(AYE)数据集，该数据来自于1个交通仿真系统，在其他交通事件检测论文中也得到了应用[19]。仿真系统在路段上游和下游生成交通量、占有率和速度数据，AYE数据集模拟了300个事件的交通数据集，每个事件包含3部分：10 min事件预热;10 min事件持续;30 min事件消散。数据集被分成2个部分，训练数据集和测试数据集。每个数据集包括对应事件状态的3 000个输入和对应无事件状态10 500个输入。以30 s为间隔，每个输入部分包含交通量、速度、道路占有率和事件状态标签。

为了建立TAN分类器事件检测模型，首先要确定模型中包含的变量。通过数据集内容和现有研究，选取了8个变量作为TAN分类器节点，见表1。

表1 TAN分类器中的变量描述Tab.1 Description of Variables Containedin The TAN Classifier

3.2 数据预处理

3.2.1 小波去噪

采用Matlab中的小波工具箱对原始交通数据进行去噪处理，分解水平越高，去噪效果越好，但是也会增加计算时间和失真程度。划分1～5共5个分解水平，将原始交通数据(包括训练数据和测试数据)进行小波去噪，通过实验，本文中最优的分解水平是3，见图2。

图2 分解水平为3的小波去噪结果Fig.2 Wavelet denoising results at level 3

3.2.2 标准化

根据去噪后的训练数据集，可以得到式(2)中的Aα和Aβ，其结果见表2，训练和测试数据集都将按照式(2)进行标准化。

表2 由训练数据集得到的公式2中Aα和Aβ取值Tab.2 The values of Aαand Aβin equation 2 according to training dataset

3.2.3 离散化

采用2.1中基于熵的离散化处理，可以用训练数据得到分界点，见表3。通过比较交通特征参数与分界点的值，将训练数据和测试数据离散化，所有的交通特征参数将被划分为3个状态。

表3 TAN分类器中连续变量分界点

3.3 结构学习

使用贝叶斯网络，通过学习预处理数据，可以得到用于交通事件检测的TAN分类器结构，见图3。

图3 TAN分类器结构Fig.3 The structure of the TAN classifier

下面以节点Qu为例，得到的参数概率表见表4。

表4 Qu参数表Tab.4 The Parameters of Qu

3.4 实验结果

图4 TAN分类器事件检测算法的1个典型输出Fig.4 A typical output of TAN classifier basedincident detection algorithm

交通事件检测存在4种可能结果：无事件正确检测、有事件正确检测、无事件误报和有事件漏检。本文采用检测率(detection rate，DR)，误报率(false alarm rate，FAR)和平均检测时间(mean time to detection， MTTD)3个指标评估TAN算法性能。为了更好的体现TAN算法的性能，本文还采用贝叶斯网络(BN)算法和多层前馈神经神经网络(MLF)算法作为对比算法[19]，其测试结果见表5。

表5 TAN和MLF算法性能比较Tab.5 Comparison between TAN and MLF with AYE data

根据表5的结果，TAN算法比BN算法具有更好的性能，同时TAN算法的平均检测时间和误报率会稍高，这是由于TAN算法的网络结构和参数是由数据学习得到的，而BN算法是基于专家经验得到的。值得注意的是，BN算法性能也依赖专家经验，如果专家经验对网络结构和参数的标定较差，输出结果性能也会较差，相比之下，TAN算法的性能具有更好的稳定性。对比MLF算法，TAN算法的检测率稍低，但它的误报率也更低，当TAN算法阈值设置为0.5时，两种算法的平均检测时间相当。然而，MLF在理论上比TAN算法更复杂：MLF是一个黑盒模型，其内在原理较为复杂，难以解释；而TAN分类算法是概率和统计理论，更容易理解。另外在数据训练上，MLF网络需要更多的数据和时间，本研究中MLF的平均训练时间达到344.7 s，而TAN算法的训练时间仅需要2 s。综上所述，TAN事件检测算法相比MLF算法具有一定的优势，将会得到更加广泛的应用。

4 结 论

贝叶斯网络检测算法在性能和转换性方面有着优势，但对专家的经验要求较高，为了减少对于专家经验的依赖，提出了TAN事件检测算法，通过数据学习得到TAN网络结构和参数，采用基于熵的方法对检测数据进行离散化处理，并用新加坡艾耶尔国王高速公路的仿真数据证实了TAN分类算法的性能。

将TAN算法与BN算法和MLF算法进行性能对比，实验结果显示TAN算法优于BN算法，其性能稍逊于MLF算法，但TAN算法在模型训练和标定方面有着更快的速度，同时TAN算法相对MLF算法更加容易理解，因此TAN算法具有更广泛的应用前景。此外，TAN分类算法能更合理的满足现实需求，包括初始训练数据需求和处理不同监测系统设计和技术的灵活性。

由于缺乏合适的数据集，本文没有对TAN算法的转移性进行评估，将来应该对TAN算法进行更加全面和详细的评估。在接下来的研究中，我们将采用先验分布或者动态TAN分类器，提高算法处理连续交通流参数变量的能力。