基于密度的停留點(diǎn)識(shí)別方法

李毓瑞，陳紅梅，王麗珍，肖清

云南大學(xué)信息學(xué)院，云南 昆明 650091

1 引言

隨著移動(dòng)設(shè)備、移動(dòng)互聯(lián)網(wǎng)等技術(shù)的發(fā)展，用戶、車輛等移動(dòng)對(duì)象產(chǎn)生的GPS軌跡數(shù)據(jù)總量呈爆炸式增長(zhǎng)。通過分析GPS軌跡數(shù)據(jù)，人們可以發(fā)現(xiàn)移動(dòng)對(duì)象的時(shí)空模式，進(jìn)而提供基于位置的服務(wù)，例如用戶行為分析[1-2]、個(gè)性化興趣點(diǎn)推薦[3-4]等。GPS軌跡數(shù)據(jù)的采樣頻率普遍較高，但其中的軌跡點(diǎn)并不是同等重要的，有些軌跡點(diǎn)僅僅是移動(dòng)對(duì)象瞬時(shí)經(jīng)過的地方，例如用戶乘車經(jīng)過的公交站，而有些軌跡點(diǎn)集合代表了移動(dòng)對(duì)象在某個(gè)地方停留了一段時(shí)間，即停留點(diǎn)，例如代表用戶在商場(chǎng)購(gòu)物或在家中休息的軌跡點(diǎn)集合。停留點(diǎn)是移動(dòng)對(duì)象在較小空間區(qū)域內(nèi)停留了較長(zhǎng)時(shí)間的軌跡點(diǎn)集合。從GPS軌跡數(shù)據(jù)中識(shí)別停留點(diǎn)，可以有效去除GPS軌跡數(shù)據(jù)中不重要的和冗余的信息，而得到的停留點(diǎn)序列有助于對(duì)GPS軌跡序列的深入理解。因此停留點(diǎn)識(shí)別是軌跡數(shù)據(jù)分析的重要預(yù)處理步驟，是位置服務(wù)的基礎(chǔ)。

現(xiàn)有的停留點(diǎn)識(shí)別方法可以分為3類[5]：基于聚類策略的方法、基于概率策略的方法和基于區(qū)分策略的方法。基于聚類策略的方法是對(duì)GPS軌跡數(shù)據(jù)進(jìn)行時(shí)空聚類，包括僅考慮空間因素的方法（如DBSCAN[6]）以及同時(shí)考慮時(shí)間因素的方法（如DJCluster[7]和CB-SMoT[8]）?；诟怕什呗缘姆椒ㄍㄟ^概率模型，從GPS軌跡數(shù)據(jù)中推導(dǎo)頻繁訪問的地點(diǎn)，這些概率模型包括高斯混合模型[9]、貝葉斯模型[10]、條件隨機(jī)場(chǎng)[11]?；趨^(qū)分策略的方法通過分析GPS軌跡點(diǎn)之間的時(shí)間和空間差異，尋找停留點(diǎn)及其代表點(diǎn)[12-16]，其需要兩個(gè)閾值：限定移動(dòng)對(duì)象停留區(qū)域大小的距離閾值和限定移動(dòng)對(duì)象停留時(shí)間長(zhǎng)度的時(shí)間閾值。在這3類方法中，基于聚類策略的方法主要考慮軌跡點(diǎn)的時(shí)空鄰近，基于概率策略的方法主要考慮軌跡點(diǎn)的訪問頻率，它們都沒有考慮軌跡點(diǎn)的時(shí)間連續(xù)性和方向性。而基于區(qū)分策略的方法僅考慮了時(shí)間連續(xù)性的一個(gè)方向，沒有考慮停留點(diǎn)中軌跡點(diǎn)的時(shí)空聚集。

為了更好地識(shí)別停留點(diǎn)，有必要考慮軌跡點(diǎn)的時(shí)間連續(xù)性和方向性以及時(shí)空聚集。如果不考慮軌跡點(diǎn)的時(shí)間連續(xù)性，可能會(huì)得到一些無意義的停留點(diǎn)[14]。如圖1所示，用戶在上班、購(gòu)物、回家途中多次但不連續(xù)經(jīng)過虛線所圈的路口，深色軌跡點(diǎn)之間的距離滿足距離閾值且它們的累計(jì)時(shí)間滿足時(shí)間閾值。如果不考慮時(shí)間連續(xù)性，它們會(huì)被判定為停留點(diǎn)，但是它們并不代表用戶的停留行為。

