一種基于MapReduce的短時交通流預測方法

梁 軻,譚建軍,李英遠

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

一種基于MapReduce的短時交通流預測方法

梁 軻1,2,譚建軍1,李英遠3

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

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

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

1 概述

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

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

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

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

2 MapReduce編程模型

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

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

圖1 MapReduce編程模型

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

3 基于MapReduce的短時交通流預測

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

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

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

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

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

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

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

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

3.3 Top K算法

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

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

3.4 K最近鄰搜索與交通流預測

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

圖2 基于MapReduce的KNN預測算法流程

基于MapReduce的KNN預測算法流程具體如下:

(1)Map階段

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

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

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

Step3輸出鍵值對＜key,value＞,其中,value是該Mapper過程得到的K個最鄰近點信息集合,每個鄰近點信息由它與當前點的距離di和該近鄰點對應的下一時刻交通流量vi(t+1)構成。

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

(2)Reduce階段

Reduce階段從Map階段的結果中規(guī)約出K個最臨近點,并進行交通流的預測。

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

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

Step3進行交通流預測,通過對K個最近鄰對應的下一時刻的交通流量vi(t+1)進行加權平均,得到預測結果v(t+1)并輸出到HDFS中。預測算法的形式如下:

本文對交通流量的預測采用反距離加權法,使得與當前點更近的近鄰具有更大的權重,更符合人們的認知[17]。

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

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

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

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

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

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

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

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

2)對于每一個個體,利用其對應的狀態(tài)分量權值和K值,根據(jù)歷史模式庫對預測樣本庫中的數(shù)據(jù)進行離線預測,將預測結果與實際數(shù)據(jù)對比。定義適應度f為:

其中,MAPE為平均相對誤差:

其中,Xi代表第i個周期的實際流量;Yi為第i個周期的預測流量。

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

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

4)結束準則。可以在適應度函數(shù)收斂和達到一定迭代次數(shù)之中選擇一種作為結束條件。

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

5 實驗結果與分析

5.1 實驗環(huán)境配置

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

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

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

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

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

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

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

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

圖5 實驗道路場景

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

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

圖6 采用不同K值時的預測效果

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

表1 算法耗時對比 s

5.4 預測效果分析

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

圖7 路段3實際交通流量與預測交通流量的對比

采用傳統(tǒng)的KNN預測算法與基于MapReduce的KNN預測算法進行綜合性能對比。引入平均絕對百分誤差(MAPE)和均方誤差(MSE)作為預測結果的評價指標。實驗結果見表2。

表2 2種預測算法的綜合性能對比

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

6 結束語

本文提出一種面向海量歷史數(shù)據(jù)的非參數(shù)回歸短時交通流預測方法,利用MapReduce將K最近鄰搜索過程并行化,并給出MapReduce編程模型下K最近鄰搜索與預測算法的流程。實驗結果證明K最近鄰搜索速度有了明顯提高,預測算法可伸縮性良好,并且無需特別的數(shù)據(jù)結構,歷史數(shù)據(jù)庫也能夠方便地進行擴充。同時,本文利用基于MapReduce的遺傳算法優(yōu)化KNN算法中的K最近鄰數(shù)和各個狀態(tài)分量的參數(shù)選取,并通過實驗驗證了其優(yōu)化和加速效果。另外,在MapReduce編程模型下,可以通過增加計算節(jié)點來應對歷史數(shù)據(jù)的增長,而無需對算法進行大幅修改。這對非參數(shù)回歸算法應用于實時短時交通流預測具有一定的指導作用。今后將進一步提高算法的預測精度和速度,并將其應用于城市交通流誘導與控制系統(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] 賀國光,李 宇,馬壽峰.基于數(shù)學模型的短時交通流預測方法探討[J].系統(tǒng)工程理論與實踐,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ù)回歸的短時交通流預測與事件檢測綜合算法[J].中國公路學報,2003,16(1):82-86.

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

[9] 賈 寧,馬壽峰,鐘石泉.基于遺傳算法優(yōu)化和KD樹的交通流非參數(shù)回歸預測方法[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ù)回歸的快速路行程速度短期預測算法[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] 張曉利,賀國光.基于主成分分析和組合神經網絡的短時交通流預測方法[J].系統(tǒng)工程理論與實踐, 2007,27(8):167-171.

[16] 于 濱,鄔珊華,王明華,等.K近鄰短時交通流預測模型[J].交通運輸工程學報,2012,12(2):105-111.

[17] 周小鵬,馮 奇,孫立軍.基于最近鄰法的短時交通流預測[J].同濟大學學報:自然科學版,2006,34(11): 1494-1498.

[18] 李 東,潘志松.一種適用于大規(guī)模變量的并行遺傳算法研究[J].計算機科學,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

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

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

2014-02-17

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

中文引用格式:梁 軻,譚建軍,李英遠.一種基于MapReduce的短時交通流預測方法[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.