基于最小覆蓋圓時空聚類算法的出行軌跡停駐點識別

張小佳， 孫然然， 李曉璐， 趙 暉， 張 彭， 朱廣宇*

(1.北京交通大學綜合交通運輸大數據應用技術交通運輸行業重點實驗室， 北京 100044；2.北京交通發展研究院，北京 100073； 3.交通運輸部規劃研究院， 北京 100028)

對居民出行行為的研究有助于提取居民出行規律、分析交通問題成因、確定合理的規劃方案。20世紀90年代以來，GPS軌跡數據在居民出行行為分析中得到廣泛應用[1-2]?；贕PS數據的出行行為研究包括出行路徑選擇建模[3]、出行方式選擇建模[4]、目的地選擇建模[5]、地理興趣點挖掘[6]等諸多方面。 GPS軌跡點具有位置精度高、時間信息準確、數據量豐富等優點，但由于其并不直接包含用戶出行方式和出行目的信息，在出行行為分析前，需從GPS 點數據中識別出行方式和出行目的。GPS軌跡點數據通常記錄用戶至多一天的完整出行鏈信息，基于GPS軌跡點數據進行用戶出行方式與出行目的推斷的一個重要前提是將出行鏈分段為多個單次出行[2]。根據出行者運動狀態，軌跡數據可劃分為出行段與停留段，每一完整出行信息由起始停留段、出行段與終止停留段構成，由于停留段通常具有速度趨近于0、軌跡點分布集中、停駐時間較長等特征，因此可通過確定停留段完成出行鏈劃分。通過出行段軌跡速度、加速度、出行路徑等數據并結合出行者社會屬性、地理信息數據庫可推斷出行方式[7-10]。對停留段軌跡結合周圍土地利用信息、POI(point of interest)信息、出行者社會屬性等可推斷用戶出行目的[9, 11-12]。因此，停留段識別已成為出行方式與出行目的推斷的重要基礎。由于用戶在停留段位置較固定，因此使用停留段軌跡中心點表示停留位置，稱之為停駐點。

現有研究已提出多種停駐點識別算法。針對車載GPS設備采集到的軌跡點，通常使用速度閾值和停駐時間閾值識別停駐點[13-15]。在基于手持GPS設備(包括含有GPS采集功能的智能手機)的研究中，由于用戶停駐點多位于室內，GPS信號弱導致的軌跡點漂移、軌跡點缺失現象使得基于速度閾值的判斷方法難以有效識別停駐點，研究多采用聚類算法進行停駐點識別。文獻[16]提出基于速度的時間聚類法與基于速度的速度聚類法兩種方法進行停駐點識別，其中基于速度的速度聚類法適用于因出入室內建筑或其他原因引起軌跡點采樣頻率不等、數據缺失較嚴重的軌跡數據。文獻[17]提出了一種同時考慮時空特性的交互式聚類方法用于停駐點識別，該方法能夠有效識別因GPS信號弱所引起的軌跡點漂移條件下可能被隱藏的停駐點。文獻[18]提出了一種時空聚類算法用于手機信令數據中停駐點識別，該算法首先根據軌跡點密度確定核心點，鄰近核心點形成初始類簇。隨后將鄰近類簇進一步合并，最后根據最小駐留時間過濾掉偽停駐點，剩余類簇中心點為所推斷停駐點。相較于其他基于密度的聚類算法，該時空聚類算法具有計算效率高、準確性高、對異常軌跡點不敏感等優點，并能解決傳統基于密度聚類中的軌跡重疊問題。

時空聚類停駐點識別算法的核心步驟為初始類簇的確定，在文獻[18] 中研究基礎上，提出了一種基于最小覆蓋圓的時空聚類算法，用于手持GPS設備采集數據的停駐點識別。通過停駐區域范圍閾值、停駐時間閾值、近鄰類簇最大間隔時間、近鄰類簇最大間隔距離四個參數進行停駐點識別算法調優。針對停駐點識別效果評價，提出了基于停駐點識別精度的查全率與查準率指標。

1 數據采集及預處理

1.1 GPS數據采集

