基于多變量決策樹交通事件持續(xù)時間預測模型

向紅艷，金 明

(1. 重慶交通大學 交通運輸學院，重慶 400074；2. 重慶工業(yè)職業(yè)技術學院 車輛工程學院，重慶 401120)

?

基于多變量決策樹交通事件持續(xù)時間預測模型

向紅艷1，金 明2

(1. 重慶交通大學 交通運輸學院，重慶 400074；2. 重慶工業(yè)職業(yè)技術學院 車輛工程學院，重慶 401120)

基于粗集理論和決策樹方法，建立了交通事件持續(xù)時間的多變量決策樹預測模型。通過分析交通事件的屬性特點，運用粗集理論中的屬性約簡方法，確定了交通事件的核心屬性；運用等價關系相對泛化原理構造了多變量組合檢驗，并根據(jù)變量依賴度確定了最優(yōu)變量組合；以多變量組合判據(jù)代替單變量判據(jù)建立了決策樹模型，利用決策樹高度和節(jié)點樣本數(shù)對樹的規(guī)模進行控制，優(yōu)化了決策樹結構。實例應用表明，該模型對交通事件持續(xù)時間的分類和預測能力較強，預測精度較高。

交通工程；持續(xù)時間；粗糙集；多變量決策樹；預測

0 引 言

高速公路交通事件管理是高速公路日常運營管理與控制的重要組成部分。隨著我國高速公路運營里程的迅猛增長，各種原因導致的高速公路交通事件數(shù)量日益增多。高速公路交通事件造成的人員傷亡和經濟損失巨大，其社會影響十分顯著。高速公路交通事件主要包括交通事故、自然災害以及其他突發(fā)事件等。交通事件的持續(xù)時間是高速公路管理部門和道路使用者十分關注的指標，是實施交通事件管理和應急救援的重要依據(jù)。持續(xù)時間預測結果有利于幫助高速公路管理者快速制定決策以減輕交通事件造成的擁堵、出行延誤，減少二次事故發(fā)生率，降低人員傷亡和財產損失。

關于交通事件持續(xù)時間的預測方法主要有：回歸分析法[1-2]，概率分布法[3-5]，單變量決策樹法[6-7]。交通事件持續(xù)時間的影響因素主要包括交通事件類型、發(fā)生時間、地點、占道、人員傷亡、車輛、環(huán)境、救援、天氣等，由于上述影響因素相互作用及耦合關系十分復雜，造成現(xiàn)有方法的預測精度十分有限。因此，決策樹方法是數(shù)據(jù)挖掘中應用最廣泛的方法之一。

決策樹采用優(yōu)先策略自上而下進行不斷細分和輸出預測結果。劉偉銘，等[6]建立了不同類別交通事件的單變量決策樹模型，提出了基于單因素顯著性判據(jù)的節(jié)點分類判別方法，分別預測了火災、故障、人員傷亡等類別交通事件的持續(xù)時間；C．Zhan，等[7]提出了基于M5P方法的單變量決策樹模型，該方法通過整合決策樹法與回歸分析法，采用不同分類情況下多個多元線性回歸模型計算交通事件的持續(xù)時間，提高了預測精度，其結果優(yōu)于簡單決策樹模型。然而，上述模型均以單以變量作為決策判據(jù)建立模型，導致所建立的決策樹判別規(guī)則十分復雜，容易造成樹形龐大，計算效率低。同時，單變量決策樹忽略了要素之間的相關性，還有可能造成變量的重復檢驗，影響預測效果?；诖?，筆者結合粗集理論中的屬性約簡和等價關系泛化原理，建立基于粗糙集的多變量決策樹預測模型，以改進交通事件持續(xù)時間的預測效果。

1 交通事件的持續(xù)時間特征

1.1 持續(xù)時間的定義

