城市快速路交通事件自動檢測算法

邴其春，龔勃文，林賜云，楊兆升

?

城市快速路交通事件自動檢測算法

邴其春1, 2，龔勃文1, 3，林賜云1, 3，楊兆升1, 3

(1. 吉林大學交通學院，吉林長春，130022；2. 青島理工大學汽車與交通學院，山東青島，266520；3. 吉林大學汽車仿真與控制國家重點實驗室，吉林長春，130022)

為了進一步提高城市快速路交通事件檢測的精度，在分析交通事件上、下游交通流參數變化規(guī)律的基礎上，構建包含12個變量的交通事件檢測初始變量集，并采用隨機森林方法對初始變量集的關鍵變量進行篩選，進而構建基于粒子群優(yōu)化的組合核函數相關向量機模型。最后，利用上海市南北高架快速路的感應線圈實測參數進行實驗驗證和對比分析。研究結果表明：關鍵變量篩選可以有效提高交通事件檢測的精度，組合核函數相關向量機模型也明顯優(yōu)于單一核函數相關向量機模型和支持向量機模型。

交通事件自動檢測；隨機森林；相關向量機模型；組合核函數

城市快速路是城市路網的重要組成部分，承載著城市中大部分出行交通，快速路的暢通程度直接影響著城市路網的總體運行效率。然而，交通事件常常導致快速路發(fā)生大范圍交通擁堵，嚴重影響著快速路的交通運行效率。據統計，在發(fā)達國家的快速路交通擁堵中，由交通事件引起的超過70%，在我國上海，因交通事件引起的交通擁堵也占快速路總擁堵的50%~75%[1]，因此，研究準確、及時的交通事件自動檢測(automatic incident detection，AID)算法對于保證快速路運行效率、提高道路安全水平具有重要意義。迄今為止，已有許多有效的模型與方法應用于交通事件自動檢測的研究。早期開發(fā)的交通事件檢測算法主要有加利福尼亞算法[2]、標準偏差算法[3]、基于突變理論的McMaster算法[4]、低通濾波算法[5]等。隨著對交通流特性的深入研究以及人工智能新技術的發(fā)展，越來越多的交通事件自動檢測模型相繼被提出，如神經網絡模型[6?7]、支持向量機模型[8?9]、貝葉斯方法[10]、小波理論[11]以及模糊邏輯方法[12]等，并取得了一定的應用效果。然而，現有的研究主要集中于模型方法的整合優(yōu)化，忽視了對交通事件檢測輸入變量的有效篩選；同時，神經網絡、支持向量機等人工智能算法普遍存在計算復雜、泛化能力不強、容易出現過擬合等問題，嚴重影響模型的推廣應用。為此，本文作者以交通流基本參數及其多角度組合的方式，構建較全面的交通事件檢測初始變量集，并采用隨機森林的變量重要性度量篩選出對交通事件更為敏感的關鍵變量，進而構建基于粒子群優(yōu)化的組合核函數相關向量機模型，并以快速路實測數據對變量篩選及模型的有效性進行評價分析。

1 初始變量集構建

事件發(fā)生時段交通流參數的顯著變化是設計交通事件自動檢測算法的基本依據。當路段發(fā)生交通事件時，交通事件發(fā)生位置上游檢測器采集的流量和速度急劇下降，占有率急劇上升；下游檢測器采集的流量下降，速度上升，占有率下降[13]。通過大量分析線圈檢測器檢測結果發(fā)現，不僅流量、速度、占有率這3個基本交通參數在交通事件發(fā)生時段會有明顯變化，不同交通參數之間的組合以及上、下游檢測器交通參數的組合對交通事件的發(fā)生也表現出很強的敏感性。因此，本文以交通流基本參數及其多角度組合的方式，構建較全面的交通事件檢測初始變量集。初始變量集分為3部分：第1部分為檢測器獲取的基本交通參數；第2部分為同一檢測器交通參數的組合；第3部分為相鄰上、下游檢測器交通參數的組合。表1所示為交通事件檢測初始變量集。

