葉 鋒,歐陽智超,陳威彪,周伊琴,周曉玲

1(福建師范大學 數學與信息學院,福州 350007)

2(廈門大學 信息科學與技術學院,廈門 361005)

引言

如今,人們可以在世界上任何地方找到和使用基于 GPS 的出租車服務系統(tǒng),如 Uber,Lyft等.啟用 GPS功能的的出租車系統(tǒng)實時收集和記錄GPS軌跡并且將數據上傳到服務器數據采集系統(tǒng).從出租車的GPS軌跡和實時收集的數據流中提取的集體交通動態(tài)是了解和預測未來旅程的重要信息來源.通過對出租車目的地和抵達時間的預測,可以動態(tài)調度出租車的資源,使理想的行程目的地應該是非常接近下一次行程的起點.

對出租車目的地和抵達時間的預測,目前在國內對這方面課題的研究普遍缺乏.國外研究學者較多運用的還是 K 最鄰近算法(K-Nearest Neighbor,K-NN)來對數據集進行分析.但對于大型訓練數據集,K-NN算法在計算上代價是非常大的,對于具有n個訓練模式和p維度的訓練數據集,K-NN算法的時間復雜度為O(np)[1].而由Jaeger和Hass提出的回聲狀態(tài)網絡(Echo State Network,ESN)以及相應的學習算法為遞歸神經網絡的研究開辟了嶄新的道路.調整僅僅針對讀出網絡進行.通過該算法大大降低了訓練的計算量,又避免了大多數基于梯度下降的學習算法所難回避的局限極小現象,并同時能夠取得很好的建模精度.

本文提出了一種基于機器學習的智能出租車預測系統(tǒng):先對波爾圖出租車GPS數據集[2]進行預處理,并對數據集進行分割,抽取部分數據集作為研究對象;主要借助回聲狀態(tài)網絡算法[3,4],隨機森林算法(Random Forest,RF)[5]等機器學習的算法,在算法處理器上對訓練集進行訓練學習,從而在測試集中預測出出租車的目的地和抵達時間.

1 系統(tǒng)總體結構設計與分析

提出的智能交通系統(tǒng)如圖1所示,它包括Sklearn開源庫處理平臺、Numpy、Scipy、Pandas、Matplotlib、算法處理器、波爾圖GPS出租車數據集.其中,波爾圖出租車GPS數據集是我們實驗中所使用的數據集,是實驗分析的對象.Sklearn開源庫處理平臺是實驗中所使用的主要開源算法平臺.算法處理器用于在Sklearn開源庫處理平臺上預測波爾圖出租車GPS數據集的目的地和抵達時間.

圖1 系統(tǒng)總體結構圖

算法處理器包括回聲狀態(tài)網絡算法和隨機森林算法.其中,回聲狀態(tài)網絡算法先對預處理過的波爾圖出租車GPS訓練集進行訓練,更新儲備池狀態(tài),接著導入測試集進行測試預測出該數據集出租車的目的地,輸出的數據是WGS84坐標.隨機森林算法將從原始訓練樣本集N中有放回地重復隨機抽取k個樣本生成新的訓練樣本集合,然后根據自助樣本集生成k個分類樹組成隨機森林,新數據的分類結果按分類樹投票多少形成的分數而定.接著導入測試集進行測試預測出該數據集出租車的抵達時間,輸出的數據是抵達目的地所要花費的時間.

提出的系統(tǒng)工作流程如圖2所示,對波爾圖GPS出租車數據集進行預處理抽取我們所需的特性,并對數據集進行分割.在Sklearn開源處理平臺使用算法處理器預測數據集中出租車的終點和抵達時間,將結果分別導出到兩個.cvs文件中,分別記錄出租車旅程的目的地和抵達時間.

圖2 系統(tǒng)工作流程圖

2 波爾圖出租車 GPS 數據集

2.1 數據集描述

本文使用了波爾圖出租車GPS數據集,該數據集是公開的,也是Kaggle競賽官方使用的數據集,故本文使用該數據集進行實驗.原始數據集中具體的屬性有:TRIP_ID(旅行編號),CALL_TYPE(調度類型),ORIGIN_CALL(來電詳細信息),ORIGIN_STAND(出租車站),TAXI_ID(出租車編號),TIMESTAMP(旅行開始時間戳),DAY_TYPE(日期類型),MISSING_DATA(丟失數據),PLOYLINE(旅行折線信息).PLOYLINE是一系列GPS坐標,每次坐標都是在旅程開始后的每15 s 記錄一次,并且以上車開始,以下車結束.這些數據并無法直接用于出租車目的地和抵達時間的預測,而需要進行一定的數據處理后方能使用,以此獲得旅行目的地和抵達時間,上車坐標(起點緯度,起點經度)和下車坐標(終點緯度,終點經度).我們將這個數據集稱為波爾圖出租車GPS數據集.

