基于變量分析和粒子群優(yōu)化加權(quán)隨機(jī)森林的交通事件檢測(cè)方法

羅預(yù)欣，張 兵，薛運(yùn)強(qiáng)

(華東交通大學(xué)交通運(yùn)輸與物流學(xué)院，南昌 330013)

高速公路是城市間的主要通道，其特點(diǎn)是流量大，速度快，在高速公路上發(fā)生交通事件會(huì)帶來(lái)嚴(yán)重的人員傷亡和降低道路通行效率，若不及時(shí)處理對(duì)后續(xù)的車(chē)輛還是乘車(chē)人員都有發(fā)生二次安全事故的可能性。據(jù)統(tǒng)計(jì)，美國(guó)快速路總擁堵事件中的55%～75%擁堵事件是由交通事件的發(fā)生引起的[1]，在中國(guó)上海，1/3的交通擁堵是由交通事件、車(chē)輛故障等交通事件造成[2]。因此，為了保障道路通行效率，道路安全水平，研究出準(zhǔn)確及時(shí)的AID算法具有重要意義。近幾十年，越來(lái)越多的交通自動(dòng)檢測(cè)(AID)算法被相繼研究出。早期開(kāi)發(fā)的AID算法主要有加利福尼亞算法[3]、基于突變理論的McMaster算法[4]等。隨著對(duì)交通事故影響下事發(fā)路段交通特性變化分析[5]和機(jī)器學(xué)習(xí)、大數(shù)據(jù)的發(fā)展，越來(lái)越多的算法模型被相繼提出，如神經(jīng)網(wǎng)絡(luò)模型[6]、支持向量機(jī)(SVM)模型[7]，隨機(jī)森林(RF)模型[8]等。然而，在以往的交通事件自動(dòng)檢測(cè)算法中大多數(shù)的輸入特征變量只是簡(jiǎn)單的流量、速度、占有率，并沒(méi)有對(duì)交通事件初始變量進(jìn)行全面的分析，導(dǎo)致檢測(cè)效果并不理想。為此，從變量分析的角度構(gòu)建全面的初始變量并進(jìn)行篩選，在算法層面，將根據(jù)隨機(jī)森林算法分類(lèi)的缺點(diǎn)，提出對(duì)決策樹(shù)進(jìn)行權(quán)重賦值并利用粒子群(PSO)算法進(jìn)行優(yōu)化。提出基于變量分析和粒子群優(yōu)化加權(quán)隨機(jī)森林交通事件檢測(cè)算法，實(shí)現(xiàn)快速有效地檢測(cè)交通事件，提高AID系統(tǒng)的檢測(cè)性能，確保高速公路交通事件發(fā)生時(shí)能及時(shí)有效地處理。

1 交通事件初始特征變量分析

高速公路交通流參數(shù)主要包括流量、速度、占有率、車(chē)頭時(shí)距、車(chē)頭間距。但對(duì)于交通事件檢測(cè)算法來(lái)說(shuō)常用的三種參數(shù)為流量、速度、占有率。其中流量指在某一截面或某一地點(diǎn)單位時(shí)間內(nèi)通過(guò)的車(chē)輛數(shù)；速度指車(chē)輛在單位時(shí)間內(nèi)行駛的距離；占有率也分為時(shí)間和空間上的占有率，由于空間占有率難以獲取，一般來(lái)說(shuō)在交通事件檢測(cè)中，占有率通常指的是時(shí)間占有率，其含義指的是在某一時(shí)間內(nèi)，車(chē)輛占用檢測(cè)器時(shí)間與檢測(cè)時(shí)間的比值。在高速公路上目前車(chē)輛檢測(cè)器是常見(jiàn)的采集設(shè)備，它能采集交通流各參數(shù)，可運(yùn)用這些參數(shù)進(jìn)行AID算法的研究。

1.1 交通流基本參數(shù)分析

在發(fā)生交通異常狀態(tài)時(shí)，交通流各參數(shù)數(shù)據(jù)將會(huì)發(fā)生顯著的波動(dòng)，與之相反，對(duì)于交通狀態(tài)處于正常情況下的交通流各參數(shù)數(shù)據(jù)波動(dòng)是在一定范圍內(nèi)的，當(dāng)高速公路發(fā)生交通事件時(shí)，往往屬于偶發(fā)性交通事件，如車(chē)輛追尾，貨物散落等將造成這一路段在一定時(shí)間和范圍內(nèi)的交通擁堵導(dǎo)致道路的通行能力下降，車(chē)輛的行駛速度降低，道路占有率增加，如圖1所示。其初始特征變量：檢測(cè)器所采集的流量、速度、占有率。

