慕　偉， 陳國定， 鐘引帆

（浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023）

基于K-Means和GA-WNN的交通流量預(yù)測

慕偉， 陳國定， 鐘引帆

（浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023）

如何對交通流進(jìn)行準(zhǔn)確和實時的預(yù)測是實現(xiàn)交通管理的關(guān)鍵所在。文章根據(jù)交通流數(shù)據(jù)的時間序列特性，提出基于K-Means算法與遺傳算法（GA）優(yōu)化的小波神經(jīng)網(wǎng)絡(luò)（WNN）預(yù)測方法：首先對交通流流量序列按照流量采用K-Means算法進(jìn)行分割，分割后的結(jié)果較符合流量的分布情況；然后使用GA-WNN對分割后的每一個時間段的交通流數(shù)據(jù)分別進(jìn)行建模和預(yù)測。仿真結(jié)果表明，該方法對交通流量預(yù)測的精度較好。

交通流量預(yù)測；K-Means算法；遺傳算法；小波神經(jīng)網(wǎng)絡(luò)

準(zhǔn)確預(yù)測城市道路交通流量對交通控制和交通誘導(dǎo)起到非常關(guān)鍵的作用。交通流量預(yù)測是在實時的路段檢測交通流數(shù)據(jù)基礎(chǔ)上，將各種檢測設(shè)備取得的實時數(shù)據(jù)通過適當(dāng)?shù)哪Ｐ秃头椒ɡ脷v史數(shù)據(jù)預(yù)測得到下一時段流量的數(shù)據(jù)。目前，交通流的預(yù)測方法主要有自回歸移動平均模型、時間序列模型、卡爾曼濾波模型、非參數(shù)回歸模型、神經(jīng)網(wǎng)絡(luò)模型、支持向量機模型和組合模型等［1-10］。自回歸移動平均模型方法計算簡單，但不能反映出交通流過程的不確定性與非線性，無法應(yīng)對突發(fā)事件對交通流造成的影響。時間序列模型方法較為成熟且預(yù)測精度較高，但初始化參數(shù)非常復(fù)雜、數(shù)據(jù)遺失嚴(yán)重?？柭鼮V波模型方法是線性預(yù)測，所以在預(yù)測非線性的交通流數(shù)據(jù)時計算量較大，輸出也有很大延遲。非參數(shù)回歸模型方法通過歷史數(shù)據(jù)中與當(dāng)前點相似的“近鄰”數(shù)據(jù)去預(yù)測下一時刻值，預(yù)測結(jié)果比參數(shù)建模精確［11-12］。支持向量機模型在解決小樣本、高維非線性模式識別問題有優(yōu)勢。相比之下神經(jīng)網(wǎng)絡(luò)模型更適合復(fù)雜、非線性的交通流預(yù)測。神經(jīng)網(wǎng)絡(luò)模型中在非線性參數(shù)估計和逼近中應(yīng)用較好的是小波神經(jīng)網(wǎng)絡(luò)（WNN），相對于BP神經(jīng)網(wǎng)絡(luò)，WNN時效性和收斂性方面都有明顯改善。遺傳算法（GA）是一種自適應(yīng)全局優(yōu)化的概率搜索算法，具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；概率化的尋優(yōu)方法能夠自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向。用GA優(yōu)化WNN可以使其具有較快的收斂性和較強的學(xué)習(xí)能力［13］。

本文采用GA-WNN的預(yù)測方法，同時考慮了交通流時間序列的特性，提出了對交通流數(shù)據(jù)使用K-Means算法進(jìn)行分割后再進(jìn)行分段預(yù)測的方法。

1　交通流量的序列分割

1.1 K-Means算法簡介

K-Means算法是由MacQueen在1967年提出的，作為較早期的聚類分析算法之一，它在很多學(xué)科領(lǐng)域中都有著廣泛的應(yīng)用［14］。它是基于目標(biāo)函數(shù)的聚類分析方法，目的是將樣本聚類成K個簇，其算法步驟有以下4個步驟：

（1）初始化。已知m個數(shù)據(jù)點的集合X={x1，x2，…，xi，…，xm}，其中xi∈R以及K個初始聚類集合C={c1，c2，…，cK}，每個劃分是一個類cK，每個類都有一個聚類質(zhì)心點μi。以歐氏距離作為判斷準(zhǔn)則，計算每類樣本點到質(zhì)心μi的距離平方和。

