目錄
時(shí)空軌跡相似性度量方法：
- 基于軌跡點(diǎn)的相似性度量方法侯繁；（一般也成為distance-based)
基于軌跡的相似性度量方法充分考慮了軌跡的局部信息偿洁，精確度比較高本谜，但是時(shí)間復(fù)雜度達(dá)到了O(m×n)，其中n和m為軌跡點(diǎn)個(gè)數(shù)衬以。
- 基于軌跡段的相似性度量方法贝攒。(ε-threshold-based)
基于軌跡段相似性度量通過對(duì)軌跡進(jìn)行分段幻赚，然后分別比較每一段的相似性覆享，大大降低了時(shí)間復(fù)雜度椎瘟。但是沒有充分考慮軌跡的局部信息屑那，因此精確率比較低。
以上方法都是把時(shí)間屬性作為簡(jiǎn)單的時(shí)間序列來處理丑罪。時(shí)間屬性屬于重要的屬性只一传黄，把空間和時(shí)間屬性結(jié)合將作為時(shí)空軌跡相似性度量的一個(gè)判斷標(biāo)準(zhǔn)杰扫，使相似性度量方法更加完善。
基于軌跡點(diǎn)的相似性度量方法
基于軌跡點(diǎn)的相似性度量方法又分為全局匹配度量法和局部匹配度量法膘掰。
全局匹配度度量：要求兩條軌跡整體相似章姓。，即軌跡中的每個(gè)點(diǎn)都需要找到對(duì)應(yīng)的匹配點(diǎn)，每個(gè)點(diǎn)對(duì)之間的距離都是相似性度量值的一部分凡伊。具體方法有：Euclid零渐、DTW、ERP系忙。
局部匹配度量法：只要求兩條軌跡部分相似诵盼。無需軌跡中的每個(gè)點(diǎn)都找到對(duì)應(yīng)的匹配點(diǎn)，而且只有部分匹配點(diǎn)之間的距離作為相似性結(jié)果的一部分银还。具體方法有：EDR拦耐、LCSS、k-BCT见剩、LCS、CATS扫俺。
全局匹配度量法
1. Euclid：歐氏距離法則
主要過程是通過計(jì)算軌跡之間對(duì)應(yīng)點(diǎn)之間的歐式距離苍苞，然后累加求和作為最后的度量值。計(jì)算方式最簡(jiǎn)單狼纬。
2. ERP：編輯距離法 Edit Distance on Real Penalty
編輯距離原本是指通過對(duì)字符串進(jìn)行增羹呵、刪、改等操作疗琉，使其中一個(gè)字符串與另一個(gè)字符串完全相同所需要的最小操作次數(shù).
3. DTW：動(dòng)態(tài)時(shí)間扭曲法則 Dynamic Time Warping
對(duì)軌跡進(jìn)行局部的拉伸或者縮放冈欢，從而可以對(duì)不同采樣率和不同長(zhǎng)度的軌跡進(jìn)行比較，DWT距離就是所有最優(yōu)匹配軌跡點(diǎn)間距離的累加和盈简。DTW通過遞歸迭代的方式來計(jì)算軌跡之間的距離凑耻。時(shí)間復(fù)雜度O(m×n)
歐式距離是最簡(jiǎn)單的，只需要累加求和柠贤，時(shí)間復(fù)雜度O(n)香浩，滿足三角不等式的檢索方法（MVP樹，M樹臼勉，Sa樹）邻吭。但是局限性也很大：①采樣率、軌跡點(diǎn)必須一致宴霸；②你須滿足單調(diào)連續(xù)原則且不支持局部時(shí)間扭曲囱晴；③對(duì)噪聲敏感。
DTW和ERP可以對(duì)局部進(jìn)行拉伸或者縮放瓢谢，從而可以對(duì)不同采樣率和不同長(zhǎng)度的軌跡進(jìn)行度量畸写。他們之間的區(qū)別是：①DTW的軌跡點(diǎn)找到匹配的點(diǎn)之后，直接計(jì)算出兩個(gè)軌跡點(diǎn)的距離作為相似性結(jié)果的一部分恩闻；②而ERP發(fā)現(xiàn)該軌跡點(diǎn)與匹配點(diǎn)的距離超過閾值的時(shí)候艺糜，并不計(jì)算該店與匹配點(diǎn)之間的距離，二十計(jì)算該點(diǎn)與一個(gè)特定點(diǎn)（如原點(diǎn)之間的距離）來替代該店與匹配點(diǎn)之間的距離，從而減少噪聲的影響破停。
只有兩條軌跡整體相似是才能被全局匹配度量法判定為相似翅楼。
局部匹配度量法
1. EDR：編輯距離法 Edit Distance on Real sequence
需要計(jì)算兩條軌跡中每個(gè)軌跡點(diǎn)與對(duì)應(yīng)匹配點(diǎn)之間的距離，時(shí)間復(fù)雜度為O(m×n)真慢。
EDR通過將元素之間的距離量化為0 1兩個(gè)值來消除噪聲影響毅臊。因?yàn)槊總€(gè)異常值只可能是EDR值上升1，因此比DTW和ERP更加魯棒黑界。由于EDR將距離量化管嬉，導(dǎo)致了EDR不滿足三角不等式，從而不可以使用傳統(tǒng)的基于距離的索引方法朗鸠。
2. LCSS：最長(zhǎng)公共子序列 Longest Common Subsequence
主要考慮軌跡之間相似的部分作為軌跡相 似性的度量蚯撩，因此對(duì)于一些因匹配距離超過閾值的軌跡點(diǎn)可以跳過，這樣的特征使它對(duì)噪聲具有魯棒性烛占。但是它不考慮相似子序列之間不相似部分胎挎，會(huì)導(dǎo)致判斷不準(zhǔn)確。
EDR將距離量化成0 1忆家，因此帶來了一個(gè)優(yōu)點(diǎn)和一個(gè)缺點(diǎn)：① 對(duì)噪聲的魯棒性相較于DTW和ERP更加魯棒犹菇；②但是EDR不滿足三角不等式，從而不可以使用傳統(tǒng)的基于距離的索引方法芽卿。
LCSS具有以下優(yōu)點(diǎn)：①對(duì)采樣率沒有要求揭芍；②不要求進(jìn)軌跡的長(zhǎng)度相等；③因?yàn)長(zhǎng)CSS只關(guān)注時(shí)空上都比較接近的點(diǎn)對(duì)（否則會(huì)被跳過）卸例，所以不需要對(duì)每個(gè)軌跡點(diǎn)進(jìn)行匹配称杨，對(duì)噪聲點(diǎn)更具有魯棒性。但是也有一些缺點(diǎn)：①也是把距離量化成0 1币厕，因此不滿足三角不等式列另；②只關(guān)注相似的部分，會(huì)導(dǎo)致判斷不準(zhǔn)確旦装。
3. Fréchet：弗雷歇距離度量法
弗雷歇距離度量法（Fréchet distance）由 Fréchet等人提出页衙，通常以直觀的方式描述：人遛狗時(shí) 的狗繩距離 。
4.CATS：Clue-Aware Trajectory Similarity
由于軌跡在采集的時(shí)候可能會(huì)存在大量采樣點(diǎn)缺 失的軌跡段阴绢，而對(duì)象的同一種運(yùn)動(dòng)行為形成的軌跡在空 間上和時(shí)間上應(yīng)該都比較接近店乐，因此Hung等人通過識(shí)別 時(shí)空上相似的軌跡，而推斷出軌跡中缺失采樣點(diǎn) [16] 呻袭。 如圖10所示眨八，前三條軌跡的采樣點(diǎn)缺失十分嚴(yán)重，通過 CATS（CATS: Clue-Aware Trajectory Similarity）方 法左电，可以找出同一模式的軌跡廉侧，將他們的采樣點(diǎn)相互補(bǔ) 充页响，得到一條采樣完整的軌跡。CATS可以支持局部時(shí)間 扭曲段誊，對(duì)軌跡的采樣率和長(zhǎng)度都沒有要求闰蚕，并且對(duì)噪聲 具有魯棒性。
基于軌跡段的相似性度量方法
1.豪斯多夫距離法 (Hausdorff）
Lee等人 [18] 提出了基于軌跡的豪斯多夫距離方法连舍， 主要由三部分組成：①垂直距離没陡，②平行距離，③角距 離索赏。該方法分別從平行距離盼玄，垂直距離和角距離3個(gè)方 面對(duì)軌跡段之間的距離進(jìn)行計(jì)算，比最小邊界矩形法考 慮的更加全面潜腻，精度更高埃儿，時(shí)間復(fù)雜度為O (m ×n )，其 中m 融涣、n 分別為兩條軌跡的軌跡段個(gè)數(shù)蝌箍。q
幾個(gè)要注意的指標(biāo)
形成最終方案時(shí)要一般考慮的問題：local time shifting、retrieval efficiency暴心、metric distance、various gap杂拨、low bounds专普。
