基于卷積神經網絡的移動對象目的地預測

江 婧,張懷峰,皮德常

(南京航空航天大學 計算機科學與技術學院,南京 211106)

1 引 言

隨著移動傳感器(如手機,GPS)的普及,人們越來越多地受益于各種基于位置的服務.移動設備所配備的位置傳感器利用全球定位系統精準的提供了用戶的位置,不同時間戳的位置形成用戶的日常活動軌跡.這種軌跡數據具有高度時間和空間規律,為許多基于位置的應用的出現和改進提供了數據來源.大量新型的基于位置的應用都需要對目的地和未來路線進行預測,例如,推薦旅游景點,獲取用戶可能感興趣的附近場所,基于目的地發送針對性的廣告等.此外,文獻[1]和文獻[2]還將目的地預測應用于判斷是否偏離了預定路線、捕捉汽車盜賊.

目的地的預測通常需要使用到歷史軌跡,如果所要查詢的軌跡與歷史軌跡中出現的某一部分相匹配,那么這部分軌跡的目的地很可能也是所查詢軌跡的目的地.貝葉斯模型[3-5]和馬爾科夫模型[6,7]一直以來被廣泛應用于目的地預測,此外,文獻[8]從軌跡中學習相關的移動模式構建出T-pattern決策樹,通過從樹中查找最佳匹配路徑來預測新軌跡的下一個位置.文獻[9]提出了一種最近鄰軌跡(NNT)技術,識別與當前車輛部分軌跡最相似的歷史軌跡,然后根據歷史軌跡來預測車輛未來的移動.文獻[10]首先對歷史軌跡進行聚類,隨后將擬查詢軌跡分配到最可能屬于的簇,通過學習簇內軌跡的特征來對目的地進行預測.

盡管上述方法通過對歷史軌跡模式的學習,有效地實現

1https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i

目的地預測,但都忽略了預測過程中“數據稀疏問題”所帶來的影響.也就是說,由于現有數據集中歷史軌跡數量有限,所要查詢的路線很難與歷史軌跡完全匹配,相同的目的地可能通過不同的路徑所到達;即使查詢軌跡與歷史軌跡的一部分完全匹配,目的地也很可能不同.

為了解決數據稀疏問題,一些學者借助外部信息來改善預測效果,如結合道路網絡信息和車輛行駛信息,根據道路結構和走向以及行駛速度進行分析,或根據用戶歷史信息確定其個人喜好從而對目的地進行推薦[3,11,12].由于有時并不能準確地獲取這些信息,Xue等人在未使用外部信息的情況下,提出了SubSyn[13]及其改進算法[5,14],將歷史軌跡分解成由兩個相鄰位置構成的子軌跡,子軌跡被重構形成合成軌跡,然后建立馬爾可夫模型量化相鄰位置之間的相關性,該過程可有效擴展歷史軌跡數據集的數量.Wang等人[11]基于最優化理論中的梯度下降原理,提出MGDPre算法,通過分析查詢軌跡采樣點位置與最終目的地之間的距離變化,實現對稀疏軌跡集的目的地預測.Li等人[15]構建鏡像吸收馬爾科夫鏈模型對軌跡進行建模,并引入上下文感知張量分解方法,有效解決了目的地預測時的軌跡稀疏問題.

此外,大部分文獻都將軌跡數據作為一維的時空點序列進行分析.這樣的一維結構雖然簡潔,但在一定程度上限制了從中了解其他詳細的信息.在一維軌跡序列中,只能獲取各個時間點移動對象的位置信息,以及軌跡點的先后關系,并不能了解軌跡在平面圖上的整體形態,也無法看出移動對象何時拐彎、何時繞行等.正如常言道,“一圖勝千言”.本文將一維軌跡序列轉換為二維像素圖像,利用這種可視化的方式向人們更清晰地展示了軌跡的整體走向和終點位置,通過挖掘軌跡圖像的空間特征來確定目的地的位置.

本文使用Kaggle-ECML/PKDD競賽數據集1,并與該競賽冠軍團隊的預測結果[16]進行對比.競賽獲勝團隊通過構建多層感知機(MLP)實現對目的地坐標的預測,他們選取軌跡前5個點和后5個點的經度和緯度,結合駕駛員ID、客戶信息等其它相關信息,以一維向量的形式輸入MLP,最終以Custom Test=2.81,Kaggle Public=2.39,Kaggle Private=1.87的測試誤差獲得第一名.但是,競賽方法的輸入向量所含信息量有限,僅將起點和終點附近5個GPS點經緯度轉換為兩個一維向量,雖然結合了其他信息,仍舊不能很好的表示軌跡的特征,這對最終的預測精度造成了一定的影響.

