基于結(jié)構(gòu)相似度的軌跡聚類算法

袁冠，夏士雄，張磊，周勇

（中國礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116）

1 引言

近幾年，GPS設(shè)備、傳感器網(wǎng)絡(luò)、衛(wèi)星和無線通信等技術(shù)的快速發(fā)展，使得全球范圍內(nèi)的各種移動對象都可以得到有效跟蹤，由此產(chǎn)生了越來越多的移動對象軌跡數(shù)據(jù)。這些數(shù)據(jù)蘊(yùn)含著大量信息，迫切需要研究人員進(jìn)行有效分析。數(shù)據(jù)分析典型的目標(biāo)就是聚集相似的運(yùn)動軌跡，提取移動對象的運(yùn)動特征模式和預(yù)測移動對象運(yùn)動行為。聚類分析是對數(shù)據(jù)對象進(jìn)行分組，使得同一組中對象之間具有較高的相似度，而不同組中的對象具有較低的相似度[1]。軌跡聚類的目標(biāo)是尋找那些具有相同運(yùn)動模式的軌跡，通過對軌跡內(nèi)部運(yùn)動模式和特征信息的分析，確定軌跡間的相似程度，然后將相似程度較高的軌跡歸為一類。近年來，有很多學(xué)者對聚類進(jìn)行了研究，典型的如文獻(xiàn)[1～3, 7～11]，比較有代表性的算法如：K-MEANS、BIRCH，DBSCAN、OPTICS、STING等[2]。這些方法在軌跡聚類中大多對軌跡中的采樣點(diǎn)位置進(jìn)行聚類，無法從全局的角度把握軌跡的特征和運(yùn)動趨勢。在非約束環(huán)境下，軌跡具有局部的相似性和整體的非相似性。事實(shí)上，軌跡中的不同部分在時空數(shù)據(jù)分析中都扮演非常重要的角色，如圖1所示[2]的5條軌跡中，它們在矩形框中的分段是相似的，而矩形框之外的部分則差別較大。

圖1 軌跡間的局部相似性

目前，軌跡聚類研究大多是以整條軌跡作為基本單元參與聚類計(jì)算，而通過對軌跡進(jìn)行分段展開軌跡聚類的研究不多，這樣存在 2個問題：① 忽略軌跡的局部特征；② 無法發(fā)現(xiàn)軌跡中的公共子模式。在典型的軌跡分段分析方法中，為了獲得高質(zhì)量的聚類結(jié)果，最大的挑戰(zhàn)是需要將不同的軌跡段聚集到不同的類簇中[2,4]。傳統(tǒng)聚類算法中對象的不匹配程度（距離）通常由一些相互獨(dú)立屬性之間差值的加權(quán)和來表示，由于軌跡的局部相似性，這種方式不能直接用于軌跡之間的距離測量。KREVELD[4]等首次將軌跡的時間依賴關(guān)系引入到形狀依賴的軌跡分析中，通過軌跡采樣點(diǎn)之間的時延來計(jì)算軌跡的相似度。KNORR[13]等通過用一些獨(dú)立的屬性來表示軌跡的特征，如：起始位置、方向、速度（包括最大、最小、平均速度），然后通過加權(quán)和的距離算法來計(jì)算軌跡間的相似度。這些方法都將軌跡看作一個整體，忽略了軌跡的局部特征，無法匹配路徑較長或較復(fù)雜的軌跡。LEE[2]等為了表示復(fù)雜軌跡的局部特征，采用圖像處理中的線段 Hausdorff距離的思想，將軌跡劃分成若干t-partition。該方法很好地解決了復(fù)雜軌跡之間的比較問題，但是，由于每個t-partition僅僅是軌跡段的2個端點(diǎn)的連線，是軌跡的近似描述，造成了軌跡局部特征的丟失。

