一種基于頻繁序列匹配的交通狀態(tài)趨勢預測方法

杜 瑾 ，郝 珺 ，成菊芳

（1．長安大學 信息工程學院，陜西 西安 710064；2．西安鐵路局 陜西 西安 710054；3．陜西安達綜合性能檢測站 陜西 西安 710068）

交通狀態(tài)的辨識和短時預測是是智能交通系統(tǒng)（ITS）研究中的一個重要內(nèi)容，其研究受到廣泛關注。交通狀態(tài)辨識主要包括對交通流量變（交通流統(tǒng)計分布情況不變，但其分布參數(shù)發(fā)生變化）及質變（交通流參數(shù)的突變）的檢測以及交通流的預測[1]。而交通狀態(tài)又是一種不斷變化的動態(tài)過程，具有很大的隨機性和偶然性[2]。交通狀態(tài)的潛伏、發(fā)展和發(fā)生具有連貫性和相關性的特點[3]。因此，交通狀態(tài)的發(fā)生與它的過去和現(xiàn)狀緊密相關，就有可能通過對交通狀態(tài)歷史規(guī)律和當前現(xiàn)狀進行綜合分析，推測它的后期趨勢，為采取各種預防措施提供依據(jù)。

文中提出一種基于頻繁序列模式匹配的交通狀態(tài)預測解決思路：提出基于時間、車、路、環(huán)境等綜合因素的交通狀態(tài)序列模型，并以此為基礎采用序列模式挖掘的方法，研究交通狀態(tài)在時序、聚集、依賴等方面狀態(tài)變化規(guī)律；再進一步研究基于頻繁序列匹配的交通狀態(tài)趨勢預測機制。最后，將上述方法以及所生成的交通狀態(tài)序列模式在實際道路觀測數(shù)據(jù)中進行驗證。

1 交通狀態(tài)序列模型

序列模式的概念最早是由Agrawal和Srikant提出的[4-5]：給定一個由不同序列組成的集合，其中，每個序列由不同的元素按順序排列，每個元素由不同項目組成，同時給定一個用戶指定的最小支持度閾值，序列模式挖掘就是找出所有的頻繁子序列，即該子序列在序列集中的出現(xiàn)頻率不低于用戶指定的最小支持度閾值。

序列中的元素在本文中則對應于特定交通狀態(tài)指標，交通狀態(tài)的描述指標及方法較多[6]，如采用模糊評價，層次分析法等確定擁擠度等，一般將交通流量，占有率，行程速度，行程時間和延誤確定為交通狀態(tài)的主要衡量指標。本文提出一種基于時間、通行狀態(tài)、道路、天氣等多維參數(shù)的交通狀態(tài)模型，交通狀態(tài)模型可如下元組描述：

其中T為時間屬性，這里為僅考慮交通狀態(tài)采集的時間戳，時間戳格式可明確地區(qū)分季節(jié)（春夏秋冬）、工作時區(qū)（凌晨、上午、中午、下午、傍晚、夜晚、深夜，工作日、節(jié)假日）等信息。

C為道路通行狀態(tài)，國內(nèi)外研究劃分通行狀態(tài)的方包括時間占有率法、車輛速度法、道路密度法以及模糊聚類法，最終都將道路通行狀態(tài)分為3級：通暢、擁擠、阻塞[7]；

L為道路狀態(tài)，用道路id來描述，可識別道路的等級如車道數(shù)、最高最低限速等，也可識別不同道路間的連通關系，在研究交叉分流交通狀態(tài)趨勢預測將發(fā)揮作用；

W代表天氣狀態(tài)，可區(qū)分為晴、多云、霧、小雨、中雨、小雨、冰雪天氣等。

利用交通數(shù)據(jù)監(jiān)測系統(tǒng)，可獲取道路交通狀況數(shù)據(jù)，并以交通狀態(tài)中的時間戳為索引，構建原始的交通狀態(tài)序列模型 S=＜s1，s2，…sn＞，這里 si為連續(xù)的某個時間段內(nèi)采集的狀態(tài)點。之所以稱為原始交通狀態(tài)序列，是因為這種序列還需進行序列切分處理。

