基于時(shí)序關(guān)聯(lián)規(guī)則挖掘的交通擁堵預(yù)測(cè)研究

喬春凱+++趙佳文

摘 要：交通擁堵造成的時(shí)間延誤和能源浪費(fèi)給社會(huì)帶來(lái)了巨額的經(jīng)濟(jì)損失并嚴(yán)重影響了居民的生活環(huán)境，是當(dāng)前亟需解決的重要問題。現(xiàn)有的交通擁堵預(yù)測(cè)方法并沒有考慮到交通流量的時(shí)序性，因而不能很好地適應(yīng)復(fù)雜的交通情況。針對(duì)這一背景，提出了一種基于遺傳算法的時(shí)序關(guān)聯(lián)規(guī)則挖掘的方法，并通過對(duì)挖掘出的時(shí)序關(guān)聯(lián)規(guī)則進(jìn)行分類來(lái)預(yù)測(cè)交通擁堵。實(shí)驗(yàn)結(jié)果表明，本方法能夠準(zhǔn)確有效地對(duì)交通擁堵事件進(jìn)行預(yù)測(cè)，能夠很好地適用于復(fù)雜的交通擁堵狀況。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；交通擁堵預(yù)測(cè)；遺傳算法；數(shù)據(jù)挖掘

引言

目前，城市交通擁堵已經(jīng)成為我國(guó)各大中城市正在面臨的通病，因其造成的時(shí)間延誤和能源浪費(fèi)已給社會(huì)帶來(lái)了巨大的經(jīng)濟(jì)損失，對(duì)復(fù)雜的交通狀況進(jìn)行預(yù)測(cè)是當(dāng)前亟需解決的重要難題。常見的預(yù)測(cè)交通擁堵的方法主要是基于各類數(shù)學(xué)模型并且大多只對(duì)單個(gè)時(shí)刻進(jìn)行預(yù)測(cè)，由于交通系統(tǒng)復(fù)雜多變的特性，這類方法往往考慮到的參數(shù)并不全面，同時(shí)沒有考慮到交通擁堵狀況的時(shí)序性。

近年來(lái)，許多人開始致力于智能交通系統(tǒng)的研究，提出多種交通擁堵預(yù)測(cè)方法。文獻(xiàn)[1]中，使用了多元線性回歸模型，其具有實(shí)現(xiàn)起來(lái)容易且理論基礎(chǔ)成熟等優(yōu)點(diǎn)，但是該模型對(duì)不同交通狀況的適應(yīng)度較差。文獻(xiàn)[2]中，F(xiàn)ahmy M.F.和Ranasinghe D.N.等人提出了一種使用排隊(duì)模型從而對(duì)交通狀態(tài)進(jìn)行判別的算法。文獻(xiàn)[3]通過人工神經(jīng)網(wǎng)絡(luò)模型進(jìn)行交通擁堵預(yù)測(cè)，這種方法具有很強(qiáng)的學(xué)習(xí)能力，但對(duì)數(shù)據(jù)量的需求過于龐大，當(dāng)交通系統(tǒng)數(shù)據(jù)不足時(shí)，預(yù)測(cè)結(jié)果不盡如人意。文獻(xiàn)[4]采用了ARIMA模型，能夠較好地體現(xiàn)出交通流量的非線性特征，但當(dāng)系統(tǒng)中出現(xiàn)交通事故等突發(fā)性事件時(shí)，會(huì)使模型運(yùn)算效率降低。

在實(shí)際的交通系統(tǒng)中，各個(gè)路段發(fā)生擁堵往往遵循一定因果關(guān)系，同時(shí)考慮到交通擁堵的時(shí)序性，提出一種基于遺傳算法的時(shí)序關(guān)聯(lián)規(guī)則挖掘的方法，挖掘出各個(gè)路段發(fā)生擁堵事件的潛在的規(guī)律，并通過將挖掘出的關(guān)聯(lián)規(guī)則進(jìn)行分類，以達(dá)到預(yù)測(cè)交通擁堵的目的，為提升交通系統(tǒng)整體性能提供前提保證。

1 問題分析

擁堵等級(jí)劃分（一）：

