基于集成算法的路段短時行駛時間預測

蔣怡玥，董蜀黔，周淑敏

(1.北京交通大學交通運輸學院，北京 100044；2.北京郵電大學信息與通信工程學院，北京 100876)

路段行駛時間是反映道路擁擠程度最為直觀的參數[1]，是構建交通信息服務系統、交通流誘導系統等ITS子系統的重要基礎。從道路管理者和出行者的角度來看，了解道路交通狀況并對其進行短時預測，在運輸效率和可靠性方面都是值得關注的問題。不僅可以輔助管理者應對交通擁堵和實施應急策略，還可以幫助出行者規劃自己的行程和路線，以避開擁擠的路段，避免旅行延誤。時間尺度越小，實時性越好，越能真實反映路段的交通狀態；但正是如此，路段行駛時間常呈現出強烈的波動，而這些快速變化往往是復雜且難以預測的。因此，基于交通信息建立算法模型，精準預測各路段在某個時段的通行時間，對交通狀態波動進行預測，有助于城市交通智能管控和社會智慧出行，是現在交通發展的大勢所趨。

行駛時間預測對于交通預測來說一直是一個重要的研究領域，國內外學者已經將很多方法用于其中。由于交通狀態的動態性和非線性，短時旅行時間的預測仍是一個非常有挑戰性的任務?，F有的應用于短時行駛時間預測的數據驅動方法可分為兩大類，即參數方法和非參數方法。

參數方法主要有線性回歸模型[2]、時間序列模型，如卡爾曼濾波[3]、自回歸綜合移動平均法[4]。在這些模型中，交通狀態本質上假定為線性的。當交通呈現有規律的變化時可以產生比較理想的預測結果，而對于波動性較強和非線性的交通狀態，這些方法計算耗時并且易產生較大的偏差。由于非參數方法對基本模型不做很強的假設，應用中相對具有優勢[5]。其中，以神經網絡為代表的方法對非線性關系的擬合能力使得其在交通預測方面得到了廣泛應用[6]。神經網絡算法具有較強的魯棒性和容錯能力，但是神經網絡缺乏解釋性，且對參數比較敏感，需要比較多的參數訓練，訓練時間過長，可能預測結果更差。

近年來，在解決預測問題方面，基于集成的算法被應用于各個領域并取得了巨大的成功[7]。在各種不同的集成方法中，基于樹的集成方法是一種流行的集成方法，該方法將多個簡單樹模型結合，優化預測性能?；跇涞募赡Ｐ偷目山忉屝允沟媒煌Q策者能夠更好地理解模型的輸出，并且便于分析交通量之間的影響因素。這些特性使得基于樹的集成方法在解決交通問題方面具有很好的應用前景。Hamner[8]將隨機森林(random forest，RF)應用于旅行時間預測中并在IEEE ICDM比賽中表現最佳，相比于其他算法具有明顯優勢。梯度提升樹(gradient boosting decision tree，GBDT)與傳統的統計方法和其他集成方法相比，在預測精度方面具有優越的性能。Zhang等[9]首次將梯度提升樹應用于旅行時間預測，并得到了很好的結果，尤其是在交通狀況發生突變時。

盡管在高速公路交通預測方面已經做了大量工作，但其中基于樹的集成方法在短時交通預測中應用十分有限。路段行駛時間隨時間的變化波動很大，而天氣、節假日等非線性因素都會對路段行駛時間造成影響，時間尺度較小時，其不確定性和時變性較強[10]?；跇涞募煞椒ǖ玫降慕Y果可解釋性較強，不僅能夠處理不同類型的預測變量，并且可以較好地擬合復雜的非線性關系，可直接通過原始數據預測路段行駛時間，因此更加適合路段行駛時間的短時預測。在機器學習中，基于樹的集成方法通常比傳統的統計方法具有更好的預測性能。本文提出了一個基于樹的集成方法來預測短時的路段行駛時間。首先針對小時間尺度下交通時變性強這一特性，通過對其損失函數的改造得到一個更加魯棒的GBDT，并與RF進行融合。其次考慮各種歷史旅行時間數據的相關變量，以揭示影響旅行時間波動的重要因素。最后，比較了不同方法的預測準確性及算法穩定性。

1 數據分析

1.1 數據描述

本文數據來源于天池大數據競賽中智慧交通預測挑戰賽。數據集中記錄了城市關鍵路段的屬性信息、路段間網絡拓撲結構，以及歷史每天以2 min為一個間隔的每條路段上的平均旅行時間。提供2017年4月至2017年6月132條路段以2 min為一個時間窗的覆蓋全天的旅行時間數據。

1.2 數據處理

缺失值利用歷史相同時間片的行駛時間進行補充。由于均值可能受到統計樣本中極端值的影響，因此本文使用數據集中觀察到的路段旅行時間的中位數進行缺失數據填充，具體缺失數據填充流程見圖1。

1.3 特征工程

