自適應參數尋優短期車流量預測

王鳳琴 盧官明 柯亨進

1(湖北師范大學物理與電子科學學院 湖北 黃石 435102) 2(南京郵電大學信息與通信工程學院 江蘇 南京 210003) 3(武漢大學計算機學院 湖北 武漢 430072)

0 引 言

當前，交通擁堵是影響城市生活的重要問題。交通疏導系統通過預測短時路口車流量，向上下班高峰期的司機推薦合適的路徑，以達到疏導交通目的。針對這一問題，國內外很多研究學者致力于相關方面的研究[1-2]。在短期流量預測上，自回歸滑動平均模型(ARIMA)可取得較高的預測性能[1]。在有效理解周期變化較為明顯數據的變化趨勢以及季節性模式的基礎上，已有時間序列模型可有效刻畫歷史數據模式，從而演化預測數據的變化趨勢[2]。然而，缺乏對影響預測性能起關鍵作用的步長和順序等隱變量進行有效建模。

鑒于很多不確定因素(季節、氣候條件、交通事故和司機的心里狀態)對交通狀況有著不可忽視的巨大影響，致使現實中的交通流量數據往往呈現出非線性、非平穩和高噪聲、高干擾等特性，其結果是實時的交通流量預測難上加難。盡管數據呈現出隨機的、雜亂無章的特性，但畢竟是有序的、有界的。因此模式具備潛在規律，簡言之，灰色預測就是利用這種規律建立灰色模型對灰色系統進行預測[3]。灰色預測由于其高預測精度、簡單和易用性而受到越來越多研究者的關注，并已成功應用于交通流量預測中[4]。針對灰色模型對呈現出近似指數增長的數據所取得的預測性能出現震蕩和下降等問題，一個新的組合模型(組合灰色模型和最小二乘支持向量機)被提出進行交通流量預測并取得較優的預測性能[5]。但由于支持向量機的所需訓練時間太長，在實際應用中難以實現實時動態訓練。

一個有效刻畫時間序列的隱變量的策略是對時間序列歷史時間點進行加權。當前，加權策略包括設定固定值的靜態策略和線性回歸預測法等[6]。靜態策略對于動態數據的擬合程度不高，不滿足動態系統的要求。線性回歸預測法所預測的權值對于屬性權值呈現線性的情況下，其預測性能較好。而對于非線性、非平穩、高噪聲高干擾的數據，擬合效果欠佳。為消除由于隱變量的不確定性和非線性而造成的序列的動態性，本文對隱變量進行動態建模，動態擬合隱變量的非線性變化關系，對隱變量自動尋優建模，以期對時間序列的動態建模。

隨著近幾年統計學習理論和統計方法的發展，很多相干性度量方法被提出，以彌補線性相關系數無法識別非線性關系的缺陷。如相關比例、最大相關系數、均方列聯系數、斯皮爾曼相關系數、距離相關和基于信息理論的指標等。從相依性指標所應用的性質上看，基于信息理論的指標是最好的。而文獻[7]從線性、非線性、抗噪性、健壯性和尋求非函數關系等方面對最大信息系數MIC(Maximal Information Coefficient)，相關系數和互信息進行比較，MIC都取得了較優的性能。其主要優點包括：(1) 不需要對數據分布做任何假設，估計變量之間的相關性(包括線性和非線性)；(2) MIC也能檢測非線性相關性(正弦關系)；(3) 最大信息系數的非參數特性與抗噪能力。

綜上所述，本文基于動態建模理論，提出一種針對動態非線性變化的隱變量的動態隨機過程模型，以期理解時間序列的動態演化模式，并結合度量雙變量相關性的最大信息系數對時間序列屬性加權，最后成功運用于短時車流量預測。本文的貢獻如下：

1) 基于步長有限時間序列，提出近似平穩假設條件，結合動態建模理論，設計一種對影響預測性能隱變量的建模方法。

2) 理論證明隱變量動態隨機過程模型的收斂條件。

3) 采用無監督學習策略對諸如條件模型、權值和閾值等參數進行自動學習，這樣可以節省大量的人力，使得模型具有現實意義。

1 動態隨機過程模型

