向隆剛,邵曉天

1. 武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢430079； 2. 地球空間信息技術(shù)協(xié)同創(chuàng)新中心，湖北 武漢 430079

?

載體軌跡停留信息提取的核密度法及其可視化

向隆剛1,2,邵曉天1,2

1. 武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢430079； 2. 地球空間信息技術(shù)協(xié)同創(chuàng)新中心，湖北 武漢 430079

軌跡停留蘊(yùn)含重要語(yǔ)義信息，其有效提取是開(kāi)展軌跡Stop/Move模型分析的前提。本文首先依據(jù)核密度思想，通過(guò)累計(jì)鄰域點(diǎn)時(shí)空貢獻(xiàn)來(lái)定義軌跡點(diǎn)的停留指數(shù)，在此基礎(chǔ)上設(shè)計(jì)了停留指數(shù)圖，以圖形方式直觀表達(dá)軌跡點(diǎn)的時(shí)空聚集程度變化。進(jìn)一步針對(duì)源于停留指數(shù)的潛在停留段，提出了一種基于潛在停留段時(shí)空臨近關(guān)系的逐級(jí)合并算法，以自動(dòng)發(fā)現(xiàn)和提取停留。試驗(yàn)表明，該算法兼顧停留識(shí)別的完整性和準(zhǔn)確性，可以有效識(shí)別復(fù)雜多樣的軌跡停留，即使面對(duì)噪聲嚴(yán)重的軌跡，停留提取的正確率依然較高。

核密度；軌跡；停留指數(shù)；停留；時(shí)空貢獻(xiàn)

隨著GPS、無(wú)線通信和移動(dòng)設(shè)備的結(jié)合與發(fā)展，時(shí)空軌跡數(shù)據(jù)獲取技術(shù)突飛猛進(jìn)，相關(guān)行業(yè)已經(jīng)累積了海量的時(shí)空軌跡數(shù)據(jù)。如何分析挖掘這些時(shí)空軌跡數(shù)據(jù)，從中提取信息與知識(shí)，已逐漸受到國(guó)內(nèi)外學(xué)者的重視，成為空間信息領(lǐng)域的一大研究熱點(diǎn)。軌跡Stop/Move模型是近年來(lái)提出的一種較為新穎的軌跡分析方法[1-2]，該方法首先將軌跡點(diǎn)序列劃分為Stop/Move序列，并賦予相關(guān)語(yǔ)義，在此基礎(chǔ)上可以開(kāi)展語(yǔ)義更為明確的分析挖掘研究[3-4]。Stop，即停留，指在移動(dòng)對(duì)象的軌跡中靜止或在一定范圍內(nèi)緩慢移動(dòng)的部分，是軌跡中具有重要語(yǔ)義特征的點(diǎn)序列。一方面，停留提取是支持面向軌跡數(shù)據(jù)的知識(shí)發(fā)現(xiàn)與行為識(shí)別的重要手段，如從候鳥軌跡中發(fā)現(xiàn)遷徙過(guò)程中的停歇地，從漁船軌跡中分析出海過(guò)程中的捕魚行為；另一方面，從軌跡停留出發(fā)，研究大量軌跡在停留-移動(dòng)序列上的相似性，可以進(jìn)一步發(fā)掘移動(dòng)對(duì)象的時(shí)空移動(dòng)模式[5-6]，從而為城市交通、居民出行提供決策支持。以出租車軌跡數(shù)據(jù)為例，在停留提取的基礎(chǔ)上，分析出租車司機(jī)的午餐行為在空間和時(shí)間上的分布，可以輔助政府設(shè)計(jì)合理的出租車就餐點(diǎn)，從而提高出租車的服務(wù)效率，并方便居民出行；又如微軟的GeoLife項(xiàng)目[7]，通過(guò)收集游客軌跡數(shù)據(jù)，并分析挖掘其中關(guān)于停留-移動(dòng)的頻繁模式，在旅游線路推薦和朋友圈發(fā)現(xiàn)等方面進(jìn)行了一些有益嘗試。為此，國(guó)內(nèi)外學(xué)者提出了多種停留提取方法，大致可以分為集成地理背景信息的方法[8-9]、基于軌跡導(dǎo)出特征的方法[10-11]、密度聚類法[12-14]以及逐級(jí)合并方法[15]。

集成地理背景信息的方法是指在軌跡停留提取過(guò)程中，從地理背景信息出發(fā)，通過(guò)檢測(cè)移動(dòng)對(duì)象相對(duì)于不同地理實(shí)體(POI、ROI)的時(shí)空關(guān)系來(lái)識(shí)別軌跡停留。具體來(lái)說(shuō)，這類方法通過(guò)計(jì)算軌跡在地理實(shí)體內(nèi)部或其鄰域范圍內(nèi)的累積連續(xù)停留時(shí)間，來(lái)判斷軌跡在該處是否存在停留。該類方法適用于在已有地理背景數(shù)據(jù)環(huán)境下查詢或挖掘軌跡與地理實(shí)體間聯(lián)系的應(yīng)用，但無(wú)法從地理背景信息缺失的區(qū)域提取出停留[9]。

基于軌跡導(dǎo)出特征的方法通過(guò)在軌跡中諸如速度、加速度、點(diǎn)密度、轉(zhuǎn)向角、信號(hào)缺失等一個(gè)或多個(gè)特征上設(shè)置規(guī)則，已從軌跡數(shù)據(jù)中提取出停留。如文獻(xiàn)[10]通過(guò)設(shè)置累積轉(zhuǎn)向角閾值來(lái)發(fā)現(xiàn)漁船軌跡中方向頻繁變化的捕魚點(diǎn)；文獻(xiàn)[11]綜合利用信號(hào)在缺失時(shí)間、轉(zhuǎn)向角多上的多個(gè)規(guī)則來(lái)挖掘居民出行中的活動(dòng)地點(diǎn)。由于軌跡停留識(shí)別的最佳特征選取往往取決于特定的數(shù)據(jù)或應(yīng)用，使得該類方法的通用性受到一定程度的制約。