圖1 事件發(fā)生前后基本參數(shù)的變化Fig.1 Changes in basic parameters before and after the event

1.2 交通流參數(shù)組合分析

在發(fā)生交通事件時(shí)候，交通流參數(shù)將會(huì)發(fā)生一定的變化，對(duì)于單一的參數(shù)不能將這種變化放大，將考慮同一檢測(cè)器參數(shù)的不同的組合，例如不同參數(shù)之間的差值、乘積、比值，以同一檢測(cè)器交通實(shí)測(cè)量和交通預(yù)測(cè)量差值為例，如圖2所示，圖2中橢圓區(qū)域代表事件的發(fā)生。其中，本文交通流參數(shù)的預(yù)測(cè)值將采用移動(dòng)平均法算出。其初始特征變量：同一檢測(cè)器所采集的實(shí)測(cè)流量與預(yù)測(cè)流量的差值，同一檢測(cè)器所采集的實(shí)測(cè)速度與預(yù)測(cè)速度的差值，同一檢測(cè)器所采集的實(shí)測(cè)占有率與預(yù)測(cè)占有率的差值，同一檢測(cè)器所采集的占有率與速度的比值，同一檢測(cè)器所采集的流量與速度的比值，同一檢測(cè)器所采集的占有率與流量的比值。

圖2 事件發(fā)生時(shí)交通實(shí)測(cè)量與預(yù)測(cè)量之差Fig.2 The difference between the measured and predicted traffic at the time of the incident

1.3 不同區(qū)間交通流參數(shù)分析

當(dāng)交通事件發(fā)生時(shí)，在事件發(fā)生路段的上下游是處于一個(gè)相反的交通狀態(tài)，上游擁堵，則下游暢通。從數(shù)據(jù)層面上，其相鄰的兩個(gè)檢測(cè)器采集到的交通流參數(shù)車(chē)輛速度、流量、占有率等數(shù)據(jù)將有明顯的不同的變化，上游車(chē)輛速度降低，流量增加，占有率增加；下游則相反。其上下游檢測(cè)器交通參數(shù)的組合對(duì)交通事件的發(fā)生也有很強(qiáng)的敏感性。其初始特征變量：上下游檢測(cè)器流量的比值，上下游檢測(cè)器占有率的比值，上下游檢測(cè)器速度的比值。

綜上所述，設(shè)計(jì)15個(gè)特征變量，構(gòu)成交通事件檢測(cè)的初始變量見(jiàn)表1。

2 基于樹(shù)模型的變量選擇

樹(shù)模型一般不僅可以用來(lái)作為分類(lèi)和回歸，還可以對(duì)特征變量進(jìn)行選擇和重要度排序，比如決策樹(shù)是一種基本的分類(lèi)和回歸的方法，但它也可以對(duì)特征變量進(jìn)行選擇，選出對(duì)訓(xùn)練集有較好分類(lèi)能力的特征，一般采用的準(zhǔn)則是基尼系數(shù)、信息增益或者信息增益比來(lái)進(jìn)行特征選擇。通過(guò)樹(shù)模型：AdaBoost[9]、決策樹(shù)的提升方法梯度提升樹(shù)(GBDT)[10]，還有決策樹(shù)的集合隨機(jī)森林(RF)作為樹(shù)模型對(duì)初始變量集進(jìn)行特征變量篩選和排序，然后再將各特征變量在不同樹(shù)模型中的重要度排序，最終得到所有變量的重要度排序?qū)?yīng)不同變量個(gè)數(shù)的分類(lèi)正確率。其流程如圖3所示。

表1 初始特征變量Table 1 Initial characteristic variables

圖3 變量選擇流程Fig.3 Variable selection process

3 加權(quán)隨機(jī)森林

3.1 隨機(jī)森林理論

隨機(jī)森林(RF)[11-14]是一種集成學(xué)習(xí)的組合分類(lèi)器，利用Bootstrap重采樣方法從原始數(shù)據(jù)中有放回的抽樣，然后對(duì)抽取的樣本進(jìn)行決策樹(shù)建模，將多顆決策樹(shù)組合在一起，通過(guò)投票得出最終分類(lèi)和預(yù)測(cè)的結(jié)果。隨機(jī)森林算法在生成過(guò)程中實(shí)質(zhì)上是采用Bagging采樣技術(shù)對(duì)決策樹(shù)進(jìn)行集成，其目的是防止產(chǎn)生局部最優(yōu)解。隨機(jī)森林算法的隨機(jī)性主要體現(xiàn)在兩點(diǎn)，第一是訓(xùn)練集的隨機(jī)抽取，第二是特征變量的隨機(jī)選擇。其算法流程如下：