從文獻(xiàn)[2～7,14]中可以看出，現(xiàn)有的軌跡分析還僅僅是從軌跡的靜態(tài)數(shù)據(jù)本身出發(fā)，沒有充分考慮到軌跡內(nèi)部所蘊(yùn)含的有價值信息，如：軌跡的產(chǎn)生時間對其形狀、位置、分布、轉(zhuǎn)角等特征的影響以及采樣的誤差對于軌跡計(jì)算的影響等。軌跡數(shù)據(jù)不僅僅是傳統(tǒng)意義上的按照時間排序的靜態(tài)點(diǎn)集合，而是在特定時間與環(huán)境下對象的運(yùn)動路徑，因此，在軌跡數(shù)據(jù)分析過程中，應(yīng)考慮更多的軌跡特征信息，如：發(fā)生的時間、位置、方向、轉(zhuǎn)角、速度等，這些特征屬性體現(xiàn)了軌跡的結(jié)構(gòu)組成。特征之間的敏感度（應(yīng)用領(lǐng)域確定）可以通過特征屬性的權(quán)重進(jìn)行調(diào)整。軌跡的匹配程度可以用基于結(jié)構(gòu)的相似度來衡量，這種方式更能體現(xiàn)軌跡內(nèi)在、外在的異同，增強(qiáng)分析效果。

針對以上問題及軌跡自身的結(jié)構(gòu)特征，本文提出了基于結(jié)構(gòu)相似度的軌跡聚類算法。結(jié)構(gòu)相似度最初用于文獻(xiàn)[12]中的圖像質(zhì)量評價，后來被用于文本結(jié)構(gòu)分析中。本文借鑒圖像質(zhì)量評價中的結(jié)構(gòu)相似度（SSIM, structural similarity）的思想，抽取軌跡的結(jié)構(gòu)性特征信息，并通過計(jì)算軌跡的結(jié)構(gòu)相似度進(jìn)行聚類。為了避免傳統(tǒng)算法對整條軌跡聚類而造成的精確度不高，本文首先計(jì)算軌跡的每個轉(zhuǎn)角，根據(jù)轉(zhuǎn)角閾值將軌跡劃分成若干軌跡段（也稱為基本特征單元，用于描述軌跡的局部特征，轉(zhuǎn)角閾值由應(yīng)用領(lǐng)域確定）。接下來比較所有軌跡段的結(jié)構(gòu)相似度，然后提出基于結(jié)構(gòu)相似度的軌跡聚類算法(TC-SS, trajectory clustering algorithm based on structural similarity)。由于基于結(jié)構(gòu)相似度的軌跡計(jì)算量比較大，為了加速計(jì)算，本文采用類 R-Tree的結(jié)構(gòu)來存儲軌跡段以及其近鄰索引，通過空間代價來換取時間代價，提高檢索速率。最后，本文通過詳細(xì)的實(shí)驗(yàn)分析了各個參數(shù)對算法以及實(shí)驗(yàn)結(jié)果的影響。實(shí)驗(yàn)結(jié)果表明，本文的方法可以對軌跡進(jìn)行有效劃分，同時還保留軌跡的重要特征，計(jì)算出的聚類結(jié)果較其他文獻(xiàn)更具有實(shí)際意義。

2 相關(guān)定義

為了更好地描述本文方法，需要對軌跡及其相關(guān)屬性進(jìn)行形式化描述。文獻(xiàn)[2]對軌跡進(jìn)行了相關(guān)定義，本文同樣適用。TD(trajectory database)表示軌跡集合，TD={TR1,TR2,…,TRn}。軌跡(TR)是由若干個多維度的位置點(diǎn)按照時間順序組成的一個序列：TRi={P1,P2,…,Pm}(1≤i≤n)，其中，Pj(1≤j≤m)表示為＜Locationj,Tj＞，是軌跡中的一個采樣點(diǎn)，表示在Tj時刻運(yùn)動物體位置為Locationj，其中，Locationj是一個多維度的位置點(diǎn)。一條軌跡Pc1,Pc2,…,Pci(1≤c1＜c2＜…≤m)表示TRi的軌跡段或子軌跡，記作：TS(trajectory segment)，TSi={Li1,Li2,…,Linum}。軌跡段表示通過計(jì)算轉(zhuǎn)角后而劃分的軌跡段或子軌跡，包含軌跡的局部特征。

2.1 軌跡段劃分