交通事件持續(xù)時間可以分為4個階段：①報警時間，是指從交通事件發(fā)生到管理人員接到報警的時間；②響應時間，是指接到報警開始一直到救援隊伍到達現(xiàn)場之間經歷的時間；③現(xiàn)場處理時間，是指救援隊伍現(xiàn)場搶救傷員，清理障礙的時間；④恢復交通事件，是指從現(xiàn)場清理完畢到交通完全恢復正常的時間。

但現(xiàn)有資料大多數(shù)無法統(tǒng)計高速公路交通事件發(fā)生后到報警前的這一段時間，現(xiàn)場清理完成到交通狀態(tài)恢復正常的時間也無法準確統(tǒng)計。因此，筆者將研究的高速公路交通事件持續(xù)時間確定為：以高速公路管理部門接到報警為開始時間，以交通事件現(xiàn)場處理完畢工作人員全部撤離為結束時間。這一時間主要包括響應時間和現(xiàn)場處理時間，不包括報警時間和恢復交通事件，交通事件持續(xù)時間與事件類別、嚴重程度、發(fā)送地點、發(fā)生時間有關。交通事件的持續(xù)過程見圖1。

圖1 交通事件的持續(xù)過程

1.2 交通事件持續(xù)時間的特征

根據(jù)我國高速公路交通事故的統(tǒng)計資料進行分析，結果表明：高速公路交通事件的持續(xù)時間分布具有一定的規(guī)律性。其中持續(xù)時間短(<30 min)的交通事件占絕大多數(shù)，隨著持續(xù)時間增長，交通事件數(shù)量呈現(xiàn)逐漸減少的趨勢。根據(jù)K．Ozbay，等[8]的研究，交通事件的持續(xù)時間總體上近似服從對數(shù)正態(tài)分布，具有向左偏移的特征。不同類別的交通事件持續(xù)時間具有不同的均值和變異系數(shù)，其變化特征差異較大；同一類別相同嚴重程度的交通事件，其持續(xù)時間總體上服從呈正態(tài)分布[6]。交通事件的持續(xù)時間的影響因素十分復雜，不僅與交通事件本身的性質有關，還與救援實施的進度有關，準確預測交通事件持續(xù)時間，有助于緩解交通事件造成的出行延誤、交通擁堵等問題。

2 基于粗集的多變量決策樹模型

粗集理論具有處理模糊性、不確定和不完整數(shù)據(jù)的強大能力[9-11]。筆者嘗試建立一種基于粗集理論與決策樹算法整合的多變量組合預測模型。其具體方法為：在傳統(tǒng)方法基礎上，運用粗集中的屬性約簡方法，構造決策變量相對核；在建立決策樹過程中，允許兩個或多個屬性變量的組合檢驗，根據(jù)等價關系泛化原理，產生更快速、有效的決策判據(jù)；通過限制節(jié)點記錄數(shù)和樹的最大高度，對決策樹的結構進行修剪和優(yōu)化。多變量決策樹的優(yōu)點在于考慮了變量之間的相關性，通過變量組合降低了算法的復雜性，減小了樹的規(guī)模，提高了計算速度。

2.1 交通事件屬性變量的約簡

設交通事件樣本集合為U，x表示任意交通事件樣本，x∈U。設表示描述交通事件的屬性集合為R={R1，R2，…，Rn}。為消除屬性集合中不必要的冗余屬性，運用屬性約簡算法構造屬性變量相對核。

對任意屬性Ri，設U/Ri為根據(jù)Ri的取值對U進行的一個劃分，將序對(U，Ri)稱為一個近似空間。設[x]Ri為包含x的Ri的等價類，對任意集合X∈U，定義以Ri為基礎的集合X的上、下近似集合為：

(1)

設T表示決策屬性(即持續(xù)時間)，U/T表示根據(jù)決策變量T的取值對U進行的劃分。令P表示約簡后的核心屬性集，則P的T正區(qū)域為：

(2)

式中：IND(P)，IND(T)分別表示P，T中元素的交集。對集合R中的元素進行逐一檢驗，如果：

POSIND(P)[IND(T)]=POSIND(P-Ri)[IND(T)]

