[發(fā)明專利]一種基于決策樹的自動(dòng)駕駛搜索決策方法

有效

• 申請?zhí)枺?/td>: 201911021966.2
• 申請日: 2019-10-25
• 公開（公告）號: CN110836675B
• 公開（公告）日: 2021-09-28
• 發(fā)明（設(shè)計(jì)）人: 李大慶;李秋玥
• 申請（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京慧泉知識產(chǎn)權(quán)代理有限公司 11232
• 代理人: 王順榮;唐愛華

1.一種基于決策樹的自動(dòng)駕駛搜索決策方法，其特征在于：其步驟如下：

步驟A：獲取每輛出租車的搜索軌跡序列和載客軌跡序列，利用搜索軌跡序列及載客軌跡序列計(jì)算每輛出租車當(dāng)天運(yùn)載效率；

步驟B：選擇包括城市乘客流量網(wǎng)絡(luò)節(jié)點(diǎn)強(qiáng)度、行駛速度、搜索時(shí)長在內(nèi)的復(fù)數(shù)個(gè)交通決策屬性，在城市范圍內(nèi)劃分規(guī)定大小格點(diǎn)，并對各格點(diǎn)內(nèi)的交通決策屬性進(jìn)行計(jì)算；基于城市交通屬性的時(shí)空分布，計(jì)算搜索路徑的特點(diǎn)；

在步驟B中所描述的“選擇包括城市乘客流量網(wǎng)絡(luò)節(jié)點(diǎn)強(qiáng)度、行駛速度、搜索時(shí)長在內(nèi)的復(fù)數(shù)個(gè)交通決策屬性，在城市范圍內(nèi)劃分規(guī)定大小格點(diǎn)，并對各格點(diǎn)內(nèi)的交通決策屬性進(jìn)行計(jì)算；基于城市交通屬性的時(shí)空分布，計(jì)算搜索路徑的特點(diǎn)”，其做法如下：對于城市乘客流量網(wǎng)絡(luò)節(jié)點(diǎn)強(qiáng)度、行駛速度和搜索時(shí)長交通搜索決策變量進(jìn)行統(tǒng)計(jì)分析，對于選擇的交通搜索決策變量進(jìn)行時(shí)空分布統(tǒng)計(jì)，最后對每輛出租車進(jìn)行其交通搜索決策變量參數(shù)計(jì)算，具體步驟如下：

步驟B1：計(jì)算交通搜索決策變量；包括城市乘客流量網(wǎng)絡(luò)節(jié)點(diǎn)強(qiáng)度、行駛速度和搜索時(shí)長；對于可能影響出租車搜索決策的交通搜索決策變量，從成本及收益兩個(gè)角度考慮：成本為時(shí)間成本和油耗成本，這二者均與行駛速度強(qiáng)相關(guān)：

步驟B2：刻畫交通搜索決策變量的時(shí)空分布；對于選取的交通搜索決策變量，應(yīng)明確其在城市中的分布；應(yīng)注意到，城市交通路況與乘客需求均有很強(qiáng)的日周期性，因此，將城市以500m×500m大小的方格進(jìn)行空間劃分，對于乘客流量網(wǎng)絡(luò)節(jié)點(diǎn)強(qiáng)度、區(qū)域搜索距離、區(qū)域旅程長度和區(qū)域速度搜索決策變量，具體計(jì)算能分時(shí)段進(jìn)行，時(shí)段分為早高峰、午平峰和晚高峰；在此時(shí)空劃分基礎(chǔ)上，對各日相應(yīng)區(qū)域相應(yīng)時(shí)段的相應(yīng)搜索決策變量分別進(jìn)行均值處理，得到各區(qū)域在各時(shí)段的搜索決策變量，即交通搜索決策變量的時(shí)空分布；