（2）樣本分類。對于樣品中的數(shù)據(jù)點，根據(jù)它們與聚類質(zhì)心點的距離，以距離最近即J（c，μ）最小的準(zhǔn)則分別將它們分配給與其最相似的聚類質(zhì)心所代表的類。

（3）計算新的聚類質(zhì)心C*。計算每個類別中所有數(shù)據(jù)點的均值作為該類的新聚類質(zhì)心。

式中：Ni是ck中的樣本個數(shù)。

（4）檢驗是否收斂：重復(fù)迭代第2步和第3步直到質(zhì)心不變或者變化很小，算法停止［10］。

1.2 交通流量的聚類分析

選取K-Means算法作為交通流量序列分割的方法，對一天或者一周甚至更長時間的交通流量作為聚類的原始樣本數(shù)據(jù)點。由于交通流量數(shù)據(jù)呈現(xiàn)一定的規(guī)律性，每一天從00∶00～24∶00的流量變化趨勢非常相似，所以采用預(yù)測當(dāng)天前一周同一天的流量數(shù)據(jù)來進(jìn)行聚類分析，流量聚類分析的步驟如下：

（1）首先對于交通流量樣本X根據(jù)流量值的大小，采用歐氏距離作為目標(biāo)函數(shù)，取K=3將其聚為類C1、C2、C3，流量值依次遞減。

（2）根據(jù)時間的先后順序?qū)1分為2類，而C2分為3類，C3分成2類，之所以這樣聚類是由于交通流量變化呈雙峰狀。

（3）最終一天的交通流量聚類分割之后變?yōu)?類，類與類之間可以通過時間的先后順序分辨出來。

2　交通流量預(yù)測模型

本文采用GA-WNN為交通流預(yù)測模型，小波神經(jīng)網(wǎng)絡(luò)是小波理論與人工神經(jīng)網(wǎng)絡(luò)的結(jié)合，用非線性小波基函數(shù)取代了BP神經(jīng)網(wǎng)絡(luò)原有的非線性傳遞函數(shù)，結(jié)合了小波變換的時頻局域化較好的特點以及BP神經(jīng)網(wǎng)絡(luò)的自學(xué)習(xí)能力，預(yù)測效果要優(yōu)于BP神經(jīng)網(wǎng)絡(luò)［15］。

2.1 小波神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

小波神經(jīng)網(wǎng)絡(luò)預(yù)測模型結(jié)構(gòu)與傳統(tǒng)的BP神經(jīng)網(wǎng)絡(luò)一樣采用3層結(jié)構(gòu)，即輸入層、隱含層、輸出層。本文采用示。

圖1　小波神經(jīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

圖中x1，x2，…，xk為網(wǎng)絡(luò)輸入?yún)?shù)，k為輸入層結(jié)點個數(shù)，m為隱含層結(jié)點個數(shù)，wij為輸入層結(jié)點i（i=1，2，…，k）跟隱含層結(jié)點j（j=1，2，…，m）連接的網(wǎng)絡(luò)連接權(quán)值，w1，w2，…，wm為隱含層跟輸出層之間的網(wǎng)絡(luò)連接權(quán)值，y為網(wǎng)絡(luò)輸出層的輸出值。

根據(jù)交通流量的相關(guān)性，構(gòu)造小波神經(jīng)網(wǎng)絡(luò)交通流預(yù)測模型。其中某路段交通流量Qt與其前幾個時段的交通流量有必然聯(lián)系，本文輸入層有4個神經(jīng)元（Qt， Qt-1，Qt-2，Qt-3）；隱含層神經(jīng)元個數(shù)的確定一直是神經(jīng)網(wǎng)絡(luò)的領(lǐng)域的難點，我這里采用傳統(tǒng)的經(jīng)驗測試法，一般取2k+1；輸出結(jié)點數(shù)為1，即預(yù)測的交通流量Qt+1。

隱含層轉(zhuǎn)移函數(shù)φ（x）選取的是小波函數(shù)Morlet，其定義如下：

對φ（x）做伸縮和平移變換便可以得到小波基函數(shù)φa，b（x）：

式中：a為伸縮因子，b為平移因子。