在實(shí)際路網(wǎng)中，道路的車輛密度是評(píng)價(jià)該條路的擁堵等級(jí)的重要參數(shù)。車輛密度由道路長(zhǎng)度，平均車長(zhǎng)，平均車間距，車道數(shù)以及車輛總數(shù)等參數(shù)共同決定。

車輛密度計(jì)算公式如下：

公式（1）中，D為車輛密度，N為當(dāng)前道路上的車輛總數(shù)，l和s分別為平均車長(zhǎng)與平均車間距，L為當(dāng)前道路的長(zhǎng)度，n為當(dāng)前道路的車道數(shù)。

根據(jù)道路的車輛密度，本文將擁堵等級(jí)劃為三個(gè)等級(jí)，1級(jí)為通暢，2級(jí)為輕微擁堵，3級(jí)為嚴(yán)重?fù)矶?，擁堵等?jí)及密度閾值見表1。

2 時(shí)序關(guān)聯(lián)規(guī)則挖掘

2.1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則就是在一個(gè)數(shù)據(jù)集中發(fā)現(xiàn)不同事務(wù)彼此之間的相關(guān)性，其兩個(gè)最重要的約束參數(shù)，一個(gè)是支持度（Support），表示規(guī)則出現(xiàn)的頻率程度，另一個(gè)是置信度（Confidence），表示規(guī)則可靠性的程度。本課題中關(guān)聯(lián)規(guī)則如下所示：

可解讀為，當(dāng)滿足道路1五分鐘前輕微擁堵，以及道路2當(dāng)前時(shí)刻通暢的情況時(shí)，那么道路3在五分鐘后會(huì)發(fā)生嚴(yán)重?fù)矶隆?/p>

2.2 遺傳算法

為了適應(yīng)交通系統(tǒng)的高度復(fù)雜性和各種突發(fā)事件，傳統(tǒng)的利用數(shù)學(xué)模型的交通擁堵預(yù)測(cè)算法的實(shí)施困難性很大，而且難以加入時(shí)序關(guān)系，而交通擁堵事件的時(shí)序性又是有必要考慮的，所以本課題設(shè)計(jì)了一種利用遺傳算法來(lái)挖掘時(shí)序關(guān)聯(lián)規(guī)則的方法。

2.2.1 編碼

如圖1所示，遺傳算法的每個(gè)染色體由上下兩層結(jié)構(gòu)組成，其中上層為道路的擁堵程度，取值為1～3，分別對(duì)應(yīng)三個(gè)等級(jí)，下層為引入屬性type，type取值為0～2，代表其上層擁堵程度的類型，type為1和2的個(gè)數(shù)為定值，染色體的長(zhǎng)度與路網(wǎng)中道路的個(gè)數(shù)相對(duì)應(yīng)。

2.2.2 解碼

規(guī)定解碼出的規(guī)則的前提有且最多有三個(gè)，規(guī)則的結(jié)論有且只有一個(gè)，若染色體type=1的個(gè)數(shù)為a，type=2的個(gè)數(shù)為b，當(dāng)規(guī)則未添加時(shí)序時(shí)，每個(gè)染色體可解碼出的規(guī)則數(shù)為（A3a+A2a+A1a）*A1b條，當(dāng)規(guī)則添加時(shí)序時(shí)，規(guī)定規(guī)則取三個(gè)時(shí)刻，分別為t1，t2，t3，相鄰兩間隔相差300秒，t2為當(dāng)前時(shí)刻，前提可為t1或t2時(shí)刻，結(jié)論只能為t3時(shí)刻，則每個(gè)染色體可解碼出的規(guī)則數(shù)為（A3a*8+A2a*4+A1a*2）*A1b條。

2.2.3 交叉

若兩個(gè)父染色體的第i 位上層屬性分別為L(zhǎng)ix，Liy，子染色體的第i位上層屬性為L(zhǎng)iz，當(dāng)進(jìn)行交叉操作時(shí)，子染色體的每一位的Liz，由隨機(jī)從對(duì)應(yīng)的Lix和Liy中選擇一個(gè)遺傳而來(lái)。

