劉志強，王俊彥，汪澎，倪捷

(江蘇大學(xué)汽車與交通工程學(xué)院，江蘇鎮(zhèn)江 212013)

基于決策樹的高速公路入口合流區(qū)域換道研究

劉志強，王俊彥，汪澎，倪捷

(江蘇大學(xué)汽車與交通工程學(xué)院，江蘇鎮(zhèn)江 212013)

針對高速公路入口合流區(qū)域換道事故頻繁發(fā)生的情況，利用決策樹方法建立了車輛在該區(qū)域的并線決策模型，保證車輛并線時的安全;借助車輛軌跡數(shù)據(jù)對模型進行了學(xué)習(xí)與驗證。模型驗證結(jié)果表明:并線車輛相對于目標(biāo)車道前方車輛的相對速度是駕駛?cè)瞬⒕€時需要考慮的最重要的因素;相比傳統(tǒng)模型，決策樹模型具有更高的預(yù)測精度;模型還可進一步應(yīng)用于交通仿真以及駕駛?cè)溯o助系統(tǒng)。

合流區(qū)域;決策樹;信息增益率;車輛換道

車道變換分為強制性車道變換和自由車道變換。車道結(jié)束時將執(zhí)行強制性車道變換，當(dāng)想獲取更好的車道時將執(zhí)行自由車道變換。換道模型描述在不同交通條件下駕駛?cè)说膿Q道行為，這些模型是微觀交通仿真不可缺少的一部分。隨著汽車智能技術(shù)的發(fā)展，高效的換道模型已成為駕駛員輔助系統(tǒng)必不可少的組成部分。

H.N.Koutsopoulos等運用可接受間隙模型來進行換道模型［1-6］的研究。建立的模型基于同一假設(shè)，即當(dāng)目標(biāo)車道前后車距可以被接受時駕駛?cè)诉M行并線或進行車道變換。Kita等運用離散選擇模型(如二元Logit模型、博弈論)來建立換道模型［7-9］。

本文應(yīng)用決策樹方法來模擬駕駛員處于高速公路入口合流區(qū)域時的復(fù)雜并線決策過程。決策樹方法應(yīng)用于換道建模具有許多優(yōu)點:首先，決策樹方法是非參數(shù)性的，不需要假設(shè)分布形式;其次，決策樹可以提供簡單的規(guī)則去反映駕駛?cè)说男袨?再次，決策樹的結(jié)果易于解釋，模型結(jié)構(gòu)便于實現(xiàn)。

1 并線行為的定義與影響因素

1.1 定義

本文將高速公路中加速車道與應(yīng)急車道統(tǒng)稱為并線車道，加速車道與應(yīng)急車道的相鄰車道稱為目標(biāo)車道。駕駛員行駛在并線車道的任何時刻都有2個選擇:并線和不并線。

并線事件定義為車輛橫向坐標(biāo)開始向目標(biāo)車道方向改變并且沒有發(fā)生震蕩。在并線之前的其他時刻定義為非并線事件，即駕駛?cè)藳]有并線且保持駕駛在并線車道上。一位駕駛?cè)丝梢詤⑴c很多次非并線事件，但只能參與一次并線事件。圖1是本文研究區(qū)域與相關(guān)參數(shù)的簡圖。

圖1 研究區(qū)域與相關(guān)參數(shù)簡圖

研究通過車輛軌跡數(shù)據(jù)獲得325次觀察值，其中包括177次非并線事件和148次并線事件。數(shù)據(jù)集被進一步劃分，其中80%用于模型訓(xùn)練，20%用于模型測試，部分訓(xùn)練數(shù)據(jù)如表1所示。

表1 部分訓(xùn)練數(shù)據(jù)

1.2 影響并線行為的因素

駕駛?cè)诵旭傇诓⒕€車道上通過考慮交通狀況(包括目標(biāo)車道和并線車道)來決定是否并線。影響駕駛?cè)瞬⒕€決定的因素有很多，根據(jù)文獻［2，5］，有5個主要因素影響駕駛員的并線行為，它們將作為本文決策樹模型C4.5算法的輸入變量，見表2。

表2 并線行為影響因素信息

1)ΔV前:并線車輛與目標(biāo)車道前方車輛的速度差(m/s)。ΔV前=V前-V并線，其中:V前是目標(biāo)車道前方車輛的速度;V并線是并線車輛的速度。