切分，是將長序列進行合理的分割，構造成若干較短的序列。假設采集周期為5分鐘，則一天內(nèi)記錄的交通狀態(tài)序列長度為（60÷5）×24=288。這樣長度的序列在后期的挖掘中不論是存儲還是計算將花費非常大的代價。此外，由于交通狀態(tài)是連續(xù)的采集，前后兩日首尾相接，如果不進行合理的切分，序列長度將會更長。由于交通狀態(tài)趨勢預測是為了提前獲知可能出現(xiàn)的擁擠或堵塞狀態(tài)，從而提前做出交通誘導或控制操作避免擁堵的發(fā)生，因此擁擠和堵塞狀態(tài)的出現(xiàn)趨勢更加受人關注。這里可在長時間的通暢狀態(tài)（交通事件發(fā)生除外）時間階段內(nèi)可設斷點進行序列切分。例如，晚上11點到凌晨5點為連續(xù)的通暢狀態(tài)，則在凌晨2點處設斷點，將連續(xù)的交通狀態(tài)序列分割為前后兩日的較短的狀態(tài)序列。進一步：設長時通暢的判定時間為閾值tf，若交通狀態(tài)序列中出現(xiàn)連續(xù)的通暢狀態(tài)，設保持時間為t，t＞tf，則在t/2處對該序列進行分割。閾值tf可根據(jù)道路的長度、寬度以及平均車速綜合計算而得。

至此，交通狀態(tài)序列庫得以建立。

2 交通流狀態(tài)序列匹配

交通流狀態(tài)序列匹配的目的是在頻繁交通流狀態(tài)序列模式庫中發(fā)現(xiàn)所有以當前交通流狀態(tài)序列為前綴的頻繁交通流狀態(tài)序列，從而獲得當前交通流狀態(tài)序列的潛在后續(xù)序列。這里先介紹交通狀態(tài)序列匹配的相似度計算方法。

設有兩條交通狀態(tài)序列 Si和 Sj，其中 Si=（si1，si2，...，sin）且Sj=（sj1，sj2，...，sjm）。

第一步，先進行長序列投影壓縮。

不失一般性，假設n≤m，即Si長度小于 Sj。將長序列 Sj向短序列Si投影壓縮，即將Sj中所有不屬于Si的元素刪除。經(jīng)投影壓縮后，Sj變形為其中壓縮比率為這里，將的長度標記為=t。這種長序列投影壓縮變形不需要保持Si的原子性（序列不可分割），但可以保證投影前后短序列Si所有元素在長序列Sj中的出現(xiàn)順序保持不變。其作用體現(xiàn)在：一方面縮短比較序列的長度，可適當提高比較效率；另一方面收斂序列匹配目標，使得序列比較只在具有共同狀態(tài)元素的子序列間進行。

第二步滑動窗口比較。

Si和Sj′的相似性比較通過滑動窗口的方式進行，這里以滑動窗口的尺寸等于Si和Sj′中的較短序列的長度，標記為sizew=min（n，t），則被比較的序列，再次不失一般性，設 n≤t，（Si的長度小于等于 Sj′）。 因此，Si設為比較序列，且窗口尺寸為n，如圖2所示，在T時刻，Si和落入滑動窗口的 Sj′的子序列（記為sT）進行比較。

如圖1所示，初始比較由Si的末位和Sj′的首位開始；而在圖3中，終止時的比較位置為Si的首位和Sj′的末位。為了保證長序列中的每一個元素都被等次數(shù)的比較，給Sj′分別加上特殊序列 Sh=（0，0，...，0）作為補長前綴和補長后綴。

圖1 初始比較（T=1）Fig.1 Initial matching（T=1）

圖2 T時刻比較（T=t）Fig.2 Matching at t moment（=t）

圖3 末次比較（T=t+n-1）Fig.3 Final matching （T=t+n-1）

其中Sh=sizew-1，且 Sh的任意元素都不屬于 Si，即 Sh∩Si=?。設滑動窗口步長為1，Si和ST總共比較了t+n-1次。

