程政，陳賢富

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

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

　　關鍵詞：智能交通；交通流預測；決策樹；隨機森林；支持向量機

0引言

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

　　反映路網狀態的一個重要變量是交通流，即一定時間段內通過某一道路截面的車輛數。優秀的交通誘導系統需要根據在未來短時間（5~15 min）內的道路交通流作出誘導建議，而由于短時交通流數據的非線性和噪聲干擾，使其規律很難把握，對于短時交通流的預測一直是個難點。

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

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

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

1隨機森林算法

　　1.1算法步驟

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

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

　?、購目偟挠柧毤疭中用bootstrap方法抽取一個大小為N的訓練子集Sr；

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

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

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

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

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

　　1.2完全生成樹算法分析

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

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

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

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

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

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

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

　　1.3隨機森林算法分析

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

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

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

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

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

2構造特征向量

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

　　圖1是一周的車流量變化曲線。通過對數據集的大致觀察可以發現，車流量在每24小時和每周均有一定的相似波動，但短時間內卻很不規則。

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

3實驗分析

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

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

　　本文采用如下指標來評估模型的表現：

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

　　表1所示為預測結果指標，可看出OOB集的指標能很好地反映模型的實際表現，故可用來評估模型。模型的預測準確率達到94%，這已可以滿足工程實踐的需求。

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

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

4與SVM模型比較

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

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

5結論

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

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

參考文獻

　?。?］ 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.

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

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

　　［4］ 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.

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

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

　　［10］ 傅貴，韓國強，逯峰，等．基于支持向量機回歸的短時交通流預測模型［J］．華南理工大學學報(自然科學版)，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.