喬春凱+++趙佳文

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

關鍵詞：關聯規(guī)則；交通擁堵預測；遺傳算法；數據挖掘

引言

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

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

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

1 問題分析

擁堵等級劃分（一）：

在實際路網中，道路的車輛密度是評價該條路的擁堵等級的重要參數。車輛密度由道路長度，平均車長，平均車間距，車道數以及車輛總數等參數共同決定。

車輛密度計算公式如下：

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

根據道路的車輛密度，本文將擁堵等級劃為三個等級，1級為通暢，2級為輕微擁堵，3級為嚴重擁堵，擁堵等級及密度閾值見表1。

2 時序關聯規(guī)則挖掘

2.1 關聯規(guī)則

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

可解讀為，當滿足道路1五分鐘前輕微擁堵，以及道路2當前時刻通暢的情況時，那么道路3在五分鐘后會發(fā)生嚴重擁堵。

2.2 遺傳算法

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

2.2.1 編碼

如圖1所示，遺傳算法的每個染色體由上下兩層結構組成，其中上層為道路的擁堵程度，取值為1～3，分別對應三個等級，下層為引入屬性type，type取值為0～2，代表其上層擁堵程度的類型，type為1和2的個數為定值，染色體的長度與路網中道路的個數相對應。

2.2.2 解碼

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

2.2.3 交叉

若兩個父染色體的第i 位上層屬性分別為Lix，Liy，子染色體的第i位上層屬性為Liz，當進行交叉操作時，子染色體的每一位的Liz，由隨機從對應的Lix和Liy中選擇一個遺傳而來。

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

2.2.4 變異

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

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

2.2.5 選擇

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

其中，r為挖掘出的規(guī)則，R為染色體挖掘出的所有規(guī)則的集合，x2（r）為規(guī)則r的卡方值，recov為規(guī)則新穎程度，如果該規(guī)則是一條新規(guī)則，則給recov設置一個值，否則recov為0。卡方值可以表達數據樣本實際值與理論值的偏差程度，即兩個事務相關聯的程度，利用卡方值可以很好的評價規(guī)則的質量?？ǚ街翟礁邉t說明該規(guī)則的前提和結論關聯程度越過。

3 分類預測

將已挖掘出的關聯規(guī)則按結論擁堵程度分成3類，分別為1，2，3，即通暢，輕微擁堵，嚴重擁堵。分類時并非只用置信度高的規(guī)則，而是利用與待分類數據匹配成功的規(guī)則進行計算，則分類過程如下所示：

3.1 獲取Rk

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

3.2 計算每一類的Creditk

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

3.3 計算每一類的Scorek

其中，Totalk是類別中包含的規(guī)則的數量，Scorek是計算出的評價值。

3.4 分類

在得到每一類的Scorek后，則認為分類結果就是Scorek值最高的那一類。

4 仿真實驗及結果分析

實驗環(huán)境：

樣本數據收集工作來源于開源軟件SUMO仿真器，使用Java語言以及MySQL數據庫進行程序開發(fā)。

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

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

5 結束語

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

同時在研究過程中也面臨一些問題，當路網中道路個數過多時，本方法會面臨計算能力不足，計算耗時過長的問題。這需要后續(xù)提出更好的路網劃分方法以及采用MapReduce等大數據環(huá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.

作者簡介：喬春凱（1992-），男，漢族，遼寧省瓦房店市，碩士，單位：沈陽理工大學，信息科學與工程學院，研究方向：數據庫理論與信息系統(tǒng)。

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