程政，陳賢富

　　(中國科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥 230027)

       摘要：短時交通流的準(zhǔn)確高效預(yù)測對于智能交通系統(tǒng)的應(yīng)用十分關(guān)鍵，但較強的非線性和噪聲干擾使其對模型的靈活性要求較高,并且還需在盡可能短的時間內(nèi)處理大量的數(shù)據(jù)。因此，討論了用隨機森林模型對短時交通流進行預(yù)測，該模型具有比單棵樹更強的泛化能力，參數(shù)調(diào)節(jié)方便，計算高效，且穩(wěn)定性好。觀察交通流數(shù)據(jù)在較長時間跨度上的變化后，提取出主要特征變量構(gòu)造輸入空間，對模型進行訓(xùn)練后，在測試集上的預(yù)測準(zhǔn)確率約為94%。與目前廣泛使用的支持向量機模型進行對比分析，結(jié)果顯示隨機森林預(yù)測不僅準(zhǔn)確率稍好于支持向量機，而且在效率、易用性及未來應(yīng)用的擴展上都要優(yōu)于支持向量機。

　　關(guān)鍵詞：智能交通；交通流預(yù)測；決策樹；隨機森林；支持向量機

0引言

　　現(xiàn)代城市車輛增長的速率遠(yuǎn)大于新修道路的里程數(shù)，由此引發(fā)的道路擁堵、環(huán)境污染等一系列問題給人們的生活帶來了很大不便。解決該問題的最好辦法是發(fā)展智能交通系統(tǒng)（Intelligent Traffic System,ITS），利用交通誘導(dǎo)技術(shù)，提高交通路網(wǎng)通行效率。這要根據(jù)當(dāng)前及未來時間內(nèi)道路網(wǎng)的交通狀態(tài)來為車輛建議較佳的行車路線，從而使車流均衡地分布于路網(wǎng)，發(fā)揮各條道路的最大功用。

　　反映路網(wǎng)狀態(tài)的一個重要變量是交通流，即一定時間段內(nèi)通過某一道路截面的車輛數(shù)。優(yōu)秀的交通誘導(dǎo)系統(tǒng)需要根據(jù)在未來短時間（5~15 min）內(nèi)的道路交通流作出誘導(dǎo)建議，而由于短時交通流數(shù)據(jù)的非線性和噪聲干擾，使其規(guī)律很難把握，對于短時交通流的預(yù)測一直是個難點。

　　早期的預(yù)測模型主要有歷史平均、線性回歸、時間序列等，但預(yù)測精度不高，模型適應(yīng)性不強。近些年研究較多的模型有交通仿真、混沌理論、神經(jīng)網(wǎng)絡(luò)和支持向量機（Support Vector Machine,SVM）［1］。機器學(xué)習(xí)方法由于有較強的理論框架，預(yù)測效果好，越來越成為受歡迎的參考模型。參考文獻(xiàn)［2］總結(jié)了較多的研究和文獻(xiàn)，表明神經(jīng)網(wǎng)絡(luò)有較好的預(yù)測效果，神經(jīng)網(wǎng)絡(luò)一度成為研究的熱點。SVM有比神經(jīng)網(wǎng)絡(luò)更好的泛化（generalization）性能，也比神經(jīng)網(wǎng)絡(luò)更容易優(yōu)化和求解，因此SVM也成為目前預(yù)測交通流較流行的一種方法［3］。

　　但影響SVM［4］性能的超參（hyper parameter）一直沒有很好的確定方法，常用網(wǎng)格搜索（grid search）和隨機搜索（randomize search）結(jié)合交叉驗證（cross validation）。多數(shù)論文也探討了利用進化算法對參數(shù)尋優(yōu)，但這些不僅增加了模型的復(fù)雜度，還耗費了額外的計算時間。

　　因此，本文提出用隨機森林模型來預(yù)測短時交通流，該方法對超參的調(diào)節(jié)要求不高，使用方便，與SVM相比，預(yù)測精度相近，但模型的訓(xùn)練時間卻減少很多，并且適合運行在大規(guī)模的數(shù)據(jù)集上。

1隨機森林算法

　　1.1算法步驟

　　隨機森林［5］算法是BREIMAN L提出的一種集合多棵分類回歸樹（Classification And Regression Tree, CART）進行投票決策的方法。這是Bagging的思想，將多個弱學(xué)習(xí)器集合起來得到一個強的學(xué)習(xí)器。由于交通流預(yù)測的輸出為實數(shù)，因此本文僅討論了隨機森林的回歸算法，該算法如下：