(1)確定訓(xùn)練集X、隨機(jī)變量m、樹(shù)的規(guī)模T。

(2)通過(guò)Bagging采樣技術(shù)從訓(xùn)練集中采取樣本。

(3)在隨機(jī)變量m中，隨機(jī)的抽取n個(gè)變量(n≤m)與采取的樣本構(gòu)建決策樹(shù)。

(4)通過(guò)以上的不斷重復(fù)，形成多棵決策樹(shù)，生成隨機(jī)森林。并通過(guò)每棵決策樹(shù)的投票確定最終的分類(lèi)結(jié)果。

其最終的分類(lèi)結(jié)果，可以表達(dá)為

(1)

式(1)中：H(X)為分類(lèi)結(jié)果；ht(X)=y表示第t棵決策樹(shù)得出的結(jié)果；I(·)表示括號(hào)中的個(gè)數(shù)；y=1,2,…，c表示類(lèi)別數(shù)；t=1,2,…，T為決策樹(shù)的數(shù)量。

3.2 加權(quán)隨機(jī)森林算法

對(duì)于傳統(tǒng)的隨機(jī)森林，在進(jìn)行最后投票分類(lèi)的時(shí)候，每棵決策樹(shù)的投票權(quán)重都是相同的，看似這種投票方式公平，但在隨機(jī)森林中每棵決策樹(shù)的分類(lèi)精度都不一樣，有些分類(lèi)效果可能較好，有些則相對(duì)較差，再加上交通事件數(shù)據(jù)樣本是一個(gè)不平衡數(shù)據(jù)樣本，將導(dǎo)致隨機(jī)森林的分類(lèi)能力將趨向于大樣本數(shù)據(jù)下決策樹(shù)的分類(lèi)結(jié)果。因此，提出加權(quán)隨機(jī)森林模型[15-16]。其主要思路是在給每棵決策樹(shù)設(shè)置一個(gè)權(quán)重，在進(jìn)行投票時(shí)，每棵決策樹(shù)都要乘以這個(gè)權(quán)重值。其中將訓(xùn)練樣中的一部分樣本用來(lái)對(duì)傳統(tǒng)隨機(jī)森林中的決策樹(shù)進(jìn)行訓(xùn)練，在訓(xùn)練完成后，用另一部分訓(xùn)練樣本作為測(cè)試樣本，對(duì)決策樹(shù)進(jìn)行測(cè)試其分類(lèi)能力。

(2)

(3)

4 粒子群優(yōu)化加權(quán)隨機(jī)森林模型

對(duì)于加權(quán)隨機(jī)森林算法，其中決策樹(shù)數(shù)量T、測(cè)試樣本X、隨機(jī)變量m、剪枝閾值ε等參數(shù)在實(shí)際編程時(shí)都是通過(guò)經(jīng)驗(yàn)來(lái)選取，若取值不當(dāng)將對(duì)模型的輸出有很大的影響，所以這些參數(shù)要進(jìn)行優(yōu)化?，F(xiàn)在常用的參數(shù)優(yōu)化方法有網(wǎng)格子搜索法、遺傳算法相對(duì)于粒子群算法在優(yōu)化上的性能較差。為此，采用粒子群算法[17]對(duì)加權(quán)隨機(jī)森林的參數(shù)進(jìn)行優(yōu)化，獲取最優(yōu)的參數(shù)。

基于粒子群算法對(duì)加權(quán)隨機(jī)森林參數(shù)優(yōu)化的步驟如下：

(1)最開(kāi)始對(duì)決策樹(shù)數(shù)量T、測(cè)試樣本X、隨機(jī)變量m、剪枝閾值ε進(jìn)行一個(gè)隨機(jī)的設(shè)定。

(2)對(duì)用于分類(lèi)的數(shù)據(jù)集進(jìn)行Bootstrap采樣，隨機(jī)生成T個(gè)訓(xùn)練數(shù)據(jù)集，并在每個(gè)訓(xùn)練數(shù)據(jù)集中選出X個(gè)測(cè)試樣本。

(3)將每個(gè)訓(xùn)練數(shù)據(jù)集中的另一部分?jǐn)?shù)據(jù)樣本對(duì)決策樹(shù)進(jìn)行構(gòu)建，共T棵，在對(duì)決策樹(shù)進(jìn)行構(gòu)建時(shí)，變量的選擇均從全部的變量中選出m個(gè)特征變量作為該決策樹(shù)結(jié)點(diǎn)的決策變量。

