[發(fā)明專利]一種時空軌跡相似度計算方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201210162995.2
• 申請日: 2012-05-23
• 公開（公告）號: CN102722541A
• 公開（公告）日: 2012-10-10
• 發(fā)明（設計）人: 葉劍;朱珍民;張筱旋;王冠男;姚昱旻;杜靜
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京律誠同業(yè)知識產(chǎn)權代理有限公司 11006
• 代理人: 祁建國;梁揮

技術領域

本發(fā)明涉及數(shù)據(jù)挖掘領域，特別涉及一種時空軌跡相似度計算方法及系統(tǒng)。

背景技術

近年來，諸如平板電腦、智能手機等支持GPS的移動設備發(fā)展迅速，越來越多的人開始使用基于位置的服務（LBS），例如定位、位置共享等等，大量時空信息被上傳和共享。記錄用戶移動歷史的同時，這些位置信息也能夠在一定程度上反應用戶的興趣、偏好以及生活規(guī)律。為此，時空軌跡作為計算機應用的一大研究熱點，在普適計算、數(shù)據(jù)挖掘和社會網(wǎng)絡等領域受到了廣泛關注。

人類活動具有不同程度的共性，這種共性差異映射到活動軌跡上，導致軌跡之間呈現(xiàn)不同程度的相似性。相應地，軌跡的相似程度反應了活動的共性，進而關系到相近似的人類習慣和偏好。正因如此，如何科學地刻畫軌跡之間的相似度是當前軌跡模式挖掘等研究工作所面臨的最重要問題之一。

當前，軌跡相似度計算方法考慮因素包括：子列重疊程度、相近的位置數(shù)目、地點的數(shù)目等。然而，軌跡不是單純的序列，用序列包含關系去刻畫軌跡之間的關系是遠遠不夠的。此外，計算的粒度也是這類工作所面臨的困難，軌跡的離散化程度越高，和原始軌跡的偏差就越大，而細粒度的計算又難免降低效率。

發(fā)明內(nèi)容

為解決上述問題，本發(fā)明提供了有效利用歐式空間的度量屬性和笛卡爾坐標系中的向量關系，刻畫軌跡模式之間的相似度。該方法可應用于分析人的活動模式，可作為個性化推薦的依據(jù)，以及可以用于構建和分析基于位置的社會網(wǎng)絡。

本發(fā)明的目的在于提供一種全新的路線相似度計算方法，該方法基于幾何特征，充分考慮到路線在地理空間上的特點，同時具有高準確性和較高計算效率。

本發(fā)明公開一種時空軌跡相似度計算方法，包括：

步驟1，定義距離轉角率，刻畫用戶興趣點的特征；

步驟2，根據(jù)經(jīng)驗閾值，識別用戶興趣點；根據(jù)軌跡的用戶興趣點計算其公共興趣點；

步驟3，計算分段之間的相似度以及不相似度，其中所述分段為兩個公共興趣點之間的分段；通過定義分段時間、相似分段、相似路線，計算軌跡之間的相似度以及不相似度，從而得到軌跡相似度。

所述的時空軌跡相似度計算方法，所述步驟1還包括：

步驟21，定義p_i-1、p_i到p_i+1的距離轉角率LATatio(p(i-1),p(i),p(i+1))，其中p_i-1、p_i、p_i+1分別為用戶興趣點。

所述的時空軌跡相似度計算方法，包括：距離轉角率公式如下

其中，ε是滿足下述條件的任意一個常量：

且

其中，是向量的模，是的第二小值。如果ε滿足一下不等式：

且

其中，sec和th分別表示第二和第三，因此是的第三小值。

所述的時空軌跡相似度計算方法，所述步驟2還包括：

步驟41，如果ratio>ρ（這里ρ是一個經(jīng)驗閾值），則認為興趣點p(i)和p(i+1)是同一個興趣點，IS(j)表示軌跡中的j個興趣點；為了計算軌跡的相異程度，用IP(j)表示IS(j)，IP(j)=(long(j),Lat(j),T(j))是IS(j)中興趣點的加權平均,其中j是興趣點的編號，