白小曼， 馮永祥，2*， 李雷孝，2， 張利平， 馬志強，2， 王永生，2， 王 慧，2

(1.內(nèi)蒙古工業(yè)大學(xué)數(shù)據(jù)科學(xué)與應(yīng)用學(xué)院， 呼和浩特 010080； 2.內(nèi)蒙古自治區(qū)基于大數(shù)據(jù)的軟件服務(wù)工程技術(shù)研發(fā)中心， 呼和浩特 010080)

隨著中國社會經(jīng)濟的快速發(fā)展，機動車保有量逐年迅速上漲，交通擁堵現(xiàn)象在各大城市路網(wǎng)中頻發(fā)，以交通擁堵為主的各種交通問題已成為制約中國眾多城市交通發(fā)展的重要問題。有效預(yù)測擁堵情況的發(fā)生、及時對可能出現(xiàn)的擁堵采取預(yù)防措施，可以有效提高城市交通通行效率、節(jié)約出行時間、降低環(huán)境污染和能源浪費。因此，如何有效對交通擁堵進行預(yù)測，是近年來學(xué)者們聚焦的熱點問題。

傳統(tǒng)的交通擁堵預(yù)測方法通常采用基于統(tǒng)計和微積分的數(shù)學(xué)方法，如時間序列、卡爾曼濾波、馬爾可夫模型等，對短期交通擁堵情況進行預(yù)測[1-5]。在后續(xù)的研究中，學(xué)者們提出了很多基于機器學(xué)習(xí)和深度學(xué)習(xí)的預(yù)測研究方法。韋清波等[6]考慮了特殊條件對交通狀況的影響，將天氣、重大活動、節(jié)假日等等綜合考慮，分析道路擁堵指數(shù)總體變化趨勢，基于K近鄰構(gòu)建城市道路擁堵預(yù)測模型，并通過實驗驗證了模型效果。呂鮮等[7]考慮了交通流特征，利用去躁自編碼模型提取數(shù)據(jù)核心特征，結(jié)合LSTM(long short-term memory)模型長時記憶歷史數(shù)據(jù)。實驗證明，該模型可以對城市道路擁堵進行有效預(yù)測，但訓(xùn)練速度較慢，消耗的計算資源較多。邢一鳴等[8]提出了組合多個超限學(xué)習(xí)機子模型而成的核超限學(xué)習(xí)機擁堵預(yù)測模型，實驗證明，相比超限學(xué)習(xí)機提高了準(zhǔn)確率和訓(xùn)練速度。曹潔等[9]提出了基于信息熵加權(quán)的FCM(FuzzyC-means)聚類算法識別局部路網(wǎng)交通狀態(tài)的方法，相較于傳統(tǒng)FCM聚類算法在一定程度上提高了準(zhǔn)確率，其模型性能受聚類中心個數(shù)選取的影響，可通過進一步研究以達到更好的效果。晏雨嬋等[10]提出了一種多指標(biāo)模糊擁堵級別評價方法，利用PSO-SVR(particle swarm optimization-support vector regression)預(yù)測平均速度和交通流量進行交通擁堵級別模糊評價，提升了預(yù)測效果。陳忠輝等[11]提出一種模糊C均值聚類融合隨機森林的短時交通狀態(tài)預(yù)測模型，利用FCM算法評估歷史交通狀態(tài)，并通過隨機森林進行短時交通專題預(yù)測，提升了預(yù)測準(zhǔn)確率。

在交通擁堵預(yù)測領(lǐng)域，中外學(xué)者已取得較為豐碩的研究成果。由于隨機森林算法既能處理離散型數(shù)據(jù)，也能處理連續(xù)型數(shù)據(jù)，且訓(xùn)練速度快，非常適合用于研究交通數(shù)據(jù)?，F(xiàn)針對隨機森林模型的特性，采用低復(fù)雜度且能夠迅速確定最優(yōu)解的陰陽對優(yōu)化算法對隨機森林的關(guān)鍵參數(shù)進行合理選取，提高預(yù)測準(zhǔn)確性，并利用Spark機器學(xué)習(xí)平臺針對隨機森林進行并行化設(shè)計，以期達到提高計算速度和計算精度的目的，以便更好地對城市道路擁堵情況進行預(yù)測。

1 相關(guān)算法研究

1.1 隨機森林算法