軌跡段的結(jié)構(gòu)相似度匹配是定義軌跡聚類的關(guān)鍵問題之一，而軌跡段的劃分又決定了軌跡段的結(jié)構(gòu)相似度匹配的準(zhǔn)確程度。軌跡劃分的目標(biāo)在于發(fā)現(xiàn)軌跡行為變化特別快的特征點(diǎn)，通過這些點(diǎn)將軌跡劃分為若干軌跡段。通過這些點(diǎn)對軌跡進(jìn)行劃分，能夠有效地保持軌跡局部特征，同時又不會丟失軌跡的全局特征。本文中軌跡的劃分是通過計(jì)算軌跡轉(zhuǎn)角的大小來決定的。軌跡的轉(zhuǎn)角反映了軌跡方向的變化程度，過大的轉(zhuǎn)角體現(xiàn)了軌跡內(nèi)部的一些突變，這些轉(zhuǎn)角較大的采樣點(diǎn)亦被稱為拐點(diǎn)或突變點(diǎn)。依據(jù)轉(zhuǎn)角來劃分軌跡有利于保存軌跡局部較為平穩(wěn)的結(jié)構(gòu)特征。

文獻(xiàn)[2]采用一種簡單的策略對軌跡進(jìn)行劃分，雖然比較簡單且不需要過多的參數(shù)來干預(yù)，但這不能從根本上解決軌跡細(xì)節(jié)信息丟失的可能性。

定義1 軌跡轉(zhuǎn)角（corner）：相鄰軌跡分段的轉(zhuǎn)向角，反映了軌跡運(yùn)動的趨勢。如圖2所示，連續(xù)軌跡分段在采樣點(diǎn)處的夾角表示為α，軌跡的轉(zhuǎn)角表示為θ1和θ2。為了便于軌跡運(yùn)動趨勢的相似度計(jì)算，指定外向轉(zhuǎn)角θ1為正值，內(nèi)向轉(zhuǎn)角θ2為負(fù)值。

圖2 軌跡轉(zhuǎn)角示意

由圖2可以看出：a，b，c分別為夾角α的鄰邊和對邊，則夾角α的計(jì)算式如(1)所示。

根據(jù)式(1)，轉(zhuǎn)角θ的計(jì)算公式定義如下：

軌跡段的劃分是軌跡分析的第1步，本文借鑒文獻(xiàn)[3]中定義的2階段拐點(diǎn)檢測算法并進(jìn)行改進(jìn)。整個算法由3部分組成：①掃描軌跡中的點(diǎn)序列；②利用式(1)、式(2)計(jì)算軌跡轉(zhuǎn)角；③根據(jù)轉(zhuǎn)角閾值ω對滿足|θ|＞ω的軌跡點(diǎn)進(jìn)行劃分。軌跡劃分算法的時間復(fù)雜度O(n)，其中，n為采樣點(diǎn)的個數(shù)。

2.2 軌跡結(jié)構(gòu)

定義2 軌跡結(jié)構(gòu)（trajectory structure）：是軌跡內(nèi)部特征屬性的集合，這些特征屬性構(gòu)成了軌跡的全部。本文中，軌跡并不單純地由若干個靜態(tài)采樣點(diǎn)按照時間序列組成的線段。軌跡蘊(yùn)含著豐富的信息，如：速度、形狀、位置、轉(zhuǎn)角、加速度等，在軌跡分析時充分考慮這些特征，可以增強(qiáng)準(zhǔn)確度和分析效果。本文定義的軌跡結(jié)構(gòu)包括4個特征，Trajectory Structure ＜Direction, Speed, Angle, Location＞分別為方向、速度、轉(zhuǎn)角、位置等。定義W={WD,WS,WA,WL}為特征權(quán)重向量，分別對應(yīng)軌跡的結(jié)構(gòu)特征向量。各權(quán)重滿足：① 所有權(quán)重取值均大于或等于零；②WD+WS+WA+WL=1。軌跡結(jié)構(gòu)的特征屬性的敏感程度可以通過特征權(quán)重進(jìn)行調(diào)節(jié)，例如：在位置敏感的軌跡分析方法中，通過設(shè)置權(quán)重（WD =WS=WA=0,WL= 1）實(shí)現(xiàn)，這種情況同基于密度的軌跡分析思想是一致的。

2.3 軌跡結(jié)構(gòu)相似度

借鑒 WANG等[12]關(guān)于結(jié)構(gòu)相似度的思想，在進(jìn)行軌跡聚類時，首先根據(jù)轉(zhuǎn)角將軌跡劃分成若干軌跡段，接下來提取軌跡段的結(jié)構(gòu)信息，通過計(jì)算軌跡段的結(jié)構(gòu)相似度來確定 2條軌跡段的相似程度，進(jìn)而完成聚類。基于以上思想，本文提出基于結(jié)構(gòu)相似度的軌跡聚類算法(TC-SS)。