現實數據往往呈現出非線性、非平穩、高噪聲、高干擾、無固定模式等特點，其主要原因是影響數據變化的因數是不確定的。動態建模是解決這一問題的有效手段，如基于狀態空間可測的準域動態系統[8]和狀態約束動態系統[9]，但其只能刻畫固定狀態空間的動態系統而無法刻畫狀態變化的動態系統。而針對狀態空間實時動態變化的數據，動態隨機過程模型可感知外界環境，依據歷史狀態持續更新當前狀態和未來狀態，自適應動態地選擇不同的超參數，以至于對未來狀態的預測。

動態模型由一組模型行為所組成，包含一組隨機變量以及所需滿足的隱變量條件。根據強化學習策略，動態隨機過程模型對影響優化目標的隱變量進行建模，逐步確定優化目標與隱變量之間的關系，最終達到目標優化。傳統貝葉斯強化學習無法用于加權時間序列分析的主要原因是時間序列往往比較長，所需訓練參數太多而算不了、算不清。針對POMDP[11]的Markov特性限制，無法刻畫多個狀態間關系等缺陷。因此有必要設計一種動態建模方法，解決隱變量的動態演化與動態反饋問題。針對這一問題，動態隨機過程模型DSPM(Dynamic Stochastic Process Model)試圖對隱變量進行動態建模，其定義如下：

定義1(DSPM) 一個動態隨機過程模型是一個四元組(V,P,TS,C,T)，其中：V是隨機變量的有限集合，P是特定時間點隨機變量的聯合概率，TS是整個時間序列，C是時間序列的隱變量，是影響預測性能的參數，T：P×Cts→Π(P)是概率轉移函數，在特定時間點，對于每一個狀態和行動，計算相應狀態下采取行動的概率分布。

動態隨機過程模型需要解決兩個問題：一方面是隱變量的量化，另一方面是確定概率轉移矩陣。第二個問題在第一個問題解決的基礎上結合Markov鏈而解決，因此，第一個問題是解決動態隨機過程的首要問題，該問題用Bayes強化學習策略[10]解決。在特定時間點，令P(ci)是隱變量的先驗概率分布，P(p|ci)是在特定隱變量下，觀測目標的條件概率，依據貝葉斯原理，隱變量的后驗概率更新如下：

(1)

傳統POMDP認為當前狀態和回報值只與前一個狀態和回報值有關。但在實際中，當前狀態與之前多于1時刻的先前狀態有關。選擇多少步長的時間序列是至關重要的：(1) 可以減弱無關步長序列的影響；(2) 大大減少權值訓練參數。所有歷史決策條件的分布都被保存，結合貝葉斯強化學習策略，預測當前相應的上下文條件分布。即在每一個時刻，后驗分布Pr(Ct)被遞歸更新，且agent執行一個動作(參數的確定)a，同時接受一個觀測值Z[10]:

(2)

動態隨機過程模型隨著所有之前時間步長下的所有隱變量的確定而創建。其計算過程是一個迭代過程，圖1顯示了該逐步求解過程。在當前第i步，之前的所有步(1…i-1)條件C(c和c″)和觀測值Z都已經被求解出，依據式(2)可以求出當前時刻的隱變量，當前時刻的權值由式(11)(見下一節)求出，而當前觀測值由灰色加權預測得出。

圖1 動態隨機過程模型的迭代更新過程

定義2(動態隨機過程) 對于隨機過程{X(t),t∈T}，及任何n時刻點ti,i=1,2,…,n,滿足t1

(1)X(0) = 0。

(2)X(t)是獨立增量過程。

(3)P{X(t+h)-X{t}=1}=f(c,t)h+o(h)

P{X(t+h)-X{t}>1}=o(h)

(4) 均值函數是條件和時間的函數，也稱為條件期望。即：

定理1(收斂性條件) 如果X的動態隨機過程的收斂性、滿足定義2得計算條件方程：

(3)

2 自適應參數尋優灰色加權預測