本文針對以上缺點和限制,基于卷積神經網絡(CNN)實現了移動對象目的地的準確預測.文章的主要貢獻如下:

·本文將一維軌跡序列轉換為二維像素圖像,通過構建CNN來實現特征的提取和目的地預測.不同于傳統文獻中直接對一維軌跡序列進行分析,本文從二維像素圖片中可以獲取更多空間模式和移動對象運動的細節信息,CNN從圖像中提取出的高階特征更有助于之后的預測任務.

·“數據稀疏”作為目的地預測中最常見的問題,在很多文獻中都沒有得到很好的解決.本文在對軌跡數據進行處理的過程中,先后引入PMDL和PRT算法,有效地克服了目的地預測時的數據稀疏問題.

·本文未將完整的軌跡圖像直接輸入模型進行學習,而是先對局部特征的重要程度進行分析,然后截取重要特征附近區域作為模型的輸入.本文對重要特征區域的大小進行了探討,并找到最佳局部特征范圍,在一定程度上提高了預測的準確率.

文章后續內容由以下幾部分組成,第二部分給出了相關術語定義和問題陳述,第三部分詳細介紹本文的模型方法,第四部分呈現了實驗設置和實驗結果,第五部分對文章進行了總結和展望.

2 問題定義

本節定義了相關術語和需要解決的問題.

問題1.數據稀疏問題

數據稀疏問題是在實現目的地預測時很常見的問題之一.在將查詢軌跡與歷史軌跡進行匹配時,現有的歷史軌跡遠遠不足以覆蓋所有可能的查詢軌跡,從而影響對軌跡目的地位置預測的精度.數據稀疏性可能由以下幾種原因造成:

第一,數據集中給出的歷史軌跡數量有限,只能覆蓋一部分所要查詢的軌跡.例如,已知歷史軌跡tra1:A→B→C,tra2:A→D→E→F,tra3:A→D→E→G.當查詢tra4:A→B時,它與tra1的一部分完全重合,可以認為它的目的地很可能與tra1相同,即目的地為C;當查詢tra5:A→D→E時,它和tra2,tra3的其中一部分都相同,因此它的目的地可能是F也可能是G.

第二,在劃分網格上表示軌跡數據時,由于二維空間數據的多尺度特性,在不同尺寸的網格圖中,軌跡會呈現出不同的模式.如圖1所示,可以明顯地看出不同尺寸的網格中各軌跡的形態有明顯差異.在圖1(a)較小的尺寸下,各軌跡的細節信息變得更加顯著,導致軌跡重疊程度較低,幾乎不能保證查詢軌跡與歷史軌跡中的某部分完全重合.在圖1(b)較大的尺寸下,所有軌跡的細節被縮小,軌跡重疊程度增加,對目的地預測造成了很大的難度.因此,網格尺寸也會導致數據稀疏問題.

圖1 不同尺寸網格下的軌跡形態Fig.1 Trajectory patterns in different size of grid

第三,當每條軌跡的采樣頻率不同時,有些軌跡的特征表示非常詳細,但有些軌跡卻表示的過于簡略.即使兩段軌跡的起點和終點相同,由于特征表示的詳細程度不同,網格圖像上表示出來的路線也很可能有很大的差異.

為了解決以上情況導致的“數據稀疏問題”,本文首先對軌跡進行分段表示,在保留原始信息的同時,最大程度降低相似軌跡之間的差異;然后用盡可能小的網格將軌跡表示成像素圖片,以免丟失大量細節信息.具體算法見3.1和3.2節.

問題2.軌跡目的地預測問題

預測任務要求根據測試集給出的不完整的軌跡段,來預測可能的目的地坐標.這很容易聯想到直接對經度和緯度這一對數值進行預測.當使用神經網絡解決這類問題時,這意味著輸出層由兩個神經元組成.然而,由于模型的輸入所含信息量有限,僅根據現有的信息,很難對目的地坐標直接進行計算.

為了解決這個問題,本文為所有軌跡圖像增加標簽,將對原始不帶標簽的軌跡目的地預測問題,轉化成一個有監督的軌跡分類問題,這在一定程度降低了直接對坐標進行預測的難度.具體見3.2節.

3 基于CNN 的目的地預測

