一種時空軌跡相似度計算方法及系統的製作方法

2023-08-14 05:20:01

專利名稱：一種時空軌跡相似度計算方法及系統的製作方法
技術領域：
本發明涉及數據挖掘領域，特別涉及一種時空軌跡相似度計算方法及系統。
背景技術：
近年來，諸如平板電腦、智慧型手機等支持GPS的行動裝置發展迅速，越來越多的人開始使用基於位置的服務(LBS)，例如定位、位置共享等等，大量時空信息被上傳和共享。記錄用戶移動歷史的同時，這些位置信息也能夠在一定程度上反應用戶的興趣、偏好以及生活規律。為此，時空軌跡作為計算機應用的一大研究熱點，在普適計算、數據挖掘和社會網絡等領域受到了廣泛關注。人類活動具有不同程度的共性，這種共性差異映射到活動軌跡上，導致軌跡之間呈現不同程度的相似性。相應地，軌跡的相似程度反應了活動的共性，進而關係到相近似的 人類習慣和偏好。正因如此，如何科學地刻畫軌跡之間的相似度是當前軌跡模式挖掘等研究工作所面臨的最重要問題之一。當前,軌跡相似度計算方法考慮因素包括子列重疊程度、相近的位置數目、地點的數目等。然而，軌跡不是單純的序列，用序列包含關係去刻畫軌跡之間的關係是遠遠不夠的。此外，計算的粒度也是這類工作所面臨的困難，軌跡的離散化程度越高，和原始軌跡的偏差就越大，而細粒度的計算又難免降低效率。

