一種基于密度峰值聚類(lèi)的經(jīng)典軌跡計(jì)算方法

李旭東，成 烽

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 基于軌跡距離的密度峰值聚類(lèi)

經(jīng)過(guò)相似度計(jì)算之后，任意兩條軌跡之間的距離被量化為一個(gè)零維數(shù)值，從而形成一個(gè)相似度矩陣，在此基礎(chǔ)上有多種聚類(lèi)算法可供選擇，如K-MEANS[19]、DBSCAN[20]等，但是，面向軌跡的聚類(lèi)算法應(yīng)具備以下特點(diǎn)：(1)挖掘出軌跡長(zhǎng)程運(yùn)動(dòng)模式，(2)發(fā)現(xiàn)任意形狀的簇，(3)對(duì)全局參數(shù)不敏感，(4)不需要先驗(yàn)知識(shí)。為此，我們選擇2014年發(fā)表于《Science》期刊上的密度峰值聚類(lèi)算法[13]。該算法的核心思想十分簡(jiǎn)潔，基于兩個(gè)樸素的假設(shè)來(lái)確定聚類(lèi)中心：(1)聚類(lèi)中心是局部密度的最大對(duì)象；(2)聚類(lèi)中心到其他聚類(lèi)中心的距離相對(duì)較遠(yuǎn)，以不被歸入其他聚類(lèi)中心所屬聚類(lèi)簇內(nèi)。密度峰值聚類(lèi)算法對(duì)于任意一條軌跡Ti，需要計(jì)算局部密度ρi和上向距離δi，即到更大密度聚類(lè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é)果對(duì)于截?cái)嗑嚯xdc有一定的健壯性，而在數(shù)據(jù)規(guī)模較小時(shí)，由于數(shù)據(jù)分布不一定符合真實(shí)分布情況，此時(shí)截?cái)嗑嚯x取值的影響不可忽略。為此，我們引入一種改進(jìn)策略，將K最近鄰思想引入到局部密度計(jì)算中，從而形成基于K最近鄰的密度峰值聚類(lèi)算法[14]，其局部密度ρi的定義被修正為如下所示。其中，KNN(i)為樣本Ti的的K最近鄰軌跡集。

(3)

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

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

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

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

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

為此，我們選用最優(yōu)代表法來(lái)輸出經(jīng)典軌跡，由于不需要形成合成軌跡，其實(shí)現(xiàn)較為簡(jiǎn)單，計(jì)算非常高效。一種直觀(guān)的實(shí)現(xiàn)最優(yōu)代表法的策略是針對(duì)每一個(gè)軌跡簇，將每條軌跡到其他軌跡的相似度距離之和作為該軌跡的分?jǐn)?shù)，從而選擇得分最高的軌跡作為該軌跡蔟的經(jīng)典軌跡。具體到密度峰值聚類(lèi)算法中，聚類(lèi)中心是具有局部密度極大值，且距離更高密度中心較遠(yuǎn)的軌跡，即在一個(gè)軌跡蔟中，聚類(lèi)中心是具有最高密度的軌跡，也就是說(shuō)，其他軌跡到該軌跡的距離之和是最小的，因而可以輸出為該軌跡蔟的代表性軌跡，即經(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展示了該軌跡集的密度峰值聚類(lèi)決策圖，其中，橫坐標(biāo)和縱坐標(biāo)分別表示局部密度和上向距離。

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

圖4 船舶軌跡的密度峰值聚類(lèi)決策圖

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

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

5 結(jié) 語(yǔ)

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

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