隨機森林(random forest)是由Breiman[12]提出的一種集成機器學(xué)習(xí)方法。它的主要思想是通過隨機抽樣的方式建立由多個互不關(guān)聯(lián)的決策樹組成的森林；每棵決策樹均采用bagging方法進行抽樣。對于城市道路交通數(shù)據(jù)集，假設(shè)訓(xùn)練集樣本個數(shù)為X，共有M個決策屬性，從中有放回地隨機抽取x個樣本構(gòu)造道路交通訓(xùn)練子集，再從所有M個決策屬性中隨機選擇m個屬性構(gòu)造道路交通特征子集。利用訓(xùn)練子集和特征子集構(gòu)造對應(yīng)的決策樹，需要n棵樹，則隨機抽樣n次；訓(xùn)練結(jié)束后，將待測試數(shù)據(jù)輸入訓(xùn)練好的森林中，利用森林中的決策樹對數(shù)據(jù)進行分類，采用投票的思想，選擇決策樹分類最多的類別作為測試數(shù)據(jù)的最終類別。

在隨機森林模型構(gòu)建過程中，決策樹數(shù)量(ntree)和分裂屬性個數(shù)(mtry)兩個參數(shù)設(shè)置的大小對其模型預(yù)測精度有著至關(guān)重要的影響。若這兩個參數(shù)設(shè)置不合理，則在訓(xùn)練過程中會使模型出現(xiàn)過擬合或欠擬合現(xiàn)象，進而嚴(yán)重降低隨機森林預(yù)測準(zhǔn)確性。因此，為提高隨機森林模型預(yù)測精度，選取陰陽對優(yōu)化算法對隨機森林進行參數(shù)調(diào)優(yōu)。

1.2 陰陽對優(yōu)化算法

陰陽對優(yōu)化算法(Yin-Yang-pair optimization, YYPO)是Punnathanam等[13]于2016年提出的一種新型的元啟發(fā)式算法。它能迅速確定最優(yōu)解，是一種低復(fù)雜度的隨機算法，基于陰陽平衡原理通過利用和探索兩個點進行工作，并根據(jù)優(yōu)化問題中決策變量的數(shù)量產(chǎn)生相應(yīng)維度的點。

YYPO算法根據(jù)待優(yōu)化問題的維度D隨機生成兩個點P1和P2。P1專注于利用變量空間，P2專注于探索變量空間，點P1和P2作為中心分別負責(zé)變量空間中以δ1和δ2為半徑的超球體。該算法包括兩個主要階段，分裂階段和存檔階段。分裂階段用于在迭代過程中搜索兩個點半徑范圍內(nèi)的超球體；存檔階段用于存儲分裂階段搜索后的P1和P2點和通過比較存檔中的點的適應(yīng)度更新P1、P2，并根據(jù)用戶定義的擴展/收縮因子α更新δ1和δ2。

1.2.1 分裂階段

分裂階段的目的是在以點P為球心的半徑為δ的超球體中于盡可能變化的方向上以隨機的方式生成新的點，利用適應(yīng)性函數(shù)評估產(chǎn)生的新點適應(yīng)度，將最適點替換為當(dāng)前點并記入存檔。分裂階段主要有兩種分裂方式：單向分裂和多向分裂。每次分裂通過范圍在0～1的隨機生成數(shù)R來決定分裂方式。

(1)單向分裂：設(shè)置矩陣S，它表示點P的2D維度的相同副本，大小為2D×D。矩陣S中的每一個點按式(1)所示設(shè)置。

(1)

式(1)中：上標(biāo)為行號；下標(biāo)為列號；r為0～1的隨機數(shù)矩陣；δ為點的半徑。

(2)多向分裂：同樣存在矩陣S，它表示點P的二維相同副本，大小為2D×D。矩陣S中的每一個點按式(2)所示設(shè)置。

(2)

式(2)中：B為由一個長度為D的二進制字符串組成的矩陣，其中每一個字符串通過隨機選擇0～(2D-1)之間的2D個唯一整數(shù)轉(zhuǎn)換而成。

1.2.2 存檔階段

存檔階段在計數(shù)器i達到存檔更新次數(shù)I后啟動。此時存檔中包含2I個點，分別對應(yīng)分裂階段每次更新之前添加的兩個點P1、P2。比較存檔中點與當(dāng)前P1、P2的適應(yīng)度，將最優(yōu)點替換為P1、P2。替換后使用式(3)更新搜索半徑δ1、δ2。