若每個(gè)染色體下層屬性為2和1的個(gè)數(shù)分別為x個(gè)和y個(gè)，記錄兩個(gè)父染色體所有下層屬性為2的位置，則子染色體下層屬性在這些位置中隨機(jī)選擇x個(gè)設(shè)置為2，記錄兩個(gè)父染色體所有下層屬性為1的位置，若子染色體下層屬性已經(jīng)設(shè)置為2，則排除該位置，子染色體下層屬性在其余位置中隨機(jī)選擇y個(gè)設(shè)置為1，其余位置都為0，以確保子染色體與父染色體下層不同類型屬性個(gè)數(shù)分別相同。

2.2.4 變異

染色體在發(fā)生突變時(shí)，上層屬性的每一位會(huì)變化成其它擁堵程度，例如2會(huì)變成1或3，而不會(huì)停留在2。

若父染色體下層屬性為2和1的個(gè)數(shù)分別為x個(gè)和y個(gè)，記錄父染色體下層屬性為2和1 的位置，則子染色體在這些位置之外，隨機(jī)選取x位突變?yōu)?，隨機(jī)選取y位突變?yōu)?，其余位置都為0，以確保子染色體與父染色體下層不同類型屬性個(gè)數(shù)分別相同。變異操作如圖3所示：

2.2.5 選擇

通過Fitness函數(shù)，對(duì)種群中每個(gè)染色體進(jìn)行評(píng)價(jià)，在每輪進(jìn)化過程中利用輪盤賭方法選擇出新的子代，該輪子代作為下一輪進(jìn)化的父代，這樣持續(xù)進(jìn)化下去。Fitness函數(shù)如下所示：

其中，r為挖掘出的規(guī)則，R為染色體挖掘出的所有規(guī)則的集合，x2（r）為規(guī)則r的卡方值，recov為規(guī)則新穎程度，如果該規(guī)則是一條新規(guī)則，則給recov設(shè)置一個(gè)值，否則recov為0?？ǚ街悼梢员磉_(dá)數(shù)據(jù)樣本實(shí)際值與理論值的偏差程度，即兩個(gè)事務(wù)相關(guān)聯(lián)的程度，利用卡方值可以很好的評(píng)價(jià)規(guī)則的質(zhì)量。卡方值越高則說明該規(guī)則的前提和結(jié)論關(guān)聯(lián)程度越過。

3 分類預(yù)測(cè)

將已挖掘出的關(guān)聯(lián)規(guī)則按結(jié)論擁堵程度分成3類，分別為1，2，3，即通暢，輕微擁堵，嚴(yán)重?fù)矶隆７诸悤r(shí)并非只用置信度高的規(guī)則，而是利用與待分類數(shù)據(jù)匹配成功的規(guī)則進(jìn)行計(jì)算，則分類過程如下所示：

3.1 獲取Rk

獲取交通數(shù)據(jù)之后，分別與每一類里的所有規(guī)則的前提進(jìn)行匹配，Rk為匹配成功的規(guī)則的集合。

3.2 計(jì)算每一類的Creditk

其中，Confidencer是規(guī)則r的置信度，Creditk是在類別k中，所有匹配成功的規(guī)則的置信度的和。

3.3 計(jì)算每一類的Scorek

其中，Totalk是類別中包含的規(guī)則的數(shù)量，Scorek是計(jì)算出的評(píng)價(jià)值。

3.4 分類

在得到每一類的Scorek后，則認(rèn)為分類結(jié)果就是Scorek值最高的那一類。

4 仿真實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)環(huán)境：

樣本數(shù)據(jù)收集工作來(lái)源于開源軟件SUMO仿真器，使用Java語(yǔ)言以及MySQL數(shù)據(jù)庫(kù)進(jìn)行程序開發(fā)。

獲取道路的車輛擁堵程度之后，采用本文提出的方法進(jìn)行時(shí)序關(guān)聯(lián)規(guī)則挖掘。其中，每個(gè)種群包含10個(gè)染色體，遺傳算法中染色體的交叉率和變異率分別為80%和90%，設(shè)置的支持度閾值為5%，置信度閾值為60%，另外，評(píng)價(jià)每條規(guī)則過程中，如果該條規(guī)則為新規(guī)則，則設(shè)置recov為0.2。由于計(jì)算能力限制，實(shí)驗(yàn)設(shè)置每個(gè)染色體下層屬性有5位可以作為前提，有3位可以作為結(jié)論，在進(jìn)化過程中不斷將滿足條件的規(guī)則保存下來(lái)獲取滿足支持度和置信度的時(shí)序關(guān)聯(lián)規(guī)則之后，使用本文的方法進(jìn)行分類以達(dá)到預(yù)測(cè)的目的，最終使用獲得的規(guī)則中最后100條規(guī)則作為測(cè)試集，其余規(guī)則作為訓(xùn)練集的方式來(lái)對(duì)預(yù)測(cè)結(jié)果做出評(píng)價(jià)。表2分別記錄五次實(shí)驗(yàn)下獲取的規(guī)則數(shù)量以及預(yù)測(cè)正確率。

