一種基于MapReduce的短時(shí)交通流預(yù)測(cè)方法

梁 軻,譚建軍,李英遠(yuǎn)

(1.中國(guó)科學(xué)院廣州地球化學(xué)研究所,廣州510640;2.中國(guó)科學(xué)院大學(xué),北京100049; 3.廣州中科盛博信息技術(shù)有限公司,廣州510630)

一種基于MapReduce的短時(shí)交通流預(yù)測(cè)方法

梁 軻1,2,譚建軍1,李英遠(yuǎn)3

(1.中國(guó)科學(xué)院廣州地球化學(xué)研究所,廣州510640;2.中國(guó)科學(xué)院大學(xué),北京100049; 3.廣州中科盛博信息技術(shù)有限公司,廣州510630)

非參數(shù)回歸方法是短時(shí)交通流預(yù)測(cè)常用的方法,但現(xiàn)有非參數(shù)回歸方法存在預(yù)測(cè)速度與精度之間的矛盾。為此,提出一種適用于海量歷史數(shù)據(jù)、基于MapReduce與遺傳算法的非參數(shù)回歸短時(shí)交通流預(yù)測(cè)方法。通過(guò)引入MapReduce并行計(jì)算框架,加快K最近鄰算法的搜索速度。在數(shù)據(jù)預(yù)處理階段利用遺傳算法優(yōu)化關(guān)鍵參數(shù)的設(shè)置,并采用MapReduce加速參數(shù)優(yōu)化過(guò)程,以解決遺傳算法迭代運(yùn)算時(shí)間長(zhǎng)的問(wèn)題。實(shí)驗(yàn)結(jié)果表明,該方法在保證交通流預(yù)測(cè)精度的前提下,明顯提高了預(yù)測(cè)速度,并且具有較好的可伸縮性。

交通流預(yù)測(cè);非參數(shù)回歸;K最近鄰搜索;遺傳算法;MapReduce編程模型;并行計(jì)算

1 概述

近年來(lái),智能交通系統(tǒng)(Intelligent Transport System,ITS)蓬勃發(fā)展,交通控制和實(shí)時(shí)交通流誘導(dǎo)成為智能交通系統(tǒng)研究的熱門問(wèn)題,而實(shí)現(xiàn)交通控制與誘導(dǎo)的關(guān)鍵問(wèn)題是實(shí)時(shí)準(zhǔn)確的短時(shí)交通流量預(yù)測(cè)[1]。由于交通流的非線性和不確定性,因此基于數(shù)學(xué)模型的方法難以處理該問(wèn)題[2]。而非參數(shù)回歸方法由于精度高、魯棒性好的優(yōu)點(diǎn)已成為交通流短時(shí)預(yù)測(cè)中最重要的方法之一[3-4]。但非參數(shù)回歸方法的一些問(wèn)題限制了它在短時(shí)交通流預(yù)測(cè)的實(shí)際應(yīng)用。

非參數(shù)回歸預(yù)測(cè)是一種類似于基于案例的推理方法,它不對(duì)數(shù)據(jù)做任何嚴(yán)格的假設(shè),而是在歷史數(shù)據(jù)中搜索與當(dāng)前狀態(tài)最相似的集合,并用它們來(lái)估算系統(tǒng)未來(lái)的狀態(tài)[5]。非參數(shù)回歸預(yù)測(cè)常用的算法是K最近鄰(K Nearest Neighbors,KNN)算法。如果歷史數(shù)據(jù)過(guò)于龐大,則K最近鄰搜索的開(kāi)銷會(huì)很大[6]?，F(xiàn)有研究大多通過(guò)改變歷史數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)來(lái)加快搜索速度,如對(duì)歷史數(shù)據(jù)進(jìn)行聚類[7],或使用如動(dòng)態(tài)散列[8]、KD樹(shù)[9]等數(shù)據(jù)結(jié)構(gòu)作為數(shù)據(jù)索引。這些方法都有效地提升了K最近鄰搜索的速度,但需要對(duì)數(shù)據(jù)進(jìn)行一定處理,這對(duì)于不斷擴(kuò)充的歷史數(shù)據(jù)庫(kù)而言開(kāi)銷較大。

非參數(shù)回歸方法的預(yù)測(cè)精度直接受限于關(guān)鍵參數(shù)的選擇。KNN算法中各狀態(tài)分量的權(quán)值和K最近鄰數(shù)的選取一般采用設(shè)定一個(gè)取值范圍,通過(guò)分別進(jìn)行實(shí)際預(yù)測(cè)以取得最優(yōu)值的方法[10-11]。但是由于狀態(tài)向量維數(shù)多,權(quán)值和K值的取值范圍比較大,該方法通常效率較低。針對(duì)該問(wèn)題,文獻(xiàn)[5,9]指出可以使用遺傳算法來(lái)優(yōu)化參數(shù)設(shè)置,但遺傳算法是一種需要多次迭代的啟發(fā)式算法,如果模式庫(kù)較大,則算法需要較長(zhǎng)的時(shí)間[12]。

