周 洋，楊 超

(同濟(jì)大學(xué)道路與交通工程教育部重點實驗室，上海201804)

0 引言

傳統(tǒng)的居民出行調(diào)查采用路邊問卷、家庭上訪、電話咨詢等方式獲取居民出行數(shù)據(jù)，具有成本高、反饋差、錯誤多等缺點.隨著智能手機(jī)快速普及與功能擴(kuò)展，精確的定位功能、豐富的感應(yīng)器模塊，為長時期、大規(guī)模、被動式的城市居民出行調(diào)查提供了硬件基礎(chǔ)，不僅獲得大量高精度時空軌跡數(shù)據(jù)，同時極大減輕了被調(diào)查者的負(fù)擔(dān)[1].然而無法直接獲取居民出行的起訖點、出行方式、出行目的等信息，成為了智能手機(jī)調(diào)查技術(shù)發(fā)展的主要瓶頸.

停駐點表現(xiàn)為空間停留、時間消耗、滿足某種需求，出行側(cè)重于個體借助某種交通方式從一個停駐點移動到下一個停駐點.停駐點識別是推測出行方式與出行目的的重要基礎(chǔ)，目前研究主要有：①基于路網(wǎng)信息，即以道路網(wǎng)擬合出行，通過計算密集軌跡點與道路距離來檢驗停駐點[2].②基于運動特征，即以速度趨近于0的軌跡點判斷停留[3]，或以方向變化大、重復(fù)路段長等條件判斷接送人的活動[4].③基于地理語義，Alvares等提出SMoT模型，將個體常去的興趣位置編碼為地理幾何實體，以軌跡點在實體內(nèi)連續(xù)時長判斷停駐點[5]；Palma提出了CB-SMoT算法，引入基于速度的時空聚類方法尋找軌跡中的重要停留，改進(jìn)了SMoT對興趣位置依賴的不足[6].④基于密度聚類，Ester等提出DBSCAN，設(shè)定Eps鄰域與MinPts兩個參數(shù)，以核心點為基礎(chǔ)，以密度可達(dá)為歸類方式，向外不斷擴(kuò)展相連搜索簇[7]；Birant等用Eps1定義空間距離，Eps2表征非空間距離，提出時空聚類的ST-DBSCAN算法[8]；Tran等將DBSCAN中Eps改為時間線性鄰域，將MinPts改為最小時長，提出TrigDBSCASN算法[9]；Gong等引進(jìn)方向變化系數(shù)、軌跡中異常點比例，針對停駐點的時間序列限制與方向變化限制，提出C-DBSCAN算法[10]；向隆剛等提出停留指數(shù)，從鄰域內(nèi)點數(shù)目、空間距離、逗留時間上反映軌跡的時空聚集程度[11]；何源浩等結(jié)合DBSCAN與地理語義，通過密度聚類提取簇，再根據(jù)簇中心反向地理編碼語義合并[12].

現(xiàn)有研究的不足：GIS信息與地理語義額外增加了識別負(fù)擔(dān)，不便于大量個體軌跡數(shù)據(jù)的處理；運動特征閾值設(shè)定缺乏科學(xué)依據(jù)；現(xiàn)有聚類算法對核心點搜索方式、簇合并方法研究不足，對于空間位置發(fā)散、路徑重疊等較難識別的軌跡缺乏分析.此外在方法上，停駐點數(shù)目、時空信息存在較大誤差；驗證上，未能獲得準(zhǔn)確的驗證數(shù)據(jù).本文利用課題組自主開發(fā)的居民出行調(diào)查系統(tǒng)獲取出行軌跡與驗證日志；在DBSCAN的基礎(chǔ)上提出一種新的時空聚類算法AT-DBSCAN(Adjacent Temporospatial DBSCAN)，以固定長度的滑窗搜索核心點，以時空鄰近條件定義簇間距離，以密度大小次序進(jìn)行簇合并，識別GPS軌跡中的停駐點；提出出行次數(shù)一致性、出行起止時刻誤差、停駐點時長誤差、停駐點中心偏移距離4項評價指標(biāo)，驗證算法的準(zhǔn)確性.

1 居民出行調(diào)查系統(tǒng)

最早美國采用紙筆表格(PAPI)記錄的方式開展了全國范圍內(nèi)的個人與家庭出行調(diào)查(NPTS/NHTS)，隨后產(chǎn)生了計算機(jī)輔助的電話調(diào)查(CATI)和自助調(diào)查(CASI)等技術(shù)[13].1997年GPS設(shè)備首次應(yīng)用于出行軌跡采集[14]，開啟了被動式調(diào)查的先河.最近十年，智能手機(jī)性能的提升與大數(shù)據(jù)技術(shù)的發(fā)展為出行調(diào)查帶來了新的契機(jī)，研究者開發(fā)了一系列出行信息采集系統(tǒng)，包括新加坡Future Mobility Survey(FMS)[1]、美國的 SmarTrAC[15]、北京大學(xué)的定位服務(wù)調(diào)查系統(tǒng)[16]、西南交通大學(xué)的傳感器數(shù)據(jù)采集軟件[17]、東南大學(xué)的TransGPS[18]等.

