基于支持向量機的高速公路事件檢測算法

1、基于支持向量機的高速公路基于支持向量機的高速公路事件檢測算法事件檢測算法 體系結(jié)構(gòu)體系結(jié)構(gòu)緒論（研究背景、研究現(xiàn)狀、研究意義、研究內(nèi)容）高速公路交通流特性分析高速公路事件檢測算法（ Automatic Incident Detection, AID）研究統(tǒng)計學(xué)與支持向量機(Support Vector Machine，SVM)理論基于支持向量機的事件檢測算法設(shè)計總結(jié)與展望高速公路事件是指非周期性發(fā)生且使某段道路通行能力下降的事件, 它分為不可預(yù)測類（貨物散落、車輛拋錨、交通事故等）和可預(yù)測類（如大型活動、道路修筑、路面養(yǎng)護等）。本文研究的交通事件是指不可預(yù)測的各種突發(fā)交通事件。 一、國內(nèi)外發(fā)展

2、現(xiàn)狀一、國內(nèi)外發(fā)展現(xiàn)狀 1.1 1.1 國外研究現(xiàn)狀國外研究現(xiàn)狀經(jīng)典算法：經(jīng)典算法： California算法、（雙）指數(shù)平滑算法、McMaster算法、 Bayesian算法、高占有率算法、自回歸移動平均法、Monica算法 UCB算法等 SND算法、非參數(shù)回歸算法、時間序列ARIMA算法、Dutch算法等先進的事件檢測算法先進的事件檢測算法：模糊邏輯理論、小波分析方法、基于神經(jīng)網(wǎng)絡(luò)方法、基于視頻圖像處理技術(shù)的事件檢測算法。 國內(nèi)對交通事件檢測算法的研究主要集中在近些年來發(fā)展起來的新技術(shù)和新理論的應(yīng)用研究方面。包括小波變換、神經(jīng)網(wǎng)絡(luò)、模糊理論、支持向量機以及基于視頻圖像處理的交通事件檢測算法

3、研究。1.2 1.2 國內(nèi)發(fā)展現(xiàn)狀國內(nèi)發(fā)展現(xiàn)狀良好的事件算法應(yīng)該是快和準的算法，目前主要的衡量指標有三個，即檢測率（TP）、誤報率（FAR）、平均檢測時間（MTTD）。檢測率越高越好，誤報率越小越好，平均檢測時間越短越好。在實踐中，通常是先設(shè)定一個可接受的誤報率，在滿足這個要求的前提下，檢測率越高，平均檢測時間越短的AID算法，性能越好 1.3 1.3 算法性能指標算法性能指標100%pfEDRE100%etAFARA11( )( )NiMTTDTI iAT iN檢測率是指使用某事件檢測算法時，在一定時間內(nèi)，所檢測到的事件數(shù)與實際發(fā)生的引起通行能力下降的總事件數(shù)的比值 誤報率是指在一定時間內(nèi)，

4、誤報事件的次數(shù)與總決策數(shù)（事件決策和非事件決策）的百分比 平均檢測時間是指在一定時間內(nèi)，從事件發(fā)生到被算法檢測到的時間差的平均值 到目前為止，從已開發(fā)的高速公路事件檢測算法中，并沒有一種算法的成效完全優(yōu)于其它算法，不同的算法只是在不同的情況下其性能優(yōu)越。利用人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練數(shù)據(jù)進行事件檢測有一定的優(yōu)勢，但是需要大量數(shù)據(jù)進行訓(xùn)練才能使其具有好的移植性。視頻圖像處理應(yīng)用于AID是近年來的新技術(shù)，然而，需要設(shè)置密集的攝像機，導(dǎo)致需要較高的資金投入。基于上述原因，有必要研究經(jīng)濟方便、而且泛化能力好的事件檢測算法。 1.4 1.4 研究意義研究意義 支持向量機( Support Vector Machi

5、ne，SVM) 是建立在統(tǒng)計學(xué)習理論的基礎(chǔ)上, 是針對結(jié)構(gòu)風險最小化原則提出的, 具有很好的泛化能力。SVM使用核函數(shù)巧妙地將非線性空間轉(zhuǎn)化到線性空間，避免了復(fù)雜的計算， 而且它適用于小樣本學(xué)習，已在模式識別、回歸分析、函數(shù)逼近、信號處理等領(lǐng)域得到了成功的應(yīng)用。 正是基于SVM上述優(yōu)點，我們將SVM引入到事件檢測中，試圖設(shè)計出一種泛化能力好，各項評價指標（檢測率、誤報率、平均檢測時間）理想的事件檢測算法。基于上述分析，本文采用SVM技術(shù)開展基于SVM的AID算法研究。通過深入分析高速公路交通流的運行特性，挖掘交通事件條件下交通參數(shù)的變化特征，選擇合適的交通參數(shù)作為SVM的特征向量，構(gòu)建基于線性

