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

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

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

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

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

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

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

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

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

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

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

1.1 定義

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

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

圖1 研究區(qū)域與相關參數簡圖

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

表1 部分訓練數據

1.2 影響并線行為的因素

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 并線行為決策樹

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

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

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

3 模型驗證

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

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

表4 部分測試數據

表5 決策樹模型結果

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

4 結束語

通過對駕駛人并線行為影響因素的分析，建立了駕駛人并線行為的決策樹模型，并借助車輛軌跡數據對模型進行了學習與驗證。驗證結果顯示預測精確度高達89.2%，表明運用提出的決策樹模型來預測駕駛人的并線行為能夠獲得較好的結果。

未來，決策樹模型可應用于微觀仿真和駕駛員輔助系統開發(fā):換道模型會成為微觀交通仿真計劃的重要組成部分;駕駛員輔助系統能使駕駛員在高速公路入口合流區(qū)域換道時得到指示信息，幫助駕駛人做出并線決策，以保障車輛與駕駛人的安全。

［1］王軍雷，李百川，應世杰，等.車道變換碰撞預警分析及最小縱向安全距離模型的研究［J］.人類工效學，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］智永鋒，張駿，史忠科.高速公路加速車道長度設計與車輛匯入模型研究［J］.中國公路學報，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］.吉林大學學報:工學版，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)預測［J］.河北工業(yè)大學學報，2010(2):105.

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

［12］范明，范宏建.數據挖掘導論［M］.北京:人民郵電出版社，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］傅亞莉.數據挖掘技術C4.5算法在成績分析中的應用［J］.重慶理工大學學報:自然科學版，2013(11):78 -82.

(責任編輯 劉舸)

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);江蘇省道路載運工具新技術應用重點實驗室資助項目(BM2008206002)

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

劉志強，王俊彥，汪澎，等.基于決策樹的高速公路入口合流區(qū)域換道研究［J］.重慶理工大學學報:自然科學版，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.