侯 穎 超,王 盼 成,劉 興 權(quán),滕 潔

(中南大學(xué)地球科學(xué)與信息物理學(xué)院地理信息系，湖南，長沙 410083)

基于速度的空間軌跡停留點(diǎn)提取算法

侯 穎 超,王 盼 成*,劉 興 權(quán),滕 潔

(中南大學(xué)地球科學(xué)與信息物理學(xué)院地理信息系，湖南，長沙 410083)

空間軌跡中的停留點(diǎn)提取是將空間軌跡轉(zhuǎn)換到語義軌跡的關(guān)鍵步驟。該文將速度變量引入停留點(diǎn)的提取，提出基于速度的時(shí)間聚類算法和速度聚類算法解決現(xiàn)有方法中的“偽停留點(diǎn)”和停留點(diǎn)丟失的問題?；谒俣鹊臅r(shí)間聚類算法首先沿時(shí)間軸將軌跡點(diǎn)進(jìn)行聚類得到候選停留點(diǎn)，然后利用速度閾值過濾候選停留點(diǎn)，得出實(shí)際停留點(diǎn)。速度聚類算法首先通過對(duì)速度的判斷選取候選停留點(diǎn)，然后根據(jù)空間距離閾值對(duì)候選停留點(diǎn)的空間距離進(jìn)行過濾，得出實(shí)際停留點(diǎn)，解決了停留點(diǎn)判斷中的漏判問題。實(shí)驗(yàn)表明，基于速度的時(shí)間聚類算法對(duì)出租車軌跡數(shù)據(jù)(穩(wěn)定時(shí)間間隔、不存在長時(shí)間軌跡點(diǎn)缺失)的空間軌跡停留點(diǎn)識(shí)別效果較好，而速度聚類算法更適用于步行軌跡(可能存在長時(shí)間軌跡點(diǎn)缺失)的分析。

停留點(diǎn);空間軌跡;速度聚類;時(shí)間聚類

0 引言

隨著全球衛(wèi)星定位系統(tǒng)和基于無線蜂窩網(wǎng)的手機(jī)定位技術(shù)的發(fā)展，人們對(duì)于自身位置信息的獲取越來越容易[1,2]。具有GPS定位功能的智能手機(jī)的普及和車載GPS的廣泛使用，有助于獲得大量高精度人類出行軌跡數(shù)據(jù)[3,4]。如何有效地分析利用這些數(shù)據(jù)，已成為當(dāng)前學(xué)術(shù)界研究的熱點(diǎn)問題。使用(longitude,latitude,time)記錄的原始空間軌跡數(shù)據(jù)并不具備語義信息，不方便理解和使用。Alvares等提供了一個(gè)將坐標(biāo)軌跡轉(zhuǎn)換成語義軌跡的框架,并在實(shí)際工作中得到廣泛使用[5,6]。該框架首先從連續(xù)記錄的軌跡點(diǎn)中找出停留點(diǎn)，再將停留點(diǎn)和地名地址庫相匹配(逆地理編碼)得到停留的地名地址。這些按時(shí)間先后排列的地名地址點(diǎn)序列就是語義軌跡。因此，如何有效地找出軌跡中的停留點(diǎn)或停留區(qū)域，是從空間軌跡向語義軌跡轉(zhuǎn)換過程中不可繞開的環(huán)節(jié)。

當(dāng)前已有很多關(guān)于軌跡停留點(diǎn)的提取算法，大致可分3類：分割聚類算法、基于時(shí)間的聚類算法和基于密度的聚類算法。Ashbrook等利用K-Means算法設(shè)計(jì)了基于分割聚類的停留點(diǎn)挖掘方法[7]。該算法首先提取位置點(diǎn)，再用改進(jìn)的K-Means算法將這些位置點(diǎn)聚類得到停留點(diǎn)，但該算法無法獲取GPS信號(hào)未完全消失的室內(nèi)地點(diǎn)。Kang等利用軌跡點(diǎn)的時(shí)間連續(xù)性設(shè)計(jì)了一個(gè)基于時(shí)間的聚類算法以挖掘停留點(diǎn)[8]，然而GPS信號(hào)丟失問題會(huì)擾亂位置點(diǎn)的時(shí)間連續(xù)性，導(dǎo)致遺漏某些停留點(diǎn)?；诿芏鹊木垲愃惴▽?duì)位置點(diǎn)稠密區(qū)域進(jìn)行聚類，如SMoT[9]、CB-SMoT[10]、DJ-Cluster[11]等，此類算法可發(fā)現(xiàn)任意形狀的停留點(diǎn)，但難以解決GPS信號(hào)在室內(nèi)丟失的問題。建筑物對(duì)GPS信號(hào)的屏蔽使得信號(hào)在進(jìn)入和離開建筑物時(shí)產(chǎn)生兩個(gè)聚類區(qū)，文獻(xiàn)[12]在基于時(shí)間的聚類算法[8]基礎(chǔ)上，根據(jù)時(shí)間間隔閾值和容忍距離閾值決定是否對(duì)這兩個(gè)聚類區(qū)進(jìn)行合并處理。但由于現(xiàn)實(shí)世界中的建筑物大小不一，經(jīng)驗(yàn)值的選取較為困難，這種改進(jìn)并不能有效地判別用戶是僅從該建筑物內(nèi)穿過還是在其內(nèi)停留這一問題。

