基于K-Means和GA-WNN的交通流量預測

慕　偉， 陳國定， 鐘引帆

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

基于K-Means和GA-WNN的交通流量預測

慕偉， 陳國定， 鐘引帆

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

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

交通流量預測；K-Means算法；遺傳算法；小波神經網絡

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

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

1　交通流量的序列分割

1.1 K-Means算法簡介

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

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

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

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

式中：Ni是ck中的樣本個數。

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

1.2 交通流量的聚類分析

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

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

（2）根據時間的先后順序將C1分為2類，而C2分為3類，C3分成2類，之所以這樣聚類是由于交通流量變化呈雙峰狀。

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

2　交通流量預測模型

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

2.1 小波神經網絡的拓撲結構

小波神經網絡預測模型結構與傳統(tǒng)的BP神經網絡一樣采用3層結構，即輸入層、隱含層、輸出層。本文采用示。

圖1　小波神經網絡拓撲結構

圖中x1，x2，…，xk為網絡輸入參數，k為輸入層結點個數，m為隱含層結點個數，wij為輸入層結點i（i=1，2，…，k）跟隱含層結點j（j=1，2，…，m）連接的網絡連接權值，w1，w2，…，wm為隱含層跟輸出層之間的網絡連接權值，y為網絡輸出層的輸出值。

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

隱含層轉移函數φ（x）選取的是小波函數Morlet，其定義如下：

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

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

輸出層激勵函數采用Sigmoid函數：

網絡輸出y為：

2.2算法流程

本文根據交通流量數據時變、非線性的特點，設計了小波神經網絡，其具體算法流程如圖2所示。

圖2　小波神經網絡算法流程

當輸入交通流量樣本數據時，小波神經網絡首先進行前向傳播得到網絡的輸出值，然后根據輸出值與期望值之間的誤差反向傳播調整連接權值等參數。小波神經網絡的反向傳播采用梯度下降法修正權值參數，其修正過程為：式中：yqw為期望輸出；y為預測輸出。

取均方誤差函數E為性能指標函數，其表達式如下：

為了使誤差E最小，采用梯度下降法修正網絡參數：

式中：wij和wm為網絡權值；aj為伸縮因子；bj為平移因子。

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

2.3 基于遺傳算法的小波神經網絡參數優(yōu)化

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

（1）選擇編碼方式

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

（2）確定個體適應度函數

個體i的適應度函數f（i）為：式中：E為上述小波神經網絡的誤差函數。

（3）選擇算子

每一個個體按照其適應值進行排序，采用輪盤賭選擇法，然后按照公式（18）選擇網絡個體：

（4）交叉變異

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

3　仿真試驗

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

未分段只采用小波神經網絡進行預測，網絡結構為4-9-1，即輸入層參數為4個過去時間點的流量（Qt，Qt-1，Qt-2，Qt-3），隱含層為9個，輸出層為1個預測

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

圖3　小波神經網絡預測交通流量

模型的指標預測誤差如表1所示。

表1 未分段的小波神經網絡預測誤差

采用本文的方法預測，首先使用K-Means算法對交通流序列進行劃分，樣本數據為預測當天前一周同一天的從凌晨0∶00到晚上24∶00的交通流量歷史數據，根據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ù)的時間段且聚類結果為同一類，所以預測時把2個時間段歸為一個時間段進行預測。然后對交通序列分割之后的每個時段分別用小波神經網絡預測模型進行預測，得到各時段的預測誤差如表2所示。

表2　各時段的預測誤差

由表2數據可以看出，流量較低的時段預測誤差相對較高，流量較高的2個高峰時段預測誤差相對較低，后5個時段的預測誤差都要小于未采用序列分割的小波神經網絡預測模型。

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

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

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

圖5　第1個高峰時段的預測結果圖

圖6　第2個高峰時段的預測結果圖

4　結論

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

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

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

［3］臧利林，賈磊，楊立才，等.交通流實時預測的混沌時間序列模型［J］.中國公路學報，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］楊兆升，朱中.基于卡爾曼濾波理論的交通流量實時預測模型［J］.中國公路學報，1999，7（3）：63-67.

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

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

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

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

［10］沈國江，王嘯虎，孔祥杰.短時交通流量智能組合預測模型及應用［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］張曉利，陸化普.非參數回歸方法在短時交通流預測中的應用［J］.清華大學學報，2009，49（9）：1471-1475.

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

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

［15］陳振偉，郭拯危.小波神經網絡預測模型的仿真實現［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）