基于優化隨機森林算法的浮動車GPS數據插補模型

呂勤學，郭杜杜，李心，趙亮

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

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

目前針對浮動車GPS數據缺失研究，主要集中于利用道路匹配算法進行插補。盛彩英等[9]利用空間幾何、路網拓撲關系，實現軌跡點插補；Yuan等[10]在路網拓撲關系基礎上，通過路段分割法插補缺失數據點；黃振鋒等[11]利用曲線擬合算法和評價函數找到最佳道路匹配結果補齊缺失數據；Ersan等[12]利用卡爾曼濾波算法降低浮動車GPS數據與路網之間的偏差率補齊缺失數據；邵天浩等[13]利用哈希函數和路網邊權修正方法搜索路網信息對缺失數據點進行修復；谷遠利等[14]引入遺傳算法迭代出最佳空間相似度和最短路徑進行數據點插補。

上述研究從優化算法和空間關聯性出發，實現了浮動車GPS缺失數據的有效插補，但這些研究過度依賴路網信息的精準性和完整性，且需要與路網信息進行復雜比對，影響插補精度的提升。由文獻[15-16]表明隨機森林算法可對地面檢測器檢測的交通流缺失數據和事件進行有效插補，但尚未運用在浮動車GPS數據插補中。因隨機森林算法的隨機性，導致預測結果易產生波動，影響算法預測性能，故結合浮動車GPS數據點在道路上呈線形分布的空間特點，挖掘浮動車GPS數據點與交通流狀態之間的時間變化規律，提出基于優化隨機森林算法的插補模型。該模型將線性回歸算法融入隨機森林算法的結果輸出部分，并利用序列插補思想，依次插補缺失數據點。以浮動車GPS數據點出發，實現對缺失的浮動車GPS數據進行穩定的高精度插補，為后續研究與應用提供數據基礎。

1 基于優化隨機森林算法的GPS插補模型設計

本實驗模型利用隨機森林算法建立浮動車GPS數據點與速度、加速度和位移之間的關聯性，同時考慮到道路線形的特點，將線性回歸算法融入隨機森林算法的結果中進行優化，提升預測精度。

1.1 優化隨機森林算法

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

(1)

(2)

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

訓練出相應權重后，采用序列插補思想，逐一對預測點進行擬合，當第i+1個點擬合出后將作為擬合第i+2點的輸入，同時第1個點將被剔除依次進行預測至缺失點的個數n次后，生成n個最佳權重矩陣后輸出插補點Dn。其結構示意圖如圖1所示。

圖1 優化隨機森林模型示意圖

1.2 浮動車GPS數據插補優化隨機森林模型構建

本模型構建如圖2所示。

MAE為平均絕對誤差

1.2.1 數據預處理

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

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

1.2.2 樣本特征和數據集的劃分

對數據的時間間隔列進行遍歷，記錄其數值并除以時間間隔來確定缺失點的個數，同時選取插補段前若干個點作為預測模型預測函數的自變量，其預測函數F表達式見式(3)，其余點作為模型的訓練集。

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

(3)

式(3)中：下標n為預測點；S為經度；L為緯度；Z為高程；a為加速度；v為速度；m為位移。式(3)中，速度、加速度和位移為基礎特征，經度，緯度和高程為變化特征，如需要對經度進行預測時緯度和高程將作為訓練特征，經度為目標特征，一共5個特征作為建立預測經度的優化隨機森林模型。

1.2.3 浮動車GPS數據插補模型構建及訓練

在建立優化隨機森林模型過程中，最重要的參數是隨機森林中決策樹的個數nesti和特征屬性，的優化隨機森林模型進行預測時以MAE為特征屬性，其表達式為

(4)

以MAE最小為最優特征屬性。決策樹的個數則是根據平均絕對誤差與決策樹個數圖MAE-nesti得到，為了避免隨機性，對應到每個決策樹的平均絕對誤差都進行5次交叉驗證，取五次結果的平均值為最終結果，當決策樹的個數達到某個值時，誤差趨于平穩時的值就是最終優化隨機森林中決策樹的個數。

1.2.4 構建線性方程及更新權重

將線性回歸模型融入隨機森林模型結果輸出中，將結果分別乘以權重ω、α、β構建出線性方程，其表達式為

(5)

式(5)中：ωi、αi、βi分別為第i個點經度、緯度、位移的權重；Si、Li、mi為第i個點的經度、緯度、位移。

再利用最小二乘估計法計算出最佳權重，得出插補段中的經度、緯度和高程等變量。

1.2.5 插補結果判斷

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

(6)

2 實驗驗證

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

表1 實驗數據

2.1 最優參數調整

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

圖3 實驗數據MAE-nesti圖

2.2 預測函數點的選取

根據相鄰數據點之間的關聯性特點，選取插補段前的點數過多易導致數據間關聯性變弱，過少則易造成影響最終精度，因此分別選取插補段前3、5、7、10、13、15個點作為預測函數的自變量，相應的誤差為因變量，考慮到誤差單位不同，故將經度和緯度變量數值乘100，高程變量乘0.1，位移變量乘0.5。綜合其各個預測變量的結果(圖4)可知，選取缺失點前5個點作為預測函數輸入為最佳。

圖4 不同時間間隔誤差

2.3 線性方程的權重確定

以28 s插補段為例，選取前5個點作為模型預測函數的輸入，相應的得出5個預測點，此5個預測值作為線性模型的輸入，依次將構建出五元一次線性方程，以經度為例得出的權重為

(7)

2.4 優化隨機森林模型與其他模型的插補結果對比

結果對比是通過刪除其中140組連續已知的28 s浮動車GPS數據，再通過上述建立的插補模型進行插補，插補出的數據與刪除前的數據做對比，最后得出結果。表2、表3分別為刪除前保留部分數據和利用線性回歸模型、決策樹模型、隨機森林模型和優化隨機森林模型進行插補后的部分數據，圖5為插補數據的誤差距離分布曲線。

表2 插補前數據

表3 插補后數據

圖5 模型對比結果

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

表4為優化隨機森林模型與其他模型的誤差結果分析，從結果的波動性來看，優化隨機森林模型明顯優于其他模型，其標準差為7.6 m相較于線性回歸模型、決策樹模型、隨機森林模型分別降低了174.8、23.2、10.9 m。可見優化隨機森林模型具有更好的穩定性。

表4 模型結果對比分析

3 結論

為解決浮動車GPS數據收集過程中缺失問題，利用浮動車GPS數據與速度、加速度、位移變量之間的關聯性并考慮到道路線形的特點，將隨機森林算法和線性回歸算法進行融合，建立基于優化隨機森林算法的浮動車GPS數據插補模型并與線性回歸模型、決策樹模型和隨機森林模型進行對比分析，得出如下結論。

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

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

(3)經過浮動車GPS數據插補模型處理結果可為城市交通狀態預測、交通規劃管理誘導和基于浮動車GPS數據識別出行方式研究等提供可靠的數據基礎。