本文針對(duì)上述方法的不足，將速度變量引入停留點(diǎn)的提取，提出了基于速度的時(shí)間聚類算法和速度聚類算法。移動(dòng)對(duì)象處于停滯狀態(tài)時(shí)，速度字段的數(shù)值小于給定閾值,基于速度的時(shí)間聚類算法充分利用GPS軌跡數(shù)據(jù)這一特征，相對(duì)于軌跡記錄的逐條處理而言，計(jì)算效率得到很大的提高。而對(duì)于未記錄速度的GPS軌跡點(diǎn)，可以由上一點(diǎn)或下一點(diǎn)計(jì)算出速度值，因此基于速度聚類算法對(duì)于簡易的GPS數(shù)據(jù)(longitude,latitude,time)同樣具有很好的普適性，同時(shí)也能有效地避免停留點(diǎn)漏判問題。

1 移動(dòng)對(duì)象停留點(diǎn)的提取算法

1.1 原始軌跡獲取及預(yù)處理

空間軌跡由按時(shí)間先后順序排列的空間點(diǎn)組成?？臻g點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可以是簡單的(longitude,latitude,time)，也可以是復(fù)雜的(longitude,latitude,time,altitude,radius,speed,direction)。

不同的應(yīng)用場景，采集得到的空間軌跡特點(diǎn)不同。車載GPS不需要考慮省電問題，設(shè)備在車輛行進(jìn)期間一直保持供電;由于行駛在戶外，GPS信號(hào)一般不會(huì)丟失。因此車載GPS得到的空間點(diǎn)序列時(shí)間間隔恒定，一般不存在長時(shí)間位置信息缺失，是比較理想的空間軌跡處理樣本。當(dāng)前大多數(shù)的算法，也針對(duì)此類數(shù)據(jù)設(shè)計(jì)。通過手機(jī)取得的行人步行軌跡則不同，存在時(shí)間間隔變化大、較長時(shí)間位置信號(hào)缺失的情況。主要原因有：1)使用者進(jìn)入建筑物內(nèi)部，GPS信號(hào)消失，不能獲取位置信息，造成空間點(diǎn)序列中相鄰點(diǎn)時(shí)間間隔過長的情況;而在建筑物邊緣靠門或窗的地方，接收到的衛(wèi)星數(shù)目有限，位置精度不高，造成位置漂移或跳躍現(xiàn)象。2) 由于省電的要求，某些手機(jī)操作系統(tǒng)會(huì)殺死收集位置信息的后臺(tái)服務(wù)進(jìn)程;同樣，用戶出于省電的要求，也會(huì)有意識(shí)地禁用GPS位置服務(wù)。

上述原因使得個(gè)別定位點(diǎn)出現(xiàn)很大偏差，所以要識(shí)別異常點(diǎn)并將其剔除，即對(duì)軌跡進(jìn)行清洗。軌跡清洗可采用以下規(guī)則：1) 手機(jī)上獲取的位置信息一般包含radius字段，此字段記錄了定位的精度,可以設(shè)定一定閾值，將radius值過大的記錄剔除;2)采用文獻(xiàn)[13]的方法剔除速率異常點(diǎn)、時(shí)間戳異常點(diǎn)和“跳躍點(diǎn)”。

1.2 基于速度的時(shí)間聚類算法

對(duì)于空間點(diǎn) (longitude,latitude,time，altitude，radius，speed，direction)組成的空間軌跡，采用以下步驟進(jìn)行處理：1)沿時(shí)間軸將速度為零的紀(jì)錄通過時(shí)間閾值進(jìn)行聚類，生成候選停留點(diǎn)；2)使用速度閾值對(duì)候選停留點(diǎn)進(jìn)行過濾，得出實(shí)際停留點(diǎn)。

