李旭東，成 烽

(1.南京電子技術(shù)研究所，江蘇 南京 210039；2.武漢大學(xué)測繪遙感信息工程國家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430079)

0 引 言

不斷普及的位置傳感器、飛速發(fā)展的移動互聯(lián)網(wǎng)、以及日益完善的通信基礎(chǔ)設(shè)施，使得各行各業(yè)正在以越來越快的速度采集關(guān)于移動對象的軌跡數(shù)據(jù)。軌跡數(shù)據(jù)是按時(shí)間戳排序的一組位置點(diǎn)，同時(shí)集成了空間信息、時(shí)間信息和屬性信息，并且蘊(yùn)含了豐富多樣的語義信息和行為模式。目前，針對軌跡數(shù)據(jù)的處理與分析已在越來越多的領(lǐng)域得到了應(yīng)用，例如，理解動物遷徙過程中的移動軌跡從而開展動物生態(tài)與行為的研究[1]、基于歷史軌跡與當(dāng)前路徑的臺風(fēng)災(zāi)害實(shí)時(shí)預(yù)警[2]，以及在智能交通系統(tǒng)中，獲取與分析車輛軌跡信息以提高交通調(diào)度的效率[3]。

在軌跡數(shù)據(jù)激增和大數(shù)據(jù)技術(shù)發(fā)展的背景下，如何從軌跡數(shù)據(jù)中挖掘有意義的群體移動模式，已經(jīng)成為軌跡數(shù)據(jù)分析領(lǐng)域的研究熱點(diǎn)之一。Gudmundsson等提出了Flock移動模式[4]，對在指定圓形區(qū)域中連續(xù)移動至少k個(gè)時(shí)間片的移動對象進(jìn)行了探測。為了克服Flock關(guān)于區(qū)域形狀和群體大小的限制，Jeung等提出了Convoy模式[5]，不再強(qiáng)調(diào)移動區(qū)域的形狀，僅要求對象群之間是密度相連的。Aung等考慮到在Convoy中，某些參與對象可能會暫時(shí)離開群體，提出了dynamic convoy 和evolving convoy模式[6]。Li等進(jìn)一步弱化限制條件，即參與對象僅需持續(xù)k個(gè)時(shí)間片，且不一定是連續(xù)的，提出了更通用化的Swarm模型[7]。為了模擬游行、抗議、擁堵等群體事件，Zheng等提出Gathering模式[8]，用以表示大量對象時(shí)空聚集而形成持續(xù)且穩(wěn)定的高密度區(qū)域。

經(jīng)典軌跡計(jì)算用于分析具有相似移動路徑的軌跡分組，屬于一類典型的群體移動模式分析，其主要技術(shù)思想是度量軌跡之間的相似性，將大規(guī)模軌跡數(shù)據(jù)聚類成簇，并進(jìn)一步發(fā)現(xiàn)軌跡簇的整體移動特征，從而用一條代表性軌跡來表征軌跡簇的群體移動模式。經(jīng)典軌跡描述了大規(guī)模軌跡數(shù)據(jù)的群體移動特征，在刻畫海量軌跡時(shí)空特征、分析群體行為模式和預(yù)測移動對象路徑等方面具有十分重要的應(yīng)用意義。在經(jīng)典軌跡分析方面，Gaffney等提出了一種基于模型的軌跡聚類算法[9]，將其用于經(jīng)典軌跡的生成；Jiawei Han等提出了基于軌跡分段思想的經(jīng)典軌跡生成算法TRACLUS[10]；鄭林江等人將軌跡映射到城市網(wǎng)格空間中，利用密度閾值提取熱點(diǎn)格網(wǎng)[11]，并通過合并熱點(diǎn)格網(wǎng)來尋找經(jīng)典軌跡。

本文面向大規(guī)模軌跡數(shù)據(jù)，聚焦于群體移動對象的經(jīng)典軌跡計(jì)算問題，提出了一種基于密度峰值聚類的經(jīng)典軌跡計(jì)算方法，包括相似矩陣計(jì)算、軌跡聚類分析和經(jīng)典軌跡生成三個(gè)前后無縫銜接的步驟。在相似性度量方面，我們采用并改進(jìn)了顧及軌跡幾何與方向的SSPD方法[12]；在軌跡數(shù)據(jù)聚類方面，我們引入了密度峰值聚類方法[13]，并使用其K近鄰版本[14]，以消除參數(shù)選擇的不利影響?？紤]到在密度峰值聚類中，中心點(diǎn)表征了基于軌跡距離的局部密度最大軌跡，我們直接將軌跡蔟中心作為經(jīng)典軌跡輸出。基于船舶軌跡的實(shí)驗(yàn)表明，本文方法可以有效從大規(guī)模軌跡中分析出經(jīng)典軌跡，且同TRACLUS算法相比，本文方法輸出的經(jīng)典軌跡更為真實(shí)自然。

