李紅星

(安徽新華學(xué)院 電子通信工程學(xué)院，合肥 230088)

隨著城市化的進展和汽車的日益普及，交通擁堵更加嚴重.出行者迫切需要了解未來某段時間內(nèi)某一路段的車流量情況，從而避開擁塞路段，選擇最快路徑.但交通廣播等形式的交通信息服務(wù)只能提供某些重點路段的實時車流量情況.依據(jù)實時的道路交通信息采用適當(dāng)?shù)姆椒L動預(yù)測未來某一段時間內(nèi)道路的車流量狀況，向出行者提供最佳行車路線，不僅可以幫助出行者避開擁塞路段，選擇最快路徑，又能均衡交通流.

交通流量預(yù)測存在多種方法.1960年Kalman[1]提出了卡爾曼濾波模型.1993年Vythotkaspc[2]提出了基于卡爾曼濾波理論的車流量預(yù)測模型[2]，計算結(jié)果較為令人滿意.1974年，Box和Jenkins提出了差分自回歸滑動平均模型ARIMA[3].1984年，Okutani等人[4]將ARIMA模型應(yīng)用到城市交通控制系統(tǒng)中.1999年，Williams等人[5]將ARIMA模型應(yīng)用在路段單點交通流量預(yù)測中.2017年，Yang等人[6]采用運用指數(shù)平滑法和多元回歸模型組合進行交通預(yù)測，得到了較好的預(yù)測效果.

人工神經(jīng)元網(wǎng)絡(luò)誕生于20世紀40年代.2017年Kang等人[7]提出了改進的布谷鳥搜索(cuckoo search,CS)算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的高速公路流量預(yù)測模型，預(yù)測結(jié)果較為令人滿意，但神經(jīng)網(wǎng)絡(luò)算法需要大量的訓(xùn)練數(shù)據(jù)集，當(dāng)訓(xùn)練數(shù)據(jù)集不足時，預(yù)測效果會很差.

2004年Sun等人[8]研究了在實際交通流數(shù)據(jù)有缺失的情況下，采用馬爾可夫鏈模型方法，把交通流看成是馬爾可夫鏈，轉(zhuǎn)移概率近似采用高斯混合模型，參數(shù)估計采用Competitive Expectation Maximum算法.2006年Simmons等人[9]提出了基于馬爾可夫概率模型的車輛路徑預(yù)測模型.2011年Jing Yuan等人[10]根據(jù)實時和歷史交通情況以及駕駛員駕駛行為，采用馬爾可夫鏈模型方法，提出了為駕駛員提供最快行車路徑的系統(tǒng).基于馬爾可夫鏈的預(yù)測一般為短距離的預(yù)測，這種預(yù)測的準(zhǔn)確率很高，但這種短距離預(yù)測難以更早地將信息發(fā)送給駕駛員，讓其有足夠的時間做出調(diào)整，并不適用于交通信息服務(wù).

目前，智能交通系統(tǒng)利用大量的先進的數(shù)據(jù)收集技術(shù)，采集到了大量的交通數(shù)據(jù)[11].這些海量的數(shù)據(jù)為建立車流量預(yù)測模型和使用車流量預(yù)測模型滾動預(yù)測車流量提供了數(shù)據(jù)基礎(chǔ).將交叉路口電子眼采集的數(shù)據(jù)轉(zhuǎn)換為車輛行駛路徑序列，對車輛行駛路徑序列進行序列模式挖掘，挖掘出車輛行駛路徑序列模式并生成路徑關(guān)聯(lián)規(guī)則庫.再將車輛當(dāng)前行駛路徑與關(guān)聯(lián)規(guī)則庫中的模式匹配，預(yù)測車輛將以多大概率到達下一路段，從而對路段的車流量進行合理預(yù)測與分析.

基于序列模式挖掘的車流量預(yù)測方法通過對多用戶的車輛行駛路徑序列進行挖掘，挖掘出車輛規(guī)律性的行駛路徑并生成普遍適用性的行駛路徑關(guān)聯(lián)規(guī)則，能有效地發(fā)現(xiàn)數(shù)據(jù)間的聯(lián)系，根據(jù)已有的數(shù)據(jù)預(yù)測未來發(fā)展趨勢.

1 相關(guān)定義

圖1 模擬交通路網(wǎng)

假設(shè)以一系列安裝了電子眼的交叉路口為節(jié)點構(gòu)成交通網(wǎng)絡(luò)，那么車輛行駛路徑可以用節(jié)點順序排列來表示.設(shè)計如圖1所示的模擬交通路網(wǎng)，在A-I的9個交叉路口均有電子眼采集數(shù)據(jù).