候選停留點(diǎn)的計(jì)算過程為：將移動(dòng)軌跡中速度為零的點(diǎn)按時(shí)間順序排列，將速度連續(xù)為零的軌跡點(diǎn)進(jìn)行合并，使時(shí)間間隔小于某個(gè)閾值ε的相鄰軌跡點(diǎn)成為一個(gè)聚類，即候選停留點(diǎn)。之所以稱為“候選停留點(diǎn)”是因?yàn)榇嬖谌缦虑樾危涸谙噜彽牟蓸訒r(shí)刻點(diǎn)上研究對(duì)象的速度為零，但相鄰兩個(gè)時(shí)刻點(diǎn)的時(shí)段內(nèi)，研究對(duì)象卻處于運(yùn)動(dòng)狀態(tài)，其速度并不為零。例如出租車在當(dāng)前時(shí)刻Ti處于位置Locationi，其速度為0，下一時(shí)刻Ti+1處于位置Locationi+1，其速度也是0，而在Ti和Ti+1兩個(gè)時(shí)刻之間，車輛可能處于運(yùn)動(dòng)狀態(tài)。因此得到的聚類可能是偽停留點(diǎn)。具體方法見算法1。

算法1 基于速度的時(shí)間聚類算法(候選停留點(diǎn)提取)

Input:üm//速度為零的軌跡點(diǎn)記錄,m為軌跡點(diǎn)數(shù)目

ε//時(shí)間閾值

Output:Ψn//候選停留點(diǎn),n為候選停留點(diǎn)數(shù)目

1.Ψ0←Φ,i←1,j←1;

2.BEGIN;

3.FETCHLoc0∈üm;

4.Tlast=Tstart=Loc0.time;//起始點(diǎn)的時(shí)間和位置

5.Locstart=Loc0;

6.WHILEi

7.FETCHLoci∈üm-i;

8.Tcurrent=Loci.time,Δt=Tcurrent-Tlast;

9.IFΔt<εTHEN //小于經(jīng)驗(yàn)閾值,當(dāng)前點(diǎn)和上一點(diǎn)聚合

10.Locend=Loci;

11.Tlast=Tend=Loci.time;

12.ELSE //聚合過程停止,記錄候選停留點(diǎn)的信息

13.Loccenter=CenterOf(Locstart,Locend);

14.Rowj=(Tstart,Loccenter,Tend);

15.Ψj←Rowj;

16.j←j+1;

17.Tstart=Tlast=Loci.time;//準(zhǔn)備進(jìn)行下一次聚合

18.Locstart=Loci;

19.END IF;

20.i←i+1;

21.END LOOP;

22.RETURNΨn;

23.END

從候選停留點(diǎn)中篩選出停留點(diǎn)的過程為：對(duì)連續(xù)兩個(gè)時(shí)刻內(nèi)的運(yùn)動(dòng)狀態(tài)進(jìn)行判斷，使用速度變量進(jìn)行過濾，即如果Δd=Distance(Locationi,Locationi+1),v=Δd/Δt小于速度的經(jīng)驗(yàn)閾值ρ，說明此移動(dòng)對(duì)象在Δt時(shí)段內(nèi)處于停止?fàn)顟B(tài)；否則，處于運(yùn)動(dòng)狀態(tài)。具體方法見算法2。

算法2 基于速度的時(shí)間聚類算法(停留點(diǎn)提取)

Input:üm//候選停留點(diǎn),m為候選停留點(diǎn)數(shù)目

ρ//速度閾值

Output:Ψn//停留點(diǎn),n為停留點(diǎn)數(shù)目

1.Ψ0←Φ,i←0,j←1;

2.BEGIN;

3.WHILEi

4.FETCHregioni∈üm;//判斷候選停留點(diǎn)聚合過程中運(yùn)動(dòng)狀態(tài)

5.v=CalVelocity(regioni.endPoint,regioni.startPoint);

6.IFv<ρTHEN

7.Ψ←regioni; //滿足條件,歸入停留點(diǎn)集合

8.j←j+1;

9.END IF;

10.i←i+1;

11.END LOOP;

12.RETURNΨn;

13.END

1.3 速度聚類算法

對(duì)于軌跡采樣點(diǎn)數(shù)據(jù)缺失、采樣頻率不穩(wěn)定(即采樣間隔不確定)的情形，基于速度的時(shí)間聚類算法則不能夠很好地適應(yīng)。本文提出速度聚類算法對(duì)此類數(shù)據(jù)進(jìn)行分析處理，將停留點(diǎn)的提取問題分解為對(duì)速度的判斷和對(duì)GPS信號(hào)消失空間區(qū)域的判斷兩個(gè)子問題。