(3)

式(3)中：α為擴展/收縮因子。

1.2.3 YYPORF模型

采用陰陽對優(yōu)化算法對隨機森林ntree和mtry進行尋優(yōu)，主要基于P點適應(yīng)度傾向于極小值的趨勢，即模型預(yù)測誤差最小。YYPORF步驟如下。

步驟1設(shè)置存檔更新范圍Imin和Imax，擴展/收縮因子α，迭代最大次數(shù)T，待優(yōu)化參數(shù)決策樹數(shù)量ntree和分裂屬性個數(shù)mtry取值范圍lb和ub。

步驟2確定模型適應(yīng)性函數(shù)。定義隨機森林模型的分類誤差Erro如式(4)所示：

Erro=1-acc

(4)

式(4)中：acc為模型分類準(zhǔn)確率。適應(yīng)度函數(shù)f描述如式(5)所示：

生態(tài)監(jiān)測工作在青海省是一項開創(chuàng)性的工作，專業(yè)性很強，涉及多個部門和多個專業(yè)，要結(jié)合我們所開展的工作和取得的成果，通過發(fā)布信息、媒體報道，充分提升各級政府和全社會對生態(tài)監(jiān)測工作重要性的認識。

minf(ntree,mtry)=fRF=Erro=1-acc

(5)

步驟4迭代開始，在存檔更新范圍內(nèi)隨機產(chǎn)生存檔更新次數(shù)I，初始化計數(shù)器i=0，利用模型適應(yīng)度函數(shù)評估P1、P2的適應(yīng)度，若P2的適應(yīng)度優(yōu)于P1，互換兩個點。將P1、P2記入存檔。啟動分裂階段。

步驟5利用式(1)、式(2)分別對P1、P2點進行分裂操作，通過適應(yīng)度函數(shù)評估分裂階段產(chǎn)生的新點的適應(yīng)度，將最適點替換為正在經(jīng)歷分裂的P點，計數(shù)器i加1。

步驟6若i

步驟7比較存檔中P1、P2與當(dāng)前P1、P2的適應(yīng)度，若存檔中最優(yōu)點優(yōu)于當(dāng)前P1、P2點，則替換當(dāng)前P1、P2點。

步驟8若未達到最大迭代次數(shù)T，利用式(3)更新P1、P2點搜索半徑δ1、δ2，計數(shù)器i歸零，于Imin和Imax之間隨機產(chǎn)生新的存檔更新次數(shù)I，重復(fù)步驟4～步驟8，進入下一輪迭代。

步驟9滿足最大迭代次數(shù)，獲得ntree和mtry最優(yōu)解。

YYPORF算法流程圖如圖1所示。

圖1 YYPORF算法流程圖Fig.1 Flow chart of YYPORF

1.3 并行化設(shè)計

利用Spark大數(shù)據(jù)平臺進行城市道路擁堵預(yù)測模型的并行化構(gòu)建。Spark是一種與Hadoop相似的開源集群計算環(huán)境，具有類似MapReduce的編程模型。Spark提供大量的庫，以Spark Core作為核心，提供Spark SQL、GraphX 、MLlib、Streaming等多種功能接口[14-18]。與MapReduce相比，Spark具有數(shù)倍于它的批處理速度和數(shù)十倍的數(shù)據(jù)分析速度[19]，更適用與處理城市道路交通數(shù)據(jù)集。

在使用Spark進行城市道路擁堵預(yù)測時，首先將城市道路交通數(shù)據(jù)轉(zhuǎn)化為具有數(shù)據(jù)共享抽象的彈性分布式數(shù)據(jù)集RDD(resilient distributed dataset)[20]。每個RDD可以分成多個分區(qū)，并且在集群的不同節(jié)點進行保存，從而達到的集群各個節(jié)點上并行計算的目的[21-22]。

在 Spark 上平臺上對隨機森林算法的并行化設(shè)計步驟如下。

步驟1從HDFS(hadoop distributed file system)讀取城市道路交通數(shù)據(jù)集，合理劃分為訓(xùn)練集和測試集。本文研究的集群由4個節(jié)點組成，將訓(xùn)練集復(fù)制4份分發(fā)給每個節(jié)點。

