基于支持向量机的高速公路事件检测算法

1、基于支持向量机的高速公路基于支持向量机的高速公路事件检测算法事件检测算法 体系结构体系结构绪论（研究背景、研究现状、研究意义、研究内容）高速公路交通流特性分析高速公路事件检测算法（ Automatic Incident Detection, AID）研究统计学与支持向量机(Support Vector Machine，SVM)理论基于支持向量机的事件检测算法设计总结与展望高速公路事件是指非周期性发生且使某段道路通行能力下降的事件, 它分为不可预测类（货物散落、车辆抛锚、交通事故等）和可预测类（如大型活动、道路修筑、路面养护等）。本文研究的交通事件是指不可预测的各种突发交通事件。 一、国内外发展

2、现状一、国内外发展现状 1.1 1.1 国外研究现状国外研究现状经典算法：经典算法： California算法、（双）指数平滑算法、McMaster算法、 Bayesian算法、高占有率算法、自回归移动平均法、Monica算法 UCB算法等 SND算法、非参数回归算法、时间序列ARIMA算法、Dutch算法等先进的事件检测算法先进的事件检测算法：模糊逻辑理论、小波分析方法、基于神经网络方法、基于视频图像处理技术的事件检测算法。 国内对交通事件检测算法的研究主要集中在近些年来发展起来的新技术和新理论的应用研究方面。包括小波变换、神经网络、模糊理论、支持向量机以及基于视频图像处理的交通事件检测算法

3、研究。1.2 1.2 国内发展现状国内发展现状良好的事件算法应该是快和准的算法，目前主要的衡量指标有三个，即检测率（TP）、误报率（FAR）、平均检测时间（MTTD）。检测率越高越好，误报率越小越好，平均检测时间越短越好。在实践中，通常是先设定一个可接受的误报率，在满足这个要求的前提下，检测率越高，平均检测时间越短的AID算法，性能越好 1.3 1.3 算法性能指标算法性能指标100%pfEDRE100%etAFARA11( )( )NiMTTDTI iAT iN检测率是指使用某事件检测算法时，在一定时间内，所检测到的事件数与实际发生的引起通行能力下降的总事件数的比值 误报率是指在一定时间内，

4、误报事件的次数与总决策数（事件决策和非事件决策）的百分比 平均检测时间是指在一定时间内，从事件发生到被算法检测到的时间差的平均值 到目前为止，从已开发的高速公路事件检测算法中，并没有一种算法的成效完全优于其它算法，不同的算法只是在不同的情况下其性能优越。利用人工神经网络训练数据进行事件检测有一定的优势，但是需要大量数据进行训练才能使其具有好的移植性。视频图像处理应用于AID是近年来的新技术，然而，需要设置密集的摄像机，导致需要较高的资金投入。基于上述原因，有必要研究经济方便、而且泛化能力好的事件检测算法。 1.4 1.4 研究意义研究意义 支持向量机( Support Vector Machi

5、ne，SVM) 是建立在统计学习理论的基础上, 是针对结构风险最小化原则提出的, 具有很好的泛化能力。SVM使用核函数巧妙地将非线性空间转化到线性空间，避免了复杂的计算， 而且它适用于小样本学习，已在模式识别、回归分析、函数逼近、信号处理等领域得到了成功的应用。 正是基于SVM上述优点，我们将SVM引入到事件检测中，试图设计出一种泛化能力好，各项评价指标（检测率、误报率、平均检测时间）理想的事件检测算法。基于上述分析，本文采用SVM技术开展基于SVM的AID算法研究。通过深入分析高速公路交通流的运行特性，挖掘交通事件条件下交通参数的变化特征，选择合适的交通参数作为SVM的特征向量，构建基于线性