對(duì)于在時(shí)間軸上彼此相鄰的軌跡采樣點(diǎn)，如果這兩個(gè)相鄰點(diǎn)的距離-時(shí)間比(即速度)小于某一個(gè)閾值，則可認(rèn)為移動(dòng)對(duì)象在這兩點(diǎn)所在時(shí)段內(nèi)處于停留狀態(tài)。在實(shí)際應(yīng)用中，停留點(diǎn)中的GPS軌跡采樣點(diǎn)并非表現(xiàn)為絕對(duì)的靜止不動(dòng)，而是一些小幅偏移點(diǎn)的聚合(圖1中采樣點(diǎn)聚集區(qū)是移動(dòng)對(duì)象停留點(diǎn))。假設(shè)在時(shí)間軸上有彼此相鄰的4個(gè)采樣點(diǎn)((Locationi-1,Ti-1)→(Locationi,Ti)→(Locationi+1,Ti+1)→(Locationi+2,Ti+2))，如果移動(dòng)對(duì)象在前兩個(gè)采樣點(diǎn)之間的時(shí)段內(nèi)(Ti-1,Ti)處于停留狀態(tài)，在后兩個(gè)采樣點(diǎn)之間的時(shí)段內(nèi)(Ti,Ti+1)也處于停留狀態(tài)，也就是依次連續(xù)地處于停留狀態(tài)，則將當(dāng)前的停留狀態(tài)與上一停留狀態(tài)進(jìn)行歸并，即對(duì)連續(xù)的停留狀態(tài)進(jìn)行聚類從而形成停留點(diǎn)StayPoint((Locationi-1,Ti-1),(Locationi+1,Ti+1))。而對(duì)于(Locationi+2,Ti+2)，如果在(Ti+1,Ti+2)時(shí)段內(nèi)該移動(dòng)對(duì)象依然處于停留狀態(tài)，則繼續(xù)向上述停留點(diǎn)歸并，直到移動(dòng)對(duì)象由停留狀態(tài)轉(zhuǎn)向運(yùn)動(dòng)狀態(tài)，最終得到停留點(diǎn)為StayPoint((Locationi-1,Ti-1),(Locationi+2,Ti+2))。

圖1 速度聚類算法

在現(xiàn)實(shí)環(huán)境中存在的另一問題就是移動(dòng)對(duì)象遭遇信號(hào)盲區(qū)，即GPS信號(hào)在某一區(qū)域內(nèi)消失，進(jìn)而導(dǎo)致在該區(qū)域內(nèi)軌跡數(shù)據(jù)缺失。而GPS信號(hào)缺失主要分為兩類情形：1)由于屏障的存在而引起，諸如車輛進(jìn)出隧道、行人通過地下通道或進(jìn)出大型建筑物等情形；2)由于GPS軌跡采集器本身存在的問題而引起，如手機(jī)端的GPS軌跡采集器因手機(jī)沒電而停止，或出于省電的考慮用戶手動(dòng)關(guān)閉GPS軌跡采集器。對(duì)于前一種情形，移動(dòng)對(duì)象在一定時(shí)間內(nèi)很少再次返回到該地點(diǎn)，根據(jù)空間距離-時(shí)間比(速度)這一條件判斷移動(dòng)對(duì)象所處的運(yùn)動(dòng)狀態(tài)；對(duì)于后一種情形，當(dāng)GPS信號(hào)在某一地點(diǎn)長時(shí)間缺失后在該地點(diǎn)附近再次出現(xiàn)時(shí)，可能形成信號(hào)盲區(qū)內(nèi)的偽停留點(diǎn)。如果僅僅根據(jù)速度這一條件判斷移動(dòng)對(duì)象的運(yùn)動(dòng)狀態(tài)，則可能將偽停留點(diǎn)誤判為實(shí)際停留點(diǎn)。下面是一個(gè)可能產(chǎn)生偽停留點(diǎn)的例子：某高校學(xué)生志愿者，上午Ti時(shí)刻在某實(shí)驗(yàn)樓Locationi時(shí)GPS信號(hào)存在，由于某種原因GPS信號(hào)長時(shí)間缺失，直到晚上Tj時(shí)刻回到宿舍樓Locationj時(shí)信號(hào)再次出現(xiàn)，這段時(shí)間內(nèi)該學(xué)生已從實(shí)驗(yàn)樓到過其他若干地方，最后再回到宿舍。如果僅僅通過速度確定停留點(diǎn)(v<ρ，則認(rèn)為處于停留狀態(tài))，就會(huì)出現(xiàn)很大的偏差。這種情形下該停留點(diǎn)的中心是實(shí)驗(yàn)樓Locationi和宿舍樓Locationj的區(qū)域中心處——圖書館Locationt(圖2)，而現(xiàn)實(shí)情況是圖書館并非是該學(xué)生的停留點(diǎn)(此時(shí)，圖書館是一個(gè)信號(hào)盲區(qū)內(nèi)的偽停留點(diǎn))。信號(hào)盲區(qū)的存在會(huì)影響對(duì)移動(dòng)對(duì)象真實(shí)停留點(diǎn)描述的準(zhǔn)確性。