2)ΔV后:并線車輛與目標(biāo)車道后方車輛的速度差(m/s)。ΔV后=V后-V并線，其中:V后是目標(biāo)車道后方車輛的速度;V并線是并線車輛的速度。

3)D前:并線車輛與目標(biāo)車道前方車輛的距離(m)。

4)D后:并線車輛與目標(biāo)車道后方車輛的距離(m)。

5)S:并線車輛離并線車道入口的距離(m)。

在上述5個影響因素中:2個車間距指標(biāo)D前和D后反映并線換道時目標(biāo)車道是否具有合適的并線換道空間;2個速度差指標(biāo)ΔV前和ΔV后反映并線換道時的潛在危險性;距離指標(biāo)S反映車輛并線換道的緊迫程度。

2 基于決策樹的并線換道模型

決策樹方法運用自上而下的遞歸方式，從決策樹的根到葉結(jié)點的每一條路徑對應(yīng)著一條分類規(guī)則，整個決策樹對應(yīng)著一組分類規(guī)則表達式。每一個非葉結(jié)點都與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)。本文采用決策樹C4.5算法，選擇具有最高信息增益率的屬性作為整個集合S的測試屬性［10-13］。

1)信息增益與信息增益率。信息增益來源于信息論中熵(Entropy)這一概念。本文的訓(xùn)練數(shù)據(jù)集S包含了s個數(shù)據(jù)樣本。定義C1，C2代表兩個決策類:并線類與不并線類，那么s1，s2就是類C1，C2中的樣本數(shù)目。給定的樣本分類所需要的期望信息Info(s1，s2)可以由式(1)計算得出。

其中pi是樣本屬于Ci的概率，用si/s來估計。

分別計算當(dāng)各屬性(V1，V2，D1，D2，S)作為分裂屬性時它們的信息增益率，選擇信息增益率最大的屬性作為最佳分裂屬性。

假設(shè)屬性V1可以取{a1，a2，…，am}m個不同值，那么可以用屬性V1將S劃分成m個子集{S1，S2，…，Sm}，而Sj包含S中含有值aj的樣本。如果將V1作為測試屬性(最佳分裂屬性)，則這些子集對應(yīng)于由包含集合S的結(jié)點生長出來的分支。設(shè)sij是子集Sj中類Ci的樣本數(shù)，則由V1劃分成的子集的熵E(S，V1)可以由式(2)計算得出。

其中第j個子集的權(quán)值等于子集中的樣本個數(shù)除以集合S中的樣本總數(shù)。熵值越小，子集劃分的純度越高。對于給定的子集Sj，其期望信息Info(s1j，s2j)可以由式(3)計算得出。

根據(jù)期望信息和熵值可以計算出相應(yīng)的信息增益值。屬性V1分支上得到的信息增益Gain(S，V1)可以由下式計算得出:

信息增益率是在信息增益概念基礎(chǔ)上發(fā)展起來的，屬性V1的信息增益率GainRatio(S，V1)可以用下面的公式計算得出:

比較上述5個屬性的信息增益率，數(shù)值最大的屬性就是最佳分裂屬性，根據(jù)分裂屬性的取值，可以得到?jīng)Q策樹分支，從而將數(shù)據(jù)集劃分為多個子集。對每一個生成的子樹重新計算各屬性信息增益率，依次類推，直至某一子集中的樣本屬于同一類，決策樹停止分裂。

2)屬性閾值的選擇。本文中的5個屬性都是連續(xù)型數(shù)字屬性，需要確定它們的閾值。首先需要將連續(xù)屬性進行離散化處理，將屬性值劃分成若干個區(qū)間;然后運用Fayyad邊界點判定定理［13］，計算相鄰兩類區(qū)間邊界點處屬性值的信息增益率，選擇信息增益率最大的屬性值作為最優(yōu)閾值。

