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

向隆剛,邵曉天

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

?

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

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

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

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

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

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

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

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

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

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

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

1　軌跡及其停留

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

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

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

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

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

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

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

2.1停留指數(shù)

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

(1)

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

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

(2)

2.1.1逗留時間計算

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

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

(3)

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

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

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

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

(4)

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

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

(5)

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

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

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

2.2停留指數(shù)圖

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

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

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

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

圖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) 若存在點pi-1或點pj+1，則SI(Pi-1)<ΔSI,SI(pj+1)<ΔSI。其中，ΔSI是判別潛在停留段的閾值。

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

(6)

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

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

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

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

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

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

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

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

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

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

在第1級合并中，由于S1和S3凸包重疊，使得S1、S2、S3被成功合并，其結(jié)果凸包與S4的凸包重疊，從而觸發(fā)第2級合并，最終使得4個潛在停留段被合并成1個停留段。需要指出的是，在合并停留段時，小停留段之間的軌跡點(即停留指數(shù)值較低的非停留段部分)并不參與大停留段凸包合并，這是因為非停留段部分可能包含噪聲數(shù)據(jù)，若將其加入合并，勢必將導(dǎo)致大停留段的空間范圍的假性擴張，從而有可能觸發(fā)誤合并。

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

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

輸入：traj,τ,MinMov

輸出：停留段集合SC

1.for軌跡中的每一個點

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

3.endfor

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

5.while在SC中存在未被訪問的停留段

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

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

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

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

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

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

12.endif

13.endwhile

14. 輸出停留段集合SC

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

4　軌跡停留提取試驗

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

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

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

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

4.2結(jié)果分析

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

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

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

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

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

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

5　總結(jié)與展望

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

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

[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]向隆剛, 吳濤, 龔健雅. 面向地理空間信息的軌跡模型及時空模式查詢[J]. 測繪學(xué)報, 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]齊凌艷, 陳榮國, 溫馨. 基于語義軌跡停留點的位置服務(wù)匹配與應(yīng)用研究[J]. 地球信息科學(xué)學(xué)報, 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抽象的軌跡時空關(guān)系[J]. 武漢大學(xué)學(xué)報(信息科學(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]禹文豪, 艾廷華. 核密度估計法支持下的網(wǎng)絡(luò)空間POI點可視化與分析[J]. 測繪學(xué)報, 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é)第一定律與時空鄰近度的提出[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].測繪學(xué)報，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

國家自然科學(xué)基金資助項目(41471374;41001296)

2015-07-08

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

E-mail： geoxlg@whu.edu.cn

邵曉天

E-mail： shaoxiaotian@whu.edu.cn

修回日期： 2016-04-05