圖2 GPS信號(hào)消失重現(xiàn)形成的偽停留點(diǎn)

對(duì)于上述情形，可借助空間距離閾值BlindRegion對(duì)兩個(gè)采樣點(diǎn)的空間距離Δd進(jìn)行過濾。如果相鄰兩個(gè)采樣點(diǎn)間的空間距離過大(超出經(jīng)驗(yàn)距離閾值)，且通過速度變量判斷處于停留狀態(tài)的區(qū)域，則認(rèn)為這兩點(diǎn)間存在信號(hào)消失和重現(xiàn)情況，兩個(gè)相鄰的采樣點(diǎn)應(yīng)隸屬于不同的停留點(diǎn)集合。具體實(shí)現(xiàn)方法見算法3。

算法3 速度聚類算法

Input:üm//移動(dòng)對(duì)象全天的軌跡點(diǎn),m為軌跡點(diǎn)數(shù)目

ρ//速度閾值

blindRegion//信號(hào)盲區(qū)閾值

Output:Ψn//軌跡點(diǎn)中的停留點(diǎn)集合，n為停留點(diǎn)數(shù)目

1.Ψ0←Φ,i←1,j←0;flag←0,isMove=1;

2.BEGIN;

3.FETCHLoc0∈üm;

4.WHILEi

5.FETCHLoci∈üm-1;

6.v=CalVelocity(Loci-1,Loci); //相鄰采樣點(diǎn)間的平均速度

7.Δd=CalDistance(Loci-1,Loci);//相鄰采樣點(diǎn)間的空間距離

8.IFv<ρANDΔd

9.flag←flag+1;//相鄰點(diǎn)處于停止態(tài)flag自增,連續(xù)停止

flag不斷自增

10.IFisMove>0 THEN;

11.Tstart=Loci-1.time；

12.Locstart=Loci-1；

13.END IF；

14.isMove=-1；

16.Tend=Loci.time;

17.Locend=Loci;

18.END IF;

19.ELSE //離開停留點(diǎn),處于運(yùn)動(dòng)狀態(tài)

20.isMove=1;

21.IFflag>0 THEN //記錄前一停留點(diǎn)的信息

22.Loccenter=CenterOf(Locstart,Locend);

23.Rowj=(Tstart,Loccenter,Tend);

中國各個(gè)時(shí)期園林呈現(xiàn)不同的文化特質(zhì)。秦漢時(shí)期的園林主流是一種人工的自然山水園，注重模仿自然和模擬景致的自然美，對(duì)于雄奇壯麗的自然美缺乏一種具有人文意蘊(yùn)的審美意識(shí)。這個(gè)時(shí)期園林文化呈現(xiàn)的特質(zhì)是居住與園林相結(jié)合的宅園，注重的是形似，缺乏精神和意境的追求。

24.Ψj←Rowj,j←j+1;

25.END IF;

26.flag←0;i←i+1;

27.END IF;

28.END LOOP;

29.RETURNΨn;

30.END

2 算法應(yīng)用實(shí)例及分析

本文提出的算法通過擴(kuò)展空間數(shù)據(jù)庫PostGIS/PostgreSQL實(shí)現(xiàn)。對(duì)于特別要求效率的部分，使用C語言編寫成數(shù)據(jù)庫擴(kuò)展[14,15]，其他部分則直接使用數(shù)據(jù)庫的過程語言PL/pgSQL實(shí)現(xiàn)。原始軌跡數(shù)據(jù)使用分區(qū)表存儲(chǔ)在空間數(shù)據(jù)庫，停留點(diǎn)的提取通過SQL語句直接進(jìn)行，生成的結(jié)果直接存成數(shù)據(jù)庫中的表，方便后續(xù)應(yīng)用。

2.1 出租車軌跡的停留點(diǎn)提取