1 經(jīng)典軌跡計(jì)算框架

經(jīng)典軌跡計(jì)算是指從軌跡群中選擇一條或多條最具代表性的軌跡，其他軌跡與這些代表性軌跡中的一條具有相同或相似的行經(jīng)路線，即分析大規(guī)模軌跡的頻繁模式，屬于一類典型的軌跡群整體移動模式挖掘方法。例如，通過分析船舶歷史軌跡移動規(guī)律的相似性，生成其經(jīng)典軌跡，可以用來預(yù)測當(dāng)前船舶的可能移動路徑。為此，本文提出了一個(gè)基于密度峰值聚類的經(jīng)典軌跡計(jì)算方法，其分析框架見圖1所示。

首先進(jìn)行預(yù)處理，通過速度等閾值過濾掉噪聲點(diǎn)，并采用高斯函數(shù)進(jìn)行平滑處理。然后依次執(zhí)行三個(gè)主要步驟：(1)相似度計(jì)算，(2)密度峰值聚類，(3)經(jīng)典軌跡提取。相似度矩陣計(jì)算根據(jù)軌跡之間的相似度度計(jì)算出距離度量，并形成對稱的相似度矩陣；密度峰值聚類以軌跡相似度矩陣為輸入，采用密度峰值聚類算法進(jìn)行面向軌跡的聚類處理，得到軌跡聚類簇的集合；經(jīng)典軌跡提取對每一個(gè)軌跡數(shù)量達(dá)到閾值要求的軌跡聚類簇，選擇其聚類中心對應(yīng)的軌跡作為經(jīng)典軌跡的輸出。

圖1 基于密度峰值聚類的經(jīng)典軌跡計(jì)算框架

密度峰值聚類算法將面向大規(guī)模軌跡數(shù)據(jù)，基于軌跡距離來搜索那些具有局部密度極大值，且距離更高密度中心較遠(yuǎn)的軌跡。顯然，該算法不僅生成關(guān)于軌跡的聚類蔟，而且輸出局部的聚類中心。在一個(gè)軌跡蔟中，聚類中心是具有最高密度的軌跡，自然成為該軌跡蔟的代表性軌跡，即經(jīng)典軌跡，故本文的關(guān)鍵問題在于兩方面，一是軌跡相似度計(jì)算，二是軌跡數(shù)據(jù)聚類。

2 軌跡相似度計(jì)算

軌跡相似度計(jì)算[15]通過衡量兩條軌跡之間的相似程度，形成一個(gè)正的數(shù)值型距離值，越小表示軌跡越相似，取0則表示兩條軌跡途徑同一路徑。顯然，基于相似度的軌跡距離函數(shù)定義將直接影響到相似度矩陣的計(jì)算結(jié)果，進(jìn)而關(guān)系到軌跡聚類結(jié)果的好壞。在軌跡相似性度量方面，學(xué)者們先后提出多種關(guān)于軌跡距離的定義，如歐式距離、DTW距離[16]、LCSS距離[17]、EDR距離[18]，等。由于軌跡采樣頻率不同、路徑長度不一、存在噪聲和漂移，以及具有方向性，我們期望軌跡相似度距離計(jì)算方法具備以下性質(zhì)：(1)將軌跡作為整體來計(jì)算相似度；(2)允許軌跡具有不同長度；(3)滿足三角不等式；(4)對噪聲有一定健壯性；(5)不僅識別出軌跡形狀上的相似性，而且考慮軌跡點(diǎn)的位置與方向。

為此，我們選擇SSPD(Symmetric Segment Path Distance)距離，其計(jì)算原理見圖2所示。首先計(jì)算軌跡A上每一個(gè)軌跡點(diǎn)到軌跡B上連續(xù)兩個(gè)點(diǎn)所夾線段的最小距離，然后累加這一點(diǎn)-線段距離，并除以軌跡A上軌跡點(diǎn)的數(shù)量，即得出軌跡A到軌跡B的距離。類似的，計(jì)算出軌跡B到軌跡A的距離，并將到軌跡A到軌跡B的距離和軌跡B到軌跡A的距離求和之后取平均，最終得到軌跡A和軌跡B的SSPD距離。