交通參數的預測值采用移動平均模型獲得，用相鄰前個時刻的數據預測第+1個時刻的交通參數，本文中取4。

表1 交通事件檢測初始變量集

2 基于隨機森林的變量篩選

交通事件檢測初始變量集中有12個初始變量，較全面地涵蓋了交通事件特性信息。但從實際應用的角度看，變量的個數過多，不僅會導致交通流信息冗余，而且極大地增加了模型的復雜性，因此，有必要對初始變量進行有效篩選，從初始變量集中選擇對交通事件更敏感的關鍵變量，在保證交通事件檢測效果的前提下降低模型的復雜度。隨機森林(random forest, RF)模型是由BREIMAN提出的一種集成學習方法[14]，能夠有效處理高維數據，其變量重要性度量被廣泛應用于特征選擇[15]。本文采用隨機森林算法的變量重要性度量對交通事件檢測初始變量集進行篩選，其基本思想是：依次對袋外數據中的每個變量添加隨機噪聲干擾，通過計算所有CART樹上袋外數據分類正確率的平均降低值來決定該變量的重要性。具體流程如下。

Step 1：生成隨機森林。

1) 在原始訓練樣本集中應用Bootstrap抽樣技術隨機抽出b個樣本，并由此構建1棵CART樹h，未被選中的?b個樣本構成對應的袋外數據。

2) 在CART樹的每個節(jié)點處抽取所有個變量中的try個變量(try≤)，計算每個變量蘊含的信息量，在try個變量中選擇1個分類能力最佳的變量進行節(jié)點分裂。

3) 每棵樹都自然生長，不進行剪枝處理。

4) 重復上述步驟次，生成含有棵CART樹的隨機森林={1，2，…，h}。

Step 2：對于隨機森林中的每棵CART樹h(=1，2，…，)，使用相應的袋外數據進行分類，統計分類正確率R。

Step 3：對于任一變量x(=1，2，…，)，分別對袋外數據中x加入隨機噪聲干擾，變換后的袋外數據記為。利用每棵CART樹h對進行分類，并計算分類正確率。

Step 4：計算每個變量袋外數據加入隨機干擾后分類正確率的平均降低值作為該變量的重要度。變量x重要度V的計算式為

若某個變量加入隨機噪聲后，袋外數據的分類準確率顯著降低，則說明這個變量對分類結果影響較大，其重要度也就越高。

3 組合核函數相關向量機構建

相關向量機(relevance vector machine，RVM)模型是由TIPPING[16]提出的一種稀疏貝葉斯概率模型，已成為近年來統計學習領域的重要研究熱點之一。該算法起源于支持向量機(support vector machine，SVM)模型，與SVM具有相同的決策形式，同時擁有SVM所不具備的優(yōu)點，例如RVM具有優(yōu)于SVM的稀疏性；RVM只需設置核參數，對核函數的選擇突破了Mercer條件限制；RVM在權值上引進了超參數，從而大大降低了計算的復雜度等。本文針對相關向量機模型的核函數選擇問題，將具有不同特點的核函數結合起來，構建一種組合核函數相關向量機(combined kernel function relevance vector machine，CKF-RVM)模型。

3.1 組合核函數構造

傳統的相關向量機模型大多采用單一核函數完成特征空間的映射過程，雖然在許多實際應用中取得了較好效果，但當樣本數據特征中含有異構信息、樣本規(guī)模較大或樣本數據在高維空間中分布不平坦時[17]，采用單一核函數映射方式對所有樣本數據進行處理具有較大的局限性。因此，本文綜合高斯核函數和多項式核函數各自的優(yōu)勢，構造新的組合核函數，使相關向量機模型不僅具有高斯核函數的局部學習能力，并且具有多項式核函數較強的泛化能力。構造的組合核函數形式為

式中：為權重系數，0≤≤1；為高斯核函數的核寬度；為多項式核函數的階數。