密度聚類法通過(guò)在傳統(tǒng)的空間密度聚類方法中引入時(shí)間維信息，從軌跡中提取時(shí)空兩方面同時(shí)聚集的停留。如基于DBSCAN算法的改進(jìn)算法CB-SMoT[12]、TrajDBSCAN[13]，該類方法針對(duì)軌跡的時(shí)空特征，重新定義了如鄰居、核心點(diǎn)、密度可達(dá)、密度相連等DBSCAN算法中的基本概念；又如文獻(xiàn)[14]對(duì)OPTICS中的可達(dá)距離在軌跡數(shù)據(jù)上進(jìn)行重新定義，設(shè)計(jì)了適用于軌跡的停留提取算法T-OPTICS。該類方法面向軌跡數(shù)據(jù)，對(duì)傳統(tǒng)密度聚類算法進(jìn)行了相應(yīng)擴(kuò)展，但在處理帶長(zhǎng)距離漂移的軌跡數(shù)據(jù)時(shí)，其停留識(shí)別的效果不佳，易將單個(gè)停留誤識(shí)別為多個(gè)停留[14-15]。

為了克服漂移噪聲對(duì)停留識(shí)別的影響，文獻(xiàn)[15]針對(duì)居民出行軌跡提出了逐級(jí)合并的停留識(shí)別方法，該方法首先使用簡(jiǎn)單的速度判別準(zhǔn)則，將軌跡初步分為停留/移動(dòng)類型子軌跡，并根據(jù)有意義的停留與移動(dòng)在持續(xù)時(shí)間、跨越距離上的限制，動(dòng)態(tài)更新子軌跡的停留/移動(dòng)標(biāo)簽，并通過(guò)逐級(jí)合并相同類型相鄰的子軌跡來(lái)優(yōu)化識(shí)別結(jié)果。該方法雖然在一定程度上克服了噪聲對(duì)停留識(shí)別的影響，但是其簡(jiǎn)單合并策略易于導(dǎo)致不同停留的誤合并。

通過(guò)對(duì)現(xiàn)有停留提取研究的總結(jié)，筆者發(fā)現(xiàn)：①現(xiàn)有研究往往側(cè)重于停留的定義或停留識(shí)別準(zhǔn)則的選取，對(duì)表征停留本身的時(shí)空聚集程度及其可視化方法卻較少研究；②現(xiàn)有研究較少考慮含大量漂移噪聲的室內(nèi)停留的優(yōu)化處理問(wèn)題，對(duì)軌跡停留的復(fù)雜多樣性考慮不足。為此，本文基于核密度思想提出停留指數(shù)，并據(jù)此設(shè)計(jì)停留指數(shù)圖，直觀表達(dá)軌跡點(diǎn)的時(shí)空聚集程度變化，在此基礎(chǔ)上，本文開(kāi)發(fā)停留提取算法，并采用自采軌跡和GeoLife軌跡[16]開(kāi)展試驗(yàn)，結(jié)果表明該算法在停留提取方面具有較高的正確率，能夠識(shí)別復(fù)雜多樣的軌跡停留。

1　軌跡及其停留

定義1(軌跡)：traj=(tid,)，其中，pi=(xi,yi,ti),0≤i≤N，且?i

tid是軌跡的唯一標(biāo)識(shí)，pi=(xi,yi,ti)是構(gòu)成軌跡的1個(gè)時(shí)空點(diǎn)，其中：xi和yi是二維歐氏空間中的坐標(biāo)值(通常為經(jīng)緯度)，ti是時(shí)間全序軸上的時(shí)刻值，xi、yi和ti均來(lái)自于實(shí)數(shù)域。p0和pN是兩個(gè)特殊時(shí)空點(diǎn)，即始點(diǎn)和終點(diǎn)。

軌跡在其生命周期內(nèi)并不是一直移動(dòng)，可能出于某一目的在某一地點(diǎn)停留一段時(shí)間(如就餐和加油等)。在該段時(shí)間內(nèi)，軌跡的空間位置保持不變或在較小范圍內(nèi)變化；此后，軌跡繼續(xù)在空間中移動(dòng)，并到達(dá)下一地點(diǎn)停留，或者抵達(dá)終點(diǎn)。停留，即Stop，是軌跡點(diǎn)序列中的一個(gè)連續(xù)子序列：

定義2(停留)：stop=(tid,sid,)，其中，0

由定義2可知，停留不是由絕對(duì)速度定義而來(lái)，而是在時(shí)空兩維中，由空間范圍和時(shí)間長(zhǎng)度兩者共同界定的概念。由于受到多種因素影響，軌跡停留呈現(xiàn)出復(fù)雜多樣的特征：從發(fā)生地點(diǎn)來(lái)看，可以是室內(nèi)，也可以是室外；從外在表現(xiàn)來(lái)看，停留可以是絕對(duì)靜止、小范圍內(nèi)移動(dòng)，或者兩者的結(jié)合；而從數(shù)據(jù)承載上來(lái)看，停留可以是單個(gè)軌跡點(diǎn)，多個(gè)或者大量連續(xù)的軌跡點(diǎn)。

2　停留指數(shù)及其可視化

核密度分析法[18-19]作為一種基于密度的空間點(diǎn)模式分析技術(shù)，是研究空間點(diǎn)聚集性的有效方法。該方法通過(guò)對(duì)核密度的計(jì)算，得到核密度在空間上的分布，并據(jù)此提取具有重要語(yǔ)義的聚集模式，如交通事件、犯罪熱點(diǎn)等[20-21]。通常來(lái)說(shuō)，移動(dòng)對(duì)象接近停留點(diǎn)時(shí)速度逐步降低，停留期間，速度為零或者很低，而離開(kāi)停留點(diǎn)后，速度將逐步提高，因而，從數(shù)據(jù)承載方面來(lái)看，停留表現(xiàn)為大量軌跡點(diǎn)在局部小范圍內(nèi)的聚集，據(jù)此，本文從核密度思想出發(fā)，提出停留指數(shù)，以反映軌跡在其生命周期內(nèi)時(shí)空聚集程度的變化，在此基礎(chǔ)上以可視化方式直觀揭示軌跡的“潛在”停留，并進(jìn)一步發(fā)展出軌跡停留的自動(dòng)提取算法。

2.1停留指數(shù)

核密度法通過(guò)累計(jì)目標(biāo)點(diǎn)鄰域內(nèi)其他點(diǎn)對(duì)中心點(diǎn)的空間權(quán)重，估算目標(biāo)點(diǎn)處的密度，見(jiàn)式(1)