本文使用課題組自主開發(fā)的居民出行調(diào)查系統(tǒng)進(jìn)行數(shù)據(jù)采集[19].系統(tǒng)包括用戶端、服務(wù)器端、網(wǎng)頁端，如圖1所示.用戶在初次登錄智能手機(jī)App時，需要注冊并填寫個人和家庭信息；打開App時，開啟GPS軌跡采集，采集頻率為1Hz；關(guān)閉App后，系統(tǒng)自動或人工上傳數(shù)據(jù)至云端數(shù)據(jù)庫.服務(wù)器端部署了數(shù)據(jù)處理和分析模塊，基于規(guī)則判斷軌跡中的停駐點、出行方式和出行目的.網(wǎng)頁端可視化算法的識別結(jié)果，提供用戶檢驗并修正出行日志.與傳統(tǒng)數(shù)據(jù)采集軟件不同，此系統(tǒng)中服務(wù)器端的內(nèi)置算法能夠獲得停駐點準(zhǔn)確的數(shù)量、起止時間、空間位置.

2014年4月在上海市征集了包括企事業(yè)單位人員、大學(xué)生、中小學(xué)生等22位調(diào)查者，開展了連續(xù)兩周的出行調(diào)查，平均每人調(diào)查5天，一天的出行軌跡數(shù)據(jù)平均包含4萬～5萬個位置點.

2 數(shù)據(jù)預(yù)處理

2.1 出行日志

出行日志記錄每一次出行的出發(fā)時刻、到達(dá)時刻、交通方式、起點文本地址、終點文本地址、終點經(jīng)緯度、出行目的.設(shè)定以下假設(shè)條件，反推停駐信息，結(jié)果如表1所示.

(1)假設(shè)當(dāng)天第1個停駐點的起始時刻為GPS軌跡中第1個記錄點的時間；

(2)假設(shè)當(dāng)天最后1個停駐點的終止時刻為GPS軌跡中最后1個記錄點的時間；

(3)假設(shè)停駐點的終止時刻與下一次出行的起始時刻之間沒有時間間隔；

(4)假設(shè)出行的終止時刻與下一次停駐點的起始時刻之間沒有時間間隔.

圖1 居民出行調(diào)查系統(tǒng)Fig.1 Individual travel survey system

表1 出行日志中停駐點與出行信息Table 1 Anchor and travel in trip diary

2.2 軌跡數(shù)據(jù)

GPS軌跡數(shù)據(jù)的質(zhì)量直接受到定位信號的影響，在地鐵內(nèi)會存在信號被屏蔽而無軌跡點記錄的情況.本文所采用預(yù)處理的方式是：①檢驗時間標(biāo)簽是否重疊、經(jīng)緯度是否位于調(diào)查區(qū)域內(nèi)；②將大地坐標(biāo)系下的經(jīng)緯度轉(zhuǎn)換為平面坐標(biāo)值；③計算速度、加速度等變量，過濾信號漂移等異常點；④若存在軌跡點缺失，采用線性插值法進(jìn)行修補(bǔ)，使得相鄰軌跡點時間間隔為1 s.

3 AT-DBSCAN算法

3.1 基本定義

定義1軌跡.由一連串包含時空信息的記錄點組成的集合{pi}，每個記錄點包含時空坐標(biāo)，其中xi,yi∈R.

定義2時空鄰近.對于相鄰的記錄點{pi,pi+1}，若滿足pi與pi+1的歐式距離在空間鄰域Eps范圍內(nèi)，則兩點時空鄰近；對于相鄰的簇{Cj,Cj+1}，若滿足Cj終止時刻到Cj+1起始時刻的間隔小于時間鄰近閾值I，且兩簇的中心歐式距離在空間鄰域Eps范圍內(nèi)，則兩簇時空鄰近.

定義3核心點.以記錄點pi為中心，搜索k長度的滑窗中的記錄點{pS,…,pT}，其中k為奇數(shù)，S,T分別為首尾點標(biāo)號，當(dāng)i＜(k-1)/2時，S=1,T=k；當(dāng)(k-1)/2＜i≤M-(k-3)/2 時，S=i-(k-1)/2,T=i+(k-1)/2；當(dāng)i＞M-(k-3)/2時，S=M-k+1,T=M.若pi與滑窗內(nèi)記錄點的距離小于空間鄰域的數(shù)目大于MinPts，則pi為核心點.

