桔妹導讀：每天滴滴都會為上千萬人提供出行服務，在這一程序中積累了海量軌跡資料，這些軌跡資料來自于公共服務，本文介紹如何利用這些資料回饋大眾，改善出行體驗，

1. 背景

首先簡要介紹一下什么是資料挖掘，資料挖掘（Data Mining）是指從大量資料中發現特定資訊和模式的程序，也有很多人將這一程序看作知識發現（Knowledge Discovery in Database），資料挖掘常用的演算法手段有回歸、分類、聚類和模式發現，工程上資料挖掘通常和大資料技術聯系在一起，工業實踐中還需要從業人員對資料中包含的領域知識有足夠了解，業界挖掘手段經常用在用戶畫像、商業智能（Business Intelligence）、社群關系發現等場景，本文主要分享如何從海量軌跡資料中提取關鍵資訊，改善用戶出行體驗，滴滴在業務運營程序中，司機端APP 會持續向后臺上傳位置資訊，這些資訊被用于分單、司乘碰面、導航、里程計費，每天滴滴都會為上千萬人提供出行服務，在這一程序中積累了海量軌跡資料，這些軌跡資料不涉及用戶隱私，主要反應了公共道路上的交通狀況和司機駕駛習慣，下面我們會具體介紹兩個典型場景，

2. 路網更新

作為數字道路地圖的關鍵部分，道路交叉口是多條相互連接道路的交匯處，其幾何特征和拓撲屬性的精確性在移動導航和其他位置服務中起著重要作用，隨著城市發展，交叉口的更新越來越頻繁，主要包含掛接關系變更、新路、形態變更，這類拓撲錯誤如果不能及時檢測及更新，會影響路網匹配、路徑規劃、導航播報等基于路網資料的地圖服務，產生導航繞路、播報不合理等用戶體驗問題，

▍2.1 技術挑戰

交叉口拓撲更新可以抽象成這樣一個問題：路口范圍內的軌跡矢量模式與路網是否匹配？為此，需要解決以下幾個關鍵問題：第一，軌跡資料包含了大量噪聲，如何進行有效去噪；第二，路口位置及范圍如何確定；第三，軌跡矢量模式如何表達以及如何與路網差分，為了解決以上問題，我們設計出的演算法框架如下，包含三個核心模塊：軌跡質量提升，路口影響區域檢測和拓撲結構校準模塊，相關作業發表在資料挖掘與資料庫技術頂級學識訓議 International Conference on Data Engineering (ICDE) 2020上，

▍2.2 ****軌跡質量提升原始軌跡資料可能受設備故障、信號不佳等因素影響導致采集到的定位資訊存在漂移甚至例外，我們根據前后軌跡點的距離和時間間隔進行軌跡段的分割，保證同一軌跡段在時空上具有連續性；此外，車輛在路口一般會因為等紅綠燈或交通擁堵停留，導致在短距離范圍內產生大量具有不同方向的位置資訊（噪聲），不僅增加了路口檢測的計算開銷，還給檢測精度帶來較大影響，

針對這一問題，我們基于軌跡點的密度（時間密度、空間密度）進行資料過濾，并對區域自相交軌跡段進行分段，最后通過Douglas Peucker演算法提取軌跡段關鍵形狀點，在保留軌跡轉向特征的同時，對資料實作了壓縮，因此，通過軌跡分段、去噪、壓縮的預處理，實作了對原始軌跡資料的質量提升，

▍2.3 交叉口位置及范圍生成