當趨近于0時，組合核函數近似多項式核函數，雖然對離測試點較遠處的樣本數據具有較強的擬合能力，但對測試點附近的數據擬合效果不佳；當趨近于1時，組合核函數接近于高斯核函數，對測試點附近的小范圍數據產生影響，但對全局的泛化能力較弱。由于不同的核函數各有特點，若核函數中的權重系數選擇不合適，則組合核函數的擬合能力可能會低于單一核函數的擬合能力。因此，合適的權重系數對于組合核函數的性能至關重要。

3.2 基于粒子群算法的參數優(yōu)化

本文所構造的組合核函數共有，和3個待優(yōu)化參數，目前較常用的參數優(yōu)化方法主要有交叉驗證法、網格搜索法、遺傳算法等，但這些方法往往計算量較大、耗時過長。粒子群(particle swarm optimization，PSO)算法是一種高效的全局優(yōu)化方法，已被廣泛應用于參數的優(yōu)化設置。為此，本文采用粒子群優(yōu)化算法獲取組合核函數的最優(yōu)參數，從而構建組合核函數相關向量機模型。

粒子群優(yōu)化(particle swarm optimization，PSO)算法是由KENNEDY等[18]提出來的一種進化計算技術，源于對鳥群捕食行為的研究。設在維搜索空間中，存在個粒子構成的粒子群體，PSO優(yōu)化算法采用速度?位置搜索模型，第個粒子的空間位置x=(x1，x2，…，x)(其中，=1，2，…，)表示解空間的一個可行解，將其代入優(yōu)化目標函數計算相應的適應度函數值來衡量x的優(yōu)劣。第個粒子的速度v=(v1，v2，…，v)決定粒子在搜索空間單位迭代次數時的位移。粒子通過動態(tài)跟蹤個體最佳位置P=(p1，p2，…，p)和全局最佳位置P=(p1，p2，…，p)來更新自身的速度和位置，更新公式如下：

(4)

式中：為慣性權重系數；1和2為2個在[0，1]之間變化的隨機數；1和2為加速因子。

基于粒子群算法進行參數優(yōu)化的具體步驟如下。

1) 初始化粒子群優(yōu)化算法的參數，包括種群規(guī)模、粒子維數、迭代次數、加速因子、慣性權重系 數等。

2) 采用5折交叉驗證的交通事件平均檢測率作為適應度函數值，并將其與自身的歷史最佳位置適應度進行比較，若當前位置的適應度高于歷史適應度，則將當前位置取代個體歷史最佳位置。

3) 判斷粒子群的全局最佳位置。將各個粒子的個體最佳位置適應度與群體的全局最佳位置適應度相比較，若高于群體的全局適應度，則將其位置取代全局最佳位置。

4) 判斷終止條件。若不滿足終止條件，則按式(3)和式(4)更新粒子的速度和位置，否則，輸出得到的最優(yōu)解。

4 實例分析

4.1 數據來源

本文選取上海市南北高架快速路上延東立交至共和立交長約10 km路段作為研究對象。該路段包括24個主線檢測截面和30個匝道檢測截面，共布設88個主線線圈檢測器和60個匝道線圈檢測器，主線檢測器的平均間距約為500 m。數據采集時間分別為2008?09?01，2008?09?08，2008?09?15，2008?09?22和2008?09?29這連續(xù)5個星期一，線圈檢測器可獲取流量、速度和占有率3個基本交通流參數，數據采樣間隔為5 min。通過分析交通流參數的變化趨勢，人工篩選出107個主線交通事件，其中東側主線62個，西側主線45個。將交通事件數據按照東側主線、西側主線和整個路段進行分類，并與相應的正常狀態(tài)數據構成3個樣本數據集，每個數據集中的2/3作為訓練樣本，剩余部分作為測試樣本。

4.2 變量篩選