目的地的預測通常需要使用歷史軌跡,當所要查詢的軌跡與歷史軌跡中的某一部分相匹配時,可以認為這部分軌跡的目的地很可能也是所查詢軌跡的目的地.由第2節對問題1的描述可知,數據集中軌跡數量有限,網格的尺寸和軌跡的采樣頻率影響了軌跡表示之間的差異,這些都限制了對軌跡的有效匹配.但是,數據集的樣本量以及軌跡的采樣頻率都不由實驗者決定,找到最優網格尺寸也并不是一件容易的事情.即使找到了最優網格尺寸,由于每條軌跡本身的總采樣點數目就不是很多,用像素圖像表示軌跡時也很可能丟失大量信息.

圖2 基于CNN的目的地預測流程Fig.2 Overview of destination prediction based on CNN

本文按照圖2的流程,在解決了上述“數據稀疏問題”,防止大量信息丟失的同時,對軌跡目的地進行了準確預測.首先,引入參數化最小描述長度策略(PMDL)對原始軌跡進行最優分段表示,在最大程度保留原始軌跡特征的情況下,減少相似軌跡之間的差異性并增加不同軌跡之間的差異程度,具體見3.1節;隨后,提出軌跡的像素化表示方法(PRT),將原始軌跡數據處理成像素圖片,截取其起點和終點附近的區域作為輸入,并增加類別標記,具體見3.2節;最后,使用CNN對軌跡圖片進行特征提取和目的地預測,具體見3.3節.

3.1 軌跡的分段表示

軌跡分段即從一條軌跡ti=p1p2…pj…pleni中找出特征點集,也就是軌跡某一處變化很大的點的集合,通過連接相鄰的兩個特征點形成軌跡的分段表示.最優的軌跡分段要求同時具有精確性和簡潔性.

文獻[17]提出使用最小描述長度(Minimum description length,MDL)原理來找到最佳分段方案.MDL原理包含兩個部分:L(H)和L(D|H).其中H是假設,D是數據.L(H)用來描述假設的長度,L(D|H)是在假設為H的情況下對數據D進行編碼后,數據D編碼的長度.當L(H)與L(D|H)的和最小時,此時H是能夠解釋數據D的最佳的假設.

在本文的軌跡分段中,原始軌跡相當于MDL原理中的數據D,對原始軌跡的分段相當于MDL原理中的假設H,找到最佳軌跡分段即為找到一個使L(H)+L(D|H)最小的軌跡分段.考慮到實際應用對精確性和簡潔性有不同的要求,當軌跡數據量較小時,通常要求簡潔性低而精確性高;當數據量較大,通常要求簡潔性高而精確性低.此外,按照MDL原理只能找到一個使L(H)+L(D|H)較小的近似軌跡分段,因此本文對MDL進行改進,提出了參數化最小描述長度策略(Parameterized Minimum Description Length,PMDL).

PMDL以uL(H)+vL(D|H)代替L(H)+L(D|H),即找到一個分段,使得uL(H)+vL(D|H)(u,v≥0,且u,v為實數)最小,則該分段就是最佳分段.L(H)和L(D|H)分別由公式(1)、公式(2)給出.當u/v>1 時,得到的最佳分段簡潔性較高,考慮極端情況,當u/v→∞,即v=0時,此時得到的軌跡分段即為原始軌跡起點和終點的連線,這種情況下簡潔性最高而精確性最低;當u/v<1時,得到的最佳分段精確性較高,考慮極端情況,當u/v=0即u=0時,此時得到的軌跡分段即為原始軌跡,這種情況下精確性最高而簡潔性最低.根據上述分析,可以根據具體需要來調整u,v的大小,使軌跡分段的簡潔性和精確性滿足需求.

(1)

(2)

將圖Gi視為軌跡ti中所有點組成的一個無向完全圖,其中邊pipj的權重w(pipj)由uL(H)+vL(D|H)計算得出,則求最佳分段相當于求圖Gi中以p1為起點,pleni為終點的最短路徑,即該最短路徑就是對該軌跡的最佳分段.因此,可以使用著名的Dijkstra算法求得最佳分段.圖3展示了將最佳分段問題建模為最短路徑問題的一個示例.

圖3(a)為一條包含了4個點的軌跡,任意給定該軌跡的兩個點,都可以求出這兩點的L(H)和L(D|H).因此,對于圖3(b)中的無向完全圖,每條邊上的權重L(H)+L(D|H)都可以計算出.從而,根據PMDL求出的最佳分段,也就是圖3(b)中無向完全圖從點p1到點p4的最短路徑.