定義3 結(jié)構(gòu)相似度(SSIM)計(jì)算：根據(jù)定義2，軌跡段的結(jié)構(gòu)相似度通過其結(jié)構(gòu)距離(SDIST)來衡量。SDIST計(jì)算包括4個部分的比較：方向的比較DirDist (Li,Lj)；速度的比較SpeedDist (Li,Lj)；轉(zhuǎn)角的比較AngleDist (Li,Lj)以及位置的比較LocDist (Li,Lj)。其中Li，Lj為軌跡段(1≤i≠j≤n)，這 4 部分的比較構(gòu)成了軌跡段結(jié)構(gòu)相似度的計(jì)算，如式(3)，式(4)所示，Normalized(…)為距離的歸一化函數(shù)，由于軌跡結(jié)構(gòu)中每一個特征的值域是不一樣的，因此，結(jié)構(gòu)距離的歸一化實(shí)質(zhì)上是每個特征距離的歸一化。結(jié)構(gòu)相似度表示為1減去歸一化的結(jié)構(gòu)距離。

當(dāng)利用SSIM進(jìn)行軌跡相似度比對時，需要對不在同一軌跡的所有段進(jìn)行結(jié)構(gòu)比較。SSIM 體現(xiàn)了軌跡段在結(jié)構(gòu)上的相似程度，因此SSIM越大（即距離越小）表示軌跡段越相似，反之越不相似。從定義3可以看出，基于結(jié)構(gòu)相似度的計(jì)算方法體現(xiàn)了軌跡段在結(jié)構(gòu)上的差異程度，由此可知，軌跡段結(jié)構(gòu)相似度的距離是對稱的，即SSIM(Li,Lj)= SSIM(Lj,Li)。

2.4 軌跡聚類

軌跡的匹配程度主要通過相似度來確定[1]，通過對比文獻(xiàn)[2,3,15]可以發(fā)現(xiàn)，基于密度的聚類方法可以很好地適應(yīng)軌跡段聚類。由于這些方法可以發(fā)現(xiàn)任意形狀的聚類，更重要的是，可以通過調(diào)整密度相關(guān)的參數(shù)來控制聚類的覆蓋面，因此，本文采用TC-SS來完成軌跡的聚類，下面給出TC-SS的相關(guān)定義：一個聚類主要由結(jié)構(gòu)上相似的軌跡段組成，這些結(jié)構(gòu)相似的軌跡段稱之為軌跡段的近鄰。

定義4 ε-近鄰集(ε-neighbor)：給定近鄰閾值ε，對于軌跡段Li，如果存在軌跡段Lj(i≠j)，滿足SSIM(Li,Lj)≤ε，則Lj屬于Li的ε-近鄰集，記作：

定義4給出了軌跡段的ε-近鄰集，反應(yīng)了軌跡段的相似程度。根據(jù)軌跡段的ε-近鄰集，給出軌跡段聚類的相關(guān)定義。

定義 5 核距離(Cdis, core-distance)：給定軌跡段Li，自然數(shù)σ(σ≤|Nε(Li)|)，設(shè)σ-Dis(Li)表示Li到其第σ個近鄰的距離，則Li的核距離表示如下：

若其 ε-近鄰的個數(shù)|Nε(Li)| ＜σ，則Li的核距離為空(φ)，其中σ為用戶指定參數(shù)。

定義6 可達(dá)距離(Rdis, reachability-distance)：給定軌跡段Li，Lj，自然數(shù)σ(σ≤|Nε(Li)|)，則Li，Lj的可達(dá)距離定義如下：

其中，Cdis(Li)為對應(yīng)的 Cdisε,σ(Li)。與定義 5 類似，若其ε-近鄰的個數(shù)|Nε(Li)| ＜σ，則Li，Lj的可達(dá)距離為空(φ)，即2個軌跡段是不可達(dá)的，反之稱之為距離可達(dá)。

3 基于結(jié)構(gòu)相似度的軌跡聚類算法

