車輛GPS軌跡興趣區域提取算法研究

何源浩，魏海平，周　燁，王艷濤

(信息工程大學 地理空間信息學院，河南 鄭州 450001)

?

車輛GPS軌跡興趣區域提取算法研究

何源浩，魏海平，周燁，王艷濤

(信息工程大學 地理空間信息學院，河南 鄭州 450001)

摘要：車輛行駛軌跡是駕駛員主觀意愿和路網客觀約束綜合作用的結果，從海量軌跡中挖掘興趣區域可為車輛提供更深層次、更有效的位置服務。文中深入分析車輛GPS軌跡特征，在基于時間的聚類算法中引入路網約束，實現車輛GPS軌跡的興趣點提取和噪點剔除，基于DBSCAN算法生成興趣區域，采用Google Geocoding反向地理編碼發掘并合并語義重復區域，在語義層次上實現興趣區域提取。實驗表明，該算法可在語義層次有效提取興趣區域。

關鍵詞：基于時間聚類;興趣點;噪點剔除;DBSCAN;興趣區域

興趣區域，作為車輛軌跡中隱含的重要信息，表示用戶經常出沒的、帶有重要語義信息的地區；提取興趣區域能為車主日常出行、位置信息檢索[1-2]、觀光旅游等提供輔助決策的依據，同時也是構建位置服務個性化推薦系統的基礎。

軌跡數據挖掘的早期研究主要針對其幾何屬性，并未考慮空間特征。N.Marmasse[3]與D.Ashbrook[4]將軌跡中的信號丟失點當成重要的室內區域，該方法僅對小面積室內場所的檢測有效；隨后在S.Brakatsoulas[5]，R.H.Güting[6]，X.Li[7]，M.Vazirgiannis[8]等的研究中均引入了路網概念，考慮其對軌跡數據建模、存儲和檢索的影響。2004年，Kang J H[9]提出一種增量型聚類算法，識別單軌跡中的重要區域。2007年，L.O.Alvares[10]提出SMoT算法,面向多領域應用從軌跡采樣點中提取重要區域，但要求用戶事先指定感興趣區域；S.Spaccapietra[11]引入面向軌跡數據的推理模型，分析語義得到停留與運動的子軌跡。2008年，Palma A T[12]以“停留點速度較低”為模型假設提出改進的SMoT算法CB-SMoT，解決了信號丟失點提取難的問題，但其模型假設中僅考慮速度因素。Zheng Y[13]最早開展GPS軌跡數據中興趣區域提取、排名和推薦等方面的研究，但是忽略語義因素；Cao X[14]與Xiao X[15]在Zheng的研究基礎上，實現語義層次上對興趣區域的提取。

綜上所述，目前GPS軌跡數據挖掘算法研究大多面向多種交通模式(步行、公交、騎車和開車等)，缺乏對其中某一類數據，例如車輛軌跡數據進行深入研究。因此本文在深入分析車輛軌跡特征的基礎上，研究興趣點的提取及噪點的剔除，并在語義層次上實現興趣區域的表達。

1基本概念

1.1GPS軌跡