定義4簇密度.設(shè)簇Cj中包含J個記錄點，其中任意兩點歐式距離組成矩陣[dj]J×J，則簇密度DSj為簇內(nèi)記錄點數(shù)目與簇內(nèi)任意兩點最大距離，即DSj=J/max(dj).

定義5偽停駐點.簇Cj與其相鄰簇{Cj,Cj+1}之間不滿足時空鄰近條件，且簇Cj內(nèi)點數(shù)目小于停駐點最小時長DU，則Cj為偽停駐點.

3.2 運算步驟

算法思路是基于核心點集形成原始簇，從時空維度定義簇間距離，根據(jù)密度大小順序檢驗，對時空鄰近的簇進(jìn)行合并，從而形成初始停駐點，應(yīng)用最小時長閾值過濾偽停駐.

Step 1設(shè)置算法參數(shù).包括搜索長度k、時間鄰近閾值I，空間鄰近閾值Eps、核心點判別最小數(shù)目MinPts、停駐點最小時長DU.

Step 2初始化標(biāo)號.軌跡中所有點初始標(biāo)記Label=0，停駐點編號ClustID=1.

Step 3搜索核心點.逐個檢驗軌跡中記錄點pi，分別計算k長度滑窗內(nèi)記錄點的歐式距離，若小于Eps的點數(shù)目大于MinPts，則更改點pi標(biāo)號為Label=-1.

Step 4初始簇.相鄰的核心點組成的集合形成初始簇Cj，并計算每個簇的密度DSj與中心坐標(biāo)，此時所有簇內(nèi)點為初始標(biāo)號.

Step 5簇合并.從密度最大且Label=-1的初始簇Cn開始，檢驗相鄰且標(biāo)號Label=-1的簇{Cn-1,Cn}，若滿足時空鄰近條件則合并，重新計算新簇密度與簇中心，并進(jìn)入下一輪檢驗；若相鄰簇Label≠0或Cn與相鄰簇不滿足時空鄰近，則更改簇內(nèi)記錄點編號Label=ClustID，并更新ClustID=ClustID+1，直到所有簇標(biāo)號Label＞0.

Step 6過濾偽停駐點.更改持續(xù)時長小于DU的停駐點標(biāo)號Label=0.

Step 7停駐點輸出.計算停駐點起止時刻與中心坐標(biāo)，輸出識別結(jié)果.

3.3 參數(shù)說明

(1)滑窗長度k與最小數(shù)目閾值MinPts.

滑窗長度決定核心點的檢驗范圍，k值越大，核心點檢驗越準(zhǔn)確；最小數(shù)目反映滑窗內(nèi)的點在空間上的聚集程度，MinPts越大，集聚的點越多.其中MinPts＜k，MinPts越接近于k，核心點集構(gòu)成停駐點的可能性越大.

(2)時間間隔I與空間距離Eps.

I與Eps分別作為時間鄰近與空間鄰近的參數(shù)閾值，是檢驗核心點、判斷簇合并的重要條件.在算法中，Eps對簇合并的影響更大，Eps越小，識別的停駐點位置越精確，卻容易導(dǎo)致簇被切分成多段.

(3)停駐點最小時長DU.

對于具有集聚特征而持續(xù)時長較短的簇，如交叉口等候信號燈、公交車進(jìn)站、高峰期路段擁堵等停留，可通過設(shè)定DU消除，以往研究中DU普遍取120 s[20].

4 算法驗證

4.1 評價指標(biāo)

目前使用的主要評價指標(biāo)包括查全率、查準(zhǔn)率、錯誤率等，其計算公式如下.

(1)查全率.

正確識別的停駐點數(shù)目Ncorrect與真實數(shù)目Nreal的比值，即

(2)查準(zhǔn)率.

正確識別的停駐點數(shù)目Ncorrect與識別數(shù)目Nidentified的比值，即

(3)錯誤率.

識別出的停駐點數(shù)目Nidentified與真實數(shù)目Nreal之差除以Nreal，即

實際上，查全率、查準(zhǔn)率、錯誤率等以數(shù)目反映識別準(zhǔn)確性的指標(biāo)存在以下問題(圖2)：①無法分清真實停駐點被錯誤切分或合并的情況；②易受出行中等候信號燈、路段擁堵等偶然停留的干擾；③識別的停駐點可能存在時間錯位與伸縮，不利于后期出行方式與出行目的的識別.

圖2 傳統(tǒng)指標(biāo)的缺陷Fig.2 Drawbacks of conventional evaluation indexes

本文中出行日志的特殊性在于服務(wù)器端部署了基于規(guī)則的出行模式識別算法，能夠準(zhǔn)確獲取停駐點時空信息.為進(jìn)一步評價所提取停駐點的時空信息，提出如下指標(biāo)：

(1)出行次數(shù)一致性TripNumFit.

