呂勤學(xué)，郭杜杜，李心，趙亮

(新疆大學(xué)機(jī)械工程學(xué)院，烏魯木齊 830046)

隨著數(shù)字化城市建設(shè)，推動(dòng)了大數(shù)據(jù)在城市交通的應(yīng)用[1-2]，浮動(dòng)車全球定位系統(tǒng)(global positioning system,GPS)數(shù)據(jù)因具有高精度，全天候和易收集等特點(diǎn)，被廣泛應(yīng)用于智能交通領(lǐng)域。但原始浮動(dòng)車GPS數(shù)據(jù)易受建筑物、林蔭遮擋和信號(hào)干擾等因素影響造成數(shù)據(jù)缺失[3]，導(dǎo)致數(shù)據(jù)特征量減少、特征提取存在偏差[4]，影響了浮動(dòng)車GPS數(shù)據(jù)在路網(wǎng)狀態(tài)分析[5-6]、交通流預(yù)測(cè)以及出行方式判別[7-8]等領(lǐng)域的研究與應(yīng)用，因此，研究浮動(dòng)車GPS數(shù)據(jù)插補(bǔ)具有重要意義。

目前針對(duì)浮動(dòng)車GPS數(shù)據(jù)缺失研究，主要集中于利用道路匹配算法進(jìn)行插補(bǔ)。盛彩英等[9]利用空間幾何、路網(wǎng)拓?fù)潢P(guān)系，實(shí)現(xiàn)軌跡點(diǎn)插補(bǔ)；Yuan等[10]在路網(wǎng)拓?fù)潢P(guān)系基礎(chǔ)上，通過路段分割法插補(bǔ)缺失數(shù)據(jù)點(diǎn)；黃振鋒等[11]利用曲線擬合算法和評(píng)價(jià)函數(shù)找到最佳道路匹配結(jié)果補(bǔ)齊缺失數(shù)據(jù)；Ersan等[12]利用卡爾曼濾波算法降低浮動(dòng)車GPS數(shù)據(jù)與路網(wǎng)之間的偏差率補(bǔ)齊缺失數(shù)據(jù)；邵天浩等[13]利用哈希函數(shù)和路網(wǎng)邊權(quán)修正方法搜索路網(wǎng)信息對(duì)缺失數(shù)據(jù)點(diǎn)進(jìn)行修復(fù)；谷遠(yuǎn)利等[14]引入遺傳算法迭代出最佳空間相似度和最短路徑進(jìn)行數(shù)據(jù)點(diǎn)插補(bǔ)。

上述研究從優(yōu)化算法和空間關(guān)聯(lián)性出發(fā)，實(shí)現(xiàn)了浮動(dòng)車GPS缺失數(shù)據(jù)的有效插補(bǔ)，但這些研究過度依賴路網(wǎng)信息的精準(zhǔn)性和完整性，且需要與路網(wǎng)信息進(jìn)行復(fù)雜比對(duì)，影響插補(bǔ)精度的提升。由文獻(xiàn)[15-16]表明隨機(jī)森林算法可對(duì)地面檢測(cè)器檢測(cè)的交通流缺失數(shù)據(jù)和事件進(jìn)行有效插補(bǔ)，但尚未運(yùn)用在浮動(dòng)車GPS數(shù)據(jù)插補(bǔ)中。因隨機(jī)森林算法的隨機(jī)性，導(dǎo)致預(yù)測(cè)結(jié)果易產(chǎn)生波動(dòng)，影響算法預(yù)測(cè)性能，故結(jié)合浮動(dòng)車GPS數(shù)據(jù)點(diǎn)在道路上呈線形分布的空間特點(diǎn)，挖掘浮動(dòng)車GPS數(shù)據(jù)點(diǎn)與交通流狀態(tài)之間的時(shí)間變化規(guī)律，提出基于優(yōu)化隨機(jī)森林算法的插補(bǔ)模型。該模型將線性回歸算法融入隨機(jī)森林算法的結(jié)果輸出部分，并利用序列插補(bǔ)思想，依次插補(bǔ)缺失數(shù)據(jù)點(diǎn)。以浮動(dòng)車GPS數(shù)據(jù)點(diǎn)出發(fā)，實(shí)現(xiàn)對(duì)缺失的浮動(dòng)車GPS數(shù)據(jù)進(jìn)行穩(wěn)定的高精度插補(bǔ)，為后續(xù)研究與應(yīng)用提供數(shù)據(jù)基礎(chǔ)。