則Ri為不必要的屬性，予以剔除。取R中剩下元素得到交通事件屬性相對核P：

P=∪{Ri∈R:POSIND(P)[IND(T)]≠

POSIND(P-Ri)[IND(T)]}

(3)

2.2 構建多變量組合檢驗

設交通事件的持續(xù)時間用T表示，T為決策屬性。按照T的取值將持續(xù)時間分為h級，T={T1，T2，…，Th}。根據(jù)T對U進行劃分：U/T={Yt}，t=1,2，…，h；滿足T(Yt)=Tt。從P中選擇任意k個變量，利用等價關系相對泛化原理建立多變量組合檢驗C，見式(4)。

C=P1∧P2∧…∧Pk，(k=1，2，…，m)

(4)

以C對U進行新的劃分，得：

U/IND(C)={X1，X2，…，Xr}

(5)

令Z={Z1，Z2，…，Zh，Z(h+1)}，對任意Xj∈U/IND(C) (j=1，2，…，r)進行檢驗，判斷其是否屬于U/T中的元素；若Xj?Yt(t=1，2，…，h)，將Xj的元素歸入Zt，將不屬于任何U/T子集的元素一起歸入集合Z(h+1)。Z即為根據(jù)變量組合C在U上確定的新的等價關系，是C相對于T的泛化。如式(6)、式(7)：

Zt=∪Xj∈U/IND(C){Xi;Xj∈Yt}，(t=1，2，…，h)

(6)

Z(h+1)=∪Xj∈U/IND(C){Xi;Xj?Yt,?t}

(7)

選擇依賴度最大的變量組合作為最優(yōu)組合，記為C*，見式(8)：

Card[POSCq(T)]/Card(U)，(q=1,2,…)

(8)

式中：γ(Cq,T)表示決策屬性T對變量組合Cq的依賴度；Card(U)表示集合U中的元素個數(shù)。

2.3 建立多變量持續(xù)時間決策樹

令N表示決策樹的節(jié)點；UN表示節(jié)點上的當前交通事件樣本集合；lN表示交通事件樣本個數(shù)。在建樹過程中通過限制樹的最大高度和每個節(jié)點的最少樣本數(shù)來控制樹的生長。令樹的最大高度為Nmax，節(jié)點必須包含的最少記錄數(shù)為lmin。以下是構建多變量決策樹的具體步驟。

1)創(chuàng)建決策樹根節(jié)點，N=1；

2)根據(jù)式(1)～式(3)對節(jié)點N上的當前樣本集合UN進行屬性約簡，得到屬性相對核PN；

3)采用式(4)、式(5)構造節(jié)點N的最優(yōu)多變量檢驗CN*。

4)用式(6)、式(7)計算等價關系Z，并為節(jié)點UN分配類別，共有(h+1)類；

5)分別計算子集Zi(i=1,2,…,h)所對應的持續(xù)時間；

6)判斷是否滿足條件：Nlmin，如果滿足，至7)，否則，至8)；

7)令N=N+1，UN=Z(h+1)，回2)；

8)結束，計算集合Z(h+1)所對應的持續(xù)時間。

其中，當決策樹葉節(jié)點上的交通事件集合為Zt時，對應的持續(xù)時間預測結果為Tt,t=1，2，…，h。當決策樹葉節(jié)點上的交通事件集合為Z(h+1)時，按照T的等級對Z(h+1)進行劃分，選擇Z(h+1)/T中元素最多的子集所對應的持續(xù)時間作為預測結果，具體見式(9)：

(9)

3 實例應用

采用某雙向4車道高速公路2012年全年的交通事件數(shù)據(jù)進行應用分析。所用數(shù)據(jù)來源于高速公路管理部門交通事件統(tǒng)計報表以及部分文本整理資料。案例包含有效組樣本數(shù)據(jù)833組，平均延誤時間為53 min，樣本數(shù)據(jù)80%用于決策樹構造， 20%用于預測效果驗證。