車輛GPS數據是通過車載GPS定位設備采集，采樣點Pi=(lat,lon,t)表示用戶當前所處位置的緯度lat，經度lon和時間t，坐標系統采用UTM。一條GPS軌跡(GPS Trajectory)是由一系列GPS采樣點Pi依時序連接而成，軌跡T=P1→P2→…→Pn，其中Pi∈P，Pi+1.t>Pi.t，(1≤i

圖1　軌跡及興趣點

1.2興趣點

興趣點(Point of Interest，POI)指在單條軌跡中，車輛停留時間超過閾值Tmin的地點或小范圍區域。根據車輛軌跡數據的特征，興趣點S分為①軌跡T的起點P1和終點Pn。當泊車時，車載GPS終端會停止采集數據，而起點與終點在一定程度上表示用戶經常出沒的地點(如住宅區，辦公區等)。興趣點S=(lati,loni,Tsta,Tend) ，其中i={1,n}，Tsta=Tend，如圖1中的Stay point 1和Stay point 3；②軌跡T中，當存在T′={Pm,Pm+1,…,Pk}，對于?m≤j

1.3興趣區域

興趣區域(Region of Interest，ROI)是由多時段多軌跡的興趣點序列聚類生成，通過地理反編碼發掘并消除語義重復區域而產生的，如聚類結果中“鳥巢東南角”和“鳥巢西北角”兩個區域本質上都是表示“鳥巢”,在語義層次上應該合并。興趣區域R=(lat,lon,Sem)，其中(lat,lon)表示R質心的經緯度坐標，Sem表示R的語義信息。

2車輛GPS軌跡興趣區域提取算法

2.1興趣點提取

Li Q[16]基于“最短停留時間”和“最大空間范圍”約束實現興趣點的提取，該算法將信號丟失點(住宅，購物大廈等室內場所)當作興趣點，但是計算量大，非實時；Kang J H[9]提出一種基于時間的聚類(Time-based Clustering)算法，可實時檢測興趣點且計算量較小，但是并未考慮信號丟失點的處理。

鑒于車輛軌跡數據的特征：①當車輛駛入隧道或道路兩旁有高樓遮擋時，會出現GPS信號丟失的情況。顯然，對于信號丟失點的處理方法不適用于此；②與步行、騎車等不同，車輛行駛時會發生擁堵，尤其在早晚高峰時。發生擁堵時，車輛會在較小的地理范圍內停留較長時間，因此擁堵點會被誤認為是興趣點；此外，車輛在立交橋上行駛，當空間范圍小于Dmax、行駛時間大于Tmin時，也會被錯誤地添加到興趣點序列中。綜上所述，本文對基于時間的聚類算法進行改進，過濾信號丟失點，并對興趣點序列中的噪點(擁堵點和立交橋路段)進行剔除。

圖2　基于時間聚類示意圖(引自Kang J H，2004)

算法思想：該算法是對GPS位置點沿著時間軸進行聚類。將新產生的位置點與前一個進行比較，如果二者距離大于閾值，則將新位置點歸于一個新簇。如圖2所示，當車輛在區域A，所有位置點都在Dmax范圍內，則將其標記為簇a；車輛向區域B移動時，形成若干新簇i1，i2，i3與b。當車輛在區域內停留時間超過Tmin，則標記為興趣點，圖2中將簇a與b添加到興趣點序列。因興趣點序列可能含信號丟失點、擁堵點與立交橋路段，采用①在相同的采樣頻率下，出現信號丟失現象的子軌跡包含的GPS點數目較少，所以本文引入最少點數目Nmin，過濾點數較少的興趣點(軌跡起、始點除外)；②車輛擁堵和立交橋路段大多在路口及其附近，所以當簇質心在路面上和以路口中心點為圓心的圓形緩沖區Rbuffer內時，可將其視為噪點予以剔除。

算法流程：

輸入：新GPS位置點loc、最大空間范圍Dmax、最短停留時間Tmin、最少點數目Nmin、路面Rroad、路口圓形緩沖區Rbuffer；

變量:當前簇cl,待處理點ploc；

輸出:興趣點序列SP；

Begin：

if distance (cl,loc) < Dmaxthen

add loc to cl

ploc = null

else

if ploc !=null then

if duration(cl) > Tminthen

if pointNum(cl) > Nminthen

if CalCentroid(cl) ? (Rroad∩Rbuffer) then

add cl to SP

clean cl

add ploc to cl

if distance(cl,loc) < Dmaxthen

add loc to cl

ploc = null

else

ploc = loc

else

ploc = loc

End

2.2興趣區域提取

目前，興趣區域提取的算法較多，參考文獻[3]采用K-means算法，參考文獻[17]運用OPTICS算法，參考文獻[18]采用基于格網的聚類算法(Grid-based Clustering)。由于K-means算法需要預先指定聚類數目，而基于格網的聚類算法是與個性化推薦應用相關聯的，因此本文選用基于密度的聚類算法；又由于DBSCAN算法在異常數據抗干擾性上優于OPTICS算法，因此本文選用DBSCAN算法進行興趣區域提取。

基于改進的時間聚類算法可得到多時段大眾軌跡的興趣點序列集，選取合適的最少點數目MinPts和半徑e做輸入參數,運用DBSCAN算法聚類得到若干簇。取各簇的質心，利用Google Geocoding工具對其進行反向地理編碼獲得其語義信息，人工識別出在語義層次表示同一地理實體的簇后進行合并，最終得到的簇即為興趣區域，以簇質心和語義信息表示。

3實驗

3.1數據準備

實驗數據來自微軟亞洲研究院GeoLife項目,該項目提供的GPS軌跡數據覆蓋30多個城市，從2007～2012年，包含17 621條軌跡，91%數據的采樣頻率為1～5 s或5～10 m，涉及多種交通模式。

本文以北京市為研究區域，取交通模式為taxi或car的軌跡數據。以數據的時效性、全部軌跡的覆蓋范圍、軌跡特征多樣性和軌跡的平均長度等作為選取測試數據的主要指標。2010～2012年間軌跡總數為45條，而2009年軌跡總數為472條，且時間上覆蓋全年11個月份、空間上幾乎覆蓋北京市區主要道路，特征較豐富，軌跡平均采樣點數超過500個，因此取2009年472條軌跡作為測試數據，剔除野值后即可使用。

3.2興趣點與興趣區域提取

本文運用Java語言進行算法實現，以最大空間范圍Dmax，最短停留時間Tmin，最少點數目Nmin，路面Rroad，路口緩沖區Rbuffer作為輸入參數提取興趣點。取2009年472條車輛軌跡進行算法測試，得出Dmax,Tmin與興趣點聚類的簇數目C的對應關系，如圖3所示。

圖3　Dmax,Tmin與C關系折線圖

在參數選取上,若Dmax太大,會將多個興趣點粗略地合并為一個,而太小又會割裂興趣點；同理，Tmin太大會遺漏許多興趣點，而太小又會將低速行駛的子軌跡納入興趣點序列。參照圖3并結合Google Earth的GPS軌跡可視化效果可知，在該應用中Dmax∈[100,150]，Tmin∈[180,240]，Nmin=3時興趣點提取效果最佳。

對北京市北三環附近的車輛GPS軌跡進行興趣點提取。以其中一條軌跡(含4 345個采樣點)的提取效果為例，如圖4所示,點P1至點P2之間的采樣點組成軌跡T，取Dmax= 130 m，Tmin=210 s，Nmin=3時，得到興趣點聚類的簇數目C=8個，依次為S1～S8；圖中的N1和N2，經人工確認分別為立交橋路段和堵車點，通過本文的算法，有效地將N1和N2排除在興趣點序列之外。圖4中矩形放大窗口內的橢圓或多邊形輪廓線僅用于標記聚類結果，不表示簇的形狀或空間范圍。

圖4　軌跡T的興趣點提取結果

運用DBSCAN算法對北三環附近區域的大眾軌跡興趣點序列集進行聚類，最少點數目MinPts=2，半徑e=Dmax=130 m，得到若干個簇，并合并語義相同的簇，如圖5所示，圖5(a)中C1和C2分別是簇R1、R2的質心，其中R1=(39.993 8°，116.389 1°，朝陽區天辰西路/國家體育館售票處)，R2=(39.988 6°，116.388 0°，朝陽區北辰西路69號/國家體育館南路)，經分析可知R1、R2實際表示同一地理實體，可合并為R3=(39.991 2°，116.388 5°，國家體育館/鳥巢)，簇質心為C3，如圖5(b)所示。

經合并后最終得到9個興趣區域RA～RK，以對應的簇質心CA～CK可視化表示興趣區域，見圖6；帶語義信息的興趣區域見表1。提取的興趣區域在地理空間分布上基本覆蓋了北三環附近區域；在興趣區域的類型上，景區、公園、購物中心與實地情況基本吻合，而RB住宅區則反映了用戶的特有信息，說明用戶多住于此，隨著數據源的改變，住宅區可能會變化。綜上所述，本文的算法達到了較好的效果，并可以發掘用戶的特有信息。

圖5　語義相同的簇合并

圖6　北京市北三環附近興趣區域的簇質心分布

實驗結果表明：①提取的興趣點序列中不包含信號丟失點、擁堵點和立交橋路段，可見改進的基于時間聚類算法可有效地實現信號丟失點的過濾和噪點的剔除；②提取的興趣區域中包含景區、公園、購物中心和住宅區等，可見提供GPS軌跡的車主大多數居住在太平湖小區，且其它興趣區域的位置與語義信息符合實際情況，說明本文提出的興趣區域提取算法是科學有效的；③對于RF,RG,RH,RK等4個在空間位置上臨近的區域，本文實現了精確的提取，并未出現區域混淆的情況，說明實驗參數在選取上是合理的。

表1　興趣區域RA～RK詳細信息表

4結束語

車輛行駛軌跡是駕駛員主觀意愿和路網客觀約束綜合作用的結果，從海量軌跡數據中挖掘興趣區域可為車輛提供更人性化的位置服務。本文的貢獻在于專門針對車輛軌跡提出興趣區域提取算法；在興趣點提取上，創新地提出基于路網約束的噪點剔除方法，有效地排除擁堵點與立交橋等的干擾。此外，基于位置大數據的車輛位置服務推薦算法將是后期的研究方向。

參考文獻：

[1]周國眾,夏青.移動位置服務中增強現實技術的應用[J].測繪工程.2012,10,21(5):63-68.

[2]朱曉東，張慶全，周源.北斗二代衛星導航系統在生產車輛管理中的應用[J].測繪與空間地理信息，2015,38(5)：25-27.

[3]MARMASSE N,SCHMANDT C.Location-aware information delivery with commotion[M].In Proc.Huc，2000.

[4]ASHBROOK D,STARNER T.Using GPS to learn significant locations and predict movement across multiple users[M].Personal Ubiquitous Computing，7，2003.

[5]brakatsoulas S，PFOSER D，TRYFONA N.Modeling，storing，and mining moving object databases[C].Proceedings of the International Database Engineering and Applications Symposium，Washington，DC，USA，2004:68-77.

[6]GüTING R H，DE ALMEIDA V T，DING Z.Modeling and querying moving objects in networks[J].VLDB J.，15(2):165-190，2006.

[7]LI X，CLARAMUNT C，RAY C，et al.A semantic-based approach to the representation of network-constrained trajectory data[C].In Progress in Spatial Data Handling-12th International Symposium on Spatial Data Handling，Springer，Berlin，2006:451-464.

[8]VAZIRGIANNIS M,WOLFSON O.A spatio-temporal model and language for moving objects on road networks[C].In SSTD，2001:20-35.

[9]KANG J H，WELBOURNE W，STEWART B,et al.Extracting places from traces of locations[C].Proceedings of the 2nd ACM international workshop on Wireless mobile applications and services on WLAN hotspots，ACM，New York，NY，USA，2004:110-118.

[10] ALVARES L O，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，NY，USA，ACM Press,2007.

[11] SPACCAPIETRA S，PARENT C，DAMIANI M L，et al.A conceptual view on trajectories[R].Technical report，Ecole Polytechnique Federal de Lausanne，2007,4.

[12] PALMA A T，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.ACM，2008:863-868.

[13] ZHENG Y，ZHANG L，XIE X，et al.Mining interesting locations and travel sequences from GPS trajectories[C]//Proceedings of the 18th international conference on World wide web.ACM，2009:791-800.

[14] CAO X，CONG G，JENSEN C S.Mining significant semantic locations from GPS data[J].Proceedings of the VLDB Endowment，2010，3(1-2):1009-1020.

[15] XIAO X，ZHENG Y，LUO Q，et al.Finding similar users using category-based location history[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems.ACM，2010:442-445.

[16] LI Q，ZHENG Y，XIE X，et al.Mining user similarity based on location history[C]//Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems.ACM,2008:34.

[17] YE Y，ZHENG Y，CHEN Y，et al.Mining individual life pattern based on location history[C]//Mobile Data Management:Systems，Services and Middleware，2009.MDM’09.Tenth International Conference on.IEEE，2009:1-10.

[18] ZHENG V W，ZHENG Y，XIE X，et al.Collaborative location and activity recommendations with GPS history data[C]//Proceedings of the 19th international conference on World wide web.ACM，2010:1029-1038.

[19] MONTOLIU R，BLOM J，GATICA-PEREZ D.Discovering places of interest in everyday life from smartphone data[J].Multimedia tools and applications，2013，62(1):179-207.

[責任編輯：李銘娜]

Algorithm for extracting regions of interest from vehicle GPS trajectoryHE Yuanhao，WEI Haiping，ZHOU Ye，WANG Yantao

(School of Geographic Space Information，Information Engineering University,Zhengzhou 450001,China)

Abstract：Vehicle trajectory is the comprehensive result of the driver’s subjective will and the road network objective constraints.Extracting the region of interest from massive trajectory data can provide a deeper level and more effective location-based service.This paper analyzes the characteristic of vehicle GPS trajectories，extracts points of interest and excludes noises by using a time-based clustering algorithm with the road network constraints，then generates regions of interest by using DBSCAN algorithm and merge semantic repeat ones with Google encoding tool，and finally obtains the regions of interest semantically.Its efficiency is verified with the investigation and experiment result.

Key words：time-based clustering;point of interest;noise excluding;DBSCAN;region of interest

中圖分類號：P228

文獻標識碼：A

文章編號：1006-7949(2016)05-0047-05

作者簡介：何源浩(1989-)，男，碩士研究生.

收稿日期：2015-05-22;修回日期：2015-06-01