如果僅考慮時(shí)間連續(xù)性的一個(gè)方向，可能會(huì)漏掉一些有意義的停留點(diǎn)。如圖2所示，由5個(gè)軌跡點(diǎn)組成的軌跡點(diǎn)序列分布在較小的空間區(qū)域內(nèi)且時(shí)間跨度較大，從而構(gòu)成一個(gè)停留點(diǎn)，其中，軌跡點(diǎn)p1到p2的距離大于距離閾值，但軌跡點(diǎn)p3到其他點(diǎn)的距離都小于距離閾值，并且p1到p5的時(shí)間跨度大于時(shí)間閾值，但p2到p5的時(shí)間跨度小于時(shí)間閾值。若僅考慮向前這個(gè)方向，由于p1到p2的距離大于距離閾值，而p2到p5的時(shí)間跨度不滿足時(shí)間閾值，因此不能識(shí)別這個(gè)停留點(diǎn)[14]。但是，若以p3為錨點(diǎn)，考慮向前和向后兩個(gè)方向，即可識(shí)別這個(gè)停留點(diǎn)。

圖1 不考慮時(shí)間連續(xù)性下的停留點(diǎn)

圖2 考慮時(shí)間方向性后的停留點(diǎn)

基于上述討論，本文提出一種新的基于區(qū)分策略的方法：基于密度的停留點(diǎn)識(shí)別（stay point identification based on density，SPID）方法。本文主要貢獻(xiàn)如下。

● 考慮了軌跡點(diǎn)的時(shí)空聚集，即計(jì)算軌跡點(diǎn)的密度區(qū)間及密度，生成候選集。根據(jù)密度，迭代地在候選集中進(jìn)行識(shí)別、更新操作，得到停留點(diǎn)集。

● 兼顧了軌跡點(diǎn)的時(shí)間連續(xù)性和方向性，即在計(jì)算軌跡點(diǎn)的密度區(qū)間及密度時(shí)，沿時(shí)間維從向后和向前兩個(gè)方向，搜索時(shí)間連續(xù)且滿足距離閾值的軌跡點(diǎn)。

● 設(shè)計(jì)了有效的基于密度的停留點(diǎn)識(shí)別方法，并通過在GeoLife數(shù)據(jù)集上的實(shí)驗(yàn)，驗(yàn)證了該方法的識(shí)別能力優(yōu)于基準(zhǔn)方法，可以進(jìn)一步識(shí)別基準(zhǔn)方法不能識(shí)別的兩類停留點(diǎn)。

2 相關(guān)工作

現(xiàn)有的停留點(diǎn)識(shí)別方法可以分為3類：基于聚類策略的方法、基于概率策略的方法和基于區(qū)分策略的方法。本節(jié)將分別對(duì)這3類方法進(jìn)行介紹。

2.1 基于聚類策略的方法

基于聚類策略的方法設(shè)計(jì)距離度量，采用聚類算法，聚類軌跡點(diǎn)為停留點(diǎn)，包括僅考慮空間因素的方法和同時(shí)考慮時(shí)空因素的方法。Ashbrook D等人[17]采用K-means聚類算法識(shí)別停留點(diǎn)；Toyama N等人[18]分析了聚類半徑對(duì)停留點(diǎn)識(shí)別結(jié)果的影響；Zhou C Q等人[7]基于DBSCAN聚類算法提出停留點(diǎn)識(shí)別方法DJ-Cluster；Palma A T等人[8]在DBSCAN算法中引入時(shí)間因素，提出識(shí)別方法CB-SmoT；Zimmermann M等人[19]引入時(shí)間因素提升OPTICS聚類算法在停留點(diǎn)識(shí)別中的效果；Cao X等人[20]針對(duì)汽車軌跡數(shù)據(jù)，采用OPTICS（ordering points to identify the clustering structure）算法和K-means算法識(shí)別停留點(diǎn)。

2.2 基于概率策略的方法

基于概率策略的方法建立概率模型，從GPS軌跡數(shù)據(jù)中推導(dǎo)頻繁訪問的地點(diǎn)。Zhang K S等人[21]使用高斯混合模型，提出一種停留點(diǎn)在線學(xué)習(xí)算法。Liao L等人[22]提出了一種基于條件隨機(jī)場(chǎng)的停留點(diǎn)識(shí)別算法。Nurmi P等人[10]提出了一種基于狄利克雷過程的非參數(shù)停留點(diǎn)識(shí)別方法。

2.3 基于區(qū)分策略的方法

基于區(qū)分策略的方法通過分析軌跡點(diǎn)在時(shí)間和空間上的差異，識(shí)別停留點(diǎn)及其代表點(diǎn)。Hariharan R等人[12]從錨點(diǎn)出發(fā)，沿時(shí)間維向前選擇滿足時(shí)間閾值的子軌跡，然后根據(jù)距離閾值判斷子軌跡是否構(gòu)成一個(gè)停留點(diǎn)，并將停留點(diǎn)中到其他軌跡點(diǎn)的最大距離最小化的軌跡點(diǎn)作為代表點(diǎn)。Li Q N等人[14]從錨點(diǎn)出發(fā)，沿時(shí)間維向前選擇滿足距離閾值的子軌跡，然后根據(jù)時(shí)間閾值判斷子軌跡是否構(gòu)成了一個(gè)停留點(diǎn)，并采用停留點(diǎn)中軌跡點(diǎn)的平均位置點(diǎn)作為代表點(diǎn)。Liu J H等人[13]和Pérez-Torres R等人[15]分別采用Hariharan方法[12]和Li Q N等人的方法[14]預(yù)處理軌跡點(diǎn)序列，從中提取停留點(diǎn)。Pavan M等人[16]在Li Q N等人的方法[14]的基礎(chǔ)上考慮了速度。