采用隨機森林算法對初始變量的重要性進行度量，進而篩選出對交通事件更為敏感的關鍵變量。其中，try取Breiman建議的特征變量個數的平方根，設置為3；隨機森林中CART數的數量設置為1 000。利用Matlab7.0編程實現隨機森林的變量重要度計算，將12個初始變量歸一化處理后輸入到隨機森林程序中。圖1所示為各個初始變量的重要度(其中，變量序號見圖1)。

為了體現關鍵變量篩選的作用，應選擇盡量少的變量個數，但又要保證交通事件檢測的正確率。通過比較分析，最終選擇重要度最高的4個變量作為關鍵變量。由圖1可見：重要度最高的4個變量分別為同一檢測器占有率與速度的比值、相鄰上、下游檢測器在同一時刻采集的占有率比值、同一檢測器占有率與流量的比值、相鄰上下游檢測器在同一時刻采集的速度比值。

圖1 變量重要度

4.3 參數優(yōu)化

采用粒子群優(yōu)化算法獲得組合核函數的最優(yōu)參數，其中，粒子群優(yōu)化算法的具體參數設置如下：粒子個數為20，粒子維數為3，加速因子1=2=2，慣性權重系數從0.9隨迭代次數線性減小至0.4，最大迭代次數為100，采用5折交叉驗證的交通事件平均檢測率作為適應度函數值。以東側主線的樣本數據集為例進行參數優(yōu)化，圖2所示為PSO尋優(yōu)的適用度曲線。

1—平均適應度；2—最佳適應度。

由圖2可見：東側主線樣本數據集的組合核函數最優(yōu)參數分別為=0.53，=0.25，=3。

4.4 實驗結果分析

4.4.1 評價指標

常用的AID算法評價指標主要有檢測率D、誤警率FA和平均檢測時間MTT，但由于本文的交通事件數據庫中無法獲取交通事件的確切發(fā)生時間，因此，只能采用檢測率和誤警率這2個指標進行評價。

檢測率D是指在特定的時間段內，由AID算法檢測出的交通事件的數量D占實際發(fā)生交通事件數量A的百分比，即D=(D/A)×100%。誤報率FA是指在特定時間段內，由AID算法檢出的虛假交通事件的數量F占所有決策次數R的百分比，即FA=(F/R)×100%。

4.4.2 變量篩選有效性分析

為了驗證基于隨機森林的變量篩選對于提高交通事件檢測效果的有效性，分別將初始變量和經過篩選的關鍵變量作為模型輸入變量，利用東側主線樣本數據集構建的相關向量機模型和支持向量機模型進行實驗驗證，核函數均采用高斯核函數。表2所示為變量篩選有效性分析結果。

表2 變量篩選有效性分析結果

由表2可知：2種不同形式的輸入變量均獲得了較好的檢測效果，以關鍵變量作為模型輸入的交通事件檢測效果更優(yōu)。由此可見：深入分析交通事件對交通流參數的影響，多角度設計初始變量，能夠獲得較好的交通事件檢測效果。同時，對初始變量進行有效篩選，既能減少冗余信息，又能有效提高交通事件檢測的精度。

4.4.3 模型有效性分析

為了進一步驗證組合核函數相關向量機模型在交通事件檢測上的優(yōu)越性，分別選取高斯核函數相關向量機(Gaussian kernel function relevance vector machine，GKF-RVM)模型、多項式核函數相關向量機(polynomial kernel function relevance vector machine，PKF-RVM)模型以及經典的高斯核函數支持向量機(Gaussian kernel function support vector machine，GKF-SVM)模型作為對比方法進行對比分析，模型輸入變量均為篩選后的關鍵變量。為確保實驗的充分性與全面性，分別對3個樣本數據集進行實驗與對比分析。表3所示為不同方法對3個數據集的參數取值，表4所示為不同方法的實驗結果。