6、不可分支持向量机线性不可分支持向量机、高斯径向基核函数、双曲线正高斯径向基核函数、双曲线正切核函数切核函数的事件检测算法。1.5 1.5 研究内容研究内容二、二、 事件条件下的高速公路交通流特性分析事件条件下的高速公路交通流特性分析一般情况下，采用速度、流量和占有率等表征交通流特性。 这些参数的变化规律基本上反应了交通流的运行状态。交通事件检测的基本原理是通过实时监测道路上不同位置的交通流参数变化值来加以识别。若变化程度超过了预先设置的交通异常门限值，则判定为交通事件发生。图图2-1 事件对交通流的影响事件对交通流的影响3.1 3.1 发展历史发展历史 支持向量机(Support Vector

7、 Machine，SVM)是在统计学习理论的基础上发展起来的，是由Vapnik与其领导的贝尔实验室的研究小组一起开发出来的一种新的机器学习技术，它是统计学理论中最年轻的部分。其主要内容是在1992-1995年间才基本完成。目前仍处在不断发展的阶段。 三、支持向量机理论三、支持向量机理论 3.2 3.2 分类问题的数学表示分类问题的数学表示 已知：已知：训练集包含 个样本点： 问题问题：对一个新的输入 ，找到实值函数g(x),推断它所对应的输出 是1还是-1.决策函数决策函数：f(x)=sgn(g(x)实质：实质：找到一个把 上的点分成两部分的规则.l11(,),(,)()lllTxyxyyxx

8、ynR SVM分类问题大致有三种：线性可分问题、线性不可分问题、非线性可分问题。图图3-1 线性可分情况线性可分情况图图3-2 线性不可分情况线性不可分情况图图3-3 非线性可分情况非线性可分情况 3.3 SVM三种分类问题三种分类问题 3.4 最优分类面、最大间隔原则最优分类面、最大间隔原则0H1H1H)1w xb（()0w xb()-1w xb2ww3.4.1 线性可分支持向量机线性可分支持向量机 对于任意 ： ()11()11iiiiw xbyw xby gg()1iiyw xbg( ,)iix y将上述两式合并可得：2w最大间隔原则min w21min2w2,1min| , (3.1)

9、2s.t.() 1,1, (3.2)w biiwyw xbil L 说明：说明：只要我们求得该问题的最优解 ，从而构造分类面 ， 求出决策函数 。上述方法考虑的是二维空间的分类问题。但对一般 上的分类问题也适用.nR*,w b*()0wxb*( )sgn()f xwxb线性可分SVM求解最优分类面的原始问题原始问题11111min2. .0,0,1llli jijijjijjliiiiyyx xstyil （3.3）*1liiiiwyx*1ljiiijibyy ax x构造分类面 , 决策函数*()0wxb*( )sgn()f xwxb线性可分SVM求解最优分类面的对偶问题对偶问题3.4.2

10、线性不可分支持向量机线性不可分支持向量机1lii1,Tl软间隔软间隔：在被错分的样本数目最少的情况下构造最优分类面。引入松弛变量 软化最大间隔的要求。约束条件约束条件：0i1iiiyw xb 体现了训练集被错分的情况，可采用 作 为一种度量来描述错分程度。1lii两个目标两个目标：1. 间隔 尽可能大 2. 错分程度 尽可能小2w0C 2, ,11min 2. ()1,1, 0,1,liw biiiiiwCstyw xbilil 为避免 过大，需要引入一个惩罚参数 对它们进行惩罚 ，新的目标函数变为:（3.4）原始问题原始问题i线性不可分SVM求解最优分类线的对偶问题对偶问题：*1liiiiw