與上述方法不同，本文提出一種新的基于區(qū)分策略的方法——基于密度的停留點(diǎn)識(shí)別方法，該方法考慮了軌跡點(diǎn)的時(shí)空聚集，兼顧了軌跡點(diǎn)的時(shí)間連續(xù)性和方向性。

3 相關(guān)概念及問題描述

如圖3所示，GPS軌跡點(diǎn)p(＜latitude,longitude＞, time)表示移動(dòng)對(duì)象在時(shí)間time位于坐標(biāo)＜latitude, longitude＞的位置，p.time表示軌跡點(diǎn)p的時(shí)間，p.longtitude表示經(jīng)度，p.latitude表示緯度。將移動(dòng)對(duì)象的軌跡點(diǎn)按時(shí)間有序連接，即得到移動(dòng)對(duì)象的軌跡點(diǎn)序列Traj =p1?p2?p3?…?pn-1?pn。

定義1軌跡點(diǎn)的密度區(qū)間

給定GPS軌跡點(diǎn)序列Traj，其中，任意軌跡點(diǎn)pa的密度區(qū)間pa.interval=[pas, pae]是滿足下列條件的連續(xù)子序列：

其中，pas和pae分別表示密度區(qū)間的起點(diǎn)和終點(diǎn)，dth是距離閾值，d(·)是距離函數(shù)，本文采用的是球面距離。

定義2軌跡點(diǎn)的密度

給定軌跡點(diǎn)pa的密度區(qū)間pa.interval=[pas, pae]，pa的密度pa.density定義為其密度區(qū)間中的軌跡點(diǎn)數(shù)目，即：

圖3 GPS軌跡點(diǎn)、軌跡點(diǎn)序列和停留點(diǎn)

定義3軌跡點(diǎn)的時(shí)間跨度

給定軌跡點(diǎn)pa的密度區(qū)間pa.interval=[pas, pae]，pa的時(shí)間跨度pa.timespan定義為其密度區(qū)間起點(diǎn)與終點(diǎn)的時(shí)間差，即：

事實(shí)上，軌跡點(diǎn)的密度是移動(dòng)對(duì)象在以此點(diǎn)為中心、距離閾值為半徑的區(qū)域內(nèi)的軌跡點(diǎn)數(shù)目。在軌跡點(diǎn)采樣頻率一定的情況下，軌跡點(diǎn)密度越大，移動(dòng)對(duì)象在該區(qū)域停留的時(shí)間越長(zhǎng)。

定義4停留點(diǎn)

給定GPS軌跡點(diǎn)序列Traj、距離閾值dth和時(shí)間閾值tth，停留點(diǎn)sp=[ps, pe]是滿足以下條件的連續(xù)子序列：

例如，在圖3中，如果連續(xù)軌跡點(diǎn)子序列[p5, p8] = p5?p6?p7?p8滿足定義4的停留點(diǎn)條件，即其中任意兩個(gè)軌跡點(diǎn)的距離小于或等于2dth，起點(diǎn)p5和終點(diǎn)p8的時(shí)間差大于或等于tth，則連續(xù)子序列[p5,p8]為一個(gè)停留點(diǎn)。

給定GPS軌跡點(diǎn)序列Traj、距離閾值dth和時(shí)間閾值tth，停留點(diǎn)識(shí)別的基本任務(wù)就是從Traj中找出盡可能多的、互不相交的、滿足定義4條件的停留點(diǎn)。

4 基于密度的停留點(diǎn)識(shí)別方法

本文所提的基于密度的停留點(diǎn)識(shí)別方法的處理框架如圖4所示，主要包括兩個(gè)步驟：密度計(jì)算和停留點(diǎn)識(shí)別。

4.1 密度計(jì)算

4.1.1 算法思想

在密度計(jì)算步驟中，依次以GPS軌跡點(diǎn)序列Traj中的每個(gè)軌跡點(diǎn)pa為錨點(diǎn)，根據(jù)距離閾值dth，沿時(shí)間維向后搜索和向前搜索，得到pa的密度區(qū)間pa.interval =[pas,pae]，基于密度區(qū)間計(jì)算pa的密度pa.density=ae-as+1和時(shí)間跨度pa.timespan = pae.time-pas.time，然后根據(jù)時(shí)間閾值，生成候選停留點(diǎn)列表。