由表4可知：不同核函數RVM模型的檢測效果均優(yōu)于SVM模型的檢測效果，說明RVM模型具有較強的分類能力，能夠有效地進行交通事件檢測。從3種不同核函數RVM模型的檢測效果看，本文構建的CKF-RVM模型的檢測效果明顯優(yōu)于GKF-RVM模型和PKF-RVM模型的檢測效果，說明組合核函數能夠兼顧不同核函數的優(yōu)勢，具有比單一核函數更強的交通事件檢測性能。從不同樣本數據集的檢測效果看，東側主線的事件檢測效果最好，這是因為東側主線的交通事件大多導致交通流參數波動較大，且持續(xù)時間較長；西側主線的事件檢測效果最差，這是由于西側主線的交通事件大多對交通流影響較小，交通流參數波動不明顯。綜合結果表明：本文所構建的CKF-RVM模型取得了較好的檢測效果，明顯優(yōu)于對比算法。

表3 不同方法的參數取值

表4 不同方法的交通事件檢測效果對比

5 結論

1) 在綜合分析交通事件對交通流參數影響的基礎上，構建交通事件檢測初始變量集，并采用隨機森林方法篩選出對交通事件敏感性較強的關鍵變量。

2) 構建組合核函數相關向量機模型，并利用粒子群優(yōu)化算法獲得最優(yōu)參數。

3) 利用上海市南北高架快速路實測數據對算法的有效性進行了實驗驗證和對比分析。然而，本文在變量篩選過程中關鍵變量的個數需要依靠人工經驗確定，定量確定標準有待進一步研究。

[1] 姬楊蓓蓓, 張小寧, 孫立軍. 基于貝葉斯決策樹的交通事件持續(xù)時間預測[J]. 同濟大學學報(自然科學版), 2008, 36(3): 319?324. JI Yangbeibei, ZHANG Xiaoning, SUN Lijun. Incident duration prediction grounded on Bayesian decision method based tree algorithm[J]. Journal of Tongji University(Natural Science), 2008, 36(3): 319?324.

[2] PAYNE H J, HELFENBEIN E D, KNOBEL H C. Development and testing of incident detection algorithms[R]. Washington D C, USA: Federal Highway Administration, 1976: 1?20.

[3] DUDEK C L, MESSER C J, NUCKLES N B. Incident detection on urban freeways[C]//Transportation Research Board. Washington D C: Transportation Research Board, 1974: 12?24.

[4] PERSAUD B N, HALL F L. Catastrophe theory and patterns in 30-second freeway traffic data-implication for incident detection[J]. Transportation Research Part A, 1990, 23(2): 103?113.

[5] STEPHANEDES Y J, CHASSIAKOS A P. Application of filtering techniques for incident detection[J]. Journal of Transportation Engineering, 1993, 119(1): 13?26.

[6] 姜桂艷, 溫惠敏, 楊兆升. 高速公路交通事件自動檢測系統與算法設計[J]. 交通運輸工程學報, 2001, 1(1): 77?81. JIANG Guiyan, WEN Huimin, YANG Zhaosheng. Design of freeway automatic incident detection system and algorithm[J]. Journal of Traffic and Transportation Engineering, 2001, 1(1): 77?81.

[7] SRINIV D, SHARMA V, TOH K A. Reduced multivariate polynomial-based neural network for automated traffic incident detection[J]. Neural Networks, 2008, 21(2/3): 484?492.

[8] 王武功, 馬榮國. 交通事件檢測的加權支持向量機算法[J]. 長安大學學報(自然科學版), 2013, 33(6): 84?87. WANG Wugong, MA Rongguo. Weighed support vector machine for traffic incident detection[J]. Journal of Changan University (Natural Science Edition), 2013, 33(6): 84?87.

[9] 陳維榮, 關佩, 鄒月嫻. 基于SVM的交通事件檢測技術[J]. 西南交通大學學報, 2011, 46(1): 63?67. CHEN Weirong, GUAN Pei, ZOU Yuexian. Automatic incident detection technology based on SVM[J]. Journal of Southwest Jiaotong University, 2011, 46(1): 63?67.