將電子眼采集的每條數(shù)據(jù)，以時間區(qū)間T為閾值劃分成多個行駛記錄，即如果同一輛車被相鄰兩路口電子眼檢測到的時間間隔超過了設(shè)定的時間閾值T，則認為是該車的兩次行駛記錄.將車輛的行駛記錄存入車輛行駛路徑序列數(shù)據(jù)庫中，如表1所示.

表1 車輛行駛路徑序列數(shù)據(jù)庫

定義1 設(shè)I={ik,k=1,2，…,n}是一個項目集合，項目ik表示道路節(jié)點即道路上安裝有電子眼的交叉路口.路徑序列是不同項目的有序排列，路徑序列S可以表示成S=〈I1,I2,…,In〉，Ij?I.

性質(zhì)1 路徑序列不存在同位項.即車輛不可能在同一時間經(jīng)過不同的兩個節(jié)點.

性質(zhì)2 路徑序列所含每兩個相鄰項目為道路相鄰兩節(jié)點.即不可能出現(xiàn)類似于〈B H〉這樣的車輛行駛路徑，因為車輛不可能經(jīng)過B節(jié)點后不經(jīng)過E節(jié)點而直接到達H節(jié)點.

定義2 一個路徑序列中任意個連續(xù)項目組成的序列稱為該路徑序列的子路徑序列.若路徑序列α為路徑序列β的子路徑序列，則稱路徑序列β包含路徑序列α.

定義3 路徑序列S在路徑序列數(shù)據(jù)庫的支持度為路徑序列數(shù)據(jù)庫中包含S的序列個數(shù)，記為Support(S).給定最小支持度ξ，如果路徑序列S在路徑序列數(shù)據(jù)庫中的支持度不低于ξ，則稱路徑序列S為路徑序列模式.

2 GSP算法改進

序列模式挖掘算法是由R.Agrawal和R.Srikant在文獻[12]中提出的.對序列模式的挖掘一般采用GSP算法[13]或者PrefixSpan算法[14].研究表明PrefixSpan算法在時間和空間上的執(zhí)行性能比GSP算法更優(yōu)，但GSP算法對于有約束條件的序列模式挖掘更適用[15]，車輛行駛路徑序列是典型的時間特征約束下的序列，所以GSP算法對車輛行駛路徑序列的序列模式挖掘更有效.

GSP算法的基本思想是首先第一次掃描序列數(shù)據(jù)庫中的所有序列得到1-序列模式L1，然后由k-序列模式Lk通過產(chǎn)生候選序列模式函數(shù)GenCandidate()產(chǎn)生候選k+1-序列Ck+1，然后再一次掃描序列數(shù)據(jù)庫中所有序列，統(tǒng)計候選k+1-序列Ck+1的支持度，滿足用戶設(shè)定的最小支持度的候選k+1-序列Ck+1即為k+1序列模式Lk+1，然后循環(huán)這幾步，直至產(chǎn)生不了新的序列模式.其中，產(chǎn)生候選序列模式函數(shù)GenCandidate()包含如下兩個步驟：

(1)連接：如果刪去某一個序列模式S1所包含的第一項與刪去某一個序列模式S2所包含的最后一項所得到的子序列是一樣的，則將S1與S2進行連接，即將S1的第一項添加到S2的最前面.

(2)修剪：如果某一個候選序列模式的所有子序列中有一個子序列不為序列模式，則這一個候選序列模式不可能是序列模式，將其刪掉.

從以上的描述可知，當(dāng)序列數(shù)據(jù)庫中包含的序列很多時或者用戶設(shè)定的最小支持度較小時，容易產(chǎn)生大量的候選2-序列[16].因此，如果能減少2-序列模式的生成個數(shù)進而減少數(shù)據(jù)庫掃描時間，則算法的性能將有所提高.本文依據(jù)性質(zhì)2改進原始GSP算法產(chǎn)生候選序列模式子過程GenCandidate()，對候選2-序列模式的生成方式進行限定，減少候選2-序列模式的個數(shù).產(chǎn)生候選序列模式子過程偽代碼如下：

GenCandidate(L)

參數(shù)L：被連接路徑序列模式長度

if(L==1)

如果1-路徑序列模式S1中的項目與1-路徑序列模式S2中的項目是相鄰節(jié)點，則可以將S1與S2進行連接，即將S2中的項目添加到S1中.

else