（1）后向搜索

圖4 算法框架

后向搜索是以軌跡點(diǎn)pa為錨點(diǎn)，沿時(shí)間維向后搜索與pa的距離小于或等于距離閾值dth的在時(shí)間上連續(xù)的所有軌跡點(diǎn)，直至最后一個(gè)滿足條件的軌跡點(diǎn)pas，即搜索滿足下列條件的軌跡點(diǎn)pi：

因此，后向搜索過程是從錨點(diǎn)pa出發(fā)，沿時(shí)間維重復(fù)如下步驟（初始j=1）：

① 向后搜索一個(gè)軌跡點(diǎn)pi=pa－j，判斷pa－j是否已經(jīng)超過GPS軌跡點(diǎn)序列Traj的起點(diǎn)，即判斷a-j是否小于0，若是，則最后一個(gè)滿足條件的軌跡點(diǎn)pas=pa－j+1=p0，后向搜索過程停止，否則執(zhí)行第②步。

② 判斷pa－j與錨點(diǎn)pa的距離是否大于距離閾值dth，即判斷d(pa,pa－j)是否大于dth，若是，則最后一個(gè)滿足條件的軌跡點(diǎn)pas=pa－j+1，后向搜索過程停止，否則執(zhí)行第③步。

③ j=j+1，轉(zhuǎn)第①步，繼續(xù)搜索。

（2）前向搜索

前向搜索是以軌跡點(diǎn)pa為錨點(diǎn)，沿時(shí)間維向前搜索與pa的距離小于或等于距離閾值dth的在時(shí)間上連續(xù)的所有軌跡點(diǎn)，直至最后一個(gè)滿足條件的軌跡點(diǎn)pae，即搜索滿足下列條件的軌跡點(diǎn)pi：

因此，前向搜索過程是從錨點(diǎn)pa出發(fā)，沿時(shí)間維重復(fù)如下步驟（初始j=1）：

① 向前搜索一個(gè)軌跡點(diǎn)pi=pa+j，判斷pa+j是否已經(jīng)超過GPS軌跡點(diǎn)序列Traj的終點(diǎn)，即判斷a+j是否大于|Traj|-1，若是，則最后一個(gè)滿足條件的軌跡點(diǎn)pae=pa+j-1=p|Traj|-1，前向搜索過程停止，否則執(zhí)行第②步。

② 判斷pa+j與錨點(diǎn)pa的距離是否大于距離閾值dth，即判斷d(pa,pa+j)是否大于dth，若是，則最后一個(gè)滿足條件的軌跡點(diǎn)pae=pa+j-1，后向搜索過程停止，否則執(zhí)行第③步。

③ j=j+1，轉(zhuǎn)第①步，繼續(xù)搜索。

（3）密度計(jì)算及候選生成

通過后向搜索和前向搜索，所有介于pas和pae之間的軌跡點(diǎn)pi(as≤i≤ae)即構(gòu)成了錨點(diǎn)pa的密度區(qū)間pa.interval = [pas,pae]，利用式（1）和式（2）即可計(jì)算pa的密度pa.density和時(shí)間跨度pa.timespan。

如果錨點(diǎn)pa的時(shí)間跨度小于時(shí)間閾值，即如果pa.timespan＜tth，則pa的密度區(qū)間pa.interval = [pas, pae]不可能是一個(gè)停留點(diǎn)，可以直接剪枝，否則pa.interval= [pas, pae]是一個(gè)候選停留點(diǎn)，將pa及pa.interval = [pas, pae]放入按密度降序排列的候選列表CL中，即CL={(pu, [pus,pue]), …, (pv, [pvs, pve])}滿足下列條件：

● (pa,[pas,pae])∈CL，pa.timespan≥tth；

● pu.density≥…≥pv.density。

在之后的停留點(diǎn)識(shí)別步驟中，將從候選列表CL中按密度從大到小的順序識(shí)別停留點(diǎn)。

4.1.2 算法描述

密度計(jì)算Computing-Density的算法描述如算法1所示。

算法1：密度計(jì)算Computing-Density。

輸入：GPS軌跡點(diǎn)序列Traj，距離閾值dth，時(shí)間閾值tth。

輸出：候選停留點(diǎn)列表CL。

步驟：

在算法1中，backwardSearching(pa,dth)和forwardSearching(pa, dth)實(shí)現(xiàn)前向搜索和后向搜索，CL.SortInsert(pa,[pas,pae])將候選停留點(diǎn)按密度降序插入候選列表CL中。

設(shè)GPS軌跡點(diǎn)序列的長(zhǎng)度為n，軌跡點(diǎn)密度區(qū)間的平均長(zhǎng)度為l。在算法1中，前向搜索和后向搜索的時(shí)間復(fù)雜性為O(n·l)，密度計(jì)算及候選生成的主要開銷是候選列表的排序，時(shí)間復(fù)雜性為O(nlbn)，通常l＜＜n，因此算法1的時(shí)間復(fù)雜性為O(nlbn)。