為高效準確地對早高峰車流量進行預測以輔助交通疏導，針對影響時間序列預測性能的隱變量動態變化問題，建立基于閾值系統和動態隨機過程模型的數據特征選擇模型，結合貝葉斯強化學習策略與動態隨機過程模型，實現最大信息系數屬性加權灰色算法。圖2顯示了系統的總體架構圖。系統對早高峰車流量信息建立時間序列數據庫，主體包含分析建模、模型運行和模型發布三個模塊。分析建模模塊主要完成學習率等超參數設定的閾值系統建立、建立步長和順序的上下文條件動態模型以實現特征選擇、利用動態隨機過程模型實現屬性重要程度的最大信息系數的屬性加權策略。模型運行模塊主要實現灰色模型時間序列預測算法和基于貝葉斯強化學習策略的動態隨機過程模型。模型發布主要產生基于知識庫的模型文件、后臺監控日志和各種預測曲線的圖表生成。

圖2 系統架構圖

2.1 懲罰因子選擇

時間序列預測的一個重要目標是獲得預測值與真實值之間絕對殘差的最小值，因此，選擇絕對殘差作為懲罰因子是合適的。絕對殘差的定義如下：

εi=|predicti-reali|/reali

(4)

在任意需要決策的時間點，之前所有的懲罰因子被觀測。依據貝葉斯強化學習策略，并運用式(2)，可計算當前時間點的懲罰因子。

2.2 最大信息系數

為量化雙變量非線性函數關系，Reshef提出“最大信息系數”，通過在線性和非線性度量、抗噪聲、健壯性和尋找非線性函數關系等方面比較MIC和MI、相關系數，得出MIC具有較優的性能[7]。

給定有序屬性對的有限集合D，每一個屬性都有x方向和y方向兩個方向的成分。將x成分以網格方式分割成x網格，同理，將y部分分割為y網格，整個網格稱為x×y網格。每個子格的互信息計算如下：

I(D|G)=I(X;Y)=

(5)

其中最大的互信息定義為：

I*(D,G(b1,b2,…,bm))=maxI(D/G)

(6)

對于無限數據，MIC定義為：

(7)

而對于樣本大小為n并且格數小于B(n)的雙變量，MIC定義為：

(8)

式中:ω(1)

MIC可以有效度量大量數據集各屬性之間關聯強度，具有如下性質：

? 有界性：所有MIC值都落在[0,1]區間內。

? 對稱性：MIC(x,y)=MIC(y,x)。

? 穩健性：MIC不受異常值的影響，而相關系數易受異常值的影響。

2.3 動態特征融合權值計算

時間序列預測中，有兩個問題亟待解決。

(1) 為避免過分擬合，需進行特征選擇。特征選擇一般基于閾值系統。有別于傳統專家建議的固定閾值，本文把閾值當作一種隱變量，運用動態隨機過程模型對閾值與預測精度關系的迭代更新，最終獲得較優的動態閾值。

(2) 屬性加權問題。在每個時間點，依據動態隨機過程模型獲取歷史隱變量，以及根據式(2)所得相應概率，不同時間點所有隱變量(步長和逆序數)的融合度量值：

(9)

式中：P(C=ci)表示選擇第i個隱變量的后驗概率，依據動態隨機過程模型，由式(2)計算出，ci是對第i個隱變量的量化，其量化值如下：

(10)

式中:MIC(εi)為第i步所有隱變量預測殘差序列之間的相干性度量，其具體計算過程如下：

首先依據DSPM選擇決定性隱變量，也即時間步長，由式(2)確定不同步長的后驗概率，其概率大者就是步長的最佳選擇。例如，在當前步長為4時，其最佳步長是3(見3.2節的圖5)；其次，在特定步長下，依據DSPM選擇出逆序數候選集，本文采用擊中概率前10的逆序數候選集，繼而計算所有候選集內每個逆序數所對應的殘差序列。最后，依據式(8)計算所有殘差序列之間的MIC度量值。

2.4 屬性加權灰色模型

2.4.1 灰色模型

灰色預測模型[3]由于具有所需原始信息量少、計算簡單及預測精度高等優點而受到研究學者關注[12-13]。王利等基于滾動推演策略提出動態灰色預測模型，并成功應用于大壩變形的預測預報[12]。為提高雷達電子部件狀態趨勢預測精度，黃建軍等人改進GM(1，1)和SVR模型，提出基于GM(1，1)與支持向量回歸機(SVR)組合預測模型，取得更高的預測精度與更強的適應能力[13]。詳細算法請參見文獻[3]。

2.4.2 權值計算