根據上述思路,本節對原始軌跡進行了最佳分段表示,削弱了相似軌跡之間的差異性,同時也保留了原始軌跡的重要特征.

3.2 從一維軌跡到二維圖像

根據上一節提出的PMDL算法,得到了原始軌跡的最優分段表示.在沒有相應道路網絡信息的情況下,為避免上文所述的數據稀疏問題,本小節進一步對分段表示的軌跡進行處理,用盡可能小尺寸劃分的網格將其表示成黑白像素圖片,作為最終的模型輸入.這樣不僅在一定程度上克服了軌跡數據稀疏,還減少了圖像轉換過程中的信息丟失.

圖3 PMDL將最佳分段問題建模為最短路徑問題的示例Fig.3 An example of trajectory segmentation problem and the corresponding shortest path problem

算法.Pixel Representation of Trajectory(PRT)

輸入:軌跡數據trai,j

網格邊長L

輸出:軌跡的像素矩陣G

5.forallk=1 ton-1do

//vis the direction vector of X axis

7.s=L

11.s=s+L

16.end

17.endfor

18.G=zeros(M,M)

21.G(cx,cy)=1

22.endfor

23.returnG

3.3 局部圖像提取和標簽添加

為了實現目的地預測,通常需要通過學習歷史軌跡的特征,來對未知軌跡進行匹配,從而確定查詢軌跡的最終目的地坐標.當查詢軌跡與歷史軌跡進行匹配時,可能存在以下幾種情況:

1)整條查詢軌跡段與歷史軌跡的某一部分完全相似,目的地很可能相同;

2)查詢軌跡段與歷史軌跡的出發點附近或者中間部分相似,但最終的目的地不同;

3)查詢軌跡與歷史軌跡前端部分不同,但終點附近軌跡相似,目的地可能相同.

考慮以上三種情況,直接將數據集中整段軌跡的圖像輸入到分類器中進行學習是不合理的,終點相同的兩條軌跡,其整體相似度不一定很高;反之,相似度較高的兩條軌跡目的地未必相同.

這很容易聯想到,從軌跡中提取出對最終預測結果影響較大的部分,而不是將整段軌跡作為特征輸入到模型中進行學習.文獻[18,19]通過可視化卷積網絡,獲取了不同層卷積所捕獲的軌跡圖像特征的具體含義,并得出靠近軌跡起始點和終點的局部區域對預測結果有更大決定作用的結論.起始點在某種程度上顯示出旅途的動機;靠近終點的軌跡顯示目的地的趨向.因此,本文選擇將軌跡起點和終點附近的局部區域圖像作為最終的輸入圖片.

正如第2節問題2所描述,預測任務要求在已知部分軌跡段的情況下,預測出該軌跡的最終目的地坐標.最直接的想法是對經緯度這一對數值進行預測,這在神經網絡中意味著輸出層由兩個神經元組成.由于模型輸入的信息量有限,這種方法給預測工作帶來了非常大的難度.受到競賽冠軍方法的啟發,本文采用了一種不同于傳統的目的地預測問題的方法,首先對訓練集軌跡終點進行mean-shift聚類,將每個簇的聚類中心作為該簇中所有軌跡的目的地坐標,相當于為每條軌跡加上標簽;然后對查詢軌跡進行有監督訓練.這樣就避免了直接對目的地坐標的預測,將無標簽的軌跡終點預測問題轉換為有標簽的分類問題,在一定程度上降低了預測難度,提升了算法的可行性.

值得注意的一點是,在競賽冠軍方法中,數據集中所有軌跡的終點被劃分成3392個簇.但是,劃分的簇的數量多并不意味著預測效果就好,文獻[10]通過實驗驗證了這一點,并找到了最佳劃分的簇數應為45.因此,本文將45作為軌跡目的地聚類的簇數.

3.4 基于CNN的預測模型

近年來深度學習在圖像識別、語音識別、目標檢測、自然語言處理等領域取得了巨大的成功,但是很少有學者將其應用到軌跡數據的處理尤其是目的地預測的問題上.卷積神經網絡(Convolutional Neural Networks,CNN)作為一種深度學習模型,它集特征提取與分類于一體,使用多個卷積層和池化層從訓練數據中自動提取復雜的高維特征,然后對其進行分類.

圖4 基于目的地預測的CNN模型結構圖Fig.4 Structure diagram of destination prediction based on CNN