4.2 停留點(diǎn)識(shí)別

4.2.1 算法思想

候選列表CL中的候選停留點(diǎn)已經(jīng)滿足距離閾值和時(shí)間閾值，但是這些候選停留點(diǎn)的密度區(qū)間可能重疊，因此在停留點(diǎn)識(shí)別步驟中，將基于CL按密度從大到小迭代地進(jìn)行識(shí)別更新操作，得到不相交的停留點(diǎn)，直至CL為空。

（1）停留點(diǎn)識(shí)別及候選更新

因?yàn)楹蜻x列表CL中的候選停留點(diǎn)已按密度降序排列，所以停留點(diǎn)識(shí)別及候選更新過程如下。

① 從CL中選取當(dāng)前密度值最大的候選停留點(diǎn)，即選取CL中的第一個(gè)候選停留點(diǎn)pu= [pus, pue]，作為停留點(diǎn)sp= [pus, pue]。

② 根據(jù)當(dāng)前停留點(diǎn)sp=[pus, pue]，對(duì)于所有介于起點(diǎn)pus和終點(diǎn)pue之間的軌跡點(diǎn)pi，如果pi及其密度區(qū)間pi.interval = [pis,pie]在CL中，則將(pi, [pis, pie])從CL中刪除。

（2）軌跡點(diǎn)更新及候選更新

當(dāng)前停留點(diǎn)sp=[pus,pue]識(shí)別之后，還需更新所有受其影響的軌跡點(diǎn)的密度區(qū)間，進(jìn)而還需再次更新候選列表CL，更新過程如下。

① 對(duì)于CL中每個(gè)候選停留點(diǎn)pi=[pis,pie]，如果其與停留點(diǎn)sp = [pus, pue]相交，則縮小pi的密度區(qū)間pi.interval = [pis,pie]，即如果pus≤pie≤pue，則ie=us-1；如果pus≤pis≤pue，則is=ue+1。

② 對(duì)于CL中每個(gè)縮小的候選停留點(diǎn)pi=[pis,pie]，根據(jù)式（1）和式（2），重新計(jì)算其密度pi.density和時(shí)間跨度pi.timespan，如果其時(shí)間跨度小于時(shí)間閾值，即如果pi.timespan＜tth，則pi= [pis, pie]不再是一個(gè)候選停留點(diǎn)，可以剪枝，將(pi, [pas, pae])從CL中刪除；否則按其密度pi.density調(diào)整在CL中的位置。

4.2.2 算法描述

停留點(diǎn)識(shí)別Identifying-Staypoint的算法描述如算法2所示。

算法2：停留點(diǎn)識(shí)別Identifying-Staypoint。

輸入：候選停留點(diǎn)列表CL，時(shí)間閾值tth。

輸出：停留點(diǎn)集合SP。

步驟：

在算法2中，UpdatingOne(sp, CL)根據(jù)當(dāng)前停留點(diǎn)，完成候選列表的第一次刪除更新。UpdatingTwo(sp, CL, tth)根據(jù)當(dāng)前停留點(diǎn)和時(shí)間閾值，縮小受影響軌跡點(diǎn)的密度區(qū)間，完成候選列表的第二次刪除更新以及排序。SP.insert(sp)將當(dāng)前停留點(diǎn)插入停留點(diǎn)集合。

設(shè)候選列表中初始候選停留點(diǎn)數(shù)目為m，候選列表更新次數(shù)為k。在算法2中，候選列表每次更新的時(shí)間復(fù)雜性為O(m2)，每次排序的時(shí)間復(fù)雜性為O(mlbm)，因此算法2的時(shí)間復(fù)雜性為O(km2)。

4.3 討論

本文所提的基于密度的停留點(diǎn)識(shí)別方法是一種基于區(qū)分策略的方法，這類方法找到的停留點(diǎn)滿足定義4的條件，即這類方法找到的停留點(diǎn)是正確的。但是這類方法不能保證找到所有的停留點(diǎn)，即這類方法是不完備的。

定理1基于密度的停留點(diǎn)識(shí)別方法找到的停留點(diǎn)是正確的。

證明：（1）SPID方法找到的每個(gè)sp都是某個(gè)軌跡點(diǎn)pa的密度區(qū)間pa.interval =[pas, pae]

即sp滿足定義4中的條件1。

（2）SPID方法找到的每個(gè)sp都是從候選列表CL中選取的，而CL的初始生成以及迭代更新都對(duì)每個(gè)候選進(jìn)行了時(shí)間閾值測(cè)試，使 (pa,[pas, pae])∈CL,|pae.timepas.time|≥tth成立。即sp滿足定義4中的條件2。

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)設(shè)計(jì)