(4)當(dāng)結(jié)點(diǎn)內(nèi)包含的樣本數(shù)少于閾值ε時(shí)，將該結(jié)點(diǎn)作為葉結(jié)點(diǎn)，并返回其目標(biāo)屬性的眾數(shù)作為該決策樹(shù)的分類(lèi)結(jié)果。

(5)在生成完T棵決策樹(shù)后，對(duì)每棵樹(shù)進(jìn)行測(cè)試，并計(jì)算其權(quán)重。

(6)通過(guò)式(3)計(jì)算出分類(lèi)結(jié)果。

(7)將分類(lèi)結(jié)果作為準(zhǔn)確率，采用粒子群算法對(duì)(1)中提到的參數(shù)進(jìn)行迭代優(yōu)化，確定最終模型的參數(shù)。

其本文算法流程圖如圖4所示。

圖4 本文算法流程圖Fig.4 Flow chart of the proposed algorithm

5 實(shí)例驗(yàn)證

5.1 數(shù)據(jù)來(lái)源

數(shù)據(jù)來(lái)源于某市高速公路環(huán)形線圈檢測(cè)器采集的交通事件數(shù)據(jù)，選取該高速公路長(zhǎng)約為10 km的路段作為研究對(duì)象，該路段單向2車(chē)道，單車(chē)道寬3.5 m，大約平均500 m設(shè)置一個(gè)檢測(cè)截面。檢測(cè)器所采集的交通數(shù)據(jù)為流量、速度、占有率(時(shí)間占有率)，采集時(shí)間間隔為1 min，共計(jì)發(fā)生5 760個(gè)樣本數(shù)據(jù)，部分樣本數(shù)據(jù)見(jiàn)表2。

表2 部分樣本數(shù)據(jù)Table 2 Partial sample data

5.2 特征變量選擇

采用基于樹(shù)模型的各種算法對(duì)交通事件的特征變量進(jìn)行篩選，利用Python3.7編程實(shí)現(xiàn)這三種基于樹(shù)模型的算法對(duì)初始變量進(jìn)行排序，圖5～圖7分別是各算法初始變量重要度排序，最終通過(guò)各算法得出的變量重要度[18]進(jìn)行綜合得分排序，選擇出對(duì)于交通事件發(fā)生更為敏感的關(guān)鍵變量，如圖8所示。當(dāng)進(jìn)行初始變量篩選時(shí)，在尋找關(guān)鍵變量的同時(shí)也要保證分類(lèi)正確率，經(jīng)過(guò)三種算法比較分析，選取5個(gè)重要度相對(duì)較高的關(guān)鍵變量，分別為：同一檢測(cè)器所采集的實(shí)測(cè)速度與預(yù)測(cè)速度的差值；同一檢測(cè)器所采集的實(shí)測(cè)占有率與預(yù)測(cè)占有率差值。

圖5 基于Adaboost算法變量篩選Fig.5 Variable selection based on Adaboost algorithm

圖6 基于GBDT算法變量篩選Fig.6 Variable selection based on GBDT algorithm

圖7 基于RF變量篩選Fig.7 Screening based on random forest variables

圖8 最終變量重要度排序Fig.8 Ranking of importance of final variables

同一檢測(cè)器實(shí)際占有率與預(yù)測(cè)占有率比值；上下游檢測(cè)器速度的比值；上下游檢測(cè)器占有率的比值。

5.3 參數(shù)優(yōu)化

在設(shè)定決策樹(shù)棵數(shù)T和剪枝閾值ε時(shí)，對(duì)決策樹(shù)的數(shù)量在100～1 000取值；對(duì)剪枝閾值在10～100取值，分別判斷其取值對(duì)建立加權(quán)隨機(jī)森林模型分類(lèi)正確率的影響。

從圖9和圖10可以看出剪枝閾值和決策樹(shù)數(shù)量對(duì)加權(quán)隨機(jī)森林模型的分類(lèi)準(zhǔn)確率有一定的影響，其中當(dāng)剪枝閾值達(dá)到50時(shí)，準(zhǔn)確率達(dá)到最優(yōu)值，其后準(zhǔn)確率逐漸降低并在此左右波動(dòng)；準(zhǔn)確率與決策樹(shù)的數(shù)量的曲線為緩慢上升的趨勢(shì)，決策樹(shù)到500時(shí)準(zhǔn)確率達(dá)到最高，之后緩慢降低；由此可見(jiàn)，加權(quán)隨機(jī)森林的參數(shù)對(duì)模型的分類(lèi)效果有一定的影響，所有將采用粒子群算法對(duì)模型參數(shù)進(jìn)行優(yōu)化以取得最優(yōu)值。其中，粒子群優(yōu)化算法的參數(shù)設(shè)置如下：學(xué)習(xí)因子c1=2，c2=2，慣性權(quán)重w=0.8，粒子個(gè)數(shù)為20，粒子維數(shù)為4，迭代次數(shù)為100。

