白小曼, 馮永祥,2*, 李雷孝,2, 張利平, 馬志強(qiáng),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)
隨著中國社會(huì)經(jīng)濟(jì)的快速發(fā)展,機(jī)動(dòng)車保有量逐年迅速上漲,交通擁堵現(xiàn)象在各大城市路網(wǎng)中頻發(fā),以交通擁堵為主的各種交通問題已成為制約中國眾多城市交通發(fā)展的重要問題。有效預(yù)測擁堵情況的發(fā)生、及時(shí)對可能出現(xiàn)的擁堵采取預(yù)防措施,可以有效提高城市交通通行效率、節(jié)約出行時(shí)間、降低環(huán)境污染和能源浪費(fèi)。因此,如何有效對交通擁堵進(jìn)行預(yù)測,是近年來學(xué)者們聚焦的熱點(diǎn)問題。
傳統(tǒng)的交通擁堵預(yù)測方法通常采用基于統(tǒng)計(jì)和微積分的數(shù)學(xué)方法,如時(shí)間序列、卡爾曼濾波、馬爾可夫模型等,對短期交通擁堵情況進(jìn)行預(yù)測[1-5]。在后續(xù)的研究中,學(xué)者們提出了很多基于機(jī)器學(xué)習(xí)和深度學(xué)習(xí)的預(yù)測研究方法。韋清波等[6]考慮了特殊條件對交通狀況的影響,將天氣、重大活動(dòng)、節(jié)假日等等綜合考慮,分析道路擁堵指數(shù)總體變化趨勢,基于K近鄰構(gòu)建城市道路擁堵預(yù)測模型,并通過實(shí)驗(yàn)驗(yàn)證了模型效果。呂鮮等[7]考慮了交通流特征,利用去躁自編碼模型提取數(shù)據(jù)核心特征,結(jié)合LSTM(long short-term memory)模型長時(shí)記憶歷史數(shù)據(jù)。實(shí)驗(yàn)證明,該模型可以對城市道路擁堵進(jìn)行有效預(yù)測,但訓(xùn)練速度較慢,消耗的計(jì)算資源較多。邢一鳴等[8]提出了組合多個(gè)超限學(xué)習(xí)機(jī)子模型而成的核超限學(xué)習(xí)機(jī)擁堵預(yù)測模型,實(shí)驗(yàn)證明,相比超限學(xué)習(xí)機(jī)提高了準(zhǔn)確率和訓(xùn)練速度。曹潔等[9]提出了基于信息熵加權(quán)的FCM(FuzzyC-means)聚類算法識別局部路網(wǎng)交通狀態(tài)的方法,相較于傳統(tǒng)FCM聚類算法在一定程度上提高了準(zhǔn)確率,其模型性能受聚類中心個(gè)數(shù)選取的影響,可通過進(jìn)一步研究以達(dá)到更好的效果。晏雨嬋等[10]提出了一種多指標(biāo)模糊擁堵級別評價(jià)方法,利用PSO-SVR(particle swarm optimization-support vector regression)預(yù)測平均速度和交通流量進(jìn)行交通擁堵級別模糊評價(jià),提升了預(yù)測效果。陳忠輝等[11]提出一種模糊C均值聚類融合隨機(jī)森林的短時(shí)交通狀態(tài)預(yù)測模型,利用FCM算法評估歷史交通狀態(tài),并通過隨機(jī)森林進(jìn)行短時(shí)交通專題預(yù)測,提升了預(yù)測準(zhǔn)確率。
在交通擁堵預(yù)測領(lǐng)域,中外學(xué)者已取得較為豐碩的研究成果。由于隨機(jī)森林算法既能處理離散型數(shù)據(jù),也能處理連續(xù)型數(shù)據(jù),且訓(xùn)練速度快,非常適合用于研究交通數(shù)據(jù)。現(xiàn)針對隨機(jī)森林模型的特性,采用低復(fù)雜度且能夠迅速確定最優(yōu)解的陰陽對優(yōu)化算法對隨機(jī)森林的關(guān)鍵參數(shù)進(jìn)行合理選取,提高預(yù)測準(zhǔn)確性,并利用Spark機(jī)器學(xué)習(xí)平臺針對隨機(jī)森林進(jìn)行并行化設(shè)計(jì),以期達(dá)到提高計(jì)算速度和計(jì)算精度的目的,以便更好地對城市道路擁堵情況進(jìn)行預(yù)測。
隨機(jī)森林(random forest)是由Breiman[12]提出的一種集成機(jī)器學(xué)習(xí)方法。它的主要思想是通過隨機(jī)抽樣的方式建立由多個(gè)互不關(guān)聯(lián)的決策樹組成的森林;每棵決策樹均采用bagging方法進(jìn)行抽樣。對于城市道路交通數(shù)據(jù)集,假設(shè)訓(xùn)練集樣本個(gè)數(shù)為X,共有M個(gè)決策屬性,從中有放回地隨機(jī)抽取x個(gè)樣本構(gòu)造道路交通訓(xùn)練子集,再從所有M個(gè)決策屬性中隨機(jī)選擇m個(gè)屬性構(gòu)造道路交通特征子集。利用訓(xùn)練子集和特征子集構(gòu)造對應(yīng)的決策樹,需要n棵樹,則隨機(jī)抽樣n次;訓(xùn)練結(jié)束后,將待測試數(shù)據(jù)輸入訓(xùn)練好的森林中,利用森林中的決策樹對數(shù)據(jù)進(jìn)行分類,采用投票的思想,選擇決策樹分類最多的類別作為測試數(shù)據(jù)的最終類別。
在隨機(jī)森林模型構(gòu)建過程中,決策樹數(shù)量(ntree)和分裂屬性個(gè)數(shù)(mtry)兩個(gè)參數(shù)設(shè)置的大小對其模型預(yù)測精度有著至關(guān)重要的影響。若這兩個(gè)參數(shù)設(shè)置不合理,則在訓(xùn)練過程中會(huì)使模型出現(xiàn)過擬合或欠擬合現(xiàn)象,進(jìn)而嚴(yán)重降低隨機(jī)森林預(yù)測準(zhǔn)確性。因此,為提高隨機(jī)森林模型預(yù)測精度,選取陰陽對優(yōu)化算法對隨機(jī)森林進(jìn)行參數(shù)調(diào)優(yōu)。
陰陽對優(yōu)化算法(Yin-Yang-pair optimization, YYPO)是Punnathanam等[13]于2016年提出的一種新型的元啟發(fā)式算法。它能迅速確定最優(yōu)解,是一種低復(fù)雜度的隨機(jī)算法,基于陰陽平衡原理通過利用和探索兩個(gè)點(diǎn)進(jìn)行工作,并根據(jù)優(yōu)化問題中決策變量的數(shù)量產(chǎn)生相應(yīng)維度的點(diǎn)。
YYPO算法根據(jù)待優(yōu)化問題的維度D隨機(jī)生成兩個(gè)點(diǎn)P1和P2。P1專注于利用變量空間,P2專注于探索變量空間,點(diǎn)P1和P2作為中心分別負(fù)責(zé)變量空間中以δ1和δ2為半徑的超球體。該算法包括兩個(gè)主要階段,分裂階段和存檔階段。分裂階段用于在迭代過程中搜索兩個(gè)點(diǎn)半徑范圍內(nèi)的超球體;存檔階段用于存儲分裂階段搜索后的P1和P2點(diǎn)和通過比較存檔中的點(diǎn)的適應(yīng)度更新P1、P2,并根據(jù)用戶定義的擴(kuò)展/收縮因子α更新δ1和δ2。
1.2.1 分裂階段
分裂階段的目的是在以點(diǎn)P為球心的半徑為δ的超球體中于盡可能變化的方向上以隨機(jī)的方式生成新的點(diǎn),利用適應(yīng)性函數(shù)評估產(chǎn)生的新點(diǎn)適應(yīng)度,將最適點(diǎn)替換為當(dāng)前點(diǎn)并記入存檔。分裂階段主要有兩種分裂方式:單向分裂和多向分裂。每次分裂通過范圍在0~1的隨機(jī)生成數(shù)R來決定分裂方式。
(1)單向分裂:設(shè)置矩陣S,它表示點(diǎn)P的2D維度的相同副本,大小為2D×D。矩陣S中的每一個(gè)點(diǎn)按式(1)所示設(shè)置。
(1)
式(1)中:上標(biāo)為行號;下標(biāo)為列號;r為0~1的隨機(jī)數(shù)矩陣;δ為點(diǎn)的半徑。
(2)多向分裂:同樣存在矩陣S,它表示點(diǎn)P的二維相同副本,大小為2D×D。矩陣S中的每一個(gè)點(diǎn)按式(2)所示設(shè)置。
(2)
式(2)中:B為由一個(gè)長度為D的二進(jìn)制字符串組成的矩陣,其中每一個(gè)字符串通過隨機(jī)選擇0~(2D-1)之間的2D個(gè)唯一整數(shù)轉(zhuǎn)換而成。
1.2.2 存檔階段
存檔階段在計(jì)數(shù)器i達(dá)到存檔更新次數(shù)I后啟動(dòng)。此時(shí)存檔中包含2I個(gè)點(diǎn),分別對應(yīng)分裂階段每次更新之前添加的兩個(gè)點(diǎn)P1、P2。比較存檔中點(diǎn)與當(dāng)前P1、P2的適應(yīng)度,將最優(yōu)點(diǎn)替換為P1、P2。替換后使用式(3)更新搜索半徑δ1、δ2。
(3)
式(3)中:α為擴(kuò)展/收縮因子。
1.2.3 YYPORF模型
采用陰陽對優(yōu)化算法對隨機(jī)森林ntree和mtry進(jìn)行尋優(yōu),主要基于P點(diǎn)適應(yīng)度傾向于極小值的趨勢,即模型預(yù)測誤差最小。YYPORF步驟如下。
步驟1設(shè)置存檔更新范圍Imin和Imax,擴(kuò)展/收縮因子α,迭代最大次數(shù)T,待優(yōu)化參數(shù)決策樹數(shù)量ntree和分裂屬性個(gè)數(shù)mtry取值范圍lb和ub。
步驟2確定模型適應(yīng)性函數(shù)。定義隨機(jī)森林模型的分類誤差Erro如式(4)所示:
Erro=1-acc
(4)
式(4)中:acc為模型分類準(zhǔn)確率。適應(yīng)度函數(shù)f描述如式(5)所示:
生態(tài)監(jiān)測工作在青海省是一項(xiàng)開創(chuàng)性的工作,專業(yè)性很強(qiáng),涉及多個(gè)部門和多個(gè)專業(yè),要結(jié)合我們所開展的工作和取得的成果,通過發(fā)布信息、媒體報(bào)道,充分提升各級政府和全社會(huì)對生態(tài)監(jiān)測工作重要性的認(rèn)識。
minf(ntree,mtry)=fRF=Erro=1-acc
(5)
步驟4迭代開始,在存檔更新范圍內(nèi)隨機(jī)產(chǎn)生存檔更新次數(shù)I,初始化計(jì)數(shù)器i=0,利用模型適應(yīng)度函數(shù)評估P1、P2的適應(yīng)度,若P2的適應(yīng)度優(yōu)于P1,互換兩個(gè)點(diǎn)。將P1、P2記入存檔。啟動(dòng)分裂階段。
步驟5利用式(1)、式(2)分別對P1、P2點(diǎn)進(jìn)行分裂操作,通過適應(yīng)度函數(shù)評估分裂階段產(chǎn)生的新點(diǎn)的適應(yīng)度,將最適點(diǎn)替換為正在經(jīng)歷分裂的P點(diǎn),計(jì)數(shù)器i加1。
步驟6若i
步驟7比較存檔中P1、P2與當(dāng)前P1、P2的適應(yīng)度,若存檔中最優(yōu)點(diǎn)優(yōu)于當(dāng)前P1、P2點(diǎn),則替換當(dāng)前P1、P2點(diǎn)。
步驟8若未達(dá)到最大迭代次數(shù)T,利用式(3)更新P1、P2點(diǎn)搜索半徑δ1、δ2,計(jì)數(shù)器i歸零,于Imin和Imax之間隨機(jī)產(chǎn)生新的存檔更新次數(shù)I,重復(fù)步驟4~步驟8,進(jìn)入下一輪迭代。
步驟9滿足最大迭代次數(shù),獲得ntree和mtry最優(yōu)解。
YYPORF算法流程圖如圖1所示。
圖1 YYPORF算法流程圖Fig.1 Flow chart of YYPORF
利用Spark大數(shù)據(jù)平臺進(jìn)行城市道路擁堵預(yù)測模型的并行化構(gòu)建。Spark是一種與Hadoop相似的開源集群計(jì)算環(huán)境,具有類似MapReduce的編程模型。Spark提供大量的庫,以Spark Core作為核心,提供Spark SQL、GraphX 、MLlib、Streaming等多種功能接口[14-18]。與MapReduce相比,Spark具有數(shù)倍于它的批處理速度和數(shù)十倍的數(shù)據(jù)分析速度[19],更適用與處理城市道路交通數(shù)據(jù)集。
在使用Spark進(jìn)行城市道路擁堵預(yù)測時(shí),首先將城市道路交通數(shù)據(jù)轉(zhuǎn)化為具有數(shù)據(jù)共享抽象的彈性分布式數(shù)據(jù)集RDD(resilient distributed dataset)[20]。每個(gè)RDD可以分成多個(gè)分區(qū),并且在集群的不同節(jié)點(diǎn)進(jìn)行保存,從而達(dá)到的集群各個(gè)節(jié)點(diǎn)上并行計(jì)算的目的[21-22]。
在 Spark 上平臺上對隨機(jī)森林算法的并行化設(shè)計(jì)步驟如下。
步驟1從HDFS(hadoop distributed file system)讀取城市道路交通數(shù)據(jù)集,合理劃分為訓(xùn)練集和測試集。本文研究的集群由4個(gè)節(jié)點(diǎn)組成,將訓(xùn)練集復(fù)制4份分發(fā)給每個(gè)節(jié)點(diǎn)。
步驟2假設(shè)需要?jiǎng)?chuàng)建的決策樹數(shù)目為n,共有4個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)負(fù)責(zé)創(chuàng)建n/4棵決策樹,各節(jié)點(diǎn)利用map()方法構(gòu)建訓(xùn)練子集,通過boosttrap sample()抽樣并行創(chuàng)建決策樹,各得到一個(gè)包含n/4個(gè)決策樹的集合。創(chuàng)建決策樹后,利用reduce()方法將所有決策樹整合為長度為n的決策樹集合,即訓(xùn)練得到的隨機(jī)森林模型。
步驟3使用訓(xùn)練得到的隨機(jī)森林模型對測試集進(jìn)行預(yù)測,并將結(jié)果上傳至HDFS。
隨機(jī)森林算法并行化設(shè)計(jì)如圖2所示。
圖2 隨機(jī)森林并行化設(shè)計(jì)Fig.2 Parallel design of random forest
采用合肥示范區(qū)黃科路口相關(guān)數(shù)據(jù),包含微波數(shù)據(jù)6萬條和車輛GPS(global positioning system)數(shù)據(jù)36萬條共42萬條數(shù)據(jù)作為數(shù)據(jù)集。整合兩項(xiàng)數(shù)據(jù)集,根據(jù)交通數(shù)據(jù)的實(shí)際情況,對城市道路交通數(shù)據(jù)進(jìn)行預(yù)處理。以1 min為一段,將每分鐘內(nèi)數(shù)據(jù)合并,并計(jì)算每一個(gè)時(shí)間段內(nèi)經(jīng)過道路的車流量、平均速度、占有率及密度。整理數(shù)據(jù)后,通過閾值法和交通流機(jī)理法對原始城市道路交通數(shù)據(jù)進(jìn)行異常值的判斷。
2.1.1 閾值法
通過考慮城市道路交通數(shù)據(jù)中單個(gè)參數(shù)的特征確定交通數(shù)據(jù)項(xiàng)的閾值。本文研究主要衡量的交通項(xiàng)為車流量、平均速度和車道占有率。
車流量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 交通流機(jī)理法
其基本思想是城市道路交通數(shù)據(jù)中的各項(xiàng)交通參數(shù)之間不能存在互相矛盾的關(guān)系。根據(jù)交通流機(jī)理法的交通數(shù)據(jù)項(xiàng)異常判別規(guī)則如表1所示。
表1 交通數(shù)據(jù)異常判別規(guī)則Table 1 Abnormal discrimination rules of traffic data
篩選出問題數(shù)據(jù)后,采用移動(dòng)平均法和歷史趨勢法進(jìn)行數(shù)據(jù)處理工作。單點(diǎn)異常使用移動(dòng)平均法,利用異常數(shù)據(jù)的附近數(shù)據(jù)值修復(fù)異常數(shù)據(jù),公式如式(7)所示。異常數(shù)據(jù)少于當(dāng)日數(shù)據(jù)三分之一時(shí),利用歷史趨勢法,使用上周正常數(shù)據(jù)替換異常日數(shù)據(jù),公式如式(8)所示。當(dāng)問題數(shù)據(jù)大于當(dāng)日數(shù)據(jù)的三分之一時(shí),為避免強(qiáng)行修復(fù)反而人為增加噪點(diǎn)的情況,舍棄當(dāng)日數(shù)據(jù)。
(7)
(8)
2.2.1 實(shí)驗(yàn)環(huán)境
采用由4個(gè)工作節(jié)點(diǎn)建立的計(jì)算集群,其中包含Spark的1個(gè)Master節(jié)點(diǎn)和3個(gè)Slave節(jié)點(diǎn)。Spark集群節(jié)點(diǎn)配置如表2所示。
表2 節(jié)點(diǎn)配置參數(shù)Table 2 Node configuration parameters
2.2.2 準(zhǔn)確率實(shí)驗(yàn)
本實(shí)驗(yàn)選取準(zhǔn)確率(accuracy)、精確率(precision)、召回率(recall)和F1度量(F1-measure)作為評價(jià)指標(biāo),分別使用K近鄰(KNN)、長短期記憶神經(jīng)網(wǎng)絡(luò)(LSTM)、原始隨機(jī)森林和本文提出的模型對處理后的數(shù)據(jù)進(jìn)行道路擁堵情況預(yù)測,分別運(yùn)算10次計(jì)算平均值。準(zhǔn)確率實(shí)驗(yàn)結(jié)果如表3所示。
表3 準(zhǔn)確率實(shí)驗(yàn)結(jié)果Table 3 Results of accuracy experiment
由表3可知,KNN在城市道路擁堵情況方面的預(yù)測效果最差,其準(zhǔn)確率、精確率、召回率和F1均為最低;原始RF和LSTM的預(yù)測效果次之,較KNN有所提高;YYPORF模型在4個(gè)評價(jià)指標(biāo)上對城市道路擁堵的預(yù)測均較好,準(zhǔn)確率為95.58%,精確率95.78%,召回率95.6%,F(xiàn)1為0.955 9。由此看出,YYPORF模型可以有效預(yù)測道路擁堵狀況,符合實(shí)際道路交通擁堵情況,能夠?qū)煌ü芾聿块T提供有效決策支持。
2.2.3 加速比實(shí)驗(yàn)
加速比表示集群并行化通過增加節(jié)點(diǎn)數(shù)量,對提升運(yùn)行速度減少運(yùn)行時(shí)間帶來的性能提升[23],其公式如式(9)所示:
(9)
式(9)中:TS為單個(gè)節(jié)點(diǎn)情況下進(jìn)行預(yù)測所消耗的時(shí)間;TP為在P個(gè)性能相同的節(jié)點(diǎn)并行計(jì)算的情況下進(jìn)行預(yù)測所消耗的時(shí)間。
本實(shí)驗(yàn)采用4個(gè)節(jié)點(diǎn)組成的集群,對原有數(shù)據(jù)集進(jìn)行擴(kuò)增,驗(yàn)證模型在不同節(jié)點(diǎn)不同數(shù)據(jù)量情況下的加速比。實(shí)驗(yàn)結(jié)果如圖3所示。
圖3 加速比實(shí)驗(yàn)結(jié)果Fig.3 Results of speedup radio experiment
由圖3可以看出,在數(shù)據(jù)集大小為60 M時(shí),隨著節(jié)點(diǎn)個(gè)數(shù)的增加,加速比有少量提升;在數(shù)據(jù)集大小為120 M時(shí),加速比的提升趨勢逐漸明顯;在數(shù)據(jù)集大小為240 M時(shí),加速比的提升趨勢非常明顯。由此可以看出,當(dāng)數(shù)據(jù)量不太大時(shí),節(jié)點(diǎn)數(shù)目增加可以使計(jì)算速度逐步提升、運(yùn)行時(shí)間逐漸減少,但提升的趨勢一開始并不明顯。這是因?yàn)?,在?jì)算量小的情況下,集群系統(tǒng)的啟動(dòng)、任務(wù)調(diào)度和數(shù)據(jù)通信會(huì)增加時(shí)間消耗,降低計(jì)算速度。當(dāng)數(shù)據(jù)量增大、集群的節(jié)點(diǎn)數(shù)增加后,集群的加速比呈現(xiàn)線性增長狀態(tài),逐漸趨近理想值。因此,本文研究提出的使用Spark大數(shù)據(jù)平臺的隨機(jī)森林并行化方案能夠有效提高隨機(jī)森林的計(jì)算速度,減少運(yùn)行時(shí)間。
2.2.4 可擴(kuò)展性實(shí)驗(yàn)
可擴(kuò)展性用于評價(jià)在集群的節(jié)點(diǎn)個(gè)數(shù)增加時(shí)算法性能按照節(jié)點(diǎn)個(gè)數(shù)比例提高的能力。由于節(jié)點(diǎn)個(gè)數(shù)的增加會(huì)帶來額外的通信開銷的增長,因此在增加節(jié)點(diǎn)個(gè)數(shù)的同時(shí)會(huì)致使每個(gè)節(jié)點(diǎn)的利用率降低[24]。因此使用可擴(kuò)展性衡量算法并行化對于有效可擴(kuò)展節(jié)點(diǎn)個(gè)數(shù)的利用能力。其公式如式(10)所示:
(10)
式(10)中:P為節(jié)點(diǎn)個(gè)數(shù);SpP為P個(gè)節(jié)點(diǎn)上的加速比。
可擴(kuò)展性實(shí)驗(yàn)結(jié)果如圖4所示。圖4可以看出,隨著節(jié)點(diǎn)數(shù)目的增加,算法的運(yùn)行時(shí)間逐漸減少;隨著數(shù)據(jù)量的增加,算法的運(yùn)行時(shí)間也逐漸減少;且隨著數(shù)據(jù)集大小和節(jié)點(diǎn)個(gè)數(shù)的增加,模型的運(yùn)行時(shí)間增長的倍數(shù)始終低于數(shù)據(jù)集大小和節(jié)點(diǎn)個(gè)數(shù)的增長倍數(shù)。因此,基于Spark的隨機(jī)森林模型具有良好的可擴(kuò)展性。
圖4 可擴(kuò)展性實(shí)驗(yàn)結(jié)果Fig.4 Results of scalability experiment
提出一種基于Spark大數(shù)據(jù)平臺的陰陽對優(yōu)化隨機(jī)森林模型對城市道路擁堵情況進(jìn)行預(yù)測,利用陰陽對優(yōu)化對影響隨機(jī)森林精度的關(guān)鍵參數(shù)進(jìn)行參數(shù)優(yōu)化。通過基于真實(shí)數(shù)據(jù)的實(shí)驗(yàn),得到以下結(jié)論。
(1)提出的模型較其他預(yù)測算法具有較高的精度,預(yù)測準(zhǔn)確率達(dá)到95.58%,提高了模型準(zhǔn)確率。
(2)提出的并行化設(shè)計(jì)方案能夠提高模型計(jì)算速度,降低運(yùn)行時(shí)間,具有良好的可擴(kuò)展性,能夠?yàn)榻煌ü芾聿块T的決策提供有力支持。