(1)

式中，n是落在目標(biāo)點(diǎn)s距離為h的鄰域內(nèi)的點(diǎn)數(shù)；函數(shù)K是核函數(shù)，其值隨著s與點(diǎn)Ci的距離的增大而遞減。K函數(shù)的性質(zhì)體現(xiàn)了空間影響隨距離衰減的地理學(xué)第一定律[22-23]，是核密度思想的核心。

由于記錄方式或信號(hào)質(zhì)量等原因，軌跡數(shù)據(jù)的采樣頻率并非是恒等不變的。因而，在將核密度法應(yīng)用于軌跡點(diǎn)停留指數(shù)的計(jì)算時(shí)，除了考慮鄰域內(nèi)的點(diǎn)數(shù)和空間距離之外，應(yīng)進(jìn)一步將點(diǎn)在鄰域內(nèi)的逗留時(shí)間納入進(jìn)來(lái)，以反映軌跡在目標(biāo)點(diǎn)領(lǐng)域內(nèi)(即空間維信息)的逗留時(shí)間(即時(shí)間維信息)。據(jù)此，軌跡點(diǎn)的停留指數(shù)定義如下

(2)

2.1.1逗留時(shí)間計(jì)算

一種簡(jiǎn)單直觀的計(jì)算ST(Pj)的方法是取Pj到Pj+1的時(shí)間采樣間隔，即ST(Pj)=interval(Pj,Pj+1)=Pj+1·tj+1-Pj·tj。由于軌跡是現(xiàn)實(shí)世界中對(duì)象的連續(xù)移動(dòng)在計(jì)算機(jī)世界中的離散化表達(dá)，上述方法將人為隔斷跨越鄰域的相鄰軌跡點(diǎn)之間的時(shí)空聯(lián)系，勢(shì)必造成邊緣點(diǎn)時(shí)空貢獻(xiàn)的誤計(jì)算。

設(shè)想圖1(a)所示的情形，pj到pj+1的子軌跡跨越了N(pi,τ)邊界，而在實(shí)際情況中，pj和pj+1可能間隔很久(如經(jīng)過(guò)長(zhǎng)距離隧道所造成的信號(hào)丟失)，故以時(shí)間采樣間隔來(lái)計(jì)算鄰域點(diǎn)的時(shí)空貢獻(xiàn)將導(dǎo)致點(diǎn)pi停留指數(shù)的計(jì)算結(jié)果虛高。考慮到軌跡移動(dòng)的連續(xù)性，在計(jì)算點(diǎn)pj的逗留時(shí)間時(shí)，僅需考慮子軌跡pj→pj+1落在N(pi,τ)內(nèi)的部分(在圖1中由實(shí)線表示)所對(duì)應(yīng)的時(shí)間，故停留時(shí)間的計(jì)算公式如下

(3)

式中，edin為子軌跡pj→pj+1在鄰域內(nèi)的長(zhǎng)度。此處，筆者假設(shè)軌跡對(duì)象在兩個(gè)采樣點(diǎn)之間勻速運(yùn)動(dòng)。

圖1　逗留時(shí)間計(jì)算與空間權(quán)重校正Fig.1　Calculation of stop time (ST) and its spatial weight correction

2.1.2空間權(quán)重校正

在更復(fù)雜的軌跡移動(dòng)中，軌跡可能多次進(jìn)出鄰域，而每次進(jìn)出時(shí)引入的鄰域點(diǎn)對(duì)目標(biāo)點(diǎn)的時(shí)空貢獻(xiàn)顯然是不相同的。圖1(b)示意了一條軌跡連續(xù)兩次進(jìn)出N(pi,τ)的過(guò)程，按照時(shí)間順序是：enter1→leave1→enter2→leave2，形成兩段落在N(pi,τ)內(nèi)的子軌跡，即stay1和stay2。不同于stay1，stay2在鄰域內(nèi)不存在到目標(biāo)點(diǎn)pi的直接通路，故在計(jì)算鄰域點(diǎn)時(shí)空貢獻(xiàn)時(shí)，應(yīng)對(duì)stay1與stay2加以區(qū)分。不難得出，stay2上的鄰域點(diǎn)，設(shè)為pj，對(duì)目標(biāo)點(diǎn)pi的時(shí)空貢獻(xiàn)不僅取決于pj到pi的歐氏距離，還應(yīng)考慮軌跡在pi與pj之間的移動(dòng)距離。據(jù)此，筆者對(duì)鄰域點(diǎn)pj時(shí)空貢獻(xiàn)的空間權(quán)重進(jìn)行校正，引入如下所示的校正因子

(4)

式中，n=min(i,j)；m=max(i,j)；TD(pn,pm)為軌跡從pn到pm的移動(dòng)距離；tdout為其中不在鄰域內(nèi)的長(zhǎng)度，稱作脫離距離。當(dāng)軌跡從pn移動(dòng)到pm時(shí)未曾脫離鄰域，即脫離距離為0，那么SWP(Pj)=1，這意味著無(wú)需對(duì)pj時(shí)空貢獻(xiàn)進(jìn)行校正。

校正因子依據(jù)鄰域點(diǎn)的脫離距離對(duì)其時(shí)空貢獻(xiàn)進(jìn)行矯正：對(duì)于噪聲導(dǎo)致的暫時(shí)脫離鄰域的情形，由于脫離距離較短，其對(duì)時(shí)空貢獻(xiàn)的影響可忽略不計(jì)；而對(duì)于離開(kāi)-返回形成的脫離鄰域的情形，由于脫離距離通常較長(zhǎng)，其時(shí)空貢獻(xiàn)將被調(diào)至較低水平。

(5)

需要說(shuō)明的是，此處去掉常系數(shù)是為了更好地反映時(shí)空貢獻(xiàn)蘊(yùn)含的語(yǔ)義，即保證目標(biāo)點(diǎn)pi本身在對(duì)于pi停留指數(shù)的時(shí)空貢獻(xiàn)中：空間權(quán)重為1，逗留時(shí)間則依賴于點(diǎn)pi+1的空間分布情況，具體由式(3)決定。