執(zhí)行原始GSP算法的產(chǎn)生候選序列模式函數(shù)中的連接步和修剪步.

returnCk+1；

以表1中的數(shù)據(jù)為例，令最小支持度為3.滿足最小支持度的1-序列模式為：〈A〉：3,〈B〉：4，〈C〉：4,〈D〉：6,〈E〉：13,〈F〉：6〈H〉：9,〈I〉：3.由1-路徑序列模式生成候選2-路徑序列模式時，只對相鄰交叉路口的1-路徑序列模式進行連接.如〈B〉路徑序列模式只和〈A〉、〈C〉、〈E〉相連接，形成候選2-路徑序列模式〈B A〉、〈B C〉、〈B E〉.這樣既可以減少候選2-路徑序列模式的個數(shù)，又可以產(chǎn)生具有實際意義的序列模式.

3 車流量預(yù)測模型

路徑序列模式反映的是車輛規(guī)律性的路線選擇.由路徑序列模式產(chǎn)生具有方向性的路徑關(guān)聯(lián)規(guī)則，規(guī)則的前件表示車輛已行駛的路徑序列，規(guī)則后件表示車輛將要行駛的路徑序列.

定義4 〈B E〉→〈H〉這條路徑關(guān)聯(lián)規(guī)則的置信度定義為路徑序列數(shù)據(jù)庫中包含路徑序列〈B E H〉的個數(shù)與包含路徑序列〈B E〉的個數(shù)之比.即conf(〈B E〉→〈H〉)=sup(〈B E〉 ∪〈H〉)/sup(〈B E〉)=3/4=75%.〈B E〉→〈H〉這條關(guān)聯(lián)規(guī)則的置信度表示正在BE路段上行駛的車輛到達EH路段的概率為75%.

當(dāng)最小支持度為3時，對表1的路徑序列數(shù)據(jù)庫采用改進的GSP算法進行序列模式挖掘得到路徑序列模式集，包含的序列模式有：〈A〉：3,〈B〉：4,〈C〉：4,〈D〉：6,〈E〉：13,〈F〉：6,〈H〉：9,〈I〉：3,〈B E〉：4,〈C F〉：3，〈D E〉：5,〈E H〉：9，〈F E〉：4，〈B E H〉：3，〈D E H〉：3,〈F E H〉：3,.

對路徑序列模式集中的每個長度不小于3的路徑序列模式生成路徑關(guān)聯(lián)規(guī)則并計算路徑關(guān)聯(lián)規(guī)則置信度，存入路徑關(guān)聯(lián)規(guī)則數(shù)據(jù)庫中.

假設(shè)交通流為自由流.在長度為L的路段上有連續(xù)行進的N輛車，其速度為V，由車流量的定義可知：

L路段上的車流量

(1)

由于本文研究對象為城市交通路網(wǎng)，可假設(shè)車輛在任意兩個相鄰交叉路口間的路段上勻速行駛，則可假設(shè)任意兩個相鄰交叉路口間的路段的任意截面的車流量相等.本文研究的車流量指的均為單向車流量.由車流量歷史數(shù)據(jù)得到如下函數(shù)：

t=f(Q1，Q2,…，Qn)

(2)

其中，t為L路段上車輛從路段起點到路段終點所需時間，Q1，Q2,…，Qn為與該路段相鄰路段上車流量.

假設(shè)T1時刻BE、DE、FE路段車流量為Q1BE、Q1DE、Q1FE,BE路段有m輛車，由公式(2)得當(dāng)BE、DE、FE路段車流量為Q1BE、Q1DE、Q1FE時，車輛從E點到H點所需時間為t1,查詢路徑關(guān)聯(lián)規(guī)則數(shù)據(jù)庫conf(〈B E〉→〈H〉)=C1=75%,由定義4知T1+t1時刻將有75%m輛車到達EH路段.

假設(shè)T2時刻BE、DE、FE路段車流量為Q2BE、Q2DE、Q2FE,DE路段有n輛車，由公式(2)得當(dāng)BE、DE、FE路段車流量為Q2BE、Q2DE、Q2FE時，車輛從E點到H點所需時間為t2,查詢路徑關(guān)聯(lián)規(guī)則數(shù)據(jù)庫conf(〈D E〉→〈H〉)=C2=60%,由定義4知T2+t2時刻將有60%n輛車到達EH路段.