在每次比較中，Si和sT的相似距離計算公式如下：

其中，Si（k）與 ST（k）分別是序列 Si與 ST中的第 k 個元素。 如果 Si（k）=ST（k），則 e（Si（k），ST（k））=1，否則 e（Si（k），ST（k））=0。

隨著T的變化，尋找窗口滑動過程中的Si和ST相似距離最大值，除以Si與Sj′間較長序列的長度，即為Si與Sj′間的相似度。

第三步，相似度計算。

Si和 Sj′相似度乘以 Sj壓縮為 Sj′的壓縮比率，即為 Si和 Sj的最終相似度。因此，相似度計算公式如下：

例如，有兩條序列：S1=（a，b，c）和 S2=（a，d，b，e，b，c）

首先，對其中的長序列 S2進行投影壓縮，變形為 S2′=（a，b，b，c）。

然后，進行滑動窗口序列比較，算得S1和S2′間的相似度E（S1，S2′）=2/4。

最后可得S1與S2間的相似度為

3 交通狀態(tài)序列匹配

基于以上序列相似度計算方法，論文進一步提出交通流狀態(tài)序列匹配算法：其思想是：如果某條交通流狀態(tài)序列在一定范圍內(nèi)具有一定普遍性，且當前交通狀態(tài)序列與該頻繁交通狀態(tài)序列的前綴子序列一致，則當前交通狀態(tài)的后期演變也可能與該頻繁交通流狀態(tài)序列后綴一致。文獻[8]深入討論了頻繁序列模式獲取的算法，本文不再贅述。這里，介紹交通流狀態(tài)序列匹配算法如下所示，其中，某條路段的交通流狀態(tài)序列集記為 Scurrent={S1，S2，…，Sl}，被比較的全局頻繁交通序列模式庫記為 FS={fs1，fs2，…，fsn}，θ為匹配判定閾值。 經(jīng)交通流狀態(tài)序列匹配后，獲得所有以Scurrent內(nèi)Si為前綴子序列的頻繁序列集FSm。

交通流狀態(tài)序列匹配算法的關鍵在于前綴匹配度函數(shù)prefixmatch（）的計算，和公式（4）介紹的序列相似度計算不同的是，這里僅考察Si作為fsj前綴的符合度，而前者是考察兩個序列完全符合的相似程度。因此，計算前綴匹配度時，要將Si在 fsj的方向上投影，得到 Si′，進而計算 S′作為前綴在 fsj′中的符合程度，再乘以投影比率σ，從而得出前綴匹配符合度。其過程描述如下：

Step1:Si在fsj的方向上投影，即刪除Si中所有不屬于fsj的元素，得到投影序列Si′。

Step2：獲得投影序列Si′在fsj中投影覆蓋區(qū)域，其中：

表1 交通狀態(tài)序列匹配算法Tab.1 The algorithm of traffic status sequence matching

設s為Si′中的最后一個元素

掃描fsj，獲得s在fsj中出現(xiàn)的最后位置l，

則fsj[1..l]即為S′在fsj上的投影覆蓋區(qū)；

在計算前綴匹配度要比較Si和fsj[1..l]的原因是：在進行后期的交通狀態(tài)趨勢預測時，我們認為，在一條頻繁出現(xiàn)的交通流狀態(tài)序列中，后綴序列往往是因為前綴序列元素的集體出現(xiàn)而發(fā)生的，作為前綴序列的子序列中總是不及整個前綴序列對后綴序列出現(xiàn)的影響大。例如，頻繁序列fs=（a，b，c，d），前綴序列 S=（b，c，f），S 在 fs上的投影為 S′=（b，c）。顯然，fs的前綴序列（a，b，c）對后綴序列（d）的影響必然大于（b，c）對（d）的影響。 因此我們通過計算（b，c，f）和整個前綴序列（a，b，c）的相似度來決定S對（d）出現(xiàn)的影響力度。

4 交通狀態(tài)趨勢預測