對描述交通事件的變量進行賦值和離散化處理。將持續(xù)時間T將分為5個等級，即：T={A，B，C，D，E}。其中：A(T≤30 min)，B(30 min300 min)，具體見表1。

表1 交通事件屬性描述及賦值

注：表中未列出交通事件的非核心屬性，包括：所屬公司、路段名稱、行車方向、車道數(shù)、涉及車輛總數(shù)、車型、聚眾人數(shù)、處置措施、二次事故、特殊路段等。

運用式(1)～式(3)對交通事件初始屬性集進行約簡，得到屬性相對核：P= (P1，P2，…，P11)，見表1。令決策樹最大高度Nmax=10，節(jié)點樣本數(shù)最小值lmin=15，節(jié)點多變量組合數(shù)k≤3。建立多變量決策樹如圖2，圖2中，橢圓形表示決策節(jié)點，括號內的數(shù)字表示當前訓練樣本數(shù)，長方形表示葉節(jié)點，括號內字母表示葉節(jié)點對應的持續(xù)時間等級，括號內的數(shù)字表示該葉節(jié)上的交通事件樣本數(shù)。

圖2 多變量決策樹結構

為評價模型的預測效果，選用預測準確率和誤報率作為評價指標。其中，預測準確率為模型可準確預測持續(xù)實際范圍的交通事件數(shù)與交通事件總數(shù)之比，誤報率為未能準確預測的交通事件數(shù)與事件總數(shù)之比，具體見式(10)、式(11)：

(10)

σ=1-μ

(11)

式中：μ為預測準確率；σ為誤報率；S為用于測試的交通事件總數(shù)；Sa為葉節(jié)點a上預測準確的交通事件數(shù)；w為葉節(jié)點總數(shù)。

運用構造的決策樹對驗證數(shù)據(jù)進行預測，按照持續(xù)時間等級對測試數(shù)據(jù)進行分組，各組驗證樣本的預測結果見表2。

表2 預測結果分析

表2的結果表明：多變量決策樹通過對核心屬性的組合，有利于快速分類和分級，預測平均準確率為77.25%。其中：對T≤30 min的交通事件預測準確率大于80%；對持續(xù)時間較長(120 min300 min)的交通事件預測準確率大于75%。由于持續(xù)時間本身具有隨機性，在更小時間范圍上的精確預測變得十分困難，持續(xù)時間30 min

與H．L．Chang，等[12]的預測效果相比較，結果見表3。由表3可見，與單變量決策樹比較，多變量決策樹的高度降低28.57%，葉節(jié)點數(shù)量減少40.74%，因此加快了交通事件的分類和分級運算速度。

表3 單變量、多變量決策樹的比較

4 結 語

利用粗糙集理論中的屬性約簡法和多變量構造檢驗方法，建立了具有較強分類和預測能力的多變量決策樹模型。該模型可有效避免交通事件初始屬性集合中冗余屬性的干擾，所建立的決策樹規(guī)模、結構更加合理。研究中發(fā)現(xiàn)交通事件持續(xù)時間的核心影響因素包括交通事件類別、是否涉及大貨車、車輛是否損壞、人員傷亡、占道、路產損失、地點、時間、天氣。交通事件的持續(xù)時間的變化范圍較大，多變量決策樹能真實反應交通事件持續(xù)時間的變化特征，可快速識別持續(xù)時間短、較短、中、長、較長的不同類別交通事件，具有較高的預測精度。由于樣本數(shù)量和描述交通事件的指標有限，筆者尚未結合區(qū)域社會經濟、交通管理水平對不同地區(qū)交通事件的持續(xù)時間進行分析，下一步將考慮上述因素的影響對這一問題進行研究。

[1] Garib A,Radwan A E,Al-Deek H.Estimating magnitude and duration of incident delays [J].Journal of Transportation Engineering,1997,123(6):459-466.

[2] Smith K W,Smith B L.Forecasting the Clearance Time of Freeway Accidents[D].Virginia:University of Virginia,2001.

[3] Nam D,Mannering F.An exploratory hazard-based analysis of highway incident duration[J].Transportation Research Part A:Policy and Practice,2000,34(2):85-102.

