王鳳琴 盧官明 柯亨進

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

0 引 言

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

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

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

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

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

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

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

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

1 動態(tài)隨機過程模型

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

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

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

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

(1)

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

(2)

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

圖1 動態(tài)隨機過程模型的迭代更新過程

定義2(動態(tài)隨機過程) 對于隨機過程{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) 均值函數(shù)是條件和時間的函數(shù)，也稱為條件期望。即：

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

(3)

2 自適應參數(shù)尋優(yōu)灰色加權(quán)預測

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

圖2 系統(tǒng)架構(gòu)圖

2.1 懲罰因子選擇

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

εi=|predicti-reali|/reali

(4)

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

2.2 最大信息系數(shù)

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

給定有序?qū)傩詫Φ挠邢藜螪，每一個屬性都有x方向和y方向兩個方向的成分。將x成分以網(wǎng)格方式分割成x網(wǎng)格，同理，將y部分分割為y網(wǎng)格，整個網(wǎng)格稱為x×y網(wǎng)格。每個子格的互信息計算如下：

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

(5)

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

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

(6)

對于無限數(shù)據(jù)，MIC定義為：

(7)

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

(8)

式中:ω(1)

MIC可以有效度量大量數(shù)據(jù)集各屬性之間關(guān)聯(lián)強度，具有如下性質(zhì)：

? 有界性：所有MIC值都落在[0,1]區(qū)間內(nèi)。

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

? 穩(wěn)健性：MIC不受異常值的影響，而相關(guān)系數(shù)易受異常值的影響。

2.3 動態(tài)特征融合權(quán)值計算

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

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

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

(9)

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

(10)

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

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

2.4 屬性加權(quán)灰色模型

2.4.1 灰色模型

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

2.4.2 權(quán)值計算

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

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

(11)

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

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

(12)

2.4.3 加權(quán)灰色模型

通常，統(tǒng)計模型總是可以表示為：

Y=Xβ+ε

(13)

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

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

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

(14)

式中:Σ是對角陣，也是本文中的權(quán)值矩陣：

(15)

依據(jù)最小二乘法，其參數(shù)β的評估值如下：

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

(16)

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

(au)T=(BTWB)-1BT

(17)

2.5 預測算法

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

算法1整體框架

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

輸出：預測向量y

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

訓練閾值、步長和順序

計算融合步長

建構(gòu)屬性加權(quán)灰色模型

算法2DSPM算法

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

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

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

循環(huán):在所有之前的時間點

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

裝載第i個動作

裝載第i個觀察值

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

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

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

結(jié)束循環(huán)

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

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

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

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

3.1 特征提取

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

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

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

圖4 顯示了不同逆序數(shù)與殘差之間的關(guān)系

3.2 步長與順序訓練

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

ε(p(cp|cc))

(18)

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

圖5 不同時間點下不同歷史步長的擊中概率的轉(zhuǎn)移概率圖

3.3 結(jié)果比較

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

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

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

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

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

3.3.2 與其他回歸模型的比較

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

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

4 結(jié) 語

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