1 基于優(yōu)化隨機(jī)森林算法的GPS插補(bǔ)模型設(shè)計(jì)

本實(shí)驗(yàn)?zāi)Ｐ屠秒S機(jī)森林算法建立浮動(dòng)車GPS數(shù)據(jù)點(diǎn)與速度、加速度和位移之間的關(guān)聯(lián)性，同時(shí)考慮到道路線形的特點(diǎn)，將線性回歸算法融入隨機(jī)森林算法的結(jié)果中進(jìn)行優(yōu)化，提升預(yù)測(cè)精度。

1.1 優(yōu)化隨機(jī)森林算法

隨機(jī)森林算法是Bagging集成算法和決策樹算法的融合[17]，屬于Bagging算法的一種拓展?？紤]到?jīng)Q策樹在生成的過程中容易出現(xiàn)過擬合問題，針對(duì)這一問題一般處理方法是通過限制最大生長層數(shù)和葉子結(jié)點(diǎn)個(gè)數(shù)的方式進(jìn)行優(yōu)化，但其噪聲依然存在，影響模型的精度，于是融合Bagging集成算法[18]，將樣本中的數(shù)據(jù)進(jìn)行有放回的隨機(jī)抽樣，即隨機(jī)抽取n組樣本作為訓(xùn)練集，建立n個(gè)并行獨(dú)立弱評(píng)估器。建立過程中，決策樹在節(jié)點(diǎn)處進(jìn)行分枝以平均絕對(duì)誤差最小為原則，即對(duì)于任意一個(gè)需要分枝的變量A，對(duì)應(yīng)的任意父節(jié)點(diǎn)s，其兩個(gè)子節(jié)點(diǎn)U1和U2，需要求出使得U1和U2平均絕對(duì)誤差最小，且U1和U2的平均絕對(duì)誤差值之和最小時(shí)所對(duì)應(yīng)的變量和父節(jié)點(diǎn),其表達(dá)式為

(1)

(2)

式(2)中：L為殘差平方和函數(shù)。

訓(xùn)練出相應(yīng)權(quán)重后，采用序列插補(bǔ)思想，逐一對(duì)預(yù)測(cè)點(diǎn)進(jìn)行擬合，當(dāng)?shù)趇+1個(gè)點(diǎn)擬合出后將作為擬合第i+2點(diǎn)的輸入，同時(shí)第1個(gè)點(diǎn)將被剔除依次進(jìn)行預(yù)測(cè)至缺失點(diǎn)的個(gè)數(shù)n次后，生成n個(gè)最佳權(quán)重矩陣后輸出插補(bǔ)點(diǎn)Dn。其結(jié)構(gòu)示意圖如圖1所示。

圖1 優(yōu)化隨機(jī)森林模型示意圖

1.2 浮動(dòng)車GPS數(shù)據(jù)插補(bǔ)優(yōu)化隨機(jī)森林模型構(gòu)建

本模型構(gòu)建如圖2所示。

MAE為平均絕對(duì)誤差

1.2.1 數(shù)據(jù)預(yù)處理

考慮到數(shù)據(jù)在收集的過程中會(huì)出現(xiàn)異常的數(shù)據(jù)點(diǎn)，為了避免對(duì)最終的結(jié)果造成影響，利用閾值函數(shù)法，對(duì)不同的特征設(shè)置相應(yīng)的閾值，超過設(shè)定值，則認(rèn)定為異常數(shù)據(jù)進(jìn)行剔除。處理后的數(shù)據(jù)利用速度和時(shí)間間隔計(jì)算出對(duì)應(yīng)時(shí)間段的加速度和位移。為了方便后續(xù)試驗(yàn)驗(yàn)證，將選取完整路段數(shù)據(jù)，并將數(shù)據(jù)復(fù)制為兩份。一份用于實(shí)驗(yàn)，隨機(jī)連續(xù)刪除數(shù)據(jù)點(diǎn)，并在刪除點(diǎn)后數(shù)據(jù)點(diǎn)的時(shí)間間隔列修改其數(shù)值為缺失點(diǎn)個(gè)數(shù)乘以時(shí)間間隔來模擬插補(bǔ)段；另一份用于最終的結(jié)果驗(yàn)證。

