王照生，葉群芳，龍 文

（贛州師范高等專科學校，江西 贛州 341000）

一、引言

2015年，ECML/PKDD大會組織了出租車目的地預測挑戰(zhàn)賽，并被認定為Kaggle競賽。在出租車目的地預中，最后一個位置代表目標，不同的軌跡有不同的GPS序列長度。元數(shù)據(jù)與出租車:如果客戶通過電話叫出租車,我們可以獲取一個客戶的標準ID。如果客戶在出租車點叫出租車,我們就獲得一個出租車的標準ID。否則我們沒有客戶的信息識別、出租車的ID和整個行程的開啟時間。在競賽設置中，測試數(shù)據(jù)集由320個部分軌跡組成，這些軌跡是從不同時間拍攝的5個快照中創(chuàng)建的。這個測試數(shù)據(jù)集實際上分為兩個大小相同的子集:公共測試集和個體測試集。在競賽中，使用公共集合來比較模型，而只在最終的排行榜比賽結束時使用個體集合。與其他競爭對手發(fā)布的方法相比，我們的方法很少使用手工設計。整個算法是基于人工神經(jīng)網(wǎng)絡，完全自動化的。

二、建立模型

(一)數(shù)據(jù)分析

在給定出租車軌跡前綴的情況下，采集數(shù)據(jù)預測出租車的目的地。由于數(shù)據(jù)集是由完整的軌跡組成的，我們通過正確的方法來切割軌跡來生成軌跡前綴。所提供的測試數(shù)據(jù)集由超過170萬個完整軌跡組成，這就給出了83480696個可能的前綴。測試前綴的分布盡可能接近最終評估的所提供的測試數(shù)據(jù)集。按照選擇活動的不同日期和時間，這個測試集是通過拍攝5張出租車網(wǎng)絡快照。按照假設，一個軌跡出現(xiàn)在測試集的概率正比于它的長度,為每一個整個測試軌跡,在被選中的測試集中，其所有可能的前綴有相同的概率。因此,生成一個測試集與具有前綴的所有原始測試集的完整軌跡為我們提供了一個具有相同分布的前綴測試集。

(二)多層感知器體系結構

多層感知器(MLP)是一種神經(jīng)網(wǎng)絡，在這種網(wǎng)絡中，給定層的每個神經(jīng)元都與下一層的所有神經(jīng)元相連，不存在任何循環(huán)。它將固定大小的向量作為輸入，并通過一個或幾個隱藏層處理它們，這些隱藏層計算輸入的高級表示。最后，輸出層返回相應的輸入預測。在我們的示例中，輸入層接收出租車帶有前綴的測試數(shù)據(jù)和關聯(lián)元數(shù)據(jù)，輸出層預測出租車的目的地。算法使用了標準的隱藏層，包括矩陣乘法，偏差和非線性。選擇非線性整流器線性單元[1]，它可以簡便地計算出max(0;x)，相對于傳統(tǒng)的s形激活函數(shù)，RLU限制了梯度消失問題，因此，當x為正時其導數(shù)總是1。

（三）目標集和輸出層

由于要預測的目標是由兩個標量值組成，所以算法中設有兩個輸出神經(jīng)元。然而，試驗中發(fā)現(xiàn)很難測試這樣一個簡單的模型，因為它沒有考慮任何關于數(shù)據(jù)分布的先驗信息。為了解決這個問題,可以直接集成目標的先驗知識的體系結構模型，而不是直接預測目標的位置。在幾千目的地集群中心和一個隱藏層，每個集群都有一個標量值(Pi)，我們使用一個預定義的數(shù)據(jù)集(Ci)i。由于網(wǎng)絡必須輸出單個目標位置，因此，對于輸出預測H，只要計算預定義目標集群中心的加權平均:

注釋：這個運算相當于一個簡單的線性輸出層，其權重矩陣將初始化為集群中心，并在測試期間保持固定不變。將隱藏值(Pi)累加到1，使H對應于質心計算，因此我們使用軟max層來計算它們:

其中(Tj)是j前一層的激活,對所有測試軌跡的目標采用均值-移位聚類算法計算聚類(Ci)i，回歸一組C=3392數(shù)據(jù)集。

(四)成本計算與測試算法

競賽評價成本采用Haversine平均距離[2]，定義如下(?x為x點經(jīng)度，λx為x點緯度，R為地球半徑):

其中A(x,y)定義為:

在直接測試Haversine distance函數(shù)時，模型學習能力欠佳，因此我們使用更簡單的等矩形距離，接近所討論城市的規(guī)模:

事先，設定學習率為0.01，動量為0.8，批量為350，然后使用動量隨機梯度下降(SGD)來最小化預測和實際目標點之間的等矩形平均距離。