2.2 數據集分割

1)分割的腳本命令:

2)把原來 1.80 GB 的 train 數據集分割成每個 200 MB的數據集并對其批處理重新命名:

2.3 數據集預處理

每個數據樣本對應一個完成的行程.它有9列的字段,其中我們只使用:

1)TRIP_ID(String):它包含每個行程的唯一標識符.

2)POLYLINE(String):它包含映射為字符串的GPS坐標(即WGS84格式)列表.字符串的開始和結尾分別用括號(即“[”和“]”)標識.每對坐標也由與[LONGITUDE,LATITUDE]相同的括號確定.該列表包含每15 s行程的一對坐標.

這樣做的好處是能夠減少冗余的字段,加快實驗中程序運行的速度,在比較有限的時間中得出實驗的結果.

3 基于回聲狀態(tài)網絡算法預測目的地

3.1 預測流程

圖3 回聲狀態(tài)網絡算法預測目的地流程圖

經過預處理的波爾圖GPS出租車數據集在算法處理器中完成出租車目的的預測.預測流程主要包括3個階段:預處理過程、訓練數據集和測試數據集.

3.2 評估指標

該系統(tǒng)的評估指標是平均Haversine距離(MHD).橫坐標距離通常用于導航,它根據緯度和經度來測量球體上兩點之間的距離.在兩個位置之間可以計算如下:

其中 ?是緯度,λ是經度,d是兩點之間的距離,r是球體的半徑,在我們的情況下,應以所需度量(例如6371公里)的地球半徑代替.

3.3 算法描述

回聲狀態(tài)網絡采用“儲備池”代替?zhèn)鹘y(tǒng)神經網絡[6]的隱層.“儲備池”是ESN的核心結構,它由大量稀疏連接的神經元組成,并將輸入信號從低維空間映射到高維空間,唯一需要訓練的參數即為輸出權值矩陣.這些特點大大簡化了回聲狀態(tài)網絡的訓練算法和求解過程.

ESN是一種特殊類型的遞歸神經網絡,其基本思想:使用大規(guī)模隨機連接的遞歸網絡,取代傳統(tǒng)神經網絡中的中間層,從而簡化網絡的訓練過程.

基于圖4的結構,我們可以看出回聲狀態(tài)網絡是一種典型的三層遞歸神經網絡,由輸入層、儲備池、輸出層構成.

圖4 回聲狀態(tài)網絡結構圖

則回聲狀態(tài)網絡狀態(tài)方程為:

其中 W 為儲備池內部神經元連接權值矩陣,Win為輸入單元與儲備池內部連接權值矩陣,Wout為儲備池與輸出單元連接權值矩陣,Wback為輸出單元與儲備池的連接權值矩陣,表示儲備池神經元激活函數,通常情況下取做雙曲正切函數.表示輸出函數.特殊情況下,foiut(i=1,2,···,L)取恒等函數.在網絡的訓練中,連接到儲備池的連接權值矩陣 Win,W,Wback隨機產生,一經產生就固定不變.而連接到輸出單元的連接權值矩陣 Wout需要經過訓練得到.

3.4 模型建立

考慮到共享共同后綴的旅行導致近似或相同目的地的軌跡的內在馬爾可夫性,我們可以選擇使用回聲狀態(tài)網絡算法.

模型中有一個偏置單元和輸入到讀出的連接.

圖5 回聲狀態(tài)網絡模型

ESN使用具有泄漏集的離散時間連續(xù)值單元的遞歸神經網絡(Recurrent Neural Networks,RNN)類型.一般的更新方程如下[7]:

其中x(n)∈RNx是儲備池神經元激活的向量,是對其的更新,所有在時間步長n的情況下,tan h(·)都被應用于元素,[·;·]表示垂直向量(或矩陣)級聯,1表示偏置輸入,W in ∈RNx×(1+Nu)和 W ∈RNx×Nx分別為輸入和反復權重矩陣,α ∈(0,1]是泄露率,除了之外,還可以使用其他S形外包裝,然而這是最常見的選擇.

該模型有時被使用時沒有泄露集,這是因為 α=1,故x?(n)=x(n)的特殊情況.

線性輸出層的計算公式如下:

其中y(n)∈RNy是網絡輸出,Wout∈RNy×1+Nu+Nx是輸出權重矩陣.[;;]還是代表垂直向量(或矩陣)級聯.

Wout訓練是根據嶺回歸進行的,公式如下:

給定收集的目標總數Ytarget∈RNy和X∈R1+Nu+Nx,用于符號簡化的X表示[1 ;U;X],這考慮到偏置(1),輸入(u)和儲備池(x)的讀數的連接.它們都有助于輸出,所以它們必須被收集為x.

1)訓練階段

對于每個波爾圖出租車GPS訓練序列:

步驟1.運行神經網絡,從網絡狀態(tài)x(0)=0開始,解除初始瞬態(tài)(沖洗),并用訓練輸入u(1)···u(N)更新網絡.

步驟2.對于每個時間戳n,將儲層狀態(tài)x(n)收集到X,目標值收集到Ytarget.

步驟3.沖洗是作為每個軌跡的一小部分.即0.2=用于沖洗的旅行點的20%.

然后通過公式(8)計算出輸出權重Wout.

當是處理大量數據而不是收集所有狀態(tài)時,矩陣YtargetXT和XXT可以逐個計算,一次一個模式.因為每個模式都需要一個矩陣加法和一個外部積,所以成本增加,但是當計算Wout時,我們已經計算了矩陣乘積.計算公式如下:

YtargetXT和XXT的尺寸分別為(Ny×Nx)和(Nx×Nx).如果我們考慮到目前為止所描述的架構,并將連接輸入和偏置的x重寫為[1;U;x],Nx變?yōu)?1 +Nu+Nx).

2)測試階段

對于每個波爾圖出租車GPS測試序列

步驟1.從網絡狀態(tài)開始,解除初始瞬態(tài)(沖洗),并用公式(8)計算預測輸出.

步驟2.收集每個序列的預測輸出和目標值,如果要跟蹤可以按序列訪問的方式收集預測輸出的行為.

步驟3.在預測期間,輸入是相應地采用凈預測模式:生成/預測.

步驟4.輸出波爾圖出租車GPS測試集中每段旅程對應的目的地,輸出的數據是WGS84坐標.

3.5 參數選擇和評估

選擇通過網格搜索進行優(yōu)化的參數有:

1)Nr,儲備池規(guī)模大小;

2)rho 或 sigma,光譜半徑或最大奇異值;

3)α,泄漏率;

4)Lambda,嶺回歸正則化參數;

5)Conn,連接因子,默認情況下為 100%.

參數的每個組合定義了一個模型,而模型又在驗證集上進行了評估.可以通過交叉驗證獲得更準確的評估,并在所有折疊上使用具有最小平均驗證誤差的模型.

另一個限制是隨機發(fā)生器種子是固定的;應該從不同的種子開始進行全網搜索,從而可以生成不同的網絡權重.通過多次實驗進行比較分析得到網絡搜索的最佳參數情況如表1.

表1 網絡搜索的最佳參數

4 基于隨機森林算法預測抵達時間

4.1 預測流程

經過預處理的波爾圖GPS出租車數據集在算法處理器中完成出租車目的的預測.預測流程主要包括兩個階段:訓練數據集抽樣預處理、測試數據集.

4.2 評估指標

對于行程時間,使用均方根誤差(RMSLE)評估預測,定義如下:

這里的n是測試數據集的總觀測值,pi是觀測值,ai是旅行時間的實際值,ln是自然對數.

4.3 算法描述

隨機森林中的每一棵分類樹為二叉樹,其生成遵循自頂向下的遞歸分裂原則,即從根節(jié)點開始依次對訓練集進行劃分.在二叉樹中,根節(jié)點包含全部訓練數據,按照節(jié)點純度最小原則,分裂為左節(jié)點和右節(jié)點,它們分別包含訓練數據的一個子集,按照同樣的規(guī)則節(jié)點繼續(xù)分裂,直到滿足分支停止規(guī)則而停止生長.若節(jié)點上的分類數據全部來自于同一類別,則此節(jié)點的純度I(n)=0,純度度量方法是 Gini準則,即假設P(Xj)是節(jié)點n上屬于Xj類樣本個數占訓練.

圖6 隨機森林算法預測抵達時間流程圖

具體算法實現過程如下:

步驟1.原始訓練集為N,應用自助法(bootstrap)有放回地隨機抽取k個新的自助樣本集,并由此構建k棵分類樹,每次未被抽到的樣本組成了k個袋外數據.

步驟2.設有mall個變量,則在每一棵樹的每個節(jié)點處隨機抽取mtry個變量(mtrynmall),然后在mtry中選擇一個最具有分類能力的變量,變量分類的閾值通過檢查每一個分類點確定.

步驟3.每棵樹最大限度地生長,不做任何修剪.

步驟4.將生成的多棵分類樹組成隨機森林,用隨機森林分類器對新的數據進行判別與分類,分類結果按樹分類器的投票多少而定.

4.4 抽取特征預測抵達時間