步驟B3：計(jì)算交通搜索決策變量參數(shù)；對于每輛出租車，選取其當(dāng)日全部搜索軌跡，對每一個(gè)軌跡點(diǎn)，將其所在區(qū)域當(dāng)前時(shí)段的相應(yīng)交通搜索決策變量納入計(jì)算，若當(dāng)前軌跡點(diǎn)與上一軌跡點(diǎn)處于同一區(qū)域的同一時(shí)段，則跳至下一軌跡點(diǎn)，直至與上一納入軌跡點(diǎn)區(qū)域不同及時(shí)段不同；最終得到該出租車當(dāng)日在搜索過程中的交通搜索決策變量集合，對各交通搜索決策變量集合求均值，其值作為該出租車在相應(yīng)交通搜索決策變量上的交通搜索決策變量參數(shù)；

步驟C：基于步驟B中計(jì)算的搜索決策變量參數(shù)，以運(yùn)載效率高低作為類別劃分標(biāo)準(zhǔn)，以選擇的多個(gè)交通搜索決策變量為特征，利用ID3方法構(gòu)建決策樹，分析多個(gè)交通搜索決策變量對搜索過程的影響，進(jìn)行重要度排序，挖掘搜索過程中決策對不同搜索決策變量的依賴程度，進(jìn)行決策樹的驗(yàn)證。

2.根據(jù)權(quán)利要求1所述的一種基于決策樹的自動(dòng)駕駛搜索決策方法，其特征在于：在步驟A中描述的“獲取每輛出租車的搜索軌跡序列和載客軌跡序列，利用搜索軌跡序列及載客軌跡序列計(jì)算每輛出租車當(dāng)天運(yùn)載效率”，其做法如下：首先對軌跡數(shù)據(jù)進(jìn)行清洗及過濾，接下來篩選具備一預(yù)定運(yùn)載次數(shù)的出租車，最后選擇合適的統(tǒng)計(jì)方法計(jì)算出租車運(yùn)載效率，具體步驟如下：

步驟A1：軌跡數(shù)據(jù)清洗及過濾；出租車軌跡數(shù)據(jù)的記錄中會(huì)因儀器及人為因素導(dǎo)致數(shù)據(jù)的異常及缺失，通過識別異常點(diǎn)，濾除不正確的采樣數(shù)據(jù)；軌跡數(shù)據(jù)中，空載軌跡與載客軌跡交替出現(xiàn)，空載軌跡點(diǎn)由0表示，載客軌跡點(diǎn)由1表示，空載段軌跡由載客轉(zhuǎn)為空載的第一個(gè)空載點(diǎn)到下一次載客軌跡點(diǎn)，含該載客軌跡點(diǎn)載客段軌跡由空載轉(zhuǎn)為載客的第一個(gè)載客軌跡點(diǎn)到下一次空載軌跡點(diǎn)，含該空載軌跡點(diǎn)；利用實(shí)時(shí)速度、里程對數(shù)據(jù)中的異常軌跡點(diǎn)進(jìn)行清洗，選擇保證車輛營運(yùn)數(shù)量的時(shí)間段；

步驟A2：出租車的選擇；計(jì)算出租車運(yùn)載效率，需要保證當(dāng)天該出租車有足夠的搜索及載客數(shù)據(jù)；使得效率計(jì)算不會(huì)僅由一次及兩次搜索及載客數(shù)據(jù)而大幅波動(dòng)；因此，設(shè)置最低日行駛時(shí)長與最低日載客次數(shù)，選擇日行駛時(shí)間超過低日行駛時(shí)長，載客次數(shù)超過最低日載客次數(shù)的出租車作為總體進(jìn)行運(yùn)載效率的計(jì)算；

步驟A3：計(jì)算出租車運(yùn)載效率；選擇用當(dāng)日載客總收入與行駛總里程之比作為運(yùn)載效率即yuan/km；為計(jì)算當(dāng)日載客總收入，需根據(jù)數(shù)據(jù)所在城市當(dāng)?shù)赜?jì)價(jià)標(biāo)準(zhǔn)，結(jié)合出租車軌跡數(shù)據(jù)，進(jìn)行計(jì)算，此舉將擁堵的計(jì)費(fèi)補(bǔ)償，等待時(shí)間的計(jì)費(fèi)補(bǔ)償涵蓋在內(nèi)，貼近真實(shí)成本與收益。

