郭博雷 田晗 湯玲 杜志強(qiáng)

（1.中國(guó)電子科技集團(tuán)公司第二十七研究所 河南鄭州 450047；2.南京北斗創(chuàng)新應(yīng)用科技研究院有限公司 江蘇南京 211500；3.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室 湖北武漢 430072）

作為一個(gè)整體概念，時(shí)空不僅是現(xiàn)實(shí)物體存在的維度，也是人類認(rèn)知和認(rèn)識(shí)世界的模式［1］。具有時(shí)間和空間屬性的數(shù)據(jù)或信息出現(xiàn)在日常生產(chǎn)、生活和經(jīng)濟(jì)文化活動(dòng)的各個(gè)領(lǐng)域。時(shí)空軌跡，即記錄運(yùn)動(dòng)物體位置隨時(shí)間變化的數(shù)據(jù)，是最典型的時(shí)空數(shù)據(jù)類型。近年來(lái)，隨著各種傳感器和定位芯片的大量安裝，數(shù)據(jù)不斷積累，數(shù)據(jù)內(nèi)容不斷豐富，它所包含的信息和知識(shí)反映了運(yùn)動(dòng)物體的不同運(yùn)動(dòng)規(guī)律和行為模式，具有相當(dāng)大的挖掘價(jià)值。其中，軌跡相似性是軌跡之間最基本的模式。如何綜合考慮軌跡形狀和位置不確定性等因素，衡量軌跡和軌跡子段之間的相似性，是許多軌跡數(shù)據(jù)挖掘和分析應(yīng)用的要解決的問(wèn)題。

軌跡相似性分析和相似模式計(jì)算是時(shí)空數(shù)據(jù)挖掘的重要內(nèi)容，是時(shí)空數(shù)據(jù)諸多應(yīng)用的基礎(chǔ)，如異常的軌跡聚類、熱點(diǎn)和頻繁模式挖掘等相關(guān)領(lǐng)域一直保持著較高的研究興趣［2］。時(shí)空建模、時(shí)空分析、時(shí)空模式挖掘等相關(guān)領(lǐng)域的研究一直占據(jù)著相當(dāng)大的比重，尤其是基于軌跡數(shù)據(jù)分析、挖掘和計(jì)算的研究，往往基于新的底層模型擴(kuò)展新場(chǎng)景?？臻g數(shù)據(jù)新應(yīng)用的新時(shí)空軌跡建模和相似性分析再次成為該領(lǐng)域?qū)W者關(guān)注的焦點(diǎn)。

時(shí)空軌跡相似性分析屬于計(jì)算機(jī)科學(xué)和地理信息科學(xué)的交叉領(lǐng)域，其關(guān)鍵技術(shù)包括通用時(shí)空數(shù)據(jù)模型、時(shí)空軌跡數(shù)據(jù)模型、軌跡相似性度量方法、軌跡子段匹配與相似模式挖掘等。結(jié)合本文研究?jī)?nèi)容，下面對(duì)時(shí)空數(shù)據(jù)模型、時(shí)空軌跡模型及軌跡相似性度量與計(jì)算等方面的研究現(xiàn)狀作分別介紹。

1 時(shí)空數(shù)據(jù)模型

時(shí)空動(dòng)態(tài)變化過(guò)程是空間信息在時(shí)間域的擴(kuò)展和完善，傳統(tǒng)的空間對(duì)象就是時(shí)空對(duì)象在某一時(shí)刻的空間瞬態(tài)［3］。時(shí)空數(shù)據(jù)著重于時(shí)空過(guò)程中的時(shí)序關(guān)系和時(shí)空因果聯(lián)系，使設(shè)計(jì)者、開(kāi)發(fā)者和用戶能夠更好地實(shí)現(xiàn)時(shí)空對(duì)象時(shí)間和空間信息的動(dòng)態(tài)表達(dá)與建模。時(shí)空軌跡的表達(dá)與建模更加依賴于通用時(shí)空數(shù)據(jù)模型的設(shè)計(jì)。時(shí)空數(shù)據(jù)建模所面臨的主要難點(diǎn)如圖1所示［4］。