試驗(yàn)采用假陰道法采精，挑選12只3～4歲無繁殖障礙且體況良好的多浪羊盤羊高代雜交公羊，在采精前三個(gè)星期進(jìn)行補(bǔ)飼。試驗(yàn)中將稀釋液與采集的精液按照精液密度等溫混合，對(duì)稀釋后的精液進(jìn)行活率檢測(cè)，活率達(dá)到0. 7以上，將分裝的試管放在37 ℃盛有水的燒杯中，水浴在冰箱中1. 5 h降溫至0～4 ℃以內(nèi)，并保存在冰水混合物中。

1.2.2 樣本特征和數(shù)據(jù)集的劃分

對(duì)數(shù)據(jù)的時(shí)間間隔列進(jìn)行遍歷，記錄其數(shù)值并除以時(shí)間間隔來確定缺失點(diǎn)的個(gè)數(shù)，同時(shí)選取插補(bǔ)段前若干個(gè)點(diǎn)作為預(yù)測(cè)模型預(yù)測(cè)函數(shù)的自變量，其預(yù)測(cè)函數(shù)F表達(dá)式見式(3)，其余點(diǎn)作為模型的訓(xùn)練集。

Sn=F(Ln-1,Zn-1,an-1,vn-1,mn-1)

(3)

式(3)中：下標(biāo)n為預(yù)測(cè)點(diǎn)；S為經(jīng)度；L為緯度；Z為高程；a為加速度；v為速度；m為位移。式(3)中，速度、加速度和位移為基礎(chǔ)特征，經(jīng)度，緯度和高程為變化特征，如需要對(duì)經(jīng)度進(jìn)行預(yù)測(cè)時(shí)緯度和高程將作為訓(xùn)練特征，經(jīng)度為目標(biāo)特征，一共5個(gè)特征作為建立預(yù)測(cè)經(jīng)度的優(yōu)化隨機(jī)森林模型。

1.2.3 浮動(dòng)車GPS數(shù)據(jù)插補(bǔ)模型構(gòu)建及訓(xùn)練

在建立優(yōu)化隨機(jī)森林模型過程中，最重要的參數(shù)是隨機(jī)森林中決策樹的個(gè)數(shù)nesti和特征屬性，的優(yōu)化隨機(jī)森林模型進(jìn)行預(yù)測(cè)時(shí)以MAE為特征屬性，其表達(dá)式為

(4)

以MAE最小為最優(yōu)特征屬性。決策樹的個(gè)數(shù)則是根據(jù)平均絕對(duì)誤差與決策樹個(gè)數(shù)圖MAE-nesti得到，為了避免隨機(jī)性，對(duì)應(yīng)到每個(gè)決策樹的平均絕對(duì)誤差都進(jìn)行5次交叉驗(yàn)證，取五次結(jié)果的平均值為最終結(jié)果，當(dāng)決策樹的個(gè)數(shù)達(dá)到某個(gè)值時(shí)，誤差趨于平穩(wěn)時(shí)的值就是最終優(yōu)化隨機(jī)森林中決策樹的個(gè)數(shù)。

1.2.4 構(gòu)建線性方程及更新權(quán)重

將線性回歸模型融入隨機(jī)森林模型結(jié)果輸出中，將結(jié)果分別乘以權(quán)重ω、α、β構(gòu)建出線性方程，其表達(dá)式為

(5)

式(5)中：ωi、αi、βi分別為第i個(gè)點(diǎn)經(jīng)度、緯度、位移的權(quán)重；Si、Li、mi為第i個(gè)點(diǎn)的經(jīng)度、緯度、位移。