三、優(yōu)化措施

我們將在本節(jié)中展現(xiàn)模型。在競賽測試集中，模型的特定目標任務沒有得到良好的執(zhí)行。但是，模型可以為涉及固定長度輸出和可變長度輸入的同類問題提供有價值的見解。

(一)循環(huán)神經(jīng)網(wǎng)絡

如前所述，MLP受其固定長度輸入的限制，這使得我們無法充分利用整個軌跡前綴。因此，我們自然地考慮了循環(huán)神經(jīng)網(wǎng)絡(RNN)體系結構，它可以逐個讀取所有的GPS點，在每一步都用相同的轉換矩陣更新一個固定長度的內(nèi)部狀態(tài)。預計RNN的最后一個內(nèi)部狀態(tài)將用特定任務的相關特性總結前綴。由于梯度的消失和爆炸問題，這些周期性出現(xiàn)的體系結構很難測試[3]。長短時記憶單元部分解決了這一問題，是許多藝術架構中用于任務的關鍵組件，包括手寫識別、語音識別、圖像字幕或機器翻譯。我們實現(xiàn)并測試了一個LSTM RNN，它每次讀取一個GPS點的軌跡，從輸入前綴開始到結束。我們對模型進行變體，使其中RNN的輸入不再是單個GPS點，而是前綴的4個連續(xù)GPS點的窗口，窗口在每個RNN時間步上沿前綴移動一點。

(二)內(nèi)存網(wǎng)絡

內(nèi)存網(wǎng)絡最近作為一種體系結構引入，它可以通過檢索和存儲每個預測的相關信息來利用外部數(shù)據(jù)庫[4]。編碼器與我們以前的體系結構是一樣的，只是我們停留在隱藏層，而不是預測輸出。這樣就可以在相同的向量空間中得到固定長度的表示，便于比較。然后利用前綴表示的點積與所有候選表示的點積來計算相似度。最后，使用軟最大值對這些m個相似度值進行規(guī)范化，并用得到的概率來衡量相應候選對象的目標。換句話說，軌跡前綴的最終目的地預測是采用軟最大概率加權來確定候選目的地的質心。

四、實驗結果

(一)定制驗證集

隨機提取原始測試集的部分數(shù)據(jù)，得到新的測試和驗證數(shù)據(jù)集。兩個數(shù)據(jù)集的作用是不同的，驗證數(shù)據(jù)集用于根據(jù)最佳驗證得分對每個模型的測試算法進行終止，而測試數(shù)據(jù)集用于比較不同的測試模型。

(二)結果分析

在實驗的自定義測試數(shù)據(jù)集，各種模型的測試得分優(yōu)于競爭對手。自動預測算法對每個模型的不同的參數(shù)進行了調(diào)優(yōu)。結果表明，嵌入和集群算法顯著改進了實驗模型，嵌入的重要性也可以通過可視化來確認。實驗可以觀察到其中兩個嵌入和清晰模式的二維T-SNE預測，這證明了一年中的幾個小時和幾周是預測的重要特征。算法所研究的所有模型都是密集型的計算，因此我們不得不在多臺CPU上對它們進行運行，以避免在單機上運行數(shù)周。比賽獲勝模式是最密集的計算，預計在CPU上要進行半天時間的運行。另一方面，循環(huán)網(wǎng)絡和記憶網(wǎng)絡的運行速度要慢得多，但是完全是自動運行的，我們相信，通過更長時間的運行，可以獲得更好的競賽得分。

五、結語

基于出租車軌跡的始終和相關的元數(shù)據(jù)，本文引入了一種完全自動化的神經(jīng)網(wǎng)絡方法來預測出租車的目的地。最好的模型是使用一個循環(huán)雙向神經(jīng)網(wǎng)絡來編碼前綴，制作嵌入來編碼元數(shù)據(jù)和采用目的數(shù)據(jù)集群來生成輸出?；跀?shù)據(jù)集群的輸出層有一個潛在限制是，最終的預測僅落在集群的凸區(qū)間中，它的解決方案是將數(shù)據(jù)集群作為循環(huán)雙向神經(jīng)網(wǎng)絡的參數(shù)進行學習，并對它們進行隨機初始化或從均值模糊聚類的數(shù)據(jù)集群中進行初始化。關于記憶網(wǎng)絡，可以考慮更復雜的方法來提取候選對象，例如使用手工設計的相似度度量，甚至記憶網(wǎng)絡學習的相似度度量。在后一種情況下，應該使用已學習到的相似度提取一部分候選對象，以便讓相似度較差的候選對象有機會被選中。此外，可以使用更復雜的函數(shù)，而不是使用點積來比較前綴和候選表示形式。