杜 瑾 ，郝 珺 ，成菊芳

（1．長(zhǎng)安大學(xué) 信息工程學(xué)院，陜西 西安 710064；2．西安鐵路局 陜西 西安 710054；3．陜西安達(dá)綜合性能檢測(cè)站 陜西 西安 710068）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第一步，先進(jìn)行長(zhǎng)序列投影壓縮。

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

第二步滑動(dòng)窗口比較。

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

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

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

圖2 T時(shí)刻比較（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=?。設(shè)滑動(dòng)窗口步長(zhǎng)為1，Si和ST總共比較了t+n-1次。

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

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

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

第三步，相似度計(jì)算。

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

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

首先，對(duì)其中的長(zhǎng)序列 S2進(jìn)行投影壓縮，變形為 S2′=（a，b，b，c）。

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

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

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

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

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

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

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

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

設(shè)s為Si′中的最后一個(gè)元素

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

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

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

4 交通狀態(tài)趨勢(shì)預(yù)測(cè)

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

[1]王曉原，劉海紅，譚德榮.交通流量變模式辨識(shí)的非參數(shù)概率變點(diǎn)模型[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]盛春陽(yáng)，張?jiān)?基于貝葉斯網(wǎng)絡(luò)模型的交通狀態(tài)預(yù)測(cè)[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]呂靜，王曉峰.序列模式圖及其構(gòu)造算法[J].計(jì)算機(jī)學(xué)報(bào)，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]李強(qiáng)，葛乾，繆立新.城市道路路段旅行時(shí)間的特性分析[J].交通運(yùn)輸系統(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.