本文設計了一個簡單的CNN結構,如圖4所示,由兩層卷積層,兩層池化層,兩層全連接層和一層輸出層組成,其中每個池化層直接連接在卷積層之后.詳細參數如表1所示.輸入是大小為60×60的雙通道軌跡圖片,分別代表起點和終點附近所截取的區域.輸入圖片經過卷積層Conv1大小為5×5,步長為1的卷積核處理,得到16個大小為56×56的特征映射.池化層MaxPool1通過大小為2×2,步長為2的過濾器,使用最大池化提取出最顯著的特征.后兩層Conv1,MaxPool1的操作與前兩層相同.最終提取的特征依次與包含100個神經元和50個神經元的兩層全連接層FC1,FC2相連接,最后通過一個Softmax函數區分出各個類別.

表1 CNN相關參數取值
Table 1 Values of related parameters in CNN

Layer NameNo.of neuronsKernel size for each feature mapStrideInput Lay-er60×60×2--Conv156×56×1651MaxPool128×28×1622Conv224×24×3251MaxPool212×12×3222FC1100--FC250--

4 實驗及分析

4.1 數據集設置

本文的實驗數據來源于Kaggle-ECML/PKDD競賽中的真實軌跡數據集.該數據集提供了442輛出租車在葡萄牙波爾圖市一整年(01/07/2013-30/06/2014)的行車軌跡.這些出租車均安裝了移動數據終端,精確的定位了他們在不同時間戳的坐標.訓練集包含了170萬個樣本點,每一個樣本都對應一個完整的行程,共包含了了客戶信息、客戶請求服務的方式、乘車站臺、節假日等9個屬性.為了使本文提出的方法對大多數軌跡數據集都具有適應性,本文僅使用各個時間戳對應坐標值所組成的軌跡來實現目的地預測.

為了使預測結果更具說服力,本文采用和文獻[16]相同的劃分方式,從訓練集中隨機選取19427條軌跡作為驗證集,19770條軌跡作為測試集,其余的作為訓練集.本文同樣使用Haversine距離來評價預測目的地與真實目的地之間的距離.Haversine距離根據緯度和經度測量球面上兩點的距離,其公式定義如下,λx,Φx分別為點x的經、緯度,R是地球半徑:

(3)

其中：

(4)

4.2 輸入圖片的大小確定

為了確定合適的輸入圖片大小,本文從起點和終點附近截取不同尺寸的區域作為輸入,分別輸入模型進行預測.截取區域的方法如下:分別以軌跡起點和終點為圓心,軌跡長度的N%為半徑R畫圓,并以包含該圓的最小矩形區域為輸入圖片.也就是說,當該圓的外切矩形恰巧包含了完整的方格時,取該外切矩形區域作為輸入;如果外切矩形包含不完整的小方格,那么就以最小的長度增加矩形邊長,使之恰巧包含完整的方格.隨后,將所有軌跡被截取的區域處理成相同大小的圖片,就得到了最終輸入的軌跡圖像.圖5為從一條軌跡中所截取的不同大小區域圖片的示意圖,截取后的兩部分作為一個雙通道的圖像輸入CNN模型中.

圖5 軌跡中截取的三種不同大小區域圖片的示意圖Fig.5 Three different size of regions in trajectory

通過截取起點和終點附近不同大小的區域,并將它們輸入到CNN中對目的地進行預測,得到不同大小區域作為輸入對應的預測誤差,如表2所示.從表2中可以看出,截取長度過長或過短都是不合適的,當截取的部分太短(R=10%,20%)時,獲取的信息不足以對軌跡進行有效預測,當截取的部分太長(R=50%)時,相當于把原始軌跡分割成兩段作為輸入.通過對預測誤差的對比可知,當以軌跡長度25%的比例截取起點和終點附近的區域作為輸入時,表現效果相對最好,本文將其作為本文的最終截取比例,并將最終輸入圖片大小設置為60×60.

表2 不同大小輸入圖片對應的預測誤差
Table 2 Prediction errors in different size of input

R=N%10202530354050誤差(105km)3.552.891.982.072.533.293.87

4.3 模型的訓練與測試

模型每個訓練批次的樣本個數為60,訓練輪數為400,正則化參數,學習率和動量參數分別設置為0.2,0.001和0.7.訓練過程中誤差隨著訓練輪數增加而逐漸減小,500輪訓練之后,訓練誤差和驗證誤差都達到穩定,此時模型訓練完畢.

為了驗證所提出方法的有效性,同時便于與其他文獻結果進行比較,本文采用兩種方法對模型進行測試.