不同屬性具有不同的重要程度，如何進行屬性加權是機器學習領域的一個重要問題。計算過程包括：(1) 歷史時間步長的選擇；(2) 步長固定情況下逆序數確定；(3) 步長固定情況下，度量不同逆序數下殘差序列的相干性；(4) 基于相干性度量的權值計算。本文利用所提出的動態隨機過程解決問題(1)和(2)，值得注意的是，步長和逆序數的確定有主次之分，考慮到MIC的計算需要相同長度的序列，因此首先需將步長選擇出來，利用最大信息系數進行相干性度量以解決問題(3)，對于問題(4)，我們利用相干度量值的平均化來去掉權值的波動性，致使預測算法的平穩性。在當前時間點的權值計算步驟如下：

(1) 在每個時間點，式(8)計算出兩兩隱變量的相互關系強度，對于整個時間序列來說，第i個融合步長的相關強度度量為co-stepi，正則化相關強度度量可以得到每個時間點的權值wi：

(11)

(2) 最終的權值序列如下：

W={w1,…,wi,…,wn}

(12)

2.4.3 加權灰色模型

通常，統計模型總是可以表示為：

Y=Xβ+ε

(13)

式中:X是觀測向量，β為系數，ε為殘差，Y是回歸預測向量。

定義廣義殘差平方和對參數β進行評估：

RSS(β)=(Y-Xβ)TΣ-1(Y-Xβ)

(14)

式中:Σ是對角陣，也是本文中的權值矩陣：

(15)

依據最小二乘法，其參數β的評估值如下：

β=(XTΣ-1X)-1XTΣ-1Y

(16)

加權灰色模型x(0)(i)+az(1)(i)=u，其中z(1)(i)為滑動平均算子(z(1)(i)=0.5x(1)(i-1)+x(1)(i))，a和u是待估計的模型參數。最小化平方加權殘差和argmin(εTΣε)，所以灰色參數向量估計如下：

(au)T=(BTWB)-1BT

(17)

2.5 預測算法

本節討論動態隨機過程預測算法。算法1是整體框架。算法2計算第一步中提取的所有特征所組成的融合步長，不失一般性，系統初始化隱變量的概率分布為泊松過程，最后，計算在時間序列中的每一個時間點的權值并應用于灰色模型，建構屬性加權灰色模型。

算法1整體框架

輸入：交通流向量組A{a1,a2,…,an}

輸出：預測向量y

從A中的每一個時間點中抽取特征向量

訓練閾值、步長和順序

計算融合步長

建構屬性加權灰色模型

算法2DSPM算法

初始化隱變量先驗分布為泊松分布

輸入：特征列向量，之前動作、可信狀態和上下文條件

輸出：隱變量后驗分布預測值

循環:在所有之前的時間點

在第i列，從數據庫中裝載之前所有的動作和回報

裝載第i個動作

裝載第i個觀察值

當前條件回報值計算，通過殘差re的正負號來確定是否是采用之前的條件還是對條件進行更新：

c(a,z)←min(c(a,z),c(a,z)+re*f(z)*P(z|c)))

根據式(2)更新該條件以及相關條件的回報值的后驗分布

結束循環

輸出：取得最大回報值的隱變量

3 范例——交通流量短期預測

城市交通線視為一個動態隨機圖(N,E,W)，N表示節點，E表示雙向邊，W是通過公路某段時間的車輛數。本文的預測目標是實時預測圖(N,E,W)中所有W的值。

本文的數據集來自于武漢市光谷大道早高峰的交通流數據，數據集以15 min為間隔，采集時間段內通過金融港前面的段截面的車流量作為預測目標。

3.1 特征提取

本節旨在提取出那些影響預測性能的特征，也即上下文條件。在任意時間點，所有之前的步長與相應的殘差被記錄下來。圖3顯示了不同步長下平均殘差與該步長之間的關系。x軸是當前時間點的所有步長，y軸是在不同步長下的平均殘差。在其他條件固定的情況下，步長的選擇對預測性能的影響較大，最大平均殘差幾乎可以達到最低平均殘差的1.5倍，因此，選擇不同的步長可以改善預測性能。

圖3 在當前步長，當選取不同步長時其平均殘差的變化趨勢