　　（1） For r=1 to R，R為設(shè)定的隨機森林中生成決策樹的棵數(shù):

　?、購目偟挠?xùn)練集S中用bootstrap方法抽取一個大小為N的訓(xùn)練子集Sr；

　?、谠赟r中重復(fù)以下步驟，直到節(jié)點的樣本數(shù)不超過設(shè)定的最小值Lmtn,得到一個樹Tr。

　　a.在n個特征變量中隨機選擇m個特征變量；

　　b.從m個特征變量中選擇最佳的變量j和切分點s得到θr(j,s)；

　　c.將該節(jié)點依θr(j,s)切分成兩個孩子節(jié)點。

　?。?）輸出所有生成的決策樹集合{Tr}R1，構(gòu)成隨機森林，模型的（回歸）輸出如式（1）所示。

　　1.2完全生成樹算法分析

　　以上步驟b中最佳的特征變量j和切分點s的選擇需滿足如下約束條件［6］：

　　其中,x(i)表示第i個樣本值，y(i)表示對應(yīng)的第i個輸出值，P1（j,s）和P2(j,s)為分割后得到的兩個子葉，c1和c2為這兩個子葉的輸出值。

　　式(2)中括號里的兩項可通過各自求導(dǎo)解得：

　　c＾1=ave(y(i)|x(i)∈P1(j,s))

　　c＾2=ave(y(i)|x(i)∈P2(j,s))

　　外層的minj,s可通過掃描所有m個特征變量的值來確定，當(dāng)特征變量含v個有序值時，共有(v-1)種二分方法，當(dāng)特征變量含v個無序值時，共有(2v-1)種二分方法。又由于無序值一般用以表示類別，而類別個數(shù)一般不多，為保證隨機森林中樹之間的獨立性，m的取值也不大，因此這樣的窮舉掃描能很快完成。決策樹的這種特性也使其能很容易地處理有序和無序變量相混合的問題。如在本文中所討論的問題既包含了車流量大小，也可以包含星期、天氣等類別。

　　決策樹可以完全生長來擬合復(fù)雜的數(shù)據(jù)變化，從而具有很低的偏差（bias）和很高的方差(variance)，不過對于訓(xùn)練集中微小的變動，在某一節(jié)點上產(chǎn)生不同分枝并逐層向下傳播，可能產(chǎn)生相差很大的兩棵樹。普通的決策樹模型一般都要進行剪枝（pruning）后才能有較好的泛化性能，否則很容易發(fā)生過擬合（overfitting），但是修剪的程度不好確定。同時決策樹的生長方式會對假設(shè)空間造成搜索偏置，使得無法保證找到一棵全局最優(yōu)決策樹。所以，決策樹生長方式相對簡單，擬合能力強，但不容易得到很好的泛化性能。

　　1.3隨機森林算法分析

　　隨機森林算法是從總樣本集中用bootstrap方法抽取一個子集來訓(xùn)練決策樹，因此可認(rèn)為每一棵樹服從同一分布，則隨機森林中樹的平均輸出的期望E(1RRr=1Tr)等于每棵樹的期望E(Tr)。這即說明隨機森林與單棵樹有同樣的偏差，其泛化性能的提高需要通過減少方差來實現(xiàn)，即平均許多帶噪聲的近似無偏模型來減少它們的方差［7］。

　　設(shè)樹的方差D(Ti)=σ2，并且任意兩棵樹具有正的相關(guān)系數(shù)ρ，則輸出均值的方差為：

　　D(1RRr-1Tr)=ρσ2+1-ρRσ2(3)

　　由(3)式可看出，當(dāng)樹的數(shù)量R很大時，右側(cè)第二項將接近于零，但第一項將保持不變。在生成樹的過程中，每一個節(jié)點分裂成兩個分枝之前，都隨機選取m≤n個輸入特征向量來供分枝算法使用，這將使得每棵樹之間的相關(guān)系數(shù)ρ減小，并且當(dāng)減小m時也會減小ρ,由式(3)綜上可知,即減小了輸出均值的方差。但同時需要注意的是，當(dāng)m減小時，決策樹能獲得樣本的數(shù)據(jù)減少，偏差將增大，從而使得隨機森林的偏差也增大。對于回歸問題，BREIMAN L建議m的值取為n/3」，最小節(jié)點樣本數(shù)lmin=5，但還是要依據(jù)實際問題對這些超參進行調(diào)節(jié)。