圖1 時(shí)空數(shù)據(jù)建模所面臨的主要難點(diǎn)

在此領(lǐng)域還有多位學(xué)者引入了多樣化的建模方法，提出了一系列各有側(cè)重的模型成果，如圖2所示［5］。

圖2 時(shí)空數(shù)據(jù)模型

但這些模型大多只是在上層設(shè)計(jì)概念模型，沒(méi)有觸及數(shù)據(jù)底層的組織方式，所以，大多是屬于數(shù)據(jù)與應(yīng)用之間的中間層級(jí)模型，不具備通用性，且對(duì)時(shí)空因果、時(shí)空關(guān)聯(lián)等模式支撐不足，無(wú)法在更廣泛的問(wèn)題場(chǎng)景中發(fā)揮作用。所以，業(yè)界也出現(xiàn)了一些從數(shù)據(jù)生產(chǎn)和轉(zhuǎn)換層面著手的模型設(shè)計(jì)，典型代表就是英國(guó)陸地測(cè)量部的MasterMap項(xiàng)目。如今，大多數(shù)GIS 都是基于圖層要素模型系統(tǒng)來(lái)組織和管理空間數(shù)據(jù)的?；贠GC 標(biāo)準(zhǔn)下的單元素模型，形成一套結(jié)合空間對(duì)象和平鋪地圖的混合數(shù)據(jù)結(jié)構(gòu)。底層空間數(shù)據(jù)庫(kù)也主要基于關(guān)系模型。

2 軌跡數(shù)據(jù)模型

隨著各類位置傳感器在移動(dòng)實(shí)體的廣泛安裝，移動(dòng)對(duì)象的軌跡數(shù)據(jù)成為數(shù)據(jù)量最大的時(shí)空數(shù)據(jù)類型，最常見(jiàn)的為記錄車輛、船只、飛行器、野生動(dòng)物等移動(dòng)物體的軌跡數(shù)據(jù)。許多研究部門和企業(yè)都公開(kāi)了大規(guī)模的軌跡數(shù)據(jù)集，以支撐更加開(kāi)放、多元的科學(xué)研究，例如，滴滴公司的“蓋亞”計(jì)劃公開(kāi)了數(shù)個(gè)城市的滴滴快車軌跡數(shù)據(jù)，數(shù)據(jù)量達(dá)到了數(shù)百GB。相應(yīng)地，面向新的數(shù)據(jù)現(xiàn)狀和應(yīng)用場(chǎng)景，針對(duì)軌跡數(shù)據(jù)建模的研究也層出不窮，取得了許多新的進(jìn)展。軌跡模型的研究可以追溯到20世紀(jì)70年代，人們?yōu)榱嗣枋鲲Z風(fēng)的移動(dòng)軌跡，反映颶風(fēng)異動(dòng)情況和態(tài)勢(shì)，以進(jìn)行后續(xù)的分析和預(yù)測(cè)，設(shè)計(jì)了最初的軌跡數(shù)據(jù)模型［6］，后續(xù)也發(fā)展了很多軌跡數(shù)據(jù)模型，如圖3所示。

圖3 軌跡數(shù)據(jù)模型類別

在軌跡不確定性建模方面，一種多粒度模型值得特別注意，它使用棱錐狀結(jié)構(gòu)來(lái)描述一個(gè)移動(dòng)的物體在兩個(gè)位置采樣點(diǎn)之間可能的路徑區(qū)域，用首尾相接的Bead 形成的連續(xù)的珠串表示整條軌跡［7］。其中使用的Bead模型來(lái)源于時(shí)間地理框架，因形態(tài)特征也被稱為Prism模型，其數(shù)學(xué)基礎(chǔ)在多個(gè)文獻(xiàn)中得到了進(jìn)一步的闡述，包括時(shí)空路徑和時(shí)空棱錐等時(shí)間地理學(xué)的基本要素。時(shí)空Bead 模型對(duì)軌跡數(shù)據(jù)離散采樣和插值所帶來(lái)的位置不確定性進(jìn)行了建模，但時(shí)空三維空間中融合了空間和時(shí)間特征的立體Bead 不便于處理和計(jì)算。一個(gè)經(jīng)典的簡(jiǎn)化方法是將Bead 模型投影到空間二維平面上（見(jiàn)圖4），成為一個(gè)以采樣點(diǎn)為焦點(diǎn)的橢圓，再進(jìn)行后續(xù)的分析和計(jì)算。很多文獻(xiàn)已經(jīng)基于Bead投影橢圓進(jìn)行了可達(dá)性計(jì)算、位置分布預(yù)測(cè)等研究工作［8］。