6、不可分支持向量機線性不可分支持向量機、高斯徑向基核函數(shù)、雙曲線正高斯徑向基核函數(shù)、雙曲線正切核函數(shù)切核函數(shù)的事件檢測算法。1.5 1.5 研究內(nèi)容研究內(nèi)容二、二、 事件條件下的高速公路交通流特性分析事件條件下的高速公路交通流特性分析一般情況下，采用速度、流量和占有率等表征交通流特性。 這些參數(shù)的變化規(guī)律基本上反應(yīng)了交通流的運行狀態(tài)。交通事件檢測的基本原理是通過實時監(jiān)測道路上不同位置的交通流參數(shù)變化值來加以識別。若變化程度超過了預(yù)先設(shè)置的交通異常門限值，則判定為交通事件發(fā)生。圖圖2-1 事件對交通流的影響事件對交通流的影響3.1 3.1 發(fā)展歷史發(fā)展歷史 支持向量機(Support Vector

7、 Machine，SVM)是在統(tǒng)計學(xué)習理論的基礎(chǔ)上發(fā)展起來的，是由Vapnik與其領(lǐng)導(dǎo)的貝爾實驗室的研究小組一起開發(fā)出來的一種新的機器學(xué)習技術(shù)，它是統(tǒng)計學(xué)理論中最年輕的部分。其主要內(nèi)容是在1992-1995年間才基本完成。目前仍處在不斷發(fā)展的階段。 三、支持向量機理論三、支持向量機理論 3.2 3.2 分類問題的數(shù)學(xué)表示分類問題的數(shù)學(xué)表示 已知：已知：訓(xùn)練集包含 個樣本點： 問題問題：對一個新的輸入 ，找到實值函數(shù)g(x),推斷它所對應(yīng)的輸出 是1還是-1.決策函數(shù)決策函數(shù)：f(x)=sgn(g(x)實質(zhì)：實質(zhì)：找到一個把 上的點分成兩部分的規(guī)則.l11(,),(,)()lllTxyxyyxx

8、ynR SVM分類問題大致有三種：線性可分問題、線性不可分問題、非線性可分問題。圖圖3-1 線性可分情況線性可分情況圖圖3-2 線性不可分情況線性不可分情況圖圖3-3 非線性可分情況非線性可分情況 3.3 SVM三種分類問題三種分類問題 3.4 最優(yōu)分類面、最大間隔原則最優(yōu)分類面、最大間隔原則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 說明：說明：只要我們求得該問題的最優(yōu)解 ，從而構(gòu)造分類面 ， 求出決策函數(shù) 。上述方法考慮的是二維空間的分類問題。但對一般 上的分類問題也適用.nR*,w b*()0wxb*( )sgn()f xwxb線性可分SVM求解最優(yōu)分類面的原始問題原始問題11111min2. .0,0,1llli jijijjijjliiiiyyx xstyil （3.3）*1liiiiwyx*1ljiiijibyy ax x構(gòu)造分類面 , 決策函數(shù)*()0wxb*( )sgn()f xwxb線性可分SVM求解最優(yōu)分類面的對偶問題對偶問題3.4.2

10、線性不可分支持向量機線性不可分支持向量機1lii1,Tl軟間隔軟間隔：在被錯分的樣本數(shù)目最少的情況下構(gòu)造最優(yōu)分類面。引入松弛變量 軟化最大間隔的要求。約束條件約束條件：0i1iiiyw xb 體現(xiàn)了訓(xùn)練集被錯分的情況，可采用 作 為一種度量來描述錯分程度。1lii兩個目標兩個目標：1. 間隔 盡可能大 2. 錯分程度 盡可能小2w0C 2, ,11min 2. ()1,1, 0,1,liw biiiiiwCstyw xbilil 為避免 過大，需要引入一個懲罰參數(shù) 對它們進行懲罰 ，新的目標函數(shù)變?yōu)?（3.4）原始問題原始問題i線性不可分SVM求解最優(yōu)分類線的對偶問題對偶問題：*1liiiiw

11、yx*1ljiiijibyy ax x構(gòu)造分類面 ,決策函數(shù)*()0wxb*( )sgn()f xw xb111l1i 1min 2. . 0 0,1,lllijijijjijjiiiy yx xstyC il （3.5）3.4.3. 非線性可分支持向量機非線性可分支持向量機 非線性可分SVM問題的基本思想是：引入一個從輸入空間 到高維特征空間 的變換 ： ，那么訓(xùn)練集 就轉(zhuǎn)化成了： , 比較兩個訓(xùn)練集：nRZ( ) x( )xnXRZZ 11( ,),.( ,)llTx yx y1122( (),),( (),),( ( ),)llSxyxyxy11111min( ( )()2. . 0,0

12、,1,2,lllijijijiijiliiiiy yxxstCyi ,l.引入核函數(shù) ，上式變?yōu)椋? ,)( )()ijijK x xxx11111min( ,)2. . 0,0,1,2,lllijijijiijiliiiiy y K x xstCyi,l. 采用不同的核函數(shù)，可構(gòu)成不同的SVM模型。 目前，在分類問題方面常用的核函數(shù)主要有：多項式核函數(shù)多項式核函數(shù)： d為階數(shù)高斯徑向基核函數(shù)高斯徑向基核函數(shù)： 雙曲線正切核函數(shù)雙曲線正切核函數(shù)： ， 本文采用線性不可分SVM、高斯徑向基核函數(shù)、雙曲線正切核函數(shù)三種模型，設(shè)計了不同的AID算法，并進行對比分析。 ( ,)()1,0,diiK x

