在大數據時代,位置數據成為各方都亟待挖掘的數據寶藏,比如在城市交通基建規劃、商業選址、線下廣告等場景中,都是以位置數據為重要基礎。但在此過程中,隱私問題一直未得到有效解決,如何在保護原始數據不被洩露同時,更好地服務於各種城市應用呢?
本文將介紹南洋理工大學與SAP聯合在IJCAI 2018上發表的論文《A Non-Parametric Generative Model for Human Trajectories》,文章通過真實軌跡學習城市人群的出行分布來生成軌跡,生成軌跡可以代替包含用戶隱私信息的真實軌跡,來達到相近數據分析、上層業務建設的效果,避免位置信息外洩。文章有效地學習了軌跡的位置序列Embedding,進而,通過對抗式生成網絡(GAN)來學習軌跡分布並生成模擬軌跡。
背景
想要建模城市中的人群移動特性是很有挑戰的:1)軌跡狀態空間很大;2)軌跡具有很強的獨一無二性,很難找到兩個軌跡完全相同的人;3)人群的軌跡具有相似的隱式語義,比如上班、下班、旅遊,需要用有效的表徵刻畫出這些相似的語義來;4)軌跡序列內的位置相關性與軌跡間的相關性難以顯式定義。
為了解決上述挑戰,論文首先將軌跡映射到空間網格中,轉為矩陣,每個網格包含了軌跡的訪問該網格時間與駐留該網格時長信息;然後,通過對抗式生成網絡來學習上述矩陣化後的軌跡數據,並生成相似軌跡。實驗驗證了生成軌跡對個體軌跡特徵、軌跡統計特徵有較好的保留,並與真實軌跡難以區分。
問題定義
我們記一條軌跡為經緯度時序序列
其中表示軌跡在時刻經過坐標。給定軌跡數據,問題定義為學習軌跡數據的分布函數,即。
在軌跡長度很大時,想要學出的分布是非常困難的。作者認為,馬爾科夫模型的有限階依賴關係無法學習長軌跡的先後位置關聯關係;而基於循環神經網絡如LSTM的做法,由於也被發現在長序列生成中會出現偏離[1],也不能很好適用於軌跡生成。
軌跡表徵
這裡介紹論文的軌跡表徵方式。不同於往常用時間序列來表示軌跡(就如問題定義中介紹那樣),作者從空間視角出發,將軌跡時間序列轉化為矩陣形式。
具體來說,首先城市被劃分為的網格,並將輸入軌跡轉為大小為的矩陣。包含了計算軌跡與每個網格的兩項信息,其中分別為:軌跡進入該網格的時間,與軌跡在網格內停留的時間。例如,下圖a的城市網格中,圖b的軌跡在5:00出現在網格0,一個小時後進入網格3,然後經過兩小時在8:00進入網格4直到9:00。圖c是以一小時位精度的矩陣化的結果,以網格3對應位置,即為例,由於軌跡在6:00開始進入網格3,所以,且在8:00離開,期間經過2小時,所以。
上述方法還需考慮一種情況——軌跡多次訪問某一個網格。論文的做法是將矩陣擴展為三維張量,以記錄軌跡第K次訪問的時間與停留時長。
對抗式生成模型GAN及其訓練
區別於需要人工設定目標分布形式的參數化分成模型,對抗式生成模型使用深度神經網絡來學出目標分部形式,避免人工設定,來達到無參數化的目的。作者利用了對抗式生成模型的這一優勢,來學習軌跡數據的分布。
作者直接採用了梯度較為穩定的WGAN-GP的框架進行模型訓練。形式化來說,若給定真實軌跡數據,GAN同時學習用於生成軌跡的生成網絡和用於辨別軌跡是否真實(而非人造)的辨別網絡。和均採用卷積網絡CNN來處理矩陣化的軌跡數據,以豐富軌跡局部特徵的提取。訓練的損失函數為
其中是簡單隨機分布如均勻分布、高斯分布等; 通過真實數據與生成數據的凸組合得到。優化目標分為三項,A項為辨別人工軌跡的損失,B項為辨別真實軌跡的損失,C項是避免梯度異常的懲罰項,以表示懲罰權重。
注意不同於常規模型訓練僅更新參數來縮小損失函數值,對抗式生成模型的訓練過程會反覆地通過先更新來最大化辨別誤差,以欺騙;再更新來最小化辨別誤差,以破解。詳細過程可以參考GAN相關文獻。
實驗結果
實驗設定
軌跡時序數據具有高維特點,直接驗證生成軌跡的概率分布是否符合真實數據,在計算量上可行性較差。為此,作者選了四項統計量,通過驗證統計量分布是否一致來驗證軌跡分布是否一致,這裡列出兩項:和,分別表示網格與停留時長的聯合分布,和網格與進入網格時間的聯合分布。分布差的通過常用的琴森香農散度(JSD)來衡量:
實驗將原始軌跡數據對半分成訓練數據和測試數據,並在每一輪訓練後生成軌跡。如下圖所示,生成軌跡與訓練數據、測試數據分別計算JSD值,分別以藍、紅表示。
生成軌跡語義真實性
作者同時對生成軌跡的語義進行分析,判斷生成軌跡是否還原了真實軌跡的語義。這包含了兩項驗證:常訪問位置真實度和相對語義真實度。
在常訪問位置真實度驗證中,作者分別用論文方法與馬爾科夫方法生成了軌跡,並統計top50的常訪問地,與真實top50常訪問位置進行比較計算精確度。如上圖所示,論文方法比馬爾科夫方法更準確地反映了真實top50訪問位置,並達到至少70%的精度。
在相對語義真實度驗證中,作者採用了pair-wise軌跡語義距離的分布作為評價指標。首先作者採用了一種常用的軌跡語義距離公式:
然後對生成軌跡與真實軌跡分別提取1000個軌跡pair計算pair-wise距離,得到了生成軌跡與真實軌跡的語義距離樣本集,並對比生成距離樣本與真實距離樣本的分布,下圖展示了兩組樣本的各分位數對比情況,驗證了生成軌跡在相對語義分布上與真實軌跡相似。。
小結
本文主要介紹了一篇比較有代表性的,在已有軌跡城市生成人造軌跡的論文。在當時,比較創新的點在於對軌跡的矩陣化表徵、和GAN的應用。將來會分享更多軌跡生成和城市流動性建模的相關研究或觀點。