由定義(2)可知，停留是移動(dòng)對(duì)象在一定時(shí)長(zhǎng)內(nèi)保持靜止或在小范圍內(nèi)移動(dòng)的狀態(tài)，相應(yīng)于該定義，停留指數(shù)在小范圍內(nèi)(領(lǐng)域半徑)計(jì)算移動(dòng)對(duì)象累積的逗留時(shí)間。式(5)之所以采用高斯函數(shù)，其原因在于為不同鄰域點(diǎn)的逗留時(shí)間賦予不同的空間衰減權(quán)，從而反映出軌跡點(diǎn)的不同時(shí)空聚集程度，即鄰域點(diǎn)的空間分布越集中于目標(biāo)點(diǎn)附近，目標(biāo)點(diǎn)的停留指數(shù)則越高，這也符合人們對(duì)于停留的直觀認(rèn)識(shí)。不同于CB-SMoT等在擴(kuò)展DBSCAN算法時(shí)先空間，后時(shí)間的做法，停留指數(shù)在累積每一個(gè)鄰域點(diǎn)的貢獻(xiàn)時(shí)，同時(shí)考慮其時(shí)空特征(即空間距離和逗留時(shí)間)，不僅可以表征大量軌跡點(diǎn)聚集所形成的停留，而且能夠反映軌跡點(diǎn)較少(甚至僅有一個(gè)軌跡點(diǎn))但持續(xù)時(shí)間較長(zhǎng)的停留。后者一般對(duì)應(yīng)于移動(dòng)對(duì)象在停留期間GPS設(shè)備降低采樣頻率、不采樣、甚至關(guān)機(jī)的情形，而CB-SMoT等方法在處理由此形成的停留時(shí)往往無(wú)能為力。

由式(5)可知，停留指數(shù)僅由移動(dòng)對(duì)象在鄰域內(nèi)的逗留時(shí)間決定，與速度并不發(fā)生直接的關(guān)系。設(shè)想如下情形：飛機(jī)在機(jī)場(chǎng)上空盤旋時(shí)，雖然速度很高，但始終徘徊于機(jī)場(chǎng)附近，故由機(jī)場(chǎng)這一鄰域決定的停留指數(shù)仍然較大。但在一般情況下，停留指數(shù)與速度存在一種間接的反比關(guān)系，比如移動(dòng)對(duì)象通過(guò)鄰域的速度越大，所花費(fèi)的時(shí)間越少，因而其停留指數(shù)越小，反之亦然。

2.2停留指數(shù)圖

以軌跡點(diǎn)為橫軸，停留指數(shù)為縱軸，即可繪出軌跡的停留指數(shù)圖。圖2是一條從常州自駕到溧陽(yáng)的軌跡的停留指數(shù)圖，從上到下分別是τ=50 m和τ=1000 m的停留指數(shù)圖，以及相應(yīng)于τ=1000 m的熱力圖。為了顯示方便，圖2所示的停留指數(shù)圖在縱軸進(jìn)行了最大值截?cái)唷＝柚趫D形化表達(dá)的停留指數(shù)圖，用戶不必解譯晦澀難懂的軌跡數(shù)據(jù)，即可獲知軌跡在其生命周期中的移動(dòng)-停留情況。以圖2為例，不難得出此次自駕之旅有3次明顯的停留行為，且停留③持續(xù)了較長(zhǎng)時(shí)間。此外，同停留①相比，參與停留②的軌跡點(diǎn)雖少，但其停留指數(shù)較高。

需要指出的是，停留是與空間尺度相關(guān)的概念，以長(zhǎng)距離自駕為例，大尺度上可將在城鎮(zhèn)的一次落腳休整看作一個(gè)大停留，而縮放到小尺度之后，則可將這次落腳細(xì)分為多個(gè)小停留，如就餐、購(gòu)物和住店等。不難得出，停留指數(shù)通過(guò)鄰域半徑τ建立起同空間尺度的關(guān)系，因而在不同大小的鄰域半徑下，可以觀察到不同尺度下的停留情況。繼續(xù)以圖2為例，當(dāng)τ增大到1000 m時(shí)，在τ=50 m時(shí)觀察到的前2小個(gè)停留被連接成1個(gè)大停留，即在大尺度下可將在常州市的2次停留看作1個(gè)停留。

3　基于停留指數(shù)的停留提取

從軌跡停留指數(shù)的可視化結(jié)果不難看出，實(shí)際停留對(duì)應(yīng)的子軌跡具有較高的停留指數(shù)值，這啟發(fā)筆者試著從停留指數(shù)發(fā)現(xiàn)并提取停留，為此，擬從軌跡中搜索高停留指數(shù)的軌跡點(diǎn)序列形成的子軌跡，即潛在停留段。

圖2　軌跡停留指數(shù)圖樣例Fig.2　Example of a trajectory and its stop index plot

定義3(潛在停留段)：給定軌跡Traj和鄰域半徑τ，潛在停留段S=pi→pi+1→…pj是traj中的子軌跡，j≥i，且滿足：

(1) ?k,i≥k≥j，SI(pk)≥ΔSI。

(2) 若存在點(diǎn)pi-1或點(diǎn)pj+1，則SI(Pi-1)<ΔSI,SI(pj+1)<ΔSI。其中，ΔSI是判別潛在停留段的閾值。

潛在停留段可以由大量高停留指數(shù)的軌跡點(diǎn)組成，如圖2中的③，也可以由幾個(gè)、甚至一個(gè)高停留指數(shù)的軌跡點(diǎn)組成，如圖2中的②。潛在停留段判別閾值ΔSI是提取潛在停留段的關(guān)鍵，若設(shè)置得太小，則會(huì)提取出較多的偽停留，而若設(shè)置得太大，則會(huì)忽略掉一些較短的停留。為此，本文給出在鄰域半徑τ下，潛在停留段判別閾值的推薦值的計(jì)算公式

(6)