輸出層激勵函數(shù)采用Sigmoid函數(shù)：

網(wǎng)絡(luò)輸出y為：

2.2算法流程

本文根據(jù)交通流量數(shù)據(jù)時變、非線性的特點，設(shè)計了小波神經(jīng)網(wǎng)絡(luò)，其具體算法流程如圖2所示。

圖2　小波神經(jīng)網(wǎng)絡(luò)算法流程

當(dāng)輸入交通流量樣本數(shù)據(jù)時，小波神經(jīng)網(wǎng)絡(luò)首先進(jìn)行前向傳播得到網(wǎng)絡(luò)的輸出值，然后根據(jù)輸出值與期望值之間的誤差反向傳播調(diào)整連接權(quán)值等參數(shù)。小波神經(jīng)網(wǎng)絡(luò)的反向傳播采用梯度下降法修正權(quán)值參數(shù)，其修正過程為：式中：yqw為期望輸出；y為預(yù)測輸出。

取均方誤差函數(shù)E為性能指標(biāo)函數(shù)，其表達(dá)式如下：

為了使誤差E最小，采用梯度下降法修正網(wǎng)絡(luò)參數(shù)：

式中：wij和wm為網(wǎng)絡(luò)權(quán)值；aj為伸縮因子；bj為平移因子。

可以看出參數(shù)修正方法都是一致的，修正的過程可以反映出誤差反傳播的思想。但是單一的采用梯度下降法來優(yōu)化參數(shù)，整個網(wǎng)絡(luò)容易陷入局部極小和引起振蕩效應(yīng)，因此在WNN的基礎(chǔ)之上，利用遺傳算法對其參數(shù)進(jìn)行優(yōu)化來提高預(yù)測精度。

2.3 基于遺傳算法的小波神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化

遺傳算法是基于自然選擇和遺傳學(xué)的優(yōu)化搜索算法。對小波神經(jīng)網(wǎng)絡(luò)連接權(quán)值和平移伸縮因子參數(shù)進(jìn)行編碼，形成染色體并對其進(jìn)行復(fù)制、交叉及變異操作，染色體不斷進(jìn)化，從而產(chǎn)生最優(yōu)解的染色體，即網(wǎng)絡(luò)的參數(shù)。參數(shù)優(yōu)化步驟如下：

（1）選擇編碼方式

設(shè)初始種群規(guī)模為N，對種群規(guī)模N，網(wǎng)絡(luò)連接權(quán)值wij和wm、伸縮因子aj和平移因子bj進(jìn)行初始化編碼。采用實數(shù)進(jìn)行編碼，交叉概率為Pc，突變概率為Pm，解碼時將基因值作為網(wǎng)絡(luò)相應(yīng)的參數(shù)。

（2）確定個體適應(yīng)度函數(shù)

個體i的適應(yīng)度函數(shù)f（i）為：式中：E為上述小波神經(jīng)網(wǎng)絡(luò)的誤差函數(shù)。

（3）選擇算子

每一個個體按照其適應(yīng)值進(jìn)行排序，采用輪盤賭選擇法，然后按照公式（18）選擇網(wǎng)絡(luò)個體：

（4）交叉變異

以概率Pc對2個個體Ga和Gb進(jìn)行交叉運算后產(chǎn)生的2個新個體G'a和G'b，沒進(jìn)行交叉運算的其他個體直接進(jìn)行復(fù)制即可。以概率Pm采用均勻變異法進(jìn)行變異操作產(chǎn)生新的個體，并將新個體插入到種群P中，并計算新個體的適應(yīng)度，如果適應(yīng)度滿足精度要求，優(yōu)化過程結(jié)束。將最終的群體中最優(yōu)個體解碼作為小波神經(jīng)網(wǎng)絡(luò)的連接權(quán)值和伸縮平移因子。再通過對樣本訓(xùn)練，最終得到經(jīng)遺傳算法優(yōu)化的小波神經(jīng)網(wǎng)絡(luò)預(yù)測輸出。

3　仿真試驗

本文以杭州市天目山路段為研究對象，根據(jù)該路段實測的交通流量歷史數(shù)據(jù)（連續(xù)4天工作日凌晨0∶00到晚上24∶00，每15 min一組的交通流量數(shù)據(jù)），共整理得到368條數(shù)據(jù)，取前3天的276條數(shù)據(jù)作為訓(xùn)練樣本，最后一天的92條數(shù)據(jù)作為測試樣本。