以匹配成功的頻繁交通流狀態(tài)序列集FSm為基礎，這里討論特定交通狀態(tài)序列的趨勢預測問題，即根據(jù)特定路段的當前交通流狀態(tài)序列和匹配出的頻繁序列集，預測可能發(fā)生的后續(xù)交通狀態(tài)集合及其趨勢度。 設 FSm=（S1，fs1，pm1），（S2，fs2，pm2），...，（Sk，fsk，pmk），交通狀態(tài)趨勢預測算法如表 2 所示。

這里，我們根據(jù)3條規(guī)則來計算交通狀態(tài)s的趨勢度大小，其中：

1）pmi為特定路段當前序列Si和匹配頻繁序列fsi的前綴匹配度，pmi越大，則Si對fsi的后綴序列的影響就越大，因此fsi后綴序列中的交通狀態(tài)就越有可能出現(xiàn)；

2）spt（fsi）為頻繁序列 fsi的支持度，spt（fsi）越大，則 fsi就越頻繁，因此fsi后綴序列中的交通狀態(tài)就越有可能出現(xiàn)；

3）co（j）為后綴序列中第j個交通狀態(tài)結點出現(xiàn)的趨勢系數(shù)，在頻繁序列fsi中，作為后綴序列的交通狀態(tài)結點離Si越近，就越有可能出現(xiàn)。

BSp經(jīng)過排序后，可將交通狀態(tài)候選集中的Top n個預測交通狀態(tài)及其可能出現(xiàn)的趨勢度傳遞給交通監(jiān)控系統(tǒng)，從而為智能化道路交通監(jiān)控與疏導提供支持。

表2 交通狀態(tài)趨勢預測算法Tab.2 The algorithm of traffic status predicting

5 結束語

文中提出頻繁序列匹配的交通狀態(tài)趨勢預測方法能夠根據(jù)交通狀態(tài)變化依賴關系，通過頻繁序列挖掘獲得在道路交通狀態(tài)變化的內(nèi)在規(guī)律，并采用序列匹配算法對實時交通狀態(tài)趨勢進行預測。通過實際交通狀態(tài)數(shù)據(jù)測試驗證該方法具有較高的準確性和實時性，具有實用價值。

[1]王曉原，劉海紅，譚德榮.交通流量變模式辨識的非參數(shù)概率變點模型[J].系統(tǒng)工程，2006，24（8）：19-22.WANG Xiao-yuan，LIU Hai-hong，TAN De-rong.A nonparametric probability change-point for traffic flow recognition[J].Systems Engineering，2006，24（8）:19-22.

[2]盛春陽，張元.基于貝葉斯網(wǎng)絡模型的交通狀態(tài)預測[J].山東交通科技，2007（4）:4-6.SHENG Chun-yang，ZHANG Yuan.Traffic state prediction method based on bayesian network model[J].Shandong Traffic Tehnology，2007（4）:4-6.

[3]S.，B.L..Comparison of parametric and nonparametric models for traffic flow forecasting[J].Transportation Research， 2002，10（4）:303-321.

[4]呂靜，王曉峰.序列模式圖及其構造算法[J].計算機學報，2004，27（6）:782-788.LV Jing，WANG Xiao-feng.Sequential patterns graph and its Construction Algorithm[J].2002，10（4）:303-321.

[5]Agrawal Rakesh， S.R.， Mining sequential patterns[C].In Proceedings of the 11th International Conference on Data Engineering， Taipei.China，1995:3-14.

[6]KONGQing-jie.An Approach to Urban Traffic State Estimation by Fusing Multisource Information[J].IEEE Transactions on Intelligent Transportation Systems，2009，10（3）:499-511.

[7]李強，葛乾，繆立新.城市道路路段旅行時間的特性分析[J].交通運輸系統(tǒng)工程與信息，2011，11（5）:107-109.LI Qiang，GE Qian，MIAO Li-xin.Property analysis of urban road travel time[J].Journal of Transformation Systems Engineering and Information Technology，2011，11（5）:107-109.

[8]DUJin，ZHAOXiang-mo，HAOJun.Theresearch on traffic flow pattern clustering based on frequent sequences similarity[J].Information Technology Journal，2012，11（3）:334-338.