步驟2假設(shè)需要創(chuàng)建的決策樹數(shù)目為n，共有4個節(jié)點，每個節(jié)點負責(zé)創(chuàng)建n/4棵決策樹，各節(jié)點利用map()方法構(gòu)建訓(xùn)練子集，通過boosttrap sample()抽樣并行創(chuàng)建決策樹，各得到一個包含n/4個決策樹的集合。創(chuàng)建決策樹后，利用reduce()方法將所有決策樹整合為長度為n的決策樹集合，即訓(xùn)練得到的隨機森林模型。

步驟3使用訓(xùn)練得到的隨機森林模型對測試集進行預(yù)測，并將結(jié)果上傳至HDFS。

隨機森林算法并行化設(shè)計如圖2所示。

圖2 隨機森林并行化設(shè)計Fig.2 Parallel design of random forest

2 實驗設(shè)計與結(jié)果分析

2.1 數(shù)據(jù)預(yù)處理

采用合肥示范區(qū)黃科路口相關(guān)數(shù)據(jù)，包含微波數(shù)據(jù)6萬條和車輛GPS(global positioning system)數(shù)據(jù)36萬條共42萬條數(shù)據(jù)作為數(shù)據(jù)集。整合兩項數(shù)據(jù)集，根據(jù)交通數(shù)據(jù)的實際情況，對城市道路交通數(shù)據(jù)進行預(yù)處理。以1 min為一段，將每分鐘內(nèi)數(shù)據(jù)合并，并計算每一個時間段內(nèi)經(jīng)過道路的車流量、平均速度、占有率及密度。整理數(shù)據(jù)后，通過閾值法和交通流機理法對原始城市道路交通數(shù)據(jù)進行異常值的判斷。

2.1.1 閾值法

通過考慮城市道路交通數(shù)據(jù)中單個參數(shù)的特征確定交通數(shù)據(jù)項的閾值。本文研究主要衡量的交通項為車流量、平均速度和車道占有率。

車流量q、平均速度v、車道占有率p的取值范圍如式(6)所示：

(6)

式(6)中：qmin、qmax、vmin、vmax、pmin、pmax分別為車流量q、平均速度v、占有率p的上下限；qmin、vmin、pmin取值為0；qmax取決于路段通行能力；vmax取決于路段限速；pmax取95%。

2.2.2 交通流機理法

其基本思想是城市道路交通數(shù)據(jù)中的各項交通參數(shù)之間不能存在互相矛盾的關(guān)系。根據(jù)交通流機理法的交通數(shù)據(jù)項異常判別規(guī)則如表1所示。

表1 交通數(shù)據(jù)異常判別規(guī)則Table 1 Abnormal discrimination rules of traffic data

篩選出問題數(shù)據(jù)后，采用移動平均法和歷史趨勢法進行數(shù)據(jù)處理工作。單點異常使用移動平均法，利用異常數(shù)據(jù)的附近數(shù)據(jù)值修復(fù)異常數(shù)據(jù)，公式如式(7)所示。異常數(shù)據(jù)少于當(dāng)日數(shù)據(jù)三分之一時，利用歷史趨勢法，使用上周正常數(shù)據(jù)替換異常日數(shù)據(jù)，公式如式(8)所示。當(dāng)問題數(shù)據(jù)大于當(dāng)日數(shù)據(jù)的三分之一時，為避免強行修復(fù)反而人為增加噪點的情況，舍棄當(dāng)日數(shù)據(jù)。

(7)

(8)

2.2 實驗結(jié)果與分析

2.2.1 實驗環(huán)境

采用由4個工作節(jié)點建立的計算集群，其中包含Spark的1個Master節(jié)點和3個Slave節(jié)點。Spark集群節(jié)點配置如表2所示。

表2 節(jié)點配置參數(shù)Table 2 Node configuration parameters

2.2.2 準(zhǔn)確率實驗

本實驗選取準(zhǔn)確率(accuracy)、精確率(precision)、召回率(recall)和F1度量(F1-measure)作為評價指標(biāo)，分別使用K近鄰(KNN)、長短期記憶神經(jīng)網(wǎng)絡(luò)(LSTM)、原始隨機森林和本文提出的模型對處理后的數(shù)據(jù)進行道路擁堵情況預(yù)測，分別運算10次計算平均值。準(zhǔn)確率實驗結(jié)果如表3所示。

表3 準(zhǔn)確率實驗結(jié)果Table 3 Results of accuracy experiment

