1、我們的生活：評估日常位置軌跡的相似度James Biagioni1 and John Krumm2 1 Department of Computer Science, University of Illinois at Chicago, Chicago, IL, USA 2 Microsoft Research, Microsoft Corporation, Redmond, WA, USA jckrumm 摘要。我們開發和測試的算法是基于GPS記錄的個人日常位置軌跡的相似度的評估。一份精確的 相似度評估可以被用來發現異常行為，聚類相似的天數，并且預測未來的旅程。

2、我們根據30 名志愿測試者的46天的GPS軌跡，收集了一份平均數據。每個測試者每天隨機匹配并且被要求評 估它們的相似度。我們測試了8種不同的相似度算法以準確再現我們的測試者的評估結果，并且 我們的統計測試發現有2種算法比其他算法優秀。我們也成功的運用其中一種相似度算法于通過 使用位置軌跡聚集相似的天數。 關鍵詞：位置軌跡，相似度，異常檢測，聚類。1 介紹 消費者和企業都意識到了通過位置軌跡來了解日常習慣和預測臨時的需求的價值，并且安裝了GPS的智能手機的大量使用使得這些更容易收集。這些軌跡可以幫助我們了解日常活動；特別的是，我們可以使用位置軌跡發現異常的天和聚類相似的天，以使得更好的了解我們的

3、日常行程。這兩個任務都需要一種方法來比較這些天和其他的不同。 本文開發和測試算法測算相似天數來表示位置軌跡，從真實用戶的相似性評估測試。通過可靠的方法測算相似度，我們可以發現與其它截然不同的異常天數，比如暗示混淆（一個重要的在人群中檢測到認知障礙的用戶的現象）或者某種習慣的改變。我們也可以將屬于一起的天數做出合理的歸類來獲取他們的變化并且預測一天會如何發展，為未來適應系統的影響力提供有用的基礎知識。我們相信這是第一次使用位置軌跡以人類的評估的方式來測算天數的相似度。 各種各樣的傳感器可以用來描述一天的數據，比如測算一個人的手機，臺式電腦，車輛，社交網站，生物識別傳感器等等活動。我們的工作是針對

4、位置軌跡，通常使用GPS來測算。這樣的一個好處是，位置是一個持續存在的狀態（如果不是總是可以測量的話），而不是基于事件的活動，比如短信活動，這只是偶爾發生。大多數人的位置也是不斷變化的并且在戶外是易于使用GPS來測算的。這些特征使得位置成為一個很方便的測算天數之間的相似度的變量。地理信息系統社區已經廣泛的關注位置軌跡的相似度，比如，【1】，但是這些努力主要是機器處理過程。我們感興趣的是匹配人類評估的相似度，這似乎更常見于異常檢測的研究中。在【2】中，Ma從GPS軌跡中檢測到的異常首先呈現一個正常軌跡作為地面矩陣序列的結果。如果一個新的矩陣軌跡與其他正常軌跡完全不同，那么一個異常會被申明。這里的

5、相似度測算是明確的，它依賴于一個在正常行程和查詢行程之間的地理差異的數量測算。同時它也忽略的時間。在【3】中，Patterson等進行了基于GPS跟蹤的異常行為檢測。他們基于一個人的歷史GPS軌跡建立了一個動態的概率模型。如果建立的模型的不準確度超過了一般先驗模型，那么系統就會申明一個異常。這是一個隱含的相似度測算的例子。【2】和【3】的目的都在于檢測生活中認知障礙的異常。【4】中Giroux等人的系統也是同樣的目的，只有他們在家中使用傳感器檢測與預定義日常行程不同的異常，比如制作咖啡。如果違反了事件的正常序列或者該序列的時間與正常有所不同，那么一個異常會被申明。研究人員也在錄像中檢測到異常比

6、如Xian和Gong【5】，他們的系統能自動建立正常的模型。 所有這些技術都依賴于從觀察學會某種正常行為的模型，這意味著他們必須接受新的訓練。我們的目標之一就是找到一個單一的相似度量測算工作是否適合多人，且不需要經過任何培訓。此外，以前的技術檢測基于研究者設計的算法或閥值的不同行為。相反，我們的另一個目標就是找到一個相似度量能近似估算一個人類主題的數據。實現這些目標將使我們能夠提供一種未來的自適應系統的方法來準確地再現評估人類一天的相似度且對一般人效果很好不需要任何訓練，也許有助于緩解相關應用領域的冷啟動問題。為此，我們從30名支援測試者中收集了他們的GPS數據并讓他們評估他們每天的相似度。有