表1是本文所選取數據集特征的一個示例，其中in_tt和out_tt分別表示車輛經過與該路段相鄰的上、下游路段的行駛時間；length，width分別表示該路段的路段屬性(長、寬)；of_day表示車輛通過該路段的不同時間段；of_week的索引從1到7代表從星期一到星期日；pretime表示與上一個時間段車輛經過該路段的行駛時間，t2-t1表示連續兩個時間段的行駛時間變化率；最后將天氣(weather)也作為考慮因素加入特征中。

圖1 缺失數據填充流程圖Fig.1 The process of filling the missing data

表1 數據集實例Table 1 Example of the data set

2 理論方法

2.1 隨機森林(RF)法

Breiman等[11]結合Boostrap重采樣技術和Random Subspace Method提出RF，RF是由多個決策樹構成的森林。決策樹在生成的過程中首先分別在行方向和列方向上添加隨機過程，行方向上構建決策樹時采用自助抽樣得到訓練數據，列方向上采用無放回隨機抽樣得到特征子集，并據此得到其最優切分點；之后就是對采樣之后的數據使用完全分裂的方式建立出決策樹；每棵決策樹都最大可能地進行生長而不進行剪枝(由于之前的兩個隨機采樣的過程保證了隨機性，所以就算不剪枝，也不會出現過擬合)；最后通過對所有的決策樹進行加總來預測新的數據。

2.2 梯度提升樹法(GBDT)

梯度提升的觀點是基于Boosting算法提出的一個改進[12]。假設yi,i=1,2,…,n代表i時刻某路段實際行駛時間的觀測值，迭代輪數為t=1,2,…,T，則ft-1(xi)表示第t-1輪i時刻路段行駛時間的預測值。Freidman[13]提出了用損失函數的負梯度來擬合本輪損失的近似值，進而擬合一個回歸樹。其中，第t輪的i時刻的損失函數的負梯度表示為：

。

(1)

因此GBDT的目標是，找到損失函數是L(·)使本輪損失最?。?/p>

(2)

Freidman[13]將損失函數定義為：

。

(3)

則可以求得第t輪的i時刻損失函數的負梯度：

。

(4)

也就是說GBDT中的梯度方向對應于i時刻某路段行駛時間的觀測值與預測值之差，即“殘差”，由此可以看出GBDT每一輪產生的殘差作為下一輪回歸樹的輸入，下一輪的回歸樹的目的就是盡可能地擬合這個輸入的殘差。

2.3 魯棒的GBDT

GBDT通過在每一輪梯度方向上減少殘差，以提高模型性能。而在過程中容易受到突變點的影響，對突變點就會很敏感，因此對于小時間尺度下劇烈波動的交通狀況，可能會表現不佳。本文針對這一問題，選擇了不同的損失函數，以抑制突變點的影響，得到更加穩健的GBDT。

(5)

令損失函數L(·)為：

(6)

其中，變量w表示觀察值與預測值之差，即殘差；m為參數。

這個函數表示對于殘差w值較小的點，其損失函數是二次的，而對于w值較大的點其損失函數是線性的，這種方法有助于減少突變點對交通預測的影響。

2.4 RF-GBDT回歸

偏差(Bias)度量了學習算法的期望預測與真實結果的偏離程度；方差(Variance)度量了同樣大小訓練集的變動所導致的學習性能的變化。泛化性能是由偏差和方差共同決定的，從圖2刻畫的泛化誤差與偏差、方差的關系，可以看出，偏差與方差之間是存在沖突的，即當學習器擬合能力不夠強時，訓練數據的擾動不足以使學習器產生顯著變化，此時偏差主導泛化錯誤率；而當學習器的擬合能力足夠強時，訓練數據的輕微擾動會導致學習器發生顯著變化，此時方差主導泛化錯誤率。這就是所謂的偏差-方差窘境。

圖2 泛化誤差與偏差、方差的關系示意圖Fig.5 The relationship between total error and bias, variance

從前文的分析發現對于RF，其核心就是自采樣(樣本隨機)和屬性隨機，屬于樣本數相同下的不同訓練集產生的預測結果，即數據的擾動導致模型學習性能的變化，因此RF主要關注降低方差提高模型性能；而對于GBDT，其核心是擬合損失函數梯度，而損失函數的定義就決定了在子區域內各個步長，其中就是期望輸出與預測輸出的差，因此GBDT主要關注降低偏差提高模型性能。另外，當樹的數量足夠多時，RF不會產生過擬合，提高樹的數量能夠使得錯誤率降低；而GBDT的每棵樹是按順序生成的，每棵樹生成時都需要利用之前一棵樹留下的信息，樹的數目過多時會引起過擬合。

因此，本文考慮在進行預測時，將RF與魯棒的GBDT進行結合，彼此優勢互補，使得新的模型能夠克服過擬合現象，同時兼顧偏差-方差，以產生更好的效果。在本文中，將RF和魯棒的GBDT進行融合得到RF-GBDT，并將其應用到路段行駛時間預測中。RF-GBDT算法過程如下。

輸入：訓練集D={(x1,y1),(x2,y2),…,(xm,ym)};

初級學習算法：RF;

次級學習算法：GBDT.

過程：

h=RF(D);

D'=φ;