未分段只采用小波神經(jīng)網(wǎng)絡(luò)進(jìn)行預(yù)測，網(wǎng)絡(luò)結(jié)構(gòu)為4-9-1，即輸入層參數(shù)為4個過去時間點的流量（Qt，Qt-1，Qt-2，Qt-3），隱含層為9個，輸出層為1個預(yù)測

輸出交通流量Qt+1，為了方便比較，本文采用平均絕對誤差（MAE）、平均絕對百分比誤差（MAPE）、均方誤差（MSE）、均方百分比誤差（MSP）作為模型的評價指標(biāo)，預(yù)測的交通流量圖和實際的交通流量圖如圖3所示：

圖3　小波神經(jīng)網(wǎng)絡(luò)預(yù)測交通流量

模型的指標(biāo)預(yù)測誤差如表1所示。

表1 未分段的小波神經(jīng)網(wǎng)絡(luò)預(yù)測誤差

采用本文的方法預(yù)測，首先使用K-Means算法對交通流序列進(jìn)行劃分，樣本數(shù)據(jù)為預(yù)測當(dāng)天前一周同一天的從凌晨0∶00到晚上24∶00的交通流量歷史數(shù)據(jù)，根據(jù)1.2小節(jié)的劃分步驟將一天的交通序列劃分為0∶00～5∶45，5∶45～7∶00，7∶00～9∶45， 9∶45～15∶15，15∶15～18∶30，18∶30～22∶15，22∶15～23∶45共7個時間段，如圖4所示。

圖4　交通流量時間序列聚類圖

而實際上22∶15～23∶45與0∶00～5∶45為連續(xù)的時間段且聚類結(jié)果為同一類，所以預(yù)測時把2個時間段歸為一個時間段進(jìn)行預(yù)測。然后對交通序列分割之后的每個時段分別用小波神經(jīng)網(wǎng)絡(luò)預(yù)測模型進(jìn)行預(yù)測，得到各時段的預(yù)測誤差如表2所示。

表2　各時段的預(yù)測誤差

由表2數(shù)據(jù)可以看出，流量較低的時段預(yù)測誤差相對較高，流量較高的2個高峰時段預(yù)測誤差相對較低，后5個時段的預(yù)測誤差都要小于未采用序列分割的小波神經(jīng)網(wǎng)絡(luò)預(yù)測模型。

對于分割后的交通流量序列采用遺傳算法優(yōu)化小波神經(jīng)網(wǎng)絡(luò)參數(shù)時，種群規(guī)模取10，交叉概率取0.4，變異概率為0.2，遺傳代數(shù)為100，網(wǎng)絡(luò)的目標(biāo)誤差為0.01，網(wǎng)絡(luò)結(jié)構(gòu)為4-9-1。以下是流量較高的2個高峰時段分別采用WNN、GA-WNN的預(yù)測結(jié)果，并給出了未分段前采用WNN的預(yù)測結(jié)果。

第1個交通流量的高峰時段為7:00～9:45，預(yù)測結(jié)果和實際交通流量對比如圖5所示，第2個高峰時段在15∶15～18∶30，預(yù)測結(jié)果和實際交通流量對比如圖6所示。

由表1和表2可以得出，分段后的預(yù)測結(jié)果優(yōu)于未分段前的預(yù)測結(jié)果，但是預(yù)測精度并沒有很大的提升。由圖5和圖6可以得出，采用遺傳算法改進(jìn)的小波神經(jīng)網(wǎng)絡(luò)預(yù)測精度相比于小波神經(jīng)網(wǎng)絡(luò)有較大的提升，可以更好地預(yù)測交通流量。

圖5　第1個高峰時段的預(yù)測結(jié)果圖

圖6　第2個高峰時段的預(yù)測結(jié)果圖

4　結(jié)論

本文針對交通流量序列的特性，提出了K-Means和GA-WNN結(jié)合的預(yù)測方法。首先對一天的交通流量序列采用K-Means算法進(jìn)行聚類，將其劃分成7個時間段，然后再分別對每一個時間段采用遺傳算法優(yōu)化的小波神經(jīng)網(wǎng)絡(luò)預(yù)測模型進(jìn)行預(yù)測。仿真結(jié)果表明，分段后的預(yù)測精度高于未分段，經(jīng)GA優(yōu)化WNN模型的收斂速度較WNN更快，預(yù)測精度也更高，可以有效地預(yù)測下一時段的交通流量。

