基于變量分析和粒子群優化加權隨機森林的交通事件檢測方法

羅預欣，張 兵，薛運強

(華東交通大學交通運輸與物流學院，南昌 330013)

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

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

高速公路交通流參數主要包括流量、速度、占有率、車頭時距、車頭間距。但對于交通事件檢測算法來說常用的三種參數為流量、速度、占有率。其中流量指在某一截面或某一地點單位時間內通過的車輛數；速度指車輛在單位時間內行駛的距離；占有率也分為時間和空間上的占有率，由于空間占有率難以獲取，一般來說在交通事件檢測中，占有率通常指的是時間占有率，其含義指的是在某一時間內，車輛占用檢測器時間與檢測時間的比值。在高速公路上目前車輛檢測器是常見的采集設備，它能采集交通流各參數，可運用這些參數進行AID算法的研究。

1.1 交通流基本參數分析

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

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

1.2 交通流參數組合分析

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

圖2 事件發生時交通實測量與預測量之差Fig.2 The difference between the measured and predicted traffic at the time of the incident

1.3 不同區間交通流參數分析

當交通事件發生時，在事件發生路段的上下游是處于一個相反的交通狀態，上游擁堵，則下游暢通。從數據層面上，其相鄰的兩個檢測器采集到的交通流參數車輛速度、流量、占有率等數據將有明顯的不同的變化，上游車輛速度降低，流量增加，占有率增加；下游則相反。其上下游檢測器交通參數的組合對交通事件的發生也有很強的敏感性。其初始特征變量：上下游檢測器流量的比值，上下游檢測器占有率的比值，上下游檢測器速度的比值。

綜上所述，設計15個特征變量，構成交通事件檢測的初始變量見表1。

2 基于樹模型的變量選擇

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

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

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

3 加權隨機森林

3.1 隨機森林理論

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

(1)確定訓練集X、隨機變量m、樹的規模T。

(2)通過Bagging采樣技術從訓練集中采取樣本。

(3)在隨機變量m中，隨機的抽取n個變量(n≤m)與采取的樣本構建決策樹。

(4)通過以上的不斷重復，形成多棵決策樹，生成隨機森林。并通過每棵決策樹的投票確定最終的分類結果。

其最終的分類結果，可以表達為

(1)

式(1)中：H(X)為分類結果；ht(X)=y表示第t棵決策樹得出的結果；I(·)表示括號中的個數；y=1,2,…，c表示類別數；t=1,2,…，T為決策樹的數量。

3.2 加權隨機森林算法

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

(2)

(3)

4 粒子群優化加權隨機森林模型

對于加權隨機森林算法，其中決策樹數量T、測試樣本X、隨機變量m、剪枝閾值ε等參數在實際編程時都是通過經驗來選取，若取值不當將對模型的輸出有很大的影響，所以這些參數要進行優化。現在常用的參數優化方法有網格子搜索法、遺傳算法相對于粒子群算法在優化上的性能較差。為此，采用粒子群算法[17]對加權隨機森林的參數進行優化，獲取最優的參數。

基于粒子群算法對加權隨機森林參數優化的步驟如下：

(1)最開始對決策樹數量T、測試樣本X、隨機變量m、剪枝閾值ε進行一個隨機的設定。

(2)對用于分類的數據集進行Bootstrap采樣，隨機生成T個訓練數據集，并在每個訓練數據集中選出X個測試樣本。

(3)將每個訓練數據集中的另一部分數據樣本對決策樹進行構建，共T棵，在對決策樹進行構建時，變量的選擇均從全部的變量中選出m個特征變量作為該決策樹結點的決策變量。

(4)當結點內包含的樣本數少于閾值ε時，將該結點作為葉結點，并返回其目標屬性的眾數作為該決策樹的分類結果。

(5)在生成完T棵決策樹后，對每棵樹進行測試，并計算其權重。

(6)通過式(3)計算出分類結果。

(7)將分類結果作為準確率，采用粒子群算法對(1)中提到的參數進行迭代優化，確定最終模型的參數。

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

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

5 實例驗證

5.1 數據來源

數據來源于某市高速公路環形線圈檢測器采集的交通事件數據，選取該高速公路長約為10 km的路段作為研究對象，該路段單向2車道，單車道寬3.5 m，大約平均500 m設置一個檢測截面。檢測器所采集的交通數據為流量、速度、占有率(時間占有率)，采集時間間隔為1 min，共計發生5 760個樣本數據，部分樣本數據見表2。

表2 部分樣本數據Table 2 Partial sample data

5.2 特征變量選擇

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

圖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

同一檢測器實際占有率與預測占有率比值；上下游檢測器速度的比值；上下游檢測器占有率的比值。

5.3 參數優化

在設定決策樹棵數T和剪枝閾值ε時，對決策樹的數量在100～1 000取值；對剪枝閾值在10～100取值，分別判斷其取值對建立加權隨機森林模型分類正確率的影響。

從圖9和圖10可以看出剪枝閾值和決策樹數量對加權隨機森林模型的分類準確率有一定的影響，其中當剪枝閾值達到50時，準確率達到最優值，其后準確率逐漸降低并在此左右波動；準確率與決策樹的數量的曲線為緩慢上升的趨勢，決策樹到500時準確率達到最高，之后緩慢降低；由此可見，加權隨機森林的參數對模型的分類效果有一定的影響，所有將采用粒子群算法對模型參數進行優化以取得最優值。其中，粒子群優化算法的參數設置如下：學習因子c1=2，c2=2，慣性權重w=0.8，粒子個數為20，粒子維數為4，迭代次數為100。

5.4 實驗結果分析

5.4.1 評價指標

交通事件自動檢測算法(AID)評價指標采用以下指標：檢測率(detection rate,DR)、誤報率(false alarm rate,FAR)、平均檢測時間(mean time to detection,MTTD)。

圖9 剪枝閾值對加權隨機森林分類性能的影響Fig.9 The influence of pruning threshold on the classification performance of weighted random forest

圖10 決策樹數量對加權隨機森林分類性能的影響Fig.10 The influence of the number of decision trees on the classification performance of weighted random forest

(1)檢測率(DR)：是指在同一時間段內AID算法檢測到的事件數與實際發生的事件總數的百分比。

(4)

式(4)中：DM為檢測到的事件數；AM為實際發生的事件數。

(2)誤報率(FAR):表示在一定時間段內，誤報事件數與所有決策次數之比。

(5)

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

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

(6)

式(6)中：T(i)為被檢測到的第i個事件發生的時間；A(i)為第i個事件實際發生的時間。

5.4.2 性能分析

為了驗證對初始變量篩選后對事件檢測的有效影響和本文模型(PSO優化的加權隨機森林)在交通事件自動檢測上綜合性能的評價，將引入支持向量機(SVM)、隨機森林(RF)算法進行檢測效果整體分析。通過構建初始變量訓練集，重要變量訓練集，并帶入這三種算法中測試其性能，結果見表3。

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

表3 不同算法檢測效果對比Table 3 Comparison of detection effects of different algorithms

6 結論

以往傳統的交通事件檢測算法，其輸入的特征變量是簡單的交通流參數。通過對事件發生前后基本交通流參數的分析，不同交通流參數組合分析，不同區間交通流參數的組合，構建了較為完整的初始變量，通過幾種不同基于樹模型的算法綜合分析得出重要變量。并運用PSO算法對加權隨機森林優化，構建交通事件檢測的模型，通過與SVM、RF的比較，本文算法在性能上更優。