向紅艷，金 明

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

?

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

向紅艷1，金 明2

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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 構(gòu)建多變量組合檢驗(yàn)

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

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

(4)

以C對U進(jìn)行新的劃分，得：

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

(5)

令Z={Z1，Z2，…，Zh，Z(h+1)}，對任意Xj∈U/IND(C) (j=1，2，…，r)進(jìn)行檢驗(yàn)，判斷其是否屬于U/T中的元素；若Xj?Yt(t=1，2，…，h)，將Xj的元素歸入Zt，將不屬于任何U/T子集的元素一起歸入集合Z(h+1)。Z即為根據(jù)變量組合C在U上確定的新的等價(jià)關(guān)系，是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é)點(diǎn)；UN表示節(jié)點(diǎn)上的當(dāng)前交通事件樣本集合；lN表示交通事件樣本個數(shù)。在建樹過程中通過限制樹的最大高度和每個節(jié)點(diǎn)的最少樣本數(shù)來控制樹的生長。令樹的最大高度為Nmax，節(jié)點(diǎn)必須包含的最少記錄數(shù)為lmin。以下是構(gòu)建多變量決策樹的具體步驟。

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

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

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

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

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

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

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

8)結(jié)束，計(jì)算集合Z(h+1)所對應(yīng)的持續(xù)時間。

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

(9)

3 實(shí)例應(yīng)用

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

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

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

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

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

圖2 多變量決策樹結(jié)構(gòu)

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

(10)

σ=1-μ

(11)

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

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

表2 預(yù)測結(jié)果分析

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

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

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

4 結(jié) 語

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

[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] 康國祥,方守恩.基于風(fēng)險(xiǎn)分析的交通事件持續(xù)時間預(yù)測[J].同濟(jì)大學(xué)學(xué)報(bào):自然科學(xué)版,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ù)時間預(yù)測[J].中國公路學(xué)報(bào),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] 苗奪謙,王玨.基于粗糙集的多變量決策樹的構(gòu)造方法[J].軟件學(xué)報(bào),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] 童世鑫,叢浩哲,陳雨人.高速公路交通事件清除時間模糊邏輯預(yù)測模型[J].重慶交通大學(xué)學(xué)報(bào):自然科學(xué)版,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的公路交通事故黑點(diǎn)鑒別方法研究[J].重慶交通大學(xué)學(xué)報(bào):自然科學(xué)版,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—)，女，湖北恩施人，副教授，博士，主要從事交通運(yùn)輸規(guī)劃與管理方面的研究。E-mail: xiang-@126.com。

U491.1

A

1674-0696(2015)03-112-05