[10] 張輪, 楊文臣, 劉拓. 基于樸素貝葉斯分類的高速公路交通事件檢測[J]. 同濟大學學報(自然科學版), 2014, 42(4): 558?563. ZHANG Lun, YANG Wenchen, LIU Tuo. A naive Bayesian classifier-based algorithm for freeway traffic incident detection[J]. Journal of Tongji University (Natural Science), 2014, 42(4): 558?563.

[11] 尹春娥, 陳寬民, 萬繼志. 基于小波方程的高速公路交通事故自動檢測方法[J]. 中國公路學報, 2014, 27(12): 106?112. YIN Chune, CHEN Kuanmin, WAN Jizhi. Automatic detection method for expressway traffic accident based on wavelet equation[J]. China Journal of Highway and Transport, 2014, 27(12): 106?112.

[12] ROSSI R, GASTALDI M, GECCHELE G. Fuzzy logic-based incident detection system using loop detectors data[J]. Transportation Research Procedia, 2015(10): 266?175.

[13] 蔡志理. 高速公路交通事件檢測及交通疏導技術研究[D]. 長春: 吉林大學交通學院, 2007: 51?52. CAI Zhili. Study on traffic incident detection and traffic evanesce technologies for freeway[D]. Changchun: Jilin University, College of Transportation, 2007: 51?52.

[14] BREIMAN L. Random forest[J]. Machine Learning, 2011, 45(1): 5?32.

[15] GENUER R, POGGI J M, TULEAU-MALOT C. Variable selection using random forests[J]. Pattern Recognition Letters, 2015, 31(14): 2225?2236.

[16] TIPPING M E. Sparse Bayesian learning and the relevance vector machine[J]. Journal of Machine Learning Research, 2001, 1(3): 211?244.

[17] 瞿娜娜.基于組合核函數支持向量機研究及應用[D]. 廣州: 華南理工大學經濟與貿易學院, 2011: 23?24. QU Nana. Research and application of support vector machine based on mixed-kernel function[D]. Guangzhou: South China University of Technology. School of Economic and Commerce, 2011: 23?24.

[18] KENNEDY J, EBERHART R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Network. Piscataway, NJ: IEEE Service Center, 1995: 1942?1948.

(編輯 陳燦華)

Traffic incident automatic detectionalgorithm for urban expressway

BING Qichun1, 2, GONG Bowen1, 3, LIN Ciyun1, 3, YANG Zhaosheng1, 3

(1. School of Transportation, Jilin University, Changchun 130022, China;2. School of Automobile and Transportation, Qingdao Technology University, Qingdao 266520, China;3. State Key Laboratory of Automobile Simulation and Control, Jilin University, Changchun 130022, China)

In order to improve the accuracy of traffic incident detection for urban expressway, through analyzing the change rules of traffic flow parameters, the initial variables set of traffic incident detection which contains 12 variables was built, and the random forest method was used to select the key variables. Then combined kernel function, relevance vector machine model was constructed based on particle swarm optimization. Finally, validation and comparative analysis were carried out using inductive loop parameters measured from the north-south viaduct in Shanghai. The results show that the key variable selection can effectively improve the accuracy of traffic incident detection. The detection performance of combined kernel function RVM model is also better than that of the single kernel function RVM model and SVM model.

automatic incident detection; random forest; relevance vector machine model; combined kernel function

10.11817/j.issn.1672?7207.2017.06.036

U491

A

1672?7207(2017)06?1682?06

2016?07?24；

2016?09?24

“十二五”國家科技支撐計劃項目(2014BAG03B03)；國家自然科學基金青年基金資助項目(51308248，51408257)(Project (2014BAG03B03) supported by the National Science and Technology Pillar Program During the 12th “Five-year”; Projects(51308248, 51408257) supported by the National Natural Science Youth Foundation of China)

龔勃文，博士，講師，從事智能交通關鍵理論與技術研究；E-mail：gongbowen@ jlu.edu.cn