[4] Hojati A T,Ferreira L,Washington S,et al.Hazard based models for freeway traffic incident duration[J].Accident Analysis & Prevention,2013,52:171-181.

[5] 康國祥,方守恩.基于風險分析的交通事件持續(xù)時間預測[J].同濟大學學報:自然科學版,2012,40(2):241-245. Kang Guoxiang,Fang Shouen.A hazard-based analysis of traffic incident duration prediction[J].Journal of Tongji University:Natural Science,2012,40(2):241-245.

[6] 劉偉銘,管麗萍,尹湘源.基于決策樹的高速公路事件持續(xù)時間預測[J].中國公路學報,2005,18(1):99-103. Liu Weiming,Guan Liping,Yin Xiangyuan.Prediction of freeway incident duration based on decision tree[J].China Journal of Highway and Transport,2005,18(1):99-103.

[7] Zhan C,Gan A,Hadi M.Prediction of lane clearance time of freeway incidents using the M5P tree algorithm[J].Intelligent Transportation Systems,IEEE Transactions on,2011,12(4):1549-1557.

[8] Ozbay K,Kachroo P.Incident Management in Intelligent Transportation Systems [M].Boston,MA:Artech House,1999.

[9] 苗奪謙,王玨.基于粗糙集的多變量決策樹的構造方法[J].軟件學報,1997,8(6):425-431. Miao Duoqian,Wang Jue.Rough sets based approach from multivariate decision tree construction[J].Journal of Software,1997,8(6):425-431.

[10] 童世鑫,叢浩哲,陳雨人.高速公路交通事件清除時間模糊邏輯預測模型[J].重慶交通大學學報:自然科學版,2011,30(1):85-88. Tong Shixin,Cong Haozhe,Chen Yuren.Fuzzy logic prediction model for clearance time of freeway traffic incidents[J].Journal of Chongqing Jiaotong University:Natural Science,2011,30(1):85-88.

[11] 孫連超,邵毅明,顏雪麗,等.基于TCT的公路交通事故黑點鑒別方法研究[J].重慶交通大學學報:自然科學版,2012,31(1):63-67. Sun Lianchao,Shao Yiming,Yan Xueli,et al.Identification of highway traffic accident black-spots based on traffic conflict technique [J].Journal of Chongqing Jiaotong University:Natural Science,2012,31(1):63-67.

[12] Chang H L,Chang T P.Prediction of Freeway Incident Duration based on Classification Tree Analysis[J].Journal of the Eastern Asia Society for Transportation Studies,2013,10:1964-1977.

A Traffic Incident Duration Time Predication Model Using Multivariable Decision Tree

Xiang Hongyan1, Jin Ming2

(1. School of Traffic & Transportation, Chongqing Jiaotong University, Chongqing 400074, China; 2. School of Automotive Engineering, Chongqing Industry Polytechnic College, Chongqing 401120, China)

Using theory and method of rough set and decision tree, a multivariable decision tree model was developed for traffic incident duration time prediction. Through analyzing the incident attributes, the attribute reduction algorithm in rough set theory was used to get the core attributes of the incident. By using the generalization principle of equivalence relation, a multivariable combination test was formed. By comparing the dependence of different variable combinations, the optimal variable combination was determined. Then, multivariable combination criterion instead of single variable criterion was used to set up the decision tree, and through limiting tree height and number of tree leaves, the scale of tree was controlled, so, the tree’s structure was optimized. The case study shows that this model has a good performance in classifying and forecasting traffic incident duration time, and it has good accuracy in duration time forecasting.

traffic engineering; duration; rough set; multivariable decision tree; predication

10.3969/j.issn.1674-0696.2015.03.23

2014-07-01；

2014-09-22

向紅艷(1980—)，女，湖北恩施人，副教授，博士，主要從事交通運輸規(guī)劃與管理方面的研究。E-mail: xiang-@126.com。

U491.1

A

1674-0696(2015)03-112-05