3.根據(jù)權(quán)利要求1所述的一種基于決策樹的自動(dòng)駕駛搜索決策方法，其特征在于：在步驟C中所描述的“基于步驟B中計(jì)算的搜索決策變量參數(shù)，以運(yùn)載效率高低作為類別劃分標(biāo)準(zhǔn)，以選擇的多個(gè)交通搜索決策變量為特征，利用ID3方法構(gòu)建決策樹，分析多個(gè)交通搜索決策變量對搜索過程的影響，進(jìn)行重要度排序，挖掘搜索過程中決策對不同搜索決策變量的依賴程度，進(jìn)行決策樹的驗(yàn)證”，其做法如下：對所有變量進(jìn)行特征選擇與類別劃分，在此基礎(chǔ)上構(gòu)建決策樹，依據(jù)決策樹結(jié)果分析各搜索決策變量對搜索決策的影響程度，具體步驟如下：

步驟C1：特征選擇與類別劃分；由于決策樹的特征及類別均須為有限離散值，而出租車的當(dāng)日運(yùn)載效率和當(dāng)日交通搜索決策變量參數(shù)均為連續(xù)值，因此，在上述步驟B計(jì)算得到的出租車交通搜索決策變量參數(shù)的基礎(chǔ)上，首先對各交通搜索決策變量參數(shù)利用二分法進(jìn)行離散化，其次基于步驟A的每日出租車運(yùn)載效率計(jì)算結(jié)果，選擇運(yùn)載效率在當(dāng)日前10％和當(dāng)日后10％的出租車作為樣本，在所有樣本中選擇50％作為訓(xùn)練集，50％作為測試集；

步驟C2：構(gòu)建決策樹；在信息論中，期望信息越小，信息增益越大，ID3方法的核心思想就是利用信息增益度量屬性選擇，在每次需要分裂時(shí)，計(jì)算每個(gè)屬性的信息增益，選擇分裂后信息增益最大的屬性進(jìn)行分裂；其中，集合S的信息熵H(S)定義為：

其中當(dāng)前樣本集合S中第x類樣本所占的比例為p(x)；

信息增益衡量的是一個(gè)屬性所包含的“信息價(jià)值”，用屬性A對樣本集合S進(jìn)行劃分所獲得的信息增益表示為：

其中，H(S)為當(dāng)前集合S的信息熵；T為通過屬性A分割集合S創(chuàng)建的子集，使得S＝U_t∈Tt；p(t)為t中元素?cái)?shù)量與集合S中元素?cái)?shù)量的比值；H(t)為子集t的信息熵；H(S|A)為得知屬性A后的條件熵；因此，信息增益表現(xiàn)得知屬性A的信息時(shí)樣本集合不確定度減少的程度，在每一輪分裂時(shí)，選擇信息增益最大的特征進(jìn)行分裂，將其特征屬性作為節(jié)點(diǎn)加入決策樹，并進(jìn)行下一輪信息熵、各分支信息熵與信息增益的計(jì)算，直到全部分裂；

步驟C3：決策樹的分析與驗(yàn)證；構(gòu)建決策樹后，對生成決策樹進(jìn)行節(jié)點(diǎn)分析，其中，根節(jié)點(diǎn)屬性是區(qū)分出租車運(yùn)載效率的最關(guān)鍵屬性，其余各屬性的重要度排序隨遠(yuǎn)離根節(jié)點(diǎn)依次降低；對各城市的數(shù)據(jù)集所得到的決策樹進(jìn)行共性分析與特性分析；利用測試集數(shù)據(jù)，對生成的決策樹進(jìn)行模型驗(yàn)證。