再利用最小二乘估計(jì)法計(jì)算出最佳權(quán)重，得出插補(bǔ)段中的經(jīng)度、緯度和高程等變量。

1.2.5 插補(bǔ)結(jié)果判斷

為了驗(yàn)證模型可靠度和精度，利用誤差距離[式(6)]進(jìn)行精度測(cè)試。將真實(shí)值中的經(jīng)度、緯度、高程和預(yù)測(cè)出的經(jīng)度S、緯度L、高程Z放在同一數(shù)據(jù)集中利用誤差距離公式轉(zhuǎn)換為空間坐標(biāo)系，計(jì)算出兩者之間的距離來衡量模型的精度，最終得出的誤差距離越小，表示模型精度越高。

(6)

2 實(shí)驗(yàn)驗(yàn)證

在驗(yàn)證的過程中所用到的實(shí)驗(yàn)數(shù)據(jù)來自招募的6名志愿者21 d的出行軌跡，收集裝置設(shè)定以4 s為時(shí)間間隔，10 m為定位精度，收集的過程中要求志愿者全程保持設(shè)備處于正常運(yùn)行狀態(tài)，收集結(jié)束后的數(shù)據(jù)導(dǎo)入計(jì)算機(jī)中，最終得到的原始數(shù)據(jù)中記錄有經(jīng)度、緯度、高程、時(shí)間間隔和速度。選取其中17組原始數(shù)據(jù)約15 000個(gè)數(shù)據(jù)點(diǎn)，進(jìn)行預(yù)處理后作為實(shí)驗(yàn)數(shù)據(jù)，如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)

2.1 最優(yōu)參數(shù)調(diào)整

將收集到的數(shù)據(jù)輸入模型中，根據(jù)平均絕對(duì)誤差最小的原則，誤差越小，代表模型精度越高。以決策樹的個(gè)數(shù)為x軸，平均絕對(duì)誤差為y軸，依次遞增決策樹的個(gè)數(shù)得出平均絕對(duì)誤差的值，當(dāng)決策樹的個(gè)數(shù)達(dá)到某個(gè)值之后誤差趨于平穩(wěn)時(shí)即為模型的最優(yōu)參數(shù)。根據(jù)實(shí)驗(yàn)數(shù)據(jù)MAE-nesti圖(圖3)在分別預(yù)測(cè)經(jīng)度、緯度和高程時(shí)所對(duì)應(yīng)的nesti為150、250和200時(shí)為最優(yōu)參數(shù)。

圖3 實(shí)驗(yàn)數(shù)據(jù)MAE-nesti圖

2.2 預(yù)測(cè)函數(shù)點(diǎn)的選取

根據(jù)相鄰數(shù)據(jù)點(diǎn)之間的關(guān)聯(lián)性特點(diǎn)，選取插補(bǔ)段前的點(diǎn)數(shù)過多易導(dǎo)致數(shù)據(jù)間關(guān)聯(lián)性變?nèi)?，過少則易造成影響最終精度，因此分別選取插補(bǔ)段前3、5、7、10、13、15個(gè)點(diǎn)作為預(yù)測(cè)函數(shù)的自變量，相應(yīng)的誤差為因變量，考慮到誤差單位不同，故將經(jīng)度和緯度變量數(shù)值乘100，高程變量乘0.1，位移變量乘0.5。綜合其各個(gè)預(yù)測(cè)變量的結(jié)果(圖4)可知，選取缺失點(diǎn)前5個(gè)點(diǎn)作為預(yù)測(cè)函數(shù)輸入為最佳。

圖4 不同時(shí)間間隔誤差

2.3 線性方程的權(quán)重確定

以28 s插補(bǔ)段為例，選取前5個(gè)點(diǎn)作為模型預(yù)測(cè)函數(shù)的輸入，相應(yīng)的得出5個(gè)預(yù)測(cè)點(diǎn)，此5個(gè)預(yù)測(cè)值作為線性模型的輸入，依次將構(gòu)建出五元一次線性方程，以經(jīng)度為例得出的權(quán)重為

(7)

2.4 優(yōu)化隨機(jī)森林模型與其他模型的插補(bǔ)結(jié)果對(duì)比