現(xiàn)有的軌跡數(shù)據(jù)分析方法過分地追求算法的效率而忽略了軌跡的特征及內(nèi)外在特征信息，同時也沒能有效處理數(shù)據(jù)采集時帶來的異常情況。TC-SS突破了傳統(tǒng)的基于幾何形狀和密度的方法，可以區(qū)分不同的空間區(qū)域中近似物體運(yùn)動。表1給出算法相關(guān)的參數(shù)及其說明。

表1 參數(shù)說明

根據(jù)相關(guān)定義，TC-SS首先根據(jù)轉(zhuǎn)角將軌跡劃分成軌跡段集合。然后將軌跡段與不在同一軌跡上的其他軌跡段進(jìn)行結(jié)構(gòu)相似度比較，并形成軌跡段的ε-近鄰集。最后根據(jù)ε-近鄰集數(shù)目來確定軌跡聚類中心軌跡段，進(jìn)而完成聚類。

3.1 結(jié)構(gòu)相似度計(jì)算

在2.3節(jié)定義的結(jié)構(gòu)相似度計(jì)算中說明了結(jié)構(gòu)相似度所包含的具體比較內(nèi)容：方向信息的比較DirDist (Li,Lj)；速度信息的比較SpeedDist (Li,Lj)；轉(zhuǎn)角信息的比較AngleDist (Li,Lj)；位置信息的比較LocDist (Li,Lj)。其中，1≤i≠j≤n，軌跡段Li由Pi1,Pi2,…,Pin(1≤i1＜i2＜…≤m)組成。

1) 方向信息的比較：DirDist(Li,Lj)表示相對于軌跡段Li，Lj在運(yùn)動趨勢上的偏轉(zhuǎn)程度。如圖3(a)所示，其中，φ是軌跡段的方向夾角。

圖3 軌跡結(jié)構(gòu)信息對比

方向距離的最好情況是2個軌跡段的方向相同且夾角(φ)較小（近似于同向平行），這時DirDist≈0，最差情況是2個軌跡段的方向相反且夾角(φ)較大（近似于反向平行），這時DirDist為較短軌跡段長度。

2) 速度的比較：SpeedDist(Li,Lj)體現(xiàn)了對象移動速度的差異化比較。式(8)給出了速度信息的比較公式。

其中，Smax(Li,Lj)表示|Vmax(Li)?Vmax(Lj)|，體現(xiàn)軌跡段間最大速度的差異絕對值。同理，Savg，Smin分別是平均速度、最小速度的差異程度的絕對值。SpeedDist從最大、最小和平均速度3個方面來表示綜合速度的差異。

3) 轉(zhuǎn)角的比較：AngleDist(Li,Lj) 反應(yīng)了軌跡段內(nèi)部的方向變化特征，反應(yīng)了軌跡內(nèi)部的波動程度。根據(jù)式(2)，內(nèi)向變化的角為正角，外向變化的角為負(fù)角。軌跡的轉(zhuǎn)角是一個累加量，每一個轉(zhuǎn)角的數(shù)值是由軌跡的方向來決定。

轉(zhuǎn)角距離如圖3(b)所示，最好的情況下就是Li和Lj的每一個轉(zhuǎn)角都匹配，AngleDist為0，最差情況就是每個轉(zhuǎn)角互為相反方向，也就是說在軌跡段內(nèi)2條軌跡呈對立鋸齒狀，這時AngleDist為1。通過轉(zhuǎn)角的比較能夠體現(xiàn)軌跡的內(nèi)部變化情況。

4) 位置的對比：LocDist (Li,Lj) 位置計(jì)算方法在基于密度的軌跡相似度研究中均有涉及。為了簡化計(jì)算，本文采用Hausdorff距離[1]公式來衡量軌跡段的位置距離。

3.2 TC-SS描述