本文在現(xiàn)有研究成果的基礎(chǔ)上,提出一種海量歷史數(shù)據(jù)條件下的非參數(shù)回歸短時(shí)交通流預(yù)測(cè)方法。針對(duì)海量歷史數(shù)據(jù)條件下的K最近鄰搜索問(wèn)題,使用MapReduce并行計(jì)算框架進(jìn)行K最近鄰搜索。針對(duì)預(yù)測(cè)的精確度問(wèn)題,使用基于MapReduce的遺傳算法對(duì)關(guān)鍵參數(shù)的選取進(jìn)行優(yōu)化。

2 MapReduce編程模型

MapReduce是一種分布式可伸縮的編程模型,它運(yùn)行在分布式文件系統(tǒng)HDFS上,用于大規(guī)模數(shù)據(jù)集的并行運(yùn)算[13]。MapReduce將分布式計(jì)算抽象為Map和Reduce 2個(gè)階段,每個(gè)階段中不同的Map和Reduce過(guò)程都是高度并行的。

MapReduce過(guò)程首先將源數(shù)據(jù)劃分為若干個(gè)數(shù)據(jù)塊,每個(gè)數(shù)據(jù)塊的數(shù)據(jù)被組織成＜key,value＞形式的鍵值對(duì),然后由Map過(guò)程將輸入數(shù)據(jù)的每條記錄分別進(jìn)行處理,輸出一系列鍵值對(duì),這些鍵值對(duì)按照鍵進(jìn)行排序、合并以及分區(qū)后,鍵相同的鍵值對(duì)進(jìn)入同一個(gè)Reduce過(guò)程進(jìn)行處理,并輸出最終結(jié)果。MapReduce編程模型如圖1所示。

圖1 MapReduce編程模型

MapReduce對(duì)并行運(yùn)算過(guò)程進(jìn)行了深入的封裝,隱藏了容災(zāi)、負(fù)載均衡等細(xì)節(jié),開(kāi)發(fā)者只需關(guān)心具體的邏輯。此外,MapReduce具有良好的可伸縮性,能夠非常方便地通過(guò)增加計(jì)算節(jié)點(diǎn)的方式提升運(yùn)算能力,集群中每增加一個(gè)計(jì)算節(jié)點(diǎn),運(yùn)算能力得到線性增長(zhǎng)。

3 基于MapReduce的短時(shí)交通流預(yù)測(cè)

3.1 歷史樣本數(shù)據(jù)

KNN預(yù)測(cè)算法實(shí)際上是一個(gè)模式匹配的過(guò)程,因此需要從海量的歷史數(shù)據(jù)中提取和建立完備的歷史樣本庫(kù)。本文首先以指定的時(shí)間間隔篩選出主干道上檢測(cè)器采集到的交通流量數(shù)據(jù);然后對(duì)提取出的數(shù)據(jù)進(jìn)行平穩(wěn)化處理,減少隨機(jī)因素的影響和干擾,消除噪聲和誤差[11];采用局部最小二乘插值法,并參考文獻(xiàn)[14]的實(shí)驗(yàn)成果,對(duì)采集過(guò)程中缺失的部分交通流數(shù)據(jù)進(jìn)行補(bǔ)齊和修復(fù)。

3.2 參數(shù)選擇與距離定義

參數(shù)選擇與距離定義具體如下:

(1)狀態(tài)分量篩選。影響路段上的交通流量的狀態(tài)分量很多,如路段上前幾個(gè)時(shí)段的交通流量、上下游路段前幾個(gè)時(shí)段的交通流量等。但并不是所有的狀態(tài)分量都對(duì)當(dāng)前交通流量有顯著影響,可以使用已有文獻(xiàn)中提出的相關(guān)性分析[7]、主成分分析法[15]等方法篩選出多個(gè)比較重要的狀態(tài)分量。

(2)狀態(tài)分量權(quán)重及K值選擇。各狀態(tài)分量對(duì)于交通流狀態(tài)的影響不同,因此需要賦予不同的權(quán)重[16]。KNN算法必須確定一個(gè)K值,它對(duì)于近鄰搜索的速度與預(yù)測(cè)的精度都有很大影響。本文采用遺傳算法對(duì)這些值的選取進(jìn)行優(yōu)化。

(3)距離定義。距離表征了當(dāng)前數(shù)據(jù)與樣本數(shù)據(jù)的匹配程度,本文采用加權(quán)的歐式距離:

其中,di為當(dāng)前數(shù)據(jù)與樣本數(shù)據(jù)i的距離;λj為第j個(gè)狀態(tài)分量的權(quán)重;Xij為樣本數(shù)據(jù)i的第j個(gè)狀態(tài)分量;Yj為當(dāng)前數(shù)據(jù)的第j個(gè)狀態(tài)分量。

3.3 Top K算法

KNN算法中要進(jìn)行從歷史數(shù)據(jù)集中找出與當(dāng)前點(diǎn)最近的K個(gè)點(diǎn),這個(gè)問(wèn)題可以抽象為從距離值集合A={di|1≤i≤N}中找出K個(gè)最小值。如果遍歷搜索時(shí)間復(fù)雜度為O(N2),耗時(shí)很大。本文利用一個(gè)容量為K的大根堆來(lái)解決此問(wèn)題。大根堆是一個(gè)二叉樹(shù)結(jié)構(gòu),其中,每個(gè)非葉子節(jié)點(diǎn)中的值都大于等于它的兒子節(jié)點(diǎn)中的值。向大根堆中插入一個(gè)元素后需要對(duì)堆結(jié)構(gòu)進(jìn)行調(diào)整以保持其性質(zhì),調(diào)整的時(shí)間復(fù)雜度為O(logK)。算法描述如下:

大根堆中保存了最小的K個(gè)di,而堆頂元素則是這K個(gè)值中的最大值,因此后來(lái)的每個(gè)di只需與堆頂元素比較,若比它更大,則不可能是最小的K個(gè)di之一,否則用其替換堆頂元素,得到新的最小的K個(gè)di。整個(gè)搜索過(guò)程的時(shí)間復(fù)雜度僅為O(NlogK)。

3.4 K最近鄰搜索與交通流預(yù)測(cè)

在海量歷史數(shù)據(jù)條件下利用MapReduce加速K最近鄰搜索主要依靠的是MapReduce框架的并行計(jì)算機(jī)制,使得KNN算法在K最近鄰模式匹配時(shí),可以多個(gè)部分并行進(jìn)行,從而縮短了K最近鄰的查找時(shí)間,其核心部分在于Map和Reduce 2個(gè)階段的設(shè)計(jì)?；贛apReduce的KNN預(yù)測(cè)算法流程見(jiàn)圖2。

圖2 基于MapReduce的KNN預(yù)測(cè)算法流程

基于MapReduce的KNN預(yù)測(cè)算法流程具體如下:

(1)Map階段

Map階段主要計(jì)算當(dāng)前點(diǎn)與歷史數(shù)據(jù)庫(kù)中其他點(diǎn)的距離,為下一步的規(guī)約提供基礎(chǔ)。由于歷史數(shù)據(jù)是海量的,這一階段比較耗時(shí),可以使用多個(gè)Map任務(wù)并行處理,每一個(gè)Map任務(wù)計(jì)算出當(dāng)前點(diǎn)與樣本數(shù)據(jù)點(diǎn)之間的距離,并得到K個(gè)最鄰近點(diǎn)。

Step1從HDFS上讀取歷史樣本數(shù)據(jù),Map Reduce框架會(huì)自動(dòng)將數(shù)據(jù)劃分為若干個(gè)塊,每一塊中的數(shù)據(jù)都組織成鍵值對(duì)＜key,value＞的形式,交給一個(gè)Mapper過(guò)程進(jìn)行處理。其中,key為數(shù)據(jù)塊的編號(hào);value是該數(shù)據(jù)塊中歷史數(shù)據(jù)的集合,每個(gè)元素都是按照3.2節(jié)所述方法選取出的若干狀態(tài)分量構(gòu)成的狀態(tài)向量。

Step2Mapper調(diào)用Map函數(shù)計(jì)算value中各個(gè)歷史數(shù)據(jù)到當(dāng)前點(diǎn)的距離,并按照3.3節(jié)所述Top K算法,得到每個(gè)數(shù)據(jù)塊中的K個(gè)最臨近點(diǎn)。

Step3輸出鍵值對(duì)＜key,value＞,其中,value是該Mapper過(guò)程得到的K個(gè)最鄰近點(diǎn)信息集合,每個(gè)鄰近點(diǎn)信息由它與當(dāng)前點(diǎn)的距離di和該近鄰點(diǎn)對(duì)應(yīng)的下一時(shí)刻交通流量vi(t+1)構(gòu)成。

設(shè)樣本數(shù)據(jù)集的規(guī)模為N,同時(shí)啟動(dòng)的Map任務(wù)數(shù)為M,由于M個(gè)Map任務(wù)并行運(yùn)行,因此整個(gè)Map階段的時(shí)間復(fù)雜度為O(N/M·logK)。