本實(shí)驗(yàn)使用的GPS軌跡數(shù)據(jù)為某城市1個(gè)月的出租車運(yùn)動(dòng)軌跡，記錄了車輛的longitude、latitude、time、direction、speed以及上下客信息。出租車GPS軌跡上報(bào)的時(shí)間間隔為35～40 s。此數(shù)據(jù)為典型的穩(wěn)定時(shí)間間隔的軌跡數(shù)據(jù)[16,17]。

設(shè)在基于速度的時(shí)間聚類算法中采用的參數(shù)為：ε=45 s,ρ=1 m/s,長時(shí)停留點(diǎn)的停留時(shí)間下限為90 s；速度聚類算法選用的速度經(jīng)驗(yàn)閾值也是1 m/s，長時(shí)間停留點(diǎn)的停留時(shí)間下限同樣選取90 s。圖3是某輛車全天24 h在某城市道路網(wǎng)上的軌跡點(diǎn)和兩種算法提取的停留點(diǎn)。

圖3 兩種算法的停留點(diǎn)比較

由圖3可以看出，停留點(diǎn)大多位于路口，這符合出租車因紅燈而停留的情況;同時(shí)，結(jié)果中也包含了出租車上下客形成的停留點(diǎn)。與速度聚類算法相比，基于速度的時(shí)間聚類算法可以找出其無法識(shí)別的停留點(diǎn)(如圖3中A-H)，因此，更適合出租車數(shù)據(jù)的處理。

對(duì)于基于速度的時(shí)間聚類算法，本實(shí)驗(yàn)的時(shí)間閾值ε略大于GPS軌跡采樣間隔的上限值。若ε過小，則聚類結(jié)果會(huì)產(chǎn)生過多的候選停留點(diǎn)，增加了停留點(diǎn)篩選的計(jì)算量；若ε較大，則聚類產(chǎn)生的候選停留點(diǎn)太少，會(huì)遺漏真實(shí)的停留點(diǎn)。在兩個(gè)算法對(duì)比的過程中，考慮到出租車在35～40 s的GPS軌跡采樣間隔內(nèi)可能停留的情形，本實(shí)驗(yàn)將停留時(shí)長較短的停留點(diǎn)剔除，只選取停留時(shí)長大于90 s的停留點(diǎn)。隨機(jī)選取3輛出租車的軌跡，使用兩種算法分別提取停留點(diǎn)并計(jì)算重合率，重合率均達(dá)90%以上。

2.2 步行軌跡的停留點(diǎn)提取

本次實(shí)驗(yàn)數(shù)據(jù)通過手機(jī)App獲取，設(shè)定采樣間隔為5 s。實(shí)際獲取數(shù)據(jù)如表1所示，有信號(hào)缺失情況。軌跡數(shù)據(jù)中含有radius(即GPS信號(hào)中的定位精度)字段，在對(duì)軌跡數(shù)據(jù)進(jìn)行清洗時(shí)，將radius>15 m的軌跡點(diǎn)刪除。軌跡采集志愿者手動(dòng)上報(bào)真實(shí)停留點(diǎn)，用來和實(shí)驗(yàn)得到的停留點(diǎn)進(jìn)行對(duì)比分析。

表1 步行GPS軌跡數(shù)據(jù)

圖4(彩圖見封2)為采用文獻(xiàn)[12]改進(jìn)的基于時(shí)間的聚類算法計(jì)算得到的停留點(diǎn)結(jié)果。圖中的紅色圓圈代表停留點(diǎn)或偽停留點(diǎn),其半徑大小代表停留時(shí)長;黃色小點(diǎn)代表行人的GPS軌跡點(diǎn)，局部放大圖形中紅色箭頭代表行進(jìn)方向?？梢娖溥x取的時(shí)間閾值依賴于建筑物的大小。如果時(shí)間閾值過小，不能剔除通過大型建筑物時(shí)形成的偽停留點(diǎn)(圖4a)；當(dāng)時(shí)間閾值過大，通過小型建筑物并在其中停留的真實(shí)停留點(diǎn)將被遺漏(圖4b)。

圖5(彩圖見封2)為本文提出的速度聚類算法計(jì)算得到的結(jié)果。步行速度閾值設(shè)定為0.1 m/s(該閾值與日常生識(shí)相符，小于該閾值則認(rèn)為處于停留狀態(tài))，BlindRegion設(shè)定為200 m。圖5a中是基于未設(shè)置BlindRegion參數(shù)的速度聚類算法對(duì)軌跡停留點(diǎn)進(jìn)行挖掘的結(jié)果，此時(shí)出現(xiàn)偽停留點(diǎn)(被紅色圓圈標(biāo)記的紅色圓域)。圖5b中使用速度聚類算法將BlindRegion設(shè)置為200 m，對(duì)志愿者軌跡點(diǎn)的停留點(diǎn)進(jìn)行挖掘，其中局部放大的圖形是志愿者早上進(jìn)入食堂用餐所形成的停留點(diǎn)，藍(lán)色圓圈是志愿者穿過建筑物GPS信號(hào)消失的區(qū)域，根據(jù)運(yùn)行速度可知用戶僅僅是通過這些建筑物而非停留。