根據(jù)上面的分析，TC-SS包括2個階段：① 根據(jù)轉(zhuǎn)角對軌跡進(jìn)行劃分，計(jì)算軌跡段的結(jié)構(gòu)相似度；② 根據(jù)基于密度的聚類算法思想，提出TC-SS，并完成聚類。在第1階段，首先計(jì)算每個軌跡采樣點(diǎn)Pci處的轉(zhuǎn)角θ，然后根據(jù)轉(zhuǎn)角閾值ω劃分軌跡成軌跡段集合TS(第2行)，接下來根據(jù)權(quán)重對軌跡段進(jìn)行相似度計(jì)算，并計(jì)算軌跡段的ε-近鄰集合(第3行～7行)。第2階段是軌跡段聚類(第8行～18行)，首先初始化聚類 ID 和軌跡段聚類標(biāo)志(第 8行～9行)，接下來遍歷軌跡段，尋找核心聚類并設(shè)置聚類ID(第10行～16行)，判斷近鄰中是否滿足距離可達(dá)，若滿足則對近鄰軌跡段進(jìn)行聚類 ID標(biāo)記(第 15行～17行)，同時擴(kuò)展聚類(第19行～27行)直到結(jié)束。

圖4 軌跡聚類算法偽代碼

為了更直觀地分析軌跡聚類效果，本文以 2種方式來表示軌跡聚類：① 以不同顏色來表示軌跡聚類的信息；② 本文參考文獻(xiàn)[2]聚類的特征軌跡表示方法，通過特征軌跡來表示軌跡聚類的信息。

3.3 算法性能分析

TC-SS中的轉(zhuǎn)角閾值ω、ε-近鄰閾值以及近鄰數(shù)量閾值σ是影響算法計(jì)算代價的主要參數(shù)。這些參數(shù)的含義非常直觀，領(lǐng)域?qū)＜液苋菀状_定一個比例合適的閾值。ω的設(shè)定不能太小，太小意味著容易丟失軌跡的重要特征細(xì)節(jié)；同樣不能太大，太大容易將軌跡的突變或由采樣導(dǎo)致的異常包含進(jìn)去，降低聚類分析的效果。由于本文采用類 R-Tree的結(jié)構(gòu)存儲軌跡段并為其近鄰增加空間索引，通過空間效率換取時間效率，TC-SS的時間復(fù)雜度為O(nlgn)，其中，n表示軌跡分段數(shù)目。

4 實(shí)驗(yàn)及分析