為了檢測道路交叉口影響區內的詳細拓撲資訊，首先需要識別道路交叉口的核心區域，即路口位置和覆寫范圍，考慮到不同路口大小不一，并且路口范圍內軌跡通常具有減速、轉向等特征，我們設計了一套基于四叉樹空間劃分和Mean-shift的自適應路口位置檢測演算法，在搜索道路交叉口單元的程序中，將四叉樹的最小邊長設定為25米，并從200米大小邊長開始的層（即從四叉樹底部開始的第四層）搜索道路交叉口單元，由于交叉口中心位置的軌跡往往比路段具有更多的轉向與較低的轉速，我們對每個網格單元中的所有特征點（軌跡壓碩訓得）執行速度分析和基于方向的DBSCAN聚類，篩選潛在的道路交叉口網格單元，隨后，鑒于Mean-Shift演算法可以在聚類程序中同時檢測出密度中心，我們通過該演算法，結合候選交叉口單元內的軌跡點識別路口的中心位置，

不同路口其形狀有較大差異，如何更通用地基于軌跡資料確定路口的核心區范圍？實質上道路交叉口的中心位置附近并不總是具有相對于路段區域更多轉向行為，例如，環島和立交橋，本文中我們利用環狀幾何模型逐層檢測路口覆寫范圍，對于一個路口而言，越到核心區邊緣的環包含的轉向點密度越低、速度越大，因此該路口模型適于不同形狀路口的范圍提取，

▍2.4 拓撲結構校準

在路口范圍拓撲結構的校準階段，我們基于檢測的路口中心位置和核心區范圍向外擴展，獲取交叉路口影響區內的全部軌跡，我們對這些軌跡進行轉向簇提取與中心線擬合，并將擬合的轉向路徑與基準路網進行地圖匹配，Frechet距離適于評測曲線之間的相似性，但是對于復雜形狀的路口以及路口鄰接路段間朝向偏差較小的情況，Frechet表現不佳，鑒于此，我們將方向權重引入軌跡相似性度量中，對于任意兩條軌跡序列，分別計算起點與終點間的方向差，并結合Frechet距離生成軌跡集合的距離矩陣，基于該矩陣結合DBSCAN聚類實作路口范圍內的轉向簇提取，

在提取轉向簇后，需要對各簇軌跡進行擬合來得到轉向矢量模式，我們采用基于Force Attraction的聚類方法獲取各簇對應的轉向路徑，相比如其他依賴點資訊的擬合演算法如Sweeping等，Force Attraction方法能夠充分運用軌跡線資訊，因此對復雜轉向場景的擬合更加魯棒，Force Attraction方法首先隨機采樣簇中的一條軌跡作為參考軌跡，隨后使用同簇內其余軌跡對參考軌跡中點的位置進行迭代調整，在調整程序中，Force Attraction演算法假定任意軌跡點上有吸引力和排斥力作用，通過搜索兩個力達到平衡的位置來獲得參考軌跡對應點的新位置，由于隨機采樣軌跡容易導致擬合得到的中心線不精準，特別是當隨機采樣的參考軌跡遠離實際道路中心時，擬合偏差較大，因此，我們引入基于Frechet的采樣策略，具體來說，我們從簇中隨機采樣k條軌跡作為候選參考軌跡，并分別計算每個候選者與該簇的其余軌跡之間的Frechet距離，將具有最小距離和的候選軌跡視為參考軌跡，

在獲得轉向路徑后，我們采用經典的HMM演算法結合基準路網進行地圖匹配，為加速匹配程序，我們基于每個路口的轉向路徑集生成凸包再與路網空間關聯，根據匹配概率得到低置信度轉向路徑，作為需修正拓撲情報，

在最終的路口拓撲校準上，為了評估我們解決方案的有效性，我們基于滴滴實際軌跡資料和路網檢測兩種型別的錯誤拓撲：轉向路徑缺失和轉向路徑偏移，根據我們的評估，整體的精確率能夠達到70%，轉向路徑缺失和偏移的比例在1 : 5，目前該方法已經在滴滴路網更新產線中得到應用，下圖為兩個典型案例（路網為淡灰色線，軌跡分布以深藍色表示，校正的轉向路徑以紅色箭頭線突出顯示，

3. 路線偏移

