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

蔣怡玥，董蜀黔，周淑敏

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

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

行駛時間預(yù)測對于交通預(yù)測來說一直是一個重要的研究領(lǐng)域，國內(nèi)外學(xué)者已經(jīng)將很多方法用于其中。由于交通狀態(tài)的動態(tài)性和非線性，短時旅行時間的預(yù)測仍是一個非常有挑戰(zhàn)性的任務(wù)?，F(xiàn)有的應(yīng)用于短時行駛時間預(yù)測的數(shù)據(jù)驅(qū)動方法可分為兩大類，即參數(shù)方法和非參數(shù)方法。

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

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

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

1 數(shù)據(jù)分析

1.1 數(shù)據(jù)描述

本文數(shù)據(jù)來源于天池大數(shù)據(jù)競賽中智慧交通預(yù)測挑戰(zhàn)賽。數(shù)據(jù)集中記錄了城市關(guān)鍵路段的屬性信息、路段間網(wǎng)絡(luò)拓撲結(jié)構(gòu)，以及歷史每天以2 min為一個間隔的每條路段上的平均旅行時間。提供2017年4月至2017年6月132條路段以2 min為一個時間窗的覆蓋全天的旅行時間數(shù)據(jù)。

1.2 數(shù)據(jù)處理

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

1.3 特征工程

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

圖1 缺失數(shù)據(jù)填充流程圖Fig.1 The process of filling the missing data

表1 數(shù)據(jù)集實例Table 1 Example of the data set

2 理論方法

2.1 隨機森林(RF)法

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

2.2 梯度提升樹法(GBDT)

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

。

(1)

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

(2)

Freidman[13]將損失函數(shù)定義為：

。

(3)

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

。

(4)

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

2.3 魯棒的GBDT

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

(5)

令損失函數(shù)L(·)為：

(6)

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

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

2.4 RF-GBDT回歸

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

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

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

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

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

初級學(xué)習(xí)算法：RF;

次級學(xué)習(xí)算法：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并進行預(yù)測的具體流程。值得一提的是，在訓(xùn)練階段，GBDT的訓(xùn)練集是利用RF產(chǎn)生的，若直接使用，過擬合的風(fēng)險較大，因此本文使用交叉驗證法，用RF未使用的樣本來產(chǎn)生GBDT的訓(xùn)練樣本。

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

具體步驟如下：

3 結(jié)果

3.1 評價指標(biāo)

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

(7)

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

3.2 變量解釋

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

表2 輸入變量對預(yù)測結(jié)果的相對影響Table 2 Relative influence of input variables on prediction

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

3.3 預(yù)測結(jié)果

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

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

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

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