為了驗(yàn)證 TC-SS，開發(fā)了軌跡數(shù)據(jù)分析系統(tǒng)TrajMiner。該系統(tǒng)由Borland C++ Builder 6.0開發(fā)，軌跡數(shù)據(jù)存儲在SQLServer 2000中。實(shí)驗(yàn)進(jìn)行的軟硬件環(huán)境包括：Windows XP，Lenovo ThinkCentre(Pentium Duro 2.8G的CPU，1G內(nèi)存)。本文使用以下2個數(shù)據(jù)集。①大西洋颶風(fēng)數(shù)據(jù)(http://weather.unisys.com/hurricane/index.html)，包括颶風(fēng)經(jīng)緯度、持續(xù)最大速率、壓力、采樣時間等信息。本文抽取1950年～2009年的數(shù)據(jù)子集，包括由19 750個采樣點(diǎn)組成的639條軌跡，并選取經(jīng)度緯度、采樣時間等3個屬性參與實(shí)驗(yàn)。②動物運(yùn)動軌跡(http://www.fs.fed.us/pnw/starkey/publications/index.shtml)，包括無線傳感定位數(shù)據(jù)（以及其他信息），本文抽取1995年鹿的運(yùn)動軌跡（簡稱Deer1995）由 20 065個采樣點(diǎn)組成的32條軌跡，并從傳感定位信息中抽取x，y坐標(biāo)、定位時間等信息參與實(shí)驗(yàn)分析。

4.1 參數(shù)選擇與結(jié)果對比

TC-SS的計(jì)算代價主要依賴于轉(zhuǎn)角閾值ω、近鄰閾值ε以及近鄰數(shù)量閾值σ，ω越大軌跡劃分的段越少。由于軌跡結(jié)構(gòu)的特征，計(jì)算過程中造成的軌跡段結(jié)構(gòu)距離的累加，會造成聚類結(jié)構(gòu)松散且持續(xù)過長，這樣容易將噪聲軌跡以及其他不相關(guān)的軌跡聚為一類。而隨著ε的增加，|Nε|就會減少，這樣會造成聚類數(shù)目過多等情況。為了與文獻(xiàn)[2]中的實(shí)驗(yàn)結(jié)果進(jìn)行對比，圖 5以颶風(fēng)數(shù)據(jù)為例，顯示了σ=20、16 (ω=30,ε=39)情況下的聚類效果。采用文獻(xiàn)[2]中的方法對聚類中的特征軌跡進(jìn)行表示。從圖中可以看出圖5(a)的聚類數(shù)目較少，且相對集中，而圖 5(b)的聚類效果相對比較分散且聚類數(shù)目較多，原因在于由于σ較小，距離特征軌跡較遠(yuǎn)但又比較相似的軌跡段被劃分為另外一個聚類。

圖5 颶風(fēng)數(shù)據(jù)在不同σ值的聚類效果

圖5中的聚類結(jié)果表示參考文獻(xiàn)[2]中的特征軌跡表示方法，對聚類中的特征軌跡段進(jìn)行了標(biāo)記。為了驗(yàn)證本文算法的效果，本文采用颶風(fēng)數(shù)據(jù)、Deer1995 2個數(shù)據(jù)集在不同參數(shù)下進(jìn)行計(jì)算驗(yàn)證。

由表2可以看出，由于TC-SS通過犧牲空間來換取時間效率，因此TC-SS消耗的時間僅與軌跡數(shù)量有關(guān)，相關(guān)參數(shù)的設(shè)置對算法的運(yùn)行速度影響不大，但是對聚類結(jié)果影響相對較大。

表2 不同參數(shù)下的軌跡聚類數(shù)目比較與性能分析

本文從軌跡結(jié)構(gòu)出發(fā)，分析軌跡內(nèi)部蘊(yùn)含特征，充分考慮特征屬性：方向、速度、轉(zhuǎn)角、位置等，較文獻(xiàn)[2～8]更為全面，因此本文聚類算法的可靠度與可信度都相對較高。圖6以Deer1995為例展示不同參數(shù)下的聚類效果。從圖6(a)可以看出，由于ε設(shè)置較大，導(dǎo)致|Nε|較小，因此在比較稀疏地區(qū)的軌跡段被認(rèn)為是噪音區(qū)，聚類主要集中在軌跡比較密集區(qū)；而在圖6(b)中，由于ε設(shè)置得當(dāng)，分散區(qū)域的軌跡被聚集起來，原先被孤立的軌跡段也根據(jù)結(jié)構(gòu)相似度被有效劃分到相應(yīng)的聚類中。如圖6(b)中的 2#聚類區(qū)域原本在圖 6(a)中被認(rèn)為是噪音，同時，圖6(b)中的1#聚類區(qū)域也得到了不斷的延伸，覆蓋了圖6(a)中的2#聚類。原本對象活動較為偏遠(yuǎn)的3#區(qū)域，由于具有相對集中的軌跡且對象行為較為相似，因此被聚為一類。

圖6 不同參數(shù)下Deer1995實(shí)驗(yàn)結(jié)果比較

同本文方法最為接近的文獻(xiàn)[2]，由于其對參數(shù)變化非常敏感，參數(shù)的微小調(diào)整都會導(dǎo)致聚類結(jié)果的巨大變化。如果軌跡段沒有被正確地聚類，或者丟失了一些重要的特征，文獻(xiàn)[2]將不能捕捉到復(fù)雜的軌跡運(yùn)動模式。

4.2 同類算法性能對比

本文提出的TC-SS與TRACLUS[2]、DBSCAN、OPTICS等都是密度相關(guān)的聚類算法。為了比較TC-SS與同類算法的優(yōu)劣，本文選取颶風(fēng)數(shù)據(jù)集分別與上面3種算法進(jìn)行比較（參數(shù)選取均為在同環(huán)境下的最優(yōu)參數(shù)），以驗(yàn)證TC-SS的性能。

從表 3中可以看出，相對于其他 3種方法，TC-SS具有較好的運(yùn)行速度，且發(fā)現(xiàn)的聚類數(shù)目要更多，主要有以下原因：① TC-SS采用類 R-Tree的結(jié)構(gòu)存儲軌跡段并為其近鄰增加空間索引，犧牲空間換取時間效率；② TC-SS以軌跡結(jié)構(gòu)特征為依據(jù)，從多角度來計(jì)算軌跡結(jié)構(gòu)相似性，容易發(fā)現(xiàn)比較隱蔽的離群軌跡群；③ 在參數(shù)設(shè)置時，TC-SS的部分參數(shù)直接參與軌跡聚類而不需要進(jìn)一步計(jì)算，參數(shù)調(diào)整更為直觀，有利于發(fā)現(xiàn)隱藏的軌跡運(yùn)動模式。

表3 不同算法之間的性能比較

5 結(jié)束語

本文從軌跡數(shù)據(jù)的特性出發(fā)，提出了軌跡結(jié)構(gòu)的概念，充分考慮軌跡內(nèi)外在特征信息。首先根據(jù)轉(zhuǎn)角將軌跡劃分成包含局部特征的軌跡段集合，通過計(jì)算軌跡段的結(jié)構(gòu)相似度確定相似的軌跡段集合，然后提出了TC-SS，并完成聚類。實(shí)驗(yàn)表明本文算法不僅具有很高的效率，且獲得的軌跡聚類更具有實(shí)際意義，是一種高效的軌跡聚類算法。本文的算法在氣候監(jiān)測、動物遷徙等領(lǐng)域具有重要的意義和價值。下一步工作將致力于分析軌跡在時間維度內(nèi)的運(yùn)動模式，探索時間對軌跡產(chǎn)生及運(yùn)動模式的影響。

[1]陳繼東，孟小峰，賴彩鳳.基于道路網(wǎng)絡(luò)的對象聚類[J].軟件學(xué)報，2007, 18(2):332-344.CHEN J D, MENG X F, LAI C F.Clustering objects in a road network[J].Journal of Software, 2007, 18(2):332-344.

[2]LEE J G, HAN J W, WHANG K Y.Trajectory clustering: a partition-and-group framework[A].Proceedings of the 2007 ACM SIG-MOD International Conference on Management of Data[C].Beijing,China, 2007.593-604.

[3]CHANG C, ZHOU B Y.Multi-granularity visualization of trajectory clusters using sub-trajectory clustering[A].Proceedings of the 7th IEEE International Conference on Data Mining Workshops[C].Miami,Florida, USA, 2009.577-582.

[4]KREVELD M V, LUO J.The definition and computation of trajectory and sub-trajectory similarity[A].Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems[C].Seattle, Washington, USA.2007.324-327.

[5]PELEKIS N, KOPANAKIS I, MARKETOS G,et al.Similarity search in trajectory databases[A].Proceedings of the 14th International Symposium on Temporal Representation and Reasoning[C].Washington, DC, USA, 2007.129-140.

[6]MICHAIL V, MARIOS H, DIMITRIOS G.Indexing multidimensional time-series[J].The International Journal on Very Large Data Bases,2006, 15(1):1-20.

[7]GAFFNEY S, SMYTH P.Trajectory clustering with mixtures of regression models[A].Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].San Diego, California, USA, 1999.63-72.