圖2 軌跡的SSPD距離計(jì)算

在SSPD距離計(jì)算中，軌跡A上某個(gè)點(diǎn)投影到軌跡B上某個(gè)線段后，軌跡A上后續(xù)點(diǎn)只能投影到軌跡B上后續(xù)線段，因此，SSPD距離除了顧及形狀與位置相似性之外，還能夠區(qū)分出方向差異。此外，SSPD支持非等長軌跡的距離計(jì)算，并且是對稱的，可度量的，即滿足三角不等式。平均值處理固然使得SSPD距離在一定程度上降低噪聲的影響，但在某些情況下將嚴(yán)重放大噪聲點(diǎn)的影響，使得本來相似的兩條軌跡之間距離變得特別大，如圖3所示。

圖3 帶噪聲點(diǎn)的SSPD距離

在軌跡A中，點(diǎn)A3是一個(gè)噪聲點(diǎn)，由于SSPD距離在計(jì)算點(diǎn)—線段投影時(shí)不能回溯，使得軌跡A在噪聲點(diǎn)A3之后的點(diǎn)全部匹配到軌跡B的尾點(diǎn)B5，導(dǎo)致累積之后的誤差變得十分可觀。為此，我們從以下兩方面來改進(jìn)SSPD距離的計(jì)算，使之對于噪聲數(shù)據(jù)更為魯棒：

(1)允許回溯k個(gè)點(diǎn)。計(jì)第i個(gè)點(diǎn)的投影距離為d1，計(jì)算其到第(i-j)(k≥j>0)個(gè)點(diǎn)的投影線段及后續(xù)線段的最小投影距離d2，如果d1/d2超過某一閾值，那么將作為d2作為第i個(gè)點(diǎn)的投影距離，相應(yīng)線段為第i個(gè)點(diǎn)的匹配線段；

(2)如果當(dāng)前點(diǎn)的最終投影距離超過某一閾值，將該點(diǎn)標(biāo)記為噪聲，不參與SSPD距離的計(jì)算，從而消除噪聲點(diǎn)的影響。

在圖3中，如果A3到B4B5的投影距離大于閾值，改進(jìn)的SSPD距離將其標(biāo)記為噪聲點(diǎn)，后續(xù)點(diǎn)將從B1B2嘗試投影；否則的話，A3投影到B4B5，A4則可以跳過A3，其投影的目標(biāo)線段可以回溯到B1B2，從而正確投影到B2B3。

3 基于軌跡距離的密度峰值聚類

經(jīng)過相似度計(jì)算之后，任意兩條軌跡之間的距離被量化為一個(gè)零維數(shù)值，從而形成一個(gè)相似度矩陣，在此基礎(chǔ)上有多種聚類算法可供選擇，如K-MEANS[19]、DBSCAN[20]等，但是，面向軌跡的聚類算法應(yīng)具備以下特點(diǎn)：(1)挖掘出軌跡長程運(yùn)動模式，(2)發(fā)現(xiàn)任意形狀的簇，(3)對全局參數(shù)不敏感，(4)不需要先驗(yàn)知識。為此，我們選擇2014年發(fā)表于《Science》期刊上的密度峰值聚類算法[13]。該算法的核心思想十分簡潔，基于兩個(gè)樸素的假設(shè)來確定聚類中心：(1)聚類中心是局部密度的最大對象；(2)聚類中心到其他聚類中心的距離相對較遠(yuǎn)，以不被歸入其他聚類中心所屬聚類簇內(nèi)。密度峰值聚類算法對于任意一條軌跡Ti，需要計(jì)算局部密度ρi和上向距離δi，即到更大密度聚類中心的最小距離。ρi和δi的定義分別如下：

(1)

(2)