非車載GPS軌跡數據的采集目前主要包括手持式GPS設備和安裝特定采集軟件并支持GPS模塊的智能手機兩種方式。基于智能手機的采集方式具有成本低、攜帶方便等優點，但同時也存在續航時間短、精度較低等缺點，手持式GPS設備具有采樣頻率設置多元化、數據采集導出便捷、精度高等優點[2]。表1所示為GPS軌跡點基本格式，其中PDOP(position dilution of precision)為位置精度因子，因采集設備差異，導出數據中部分字段可能并不一致。為驗證研究方法的有效性，除GPS軌跡數據外，通常需要出行者在完成一天出行后借助出行軌跡地圖來回憶并填寫出行日志。出行日志包括出行起止時間、出行方式以及出行目的，其基本格式如表2所示。

1.2 GPS數據預處理

GPS數據位置精度高，但受冷啟動、溫啟動以及樹木、建筑物遮擋等因素可能造成信號缺失和信號噪聲現象，從而導致在設備開機啟動階段、出行起始階段及停駐階段的位置點缺失、位置點漂移[2]。針對位置點漂移問題，可通過過濾衛星數量小于3或HDOP(horizontal dilution of precision)大于5的位置點進行位置點過濾[19]。對于位置點缺失問題，可通過插值方式進行填充，但應注意到若缺失時間較長，則插值得到的位置點可信度較低[18-19]。

表1 部分原始GPS數據

表2 出行日志部分數據

2 基于最小覆蓋圓時空聚類算法的停駐點識別

針對手持GPS設備采集軌跡數據，基于已有研究，提出最小覆蓋圓時空聚類算法用于停駐點識別。該算法可有效處理聚類過程中軌跡重合度高、軌跡漂移等問題。

2.1 定義

定義1軌跡：由包含時空信息的位置點按時序排列構成的位置序列數據P={pi}(i=1,2,…,n)。每一位置點包括經緯度坐標及時間戳三個基本信息，記作pi=(loni,lati,ti) 。后文算法描述中，軌跡也稱為軌跡點類簇。

定義3軌跡范圍：對于一系列軌跡點構成的軌跡tra={pi}(i=k,k+1,…,k+m)，軌跡范圍取包含所有軌跡點的近似最小覆蓋圓，近似最小覆蓋圓Sc為以軌跡中心為圓心，半徑r=max{dis(center,ps)}(s∈{k,k+1,…,k+m}),其中dis( )為兩點空間距離計算函數。

定義4近鄰軌跡：對于兩條軌跡：tra1={pi}(i=k,k+1,…,k+m，tra2={pj},j=k+l,k+l+1,…,k+l+s;l>m)、若兩軌跡中心距離dis(center1,center2) 小于距離閾值mdist且軌跡時間間隔tk+l-tk+m小于時間閾值mdura,則軌跡tra1、tra2互為近鄰。

定義5停駐軌跡：受信號噪聲影響，用戶在停留時段位置并非固定在同一位置點，而是圍繞在某位置中心附近分布，停留時段位置點構成的軌跡稱之為停駐軌跡。

定義6停駐點：為確定停留時段具體停駐位置點，使用停駐軌跡中心估計用戶實際停駐位置，稱該位置點為停駐點。

2.2 使用最小覆蓋圓時空聚類算法識別停駐點

基于最小覆蓋圓時空聚類算法的停駐點識別流程如下：

(1)基于給定圓形停駐區域范圍閾值將完整軌跡切分為連續的軌跡點類簇，使得每一軌跡類簇范圍最大且半徑不超過范圍閾值。若上一軌跡類簇點為Pi={pr,pr+1,…,ps}，對于當前類簇Pi+1={ps+1,ps+2,…,ps+k}，其類簇范圍對應半徑小于范圍閾值，且類簇P′i+1={ps+1,ps+2,…,ps+k+1}范圍對應的半徑大于范圍閾值，則類簇Pi+1={ps+1,ps+2,…,ps+k}范圍達到最大。

(2)基于停駐時間閾值對類簇進行初步過濾，僅保留停駐時長大于1/2停駐時間閾值的軌跡類簇。

(3)遞歸合并鄰近類簇。若兩相鄰類簇間隔時間小于間隔時間閾值且間隔距離小于間隔距離閾值，則進行類簇合并，合并后類簇由相鄰類簇所有軌跡點組成。

(4)基于停駐時間閾值過濾合并后類簇，僅保留停駐時長大于停駐時間閾值的軌跡類簇。

2.3 算法參數調整

最小覆蓋圓時空聚類算法共包括4個可調整參數，分別為停駐區域范圍閾值Tdist、停駐時間閾值Tdura、近鄰類簇最大間隔距離mdist、近鄰類簇最大間隔時間mdura。4個參數相互關聯，共同決定停駐點識別結果。