結(jié)果對(duì)比是通過刪除其中140組連續(xù)已知的28 s浮動(dòng)車GPS數(shù)據(jù)，再通過上述建立的插補(bǔ)模型進(jìn)行插補(bǔ)，插補(bǔ)出的數(shù)據(jù)與刪除前的數(shù)據(jù)做對(duì)比，最后得出結(jié)果。表2、表3分別為刪除前保留部分?jǐn)?shù)據(jù)和利用線性回歸模型、決策樹模型、隨機(jī)森林模型和優(yōu)化隨機(jī)森林模型進(jìn)行插補(bǔ)后的部分?jǐn)?shù)據(jù)，圖5為插補(bǔ)數(shù)據(jù)的誤差距離分布曲線。

表2 插補(bǔ)前數(shù)據(jù)

表3 插補(bǔ)后數(shù)據(jù)

圖5 模型對(duì)比結(jié)果

表2、表3和圖5反映了在不同模型下的誤差距離，可以看出，優(yōu)化隨機(jī)森林模型插補(bǔ)誤差距離較小，統(tǒng)計(jì)其17 m以內(nèi)誤差距離占結(jié)果樣本的79.5%，17～50 m占20.5%。隨機(jī)森林模型插補(bǔ)得出的誤差距離，其誤差距離17 m以內(nèi)占結(jié)果樣本的48.7%，17～50 m占17.2%，其他大于50 m的占34.1%。決策樹模型誤差距離17 m以內(nèi)占結(jié)果樣本的30.3%，17～50 m占59.2%，其他大于50 m的占10.5%。線性回歸模型其誤差距離大部分大于50 m且與真實(shí)值之間的誤差距離波動(dòng)較大。由此可見，基于優(yōu)化隨機(jī)森林模型插補(bǔ)浮動(dòng)車GPS數(shù)據(jù)的精確程度相對(duì)較高，具有更好的插補(bǔ)精度。

表4為優(yōu)化隨機(jī)森林模型與其他模型的誤差結(jié)果分析，從結(jié)果的波動(dòng)性來看，優(yōu)化隨機(jī)森林模型明顯優(yōu)于其他模型，其標(biāo)準(zhǔn)差為7.6 m相較于線性回歸模型、決策樹模型、隨機(jī)森林模型分別降低了174.8、23.2、10.9 m?？梢妰?yōu)化隨機(jī)森林模型具有更好的穩(wěn)定性。

表4 模型結(jié)果對(duì)比分析

3 結(jié)論

為解決浮動(dòng)車GPS數(shù)據(jù)收集過程中缺失問題，利用浮動(dòng)車GPS數(shù)據(jù)與速度、加速度、位移變量之間的關(guān)聯(lián)性并考慮到道路線形的特點(diǎn)，將隨機(jī)森林算法和線性回歸算法進(jìn)行融合，建立基于優(yōu)化隨機(jī)森林算法的浮動(dòng)車GPS數(shù)據(jù)插補(bǔ)模型并與線性回歸模型、決策樹模型和隨機(jī)森林模型進(jìn)行對(duì)比分析，得出如下結(jié)論。

(1)所提出的優(yōu)化隨機(jī)森林模型插補(bǔ)結(jié)果平均誤差為12.3 m，與隨機(jī)森林模型、決策樹模型和線性回歸模型相比，分別減少了14.9、24.3、239.3 m，所提的方法具有更高的精度。

(2)所提出的優(yōu)化隨機(jī)森林模型，融入線性回歸算法，得出距離誤差的標(biāo)準(zhǔn)差為7.6 m相較于隨機(jī)森林模型減少10.9 m，表明線性回歸算法應(yīng)用到模型中具有較好的效果，并使得模型具有更高的穩(wěn)定性。

(3)經(jīng)過浮動(dòng)車GPS數(shù)據(jù)插補(bǔ)模型處理結(jié)果可為城市交通狀態(tài)預(yù)測(cè)、交通規(guī)劃管理誘導(dǎo)和基于浮動(dòng)車GPS數(shù)據(jù)識(shí)別出行方式研究等提供可靠的數(shù)據(jù)基礎(chǔ)。