7、了這些真實數據，我們進行了各種相似度測算并且找出了2種方法能夠較好的再現測試者的評估結果。我們先論述如何從實驗中收集到數據。2 GPS數據和進程 為了完成基于位置軌跡天數相似度的評估實驗的結果，我們收集到的數據來自志愿者的車輛。本節展現了我們為了第三節的實驗準備的數據的記錄和處理過程。圖1.一段間隔10S的 GPS采樣點的段序列2.1 志愿者的GPS數據 我們記錄了30名志愿者（8名女性）的GPS數據。每位志愿者借了一臺RoyalTek RBT-2300 GPS記錄器并將它放在他們的車輛上，可由打火器供電。我們所有的測試者受雇于美國華盛頓的微軟總部并且大部分是獲得一張30美元的食堂消費卡作為補

8、償。少數測試者選擇無任何補償。我們的目標是從每位測試者那收集到至少6周的數據。最終我們從每個主體那獲得了平均四十天的GPS數據，從20天到60天不等，大多數的駕駛記錄包括了在當地的工作出行、通勤出行和周末出行。我們相信這組數據很好地歸納了多數人的正常工作路線。每個測試者至少擁有6周的GPS記錄，但是有些測試者沒有天天記錄。為了達到30個測試者的標準，我們最初記錄了39個測試者，但后來發現有9名測試者不知何種原因停止了記錄，沒有提供合適的數據，其中一位拒絕記錄，并且他們頻繁的交換使用他們的車輛（違反了我們的測量標準），并且有2位意外離職。我們也忽略了2位分別只有14天和18天的記錄的測試者的數據

9、。 該記錄儀每隔10S記錄一次坐標點（經度和緯度）。圖一展現了從我們的測試者記錄的10S采樣間隔的短序列GPS點。自從我們取消了測試者的可充電電池，他們只能在汽車點火器工作時記錄。對某些車輛，這只發生在汽車啟動時，對另外一些，汽車點火器是持續工作的。下面我們將詳細介紹在預處理過程中，我們填補了GPS系統相應的空白記錄和其他的限制。2.2 GPS數據處理過程 為了附加一下原始的GPS數據的語義信息，我們第一個預處理步驟是自動檢測原始軌跡上的中斷點的時間和地點。為了到達我們的目的，一個中斷點被定義為在GPS記錄中保持在300半徑的圓形區域內5分鐘及以上的我們檢測到的測試者或車輛的位置。這些參數是基

10、于數據集的，它們的測試者不包含在我們最后的評價中。 為了產生候選中斷點的初始位置，我們首先通過GOS軌跡數據制作了一個時間序列并標記那些符合上述中斷點定義的位置。因為一個中斷點位置在GPS軌跡記錄過程中會不止一次被訪問，因此在我們的數據中會有至少一次的停止表示記錄，因此我們可以用最后一個中斷點代替多余的。這樣做是我們能夠將一整套聚合知識同實際停止位置聯系起來。例如，考慮到測試者工作地點的情況下，在一個典型的工作周的過程中，他們的跟蹤數據最初將表示5個單獨的中斷點呈現的“工作”（一個表示一天）。通過將這5個中斷點表示成一個，我們得到一個代表最初5個中斷點的聚合理解的中斷點位置（即5天的位置被訪問

11、時，測試者達到/離開的時間等），這比觀測5個單獨的時間/地點顯得更為有用。為了合并這些中斷點，我們對候選的中斷點使用300米距離閥值（如上）作為合并標準而使用聚類【6】。 一點我們確定了中斷點的位置，我們就利用包含在其中的聚合信息，將語義標簽應用到某一站。具體來說，我們使用來自于American Time Use Survey (ATUS)【7】的數據來歸類最有可能成為中斷點的位置，無論是家里還是工作地點。由于我們最后的中斷點包含了每天的信息以及達到/離開的時間，停留時間以及訪問頻率，我們建立和訓練了完全基于這些標準的分類器來執行可能的家庭/工作的標貼。由于家庭/工作的中斷點在很多測試者的GP