　　由于使用bootstrap抽樣，故總樣本集S中會留有一部分未使用的數(shù)據(jù)（Out of Bag, OOB），可以作為模型預(yù)測效果的驗證，而不需要使用交叉驗證的方式，這也提高了參數(shù)的調(diào)節(jié)效率。

2構(gòu)造特征向量

　　本文采用了加利福利亞州交通管理局的PEMS網(wǎng)站的公開數(shù)據(jù)進行研究，數(shù)據(jù)來源于鋪設(shè)于道路下面的線圈傳感器采集的車流量數(shù)據(jù)，傳感器全天候工作，每隔30 s報送一次數(shù)據(jù)，經(jīng)累積后成為5 min時間段數(shù)據(jù)?！?/p>

　　圖1是一周的車流量變化曲線。通過對數(shù)據(jù)集的大致觀察可以發(fā)現(xiàn)，車流量在每24小時和每周均有一定的相似波動，但短時間內(nèi)卻很不規(guī)則。

　　所以要對路段未來時刻的車流量進行預(yù)測，需要加入時刻和星期作為特征變量，以及之前緊鄰時間段的車流量數(shù)據(jù)。設(shè)路段某一時刻的車流量為flow(t)，則可構(gòu)造輸入空間特征向量為:x0=weekday，x1=t，x2=flow(t)，x3=flow(t-1)，x4=flow(t-2)， x5=flow(t-3)。對應(yīng)輸出為當(dāng)前時刻后一時間間隔單位的車流量y=flow(t+1)。其中t為間隔時間，可取5 min、10 min、15 min。對數(shù)據(jù)進行清洗、整合后［8］,取8周的數(shù)據(jù)作為訓(xùn)練集，一周的數(shù)據(jù)作為測試集。

3實驗分析

　　由于隨機森林經(jīng)常被作為無需調(diào)節(jié)參數(shù)的模型直接使用，本文首先采用默認(rèn)值100棵樹，分枝特征數(shù)為2，最小節(jié)點樣本數(shù)為5作為模型的超參。硬件平臺為Intel雙核T6500處理器，3 GB內(nèi)存的計算機，輸入整理好的某一監(jiān)測點的訓(xùn)練數(shù)據(jù)，運行2.6 s后得到針對該路段的5 min短時交通流預(yù)測模型。

　　對模型輸入測試數(shù)據(jù)后得到的預(yù)測結(jié)果如圖2所示。其中圖2(a)為取測試集中某一天實際觀測值和模型預(yù)測輸出值在相同時刻疊加，可看出在短時間內(nèi)交通流出現(xiàn)了頻繁的變化，但模型預(yù)測輸出能很好地跟隨實際數(shù)據(jù)。圖2(b)將一周的車流量數(shù)據(jù)的觀測值和預(yù)測值分別作為x、y坐標(biāo)值繪制，其中絕大部分點均聚集在y=x直線上，這反映了在整個測試集上模型對實際數(shù)據(jù)也具有很好的擬合性能。

　　本文采用如下指標(biāo)來評估模型的表現(xiàn)：

　?。?）均方根誤差（Root Mean Square Error）

　　表1所示為預(yù)測結(jié)果指標(biāo)，可看出OOB集的指標(biāo)能很好地反映模型的實際表現(xiàn)，故可用來評估模型。模型的預(yù)測準(zhǔn)確率達(dá)到94%，這已可以滿足工程實踐的需求。

　　圖3所示是將超參m分別取1~6構(gòu)建模型，為得到光滑真實的曲線變化，將每個模型重復(fù)50遍后，得到其在各個樣本集上的平均表現(xiàn)與波動。當(dāng)m減小時，訓(xùn)練集上的誤差將增大，而測試集上的誤差先減小后增大，在m=2時測試集上的誤差最小，這說明當(dāng)m取較大時，出

　　現(xiàn)了過擬合，而當(dāng)m取得太小時，又會有欠擬合出現(xiàn)。由于隨機森林是以一部分偏差的增大作為代價來降低模型的方差，這就需要調(diào)節(jié)m來找到最小的代價實現(xiàn)最佳的預(yù)測輸出。但從OOB和測試集上的誤差變化來看，超參m對于模型預(yù)測性能的影響有限，同時超參的取值范圍明確，所以模型對于參數(shù)調(diào)節(jié)的要求并不高。

4與SVM模型比較

