算法面臨的問題
以往的算法，都是單純的去匹配，總是顧此失彼。CATS算法是CACT框架的一環(huán)。CACT框架是 Clustering and Aggregating Clues of Trajectories。包括負(fù)責(zé)度量相似度的clue-aware trajectory similarity（CATS）和clue-aware trajectory clustering（CATC）。最后，是clue-aware trajectory aggregation（CATA）。
CACT框架的思路是：以CATS算法為衡量相似度的基礎(chǔ)，以CATC算法去對軌跡進(jìn)行聚類。最后，線索感知軌跡聚合算法來聚合同一組中的軌跡，以得出相應(yīng)的軌跡模式和路線。
自我感覺：CACT最出彩的地方就是對每一個(gè)cluster都提取出一個(gè)代表性的軌跡作為模板。對于查詢軌跡，不再去匹配所有的軌跡，而是去匹配各個(gè)cluster得到的模版軌跡。這樣是是科學(xué)的。因?yàn)榧偃绮樵冘壽E去匹配數(shù)據(jù)庫里的所有軌跡，由于查詢軌跡和所有的軌跡都不是理想的，都會(huì)收到各種因素的干擾，那么很難有一種完美的且可以實(shí)際實(shí)現(xiàn)的算法去達(dá)到理想的效果。模板必須都是理想的。
針對的問題
時(shí)間和空間上的偏移（誤差）
采樣的傳感器本身就會(huì)存在誤差，在空間上可能出現(xiàn)滯后，在空間上可能出現(xiàn)偏移。
local time shifting
速度不一、用戶的延遲不一、采樣率不一、環(huán)境問題都會(huì)導(dǎo)致同一軌跡都對不上。
噪聲
Silent duration
可能由于設(shè)備壞了，或者沒有信號，導(dǎo)致軌跡的某一段是沉默的（沒有采樣點(diǎn)）
CATS算法簡介
CATS想要同時(shí)使用時(shí)間和空間的co-located點(diǎn)來判斷相似性。
clue的概念也并沒有多么的高級，只是評估兩條軌跡中滿足co-located的點(diǎn)的數(shù)目。
顯然，對于大于閾值的數(shù)值，被判斷成了0。在閾值范圍內(nèi)的，也沒有像EDR或者LCSS一樣，直接判為一個(gè)固定的數(shù)值，而是用了[0, 1]之間的連續(xù)的數(shù)值。像EDR、LCSS這樣的，直接判定為0、1，會(huì)丟失掉很多的信息。顯然，兩個(gè)點(diǎn)越近，數(shù)值越大。
而后使用了時(shí)間上的限制，把一個(gè)數(shù)據(jù)點(diǎn)對齊到目標(biāo)軌跡的最可能相似的點(diǎn)上（按照文章的話說就是包含最強(qiáng)的線索的點(diǎn)）。為了衡量“相似”的概念，提出了score函數(shù)。顧名思義就是一個(gè)點(diǎn)到另一條軌跡的相似性得分。其公式如下：
e,t分別是空間上的閾值和時(shí)間上的邊界。即對于一個(gè)點(diǎn)p，在另一條軌跡上，滿足時(shí)間邊界的所有點(diǎn)中，空間衰減函數(shù)最大的點(diǎn)就是該點(diǎn)的對齊點(diǎn)。
根據(jù)點(diǎn)到軌跡的對齊方法score，提出了軌跡之間相似度的度量CATS：
e、t、Ti、Tj和上文中符號的含義都一樣。
顯然，對于CATS來說，它能夠處理local time shifting。因?yàn)閷τ诓黄ヅ涞狞c(diǎn)，會(huì)之間判斷為0，且對采樣點(diǎn)數(shù)是否相同沒有要求。這一點(diǎn)與LCSS相同：只關(guān)注了相似的點(diǎn)，沒有關(guān)注不相似的點(diǎn)，沒有對不相似的點(diǎn)進(jìn)行懲罰。
算法偽代碼如下：
在最差的情況下，算法復(fù)雜度是O(|Ti||Tj|)。
CATS依靠e和t來克服（更準(zhǔn)確的說是容忍）空間和時(shí)間上的偏差（對正常誤差的抑制比較好）。對于大于時(shí)間偏差的，可以判斷為噪聲點(diǎn)。并且不計(jì)入影響。對于沒有對應(yīng)點(diǎn)的，很大可能上（因?yàn)檫@種點(diǎn)一般空間時(shí)間偏差都很大）也會(huì)被判斷為噪聲點(diǎn)。
綜合而言，CATS只關(guān)注了兩個(gè)軌跡中時(shí)間、空間相似度比較高、匹配度比較好的部分。顯然，這樣做的誤差會(huì)很大。為了消除這個(gè)誤差，使用聚類結(jié)果生成（實(shí)際并不存在的）模版軌跡供給匹配，就能大大減少這個(gè)問題。（LCSS中是不是也是這么用的？）
算法的問題
對于CATS的高還是低沒有一個(gè)絕對的概念?？赡苓@個(gè)數(shù)值需要根據(jù)實(shí)際的應(yīng)用去自行總結(jié)出。