在網約車業務場景中，可能會出現司機師傅未能按照導航路線行駛而出現路線偏移的現象，導致此類場景出現的原因可能是路況不佳、路線不合理、道路封閉，也可能是司機發現了更好的路線躲避擁堵，或者是對路線不熟悉，甚至故意繞路等，挖掘此類場景對于網約車提升地圖用戶體驗、避免司乘糾紛、保障司乘安全具有至關重要的意義，為了解決此類問題，地圖團隊通過全域/區域的起終點（Origin-Destination，簡稱OD) 約束，基于用戶歷史軌跡行為特征建模，實時觀測目標用戶軌跡行為空間分布特征，從而檢測路線偏移行為，基于用戶軌跡的路線偏移檢測，我們最終構建了實時觸達用戶的軌跡安全產品與路網狀態更新體系，

▍3.1 技術挑戰

基于OD軌跡路線偏移檢測，通常涉及到路線表征維度多樣性、OD觀測空間下歷史正常軌跡稀疏性、檢測實時性等建模問題以及TB級軌跡大資料的離線特征存盤更新、在線實時查詢等工程問題，雖然在學術研究領域，軌跡例外檢測已經形成了相對成熟的解決方案與不同角度的研究積累，但在實際工程實踐會面臨復雜多樣的業務場景，具體來講：

路線表征維度多樣性
用戶軌跡路線可以用一系列有序的GPS點串表征，該方式可以保留最原始的路線資訊，但是會存在軌跡飄點、冗余、無法批量高效建模的問題；也可以基于軌跡匹配道路結果進而通過一系列路段表征路線，該種表征方式最為常見，同時也會存在軌跡質量、綁路策略而帶來的誤匹問題；還可以將GPS映射到空間瓦片表示，該方式可以有效規避以上兩類問題，但是無法精確定位路網問題，因此在不同的建模場景中，應該采取不同的路線表征維度，左側藍色點串GPS軌跡的原始表示，右側表示軌跡的瓦片表示，
OD觀測空間下歷史正常軌跡稀疏性
由于我們是在OD的空間約束下進行軌跡建模，并且需要觀測在該空間下歷史用戶軌跡分布特征，如果用戶行程起終點下關聯的歷史用戶軌跡數量過少甚至不存在，那對于軌跡建模來講將是巨大的挑戰，
檢測實時性
在路線偏移的場景下，不管是路網狀態例外還是訂單狀態例外，都要求演算法能夠實時、精確、可解釋的計算結果并觸達用戶，因此要求我們的演算法要能夠實時地對端上上報的軌跡點進行狀態判定，

為了解決例外路線偏移檢測的問題，考慮到不同的產品及業務需求，我們設計并完成了以下兩大類檢測解決方案，下面進行簡單的介紹，

▍3.2 "少而不同"繞路檢測

該類場景主要是檢測單一、少數繞路訂單的例外狀態，該類訂單在OD約束下，與其他正常相同OD下其他正常訂單軌跡空間分布存在明顯的差異，主要表現為連續地出現離群軌跡點，所以可以將我們的任務轉化為實時離群軌跡點檢測，檢測方法可以由以下部分組成：

路線形狀表達
軌跡路線形狀表達的目的主要是壓縮軌跡，同時保證形狀資訊和壓縮率；同時也要平滑軌跡，去除停留點與噪點，我們采用了Minimum Description Length Partition演算法對軌跡進行壓縮表示，該演算法通過定義角度距離、垂直距離等，拓展了傳統的Douglas-Peucker演算法，無需定義閾值，可以自適應增量式劃分和壓縮軌跡，
導航特征表達
在實際業務場景中，除了軌跡路線形狀之外，我們還可以實時獲取到用戶導航-偏航狀態的特征，通過行駛方向與導航起終點方位關系，可以判定用戶當前是否在朝向終點運動，紅色線條為道路路線，綠色線條為軌跡路線，β1表示A1A2導航起終點夾角為銳角，朝向相近，即朝向終點運動，β2反之，

稀疏OD軌跡Embedding