　　在交通流預(yù)測問題上，SVM已被較多文獻(xiàn)證明具有優(yōu)于其他多種模型的表現(xiàn)［910］，因此本文選用了應(yīng)用較為廣泛的嵌入RBF核函數(shù)的SVR作為對比，該模型中懲罰系數(shù)C、核參數(shù)γ、回歸參數(shù)ε均需要調(diào)節(jié)，因此參數(shù)的尋優(yōu)較復(fù)雜。并且SVR模型在訓(xùn)練之前還應(yīng)對各特征變量作標(biāo)準(zhǔn)化處理。

　　取5 min、10 min、15 min間隔的車流量進行預(yù)測，任選一組參數(shù)值的SVR模型和經(jīng)隨機搜索算法［11］得到的最優(yōu)SVR模型、隨森林模型作實驗對比。從表2的實驗結(jié)果可以看出，SVR的參數(shù)直接決定了模型的好壞，SVR模型的優(yōu)化要耗費較多時間。并且，在相同數(shù)據(jù)集上，SVR的每一次訓(xùn)練時間可達(dá)隨機森林的十多倍，當(dāng)數(shù)據(jù)量增大時，差距將更大，這嚴(yán)重降低了模型在實時交通流預(yù)測問題中的實際應(yīng)用價值。與此同時，隨機森林的預(yù)測表現(xiàn)比SVR優(yōu)化參數(shù)后的表現(xiàn)還要稍好一點。

5結(jié)論

　　對于短時交通流預(yù)測問題，與人工神經(jīng)網(wǎng)絡(luò)和SVM相比，隨機森林參數(shù)調(diào)節(jié)方便，模型訓(xùn)練時間短，同時還有較好的預(yù)測精度。在輸入特征變量處理上，其內(nèi)部的決策樹模型能很好地適應(yīng)連續(xù)和離散變量，還能容忍小部分?jǐn)?shù)據(jù)的缺失。并且，在實際應(yīng)用中，需要監(jiān)控的是整個路網(wǎng)的狀態(tài)，輸入變量可能會涵蓋更多相鄰道路數(shù)據(jù)，為了提高預(yù)測精度，還需引入突發(fā)事故、道路施工、天氣狀況等特征變量，使得輸入向量的維數(shù)很高，同時每

　　時每刻又有海量的交通數(shù)據(jù)可以回傳用作模型的在線訓(xùn)練，隨機森林的特性可以使其將高維向量分散到低維處理，又能夠同時在不同的機器上單獨生成樹，從而能高效地建模求解。

參考文獻(xiàn)

　?。?］ VLAHOGIANNI E I, KARLAFTIS M G, GOLIAS J C. Short-term traffic forecasting: where we are and where we’re going［J］. Transportation Research Part C Emerging Technologies,2014,43(1):319.

　?。?］ 王凡．基于支持向量機的交通流預(yù)測方法研究［D］．大連：大連理工大學(xué)，2010.

　　［3］ 陸海亭，張寧，黃衛(wèi)，等．短時交通流預(yù)測方法研究進展［J］．交通運輸工程與信息學(xué)報，2009,7(4):8491.

　?。?］ CHEN P H, LIN C J, SCHLKOPF B. A tutorial on νsupport vector machines［J］.AppliedStochastic Models in BusinessandIndustry,2005,21(2):111136.

　?。?］ BREIMAN L.Random forests［J］. Machine Learning,2001,45(1):532.

　?。?］ BREIMAN L, FRIEDMAN J, CHARLES J S, et al.Classification and Regression Trees［M］. US: Chapman and Hall, 1984.

　　［7］ HASTIE T, TIBSHIRANI R, FRIEDMAN J. The element of statistical learning: data mining, inference, and prediction. (2th ed)［M］.US: Springer, 2009.

　?。?］ MCKINNEY W. Python for data analysis［M］. US: O’Reilly, 2012.

　　［9］ 朱征宇，劉琳，崔明．一種結(jié)合SVM與卡爾曼濾波的短時交通流預(yù)測模型［J］．計算機科學(xué)，2013, 40(10): 248251.

　?。?0］ 傅貴，韓國強，逯峰，等．基于支持向量機回歸的短時交通流預(yù)測模型［J］．華南理工大學(xué)學(xué)報(自然科學(xué)版)，2013,41(9):7176.

　?。?1］ BERGSTRA J, BENGIO Y. Random searchforhyperparameter optimization［J］.Journal of Machine Learning Research, 2012, 13(1): 281305.