在大資料時代，位置資料成為各方都亟待挖掘的資料寶藏，比如在城市交通基建規劃、商業選址、線下廣告等場景中，都是以位置資料為重要基礎。但在此過程中，隱私問題一直未得到有效解決，如何在保護原始資料不被洩露同時，更好地服務於各種城市應用呢？

本文將介紹南洋理工大學與SAP聯合在IJCAI 2018上發表的論文《A Non-Parametric Generative Model for Human Trajectories》，文章透過真實軌跡學習城市人群的出行分佈來生成軌跡，生成軌跡可以代替包含使用者隱私資訊的真實軌跡，來達到相近資料分析、上層業務建設的效果，避免位置資訊外洩。文章有效地學習了軌跡的位置序列Embedding，進而，透過對抗式生成網路(GAN)來學習軌跡分佈並生成模擬軌跡。

背景

想要建模城市中的人群移動特性是很有挑戰的：1）軌跡狀態空間很大；2）軌跡具有很強的獨一無二性，很難找到兩個軌跡完全相同的人；3）人群的軌跡具有相似的隱式語義，比如上班、下班、旅遊，需要用有效的表徵刻畫出這些相似的語義來；4）軌跡序列內的位置相關性與軌跡間的相關性難以顯式定義。

圖 1：演算法框架

為了解決上述挑戰，論文首先將軌跡對映到空間網格中，轉為矩陣，每個網格包含了軌跡的訪問該網格時間與駐留該網格時長資訊；然後，透過對抗式生成網路來學習上述矩陣化後的軌跡資料，並生成相似軌跡。實驗驗證了生成軌跡對個體軌跡特徵、軌跡統計特徵有較好的保留，並與真實軌跡難以區分。

問題定義

我們記一條軌跡為經緯度時序序列

其中表示軌跡在時刻經過座標。給定軌跡資料，問題定義為學習軌跡資料的分佈函式，即。

在軌跡長度很大時，想要學出的分佈是非常困難的。作者認為，馬爾科夫模型的有限階依賴關係無法學習長軌跡的先後位置關聯關係；而基於迴圈神經網路如LSTM的做法，由於也被發現在長序列生成中會出現偏離[1]，也不能很好適用於軌跡生成。

軌跡表徵

這裡介紹論文的軌跡表徵方式。不同於往常用時間序列來表示軌跡（就如問題定義中介紹那樣），作者從空間視角出發，將軌跡時間序列轉化為矩陣形式。

具體來說，首先城市被劃分為的網格，並將輸入軌跡轉為大小為的矩陣。包含了計算軌跡與每個網格的兩項資訊，其中分別為：軌跡進入該網格的時間，與軌跡在網格內停留的時間。例如，下圖a的城市網格中，圖b的軌跡在5:00出現在網格0，一個小時後進入網格3，然後經過兩小時在8:00進入網格4直到9:00。圖c是以一小時位精度的矩陣化的結果，以網格3對應位置，即為例，由於軌跡在6:00開始進入網格3，所以，且在8:00離開，期間經過2小時，所以。

圖 2：軌跡表徵例項

上述方法還需考慮一種情況——軌跡多次訪問某一個網格。論文的做法是將矩陣擴充套件為三維張量，以記錄軌跡第K次訪問的時間與停留時長。

對抗式生成模型GAN及其訓練

區別於需要人工設定目標分佈形式的引數化分成模型，對抗式生成模型使用深度神經網路來學出目標分部形式，避免人工設定，來達到無引數化的目的。作者利用了對抗式生成模型的這一優勢，來學習軌跡資料的分佈。

作者直接採用了梯度較為穩定的WGAN-GP的框架進行模型訓練。形式化來說，若給定真實軌跡資料，GAN同時學習用於生成軌跡的生成網路和用於辨別軌跡是否真實（而非人造）的辨別網路。和均採用卷積網路CNN來處理矩陣化的軌跡資料，以豐富軌跡區域性特徵的提取。訓練的損失函式為

其中是簡單隨機分佈如均勻分佈、高斯分佈等； 透過真實資料與生成資料的凸組合得到。最佳化目標分為三項，A項為辨別人工軌跡的損失，B項為辨別真實軌跡的損失，C項是避免梯度異常的懲罰項，以表示懲罰權重。

注意不同於常規模型訓練僅更新引數來縮小損失函式值，對抗式生成模型的訓練過程會反覆地透過先更新來最大化辨別誤差，以欺騙；再更新來最小化辨別誤差，以破解。詳細過程可以參考GAN相關文獻。

實驗結果

實驗設定

軌跡時序資料具有高維特點，直接驗證生成軌跡的機率分佈是否符合真實資料，在計算量上可行性較差。為此，作者選了四項統計量，透過驗證統計量分佈是否一致來驗證軌跡分佈是否一致，這裡列出兩項：和，分別表示網格與停留時長的聯合分佈，和網格與進入網格時間的聯合分佈。分佈差的透過常用的琴森夏農散度(JSD)來衡量：

準確度效果

實驗將原始軌跡資料對半分成訓練資料和測試資料，並在每一輪訓練後生成軌跡。如下圖所示，生成軌跡與訓練資料、測試資料分別計算JSD值，分別以藍、紅表示。

圖 3：訓練過程

生成軌跡語義真實性

作者同時對生成軌跡的語義進行分析，判斷生成軌跡是否還原了真實軌跡的語義。這包含了兩項驗證：常訪問位置真實度和相對語義真實度。

圖 4：常訪問位置top50準確性

在常訪問位置真實度驗證中，作者分別用論文方法與馬爾科夫方法生成了軌跡，並統計top50的常訪問地，與真實top50常訪問位置進行比較計算精確度。如上圖所示，論文方法比馬爾科夫方法更準確地反映了真實top50訪問位置，並達到至少70%的精度。

在相對語義真實度驗證中，作者採用了pair-wise軌跡語義距離的分佈作為評價指標。首先作者採用了一種常用的軌跡語義距離公式：

然後對生成軌跡與真實軌跡分別提取1000個軌跡pair計算pair-wise距離，得到了生成軌跡與真實軌跡的語義距離樣本集，並對比生成距離樣本與真實距離樣本的分佈，下圖展示了兩組樣本的各分位數對比情況，驗證了生成軌跡在相對語義分佈上與真實軌跡相似。。

圖 5：相對語義距離分佈的分位數對比

小結

本文主要介紹了一篇比較有代表性的，在已有軌跡城市生成人造軌跡的論文。在當時，比較創新的點在於對軌跡的矩陣化表徵、和GAN的應用。將來會分享更多軌跡生成和城市流動性建模的相關研究或觀點。