用于時間預測的一組特征與目的地預測的特征集非常相似,差異在于將最近旅行的抵達時間視為目標變量而不是目的地.為此提取的特征如下:

a)旅行時間和10個最鄰近的Haversine距離.

b)內核回歸特征.

除了前面描述的從部分觀察到的行程中提取的所有特征之外,我們還考慮了直接從觀察到的不完全行程中提取的以下附加的時間預測特征(即仍在進行的行程):

a)在迄今為止觀察到的部分軌跡的最后d米和整個不完全行程上計算的平均速度,其中d∈{10,20,50,100,200}.這些功能在進行預測時傳達最新的交通狀況.

b)到目前為止觀察到的不完整旅行的最后d米的平均加速度,其中d∈{10,20,50,100,200}.

c)形狀復雜度:(歐幾里德)行進距離與第一個和最后一個GPS位置之間的Haversine距離之間的比率.具有更高復雜性的旅行(例如“z -zag 之旅”(zig-zag trips)往往是出租車司機在城市周圍開車尋找乘客的行程.z-zag的旅行時間往往較長,所以事先確定這些行程是合理的.

d)通過計算任何一對連續(xù)GPS更新之間的速度來識別GPS蹤跡中的缺失值.如果估計的速度超過速度限制km / h,即使在部分觀察到的行程中只有一對連續(xù)的GPS更新,該行程被標記為缺少GPS更新的行程.我們使用速度限制少值的旅行往往有更長的旅程時間.

總的來說,得出66個特征來預測出租車旅程的抵達時間[8].,缺

5 檢測結果分析

本系統(tǒng)檢測算法在Sklearn開源庫處理平臺上編寫,操作系統(tǒng)為Windows10,服務器CPU配置為Intel Core i5-5200U 2.2 GHz,每臺節(jié)點為 8 GB 內存.還有一些核心包包括:Numpy,Scipy,Pandas,Matplotlib.

5.1 出租車目的地預測實驗結果

出租車數據集包含 1 710 670 次旅行,從 01/07/2013到24/06/2014,其中一些是空的或缺失值,我們在預處理時去除空軌跡,但一些缺失值不會影響實驗結果.

如圖7是數據集中的200 016條訓練集的終點.

圖7 部分訓練集終點

對于該實驗,只使用每個行程的軌跡折線,丟棄其他特征和空軌跡.折線在0-1與最小 -最大歸一化之間進行歸一化;也可以使用Z分數歸一化.這樣可以限制數據集的范圍,并且保證程序運行時收斂加快.

目標是軌跡的最后一點,它被分配為每個點的目標.因此,網絡被訓練用來預測每個前綴軌跡的終點.

表2 算法模型 MHD 值對比

表2為本算法模型的MHD值結果比較.抵達目的地預測評價指標為平均Haversine距離(MHD),回聲狀態(tài)網絡算法(ESN)計算結果為2.612 19.該值越小越好,故ESN算法相對較好.

如表3是測試集中各段旅程目的地坐標預測的部分結果,包括旅行ID,經緯度的坐標,共有327條預測結果.

表3 測試集中各旅程的目的地坐標

5.2 出租車抵達時間預測實驗結果

表4對本算法的抵達時間預測和GBRT和ERT進行了性能分析.評價指標為RMSLE,可以發(fā)現隨機森林算法計算結果為0.416 74.該值越小越好,故RF算法相對較好.

表5是測試集中各段旅程抵達目的地所需花費時間的部分結果,包括旅行ID,旅行時間,共有327條預測結果.總體表明:提出的預測系統(tǒng)可以較好的完成出租車的多項關鍵信息預測,有較好的實用價值.

表4 算法模型RMSLE值對比

表5 測試集中各旅程抵達目的地的所需花費時間

6 結語

出租車公司以及近年來興起的一批打車平臺在進行車倆的動態(tài)調度時,都需要掌握每個車倆出行終點和抵達時間的信息.如果車倆調度員能夠知道出租車完成當前出行的終點和抵達目的地所需時間,就可以為下一個乘車需求分配距離最近且時間點最契合的車倆.尤其是在城市的中心地帶,出租車抵達的目的地附近往往就有新的乘車需求.因此,對車倆目的地和抵達時間的預測具有實際的應用價值和廣泛的應用市場.本文提出了基于機器學習的智能交通預測系統(tǒng),可大致預測出租車的終點和抵達時間.不足之處在于實驗過程中,因為電腦設備的問題,波爾圖出租車GPS數據集實在是太大了,只抽取了部分的訓練集來訓練,所以測試集得到的目的地和抵達時間結果有可能不夠精確.但總體來說這兩種算法還是較符合我們實驗的要求,整體上性能和效果也是挺不錯的.