發明內容
為解決上述問題，本發明提供了有效利用歐式空間的度量屬性和笛卡爾坐標系中的向量關係，刻畫軌跡模式之間的相似度。該方法可應用於分析人的活動模式，可作為個性化推薦的依據，以及可以用於構建和分析基於位置的社會網絡。本發明的目的在於提供一種全新的路線相似度計算方法，該方法基於幾何特徵，充分考慮到路線在地理空間上的特點，同時具有高準確性和較高計算效率。本發明公開一種時空軌跡相似度計算方法，包括步驟1，定義距離轉角率，刻畫用戶興趣點的特徵；步驟2，根據經驗閾值，識別用戶興趣點；根據軌跡的用戶興趣點計算其公共興趣佔.步驟3，計算分段之間的相似度以及不相似度，其中所述分段為兩個公共興趣點之間的分段；通過定義分段時間、相似分段、相似路線，計算軌跡之間的相似度以及不相似度，從而得到軌跡相似度。所述的時空軌跡相似度計算方法，所述步驟I還包括步驟21,定義 Pm、Pi 到 pi+1 的距離轉角率 LATatio(p(i_l), p(i), p(i+l)),其中Pi-i、Pi、Pi+i分別為用戶興趣點。所述的時空軌跡相似度計算方法，包括距離轉角率公式如下tr[ — cos( θ)
LATalio{p(i-I), p[i\ p{i + 1)) 二 LARa!io[v(p: .,, p.),,)) =-f-'■-
" ε+\\ν(ρ( ),ρ( . + γ)\\其中，ε是滿足下述條件的任意一個常量
0< ￡■ < min III v(p(i),/)(/+ \)) |||且
f + min{|I v(p(i — I),p(i)) ||}<mm{|| v(p(i — I), p(i)) ||J·
_9]其中，[I-1),^(/))I]是向量 『0· —I),ρ(/·))的模』 min{||V(^O-I)5jP(O)IlJ 是
,(ρ(ζ·_1)，^φ·))的第二小值。如果minj|| v(/ (i-l),/ (f))||l，ε 滿足一下不等式
<￡-<min{|| v(/;(/-!), /,(/))"}且
^ + mn{|| v(p(i — I),p(i))"} < min{|| v(p(i — I),p(i)) ||}其中，sec和 th 分別表示第二和第三,因此 1，丨 H v(p(i -1), p(i)) |||^^( _ |
的第三小值。所述的時空軌跡相似度計算方法，所述步驟2還包括步驟41,如果ratio〉P (這裡P是一個經驗閾值)，則認為興趣點P (i)和p(i+l) 是同一個興趣點，is(j)表示軌跡中的j個興趣點；為了計算軌跡的相異程度，用IP (j)表示IS (j)，IP (j) = (long(j)，Lat (j)，T (j))是IS(j)中興趣點的加權平均，其中j是興趣點的編號，L°mU) = Σι VC: · lon^ 』
τ "ratio .,..Laf0) = Σ,=ι^ . *^(0，
ra!jo- …7 ( /) = h ιTTT·/(/ ) °步驟42，如果兩個興趣點IP(i)和IP(j)之間的距離小於dp，稱這兩個興趣點為公共興趣點CoIP，dp根據具體賦值而變化。所述的時空軌跡相似度計算方法，所述步驟3還包括步驟51,位於C (i)和CoIP(i+l)中間的部分為tra (I)中的分段,記做segtM(i)。下述公式計算分段的不相似程度difvector (Segi Ura1)，Segi (tra2)) =Vdifvector (Segi (tra^，Segi (tra2)) +1 nlin_n2in其中，
Vdifvector (Segi (tra^，Segi (tra2))= vql (Segi (tra^ )-vql (Segi (tra2)) + vq2 (segi Ura1)) -vq2 (Segi (tra2)) | nin是軌跡中兩個興趣點之間非公共興趣點的數量。所述的時空軌跡相似度計算方法，所述步驟3還包括步驟62，分段時間，是指用戶從一個CoIP到另一個CoIP的間隔時間，如果CoIPi= (Longi, Lati, Ti),且 CoIPi+1= (Longi+1, Lati+1, Ti+1),那麼 Ti-Tw, Ti-Tw 即 CoIPi 和CoIPi+1在軌跡中的分段時間；相似分段，是令Segi (trati)和Segi (tra2)分別為^rat1和a2中的分段，稱SegiUra1)和Segi (tra2)為相似分段，當兩個分段之間IP的數量相等；兩個分段之間的分 段時間的絕對差值小於一個常數，即I (Ti Ura1) Ti+1 Ura1)) - (Ti (tra2) Ti+1 (tra2)) | <tp相似路線，由分段組成，如果有多個連續的相似分段，則為相似路線；假設A和rj是相似路線，則認為兩條路線沒有區別，即VdifveetOT (A Ura1)，rj(tra2))=0 ;下述公式計算軌跡之間的不相似度
nP dif (Zrai 3Zra2) = Σ c0Mvecror (Seg, (tmi I Seg, Ψα )) + m^x { rlIex ； 2 }其中，max {nlexJ n2ex}是nlex和n2ex的最大值，nex是兩條軌跡中位於公共點之外的non-CoIP數量，在tra(l)中有兩個位於公共點之外的non-CoIPs，因此nlex=2，tra(2)中位於公共點之外的non-CoIPs的數量為1，n2ex=l，因此max {nlex，n2ex} =2 ；
Len.(fru') rLen(InLl) r f 、、
(-————· l.eti (Zral) +----—· Lenl (/ra，)),、— ' l,en{irax)'Len( f:ra )~
Len{ira,) + l,en(lra^)LeniUra1)表示 SegiUra1)的長度，LenUra1)是 I^a1 的長度，Leni (tra2)表示Segi (tra2)的長度,Len (tra2)是tra2的長度，Segi的距離與長度的含義不同，Segi Ura1)的距離是CoIPi和CoIPi+1之間的直線距離，而長度是用戶從CoIPi走到CoIPi+1的路程。本發明還公開一種時空軌跡相似度計算系統，包括定義轉角率模塊，用於定義距離轉角率，刻畫用戶興趣點的特徵；興趣點模塊，用於根據經驗閾值，識別用戶興趣點；根據軌跡的用戶興趣點計算其公共興趣點；相似度匹配模塊，用於計算分段之間的相似度以及不相似度，其中所述分段為兩個公共興趣點之間的分段；通過定義分段時間、相似分段、相似路線，計算軌跡之間的相似度以及不相似度，從而得到軌跡相似度。所述的時空軌跡相似度計算系統，所述定義轉角率模塊還包括定義PH、Pi 到 pi+1 的距離轉角率1^^^1:;
O < s < min j Il v{p(i\ p(i + \ )) |||且
ε + min {|| ν(ρ( -1)，ρ{ )) 11} < ιτ ι ||| v(p(i -1), p(i)) ||J其中，I]^(0)||是向量的模，ι η{||ν(^(/- χΜ0)Ι }是 1),/ (/))的第二小值。如果min|l卜』(衝-1Xzj(O)Ilj，ε滿足一下不等式 0<f <min{|| v(/ (7-l),p(i)) ||J且
ε + min {| | v(p(i -1),p{i)) ||}<min||| v(p(i — 1)，p(i))其中，sec和 th 分別表示第二和第三，因此η|η||| l)，/;(i)) ||j是丨衝·—丨)，/ (/))
的第三小值。所述的時空軌跡相似度計算系統，所述興趣點模塊還包括經驗閾值模塊，用於如果ratio〉P (這裡P是一個經驗閾值)，則認為興趣點P (i) 和P(i+1)是同一個興趣點，is(j)表示軌跡中的j個興趣點；為了計算軌跡的相異程度，用 IP(J)表示 is(j)，IP(j) = (long(j)，Lat(j)，T(j))是 IS(j)中興趣點的加權平均，其中 j
是興趣點的編號，LonsU) = Y\ 1αη°\ .· ο^(η，
j ra(io(/)LatU) =r、 師)，
Y^.raiiod)
TV·、—ratio tT0) - Σ,=ι^ ~TTT-rW。
Σ,=1 ratoW距離模塊，用於如果兩個興趣點IP⑴和IP(j)之間的距離小於七，稱這兩個興趣點為公共興趣點CoIP，dp根據具體賦值而變化。所述的時空軌跡相似度計算系統，所述相似度匹配模塊還包括分段模塊，用於位於C(i)和CoIP(i+l)中間的部分為tra(l)中的分段，記做 segtra (i)；下述公式計算分段的不相似程度 difvector (Segi Ura1)，Segi (tra2)) =Vdifvector (Segi (tra^，Segi (tra2)) +1 nlin_n2in其中，Vdifvector (Segi Ura1)，Segi (tra2))= vql (Segi (tra^ )-vql (Segi (tra2)) + vq2 (se gi (^a1)) -vq2 (Segi (tra2))
nin是軌跡中兩個興趣點之間非公共興趣點的數量。所述的時空軌跡相似度計算系統，所述相似度匹配模塊還包括相似度運算模塊，用於分段時間，是指用戶從一個CoIP到另一個CoIP的間隔時間，如果 CoIPi= (Longi, Lati, Ti)，且 CoIPi+1= (Longi+1, Lati+1, Ti+1)，那麼 Ti-Tw, Ti-Tw 即CoIPi和CoIPi+1在軌跡中的分段時間；相似分段,是令Segi Ura1)和Segi (tra2)分別為1:坪和a2中的分段,稱Segi (tra)和Segi (tra2)為相似分段，當兩個分段之間IP的數量相等；兩個分段之間的分段時間的絕對差值小於一個常數，即I (Ti Ura1) Ti+1 Ura1)) - (Ti (tra2) Ti+1 (tra2)) | <tp 相似路線，由分段組成，如果有多個連續的相似分段，則為相似路線；假設A和rj是相似路線，則認為兩條路線沒有區別，即VdifveetOT (a Ura1)，rj(tra2))=0 ;下述公式計算軌跡之間的不相似度
nPdif (Ira1, tra2) = ^ a,difrectm. (seg, ^ral), Segi (tra2)) + max {nla.，nlex}
/=1其中，max {nlex, n2ex}是nlex和n2ex的最大值，nex是兩條軌跡中位於公共點之外的non-CoIP數量,在tra(l)中有兩個位於公共點之外的non-CoIPs,因此nlex=2, tra (2)中位於公共點之外的non-CoIPs的數量為1，n2ex=l,因此max {nlex, n2ex} =2 ；
Len:(jrax). LenAira,)
(-————· Leni (Jra1) H--————· Leni (Jra2))Lenitrai)Len(tm，)
OJi =-=-
I.cu(l.ra,) + Len(ira,)LeniUra1)表示 SegiUra1)的長度，LenUra1)是 I^a1 的長度，Leni (tra2)表示Segi (tra2)的長度,Len (tra2)是tra2的長度，Segi的距離與長度的含義不同，Segi Ura1)的距離是CoIPi和CoIPi+1之間的直線距離，而長度是用戶從CoIPi走到CoIPi+1的路程。本發明的有益效果為1，基於幾何向量的軌跡相似度計算方法；技術效果新穎地利用幾何向量方法，同時考慮距離與角度變化，刻畫兩條軌跡之間的關係，得到量化的相似程度；2，距離轉角率相似特徵定義；技術效果作為影響軌跡相似程度的重要變量，距離轉角率是刻畫長度關係、角度變化和軌跡局部相似性之間關係的數學模型；3，基於向量的分段不相似度算法；技術效果刻畫兩個分段的相似程度，用於判別不同分段是否相似；4，基於向量的興趣點定義；技術效果確定相似度的計算粒度，去除不必要的興趣點，以化簡計算；5，基於向量的公共興趣點定義；技術效果利用基於幾何向量的方法，消除如GPS等設備所採集的時空軌跡數據偏差對計算造成的影響，使得屬於同一興趣點但地理左邊略有偏差的數據得以被正確識別；6，利用幾何方法實現基於單條路線的興趣點發現；技術效果可以避免基於大量用戶大量路線的聚類，提高計算效率，同時可以發現新建的興趣點。該發明可以對任意兩條形式的不同路線進行比較，通過幾何方法量化其相似程度，所得結果可以有效用於分析人的活動模式、行為相似程度，以及可以為個性化推薦和社會網絡分析提供依據。與現有的技術相比，該發明充分考慮地理空間特性，合理刻畫相似程度，實驗證明，該方法計算結果更為合理有效，同時具有更高的運算效率。