式中，v是靜止判別閾值，為軌跡對(duì)象以速度v作勻速直線運(yùn)動(dòng)通過(guò)鄰域所需的最長(zhǎng)時(shí)間。在式(6)中，靜止判別閾值v的選取需要考慮移動(dòng)對(duì)象的速度，一般來(lái)說(shuō)，移動(dòng)對(duì)象的速度越快，v應(yīng)設(shè)置得越大，但與此同時(shí)，τ也應(yīng)相應(yīng)增大，以匹配移動(dòng)對(duì)象的速度能力?？紤]到人的正常步行速度在5 km/h左右[24]，本文將靜止判別閾值設(shè)定為v=0.6 m/s，實(shí)際上，這也是大部分相關(guān)研究所使用的靜止判別標(biāo)準(zhǔn)[15]。

在GPS信號(hào)良好時(shí)，一個(gè)潛在停留段即對(duì)應(yīng)一個(gè)實(shí)際停留。但是，由于室內(nèi)遮擋或高樓反射等原因，GPS的定位精度變差，產(chǎn)生漂移噪聲，一個(gè)完整的停留將對(duì)應(yīng)多個(gè)潛在停留段。如果處理不當(dāng)，很可能將該完整停留誤識(shí)別成多個(gè)停留，這也是現(xiàn)有停留識(shí)別方法都難以有效解決的問(wèn)題[12-14]。文獻(xiàn)[14]提出的逐級(jí)合并停留識(shí)別方法雖然在克服噪聲方面效果較好，但簡(jiǎn)單的合并規(guī)則也導(dǎo)致了誤合并的發(fā)生[15]。圖3展示了一條有2次實(shí)際停留行為的軌跡，以及TrajDBSCAN算法和文獻(xiàn)[14]算法在各自文章的推薦參數(shù)下對(duì)停留的識(shí)別結(jié)果，其中，TrajDBSCAN法將B處的停留識(shí)別成了5個(gè)停留，而逐級(jí)合并算法則將2個(gè)停留合并成1個(gè)停留。

圖3　不同算法的停留識(shí)別結(jié)果對(duì)比Fig.3　Comparison of stop results extracted by different algorithms

在研究和總結(jié)現(xiàn)有方法對(duì)于停留識(shí)別的基礎(chǔ)上，本文針對(duì)源于停留指數(shù)的潛在停留段，提出了一種基于時(shí)空鄰近關(guān)系的逐級(jí)合并方法，據(jù)此發(fā)展出基于停留指數(shù)的停留識(shí)別算法。首先給出停留段概念，它或者對(duì)應(yīng)潛在停留段，或者由潛在停留段合并而來(lái)，然后定義停留段的時(shí)空相鄰關(guān)系，如下：

定義4(時(shí)空相鄰?fù)Ａ舳?：對(duì)于軌跡traj的兩個(gè)停留段Sa與Sb，設(shè)Sa發(fā)生在Sb之前，若Sa與Sb滿足下面兩個(gè)條件之一，那么Sa與Sb時(shí)空相鄰。

(1) 若Sa與Sb是兩個(gè)連續(xù)的停留段，即中間不存在其他停留段，且Itv(Sa,Sb)≤MinMov。

(2) 若Sa與Sb的凸包重疊，且Itv(Sa,Sb)≤ω·MinMov，ω>1。

其中，Itv(Sa,Sb)表示停留段Sa與Sb之間的時(shí)間間隔；MinMov表示一個(gè)有意義的移動(dòng)應(yīng)持續(xù)的最短時(shí)間。

當(dāng)Sa與Sb時(shí)空相鄰時(shí)，可以將Sa與Sb，以及Sa與Sb之間的軌跡點(diǎn)，合并成一個(gè)新停留段。在定義4的2個(gè)條件中：條件1用于合并因短時(shí)脫離形成的兩個(gè)連續(xù)停留段，而條件2用于合并被噪聲數(shù)據(jù)隔開(kāi)的停留段。此外，條件2的兩個(gè)輸入停留段并不要求是連續(xù)的，從而放寬了時(shí)間間隔方面的要求，本文統(tǒng)一取ω=2。

停留的提取可以從定位潛在停留段開(kāi)始，通過(guò)逐級(jí)合并時(shí)空相鄰的停留段，最終得到完整的停留。在逐級(jí)合并中，時(shí)空相鄰小停留段被合并成大停留段，大停留段則繼承小停留段的時(shí)間范圍，并將小停留段共同的凸包作為自身的凸包，以參與下一級(jí)合并。因此，停留段的逐級(jí)合并，實(shí)質(zhì)上是停留段時(shí)空范圍的擴(kuò)張過(guò)程。圖4示意了4個(gè)潛在停留段的合并過(guò)程，按照時(shí)間順序分別為：S1→S2→S3→S4。

在第1級(jí)合并中，由于S1和S3凸包重疊，使得S1、S2、S3被成功合并，其結(jié)果凸包與S4的凸包重疊，從而觸發(fā)第2級(jí)合并，最終使得4個(gè)潛在停留段被合并成1個(gè)停留段。需要指出的是，在合并停留段時(shí)，小停留段之間的軌跡點(diǎn)(即停留指數(shù)值較低的非停留段部分)并不參與大停留段凸包合并，這是因?yàn)榉峭Ａ舳尾糠挚赡馨肼晹?shù)據(jù)，若將其加入合并，勢(shì)必將導(dǎo)致大停留段的空間范圍的假性擴(kuò)張，從而有可能觸發(fā)誤合并。

綜上所述，不難得出基于停留指數(shù)的軌跡停留提取算法，其偽代碼如下：

算法：基于停留指數(shù)的軌跡停留提取算法

輸入：traj,τ,MinMov

輸出：停留段集合SC

1.for軌跡中的每一個(gè)點(diǎn)

2. 根據(jù)τ計(jì)算Traj中軌跡點(diǎn)的停留指數(shù)

3.endfor

4. 據(jù)定義(3)提取所有潛在停留段，標(biāo)記為未訪問(wèn)，并加入到SC

5.while在SC中存在未被訪問(wèn)的停留段

6. 從SC中取出一個(gè)尚未被訪問(wèn)的停留段S，并標(biāo)記為已訪問(wèn)

7.if在SC中存在與S時(shí)空相鄰的停留段 ∥據(jù)定義(4)

8. 將S與其時(shí)空相鄰的所有停留段合并成大停留段S‘

9. 將S與其時(shí)空相鄰的所有停留段的共同凸包設(shè)為S‘的凸包

10. 將與S時(shí)空相鄰的所有停留段標(biāo)記為已訪問(wèn)