[8]TSUMOTO S, HIRANO S.Behavior grouping based on trajectory mining[A].Social Computing and Behavioral Modeling[C].Springer Press, German, 2009.219-226.

[9]LI X L, HAN J W, LEE J G,et al.Traffic density-based discovery of hot routes in road networks[A].Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases[C].Boston, MA, USA, 2007.441-459.

[10]YUTAKA Y, TETSUJI S.Clustering multidimensional trajectories based on shape and velocity[A].Proceedings of the 22nd International Conference on Data Engineering Workshops[C].Washington, DC,USA, 2006.12-22.

[11]NANNI M, PEDRESCHI D.Time-focused density-based clustering of trajectories of moving objects[J].Journal of Intelligent Information Systems, 2006, 27(3):267-289.

[12]WANG Z, BOVIK A C, SHEIKH H R.Image quality assessment:from error visibility to structural similarity[J].IEEE Transactions on Image Processing, 2004, 13(4):600-612.

[13]KNORR E M, NG R T, TUCAKOV V.Distance-based outliers: algorithms and applications[J].International Journal on Very Large Data Bases, 2000, 8(3/4):237-253.

[14]FRENTZOS E, GRATSIAS K, THEODORIDIS Y.Index-based most similarity trajectory search[A].Proceedings of IEEE 23rd International Conference on Data Engineering[C].Istanbul, Turkey, 2007.816-825.

[15]NANOPOULOS A, THEODORIDIS Y, MANOLOPOULOS Y.C2P:clustering based on closest pairs[A].Proceedings of the 27th International Conference on Very Large Data Bases[C].San Francisco, CA,USA, 2001.331?340.