圖I為本發明時空軌跡相似度計算方法流程圖；圖2為本發明GPS軌跡和LA-Ratio的解釋；圖3為本發明一條軌跡中的IS和IP ；圖4為基於本方法的兩條軌跡中的分段的不相似程度，其中4A為第一條軌跡 tra (I) ,4B 為第二條軌跡 tra (2)；圖5為兩條軌跡中的相似路線圖6為本發明時空軌跡相似度計算系統流程圖。
具體實施例方式下面給出本發明的具體實施方式
，結合附圖對本發明做出了詳細描述。本發明提供了一種基於幾何向量方法的軌跡相似度計算方法，這部分提供算法的詳細說明，說明過程以兩個軌跡之間的相似度為例，本方法可以拓廣到計算多個路線之間的兩兩相似度。如圖I所示，本發明公開一種時空軌跡相似度計算方法，包括步驟1，定義距離轉角率，刻畫用戶興趣點的特徵；步驟2，根據經驗閾值，識別用戶興趣點；根據軌跡的用戶興趣點計算其公共興趣佔.步驟3，計算分段之間的相似度以及不相似度，其中所述分段為兩個公共興趣點之間的分段；通過定義分段時間、相似分段、相似路線，計算軌跡之間的相似度以及不相似度， 從而得到軌跡相似度。以GPS日誌為例，本算法採用包括精度、緯度和時間的時空軌跡數據，用戶攜帶專門的GPS定位設備或者支持GPS定位的其他行動裝置(如智慧型手機、pad等)，採集到的數據根據不同的用戶呈現規律性並具備個性化的特性。具體地，一個時空軌跡是指興趣點列 Tra= (p (O)，P⑴，...，P (np))，其中np為軌跡中興趣點的數量，相鄰兩興趣點之間的時間間隔是相等的，t (Pi)-t (Ph) =t(pi+1)-t (Pi) ,Pi= (Iongi, Iati, t),其中 IongiUati 和 \ 分別為興趣點Pi的經度、維度和相應的時間點，i為興趣點的序號。對於每兩個相鄰的興趣點Pm
和Pi，直接用向量連接，記做ν /丨 j../>,)../·= 1，. t該向量的方向與軌跡的方向一致,Ph為興
趣點的起點，Pi為興趣點的終點。因此一條軌跡中有np-l個這樣的向量。本發明旨在計算上述形式的兩條軌跡的近似程度，採用基於幾何向量的方法，逐層計算。首先，根據單條軌跡計算用戶的興趣點。認為興趣點和角度有關，如果用戶在感興趣的景區停留則其軌跡在該區域的軌跡變化將更加頻繁。同時，本方法基於假設在興趣點的範圍內用戶會放慢速度，相應地，等時間間隔的兩興趣點之間距離會變短。基於以上兩興趣點考慮，本方法構建距離轉角率模型，用以刻畫用戶對位置的興趣程度。利用這一概念， 我們可以根據經驗閾值識別出用戶興趣點，並用單獨的一個興趣點表示。對於輸入的兩條用戶軌跡，基於其各自的興趣點我們可以計算兩者之間的公共興趣點，我們認為時空上相近的興趣點即公共興趣點，這是第一層相似。處於計算合理性和簡便性的考慮，有了公共興趣點之後我們沒有立刻計算軌跡的相似性，而是進一步細化，對軌跡按公共興趣點進行分段。我們認為兩段軌跡如果有越多的相似點則越相似，基於這一假設刻畫了分段之間的相似度，這是第二層相似。最後，根據每對分段的相似度計算出兩條軌跡的相似度。具體實施步驟如下步驟I):刻畫識別興趣點的重要特徵，定義距離轉角率。如圖2給出的GPS軌跡。定義PH、Pi 到 pi+1 的距離轉角率 LATatio(p(i_l), p(i), p(i+l))如下式·11I — cosi^)
JAlalkAp(i.-I), p{i\ p{i + 1)) = LARalioiHp ,, p,), '-iP-,Pi ,)) =-^-L-
￡+||v(/;(/'),/ (i + l))||其中，ε是滿足下述條件的任意一個常量
O < ε (/' +1)) |||且
+ min {|I v(p(i- l),p(i)) ||}<min||| v(p(i — I), p(i)) ||J其中，是向量(』(^/-1)4(0)的模，mm{||||}是
，(/ 0·-ι)，/ (0)的第二小值。如果minDI vCp(P1)5/^)) Ilj，ε 滿足一下不等式
O <& < niin Jll v、p(i-1), p(i)) ||[且
^ + π{|| ν(/ (/-1),/Η0)Ι! < min {|| v(/;(/-1),/;(/)) ||j其中，sec和 th 分別表示第二和第三，因此 min v(p{i -1), /)(/))_yK
的第三小值。為了簡便，記
iaiio(i) = LA Ται/υ{/>(/ —I): /;(/'), p(i +1)) = L4Rulio{ v.(p(i -1),/ (/)), v(p(i), p(i +1))) , / = 1, ...JLitno。很明顯，一個軌跡有np_2個ratio (比率)，其中\中P表示總興趣點的數量。(其中，「tatio 也是 ratio」)步驟2):識別用戶興趣點。如果ratio〉P (這裡P是一個經驗閾值)，則認為興趣點P (i)和p(i+l)是同一個興趣點。我們用IS(j)表示軌跡中的j個興趣點。為了計算軌跡的相異程度(這裡用相似性表示不同軌跡之間的差異程度，符合計算相似度的目標)，用IP (j)表示IS(j)，如圖3所示，IP(j) = (long(j), Lat (j), T(j))是IS(j)中興趣點的加權平均，其中j是興趣點的編號。(Long(j)Lat(j)T(j)分別指該點的精度、緯度和時間)
權利要求
1.一種時空軌跡相似度計算方法，其特徵在於，包括 步驟1，定義距離轉角率，刻畫用戶興趣點的特徵； 步驟2，根據經驗閾值，識別用戶興趣點；根據軌跡的用戶興趣點計算其公共興趣點；步驟3，計算分段之間的相似度以及不相似度，其中所述分段為兩個公共興趣點之間的分段；通過定義分段時間、相似分段、相似路線，計算軌跡之間的相似度以及不相似度，從而得到軌跡相似度。
2.如權利要求I所述的時空軌跡相似度計算方法，其特徵在於，所述步驟I還包括 步驟 21,定義 p^、Pi 到 pi+1 的距離轉角率 LATatio(p(i-l), p(i), p(i+l)),其中 p^、Pi、Pi+i分別為用戶興趣點。
3.如權利要求2所述的時空軌跡相似度計算方法，其特徵在於，包括距離轉角率公式如下
4.如權利要求I所述的時空軌跡相似度計算方法，其特徵在於，所述步驟2還包括 步驟41,如果ratio〉P (這裡P是一個經驗閾值)，則認為興趣點P (i)和p(i+l)是同一個興趣點，IS(j)表示軌跡中的j個興趣點；為了計算軌跡的相異程度，用IP(j)表示IS (j), IP (j) = (long (j), Lat (j), T (j))是IS(j)中興趣點的加權平均，其中j是興趣點的編號，
5.如權利要求I所述的時空軌跡相似度計算方法，其特徵在於，所述步驟3還包括 步驟51,位於C (i)和CoIP(i+l)中間的部分為tra(l)中的分段,記做segtM(i)。下述公式計算分段的不相似程度difvector (Segi Ura1)，Segi (tra2)) =Vdifvector (Segi (tra^，Segi (tra2)) +1 nlin_n2in其中，Vdifvector (Segi (tra)，Segi (tra2)) = | | vql (Segi Ura1)) -vql (Segi (tra2)) | +1 | vq2 (Segi (tr B1)) -vq2 (Segi (tra2))nin是軌跡中兩個興趣點之間非公共興趣點的數量。
6.如權利要求I所述的時空軌跡相似度計算方法，其特徵在於，所述步驟3還包括步驟62，分段時間，是指用戶從一個CoIP到另一個CoIP的間隔時間，如果CoIPi= (Longi, Lati, Ti),且 CoIPi+1= (Longi+1, Lati+1, Ti+1),那麼 Ti-Tw, Ti-Tw 即 CoIPi 和 CoIPi+1在軌跡中的分段時間；相似分段，是令SegUtra1)和SegiUra2)分別為丨坪和tra2中的分段,稱SegiUra1) 和Segi (tra2)為相似分段，當兩個分段之間IP的數量相等；兩個分段之間的分段時間的絕對差值小於一個常數，即(Ti Ura1) Ti+1 Ura1)) - (Ti (tra2) Ti+1 (tra2)) | <tp 相似路線，由分段組成，如果有多個連續的相似分段，則為相似路線；假設A和&是相似路線，則認為兩條路線沒有區別，即vdifveetOT (η αΓ&1)，Γ」αΓ&2))=ο;下述公式計算軌跡之間的不相似度
7.一種時空軌跡相似度計算系統，其特徵在於，包括定義轉角率模塊，用於定義距離轉角率，刻畫用戶興趣點的特徵；興趣點模塊，用於根據經驗閾值，識別用戶興趣點；根據軌跡的用戶興趣點計算其公共興趣點；相似度匹配模塊，用於計算分段之間的相似度以及不相似度，其中所述分段為兩個公共興趣點之間的分段；通過定義分段時間、相似分段、相似路線，計算軌跡之間的相似度以及不相似度，從而得到軌跡相似度。
8.如權利要求7所述的時空軌跡相似度計算系統，其特徵在於，所述定義轉角率模塊還包括定義 Pi-i、Pi 到 Pi+i 的距離轉角率 LATatio(p(i-l), p(i), p(i+l)),其中 Pi—pPpPw 分別為用戶興趣點。
9.如權利要求8所述的時空軌跡相似度計算系統，其特徵在於，包括距離轉角率公式如下
10.如權利要求7所述的時空軌跡相似度計算系統，其特徵在於，所述興趣點模塊還包括 經驗閾值模塊，用於如果ratio>P (這裡P是一個經驗閾值)，則認為興趣點P (i)和p(i+l)是同一個興趣點，IS(j)表示軌跡中的j個興趣點；為了計算軌跡的相異程度，用IP(J)表示 IS(j)，IP(j) = (long(j)，Lat(j)，T(j))是 IS(j)中興趣點的加權平均，其中 j是興趣點的編號，
11.如權利要求7所述的時空軌跡相似度計算系統，其特徵在於，所述相似度匹配模塊還包括分段模塊，用於位於c(i)和CoIP(i+l)中間的部分為tra(l)中的分段，記做 segtra (i)；下述公式計算分段的不相似程度difvector (Segi (tra)，Segi (tra2)) =Vdifvector (Segi (tra^，Segi (tra2)) +1 nlin_n2in其中，Vdifvector (Segi (tra)，Segi (tra2)) = | | vql (Segi Ura1)) -vql (Segi (tra2)) | +1 | vq2 (Segi (tr B1)) -vq2 (Segi (tra2))nin是軌跡中兩個興趣點之間非公共興趣點的數量。
12.如權利要求7所述的時空軌跡相似度計算系統，其特徵在於，所述相似度匹配模塊還包括相似度運算模塊，用於分段時間，是指用戶從一個CoIP到另一個CoIP的間隔時間，如果 CoIPi= (Long」 Lati, Ti),且 CoIPi+1= (Long沖 Lati+1，Ti+1)，那麼 Ti-Tw, Ti-Tw 即 CoIPi 和 CoIPi+1在軌跡中的分段時間；相似分段，是令SegiUra1)和SegJtra2)分別為I^a1和a2中的分段,稱SegiUra1)和 Segi (tra2)為相似分段，當兩個分段之間IP的數量相等；兩個分段之間的分段時間的絕對差值小於一個常數，即(Ti Ura1) Ti+1 Ura1)) - (Ti (tra2) Ti+1 (tra2)) | <tp 相似路線，由分段組成，如果有多個連續的相似分段，則為相似路線；假設A和&是相似路線，則認為兩條路線沒有區別，即vdifveetOT (η αΓ&1)，Γ」αΓ&2))=ο;下述公式計算軌跡之間的不相似度
全文摘要
本發明公開一種時空軌跡相似度計算方法及系統，所述方法包括步驟1，定義距離轉角率，刻畫用戶興趣點的特徵；步驟2，根據經驗閾值，識別用戶興趣點；根據軌跡的用戶興趣點計算其公共興趣點；步驟3，計算分段之間的相似度以及不相似度，其中所述分段為兩個公共興趣點之間的分段；通過定義分段時間、相似分段、相似路線，計算軌跡之間的相似度以及不相似度，從而得到軌跡相似度。
文檔編號G06F17/30GK102722541SQ20121016299
公開日2012年10月10日 申請日期2012年5月23日 優先權日2012年5月23日
發明者葉劍, 姚昱旻, 張筱旋, 朱珍民, 杜靜, 王冠男 申請人:中國科學院計算技術研究所