程　政，陳賢富（中國(guó)科學(xué)技術(shù)大學(xué)信息科學(xué)技術(shù)學(xué)院，安徽合肥230027）

?

基于隨機(jī)森林模型的短時(shí)交通流預(yù)測(cè)方法

程政，陳賢富
（中國(guó)科學(xué)技術(shù)大學(xué)信息科學(xué)技術(shù)學(xué)院，安徽合肥230027）

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

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

0　引言

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

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

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

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

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

1　隨機(jī)森林算法

1.1算法步驟

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

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

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

②在Sr中重復(fù)以下步驟，直到節(jié)點(diǎn)的樣本數(shù)不超過(guò)設(shè)定的最小值Lmtn，得到一個(gè)樹(shù)Tr。

a.在n個(gè)特征變量中隨機(jī)選擇m個(gè)特征變量；

b.從m個(gè)特征變量中選擇最佳的變量j和切分點(diǎn)s得到θr（j，s）；

c.將該節(jié)點(diǎn)依θr（j，s）切分成兩個(gè)孩子節(jié)點(diǎn)。（2）輸出所有生成的決策樹(shù)集合｛Tr｝R1，構(gòu)成隨機(jī)森

林，模型的（回歸）輸出如式（1）所示。

1.2完全生成樹(shù)算法分析

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

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

式（2）中括號(hào)里的兩項(xiàng)可通過(guò)各自求導(dǎo)解得：

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

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

1.3隨機(jī)森林算法分析

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

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

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

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

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

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

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

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

圖1　一周的車流量數(shù)據(jù)

3　實(shí)驗(yàn)分析

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

圖2　短時(shí)車流量預(yù)測(cè)效果

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

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

（1）均方根誤差（Root Mean Square Error）

（2）平均絕對(duì)誤差（Mean Absolute Error）

（3）平均百分比誤差（Mean Absolute Percentage Error）

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

表1　隨機(jī)森林模型預(yù)測(cè)結(jié)果指標(biāo)

圖3　模型錯(cuò)誤率隨m的變化曲線

圖3所示是將超參m分別取1～6構(gòu)建模型，為得到光滑真實(shí)的曲線變化，將每個(gè)模型重復(fù)50遍后，得到其在各個(gè)樣本集上的平均表現(xiàn)與波動(dòng)。當(dāng)m減小時(shí)，訓(xùn)練集上的誤差將增大，而測(cè)試集上的誤差先減小后增大，在m=2時(shí)測(cè)試集上的誤差最小，這說(shuō)明當(dāng)m取較大時(shí)，出現(xiàn)了過(guò)擬合，而當(dāng)m取得太小時(shí)，又會(huì)有欠擬合出現(xiàn)。由于隨機(jī)森林是以一部分偏差的增大作為代價(jià)來(lái)降低模型的方差，這就需要調(diào)節(jié)m來(lái)找到最小的代價(jià)實(shí)現(xiàn)最佳的預(yù)測(cè)輸出。但從OOB和測(cè)試集上的誤差變化來(lái)看，超參m對(duì)于模型預(yù)測(cè)性能的影響有限，同時(shí)超參的取值范圍明確，所以模型對(duì)于參數(shù)調(diào)節(jié)的要求并不高。

4　與SVM模型比較

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

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

表2　模型MAPE及耗時(shí)比較

5　結(jié)論

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

參考文獻(xiàn)

［1］VLAHOGIANNIE I，KARLAFTIS M G，GOLIAS JC.Shortterm traffic forecasting：where we are and where we're going［J］.Transportation Research Part C Emerging Technologies，2014，43（1）：3-19.

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

［3］陸海亭，張寧，黃衛(wèi)，等.短時(shí)交通流預(yù)測(cè)方法研究進(jìn)展［J］.交通運(yùn)輸工程與信息學(xué)報(bào)，2009，7（4）：84-91.

［4］CHEN P H，LIN C J，SCH?LKOPF B.A tutorial on ν-support vectormachines［J］.AppliedStochastic Models in Businessand-Industry，2005，21（2）：111-136.

［5］BREIMAN L.Random forests［J］.Machine Learning，2001，45 （1）：5-32.

［6］BREIMAN L，F(xiàn)RIEDMAN J，CHARLES J S，et al.Classification and Regression Trees［M］.US：Chapman and Hall，1984.

［7］HASTIE T，TIBSHIRANI R，F(xiàn)RIEDMAN J.The element of statistical learning：data mining，inference，and prediction. （2th ed）［M］.US：Springer，2009.

［8］MCKINNEY W.Python for data analysis［M］.US：O'Reilly，2012.

［9］朱征宇，劉琳，崔明.一種結(jié)合SVM與卡爾曼濾波的短時(shí)交通流預(yù)測(cè)模型［J］.計(jì)算機(jī)科學(xué)，2013，40（10）：248-251.

［10］傅貴，韓國(guó)強(qiáng)，逯峰，等.基于支持向量機(jī)回歸的短時(shí)交通流預(yù)測(cè)模型［J］.華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，41（9）：71-76.

［11］BERGSTRA J，BENGIO Y.Random searchforhyper-parameter optimization［J］.Journal of Machine Learning Research，2012，13（1）：281-305.

程政（1991 -），男，碩士研究生，主要研究方向：智能信息處理，機(jī)器學(xué)習(xí)。

陳賢富（1963 -），男，博士，副教授，主要研究方向：復(fù)雜系統(tǒng)與計(jì)算智能。

引用格式：程政，陳賢富.基于隨機(jī)森林模型的短時(shí)交通流預(yù)測(cè)方法［J］.微型機(jī)與應(yīng)用，2016，35（10）：46-49.

The model of short term traffic flow prediction based on the random forest

Cheng Zheng，Chen Xianfu
（School of Information Science and Technology，University of Science and Technology of China，Hefei230027，China）

Abstract：The short term traffic flow prediction is very important to the application of intelligent traffic system（ITS），but it needsmore flexible model for the strong nonlinear and noisy and processes lots of data in short time.This article discusses the random forestmodel for the prediction of short term traffic flow.Themodel has characters such as stronger generalization，easy to adjust the parameter，effective computation and quality stability.It extracts the principal features as the variables to form input space after observing the variation of traffic flow in the longer term.The prediction accuracy of themodel on the test set is 94%after themodel trained on the training set.Compared with the popular support vectormachine（SVM），the random forest has better accuracy prediction.And the random forest is better than SVM on the efficiency，usability and the extension of future usage.

Key w ords：intelligent traffic system；traffic flow prediction；decision tree；random forest；support vectormachine

作者簡(jiǎn)介：

收稿日期：（2016-01-19）

中圖分類號(hào)：TP18

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.19358 /j.issn.1674-7720.2016.09.016