對于1天的軌跡數(shù)據(jù)，若識別的出行次數(shù)與真實的出行次數(shù)相等，則為1，否則為0.

(2)出行起止時刻差值TimeDiff.

對于某一次出行，預(yù)測的起始時刻tps與終止時刻tpe分別與日志記錄的起始時刻tts與終止時刻tte之差的絕對值，反映識別出行的時間錯位程度.

(3)停駐持續(xù)時長差值DUDiff.

所有預(yù)測的停駐持續(xù)時長DUpk與日志記錄的停駐持續(xù)時長DUtk之差的平均值，描述識別的停駐點在時間上的拉縮程度.

(4)活動位置偏離距離DistP.

所有預(yù)測的停駐中心位置Ppc與相對應(yīng)的真實位置Ptc偏離距離的平均值，描述停駐點在空間上的偏移程度.

4.2 驗證數(shù)據(jù)

在過濾全日記錄不完整、信號屏蔽嚴(yán)重的軌跡之后，選取了反饋日志準(zhǔn)確、GPS定位精度較高的55條數(shù)據(jù)(包含186個停駐點)對算法進(jìn)行驗證，并具體分析2條代表性的軌跡，其特征如表2所示.

表2 軌跡特點Table 2 Characteristics of trajectories

4.3 結(jié)果分析

(1)特殊軌跡結(jié)果.

設(shè)置參數(shù)k=61,I=30,Eps=30,MinPts=30,DU=120，軌跡時空圖如圖3所示，對應(yīng)的評價指標(biāo)如表3所示.可以看出，2條軌跡的識別結(jié)果與真實的出行起止時刻誤差均在30 s內(nèi)，停駐時長誤差均在20 s內(nèi)，停駐偏移位置誤差均在15 m以內(nèi).面對明顯振擺或路徑重疊的復(fù)雜軌跡，本文算法具有較好的泛化能力.

圖3 識別的停駐點—出行時空圖Fig.3 Temporospatial diagrams of identified anchor and travel

表3 軌跡I和II停駐點識別結(jié)果評價Table 3 Evaluation of the anchors identification in trajectory I and II

(2)綜合識別結(jié)果.

為評價綜合準(zhǔn)確率，將評價指標(biāo)各劃分為5個等級，即時間維度的TimeDiff與DUDiff分成＜30、[30,60)、[60,120)、[120,300)、≥ 300，單位為 s；空間維度的DistP分為＜10、[10,30)、[30,50)、[50,100)、≥ 100，單位為m.

55條數(shù)據(jù)的識別結(jié)果如圖4所示，其中78%的停駐點中心偏離真實位置在10 m以內(nèi)，20%的偏離誤差在[10,30)m內(nèi)；33%的停駐點時長與真實時長相差在30 s以內(nèi)，27%相差在[30,60)s內(nèi)，31%相差在[60,120)s內(nèi)；出行起止時刻有7%相差在30 s以內(nèi)，42%相差在[30,60)s內(nèi)，27%相差在[60,120)s內(nèi)，22%相差在[120,300)s以內(nèi).總體而言，識別的停駐點中，98%的中心誤差在30 m以內(nèi)，100%的活動持續(xù)時長誤差在5 min以內(nèi)，98%的出行起止時刻誤差在5 min以內(nèi).因此本文所提出的基于時空聚類的停駐識別方法能夠非常準(zhǔn)確地識別一天中停駐點的時空信息.

圖4 綜合準(zhǔn)確率Fig.4 Comprehensive accuracy

5 結(jié)論

本文基于居民出行調(diào)查系統(tǒng)獲取的個體GPS軌跡數(shù)據(jù)，提出了一種時空聚類的停駐識別方法(AT-DBSCAN)，通過設(shè)定時空間鄰近等控制參數(shù)，能夠準(zhǔn)確地識別停駐點，并對室內(nèi)活動、定位飄移、路徑重合程度高等復(fù)雜情況具有較好的泛化能力.同時，結(jié)合個體軌跡數(shù)據(jù)的特征，提出了算法精度評價指標(biāo).運用此算法識別了55條的出行數(shù)據(jù)，得到所有停駐點持續(xù)時長誤差在5 min內(nèi)，98%的出行起止時刻誤差在5 min內(nèi)，98%的停駐點中心偏離誤差在30 m內(nèi).此方法提升了停駐點識別的效率與準(zhǔn)確性，能夠校正傳統(tǒng)日志中出行時刻、活動位置等信息，為出行方式與出行目的識別奠定了重要基礎(chǔ).

文中處理信號缺失的軌跡，先采用線性插值法進(jìn)行修補(bǔ)，再運用時空聚類算法識別停駐點.對于軌跡端點相距較遠(yuǎn)的長時缺失難以得到可信的結(jié)果，可考慮結(jié)合個體的居住與工作地址、頻繁活動的位置等進(jìn)一步分析.