為了克服上文中提到的同OD下歷史正常軌跡稀疏性的問題，我們提出了一種基于地理空間關系學習的軌跡Embedding方案，該方案主要是在訂單起終點的約束下，建模軌跡中途經點與起終點之間的關系，由于不涉及到具體特定軌跡，只是建模起終點與途經點關系，因而在可以在一定程度上解決OD空間下稀疏性的問題，Embedding主要更新學習程序如下：

其中，地理特征矩陣更新學習的程序為：

S1）將行駛的軌跡T={p1, p2, … , pn}根據坐標映射到對應的路網網格中，軌跡可以表示為T={g1, g2, … , gn}其中gi為行駛軌跡中坐標pi在路網中對應的網格，

S2）使用具有固定視窗大小和固定滑動步長的滑動視窗，將軌跡T={g1, g2, … , gn}劃分為若干定長的子軌跡，如滑動視窗大小為10，滑動步長為1，則原始軌跡T可被劃分為子軌跡集合T’ = {Tj | Tj={gj, gj+1, … , gj+9}, 1≤i≤n-9}

S3）假設路網中有N個互不相同的路網網格，則對目標區域的所有路網網格隨機初始化兩個Nd維特征矩陣，特征矩陣中的每一行為一個特征向量，分別表示對應網格作為起點和終點時的特征，將兩個特征矩陣拼接后可以得到一個N2d維的特征矩陣，用于表示對應網格作為軌跡途經點（既非起點也非終點）時的特征，

S4）將S2）中得到的每條子軌跡T={g0, g1, … , gn} 根據軌跡點性質轉化T={S, M1, … , Mj, D}，其中S=g0表示子軌跡起點，D=gn表示子軌跡終點，M1, … , Mj表示子軌跡途經點，

S5）在起終點約束的條件下，最大化途徑點M1, … , Mj出現的平均對數概率，即可完成在在地理空間約束下的軌跡建模，根據軌跡點性質，分別從不同特征矩陣查找軌跡經過的路網網格的性質，即從起點特征矩陣中查找起點S的特征向量，為d維向量；從終點矩陣中查找終點D的特征向量，為d維向量；從途徑點矩陣中查找途徑點Mj的特征向量，為2d維向量，拼接起點S和終點D的特征向量和，即可得到2d維的起終點特征向量，

S6）通過反向傳播更新起點、途經點和終點的特征矩陣，直到模型收斂，此時即可得到送駕區域路網網格在地理空間約束下的特征向量，

實時離群點檢測
為了滿足軌跡實時例外檢測需求，需要演算法能夠在系統輸入的一定時間視窗的軌跡之后，完成路形表達、導航特征提取、軌跡特征Embedding之后，立即給出在該OD空間約束下，當前行程軌跡是否處于偏移狀態以及該狀態下基于以上特征的支持度【支持度可以定義為在OD約束下，歷史正常路線途徑該瓦片的訂單數量 / OD約束下總訂單數量】，借鑒iBOAT自適應視窗檢測在線檢測思路，類似的，我們提出了一種基于多特征表征的實時路線偏移檢測框架，具體檢測程序為：當偏航發生時，在一定時間視窗，獲取目標訂單行程軌跡，對該行程進行路形、導航、軌跡特征的表征與判別，下圖中，圖一藍色為歷史正常用戶實際軌跡路線，紅色為目標用戶軌跡；圖二為iBOAT自適應視窗判別示意圖，

▍3.3 “多而不同”封路檢測

基于“少而不同”的思路針對極少數用戶軌跡偏移的例外檢測主要是為了解決司乘糾紛、軌跡安全等問題；“多而不同”主要是多數用戶在同OD空間約束下，出現了群體性的路線偏移，該現象往往意味路網的狀態發生了變更而導航依舊按照發生變更前狀態規劃，從而導致用戶的集體被迫繞路，因此針對路網狀態例外，以道路封閉為例，我們提出了一種基于 Siamese LSTM (孿生長短期記憶網路)與LSPD（缺失路段模式檢測方法）的軌跡時空模型來解決路網封閉檢測問題，相關作業發表在GIS領域國際會議ACM SIGSPATIAL 2019 (International Workshop on Ride-hailing Algorithms, Applications, and Systems)(SIGSPATIAL 2019 RAAS)該模型主要結構如下：