圖4 改進(jìn)的基于速度的時(shí)間聚類算法

圖5 速度聚類算法

速度聚類算法不涉及時(shí)間閾值，且其速度閾值是獨(dú)立的，不依賴于建筑物的大小。對(duì)比圖4和圖5可以看出,速度聚類算法較好地避免了停留點(diǎn)識(shí)別過程中的誤判和漏判問題。

關(guān)于BlindRegion參數(shù)的設(shè)定，如果設(shè)置過大，將會(huì)使不同的停留點(diǎn)聚合為一個(gè)停留點(diǎn)，從而產(chǎn)生細(xì)粒度(大比例尺)水平上的偽停留點(diǎn)。例如將BlindRegion設(shè)為無窮大，在遭遇圖2所描述的情形時(shí)，A處停留點(diǎn)和B處停留點(diǎn)將會(huì)被合并(如圖5a所示)，進(jìn)而會(huì)形成偽停留點(diǎn)。如果設(shè)置過小，將會(huì)使本應(yīng)合并為一個(gè)停留點(diǎn)的軌跡點(diǎn)群產(chǎn)生兩個(gè)鄰近的停留點(diǎn)，例如在大型建筑物的A側(cè)進(jìn)入，經(jīng)過長時(shí)間停留后從B側(cè)離開，由于A側(cè)和B側(cè)距離較遠(yuǎn)(大于BlindRegion)，則會(huì)在A側(cè)和B側(cè)分別產(chǎn)生兩個(gè)停留點(diǎn)，實(shí)際上停留點(diǎn)CenterOf(A,B)更符合真實(shí)情況。BlindRegion參數(shù)的具體數(shù)值，采用二分法思想逐段逼近對(duì)比挖掘效率，采用文獻(xiàn)[12]中的參數(shù)評(píng)判變量漏報(bào)率(即漏報(bào)數(shù)量與用戶記錄的訪問點(diǎn)數(shù)量的比值)和誤報(bào)率(即誤報(bào)數(shù)量與算法挖掘的訪問點(diǎn)數(shù)量的比值)，對(duì)8名志愿者1個(gè)月的出行軌跡數(shù)據(jù)進(jìn)行計(jì)算分析，結(jié)果表明BlindRegion參數(shù)取值范圍在200～300 m時(shí)識(shí)別效果較好。

3 結(jié)語

本文針對(duì)空間軌跡停留點(diǎn)識(shí)別提取過程中的“偽停留點(diǎn)”和“停留點(diǎn)丟失”問題，提出了基于速度的時(shí)間聚類算法和速度聚類算法。在基于速度的時(shí)間聚類算法中，首先沿時(shí)間軸將速度接近零的記錄進(jìn)行聚類選出候選停留點(diǎn)，然后利用速度閾值過濾候選停留點(diǎn)，得出實(shí)際停留點(diǎn)。速度聚類算法則將停留點(diǎn)的提取問題分解為對(duì)速度的判斷和對(duì)GPS信號(hào)消失空間區(qū)域的判斷兩個(gè)子問題。兩種方法算法清晰，效率較高。本文采用C語言和PLpgSQL直接將算法設(shè)計(jì)成空間數(shù)據(jù)庫PostGIS/PostgreSQL的一個(gè)擴(kuò)展，可以直接使用SQL調(diào)用。通過出租車GPS軌跡和行人步行軌跡對(duì)兩種方法進(jìn)行了驗(yàn)證，結(jié)果表明基于速度的時(shí)間聚類方法能很好地適用于采樣間隔較恒定、一般不存在長時(shí)間軌跡點(diǎn)缺失的數(shù)據(jù),而速度聚類算法能更好地適用于可能存在長時(shí)間軌跡點(diǎn)缺失的步行數(shù)據(jù)。在后續(xù)的研究中會(huì)加入對(duì)軌跡點(diǎn)特征的判斷以確定自動(dòng)采用何種算法對(duì)相應(yīng)的軌跡進(jìn)行處理。

[1] 陳康,黃曉宇,王愛玉,等.基于位置信息的用戶行為軌跡分析與應(yīng)用綜述[J].電信科學(xué),2013(4):118-124.