5.4 實(shí)驗(yàn)結(jié)果分析

5.4.1 評(píng)價(jià)指標(biāo)

交通事件自動(dòng)檢測(cè)算法(AID)評(píng)價(jià)指標(biāo)采用以下指標(biāo)：檢測(cè)率(detection rate,DR)、誤報(bào)率(false alarm rate,FAR)、平均檢測(cè)時(shí)間(mean time to detection,MTTD)。

圖9 剪枝閾值對(duì)加權(quán)隨機(jī)森林分類(lèi)性能的影響Fig.9 The influence of pruning threshold on the classification performance of weighted random forest

圖10 決策樹(shù)數(shù)量對(duì)加權(quán)隨機(jī)森林分類(lèi)性能的影響Fig.10 The influence of the number of decision trees on the classification performance of weighted random forest

(1)檢測(cè)率(DR)：是指在同一時(shí)間段內(nèi)AID算法檢測(cè)到的事件數(shù)與實(shí)際發(fā)生的事件總數(shù)的百分比。

(4)

式(4)中：DM為檢測(cè)到的事件數(shù)；AM為實(shí)際發(fā)生的事件數(shù)。

(2)誤報(bào)率(FAR):表示在一定時(shí)間段內(nèi)，誤報(bào)事件數(shù)與所有決策次數(shù)之比。

(5)

式(5)中：FN為誤報(bào)事件數(shù)；NR為所有決策次數(shù)。

(3)平均檢測(cè)時(shí)間(MTTD)：指求實(shí)際發(fā)生時(shí)間和AID算法檢測(cè)出事件的時(shí)間相差的算術(shù)平均值。

(6)

式(6)中：T(i)為被檢測(cè)到的第i個(gè)事件發(fā)生的時(shí)間；A(i)為第i個(gè)事件實(shí)際發(fā)生的時(shí)間。

5.4.2 性能分析

為了驗(yàn)證對(duì)初始變量篩選后對(duì)事件檢測(cè)的有效影響和本文模型(PSO優(yōu)化的加權(quán)隨機(jī)森林)在交通事件自動(dòng)檢測(cè)上綜合性能的評(píng)價(jià)，將引入支持向量機(jī)(SVM)、隨機(jī)森林(RF)算法進(jìn)行檢測(cè)效果整體分析。通過(guò)構(gòu)建初始變量訓(xùn)練集，重要變量訓(xùn)練集，并帶入這三種算法中測(cè)試其性能，結(jié)果見(jiàn)表3。

由表3可知，從變量角度看出，在進(jìn)行過(guò)變量篩選后，利用重要變量進(jìn)行檢測(cè)，性能比利用初始變量檢測(cè)有所改善，其中構(gòu)建的三種算法檢測(cè)率提高，誤報(bào)率降低；從算法模型的角度可以看出，本文構(gòu)建的PSO優(yōu)化加權(quán)隨機(jī)森林模型對(duì)初始變量和重要變量的檢測(cè)性能都要比SVM、RF算法的檢測(cè)效果要更優(yōu)，在檢測(cè)率和誤報(bào)率上都有更優(yōu)的效果，但在檢測(cè)時(shí)間上還有進(jìn)一步提高。綜合實(shí)驗(yàn)結(jié)果分析：本文中對(duì)特征變量進(jìn)行篩選并構(gòu)建PSO優(yōu)化的加權(quán)隨機(jī)森林模型與SVM、RF算法相比，在檢測(cè)性能上更優(yōu)。

表3 不同算法檢測(cè)效果對(duì)比Table 3 Comparison of detection effects of different algorithms

6 結(jié)論

以往傳統(tǒng)的交通事件檢測(cè)算法，其輸入的特征變量是簡(jiǎn)單的交通流參數(shù)。通過(guò)對(duì)事件發(fā)生前后基本交通流參數(shù)的分析，不同交通流參數(shù)組合分析，不同區(qū)間交通流參數(shù)的組合，構(gòu)建了較為完整的初始變量，通過(guò)幾種不同基于樹(shù)模型的算法綜合分析得出重要變量。并運(yùn)用PSO算法對(duì)加權(quán)隨機(jī)森林優(yōu)化，構(gòu)建交通事件檢測(cè)的模型，通過(guò)與SVM、RF的比較，本文算法在性能上更優(yōu)。