基于GIS地圖的軌跡相似度分析系統(tǒng)實(shí)現(xiàn)

呂曉聰+祁忠琪

摘 要

隨著物聯(lián)網(wǎng)、大數(shù)據(jù)的發(fā)展以及各種可定位智能設(shè)備在我們現(xiàn)實(shí)生活中的應(yīng)用，我們可以獲得各類事物的軌跡數(shù)據(jù)，比如車輛或是行人。本文基于GIS地圖對獲取到的各類軌跡數(shù)據(jù)進(jìn)行相似度分析。

【關(guān)鍵詞】GIS地圖 軌跡 相似度

1 引言

隨著GPS技術(shù)和手機(jī)等智能終端設(shè)備的快速發(fā)展和廣泛應(yīng)用，產(chǎn)成了越來越多由經(jīng)緯度點(diǎn)組成的軌跡數(shù)據(jù)。在這些數(shù)據(jù)中蘊(yùn)含著豐富的信息，如何對這些軌跡進(jìn)行相似度分析，是研究軌跡數(shù)據(jù)的一個重要方面。鑒于此，本文基于GIS地圖以一種較為簡單的算法實(shí)現(xiàn)了軌跡相似度的計算。

2 總體設(shè)計

大體將軌跡數(shù)據(jù)分為兩類，第一類軌跡由僅包含經(jīng)緯度信息的點(diǎn)構(gòu)成，第二類軌跡所包含的點(diǎn)除了經(jīng)緯度信息外，還記錄了經(jīng)過該點(diǎn)的時間信息，軌跡數(shù)據(jù)表總體分為兩組，存放軌跡點(diǎn)數(shù)據(jù)的數(shù)據(jù)點(diǎn)表和存放各軌跡之間相似度的相似度表，而每組又分為帶時間和不帶時間的數(shù)據(jù)表。點(diǎn)表中l(wèi)on和lat字段分別表示點(diǎn)的經(jīng)度和緯度，time字段代表時間，sort_id字段表示每個點(diǎn)的主鍵，而id字段則代表該點(diǎn)所屬于的軌跡的id。相似度表中id1和id2字段分別代表比較的兩條軌跡，且兩者組成組合主鍵，dist字段代表經(jīng)過計算得到的兩條軌跡之間的編輯距離，之后可以通過公式獲得兩條軌跡之間的相似度。在本系統(tǒng)中，由于軌跡點(diǎn)的絕對位置是要參與比較的，因此，針對每條軌跡的歸一化是不需要的。

對于軌跡相似度的計算，重點(diǎn)需要考慮的是經(jīng)過各點(diǎn)的位置差異，經(jīng)過各點(diǎn)的順序以及經(jīng)過各點(diǎn)的時間差。由于采集經(jīng)緯度數(shù)據(jù)必定存在一些誤差，所以對于兩點(diǎn)重合的情況我們幾乎可以不用考慮。對于兩條軌跡，組成它們的點(diǎn)數(shù)量可能有所差異，但只要它們在形態(tài)上是相似的，那么就認(rèn)為這兩條軌跡相似。一條軌跡中點(diǎn)的數(shù)量對相似度的判斷沒有直接的影響。當(dāng)然，如果一條軌跡中包含的點(diǎn)越多，那么它的形態(tài)會越復(fù)雜。在軌跡形態(tài)相似的情況下，經(jīng)過各點(diǎn)的時間也是判斷相似度的重要考量。在GIS地圖中，根據(jù)經(jīng)過兩點(diǎn)的時間，就可以判斷這兩點(diǎn)之間的直線平均速度，可以作為相似度計算的一個度量。

3 具體實(shí)現(xiàn)

3.1 功能實(shí)現(xiàn)

3.1.1 計算

給定任意兩條同類型（帶時間或不帶時間）的軌跡，計算出兩者之間的相似度。

3.1.2 查詢

對于用戶指定的一條軌跡，查找與其相似的其他軌跡，并且按照相似度的高低對它們進(jìn)行排序。

3.1.3 用戶自定義軌跡

允許通過鼠標(biāo)點(diǎn)擊直接在地圖界面上創(chuàng)建不帶時間的軌跡路徑，并且自動將軌跡保存于數(shù)據(jù)庫中，之后可以將自定義繪制的軌跡以數(shù)據(jù)庫中已有的軌跡進(jìn)行相似度的計算，并且查詢出數(shù)據(jù)庫中與之較為相似的軌跡，按照相似度從高到底進(jìn)行排序。

3.1.4 讀取指定軌跡

該模塊的主要功能是上傳軌跡點(diǎn)的數(shù)據(jù)，自動在GIS地圖上顯示軌跡。

3.2 核心算法

步驟一：首先針對兩條軌跡上次序相同的兩個點(diǎn)，計算其轉(zhuǎn)化距離，這里用空間位置上的歐幾里得距離來計算，而對于帶有時間的軌跡點(diǎn)求轉(zhuǎn)化距離還需要帶有時間跨度的計算，最后設(shè)置歐幾里得距離和時間跨度的權(quán)值來獲得兩個點(diǎn)的轉(zhuǎn)化距離。

歐幾里德距離.計算軌跡間距離時可以利用：

symmetricRERP=（RERP（X，Y）+RERP（Y，X））/2 （2）

步驟二：得到不同軌跡上點(diǎn)之間的轉(zhuǎn)化距離以后，對于兩條軌跡的比較，可以采用LCSS算法來求得兩條軌跡的編輯距離，其中兩條軌跡的長度是可以不同的，即所包含的軌跡點(diǎn)的數(shù)目是不需要相同的，而其中元素的轉(zhuǎn)化懲罰值即為軌跡點(diǎn)的轉(zhuǎn)化距離。

步驟三：對于獲得的兩條軌跡的編輯距離，可以采用指數(shù)函數(shù)的方法，將最終的相似度作為編輯距離的底小于1的指數(shù)函數(shù)，滿足當(dāng)編輯距離為1時，相似度為1，即100%，而當(dāng)編輯距離增大時，相似度減小，且減小的趨勢越來越不明顯，并且最終趨近于0，符合相似度的變化要求，如圖1所示。

5 結(jié)語

綜上所述，通過分析軌跡之間的轉(zhuǎn)化距離，通過LCSS算法得到兩條軌跡之間的編輯距離，采用指數(shù)函數(shù)的方法，最終得到兩條軌跡的相似度。

參考文獻(xiàn)

[1]劉坤，楊杰.基于編輯距離的軌跡相似性度量[J].上海交通大學(xué)學(xué)報，2009（43）.