(2)Reduce階段

Reduce階段從Map階段的結(jié)果中規(guī)約出K個(gè)最臨近點(diǎn),并進(jìn)行交通流的預(yù)測(cè)。

Step1Reduce節(jié)點(diǎn)獲得Map階段產(chǎn)生的鍵值對(duì)＜key,value＞,將擁有相同key值的value進(jìn)行規(guī)約,構(gòu)成元組(key:value1,value2,…,valueM),交給Reducer過(guò)程處理。

Step2Reducer調(diào)用Reduce函數(shù),遍歷元組,根據(jù)3.3節(jié)所述Top K算法得到K個(gè)最小距離di以及對(duì)應(yīng)的下一時(shí)刻交通流量vi(t+1)。

Step3進(jìn)行交通流預(yù)測(cè),通過(guò)對(duì)K個(gè)最近鄰對(duì)應(yīng)的下一時(shí)刻的交通流量vi(t+1)進(jìn)行加權(quán)平均,得到預(yù)測(cè)結(jié)果v(t+1)并輸出到HDFS中。預(yù)測(cè)算法的形式如下:

本文對(duì)交通流量的預(yù)測(cè)采用反距離加權(quán)法,使得與當(dāng)前點(diǎn)更近的近鄰具有更大的權(quán)重,更符合人們的認(rèn)知[17]。

Reduce階段需要集中處理 Map階段產(chǎn)生的M組輸出,每組輸出中包含K個(gè)數(shù)據(jù),因此,這一階段的時(shí)間復(fù)雜度為O(KM·logK)。

4 基于MapReduce與遺傳算法的參數(shù)優(yōu)化

使用遺傳算法優(yōu)化KNN算法中參數(shù)的主要開(kāi)銷在于適應(yīng)度的計(jì)算以及進(jìn)化過(guò)程的迭代。本文利用MapReduce的并行計(jì)算和批處理的特性,實(shí)現(xiàn)遺傳算法,加速其參數(shù)優(yōu)化過(guò)程。算法流程見(jiàn)圖3。

圖3 基于MapReduce的遺傳算法參數(shù)優(yōu)化流程

基于MapReduce的遺傳算法參數(shù)優(yōu)化流程具體如下:

(1)種群初始化。首先使用3.2節(jié)提到的主成分分析法選取狀態(tài)分量,隨機(jī)為其賦予權(quán)值參數(shù),并隨機(jī)選擇一個(gè)K值。種群中每個(gè)個(gè)體都是一組參數(shù)的集合,由這些隨機(jī)選擇的參數(shù)構(gòu)成。重復(fù)此過(guò)程產(chǎn)生一定規(guī)模的個(gè)體作為初始種群。設(shè)種群規(guī)模為T,則本階段時(shí)間復(fù)雜度為O(T)。

(2)適應(yīng)度計(jì)算。算法關(guān)鍵在于適應(yīng)度的計(jì)算,而衡量某個(gè)個(gè)體的適應(yīng)度高低顯然是看其對(duì)應(yīng)的K值和各狀態(tài)分量的參數(shù)對(duì)于實(shí)際交通狀況預(yù)測(cè)的符合程度,計(jì)算方法如下:

1)利用歷史數(shù)據(jù)集,提取一部分?jǐn)?shù)據(jù)作為歷史模式庫(kù),選取另一部分作為預(yù)測(cè)樣本庫(kù)。

2)對(duì)于每一個(gè)個(gè)體,利用其對(duì)應(yīng)的狀態(tài)分量權(quán)值和K值,根據(jù)歷史模式庫(kù)對(duì)預(yù)測(cè)樣本庫(kù)中的數(shù)據(jù)進(jìn)行離線預(yù)測(cè),將預(yù)測(cè)結(jié)果與實(shí)際數(shù)據(jù)對(duì)比。定義適應(yīng)度f(wàn)為:

其中,MAPE為平均相對(duì)誤差:

其中,Xi代表第i個(gè)周期的實(shí)際流量;Yi為第i個(gè)周期的預(yù)測(cè)流量。

適應(yīng)度計(jì)算的主要部分是交通流的預(yù)測(cè),比較耗時(shí),因此可以利用 MapReduce來(lái)加速。每一個(gè)個(gè)體的適應(yīng)度計(jì)算是一個(gè)如 3.4節(jié)所述的MapReduce過(guò)程,設(shè)歷史模式庫(kù)的規(guī)模為H,同時(shí)啟動(dòng)的Map任務(wù)數(shù)為F,則本階段的時(shí)間復(fù)雜度為O(T(H/F+KF)logK)。計(jì)算好的適應(yīng)度與參數(shù)一起構(gòu)成一個(gè)個(gè)體。