12、S記錄集上發生的很頻繁，能夠區分我們的測試者最后的評價數據是非常重要的。具體來說，這些標簽能幫助我們的測試者迅速明確方向并且適應他們正在觀察的日子(例如，工作日/周末），并且能更容易區分正常和異常天數。 最后，作為最終的處理步驟，我們創建了一個象征著原始GPS軌跡的每一天的數據的中斷點（定義一天從早上4:00到下午3：59）。具體來說，在原始GPS數據的每個位置，我們更換了與其相關聯的中斷點的標識（與每個中斷點綁定的唯一的標識），并及時插入那些剛被啟動的車輛的記錄位置。如果一個給定的坐標對與中斷點位置是不相關的，那么它就被一個From Stop ID-To Stop ID pair替換，以此來

13、表示中斷點之間的行程。用一系列的符號表示花在中斷點中間的時間來簡化原始軌跡數據，不僅為我們提供了一個更簡要的軌跡數據的呈現，也更抽象的用于呈現評估算法，而不是依靠地理表示（見第4節）。3 日常相似度評價 我們的目標是找到一種算法使得天數相似度的評價可以達到人類評價的程度。為此，我們要求每位測試者對他們自己的位置數據進行相似度評估。由我們的作者之一引導，我們的位測試者被邀請運行一個顯示程序并要求他們對自己近期的數據記錄作相似度評估。該程序首先顯示一個日歷，標識了我們有可用的GPS數據的天數供測試者評估。對于選定的一天，該程序以3種不同的方式展示了一天的位置軌跡。1.地圖 在圖2（a）中展示的交互

14、式地圖顯示了我們發現的中斷點（在2.2節中描述的），每個都有其獨特的ID號碼。它同時也顯示了中斷點之間的GPS軌跡。這樣 的 可視化展示強調了在空間布局上每天的行程和中斷點。2.圖表 在圖2（b）中的一個交互式圖表以節點和他們的行程作為直邊的方式展示了測試者的中斷點。較厚的邊標識在2個中斷點間有更多的行程。我們發現的家庭和工作點被標貼，否則中斷點僅僅被標上他們唯一的ID以匹配它們在地圖上的號碼。點擊圖表上的一個點或者一條邊將在地圖上突出顯示相關的中斷點或者GPS軌跡，這使得研究更方便。這個可視化強調了中斷點的數量和它們之間的轉換。3.時間軸 如圖3所示的時間軸以不同的顏色塊顯示了每一個中斷點，

15、沿一條水平線展示。在中斷點之間的時間段表示行程，被涂上黑色。這給出了其它2種可視化顯示缺少的對天數的時間看法。 (a)GPS數據的交互式地圖 (b)GPS數據的圖表視圖，以及中斷點和它 它們之間的行程 圖2.為我們的測試者準備的2種可視化方式圖3.時間軸視圖，用顏色塊標識中斷點，用黑色窄條帶標識中斷點之間的行程 啟動程序后，我們要求每個測試者都熟悉可視化，測試者要挑選一天并結合可視化簡要的對我們描述。 我們的用戶研究的主要部分來到了下一：每個測試者被要求評估他們幾天的相對的相似度。也就是說，每個測試者隨機選擇4天并用上面提到的可視化來描述它們，這已經在圖4中展示。然后，我們要求測試者表述哪2對

16、是最相似的。例如，2對天數為A和B，C和D，我們要求測試者表述A和B是否比C和D彼此之間更相似，反之亦然。在第一次測試一個不同的方式，要求測試者給出每對天數的相似度等級后，我們選擇了這種簡單的評估方式。這個證明太難了，所以我們又回到了這個更簡單的問題，關于天數對的相對相似度。圖4所示的例子是一個代表我們的測試者的比較典型的問題，具有很好的代表性：平均每天5個中斷點，最左邊的天數對代表了一個簡單的例子，而最右邊的則代表了更為復雜的情況。每個測試者評定30對天數對，平均每個測試者花費了大約30分鐘。 有了這些部分的排名，下一步我們嘗試了幾種不同的算法評估一天的相似度以達到準確再現我們的測試者的評估

17、結果的要求。圖4.我們用戶研究的主要部分，我們要求測試者表述哪幾對是相似度最高的4 評估日常相似度的算法 為了找到一個算法估算天數對的數值相似度（或者說距離比分），且與我們的測試者的相似度劃分等級相匹配，我們實施和評估了4種軌跡評估算法的標準型和改進型。每個算法的標準型采用其最初定義，在下面的子節中描述。每個算法的改進型由其原來的標準型更加適用于Dynamic Time Warping (DTW) 8，技術允許我們放寬假設，對天數對之間的以時間排列。例如，考慮2天A和B組成一個簡單的“家工作地點家”的活動模式。在A天，測試者在早上8：30離家，9：00上班，下午6：00下班，6：30到家。在B

18、天，測試者早上8：00離開家，8：30上班，下午5：30下班那，6：00到家。因此A天和B天同時包含了9小時的工作時間和半小時的往返時間。主觀上來說它們實際上是相同的。但是，由于2者有30分鐘的時間差，它們必然會招致一個客觀相似度評估的懲罰。因此，我們改進各個DTW算法背后的動機就是我們的測試者是否忽略了這些變化的時間，如果是，、那么我們就要建立更加準測地捕捉和還原測試者的主觀性評估。 就形式而言，在每個算法的改進上我們通過引導每個算法定義相應的函數測量了DTW距離（DTW）。A天和B天之間的DTW距離計算如下，當并且每個對應一個中斷點ID或坐標對取決于算法是否被修改（B也類似）： 實際上，動

19、態時間整合扭曲了2個序列，因此使它們匹配最佳。下面我們描述4個標準軌跡相似度算法。4.1 校對距離 校對距離測算了需要將一串字符串符號轉換為另一個字符串的編輯操作的數量。在我們的例子中，該算法操作的中斷點符號代表了我們的軌跡數據（在2.2節中討論的），因此，這里的符號應與中斷點ID和中斷點之間的對數相符合。4.2 靈敏距離校對 標準的校對距離算法（4.1節中描述的）完全用一個中斷點符號代表給定的一天，而沒有考慮到中斷點的地理位置。為了說明為中斷點的地理位置，我們修改了標準Levenshtein算法【9】，使用了大圓形的距離，采用Haversine公式【10】來衡量，代價是為每個函數校對操作。這

20、意味著，例如，執行2個中斷點#60和#157的替代操作的代價不再是1，而是2個中斷點#60和#157之間根據它們坐標位置的距離。這個度量評估結果可以在圖5中看到。圖5.八個相似度算法的精確結果。在所有測試者中誤差在+/-1的標準偏差內。4.4 距離對的和 此度量【12】計算基于原始位置軌跡的天數之間的距離，而不是上述使用的中斷點符號。其結果是，這個度量不考慮任何相關的語義信息。距離對的和測算了每對軌跡位置（坐標點）之間的大圓環的和。由于這個度量要求A天和B天的軌跡長度相等，我們首先執行簡單的線性插值，然后計算它們的距離。這個度量評估的結果可以在圖5中看到。5 結果 我們同時在匹配我們的測試者的

21、相似度評估結果和聚類2個方面評估我們的相似度算法。5.1 匹配測試者的相似度評估 我們以30個測試者的數據運行8種相似度算法。記得每個測試者看了30組，每組4天。每組4天被分成了2對，然后測試者選擇那一對更加相似。我們將這些相同的天數組給我們的相似度算法，然后記錄下它們評估哪幾天相似度最高的結果。我們報告的精確結果表明了我們的算法能夠正確再現人類決策的比例。 精確結果如圖5所示。忽略統計學的意義，最好的執行算法是Sum of Pairs Distance with Dynamic Time Warping (w/DTW)，平均精確度為75.5%(SD=10.4%)。這個算法注重在2個位置軌跡的

22、中斷點之間的大圓環距離，并隨時間變化局部作調整。排在第2位的是Distance Sensitive Edit Distance w/DTW，整體平均度為74.2%(SD=9.3%)。實際上，我們的2個最佳執行算法都是基于在實際的地理距離已知的度量距離上來說的，顯然地，我們的測試者將天數相似度與地理位置聯系起來了。 由于我們為每位測試者計算了精確度，這為每個算法提供了30個精確度樣本，使得我們可以進行統計分析。我們最初使用一個單向的，重復測算的ANOVA測試，其結果為。這證明了算法的選擇在統計上有重要的精確度影響。我們接下來在每個算法之間進行了one-tailed, paired-sample

23、t-tests的方法，并用Holm-Bonferroni【13】校正多個t-tests。在28個可能的算法對中，16對在統計學意義上的精確度差異在0.05個等級。表1清點了各算法的勝利和失敗次數。最佳性能記錄算法是Distance Sensitive Edit Distance w/DTW，有5次勝利記錄并且0失敗記錄。次好的算法是Sum of Pairs Distance w/DTW，有4次勝利記錄并且0失敗記錄。這2種算法之間的性能差異沒有統計學上的意義。這2者中，Sum of Pairs Distance w/DTW更易實現，因為它不需要在位置軌跡中識別中斷點。雖然這2種最好的算法都使用

24、了DTW，但只對Distance Sensitive Edit Distance算法產生了統計學意義上的性能的顯著改，而非它的非DTW對應上。 總體來說，就精確度和易實現性，我們傾向于推薦Sum of Pairs Distance w/DTW作為我們測試過的評估天數相似度的算法中最好的。表1.統計學意義上的相似度算法的成功和失敗次數5.2 聚類的應用 我們的相似度測算的一個應用就是用聚類來找到相似天數的組。我們通過30位測試者評估他們自己的天數的聚類來測試。我們使用一個譜聚類算法（隨機游動的Laplacian特征向量的k均值【14】）。我們計算聚類的距離度量使用了Edit Distance w

25、/o DTW算法。Edit Distance w/o DTW的平均精度為66.2%(SD=12.5%)，略低于最好的精確度算法Sum of Pairs Distance w/DTW的75.5%。我們的調查使用Edit Distance w/o DTW是因為當我們進行我們的研究時，還沒有能力測試表現最好的算法。 為了調查的聚類部分，我們要求每個測試者從2個開始定期增加k聚類。對每個k聚類，該程序在第3節中顯示了使用相同的可視化手段展現聚類天數組。如圖6顯示的一個例子，1條時間線上顯示了3個聚類，而天數組又每行左手邊的彩色標簽表示。每個測試者都被要求選擇最佳的k，然后為Likert量表上的聚類評級

26、來表明他們對于申明的認同程度，“我的天數已經被分成合情合理的組。”這個問題的結果如圖7所示，我們看到30名測試者中有20名的回答不是“認可”就是“強烈認可”，表明聚類通常是成功的。反過來看，這進一步支持了dit Distance w/o DTW相似度算法更接近與匹配人類相似度評估。我們可以期望Sum of Pairs Distance w/DTW表現的更好，因為它是我們在5.1節中分析的最精確的算法。圖6.這是1條時間線上顯示的3個聚類。每行一天。在聚類頂部表示的那一天是一個異常值。主要的中央聚類顯示了32個工作日，在聚類的底部顯示了19個非工作日。圖7.大多數測試者對聚類結果感到滿意6 總結

27、 根據30名測試者的調查，我們基于他們的位置軌跡評估了8種不同的相似度算法的精確度。我們發現這2種算法Sum of Pairs Distance w/DTW和Distance Sensitive Edit Distance w/DTW在相似天數上最能匹配人類的評估結果。根據我們的測試者的評估，我們也發現我們測試的相似度算法中的一種在位置軌跡的聚類天數上有很好的效果。 除了聚類，這些相似度算法也可能用在發現異常以及幫助預測行為上。我們的算法沒有依賴與培訓，即它們對用戶來說是通用的，因此，它們相對更容易使用。 我們設想未來的工作在這方面可能會探索其他的相似度算法，以及采用實驗來發現異常。我們可以預

28、計異常檢測效果不錯，因為我們的算法在匹配相似度天數人類評估的結果上有很好的表現。參考1. Deng, K., et al.: Trajectory Indexing and Retrieval. In: Zheng, Y., Zhou, X. (eds.) Computing with Spatial Trajectories, Springer, New York (2011) 2. Ma, T.-S.: Real-Time Anomaly Detection for Traveling Individuals. In: Eleventh International ACM SIGACCES

29、S Conference on Computers and Accessibility (ASSETS 2009), Pittsburgh, PA USA, pp. 273274 (2009) 3. Patterson, D.J., et al.: Opportunity Knocks: a System to Provide Cognitive Assistance with Transportation Services. In: Mynatt, E.D., Siio, I. (eds.) UbiComp 2004. LNCS, vol. 3205, pp. 433450. Springe

30、r, Heidelberg (2004) 4. Giroux, S., et al.: Pervasive Behavior Tracking for Cognitive Assistance. In: 1st International Conference on PErvasive Technologies Related to Assistive Environments (PETRA 2008). ACM (2008) 5. Xiang, T., Gong, S.: Video Behavior Profiling for Anomaly Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence 30(5), 893908 (2008) 6. Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning, pp. 520528. Springer, Ne