第一種方法是從測試集中提取出的不同比例長度的軌跡前綴,對它們分別進行預測,預測誤差變化如圖6所示.圖中Proposed1是將整段已知軌跡的像素圖片作為輸入訓練模型得到的預測誤差,Proposed2是按上文所述方法對起終點附近區域進行截取,然后訓練得到的預測誤差.從圖6中首先可以看出,已知的軌跡長度越長,對目的地位置的預測越精準.當只獲取很短一部分軌跡時,他們的目的地可能與其匹配的歷史軌跡的目的地相一致,也可能完全不同;然而已知的軌跡段越長,在起點附近的信息和目的地附近的信息提供的信息越多,越有利于對目的地的坐標的確定.此外,將整段軌跡輸入模型進行預的效果并不好,其預測誤差與按照上文方法處理得到的預測誤差相比大很多.

圖6 不同完整度的軌跡所對應的預測誤差Fig.6 Prediction error given different completeness ratio of trajectories

第二種方法是從測試集中按照隨機比例的長度提取軌跡作為測試數據,對他們的目的地進行預測.本文將測試結果與文獻[16]中其他模型的預測結果進行對比,對比結果如表3所示.表中各模型的含義分別如下:其中,模型1是在競賽中取得冠軍的模型,其將軌跡前后各5個點的經度和緯度輸入一個多層感知機(MLP)中,然后嵌入其他屬性,實現對目的地的預測;模型2使用循環神經網絡(RNN)模型,依次讀取軌跡中所有的GPS點,在每個時間步中,用相同的轉換矩陣更新一個固定長度的內部狀態,該模型直接通過最后一個內部狀態來直接預測目的地;模型3使用了雙向RNN,同時正向和反向讀取已知的軌跡前綴,得到起點和終點附近的信息,將其輸入一個MLP中,隨后采取與模型1相同的操作;模型4和模型5都是模型3的變體,前者在每個時間步采用了包含5個連續GPS點的滑動窗口;后者從歷史軌跡中提取出部分候選軌跡,將查詢軌跡和候選軌跡集都編碼成固定長度的向量,通過點乘的方式比較兩者之間的相似性并將該值輸入Softmax函數,以輸出的概率作為每條候選軌跡的終點的權重,從而得到查詢軌跡可能的目的地.

表3 不同模型的預測誤差對比
Table 3 Prediction error of different models

模型測試誤差(105km)1.MLP,clustering(winning model)2.812.RNN3.143.Bidirectional RNN3.014.Bidirectional RNN with window2.605.Memory network2.87Proposed14.62Proposed21.98

Proposed1是將整段軌跡作為輸入得到的預測誤差.

Proposed2是按照25%的比例截取起點和終點部分軌跡作為輸入得到的預測誤差.

表3中Proposed1將整段軌跡作為模型輸入,進行預測的誤差明顯高于Proposed2,這再次驗證了3.2節中所說的:終點相同的兩條軌跡整體相似度并不一定很高,相似度較高的兩條軌跡也未必目的地相同.Proposed2的最終預測誤差為1.98(105km),實現了最低的預測誤差,不論與其他模型還是與冠軍模型的2.81(105km)相比,都有很大的提升.這進一步說明了將模型輸入從一維軌跡數據轉換為二維像素圖像的方法是可取的,本文通過引入PDML和PRT方法來克服數據稀疏是非常有效的.

5 結束語

在實現目的地預測時,現有數據集中的歷史軌跡數量有限,往往不足以覆蓋所要預測軌跡的所有可能,這種現象導致的“數據稀疏問題”會對預測精度造成不良影響.本文通過構建CNN對目的地實現了準確的預測,重點針對預測中的數據稀疏問題提出了相應的解決方法.首先,本文引入PMDL算法,對原始軌跡數據進行最優分段表示,突出軌跡中的重要特征;隨后,提出PRT算法,將軌跡在盡可能小尺寸的網格中表示出軌跡序列的像素圖片形式;接著,截取軌跡圖像的重要特征部位并添加相應的標簽,輸入CNN進行特征提取和目的地預測.本文在真實軌跡數據集上進行了實驗,實現了1.98(105km)的預測誤差,與當前先進模型相比有很大的提升.此外,本文所提出的克服數據稀稀疏問題的方法不僅限于對出租車目的地進行預測,為其他諸如動物遷徙、颶風運動等與軌跡數據相關的預測問題也提供了參考價值.

在未來的工作中,將繼續研究解決目的地預測中數據稀疏問題的方法,力求實現更精準的目的地預測.