其中，dij為軌跡Ti和Tj的相似度距離，而dc為截?cái)嗑嚯x。從定義不難發(fā)現(xiàn)，局部密度的計(jì)算易受截?cái)嗑嚯xdc的影響。在數(shù)據(jù)規(guī)模較大時(shí)，局部密度的計(jì)算結(jié)果對于截?cái)嗑嚯xdc有一定的健壯性，而在數(shù)據(jù)規(guī)模較小時(shí)，由于數(shù)據(jù)分布不一定符合真實(shí)分布情況，此時(shí)截?cái)嗑嚯x取值的影響不可忽略。為此，我們引入一種改進(jìn)策略，將K最近鄰思想引入到局部密度計(jì)算中，從而形成基于K最近鄰的密度峰值聚類算法[14]，其局部密度ρi的定義被修正為如下所示。其中，KNN(i)為樣本Ti的的K最近鄰軌跡集。

(3)

由于不需要設(shè)置硬性的截?cái)嗑嚯xdc，局部密度計(jì)算在不同規(guī)模數(shù)據(jù)集中是自適應(yīng)的。當(dāng)樣本Ti到其K最近鄰的距離越小，局部密度越大。基于K最近鄰的密度峰值聚類算法雖然也存在K值的選取問題，但對于聚類效果的影響較小，且不會改變對聚類簇中心的選擇。

在完成所有軌跡的局部密度和上向距離計(jì)算之后，便可生成一個(gè)橫軸為局部密度，縱軸為上向距離的二維決策圖。在決策圖中，那些局部密度ρ與上向距離δ較為突出的對象將被視作聚類簇中心，即擁有較大上向距離且局部密度大于閾值的對象。當(dāng)?shù)玫骄垲愔行闹?，進(jìn)一步可對所有軌跡進(jìn)行聚類簇分配，將每條軌跡分配到距離最近，且密度大于自身的軌跡所屬的聚類簇中。

4 經(jīng)典軌跡生成及實(shí)驗(yàn)

4.1 經(jīng)典軌跡生成

當(dāng)計(jì)算得到軌跡簇集合以后，下一步需要從每一個(gè)軌跡蔟中找到最能代表本簇整體移動趨勢的經(jīng)典軌跡，主要有三類代表性方法：(1)最優(yōu)代表法，從軌跡簇中選出一條最具代表性的軌跡作為經(jīng)典軌跡輸出，(2)等間距合并法，等距重采樣軌跡簇中的軌跡，據(jù)此計(jì)算重采樣點(diǎn)的平均坐標(biāo)，從而輸出形成經(jīng)典軌跡，(3)掃描線法，首先確定軌跡蔟的整體運(yùn)動方向，進(jìn)一步得到軌跡蔟的掃描線，然后計(jì)算掃描線與簇中軌跡的相交點(diǎn)，以其平均坐標(biāo)來形成經(jīng)典軌跡的時(shí)空點(diǎn)。后兩種方法輸出的是合成軌跡，可能在軌跡蔟中沒有任何一條軌跡的路徑與此相似，使得其輸出只是擬合了軌跡蔟的時(shí)空分布，但偏離了用戶對于經(jīng)典軌跡的認(rèn)知。此外，這兩種方法的計(jì)算比較耗時(shí)，其計(jì)算復(fù)雜度將隨著軌跡數(shù)目和采樣點(diǎn)數(shù)量的增加呈指數(shù)級增長。

為此，我們選用最優(yōu)代表法來輸出經(jīng)典軌跡，由于不需要形成合成軌跡，其實(shí)現(xiàn)較為簡單，計(jì)算非常高效。一種直觀的實(shí)現(xiàn)最優(yōu)代表法的策略是針對每一個(gè)軌跡簇，將每條軌跡到其他軌跡的相似度距離之和作為該軌跡的分?jǐn)?shù)，從而選擇得分最高的軌跡作為該軌跡蔟的經(jīng)典軌跡。具體到密度峰值聚類算法中，聚類中心是具有局部密度極大值，且距離更高密度中心較遠(yuǎn)的軌跡，即在一個(gè)軌跡蔟中，聚類中心是具有最高密度的軌跡，也就是說，其他軌跡到該軌跡的距離之和是最小的，因而可以輸出為該軌跡蔟的代表性軌跡，即經(jīng)典軌跡。

4.2 經(jīng)典軌跡實(shí)驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)為模擬產(chǎn)生某海域的船舶軌跡。這個(gè)軌跡數(shù)據(jù)集包含約6百條行船記錄，共計(jì)17736個(gè)軌跡點(diǎn)，其中，每一條軌跡包含船舶的經(jīng)度、緯度、時(shí)間戳和編碼。圖4展示了該軌跡集的密度峰值聚類決策圖，其中，橫坐標(biāo)和縱坐標(biāo)分別表示局部密度和上向距離。