11. 將S‘加入到SC，并標(biāo)記為未訪問(wèn)

12.endif

13.endwhile

14. 輸出停留段集合SC

圖4　潛在停留段合并Fig.4　Merge of potential stops

4　軌跡停留提取試驗(yàn)

為了驗(yàn)證基于停留指數(shù)的軌跡停留提取方法的有效性，本節(jié)分別選用自采和GeoLife兩組居民出行的軌跡，對(duì)日常出行中感興趣的停留開(kāi)展提取試驗(yàn)。試驗(yàn)軌跡涵蓋了步行、公共交通、駕車等多種出行方式，其中自采軌跡為由GarmineTrex20設(shè)備采集的8條軌跡數(shù)據(jù)，該設(shè)備內(nèi)置GLONASS和GPS雙星系統(tǒng)，室外定位精度約為15m，軌跡點(diǎn)采樣間隔被固定為3s；GeoLife軌跡是微軟亞洲研究院發(fā)布的免費(fèi)軌跡數(shù)據(jù)源，由于其數(shù)據(jù)采集設(shè)備規(guī)格參差不齊，筆者從中選取了15條出行信息豐富，停留數(shù)量較多、且?guī)в性肼暤能壽E，其采樣間隔為5s。

4.1參數(shù)設(shè)置

停留提取算法的運(yùn)行共依賴于2個(gè)參數(shù)，即鄰域半徑τ和移動(dòng)最短持續(xù)時(shí)間MinMov，需要指出的是，停留是一個(gè)與空間尺度相關(guān)的概念(見(jiàn)2.2節(jié))，因而，提取算法的參數(shù)也應(yīng)與用戶所關(guān)注的空間尺度相適應(yīng)?？紤]到GPS設(shè)備的定位誤差一般在15m左右，在城市范圍內(nèi)研究停留提取問(wèn)題時(shí)，可依據(jù)軌跡數(shù)據(jù)的噪聲情況，將參數(shù)τ設(shè)置為30～90m之間的值，不宜過(guò)大，也不宜過(guò)小。過(guò)大時(shí)，潛在停留段的邊界將會(huì)向兩端膨脹，從而可能引發(fā)相鄰?fù)Ａ舻腻e(cuò)誤合并；過(guò)小時(shí)，潛在停留段的邊界會(huì)收縮，甚至消失，從而可能導(dǎo)致停留未被提取。參數(shù)MinMov的設(shè)置同樣與軌跡數(shù)據(jù)的噪聲情況有關(guān)：當(dāng)GPS信號(hào)質(zhì)量較差時(shí)，單個(gè)停留易被分割成多潛在停留段，應(yīng)適當(dāng)增大MinMov值，以增強(qiáng)潛在停留段的合并能力，反之則需減小MinMov值。

考慮到試驗(yàn)數(shù)據(jù)均為居民在城市范圍內(nèi)的出行數(shù)據(jù)，本文選擇τ=50m，作為停留提取的尺度參數(shù)，以保證識(shí)別結(jié)果在邊界范圍上的合理性。同時(shí)，試驗(yàn)數(shù)據(jù)存在較多室內(nèi)停留，致使GPS信號(hào)質(zhì)量較差，數(shù)據(jù)噪聲較大，本文采用MinMov=300s作為停留合并的閾值，以確保停留識(shí)別的完整性。此外，根據(jù)定義(2)，停留應(yīng)持續(xù)一定的時(shí)間，其值設(shè)置實(shí)際上是一個(gè)應(yīng)用相關(guān)的問(wèn)題。本文將其設(shè)置為180s，即表示僅對(duì)持續(xù)時(shí)間超過(guò)此值的停留感興趣，意在剔除那些因?yàn)槎虝r(shí)減速慢行形成的，但語(yǔ)義蘊(yùn)含較弱的停留。

4.2結(jié)果分析

針對(duì)自采軌跡和GeoLife軌跡的試驗(yàn)結(jié)果分別見(jiàn)表1和表2所示，其中，真實(shí)停留數(shù)是通過(guò)人工檢驗(yàn)得到的實(shí)際停留的數(shù)目，發(fā)現(xiàn)停留數(shù)是通過(guò)算法輸出的停留數(shù)，正確識(shí)別停留數(shù)為輸出的停留中真實(shí)停留的數(shù)目，合并停留數(shù)為通過(guò)合并手段得到的停留數(shù)，未識(shí)別停留數(shù)為真實(shí)停留中未被識(shí)別的停留數(shù)。以第13條GeoLife軌跡為例，其停留指數(shù)圖見(jiàn)圖5所示，相應(yīng)的停留提取結(jié)果表2第14行：人工檢出6個(gè)停留，算法輸出6個(gè)停留，其中有3個(gè)為合并而來(lái)，而在這6個(gè)輸出停留中，5個(gè)是真實(shí)停留，意味著有1個(gè)真實(shí)停留未被檢出，且多檢出1個(gè)偽停留。

表1　自采軌跡的停留識(shí)別結(jié)果

表2　GeoLife軌跡的停留識(shí)別結(jié)果

圖5　GeoLife樣例軌跡的停留指數(shù)圖Fig.5　Example of GeoLife trajectory and its stop index plot

從表1和表2可以得出，盡管試驗(yàn)軌跡帶有不少含漂移噪聲的室內(nèi)停留，本文方法對(duì)于真實(shí)停留的正確檢測(cè)率仍然超過(guò)了90%。以圖5所示的第13條GeoLife軌跡為例，⑤為帶漂移噪聲的長(zhǎng)時(shí)室內(nèi)停留，借助于時(shí)空相鄰?fù)Ａ舳蔚闹鸺?jí)合并，算法成功提取出該停留，且其完整性與實(shí)際基本相符。自采數(shù)據(jù)總共僅有6處輸出停留是通過(guò)合并得到的，原因在于自采數(shù)據(jù)的定位精度和采樣頻率較高，一些室內(nèi)停留甚至無(wú)需通過(guò)合并即可被完整的提取出來(lái)；而對(duì)于GeoLife數(shù)據(jù)來(lái)說(shuō)，大量的漂移噪聲將實(shí)際停留分割成多個(gè)高停留指數(shù)的潛在停留段，有將近4成的輸出停留是通過(guò)合并得來(lái)的。