基于區(qū)分策略的停留點(diǎn)識(shí)別方法能保證找到的停留點(diǎn)是正確的，但是不能保證找到所有的停留點(diǎn)，因此設(shè)計(jì)了如下實(shí)驗(yàn)。

（1）實(shí)驗(yàn)?zāi)康?/p>

驗(yàn)證基于密度的停留點(diǎn)識(shí)別方法能否找到更多的停留點(diǎn)。

（2）數(shù)據(jù)集

實(shí)驗(yàn)采用的數(shù)據(jù)集是來自微軟亞洲研究院的GeoLife數(shù)據(jù)集。數(shù)據(jù)集采集了182名用戶從2007年4月份到2012年8月份的GPS軌跡，軌跡數(shù)目共計(jì)17621條，軌跡長(zhǎng)度共計(jì)1292951 km，軌跡持續(xù)時(shí)間共計(jì)20176 h。這些軌跡數(shù)據(jù)由不同GPS設(shè)備在不同采樣頻率下采集，91.5%的軌跡數(shù)據(jù)是在較高采樣頻率下采集的。

（3）對(duì)比方法

實(shí)驗(yàn)選取的對(duì)比方法是參考文獻(xiàn)[14,16]提出的兩個(gè)方法，分別以作者姓氏命名為L(zhǎng)i方法和Pavan方法。Li方法的基本思想是：首先以GPS軌跡點(diǎn)序列的起始點(diǎn)為錨點(diǎn)，沿時(shí)間維向前選擇滿足距離閾值的子軌跡，根據(jù)時(shí)間閾值判斷子軌跡是否構(gòu)成一個(gè)停留點(diǎn)。若是，則以子軌跡后面的軌跡點(diǎn)為新錨點(diǎn)；否則以錨點(diǎn)后面的軌跡點(diǎn)為新錨點(diǎn)，然后重復(fù)上述過程，直至整個(gè)軌跡點(diǎn)序列遍歷完成。Li方法是現(xiàn)有基于區(qū)分策略方法中表現(xiàn)最優(yōu)的方法[5]。但是Li方法僅考慮了時(shí)間連續(xù)的一個(gè)方向。Pavan方法在判斷子軌跡是否構(gòu)成停留點(diǎn)中增加了速度閾值的限定，以排除無意義的停留點(diǎn)。

5.2 實(shí)驗(yàn)結(jié)果

首先，對(duì)比了3種方法中距離閾值和時(shí)間閾值對(duì)停留點(diǎn)個(gè)數(shù)的影響；然后，進(jìn)一步分析了3種方法識(shí)別的停留點(diǎn)的差異。

5.2.1 閾值對(duì)于停留點(diǎn)個(gè)數(shù)的影響

實(shí)驗(yàn)對(duì)比了3種方法在不同距離閾值和時(shí)間閾值下的停留點(diǎn)個(gè)數(shù)。圖5（a）顯示了時(shí)間閾值tth=1800 s時(shí)，距離閾值對(duì)停留點(diǎn)個(gè)數(shù)的影響，圖5（b）顯示了距離閾值dth=200 m時(shí)，時(shí)間閾值對(duì)停留點(diǎn)個(gè)數(shù)的影響。tth=1800 s和dth=200 m是Li方法的最優(yōu)閾值。Pavan方法的結(jié)果均是在速度閾值為2 m/s的情況下得到的。

圖5 閾值對(duì)于停留點(diǎn)個(gè)數(shù)的影響

如圖5（a）所示，在絕大多數(shù)距離閾值情況下，SPID識(shí)別的停留點(diǎn)個(gè)數(shù)比對(duì)比方法多。當(dāng)距離閾值小于1250 m時(shí)，SPID和對(duì)比方法的停留點(diǎn)個(gè)數(shù)變化趨勢(shì)都是隨著距離閾值的增加而增加的。在距離閾值超過1250 m之后，對(duì)比方法識(shí)別的停留點(diǎn)個(gè)數(shù)變化呈現(xiàn)隨著距離閾值的增加而迅速下降的趨勢(shì)，而SPID方法則保持穩(wěn)定。對(duì)比方法識(shí)別的停留點(diǎn)個(gè)數(shù)下降的原因是較大的距離閾值使每次選擇的子軌跡變長(zhǎng)，并且不斷地對(duì)后續(xù)的子軌跡選擇產(chǎn)生影響，這種影響的累積使得一些空間和時(shí)間上鄰近的停留點(diǎn)被合并。而SPID方法由于從當(dāng)前密度最大的候選開始，迭代地進(jìn)行識(shí)別、更新，避免了這種合并。

