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、