從表1和表2也可以看出，本文方法主要存在兩方面的問(wèn)題：一是誤識(shí)別，即輸出偽停留；二是未識(shí)別，即有真實(shí)停留未被檢出。從本質(zhì)上來(lái)看，這兩個(gè)問(wèn)題的原因是相同的，即由于飄移噪聲的影響，屬于一個(gè)實(shí)際停留的多個(gè)停留段的時(shí)間間隔過(guò)大或者凸包不重疊，導(dǎo)致實(shí)際停留未能被正確合并出來(lái)，使得這些停留段或者被誤識(shí)別為多個(gè)小停留(即發(fā)生誤識(shí)別，如圖5中位于I區(qū)的⑥，經(jīng)過(guò)合并后仍然被分割成兩個(gè)凸包不重疊的子停留)，或者因短于180 s而被去除(即導(dǎo)致未識(shí)別，如圖5中位于II區(qū)的①)。

5　總結(jié)與展望

本文在分析與總結(jié)現(xiàn)有的軌跡停留識(shí)別方法的基礎(chǔ)之上，提出了基于核密度思想、顧及時(shí)空鄰近性，表征軌跡點(diǎn)時(shí)空聚集程度的數(shù)值指標(biāo)：停留指數(shù)，并進(jìn)一步發(fā)展出停留指數(shù)圖。停留指數(shù)取決于軌跡在鄰域內(nèi)的逗留時(shí)間，符合人們對(duì)于停留的直觀認(rèn)識(shí)；停留指數(shù)圖通過(guò)鄰域半徑建立起同空間尺度的關(guān)系，以可視化的方式表達(dá)不同尺度下的軌跡停留情況。源于停留指數(shù)，本文首先定義潛在停留段，提出了逐級(jí)合并的軌跡停留識(shí)別算法。該算法充分分析了潛在停留段之間的時(shí)空鄰近關(guān)系，能夠識(shí)別復(fù)雜多樣的軌跡停留:GPS信號(hào)良好的停留可直接由潛在停留段得來(lái)，而GPS信號(hào)微弱的停留則可通過(guò)合并多個(gè)潛在停留段而來(lái)?；谧圆绍壽E和GeoLife軌跡的試驗(yàn)表明，本文方法可以直觀展示軌跡在其生命周期內(nèi)時(shí)空聚集程度的變化，且能更進(jìn)一步、有效提取包括單點(diǎn)/多點(diǎn)和室內(nèi)/室外在內(nèi)的多類型、含噪聲的軌跡停留。

本文算法的不足是在處理帶有嚴(yán)重漂移噪聲的長(zhǎng)時(shí)室內(nèi)停留時(shí)，仍有可能發(fā)生誤識(shí)別和未識(shí)別的情形，后續(xù)研究將結(jié)合地理空間上下文信息，包括路網(wǎng)匹配信息和地理逆編碼信息，以進(jìn)一步合并由噪聲隔開(kāi)的停留段。

[1]SPACCAPIETRA S, PARENT C, DAMIANI M L, et al. A Conceptual View on Trajectories[J]. Data and Knowledge Engineering, 2008, 65(1): 126-146.

[2]YAN Zhixian, CHAKRABORTY D, PARENT C, et al. Semantic Trajectories: Mobility Data Computation and Annotation[J]. ACM Transactions on Intelligent Systems and Technology, 2013, 4(3): 49.

[3]PARENT C, SPACCAPIETRA S, RENSO C, et al. Semantic Trajectories Modeling and Analysis[J]. ACM Computing Surveys, 2013, 45(4): 42.

[4]向隆剛, 吳濤, 龔健雅. 面向地理空間信息的軌跡模型及時(shí)空模式查詢[J]. 測(cè)繪學(xué)報(bào), 2014, 43(9): 982-988. DOI: 10.13485/j.cnki.11-2089.2014.0121.