圖4 B ead 模型在空間平面上的橢圓投影

其他考慮空間位置不確定性的軌跡模型還包括緩沖區(qū)模型、圓筒模型、立方網(wǎng)格模型等，大多采用將采樣點(diǎn)或采樣點(diǎn)間的插值線向外按不同的幾何模型擴(kuò)展一定的距離，作為移動(dòng)對(duì)象可能的位置范圍［8］。

3 時(shí)空軌跡相似性度量方法分類

3.1 時(shí)空軌跡

軌跡數(shù)據(jù)庫(kù)T={T1，T2，T3，…，Tf}，包含一系列的原始軌跡，f表示軌跡庫(kù)中軌跡的條數(shù)，其中，每一條軌跡Tj(1≤j≤f) 都是由GPS 等設(shè)備記錄的位置點(diǎn){p1，p2，p3，…，pn}的集合，pi表示的軌跡點(diǎn)通常使用經(jīng)度、緯度、時(shí)間戳表示，即(pi·x，pi·y，pi·t)，i表示點(diǎn)在軌跡中的位置。查詢序列也是一條軌跡，本文用Q={q1，q2，q3，…，qm}表示，其中，m表示查詢序列中元素的個(gè)數(shù)。

3.2 時(shí)空軌跡相似性度量方法分類

由于時(shí)空軌跡相似性度量主要依賴于軌跡之間距離的定義，軌跡之間的距離使用軌跡之間的匹配程度來(lái)表示，不同的軌跡匹配度量方法對(duì)軌跡之間的匹配程度有著不同的解釋［9］。

本文將時(shí)空軌跡相似性度量方法分為兩類：基于軌跡點(diǎn)的相似性度量方法和基于軌跡段的相似性度量方法，如圖5所示。由于軌跡主要是以軌跡點(diǎn)的方式進(jìn)行存儲(chǔ)，當(dāng)對(duì)軌跡進(jìn)行相似性度量時(shí)，最直觀的方式就是利用兩條軌跡中對(duì)應(yīng)軌跡點(diǎn)之間的距離來(lái)度量軌跡之間的相似性［10］?；谲壽E點(diǎn)的相似度測(cè)量方法有很多種，每種方法都有自己獨(dú)特的相似度定義和應(yīng)用場(chǎng)景。例如，一些測(cè)量方法認(rèn)為兩條軌跡只需要部分相似，它們是相似的；有些測(cè)量方法認(rèn)為兩條軌跡整體上是相似的，它們是相似的。因此，本文將基于軌跡點(diǎn)的相似度測(cè)量方法分為兩類：全局匹配度量法和局部匹配度量法，具體分類如圖5所示。

圖5 軌跡相似性度量方法分類

4 結(jié)語(yǔ)

時(shí)空軌跡的相似性分析與計(jì)算是眾多軌跡模式挖掘應(yīng)用的重要手段，而軌跡的相似性度量是相似分析等上游應(yīng)用的重要基礎(chǔ)。對(duì)不同數(shù)據(jù)條件和應(yīng)用場(chǎng)景的軌跡相似性度量進(jìn)行研究，具有重要的理論和實(shí)用價(jià)值，并可以有效促進(jìn)空間數(shù)據(jù)分析與挖掘方法多樣化發(fā)展。