for i=1,2,…,m do

zi=h(xi);

D'=D'∪(zi,yi);

end for

h'=GBDT(D');

輸出：H(x)=h'(h(x)).

圖3是生成RF-GBDT并進行預測的具體流程。值得一提的是，在訓練階段，GBDT的訓練集是利用RF產生的，若直接使用，過擬合的風險較大，因此本文使用交叉驗證法，用RF未使用的樣本來產生GBDT的訓練樣本。

圖3 RF-GBDT流程示意圖Fig.3 The process of RF-GBDT

具體步驟如下：

3 結果

3.1 評價指標

評價指標采用平均絕對百分誤差(mean absolute percent error，MAPE)，計算公式如下：

(7)

其中：ttp：預測的行駛時間；ttr：真實的行駛時間；N：預測路段數量；Ti：第i個路段上的預測時間片數量；MAPE值越低說明模型準確度越高。

3.2 變量解釋

為了檢測本文所提算法的精度和穩定性，利用已知數據對2017年7月早高峰8:00—9:00、日平峰15:00—16:00和晚高峰18:00—19:00 三個時段中各一個小時的數據(以2 min為粒度)進行短時預測。根據處理之后的數據，分別使用RF、GBDG、RF-GBDT進行預測。其中，在使用RF-GBDT進行預測時，一般來說，k值越大其穩定性和保真性越好，但是效率也會隨之減少；經過測試，k=5時，可同時滿足穩定性和效率要求。

表2 輸入變量對預測結果的相對影響Table 2 Relative influence of input variables on prediction

表2給出了每個輸入變量對模型輸出的相對影響。很明顯，每個輸入變量對模型的輸出有不同的貢獻。在兩個情況下，上一個時間段車輛經過該路段的行駛時間pretime對于行駛時間的預測貢獻最大，事實也是如此，路段上一時間段的交通狀況影響之后的交通，與未來的行駛時間密切相關。行駛時間變化率t2-t1對模型輸出也有較大的影響，其表示了交通的變化，其中一個正的t2-t1值，表示行駛時間具有增加的趨勢，t2-t1值與交通擁擠正相關。我們可以看出，車輛在相鄰路段的行駛時間也很大程度影響該路段的行駛時間；另外相比于早高峰，路段本身的屬性在日平峰對行駛時間的影響有所提升，這與日平峰道路交通狀況良好有關；而天氣對早高峰的作用很微弱，這是因為早高峰出行的主要目的為通勤。

3.3 預測結果

根據預測結果輸出MAPE值并繪制三個時段不同預測周期不同方法下的MAPE對比圖。圖4代表7月份上半月早高峰、日平峰和晚高峰的MAPE值。從圖中我們可以看出，總的來說，RF的預測效果不如GBDT，特別是在早晚高峰交通狀況變化劇烈時，GBDT尤其好于RF，這從側面反應了GBDT的魯棒性較好，能夠較好地反映交通的劇烈變化；而在早晚高峰和日平峰兩種交通狀態下，RF-GBDT的預測效果均為最佳，特別是在交通狀況變化劇烈時。圖5表示7月1日—7月15日及7月1日—7月31日三個時段平均MAPE值。從圖中不難看出，RF-GBDT的預測效果明顯好于RF和GBDT。而預測周期增加之后，MAPE隨之增大，精度有所下降，也就是說預測周期越長，越難以捕捉復雜的交通狀況；對于RF-GBDT，雖然其MAPE有所上升，但上升幅度最小。從預測周期和交通狀況兩個方面的預測結果，RF-GBDT在精度和穩定性上都優于單獨的RF或GBDT。

圖4 7月1日—7月15日分時段輸出MAPE對比圖Fig.4 The comparison of three periods’ MAPE from July 1st to 15th

圖5 7月1日—7月15日與7月1日—7月31日三個時段平均MAPE對比圖Fig.5 The comparison of average MAPE from July 1st to 15th and July 1st to July 31st

4 結語

本文以2 min為預測時間尺度，以實際路段行駛時間為基礎，將在回歸預測領域表現良好，并且效率較高的兩個以RF和GBDT為代表的基于樹的集成學習方法，應用到路段行駛時間的短時預測中。為了使GBDT能夠較好地反映劇烈變化的交通情況，對其損失函數進行了處理。在偏差-方差方面，為了提高模型性能，RF主要關注降低方差；而對于GBDT，其主要關注降低偏差。因此，提出一種改進的RF-GBDT算法。

在對路段行駛時間進行短時預測的過程中，考慮了天氣對交通的影響。本文分別使用RF、GBDT、RF-GBDT對比不同預測周期、不同交通狀況下輸出的MAPE值，并對變量進行解釋。實驗結果表明，RF-GBDT能夠有效應對交通狀況劇烈變化并進行預測，無論是在精度還是在算法穩定性方面，RF-GBDT都表現出了優越性。

本文所提方法在對短時的路段行駛時間進行預測時，雖然預測結果得到了改進，但是在進行方法融合的過程中，其計算成本也會隨之增加，日后可以從這個方面進行提升。