如圖5（b）所示，在絕大多數(shù)時(shí)間閾值情況下，SPID方法和Li方法識(shí)別的停留點(diǎn)個(gè)數(shù)比較接近。SPID方法和對(duì)比方法識(shí)別的停留點(diǎn)個(gè)數(shù)都隨著時(shí)間閾值的增長(zhǎng)而下降。當(dāng)時(shí)間閾值超過21600 s（6 h）時(shí)，識(shí)別的停留點(diǎn)個(gè)數(shù)接近于0，這是因?yàn)橥Ａ魰r(shí)間超過6 h是很少見的。

從圖5還可以看出，在大多數(shù)閾值情況下，Pavan方法識(shí)別的停留點(diǎn)個(gè)數(shù)少于Li方法，這是因?yàn)槠湓谧R(shí)別過程中需要滿足對(duì)于速度閾值的限定，因此它過濾了不滿足速度閾值限定的停留點(diǎn)，比如用戶在公園里跑步時(shí)形成的不滿足速度閾值限定的停留點(diǎn)或者用戶在景點(diǎn)內(nèi)乘坐游覽車觀光時(shí)形成的不滿足速度閾值限定的停留點(diǎn)。速度閾值使得算法識(shí)別出的停留點(diǎn)更加規(guī)整，但被速度閾值過濾掉的停留點(diǎn)依然對(duì)研究用戶行為有參考價(jià)值。

5.2.2 不同方法的停留點(diǎn)比較

本節(jié)分析SPID方法能識(shí)別但對(duì)比方法不能識(shí)別的兩類停留點(diǎn)。

第一類停留點(diǎn)如圖6所示，在GPS軌跡中出現(xiàn)了“跳躍”。從圖6（a）所示的GPS子軌跡可以看出，軌跡點(diǎn)3095到軌跡點(diǎn)3096的時(shí)間跨度遠(yuǎn)大于相鄰軌跡點(diǎn)之間的時(shí)間跨度。從圖6（b）所示的軌跡點(diǎn)相對(duì)位置可以看出，軌跡點(diǎn)3095到軌跡點(diǎn)3096的距離也遠(yuǎn)大于相鄰軌跡點(diǎn)之間的距離。產(chǎn)生這種情形的原因可能是用戶從一個(gè)門進(jìn)入高樓或者地下建筑物，然后從另一個(gè)門出去，高樓和地下建筑物屏蔽了信號(hào)，使得這段軌跡產(chǎn)生了“跳躍”。在對(duì)比方法中，軌跡點(diǎn)3093、軌跡點(diǎn)3094和軌跡點(diǎn)3095會(huì)被依次選為錨點(diǎn)，由于它們與軌跡點(diǎn)3096的距離超過距離閾值，對(duì)比方法不能識(shí)別這個(gè)包含“跳躍”的停留點(diǎn)。而在SPID中，軌跡點(diǎn)3101會(huì)被選為錨點(diǎn)，并從兩個(gè)方向搜索，由于它與軌跡點(diǎn)3095和軌跡點(diǎn)3096的距離都小于距離閾值，從而可以識(shí)別這個(gè)包含“跳躍”的停留點(diǎn)。

第二類停留點(diǎn)如圖7所示，在GPS軌跡中出現(xiàn)了“暫時(shí)離開”。圖7（a）為SPID識(shí)別的停留點(diǎn)，圖7（b）和圖7（c）分別為對(duì)比方法識(shí)別的兩個(gè)停留點(diǎn)。事實(shí)上，圖7（a）的子軌跡是圖7（b）和圖7（c）子軌跡的連接。從圖7（a）可以看出，對(duì)比方法識(shí)別的停留點(diǎn)1的終點(diǎn)和停留點(diǎn)2的起點(diǎn)都與停留區(qū)域的中心相距較遠(yuǎn)，出現(xiàn)了“暫時(shí)離開”。在對(duì)比方法中，“暫時(shí)離開”使一個(gè)時(shí)間跨度較長(zhǎng)的停留點(diǎn)被識(shí)別成兩個(gè)在空間上重合、時(shí)間跨度較短的停留點(diǎn)。而在SPID中，由于從前向和后向兩個(gè)方向搜索密度區(qū)間，并根據(jù)密度大小識(shí)別停留點(diǎn)，從而可以識(shí)別這種包括“暫時(shí)離開”的停留點(diǎn)。

5.2.3 示例

某用戶的一段GPS軌跡點(diǎn)序列Traj見表1，距離閾值dth=100 m，時(shí)間閾值tth=300 s。

（1）密度計(jì)算

以軌跡點(diǎn)p220為例，展示后向搜索、前向搜索、密度計(jì)算及候選列表生成的過程。

● 后向搜索：初始j=1，因?yàn)閍-j=220-1=219＞0，d(p220, p219)=2.469＜dth=100，未達(dá)到停止條件，所以j:=j+1=2；重復(fù)此過程，直到j(luò)=11，因?yàn)閍-j=220-11=209＞0，d(p220, p209)=105.993＞dth=100，達(dá)到停止條件，所以后向搜索過程結(jié)束，軌跡點(diǎn)pas=p210作為錨點(diǎn)p220密度區(qū)間的起點(diǎn)。