3)樹的剪枝。按照上述步驟，借助訓(xùn)練數(shù)據(jù)可以構(gòu)建出并線行為決策樹。生成決策樹后要通過計算節(jié)點的分類錯誤來進行樹的剪枝。本文的決策樹C4.5算法采用后剪枝算法中的降低錯誤剪枝法REP(reduced error pruning)。對于決策樹中每個不為葉節(jié)點的子樹ST，根據(jù)對測試樣本集的分類結(jié)果判斷是否將其用葉節(jié)點代替。用e表示保留子樹ST時對測試集的分類錯誤率，e'表示用最佳葉節(jié)點代替ST后對測試集的分類錯誤率。如果滿足e'≤e，則對ST進行剪枝，將其用葉節(jié)點代替;否則，不對ST進行剪枝。重復(fù)這個過程直到對任何子樹進行剪枝都會增加對測試樣本集的分類錯誤率。最終得到的決策樹是對測試樣本集的分類精度最高的決策樹，同樣這棵決策樹也是獲得該分類精度的規(guī)模最小的決策樹。

本文的決策樹C4.5算法通過weka軟件平臺實現(xiàn)。圖2為通過weka修剪后的并線行為決策樹。

圖2 并線行為決策樹

決策樹結(jié)構(gòu)中的終端節(jié)點用方框表示，決策節(jié)點用圓圈表示。在終端節(jié)點內(nèi)標(biāo)記類標(biāo)簽以觀測樣本數(shù)。決策樹根節(jié)點通過相對速度V1進行分裂，這就表明并線車輛相對于目標(biāo)車道前方車輛的相對速度是駕駛?cè)俗龀霾⒕€決策需要考慮的最重要因素。決策樹模型的決策過程清晰、直觀，易于理解:如果并線車輛相對于目標(biāo)車道前車速度較慢(V1≥0 m/s)或者稍微比前車快一點(0＞V1≥-3.1 m/s)，距離目標(biāo)車道前后方車輛車距較大(D2≥7 m，D1≥7.6 m)，且進入并線車道不遠(S≤56.4 m)，此時駕駛?cè)丝梢圆⒕€。但如果僅因為與后車的距離沒有足夠大(D2＜7 m)，那么駕駛員也不會進行并線。與此相反，如果并線車輛相對于目標(biāo)車道前車速度過快(V1＜-3.1 m/s)，距離目標(biāo)車道前車車距較小(D1＜17.1 m)，那么駕駛?cè)瞬贿M行并線。由此可見，決策樹模型反映出的規(guī)則在日常駕駛中都有所體現(xiàn)。

4)分類規(guī)則。從決策樹根節(jié)點到任意一個葉節(jié)點所形成的一條路徑都構(gòu)成一條分類規(guī)則。根據(jù)圖2的并線行為決策樹，可以提取出“IF-THEN”形式的分類規(guī)則(表3)。

表3 并線行為決策樹分類規(guī)則

3 模型驗證

本文的交通數(shù)據(jù)從Next Generation Simulation (NGSIM)(14)獲得，數(shù)據(jù)用于決策樹模型的學(xué)習(xí)與驗證。數(shù)據(jù)集中的軌跡數(shù)據(jù)提供每輛車的縱坐標(biāo)、橫坐標(biāo)、速度、加速度和前后兩車間隔時間，采樣頻率為10 Hz。

使用分類規(guī)則對測試數(shù)據(jù)進行識別(表4是部分測試數(shù)據(jù))，并將識別結(jié)果與實際并線情況進行對比，用識別的準(zhǔn)確性來驗證模型的有效性。表5是模型最終的預(yù)測結(jié)果。

表4 部分測試數(shù)據(jù)

表5 決策樹模型結(jié)果

模型驗證結(jié)果顯示:決策樹模型的測試數(shù)據(jù)精確度達到89.2%，表明將該模型用于高速公路入口合流區(qū)域車輛并線情況研究是可行的。

4 結(jié)束語

通過對駕駛?cè)瞬⒕€行為影響因素的分析，建立了駕駛?cè)瞬⒕€行為的決策樹模型，并借助車輛軌跡數(shù)據(jù)對模型進行了學(xué)習(xí)與驗證。驗證結(jié)果顯示預(yù)測精確度高達89.2%，表明運用提出的決策樹模型來預(yù)測駕駛?cè)说牟⒕€行為能夠獲得較好的結(jié)果。

未來，決策樹模型可應(yīng)用于微觀仿真和駕駛員輔助系統(tǒng)開發(fā):換道模型會成為微觀交通仿真計劃的重要組成部分;駕駛員輔助系統(tǒng)能使駕駛員在高速公路入口合流區(qū)域換道時得到指示信息，幫助駕駛?cè)俗龀霾⒕€決策，以保障車輛與駕駛?cè)说陌踩?/p>