在決策圖中，局部密度與上向距離同時(shí)較大的軌跡將形成一個(gè)軌跡蔟，且該軌跡作為該軌跡蔟的聚類中心，輸出成為代表該軌跡蔟的經(jīng)典軌跡。實(shí)際上，軌跡的時(shí)空分布可能異常復(fù)雜，軌跡蔟的界定并不是一件很容易的事情。以圖4為例，點(diǎn)1和點(diǎn)2所代表的軌跡簇聚類效果較為顯著，點(diǎn)3雖然局部密度不大，但有較大的上向距離，仍可作為一個(gè)軌跡聚類簇(聚集的軌跡數(shù)量雖少，但其空間走向不同于其它軌跡，仍然是目標(biāo)所走的路徑之一)。后續(xù)選擇哪些軌跡來形成聚類中心，卻很難清晰地確定出來。盡管如此，決策圖給出的關(guān)于軌跡聚類信息有比較直觀的呈現(xiàn)，是一個(gè)較好的輔助用戶選擇軌跡蔟及輸出經(jīng)典軌跡的可視化工具。

圖4 船舶軌跡的密度峰值聚類決策圖

在進(jìn)一步分析圖4的聚類決策圖之后，我們將軌跡蔟數(shù)量最終選定為5，即輸出5條經(jīng)典軌跡，見圖5a)所示，圖6進(jìn)一步展示了其中2條經(jīng)典軌跡所代表的軌跡蔟。與此同時(shí)，我們也采用TRACLUS算法來計(jì)算船舶數(shù)據(jù)的經(jīng)典軌跡，見圖5b)所示，共輸出6條經(jīng)典軌跡。不難從圖5和6看出，密度峰值聚類方法輸出的經(jīng)典軌跡是真實(shí)存在的，即對于每一條經(jīng)典軌跡來說，有大量軌跡沿著相同或相似的路徑移動，而TRACLUS方法輸出的經(jīng)典軌跡是合成的，雖然比較符合軌跡數(shù)據(jù)的時(shí)空分布，但實(shí)際上很少有真實(shí)軌跡是沿此路徑移動的。以圖5b)上方輸出的長直線經(jīng)典軌跡為例，沒有任何一條船舶軌跡的走向與此該路徑相同或相似。因此，同TRACLUS方法相比，密度峰值聚類算法是一種行之有效的經(jīng)典軌跡計(jì)算方法

圖6 船舶軌跡的軌跡簇示例

5 結(jié) 語

在軌跡數(shù)據(jù)激增和大數(shù)據(jù)技術(shù)發(fā)展的背景下，如何從大規(guī)模軌跡數(shù)據(jù)中挖掘有意義的群體移動模式，已經(jīng)成為軌跡數(shù)據(jù)分析領(lǐng)域的研究熱點(diǎn)之一。經(jīng)典軌跡是群體軌跡移動時(shí)呈現(xiàn)出的相同或相似路徑，但由于存在漂移噪聲、非均勻采樣、起止點(diǎn)不一致等原因，經(jīng)典軌跡計(jì)算并不是一件容易的事情?？紤]到經(jīng)典軌跡在其局部存在大量相似的軌跡，本文提出了一種基于密度峰值聚類算法的經(jīng)典軌跡計(jì)算方法，首先采用顧及軌跡幾何與方向的SSPD方法來計(jì)算軌跡相似度，然后引入了密度峰值聚類算法來聚類軌跡數(shù)據(jù)，最后直接將峰值點(diǎn)對應(yīng)的軌跡輸出為經(jīng)典軌跡。

本文的貢獻(xiàn)主要有三方面：(1)提出了一種基于密度峰值聚類的經(jīng)典軌跡計(jì)算框架，其計(jì)算過程更為簡潔有效，(2)從噪聲抑制和回溯匹配兩方面改進(jìn)了SSPD距離的計(jì)算，消除了噪聲點(diǎn)對于軌跡距離的放大效應(yīng)，(3)顧及了軌跡數(shù)據(jù)的復(fù)雜特征，采用K最近鄰思想來計(jì)算軌跡的局部密度?；诖败壽E的實(shí)驗(yàn)表明，本文方法可以有效從大規(guī)模軌跡中分析出經(jīng)典軌跡，且同TRACLUS算法相比，輸出的經(jīng)典軌跡更加真實(shí)自然。