假設(shè)T3時刻BE、DE、FE路段車流量為Q3BE、Q3DE、Q3FE,DE路段有q輛車，由公式(2)得當(dāng)BE、DE、FE路段車流量為Q3BE、Q3DE、Q3FE時，車輛從E點到H點所需時間為t3,查詢路徑關(guān)聯(lián)規(guī)則數(shù)據(jù)庫conf(〈F E〉→〈H〉)=C3=75%,由定義知T3+t3時刻將有75%q輛車到達EH路段.

則T=T1+t1=T2+t2=T3+t3時刻EH路段車流量

4 應(yīng)用實例

以圖1中模擬交通路網(wǎng)為例，假設(shè)當(dāng)前時刻BE路段車流量為50輛/分鐘，DE路段車流量為40輛/分鐘，F(xiàn)E路段車流量為30輛/min.〈B E〉→〈H〉這條路徑關(guān)聯(lián)規(guī)則的置信度conf(〈B E〉→〈H〉)=75%，conf〈D E〉→〈H〉這條路徑關(guān)聯(lián)規(guī)則的置信度conf(〈D E〉→〈H〉)=60%，〈F E〉→〈H〉這條路徑關(guān)聯(lián)規(guī)則的置信度conf(〈F E〉→〈H〉)=75%.則EH路段的車流量為QEH=50×75%+40×60%+30×75%=84輛/min.

5 結(jié)語

在深入研究GSP算法和車輛行駛路徑序列特點的基礎(chǔ)下，對傳統(tǒng)GSP算法的候選序列模式產(chǎn)生方式進行了改進，挖掘出車輛行駛路徑序列模式,并形成路徑序列關(guān)聯(lián)規(guī)則.在此基礎(chǔ)上，結(jié)合車流量歷史數(shù)據(jù)，建立了車流量預(yù)測模型.

[1] KALMAN R E，BUCY S.New results in linear filtering and prediction theory[J].Transaction of the ASME，Journal of Basic Engineering,1960,82(1)：35-45.

[2] VYTHOULKASPC.Alternative approaches to short term traffic forecasting foruse in driver information systems[M].Transportation and Traffic Theory.Else-vier Science Publishers,1993.

[3] BOX G E P，JENKINS G M，MACGREGOR J F.Some recent advances in forecasting and control-2[J].Journal of Applied Statistics，1974,23(2)：158-179.

[4] OKUTANI，LWAO，STEPHANEDES，et al.Dynamic prediction of traffic volume through kalman filtering theory[J].Transportation Research,1984,18(1)：1-11.

[5] WILLIAMS B M.Modeling and forecasting vehicular traffic flow as a seasonal stochastic time series process[D].Department of Civil Engineering University of Virginia，Charlottesville,1999.

[6] 楊亞杰，韓印，YANG Y J.基于組合模型的交通流量預(yù)測研究[J].物流工程與管理，2017(1)：80-82.

[7] 康亞男.CS優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的高速公路流量預(yù)測[J].公路，2017(5)：194-198.

[8] SUN S L，YU G Q，ZHANG C S.Short-term traffic flow forecast using sample Markov Chain method with incomplete data[C]∥IEEE Intelligent Vehicles Symposium,Proceedings,2004：437-441.

[9] SIMMONS R，BROWNING B，ZHANG Y，et al.Learning to predict driver route anddestination intent[C]∥proceedings of Intelligent Transportation Systems Conferencee,2006：127-132.

[10] JING Y,YU Z,XING X，et al.Driving with knowledge from the physical world[C]∥proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining.New York,USA,2011：316-324.

[11] LIU J，YU X，XU Z，et al.A cloud-based taxi trace mining framework for smart city[J].Software：Practice and Experience，2017，47(8)：1081-1094.

[12] AGRAWAL R,SRIKANT R.Mining sequential patterns[C]∥proceedings of 1994 International Conference of Very Large Data Bases.Santiago,Chile，1994：487-499.

[13] SRIKANT R，AGRAWAL R.Mining sequential pattern：Generations and performance improvement[C]∥proceedings of the 5th International Conference Extending Database Technology.Avignon,France,1996：3-17.

[14] PEI J，HAN J，PINTO H.PrefixSpan mining sequential patterns efficiently by prefix-projected pattern growth[J].IEEE Transactions on Knowledge & Data Engineering，2004,16(1)：1424-1440.

[15] YU X，LIU J，LIU X，et al.A MapReduce reinforced distributed sequential pattern mining algorithm[C]∥International Conference on Algorithms and Architectures for Parallel Processing.Springer，Cham，2015：183-197.

[16] 余嘯，馬傳香，李偉亮,等.基于 MapReduce 的序列模式挖掘算法[J].計算機應(yīng)用研究，2015(11)：3312-3314.