[2] 張德干,王冬.面向LBS的服務(wù)匹配方法研究[J].計(jì)算機(jī)科學(xué),2012,39(3):19-22,61.

[3] 馬林兵,李鵬.基于子空間聚類算法的時(shí)空軌跡聚類[J].地理與地理信息科學(xué),2014,30(4):7-11,127.

[4] ZHENG Y,ZHANG L,MA Z,et al.Recommending friends and locations based on individual location history[J].ACM Transactions on the Web (TWEB),2011,5(1):3-9.

[5] AlVARES L O,BOGORNY V,DE MACEDO J A F,et al.Dynamic modeling of trajectory patterns using data mining and reverse engineering[A].Tutorials,Posters,Panels and Industrial Contributions at the 26th International Conference on Conceptual Modeling-Volume 83[C].Australian Computer Society,Inc.,2007.149-154.

[6] BOGORNY V,KUIJPERS B,AlVARES L O.ST-DMQL:A semantic trajectory data mining Query language[J].International Journal of Geographical Information Science,2009,23(10):1245-1276.

[7] ASHBROOK D,STARRIER T.Using GPS to learn significant locations and predict movement across multiple users[J].Personal and Ubiquitous Computing,2003,7(5):275-286.

[8] KANG J H,WELBOURNE W,STEWART B,et al.Extracting places from traces of locations[J].ACM SIGMOBILE Mobile Computing and Communications Review,2005,9(3):58-68.

[9] AlVARES L O,BOGORNY V,KUIJPERS B,et al.A model for enriching trajectories with semantic geographical information[A].Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems[C].2007.1-8.

[10] PALMA A T,BOGORNY V,KUIJPERS B,et al.A clustering-based approach for discovering interesting places in trajectories[A].Proc.of ACM Symposium on Applied Computing[C].2008.863-868.

[11] ZHOU C,FRANKOWSKI D,LUDFORD P,et al.Discovering personally meaningful places:An interactive clustering approach[J].ACM Transaction on Information Systems,2007,25(3):1-31.

[12] 呂明琪.基于軌跡數(shù)據(jù)的語義化位置感知計(jì)算研究[D].杭州：浙江大學(xué),2012.19-38.

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

[14] 金美含.基于PostgreSQL/PostGIS的原生軌跡數(shù)據(jù)庫研究[D].長沙：中南大學(xué),2014.11-21.

[15] https://www.postgresql.org/docs/9.5/static/index.html.2016-08-11.

[16] 張俊濤,武芳,張浩.利用出租車軌跡數(shù)據(jù)挖掘城市居民出行特征[J].地理與地理信息科學(xué),2015,31(6):104-108.

[17] 何雯,李德毅,安利峰,等.基于GPS軌跡的規(guī)律路徑挖掘算法[J].吉林大學(xué)學(xué)報(bào)(工學(xué)版),2014,44(6):1764-1770.

Algorithm Study for Stay Points Recognition of Spatial Trajectory Based on Velocity

HOU Ying-chao,WANG Pan-cheng,LIU Xing-quan,TENG Jie

(DepartmentofGeo-informatics,SchoolofGeosciencesandInfo-Physics,CentralSouthUniversity,Changsha410083,China)

Stay point recognition is a key step to convert spatial trajectory to semantic trajectory.Velocity is employed to recognize stay points.Velocity-based time clustering algorithm and velocity clustering algorithm are presented to solve pseudo stay points and losing of stay points.Given time threshold,trajectory points are clustered by velocity-based time clustering algorithm along the time axis to get candidate stay points，then real stay points are filtered out by given velocity threshold.To avoid missing stay points,the velocity clustering algorithm divides the stay point recognition task into two phases:1)Stay point candidates are obtained through the judgment of velocity;2) Real stay points are filtered out from stay point candidates by the given spatial distance threshold.Experiments show that velocity-based time clustering algorithm can recognize stay points of the spatial trajectory with stable sampling time interval well,while velocity clustering algorithm can be better adapted to the pedestrian track points which sometimes may disappear for a long time.

stay point;spatial trajectory;velocity clustering;time clustering

2016-08-16；

2016-10-20

湖南省自然科學(xué)基金項(xiàng)目(10JJ6061)

侯穎超(1987-)，男，碩士研究生，主要從事軌跡數(shù)據(jù)挖掘研究。*通訊作者 E-mail:wangpancheng@csu.edu.cn

10.3969/j.issn.1672-0504.2016.06.011

P208

A

1672-0504(2016)06-0063-06