該模型主要分為兩個模塊，第一個演算法模塊是基于時間序列流量資訊相似性建模，該模型可以引入經典的Siamese LSTM網路，并融合注意力機制與自定義損失函式，實時刻畫歷史同期流量曲線與當前流量曲線的相似性，從而在線檢測流量例外，由于采取了與歷史同期（例如本周一與上周一）的流量序列建模，因而對流量自然下降及波動具備很強的魯棒性，

基于Siamese LSTM流量例外檢測可以對全路網空間的流量例外進行實時檢測，其檢測的結果需要更強的證據佐證道路例外，因此，我們設計了第二個演算法模塊LSPD，該演算法側重于通過群體用戶行為的例外判別第一個演算法模塊結果的可解釋性與概率性，主要思想是統計同OD下路線模式的分布變更，不同于軌跡例外檢測演算法(iBOAT) 在OD場景下關注“少而不同“的例外軌跡，我們重點關注“多而不同“的用戶群體性例外行為，例如某時間段內歷史用戶集中出現了繞路事件，則通過我們的LSPD演算法模塊可以精確定位到哪些路段可能出現了道路封閉以及發生發生該類事件的置信度有多大，

以北京市某處道路封閉事件為例，該道路在下午17時左右發生道路封閉，我們的系統在18時通過Siamese LSTM深度網路檢測出該道路存在明顯的流量例外，例外置信度為0.99，隨后，該事例被系統流轉至LSPD檢測模塊尋求更多的軌跡證據佐證該道路的確存在道路例外，在該模塊，我們的演算法檢測到在區域起終點（OD）的作用下，用戶的出行方式已經發生了巨大的變化，之前多數用戶選擇右側紅色路線，而當前狀態下，用戶多選擇左側藍色路線（紅色路線的支持度從30降低到6，而藍色路線的支持度則由3上升至43），從而被系統整體判別該道路出現了道路例外，即道路封閉，

4. 總結

在當前的工業實踐中，資料挖掘也常常和一些熱門詞匯聯席出現，比如人工智能、機器學習、大資料、資料分析、資料科學等，如下圖所示，

相比于其他概念，資料挖掘不強調應用何種手段，更強調目的：從資料中提取資訊，在這個意義上講，資料挖掘天然是交叉學科，需要從業人員具備統計、機器學習、大資料乃至高并發后臺服務、資料可視化等復合技能，另一方面，目前的人工智能技術水平僅僅達到刻畫相關性的階段，尚不能進行通用推理或者知識學習，所以需要從業者對研究的領域具備一定先驗知識，并了解如何利用這些知識從資料中提取有高價值資訊，這兩個特點決定了領域資料挖掘的門檻非常高，這影響了資料價值的快速發掘和落地，筆者所在團隊承擔了公司內部很多挖掘任務，比如安全駕駛行為檢測、路網挖掘、交通事件、地理畫像、出行模式分析等等，更多的資料挖掘任務因為排期和資源限制無法快速支持，而需求方因為高技能門檻無法自行對資料進行加工和價值提取，

我們下一步的目標是嘗試將軌跡資料挖掘能力中臺化或者平臺化，能夠將演算法、工程、大資料、可視化等能力開放出來，大幅降低資料挖掘成本，使得資料的價值能被最大化利用，實際上這一挑戰不是我們團隊或者公司獨有的，互聯網公司可能會存在無法以合適的成本從資料中提取價值的問題，導致資料挖掘技術只在少數高ROI場景下得到應用，即將到來的5G和萬物互聯時代，這一問題會更加嚴重，歡迎對此感興趣的同學加入我們，一起研究和探索如何解決這些挑戰，