2.3.1 停駐區域范圍閾值

停駐區域范圍閾值決定初始類簇的劃分粒度。較小的范圍閾值能夠更精準地確定停駐起始時刻，但也容易導致一個完整的停留時段被割裂為多個停留時段。當停駐范圍過大時，最終識別得到的停駐時段通常包含更多的非停留時段軌跡點。

2.3.2 停駐時間閾值

由于用戶在停駐時段內速度減緩且運動方向多變，因此軌跡點范圍大小相同的多個類簇，包含停駐時段的類簇其持續時間通常要大于不包含停駐時段的類簇。因此，可基于停駐時間閾值對類簇進行過濾。最小覆蓋圓時空算法中包含兩次基于時間閾值的類簇過濾。第一次使用停駐時間閾值的1/2大小進行初步過濾，第二次使用停駐時間閾值對合并后類簇進行最終過濾，確定停駐點。停駐時間閾值的選擇通常要考慮到停駐區域范圍閾值的大小，當增大停駐區域范圍閾值時，要合理增加停駐時間閾值來有效過濾不包含停駐時段的類簇?？紤]當停駐區域范圍閾值為120 m(圓形范圍半徑)，停駐時間閾值設置為300 s。若增大停駐區域范圍閾值為500 m，則停駐時間閾值也應合理增加，否則部分非停駐時段軌跡點類簇可能無法被成功過濾。

2.3.3 近鄰類簇最大間隔距離

在類簇劃分時，因信號原因產生的異常軌跡點可能會偏移正常軌跡點較遠距離，導致一個連續的停駐時段被切分為多個類簇。因此在類簇切分并完成初步過濾后，需進行類簇合并。近鄰類簇最大間隔距離越大，多個相鄰類簇更可能被合并為一個類簇。

2.3.4 近鄰類簇最大間隔時間

類簇合并不僅需滿足空間間隔，同樣需考慮時間間隔?？紤]如下場景，某學生從宿舍出發繞校園跑步隨后返回宿舍，此過程包含兩個停駐點，均為其宿舍。當完成類簇劃分及初步過濾后，兩個停駐時段對應的類簇被保留下來，此時若僅依據最大間隔距離進行類簇合并，則兩個類簇可能被錯誤合并為一個類簇，若進一步判斷類簇間隔時間，間隔時間大于最大間隔時間，則不進行類簇合并，此時可正確識別兩個停駐時段。

2.4 停駐點識別評價指標

為驗證所設計停駐點識別算法有效性，需確定合適的計算指標對識別結果進行檢驗。停駐點識別算法有效性通常采用查全率和查準率進行衡量[20-21]。查全率與查準率指標主要應用在類別預測研究中，若樣本預測類別與其真實類別相同，則預測正確，反之預測錯誤。在停駐點識別研究中，使用0～1變量無法反映當前停駐點識別結果的有效精度，因此本文提出停駐點識別精度指標(0～1連續變量)，使用基于停駐點識別精度的查全率與查準率指標評價算法有效性。

對識別停駐時段tra={pi,pi+1,…,pi+k}，其對應識別停駐點為pstop，為計算其識別精度，首先選擇起始時刻與當前識別停駐時段起始時刻最接近的真實停駐時段作為其對應的真實停駐時段，記為tra′={pj,pj+1,…,pj+s}，其停駐點記為p′stop。若當前停駐點pstop落入軌跡tra′范圍內，則記當前識別停駐時段tra為正確識別停駐時段，反之為錯誤識別停駐時段。若當前識別停駐段時段為錯誤識別停駐時段，其精確度記為0；反之，其精確度為起止時刻精確度ptime-diff與停駐點精確度pdist平均值，計算公式為

(1)

(2)

(3)

式中：Mtime-diff、Mdist分別為最大距離偏差與最大時刻偏差，其值可根據多次算法識別結果進行取值?；诿恳蛔R別停駐時段的精確度，當前識別結果的查全率R(recall)與查準率P(precision)計算公式為

(4)

(5)

式中：Np、Nr分別代表識別停駐時段個數與真實停駐時段個數。

3 實例分析

3.1 數據介紹