● 前向搜索：初始j=1，因?yàn)閍+j=221＜|Tr aj|-1=409，d(p220,p221)=1.357＜dth=100，未達(dá)到停止條件，所以j:=j+1=2；重復(fù)此過程，直到j(luò)=38，因?yàn)閍+j=220+38= 258＜|Traj|-1=409，d(p220,p258)=102.781＞dth=100，達(dá)到停止條件，所以前向搜索過程結(jié)束，軌跡點(diǎn)pae=p257作為錨點(diǎn)p220密度區(qū)間的終點(diǎn)。

● 密度計(jì)算：密度值p220.density=257-210+1=48，時(shí)間跨度p220.timespan=pae.time- pas.time=3002。

● 候選列表生成：由于p220.timespan=3002＞tth=300，錨點(diǎn)及其密度區(qū)間(p220,[p210, p257])構(gòu)成一個(gè)候選停留點(diǎn)，將(p220,[p210, p257])按其密度值插入候選列表CL中的適當(dāng)位置。至此，錨點(diǎn)p220的密度計(jì)算過程結(jié)束。

當(dāng)對(duì)GPS軌跡點(diǎn)序列Traj中的所有軌跡點(diǎn)都計(jì)算密度后，可以得到按密度降序排列的初始候選列表CL，見表2。

（2）停留點(diǎn)識(shí)別

圖6 包含“跳躍”的停留點(diǎn)

圖7 包含“暫時(shí)離開”的停留點(diǎn)

表1 GPS軌跡點(diǎn)序列

表2 初始候選列表

表3 更新后的候選列表

對(duì)候選列表CL中的每個(gè)候選停留點(diǎn)進(jìn)行停留點(diǎn)識(shí)別、軌跡點(diǎn)更新。以第一個(gè)候選停留點(diǎn)(p220, [p210, p257])為例，展示停留點(diǎn)識(shí)別及候選列表更新、軌跡點(diǎn)更新及候選列表更新的過程。

停留點(diǎn)識(shí)別及候選列表更新：當(dāng)前候選列表CL中的第一個(gè)候選停留點(diǎn)(p220,＜p210,p257＞)已經(jīng)滿足停留點(diǎn)的條件，故構(gòu)成了一個(gè)停留點(diǎn)sp=(p220, ＜39.991304,116.332948＞, [2009-05-1808:29:09,2009-05-1809:19:11], [210, 257])。依次判定介于起點(diǎn)pus=p210和終點(diǎn)pue=p257之間的軌跡點(diǎn)，將出現(xiàn)在候選列表CL中的候選軌跡點(diǎn)p220、p221、p224、p223、p222、p225、p242、p241、p240、p238、p239、p237、p236、p235、p234、p233、p229、p227、p232、p231、p228、p230、p226及其密度區(qū)間從CL中刪除。

軌跡點(diǎn)更新及候選列表更新：當(dāng)前候選列表CL中沒有候選軌跡點(diǎn)的鄰域與p220的密度區(qū)間[210, 257]相交，故CL中的候選軌跡點(diǎn)及其密度區(qū)間不需更新，CL也不需要更新。在對(duì)候選停留點(diǎn)(p220, [p210,p257])進(jìn)行判定之后，候選列表CL更新后的結(jié)果見表3。

在經(jīng)過3次迭代之后，候選列表CL變?yōu)榭?，其中，大部分候選停留點(diǎn)由于與停留點(diǎn)相交，被更新策略刪除了。最終得到的停留點(diǎn)集合見表4。

表4 停留點(diǎn)集合

6 結(jié)束語(yǔ)

本文在考慮軌跡點(diǎn)時(shí)空聚集的同時(shí)，考慮了軌跡點(diǎn)的時(shí)間連續(xù)性和方向性，提出了一種新的基于密度的識(shí)別停留點(diǎn)方法。首先，以錨點(diǎn)為中心，沿時(shí)間維從向后和向前兩個(gè)方向搜索時(shí)間連續(xù)且滿足距離閾值的軌跡點(diǎn)，形成錨點(diǎn)的密度區(qū)間；然后，根據(jù)時(shí)間閾值生成候選集，再根據(jù)密度迭代地在候選集中進(jìn)行識(shí)別、更新操作，得到停留點(diǎn)集；最后，設(shè)計(jì)有效的算法，并通過實(shí)驗(yàn)驗(yàn)證了新方法是有效的，可以識(shí)別基準(zhǔn)方法不能識(shí)別的兩類停留點(diǎn)。在未來的工作中，將進(jìn)一步研究停留點(diǎn)的語(yǔ)義標(biāo)注以及基于具有語(yǔ)義的停留點(diǎn)研究位置服務(wù)。