由表3可知，KNN在城市道路擁堵情況方面的預(yù)測效果最差，其準(zhǔn)確率、精確率、召回率和F1均為最低；原始RF和LSTM的預(yù)測效果次之，較KNN有所提高；YYPORF模型在4個評價指標(biāo)上對城市道路擁堵的預(yù)測均較好，準(zhǔn)確率為95.58%，精確率95.78%，召回率95.6%，F(xiàn)1為0.955 9。由此看出，YYPORF模型可以有效預(yù)測道路擁堵狀況，符合實際道路交通擁堵情況，能夠?qū)煌ü芾聿块T提供有效決策支持。

2.2.3 加速比實驗

加速比表示集群并行化通過增加節(jié)點數(shù)量，對提升運行速度減少運行時間帶來的性能提升[23]，其公式如式(9)所示：

(9)

式(9)中：TS為單個節(jié)點情況下進行預(yù)測所消耗的時間；TP為在P個性能相同的節(jié)點并行計算的情況下進行預(yù)測所消耗的時間。

本實驗采用4個節(jié)點組成的集群，對原有數(shù)據(jù)集進行擴增，驗證模型在不同節(jié)點不同數(shù)據(jù)量情況下的加速比。實驗結(jié)果如圖3所示。

圖3 加速比實驗結(jié)果Fig.3 Results of speedup radio experiment

由圖3可以看出，在數(shù)據(jù)集大小為60 M時，隨著節(jié)點個數(shù)的增加，加速比有少量提升；在數(shù)據(jù)集大小為120 M時，加速比的提升趨勢逐漸明顯；在數(shù)據(jù)集大小為240 M時，加速比的提升趨勢非常明顯。由此可以看出，當(dāng)數(shù)據(jù)量不太大時，節(jié)點數(shù)目增加可以使計算速度逐步提升、運行時間逐漸減少，但提升的趨勢一開始并不明顯。這是因為，在計算量小的情況下，集群系統(tǒng)的啟動、任務(wù)調(diào)度和數(shù)據(jù)通信會增加時間消耗，降低計算速度。當(dāng)數(shù)據(jù)量增大、集群的節(jié)點數(shù)增加后，集群的加速比呈現(xiàn)線性增長狀態(tài)，逐漸趨近理想值。因此，本文研究提出的使用Spark大數(shù)據(jù)平臺的隨機森林并行化方案能夠有效提高隨機森林的計算速度，減少運行時間。

2.2.4 可擴展性實驗

可擴展性用于評價在集群的節(jié)點個數(shù)增加時算法性能按照節(jié)點個數(shù)比例提高的能力。由于節(jié)點個數(shù)的增加會帶來額外的通信開銷的增長，因此在增加節(jié)點個數(shù)的同時會致使每個節(jié)點的利用率降低[24]。因此使用可擴展性衡量算法并行化對于有效可擴展節(jié)點個數(shù)的利用能力。其公式如式(10)所示：

(10)

式(10)中：P為節(jié)點個數(shù)；SpP為P個節(jié)點上的加速比。

可擴展性實驗結(jié)果如圖4所示。圖4可以看出，隨著節(jié)點數(shù)目的增加，算法的運行時間逐漸減少；隨著數(shù)據(jù)量的增加，算法的運行時間也逐漸減少；且隨著數(shù)據(jù)集大小和節(jié)點個數(shù)的增加，模型的運行時間增長的倍數(shù)始終低于數(shù)據(jù)集大小和節(jié)點個數(shù)的增長倍數(shù)。因此，基于Spark的隨機森林模型具有良好的可擴展性。

圖4 可擴展性實驗結(jié)果Fig.4 Results of scalability experiment

4 結(jié)論

提出一種基于Spark大數(shù)據(jù)平臺的陰陽對優(yōu)化隨機森林模型對城市道路擁堵情況進行預(yù)測，利用陰陽對優(yōu)化對影響隨機森林精度的關(guān)鍵參數(shù)進行參數(shù)優(yōu)化。通過基于真實數(shù)據(jù)的實驗，得到以下結(jié)論。

(1)提出的模型較其他預(yù)測算法具有較高的精度，預(yù)測準(zhǔn)確率達到95.58%，提高了模型準(zhǔn)確率。

(2)提出的并行化設(shè)計方案能夠提高模型計算速度，降低運行時間，具有良好的可擴展性，能夠為交通管理部門的決策提供有力支持。