類似的，數據順序也會影響預測性能。圖4顯示不同逆序數情況下的平均殘差。x軸是當前時間點的逆序數，y軸是對應的平均殘差。排列逆序數是一個排列中逆序的總數。逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。如2431中，21、43、41、31是逆序，逆序數是4，為偶排列。從圖中可看出，最大平均殘差幾乎可以達到最低平均殘差的1.5倍，合適的逆序數可以極大改善預測性能。

圖4 顯示了不同逆序數與殘差之間的關系

3.2 步長與順序訓練

在當前時間點，所有之前的決策選擇以及與之相應的殘差都保存到數據庫中，在選擇步長時，計算在當前步長下，不同步長的選擇而產生的殘差，當殘差小于當前步長下的平均殘差時，認為該步長的選擇是有效的(為方便描述，本文定義該概率值為擊中概率)，否則是無效的(非擊中概率)，也即：

ε(p(cp|cc))

(18)

式中：ε表示殘差函數，p表示概率，cc表示當前步長，cp表示選擇在當前時間點前的某個步長，avg表示均值。圖5顯示了在不同時間點時，取不同步長時的擊中概率的轉移概率圖。從圖中可以看出，在當前步長小于6時，傾向于選擇較少的步長，反之選擇較長的步長比較合適。圖中的粗線顯示出在當前步長下的最優選擇概率。逆序數選擇策略，逆序數的選擇在步長小于等于6時，通過轉移概率圖進行選取，在大于6的時候，在上一步的逆序數選取的基礎上隨機插入當前要插入的步長進行選取，該方法主要考慮逆序數對于預測性能影響較小，但是考慮全面需非常高昂的計算費用。

圖5 不同時間點下不同歷史步長的擊中概率的轉移概率圖

3.3 結果比較

本節從兩個方面進行比較，一方面，本文方法與其他灰色模型的橫向比較；其二是同其他經典回歸模型的縱向比較。圖6顯示了縱向比較結果(包括支持向量機(左)，Arima(中)和我們的方法(右))下早高峰車流量的真實值(細線條)和預測值(粗線條)。ARIMA方法對周期不明顯的數據擬合欠佳，有些情況下幾乎是一條水平橫線，而支持向量機的快速擬合性不如我們的方法。我們的方法在短數據的時候能夠快速地擬合數據，特別適合早高峰時期的車流量預測，因為開始預測早高峰前時的類似模式的數據量較少，無法呈現出與早高峰車流量相匹配的車流量信息。

圖6 三種不同預測方法下早高峰車流量的真實值和預測值

3.3.1 與其他灰色模型進行比較

計算不同灰色模型策略(經典的灰色模型[3]，屬性加權灰色模型[14]和本文的基于動態隨機過程的貝葉斯強化學習策略)下每天早高峰預測值與真實值之間的平均殘差，通過該殘差比較不同策略的性能。圖7顯示了不同月份三種模型下的平均殘差。從圖中顯示，相較于經典灰色模型，加權灰色模型有一定的性能改進，但是由于其固定加權策略，無法準確地動態擬合數據，而本文的策略由于動態針對不同時期的數據進行加權，從而較好較快地對數據進行擬合，從而有一倍以上的性能改善。

圖7 2014年1月份到七月份不同灰色模型下的平均殘差

3.3.2 與其他回歸模型的比較

計算不同預測模型策略(ARIMA模型、徑向基支持向量機模型和本文的基于動態隨機過程的貝葉斯強化學習策略)下每天早高峰預測值與真實值之間的平均殘差，通過該殘差比較不同策略的性能。圖8顯示了不同月份三種模型下的平均殘差。從圖中可以看出，ARIMA和SVM模型的性能基本相同，而本文的性能有大約20%的性能改善。

圖8 2014年1月份到七月份不同回歸模型下的平均殘差

4 結 語

針對影響回歸預測的上下文條件的動態性問題，據我們所知，本文首次提出動態隨機過程模型，并利用貝葉斯強化學習策略對動態上下文條件進行建模，同時理論證明了動態隨機過程模型的收斂條件，最后運用該模型對早高峰車流量進行短期預測。實驗結果顯示，相較于其他的灰色模型和其他回歸預測模型，本文所提出的模型在預測精度上都有一定的改善。本文將如何利用該方法進行城市交通疏導作為下一步的研究重點。