為驗證所提算法有效性，使用實際軌跡點數據及出行日志數據對算法進行檢驗。研究共招募15名志愿者，每位志愿者攜帶GPS設備UniStrong G120-BD進行了為期3～5 d不等的調查。每位志愿者活動范圍在其所在居住點周圍20 km范圍內，每個人1 d的出行軌跡包含大約10 000個位置點。除通過隨身攜帶GPS采集器采集每日的出行軌跡外，參與者需依靠GPS設備的路徑顯示功能，填寫其實際出行日志，用于檢驗后續停駐點識別算法效果。實驗采集GPS數據格式和出行日志數據格式見表1和表2。

3.2 停駐點識別

為展示停駐點識別具體結果，選擇某一軌跡進行詳細說明。該軌跡點為2019年3月29日生成，共包含9 923個軌跡點，軌跡信息如圖1所示，表3為該條軌跡對應出行日志信息。分析表3出行日志信息可以發現，在G-H段等候公交車時間較短，J時刻步行結束后直接乘坐出租車出發，因此在這兩個換乘過程中不包含停駐點。該軌跡共對應3個停駐時段，分別為B-C段在公寓樓停駐、D-E段在圖書館停駐以及F-G段在食堂停駐。使用最小覆蓋圓時空聚類算法對該軌跡中停駐點進行識別，對停駐點范圍半徑、停駐時間閾值、近鄰類簇間隔距離、近鄰類簇間隔時間參數取值進行多次調優，結果發現，在一系列參數取值組合中，當參數取值分別為60 m、600 s、100 m、800 s時，識別準確率最佳，最終識別結果見圖2。圖2中綠色圓形為停駐軌跡近似最小覆蓋圓，位置圖標對應停駐軌跡中心，紅色圓圈為軌跡點。點擊交互式地圖中的位置圖標，可彈出該停駐時段起始時刻，點擊最小覆蓋圓，彈出該圓半徑及圓心位置。表4列出了當前識別停駐時段相關信息。計算當前識別結果精確度，Mtime-diff、Mdist取值確定為2 500 s與500 m。由于識別停駐點個數與真實停駐點個數相同，因此當前識別結果的查準率和查全率相等，其值為0.82。

表3 2019-03-29出行日志

對識別結果進行分析發現，三個真實停駐點都得到了有效識別，除第2個停駐點外，其余兩個停駐點起始終止時刻識別誤差較小。對出行軌跡點進行分析發現，造成第2個軌跡點識別誤差較大的主要原因在于室內信號差，軌跡點缺失導致。其中在17:27左右連續4條軌跡信息的時間戳分別為17:27:50、17:27:52、18:01:53、18:01:55。由于軌跡點缺失間隔過長，因此未對該缺失時段軌跡點進行插值。圖3操場西側建筑區域為圖書館，圖3中顯示當用戶18:01:53離開圖書館后，其位置點信息立即被采集到，由于此時該軌跡點偏離其在圖書館停駐中心較遠，因此其未被聚類到圖書館停駐時段中，導致圖書館停駐時段終止時刻與實際終止時刻相差較大。整體而言，本文所提出的最小覆蓋圓時空聚類算法能夠很好地識別用戶GPS軌跡中的停駐點及停駐時段。

圖1 2019-03-29軌跡Fig.1 Trajectory of 2019-03-29

圖2 2019-03-29軌跡停駐點識別結果Fig.2 Identified stop points in the trajectory of 2019-03-29

圖3 GPS信號缺失引起軌跡中斷Fig.3 Trajectory disconnected due to GPS signal missing

表4 2019-03-29軌跡識別停駐時段

4 結論

(1)提出了一種可用于GPS軌跡停駐點識別的最小覆蓋圓時空聚類算法。該算法計算量小，能夠很好地處理軌跡重合度高、異常軌跡點等情形。對某條包含9 923個位置點軌跡進行識別，所有停駐點均能夠被正確識別，除因信號缺失時段較長引起某一停駐時段終止時刻與實際相差較大外，其余停駐時段起始、終止時刻均與實際接近，驗證了該算法的有效性。

(2)最小覆蓋圓時空聚類算法能夠很好地確定用戶停駐活動起止時刻，但由于建筑物附近位置軌跡點偏移，其對于實際停駐點位置的確定存在一定偏差。后續研究可考慮進一步結合位置點信息、出行者社會屬性及出行歷史記錄對停駐點位置進行糾偏。

(3)最小覆蓋圓時空聚類算法可很好地適用于數據量較少的情形，若存在大量出行軌跡可供研究，可考慮從軌跡數據中提取高頻停駐點、挖掘用戶出行規律，作為停駐點識別的先驗信息，提高停駐點識別精確度。