［1］史其信，鄭為中.道路網(wǎng)短期交通流預(yù)測方法比較［J］.交通運輸工程學(xué)報，2004，4（4）：68-71.

［2］韓超，宋蘇，王成紅.基于ARIMA模型的短時交通流實時自適應(yīng)預(yù)測［J］.系統(tǒng)仿真學(xué)報，2004，16（7）：1530-1535.

［3］臧利林，賈磊，楊立才，等.交通流實時預(yù)測的混沌時間序列模型［J］.中國公路學(xué)報，2007，20（6）：95-99.

［4］Xie Yuanchang，Zhang Yunlong， Ye Zhirui. Short-term traffic volume forecasting using Kalman filter with discrete wavelet decomposition［J］.Computer-Aided Civil and Infrastructure Engineering，2007，22（5）：326-334.

［5］楊兆升，朱中.基于卡爾曼濾波理論的交通流量實時預(yù)測模型［J］.中國公路學(xué)報，1999，7（3）：63-67.

［6］宮曉燕，湯淑明.基于非參數(shù)回歸的短時交通流量預(yù)測與事件監(jiān)測綜合算法［J］.中國公路學(xué)報，2003，16（1）：82-86.

［7］傅惠，胡剛，徐建閩，等.基于神經(jīng)網(wǎng)絡(luò)的城市關(guān)聯(lián)交叉口交通流預(yù)測控制方法［J］.中國公路學(xué)報，2008，21（5）：91-95.

［8］傅貴，韓國強，逯峰，等.基于支持向量機回歸的短時交通流預(yù)測模型［J］.華南理工大學(xué)學(xué)報，2013，41（9）：71-76.

［9］楊顯立， 許倫輝， 周勇.基于小波神經(jīng)網(wǎng)絡(luò)的道路交通流>量實時預(yù)測模型研究［J］.公路交通技術(shù)，2013（5）：111-113.

［10］沈國江，王嘯虎，孔祥杰.短時交通流量智能組合預(yù)測模型及應(yīng)用［J］.系統(tǒng)工程理論與實踐，2011，31（3）：561-568.

［11］Smith BL，Williams BM，Oswald RK. Comparison of parametric and nonparametric models for traffic flow forecasting［J］. Transportation Research Part C-Emerging Technologies，2002，10（4）：303-321.

［12］張曉利，陸化普.非參數(shù)回歸方法在短時交通流預(yù)測中的應(yīng)用［J］.清華大學(xué)學(xué)報，2009，49（9）：1471-1475.

［13］楊超，王志偉.經(jīng)GA優(yōu)化的WNN在交通流預(yù)測中的應(yīng)用［J］.計算機工程，2011，37（14）：149-151.

［14］王千，王成，等.K-means聚類算法研究綜述［J］.電子設(shè)計工程，2012，20（7）：21-24.

［15］陳振偉，郭拯危.小波神經(jīng)網(wǎng)絡(luò)預(yù)測模型的仿真實現(xiàn)［J］.計算機仿真，2008，25（6）：147-150.

Traffic Flow Prediction Based on K-Means and GA-WNN

Mu Wei， Chen Guoding， Zhong Yinfan
（College of Information Engineering， Zhejiang University of Technology， Hangzhou 310023， China）

Accurate and real-time traffic flow prediction is the key to the implementation of traffic management. According to the characteristic of time series of traffic flow， a prediction method based on K-Means and wavelet neural network （WNN） optimized by genetic algorithm （GA） is proposed. Firstly， traffic flow sequence is segmented according to the flow using the K-Means algorithm， the segmented results is in agreement with the distribution of flow; and then the GA-WNN method is used for modeling and forecasting of the segmented traffic flow data respectively. The simulation results show that the traffic flow prediction accuracy of the method is better.

traffic flow prediction; K-Means algorithm; genetic algorithm; wavelet neural networks

U491.1+12

A

1672–9889（2015）05–0070–05

慕偉（1991-），男，安徽亳州人，碩士研究生，研究方向為智能交通。

（2015-01-08）