［1］王軍雷，李百川，應(yīng)世杰，等.車道變換碰撞預(yù)警分析及最小縱向安全距離模型的研究［J］.人類工效學(xué)，2004(4):16-19.

［2］Yang Q，Koutsopoulos H N.A Microscopic Traffic Simulator for Evaluation of Dynamic Traffic Management Systems［J］.Transportation Research，1996，4:113-129.

［3］智永鋒，張駿，史忠科.高速公路加速車道長度設(shè)計與車輛匯入模型研究［J］.中國公路學(xué)報，2009(2):93 -97.

［4］Hidas P.Modeling Vehicle Interactions in Microscopic Simulation of Merging and Weaving［J］.Transportation Research，2005，13:37-62.

［5］王榮本，游峰，崔高健，等.車輛安全換道分析［J］.吉林大學(xué)學(xué)報:工學(xué)版，2005(Z):179-182.

［6］Toledo T，KoutsopoulosH N，Ben-Akiva M.Integrated Driving Behavior Modeling［J］.Transportation Research，2007，15:96-112.

［7］Kita H.Effects of Merging Lane Length on the Merging Behavior at Expressway On-Ramps［C］//Proc.12th International Symposium on the Theory of Traffic Flow and Transportation.China:［s.n.］，1993:37-51.

［8］Meng Q，Weng J.A Cellular Automata Model for Work Zone Traffic［C］//Transportation Research Record，No. 2188，Transportation Research Board of the National A-cademies.Washington:［s.n.］，2010:131-139.

［9］Kita H.A Merging-Giveway Interaction Model of Cars in A Merging Section:A Game Theoretic Analysis［J］. Transportation Research，1999，33A:305-312.

［10］房麗俠，魏連雨，閆偉陽.基于決策樹的交通擁擠狀態(tài)預(yù)測［J］.河北工業(yè)大學(xué)學(xué)報，2010(2):105.

［11］毛國君，段立娟，王實，等.數(shù)據(jù)挖掘原理與算法［M］.北京:清華大學(xué)出版社，2005:109，126.

［12］范明，范宏建.數(shù)據(jù)挖掘?qū)д摚跰］.北京:人民郵電出版社，2006:89-118.

［13］Fayyad U M，Irani K B.On the handling of continuousvalue attributes in decision tree generation［J］.Machine Learning，1992，8(1):87-102.

［14］傅亞莉.數(shù)據(jù)挖掘技術(shù)C4.5算法在成績分析中的應(yīng)用［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，2013(11):78 -82.

(責(zé)任編輯 劉舸)

Research of Lane Change on Freeway On-ramp Merging Area on Decision Tree

LIU Zhi-qiang，WANG Jun-yan，WANG Peng，NI Jie
(College of Automotive and Traffic Engineering，Jiangsu University，Zhenjiang 212013，China)

Freeway on-ramp merging area is general accident-prone section.This paper establishes the vehicle merging decision model based on decision tree in this area in order to ensure the safety of the vehicle.Vehicle trajectory data were used for model learning and validation.Model validation results show that:the relative speed of the merging vehicle with respect to the lead vehicle in the target lane is the most important factor affecting the driver’s merging behavior.Compared to the traditional models，the decision tree model has higher prediction accuracy，and that the model can be further applied in traffic simulation and driver assistance systems.

on-ramp merging area;decision tree;information gain ratio;lane change

U491

A

1674-8425(2014)08-0001-05

10.3969/j.issn.1674-8425(z).2014.08.001

2014-03-22

教育部博士點基金資助項目(20113227110014);江蘇省道路載運工具新技術(shù)應(yīng)用重點實驗室資助項目(BM2008206002)

劉志強(1963—)，男，江蘇靖江人，博士，教授，主要從事道路交通運輸系統(tǒng)安全、智能運輸系統(tǒng)等方面研究。

劉志強，王俊彥，汪澎，等.基于決策樹的高速公路入口合流區(qū)域換道研究［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，2014(8):1-5.

format:LIU Zhi-qiang，WANG Jun-yan，WANG Peng，et al.Research of Lane Change on Freeway On-ramp Merging Area on Decision Tree［J］.Journal of Chongqing University of Technology:Natural Science，2014(8):1-5.