3)進(jìn)化過(guò)程。每一代的進(jìn)化過(guò)程可以用一個(gè)MapReduce過(guò)程來(lái)完成,其中,Map階段進(jìn)行適應(yīng)度評(píng)價(jià),生成鍵值對(duì)＜子種群編號(hào),個(gè)體＞;Reduce階段將相同的鍵對(duì)應(yīng)的值歸約起來(lái)完成一個(gè)子種群的選擇、交叉和變異,這樣就保持了子種群進(jìn)化的相對(duì)獨(dú)立性[18]。遷徙可以在Map階段利用MapReduce提供的Partition接口完成,通過(guò)隨機(jī)改變某個(gè)個(gè)體的鍵,將其從原來(lái)的子種群遷徙到另一個(gè)子種群。設(shè)個(gè)體中的狀態(tài)分量數(shù)為P,T'為選擇過(guò)程后的種群規(guī)模,同時(shí)啟動(dòng)的Map及Reduce任務(wù)數(shù)分別為N與M,則本階段時(shí)間復(fù)雜度為O(T/N+T'P/M)。

4)結(jié)束準(zhǔn)則?？梢栽谶m應(yīng)度函數(shù)收斂和達(dá)到一定迭代次數(shù)之中選擇一種作為結(jié)束條件。

上述遺傳算法是作為整個(gè)預(yù)測(cè)算法的離線預(yù)處理部分,單獨(dú)運(yùn)行,不影響實(shí)時(shí)的交通流預(yù)測(cè)。只有在遺傳算法計(jì)算出新的最優(yōu)參數(shù)時(shí),實(shí)時(shí)交通流預(yù)測(cè)算法使用的相應(yīng)參數(shù)才需要更新。另一方面, MapReduce的使用加速了遺傳算法的運(yùn)行,因此該算法能滿足實(shí)際需要。

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)環(huán)境配置

本文采用開(kāi)源的Hadoop分布式軟件框架搭建MapReduce仿真實(shí)驗(yàn)平臺(tái),平臺(tái)構(gòu)建在局域網(wǎng)中的集群上,由7臺(tái)機(jī)器組成,其中一臺(tái)為NameNode節(jié)點(diǎn),其余為DataNode節(jié)點(diǎn),相互之間通過(guò)100M以太網(wǎng)通信,所有主機(jī)采用相同的配置。硬件環(huán)境為雙核Intel奔騰E6300 2.8 GHz處理器、2 GB DDR3內(nèi)存、200 GB硬盤(pán);軟件環(huán)境為Ubuntu 12.04 LTS操作系統(tǒng)、Hadoop 0.20.2、JDK 1.6。

本文算法是基于MapReduce實(shí)現(xiàn)的,為了驗(yàn)證其效果,在仿真過(guò)程中于單機(jī)和Hadoop集群2種不同環(huán)境下進(jìn)行性能測(cè)試,其中單機(jī)環(huán)境下的軟硬件環(huán)境與Hadoop集群中的機(jī)器采用相同的配置。

5.2 MapReduce對(duì)K最近鄰搜索的加速效果分析

本文對(duì)傳統(tǒng)的單機(jī) KNN算法與基于 Map Reduce的KNN算法進(jìn)行K最近鄰搜索速度對(duì)比實(shí)驗(yàn),以檢驗(yàn)MapReduce對(duì)K最近鄰搜索的加速效果。實(shí)驗(yàn)數(shù)據(jù)為隨機(jī)生成的海量數(shù)據(jù)點(diǎn),其中每個(gè)數(shù)據(jù)點(diǎn)包括5個(gè)狀態(tài)分量,每個(gè)分量的值都為0～1之間的實(shí)數(shù)。數(shù)據(jù)規(guī)模從107～109不等,并對(duì)不同規(guī)模的數(shù)據(jù)進(jìn)行2個(gè)算法的搜索速度對(duì)比。在測(cè)試基于 MapReduce的近鄰搜索速度時(shí), Hadoop集群采用4臺(tái)、5臺(tái)、6臺(tái)DataNode機(jī)器分別進(jìn)行實(shí)驗(yàn),以驗(yàn)證算法的伸縮性能。實(shí)驗(yàn)結(jié)果見(jiàn)圖4。

圖4 基于MapReduce的KNN算法與傳統(tǒng)單機(jī)KNN算法的近鄰搜索耗時(shí)對(duì)比