11、yx*1ljiiijibyy ax x构造分类面 ,决策函数*()0wxb*( )sgn()f xw xb111l1i 1min 2. . 0 0,1,lllijijijjijjiiiy yx xstyC il （3.5）3.4.3. 非线性可分支持向量机非线性可分支持向量机 非线性可分SVM问题的基本思想是：引入一个从输入空间 到高维特征空间 的变换 ： ，那么训练集 就转化成了： , 比较两个训练集：nRZ( ) x( )xnXRZZ 11( ,),.( ,)llTx yx y1122( (),),( (),),( ( ),)llSxyxyxy11111min( ( )()2. . 0,0

12、,1,2,lllijijijiijiliiiiy yxxstCyi ,l.引入核函数 ，上式变为：( ,)( )()ijijK x xxx11111min( ,)2. . 0,0,1,2,lllijijijiijiliiiiy y K x xstCyi,l. 采用不同的核函数，可构成不同的SVM模型。 目前，在分类问题方面常用的核函数主要有：多项式核函数多项式核函数： d为阶数高斯径向基核函数高斯径向基核函数： 双曲线正切核函数双曲线正切核函数： ， 本文采用线性不可分SVM、高斯径向基核函数、双曲线正切核函数三种模型，设计了不同的AID算法，并进行对比分析。 ( ,)()1,0,diiK x

13、 xx x2( ,)exp,0iiK x xxx( ,)tanh()iiK x xx xc0 四、四、 基于基于SVM的的AID算法设计算法设计 4.1 基于基于SVM的事件检测基本原理：的事件检测基本原理： 首先基于高速公路交通特性选取具有典型特征的交通参数， 由这些交通参数组成一定维数的特征向量。 将特征向量输入到SVM中进行优化计算，依据最大间隔原理 实现分类，从而达到最终的事件检测目的。4.2 基于基于SVM的事件检测的事件检测 基本步骤：基本步骤：根据不同的数据子空间、支持向量机模型和核函数寻找相对应的最优参数上游检测点的t、t-1、 t-2、 t-3、 t-4时刻测得的流量、速度、

14、占有率；下游检测点的t、t-1、 t-2时刻测得的流量、速度、占有率。4.3 交通参数选择交通参数选择SVM共有24个输入。将有事件发生的特征向量标识为1，将无事件发生的特征向量标识为-1。输出节点数为1个，输出值为+1时，代表事件状态，输出值为-1时，代表无事件状态。 采用美国加州I-880数据库，I-880数据库是美国Berkeley大学Freeway Service Patrol Project这个项目所采集的数据，其采集路段为美国加利福尼亚州圣弗朗西斯科海湾地区的I-880高速公路9.41英里的路段，这段路段上北向共有环形线圈18组，南向共有环形线圈17组，车道数为3-5个。采集到的原

15、始数据包括环形线圈数据集、移动车数据集、事件数据集。4.4 数据来源：数据来源：事件数据集由移动车采集，移动车采集数据从每个工作日的早上6：30到9：30，下午3：30到6：30，主要有3-4辆浮动车在测试路段来回巡逻，当遇到有交通事件时，将交通事件数据例如南向还是北向交通事件、事件发生的时间地点等信息报告给指挥中心；将得到的数据划分为训练集、测试集。 环形线圈的采集时间是每天从早上5点到10点，下午2点到8点，采集的数据包括每个车道的速度、流量、占有率；I-880数据库高速公路环形线圈布置图（数据库高速公路环形线圈布置图（P42）4.5 SVM模型及核函数的选择：模型及核函数的选择： 由于不

16、同的SVM模型、不同的核函数及其参数、不同的数据空间，都影响着算法的性能指标。也即模型选择的不同以及核函数的选取不同，即使相同的数据集，检测效果仍然不一样。 对于模型的参数选择，在具体使用中，目前主要采取以下两种参数优化方法：k-折交叉验证法和网格搜索算法。k-折交叉验证法：首先把 个样本点随机地分成互不相交的k个子集，即k-折 。每个折的大小大致相等，共进行k次训练与测试，即对 进行k次迭代，第 次迭代的做法是，选择 为测试集，其余的合集为训练集，算法根据训练集求出决策函数之后，即可对测试集进行测试。 网格搜索算法：从不同的增长方向并行搜索多维数组：选定一组 的范围，如： ，搜索步长为-1;l12,kS SS,iS1,i ,kiC、10152 2 ，搜索步长为1；这样在 坐标系上构成一个二维网格。对应网格上每一组的值 ，按照交叉验证方法计算出样本预测准确率，从中选择一组使得预测准确率最高的值作为最优参数。 本文采用网格搜索算法并且对每组给定的参数采用5-折交叉验证，通过取不同的参数范围反复实验，最终获得分类效果最优的一组参数。 15102 2CC、