13、 xx x2( ,)exp,0iiK x xxx( ,)tanh()iiK x xx xc0 四、四、 基于基于SVM的的AID算法設(shè)計算法設(shè)計 4.1 基于基于SVM的事件檢測基本原理：的事件檢測基本原理： 首先基于高速公路交通特性選取具有典型特征的交通參數(shù)， 由這些交通參數(shù)組成一定維數(shù)的特征向量。 將特征向量輸入到SVM中進行優(yōu)化計算，依據(jù)最大間隔原理 實現(xiàn)分類，從而達到最終的事件檢測目的。4.2 基于基于SVM的事件檢測的事件檢測 基本步驟：基本步驟：根據(jù)不同的數(shù)據(jù)子空間、支持向量機模型和核函數(shù)尋找相對應(yīng)的最優(yōu)參數(shù)上游檢測點的t、t-1、 t-2、 t-3、 t-4時刻測得的流量、速度、

14、占有率；下游檢測點的t、t-1、 t-2時刻測得的流量、速度、占有率。4.3 交通參數(shù)選擇交通參數(shù)選擇SVM共有24個輸入。將有事件發(fā)生的特征向量標識為1，將無事件發(fā)生的特征向量標識為-1。輸出節(jié)點數(shù)為1個，輸出值為+1時，代表事件狀態(tài)，輸出值為-1時，代表無事件狀態(tài)。 采用美國加州I-880數(shù)據(jù)庫，I-880數(shù)據(jù)庫是美國Berkeley大學(xué)Freeway Service Patrol Project這個項目所采集的數(shù)據(jù)，其采集路段為美國加利福尼亞州圣弗朗西斯科海灣地區(qū)的I-880高速公路9.41英里的路段，這段路段上北向共有環(huán)形線圈18組，南向共有環(huán)形線圈17組，車道數(shù)為3-5個。采集到的原

15、始數(shù)據(jù)包括環(huán)形線圈數(shù)據(jù)集、移動車數(shù)據(jù)集、事件數(shù)據(jù)集。4.4 數(shù)據(jù)來源：數(shù)據(jù)來源：事件數(shù)據(jù)集由移動車采集，移動車采集數(shù)據(jù)從每個工作日的早上6：30到9：30，下午3：30到6：30，主要有3-4輛浮動車在測試路段來回巡邏，當遇到有交通事件時，將交通事件數(shù)據(jù)例如南向還是北向交通事件、事件發(fā)生的時間地點等信息報告給指揮中心；將得到的數(shù)據(jù)劃分為訓(xùn)練集、測試集。 環(huán)形線圈的采集時間是每天從早上5點到10點，下午2點到8點，采集的數(shù)據(jù)包括每個車道的速度、流量、占有率；I-880數(shù)據(jù)庫高速公路環(huán)形線圈布置圖（數(shù)據(jù)庫高速公路環(huán)形線圈布置圖（P42）4.5 SVM模型及核函數(shù)的選擇：模型及核函數(shù)的選擇： 由于不

16、同的SVM模型、不同的核函數(shù)及其參數(shù)、不同的數(shù)據(jù)空間，都影響著算法的性能指標。也即模型選擇的不同以及核函數(shù)的選取不同，即使相同的數(shù)據(jù)集，檢測效果仍然不一樣。 對于模型的參數(shù)選擇，在具體使用中，目前主要采取以下兩種參數(shù)優(yōu)化方法：k-折交叉驗證法和網(wǎng)格搜索算法。k-折交叉驗證法：首先把 個樣本點隨機地分成互不相交的k個子集，即k-折 。每個折的大小大致相等，共進行k次訓(xùn)練與測試，即對 進行k次迭代，第 次迭代的做法是，選擇 為測試集，其余的合集為訓(xùn)練集，算法根據(jù)訓(xùn)練集求出決策函數(shù)之后，即可對測試集進行測試。 網(wǎng)格搜索算法：從不同的增長方向并行搜索多維數(shù)組：選定一組 的范圍，如： ，搜索步長為-1;l12,kS SS,iS1,i ,kiC、10152 2 ，搜索步長為1；這樣在 坐標系上構(gòu)成一個二維網(wǎng)格。對應(yīng)網(wǎng)格上每一組的值 ，按照交叉驗證方法計算出樣本預(yù)測準確率，從中選擇一組使得預(yù)測準確率最高的值作為最優(yōu)參數(shù)。 本文采用網(wǎng)格搜索算法并且對每組給定的參數(shù)采用5-折交叉驗證，通過取不同的參數(shù)范圍反復(fù)實驗，最終獲得分類效果最優(yōu)的一組參數(shù)。 15102 2CC、