可以看出,基于MapReduce的KNN算法能夠有效地提升K最近鄰搜索的速度,并且加速效果隨著數(shù)據(jù)規(guī)模的擴(kuò)大愈加明顯,而傳統(tǒng)的單機(jī)KNN算法在數(shù)據(jù)規(guī)模超過(guò)一定程度后,受限于單機(jī)內(nèi)存而無(wú)法處理。同時(shí),隨著DataNode機(jī)器數(shù)量的增加,基于MapReduce的KNN算法對(duì)同樣規(guī)模數(shù)據(jù)的搜索速度也在不斷提升,表現(xiàn)出了良好的伸縮性能。

5.3 遺傳算法優(yōu)化與加速效果分析

基于MapReduce的遺傳算法對(duì)參數(shù)的優(yōu)化效果以及對(duì)優(yōu)化過(guò)程的加速效果實(shí)驗(yàn)使用數(shù)據(jù)來(lái)自美國(guó)明尼蘇達(dá)大學(xué)德盧斯分校交通數(shù)據(jù)研究實(shí)驗(yàn)室(The Transportation Data Research Laboratory,http:// www.d.umn.edu/tdrl/traffic/),數(shù)據(jù)集采自雙城高速公路,選取的實(shí)驗(yàn)場(chǎng)景位于Interstate 94號(hào)公路,如圖5所示。路段1為主干公路的上游路段,包括2638號(hào)～2641號(hào)傳感器,路段2為入口匝道,包括2642號(hào)傳感器,路段3為主干公路的下游路段,包括3176號(hào)～3179號(hào)傳感器。

圖5 實(shí)驗(yàn)道路場(chǎng)景

本次實(shí)驗(yàn)選取2013年6月1日-2013年6月30日的數(shù)據(jù)作為數(shù)據(jù)集,將路段3上監(jiān)測(cè)點(diǎn)處的流量作為待預(yù)測(cè)目標(biāo)。首先使用3.1節(jié)中的方法對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,以5 min為預(yù)測(cè)周期提取數(shù)據(jù)并補(bǔ)齊缺失數(shù)據(jù),處理后的數(shù)據(jù)大小約為12 MB;然后使用主成分分析方法,得到預(yù)測(cè)路段3下一時(shí)刻流量v3(t+1)需要的狀態(tài)分量為路段1、路段2、路段3當(dāng)前時(shí)刻的流量,即v1(t),v2(t),v3(t),它們對(duì)應(yīng)的權(quán)重參數(shù)分別記為λ1,λ2,λ3;接下來(lái)使用第4節(jié)提出的算法和適應(yīng)度計(jì)算函數(shù)對(duì)K和λ1,λ2,λ3的值進(jìn)行優(yōu)化,得到的最優(yōu)結(jié)果為K=15,λ1=1.67,λ2=0.38,λ3=0.75。

為了驗(yàn)證優(yōu)化的效果,以K值為例進(jìn)行對(duì)比實(shí)驗(yàn)。將λ1,λ2,λ33個(gè)參數(shù)作為不變量,將K值作為可變量,分別取不同的值進(jìn)行交通流預(yù)測(cè),預(yù)測(cè)效果的評(píng)價(jià)以平均絕對(duì)百分誤差(MAPE)值作為指標(biāo)。圖6顯示了K取不同值時(shí)預(yù)測(cè)效果的變化。當(dāng)K取其他值時(shí),預(yù)測(cè)的效果變差,這說(shuō)明基于MapReduce的遺傳算法對(duì)參數(shù)的優(yōu)化是有效的。

圖6 采用不同K值時(shí)的預(yù)測(cè)效果

使用傳統(tǒng)的遺傳算法對(duì)上述場(chǎng)景中K和λ1, λ2,λ3的值進(jìn)行優(yōu)化,與基于MapReduce的遺傳算法對(duì)參數(shù)優(yōu)化的速度進(jìn)行對(duì)比。表1顯示了一次迭代進(jìn)化過(guò)程中2個(gè)算法的耗時(shí)比較。

表1 算法耗時(shí)對(duì)比 s

5.4 預(yù)測(cè)效果分析

本節(jié)對(duì)算法預(yù)測(cè)效果進(jìn)行驗(yàn)證和評(píng)估。實(shí)驗(yàn)采用的場(chǎng)景,K值和其他參數(shù)均使用5.3節(jié)得到的優(yōu)化結(jié)果,但歷史樣本數(shù)據(jù)提取自2011年7月1日-2013年6月30日3年的數(shù)據(jù),預(yù)處理后的數(shù)據(jù)大小約為438 MB。使用基于MapRedcue的KNN預(yù)測(cè)算法對(duì)路段3在2013年7月23日一整天共288個(gè)預(yù)測(cè)周期(周期為5 min)的交通流量進(jìn)行預(yù)測(cè),預(yù)測(cè)流量與實(shí)際流量對(duì)比見(jiàn)圖7。

圖7 路段3實(shí)際交通流量與預(yù)測(cè)交通流量的對(duì)比

采用傳統(tǒng)的KNN預(yù)測(cè)算法與基于MapReduce的KNN預(yù)測(cè)算法進(jìn)行綜合性能對(duì)比。引入平均絕對(duì)百分誤差(MAPE)和均方誤差(MSE)作為預(yù)測(cè)結(jié)果的評(píng)價(jià)指標(biāo)。實(shí)驗(yàn)結(jié)果見(jiàn)表2。

表2 2種預(yù)測(cè)算法的綜合性能對(duì)比

可以看出,2個(gè)算法均有較高的預(yù)測(cè)精度。但基于MapReduce的KNN預(yù)測(cè)算法的預(yù)測(cè)耗時(shí)僅為傳統(tǒng)KNN預(yù)測(cè)算法的1/4左右。這說(shuō)明本文提出的交通流預(yù)測(cè)算法在保證一定預(yù)測(cè)精度的基礎(chǔ)上,能夠顯著提高預(yù)測(cè)速度。

6 結(jié)束語(yǔ)

本文提出一種面向海量歷史數(shù)據(jù)的非參數(shù)回歸短時(shí)交通流預(yù)測(cè)方法,利用MapReduce將K最近鄰搜索過(guò)程并行化,并給出MapReduce編程模型下K最近鄰搜索與預(yù)測(cè)算法的流程。實(shí)驗(yàn)結(jié)果證明K最近鄰搜索速度有了明顯提高,預(yù)測(cè)算法可伸縮性良好,并且無(wú)需特別的數(shù)據(jù)結(jié)構(gòu),歷史數(shù)據(jù)庫(kù)也能夠方便地進(jìn)行擴(kuò)充。同時(shí),本文利用基于MapReduce的遺傳算法優(yōu)化KNN算法中的K最近鄰數(shù)和各個(gè)狀態(tài)分量的參數(shù)選取,并通過(guò)實(shí)驗(yàn)驗(yàn)證了其優(yōu)化和加速效果。另外,在MapReduce編程模型下,可以通過(guò)增加計(jì)算節(jié)點(diǎn)來(lái)應(yīng)對(duì)歷史數(shù)據(jù)的增長(zhǎng),而無(wú)需對(duì)算法進(jìn)行大幅修改。這對(duì)非參數(shù)回歸算法應(yīng)用于實(shí)時(shí)短時(shí)交通流預(yù)測(cè)具有一定的指導(dǎo)作用。今后將進(jìn)一步提高算法的預(yù)測(cè)精度和速度,并將其應(yīng)用于城市交通流誘導(dǎo)與控制系統(tǒng)中。

[1] Brian L S.Comparison of Parametric and Non-parametric Models for Traffic Flow Forecasting[J].Transportation Research Part C:Emerging Technologies,2002,10(4): 303-321.

[2] 賀國(guó)光,李 宇,馬壽峰.基于數(shù)學(xué)模型的短時(shí)交通流預(yù)測(cè)方法探討[J].系統(tǒng)工程理論與實(shí)踐,2000, 20(12):51-56.

[3] Davis G,Nihan N.Non-parametric Regression and Shortterm Freeway Traffic Forecasting[J].Journal of Transportation Engineering,1991,117(2):178-188.

[4] Smith B L,Williams B M,Keith O R.Comparison of Parametric and Non-parametric Models for Traffic Flow Forecasting[J].Transportation Research PartC: Emerging Technologies,2002,10(4):303-321.

[5] Oswald R K,Scherer W T,Smith B L.Traffic Flow Forecasting Using Approximate Nearest Neighbor Nonparametric Regression[Z].2000.

[6] Li Shuangshuang.Implementing Short-term Traffic Flow Forecasting Based on Multipoint WPRA with MapReduce[C]//Proceedings of 2012 IEEE/ASME International Conference on Mechatronics and Embedded Systems and Applications.Suzhou,China:[s.n.], 2012:287-291.

[7] 宮曉燕,湯淑明.基于非參數(shù)回歸的短時(shí)交通流預(yù)測(cè)與事件檢測(cè)綜合算法[J].中國(guó)公路學(xué)報(bào),2003,16(1):82-86.

[8] 張曉利,賀國(guó)光,陸化普.基于K-鄰域非參數(shù)回歸短時(shí)交通流預(yù)測(cè)方法[J].系統(tǒng)工程學(xué)報(bào),2009,24(2):178-183.

[9] 賈 寧,馬壽峰,鐘石泉.基于遺傳算法優(yōu)化和KD樹(shù)的交通流非參數(shù)回歸預(yù)測(cè)方法[J].控制與決策, 2012,27(7):991-996.

[10] Huang Zhenjin,Ouyang Hao,Tian Yiming.Short-term Traffic Flow Combined Forecasting Based on Nonparametric Regression [C]//Proceedings of 2011 InternationalConference on Information Technology, Computer Engineering and Management Sciences.[S.l.]: IEEE Press,2011:316-319.

[11] 翁劍成,榮 建,任福田.基于非參數(shù)回歸的快速路行程速度短期預(yù)測(cè)算法[J].公路交通科技,2007,3(1):93-97.

[12] Verma A,Llorà X,Goldberg D E,et al.Scaling Genetic Algorithms Using MapReduce[C]//Proceedings of the 9th InternationalConference on IntelligentSystems Design and Applications.Pisa,Italy:IEEE Computer Society,2009:13-18.

[13] Dean J,GhemawatS.MapReduce:Simplified Data Processing on Large Clusters[C]//Proceedings of the 6th Conference on Symposium on Operating Systems Design and Implementation.[S.l.]:USENIX Association,2004: 107-113.

[14] Chang Gang,Ge Tongming.Comparison of Missing Data Imputation Methods for Traffic Flow[C]//Proceedings of 2011 International Conference on Transportation, Mechanical,and Electrical Engineering.[S.l.]:IEEE Press,2011:639-642.

[15] 張曉利,賀國(guó)光.基于主成分分析和組合神經(jīng)網(wǎng)絡(luò)的短時(shí)交通流預(yù)測(cè)方法[J].系統(tǒng)工程理論與實(shí)踐, 2007,27(8):167-171.

[16] 于 濱,鄔珊華,王明華,等.K近鄰短時(shí)交通流預(yù)測(cè)模型[J].交通運(yùn)輸工程學(xué)報(bào),2012,12(2):105-111.

[17] 周小鵬,馮 奇,孫立軍.基于最近鄰法的短時(shí)交通流預(yù)測(cè)[J].同濟(jì)大學(xué)學(xué)報(bào):自然科學(xué)版,2006,34(11): 1494-1498.

[18] 李 東,潘志松.一種適用于大規(guī)模變量的并行遺傳算法研究[J].計(jì)算機(jī)科學(xué),2012,39(7):182-204.

編輯 陸燕菲

A Short-term Traffic Flow Forecasting Method Based on MapReduce

LIANG Ke1,2,TAN Jianjun1,LI Yingyuan3
(1.Guangzhou Institute of Geochemistry,Chinese Academy of Sciences,Guangzhou 510640,China; 2.University of Chinese Academy of Sciences,Beijing 100049,China; 3.CASample Information Technology Co.,Ltd.,Guangzhou 510630,China)

Non-parameter regression method is widely used in short-term traffic flow forecasting,but there is a contradiction on forecasting accuracy and computational efficiency in that method.This paper proposes an improved shortterm traffic flow forecasting method based on MapReduce and genetic algorithm in the context of massive historical data. To improve the search speed of K Nearest Neighbor(KNN),a parallel computing framework MapReduce is used to search the KNN.In data preprocessing stage,genetic algorithm is used to optimize the selection of key parameters,and it accelerates parameter optimization process based on MapReduce to solve the problem of long iterative operation time for genetic algorithm.Experimental results show that the method has high scalability,and it can increase the searching efficiency significantly while the forecasting accuracy is guaranteed.

traffic flow forecasting;non-parametric regression;K Nearest Neighbor(KNN)search;genetic algorithm; MapReduce programming model;parallel computing

1000-3428(2015)01-0174-06

A

TP311

10.3969/j.issn.1000-3428.2015.01.032

廣東省中國(guó)科學(xué)院全面戰(zhàn)略合作基金資助項(xiàng)目(2012B091100266);廣州市科技計(jì)劃基金資助項(xiàng)目(2010Y1-C041);廣州市科技計(jì)劃科技支撐基金資助項(xiàng)目(09A11040726)。

梁 軻(1989-),男,碩士研究生,主研方向:智能交通,3S技術(shù)及其應(yīng)用;譚建軍,研究員、博士;李英遠(yuǎn),碩士。

2014-02-17

2014-03-13 E-mail:liangke723@sina.com

中文引用格式:梁 軻,譚建軍,李英遠(yuǎn).一種基于MapReduce的短時(shí)交通流預(yù)測(cè)方法[J].計(jì)算機(jī)工程,2015, 41(1):174-179.

英文引用格式:Liang Ke,Tan Jianjun,Li Yingyuan.A Short-term Traffic Flow Forecasting Method Based on MapReduce[J]. Computer Engineering,2015,41(1):174-179.