從上述結(jié)果來(lái)看，當(dāng)前預(yù)測(cè)準(zhǔn)確率平均值達(dá)到85.2%，當(dāng)規(guī)則個(gè)數(shù)較少時(shí)的準(zhǔn)確率與規(guī)則個(gè)數(shù)多時(shí)的準(zhǔn)確率有較大差距，分析其原因，可能是由于構(gòu)建分類器的樣本個(gè)數(shù)少，分類器構(gòu)建不夠完善的原因。第五次實(shí)驗(yàn)預(yù)測(cè)正確率相較第四次有所下降，分析其原因，可能是由于該次實(shí)驗(yàn)染色體進(jìn)化所得的規(guī)則普遍置信度較低的原因。由此也說明挖掘通過挖掘時(shí)序關(guān)聯(lián)規(guī)則時(shí)，應(yīng)注重挖掘置信度高的質(zhì)量好的規(guī)則，而不能僅僅關(guān)注規(guī)則的數(shù)量。

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

依據(jù)遺傳算法的進(jìn)化原理，并考慮在復(fù)雜多變的交通環(huán)境下，交通擁堵事件發(fā)生的時(shí)序關(guān)系，本文提出了一種基于時(shí)序關(guān)聯(lián)規(guī)則挖掘的交通擁堵預(yù)測(cè)方法。經(jīng)實(shí)驗(yàn)仿真證明，該方法準(zhǔn)確有效。

同時(shí)在研究過程中也面臨一些問題，當(dāng)路網(wǎng)中道路個(gè)數(shù)過多時(shí)，本方法會(huì)面臨計(jì)算能力不足，計(jì)算耗時(shí)過長(zhǎng)的問題。這需要后續(xù)提出更好的路網(wǎng)劃分方法以及采用MapReduce等大數(shù)據(jù)環(huán)境下的計(jì)算方法來(lái)加以解決。

參考文獻(xiàn)

[1]Rice J， Van Zwet E. A simple and effective method for predicting travel times on freeways[J]. Intelligent Transportation Systems IEEE Transactions on， 2004，5（3）：200-207.

[2]Fahmy M F， Ranasinghe D N. Discovering automobile congestion and volume using vanet's[C]// ITS Telecommunications， 2008. ITST 2008. 8th International Conference on. IEEE， 2008：367-372.

[3]DOUGHERTY M S， KIRBYHR， BOYLE R D. The use of neural networks to recognize and predict traffic congestion[J]. Traffic Engineering and Control，1993，34（6）：311-314.

[4]HORVITZE J， APACIBLE J， SARIN R， et al. Prediction，expectation， and surprise： Methods， designs， and study of a deployed traffic forecasting service[C]//Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence. Edinburgh： [s.n.]， 2005：275-283.

[5]Zhou H. Data mining and classification for traffic systems using genetic network programming[J]. Genetic Programming，2011.

[6]Martí， Nez-Ballesteros M， Martí， et al. An evolutionary algorithm to discover quantitative association rules in multidimensional time series[J]. Soft Computing， 2011，15（10）：2065-2084.

作者簡(jiǎn)介：?jiǎn)檀簞P（1992-），男，漢族，遼寧省瓦房店市，碩士，單位：沈陽(yáng)理工大學(xué)，信息科學(xué)與工程學(xué)院，研究方向：數(shù)據(jù)庫(kù)理論與信息系統(tǒng)。

趙佳文（1991-），男，滿族，吉林省蛟河市，碩士，單位：沈陽(yáng)理工大學(xué)，信息科學(xué)與工程學(xué)院，研究方向：數(shù)據(jù)庫(kù)理論與信息系統(tǒng)。