XIANG Longgang, WU Tao, GONG Jianya. A Geo-spatial Information Oriented Trajectory Model and Spatio-temporal Pattern Querying[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(9): 982-988. DOI: 10.13485/j.cnki.11-2089.2014.0121.

[5]齊凌艷, 陳榮國(guó), 溫馨. 基于語(yǔ)義軌跡停留點(diǎn)的位置服務(wù)匹配與應(yīng)用研究[J]. 地球信息科學(xué)學(xué)報(bào), 2014, 16(5): 720-726.

QI Lingyan, CHEN Rongguo, WEN Xin. Research on the LBS Matching Based on Stay Point of the Semantic Trajectory[J]. Journal of Geo-Information Science, 2014, 16(5): 720-726.

[6]VIEIRA M, BAKALOV P, TSOTRAS V J. Querying Trajectories Using Flexible Patterns[C]∥Proceedings of the 13th International Conference on Extending Database Technology. New York: ACM, 2010: 406-417.

[7]GIANNOTTI F, NANNI M, PEDRESCHI D, et al. Trajectory Pattern Mining[C]∥Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007: 330-339.

[8]ZHENG Yu, ZHANG Lizhu, XIE Xing, et al. Mining Interesting Locations and Travel Sequences from GPS Trajectories[C]∥Proceedings of the 18th International Conference on World Wide Web. New York: ACM, 2009: 791-800.

[9]ALVARES L, BOGORNY V, KUIJPERS B, et al. A Model for Enriching Trajectories with Semantic Geographical Information[C]∥Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems. New York: ACM, 2007.

[10]ROCHA J M R, TIMES V C, OLIVEIRA G, et al. DB-SMoT: A Direction-based Spatio-temporal Clustering Method[C]∥Proceedings of the 5th IEEE International Conference Intelligent Systems. London: IEEE, 2010: 114-119.

[11]STOPHER P, JIANG Q, FITZGERALD C. Processing GPS Data from Travel Surveys[C]∥Proceedings of the 2nd International Colloquium on the Behavioral Foundations of Integrated Land-use and Transportation Models: Frameworks, Models and Applications. Toronto: [s.n.], 2005.

[12]TIETBOHL A, BOGORNY V, KUIJPERS B, et al. A Clustering-based Approach for Discovering Interesting Places in Trajectories[C]∥Proceedings of the 2008 ACM Symposium on Applied Computing. New York: ACM, 2008: 863-868.

[13]TRAN L H, NGUYEN Q V H, NGOC H, et al. Robust and Hierarchical Stop Discovery in Sparse and Diverse Trajectories[EB/OL]. (2012-06-15)[2015-09-24]. http:∥cn.bing.com/academic/profile?id=1894965895&v=paper_preview&mkt=zh-cn

[14]ZIMMERMANN M, KIRSTE T, SPILIOPOULOU M. Finding Stops in Error-Prone Trajectories of Moving Objects with Time-based Clustering[M]∥TAVANGARIAN D, KIRSTE T, TIMMERMANN D, et al. Intelligent Interactive Assistance and Mobile Multimedia Computing. Berlin: Springer, 2009, 53: 275-286.

[15]張治華. 基于GPS軌跡的出行信息提取研究[D]. 上海: 華東師范大學(xué), 2010.

ZHANG Zhihua. Deriving Trip Information from GPS Trajectories[D]. Shanghai: East China Normal University, 2010.

[16]Microsoft Research. GeoLife GPS Trajectories[EB/OL]. [2015-06-10]. http:∥research.microsoft.com/en-us/downloads/b16d359d-d164-469e-9fd4-daa38f2b2e13.

[17]向隆剛, 龔健雅, 吳濤, 等. 一種面向Stop/Move抽象的軌跡時(shí)空關(guān)系[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2014, 39(8): 956-962.

XIANG Longgang, GONG Jianya, WU Tao, et al. Spatio-temporal Trajectory Relationships Based on Stop/Move Abstraction[J]. Geomatics and Information Science of Wuhan University, 2014, 39(8): 956-962.

[18]PARZEN E. On Estimation of a Probability Density Function and Mode[J]. The Annals of Mathematical Statistics, 1962, 33(8): 1065-1076.

[19]王遠(yuǎn)飛, 何洪林. 空間數(shù)據(jù)分析方法[M]. 北京: 科學(xué)出版社, 2007: 57-93.

WANG Yuanfei, HE Honglin. Spatial Data Analysis Methods[M]. Beijing: Science Press, 2007: 57-93.

[20]禹文豪, 艾廷華. 核密度估計(jì)法支持下的網(wǎng)絡(luò)空間POI點(diǎn)可視化與分析[J]. 測(cè)繪學(xué)報(bào), 2015, 44(1): 82-90. DOI: 10.11947/j.AGCS.2015.20130538.

YU Wenhao, AI Tinghua. The Visualization and Analysis of POI Features under Network Space Supported by Kernel Density Estimation[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(1): 82-90. DOI: 10.11947/j.AGCS.2015.20130538.

[21]SCHABENBERGER O, GOTWAY C A. Statistical Methods for Spatial Data Analysis[M]. Boca Raton: Chapman & Hall /CRC, 2005.

[22]MILLER H J. Tobler’s First Law and Spatial Analysis[J]. Annals of the Association of American Geographers, 2004, 94(2): 284-289.

[23]李小文, 曹春香, 常超一. 地理學(xué)第一定律與時(shí)空鄰近度的提出[J]. 自然雜志, 2007, 29(2): 69-71.

LI Xiaowen, CAO Chunxiang, CHANG Chaoyi. The First Law of Geography and Spatial-temporal Proximity[J]. Chinese Journal of Nature, 2007, 29(2): 69-71.

[24]CHANDRA S, BHARTI A K. Speed Distribution Curves for Pedestrians during Walking and Crossing[J]. Procedia-social and Behavioral Sciences, 2013(104): 660-667.

(責(zé)任編輯：張艷玲)

Visualization and Extraction of Trajectory Stops Based on Kernel-density

XIANG Longgang1,2,SHAO Xiaotian1,2

1. State Key Laboratory of Information Engineering in Surveying，Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China; 2. Collaborative Innovation Center of Geospatial Technology, Wuhan 430079, China

Trajectory stops imply important semantic information, and the extraction of trajectory stops is the premise to carry out advanced Stop/Move analysis. This paper, based on the idea of kernel density, firstly introduces the concept of stop index, which is derived by cumulating spatio-temporal contribution of neighboring points, and further designs stop index graph to intuitively visualize the evolution of spatio-clustering degree during a trajectory. Importantly, stops index and its graph are related to spatial scale through neighboring radius, which then can be exploited to analyze trajectory stops under multiple scales. In addition, this paper introduces stop sequence rooted from stop index, and proposes an algorithm for the automatic extraction of trajectory stops by progressively merging stop sequences. According to the algorithm, a stop under strong GPS signal exactly corresponds to a stop sequence, while a stop under weak GPS signal could be derived by merging multiple stop sequences. Experiments based on own-acquired and GeoLife trajectories show that the algorithm has achieves the balance between the completeness and accuracy of stop extraction, and could effectively discover and extract complex and diverse trajectory stops. Even facing trajectories with serious drift noises, the algorithm still achieves a high rate of accuracy on stop extraction.

kernel density; trajectory; stop index; stop; spatio-temporal contribution

The National Natural Science Foundation of China (Nos.41471374;41001296)

XIANG Longgang(1976—)，male, PhD, associate professor, majors in the fields of spatial database, trajectory data analysis and virtual globe technologies.

SHAO Xiaotian

向隆剛，邵曉天.載體軌跡停留信息提取的核密度法及其可視化[J].測(cè)繪學(xué)報(bào)，2016,45(9)：1122-1131.

10.11947/j.AGCS.2016.20150347.

XIANG Longgang,SHAO Xiaotian.Visualization and Extraction of Trajectory Stops Based on Kernel-density[J]. Acta Geodaetica et Cartographica Sinica,2016,45(9):1122-1131. DOI:10.11947/j.AGCS.2016.20150347.

P208

A

1001-1595(2016)09-1122-10

國(guó)家自然科學(xué)基金資助項(xiàng)目(41471374;41001296)

2015-07-08

向隆剛(1976—)，男，博士，副教授，主要從事空間數(shù)據(jù)庫(kù)、軌跡數(shù)據(jù)處理分析與虛擬地球技術(shù)研究。

E-mail： geoxlg@whu.edu.cn

邵曉天

E-mail： shaoxiaotian@whu.edu.cn

修回日期： 2016-04-05