車輛GPS軌跡興趣區(qū)域提取算法研究

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

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

?

車輛GPS軌跡興趣區(qū)域提取算法研究

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

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

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

關(guān)鍵詞：基于時(shí)間聚類;興趣點(diǎn);噪點(diǎn)剔除;DBSCAN;興趣區(qū)域

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

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

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

1基本概念

1.1GPS軌跡

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

圖1　軌跡及興趣點(diǎn)

1.2興趣點(diǎn)

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

1.3興趣區(qū)域

興趣區(qū)域(Region of Interest，ROI)是由多時(shí)段多軌跡的興趣點(diǎn)序列聚類生成，通過地理反編碼發(fā)掘并消除語義重復(fù)區(qū)域而產(chǎn)生的，如聚類結(jié)果中“鳥巢東南角”和“鳥巢西北角”兩個(gè)區(qū)域本質(zhì)上都是表示“鳥巢”,在語義層次上應(yīng)該合并。興趣區(qū)域R=(lat,lon,Sem)，其中(lat,lon)表示R質(zhì)心的經(jīng)緯度坐標(biāo)，Sem表示R的語義信息。

2車輛GPS軌跡興趣區(qū)域提取算法

2.1興趣點(diǎn)提取

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

鑒于車輛軌跡數(shù)據(jù)的特征：①當(dāng)車輛駛?cè)胨淼阑虻缆穬膳杂懈邩钦趽鯐r(shí)，會(huì)出現(xiàn)GPS信號(hào)丟失的情況。顯然，對(duì)于信號(hào)丟失點(diǎn)的處理方法不適用于此；②與步行、騎車等不同，車輛行駛時(shí)會(huì)發(fā)生擁堵，尤其在早晚高峰時(shí)。發(fā)生擁堵時(shí)，車輛會(huì)在較小的地理范圍內(nèi)停留較長時(shí)間，因此擁堵點(diǎn)會(huì)被誤認(rèn)為是興趣點(diǎn)；此外，車輛在立交橋上行駛，當(dāng)空間范圍小于Dmax、行駛時(shí)間大于Tmin時(shí)，也會(huì)被錯(cuò)誤地添加到興趣點(diǎn)序列中。綜上所述，本文對(duì)基于時(shí)間的聚類算法進(jìn)行改進(jìn)，過濾信號(hào)丟失點(diǎn)，并對(duì)興趣點(diǎn)序列中的噪點(diǎn)(擁堵點(diǎn)和立交橋路段)進(jìn)行剔除。

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

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

算法流程：

輸入：新GPS位置點(diǎn)loc、最大空間范圍Dmax、最短停留時(shí)間Tmin、最少點(diǎn)數(shù)目Nmin、路面Rroad、路口圓形緩沖區(qū)Rbuffer；

變量:當(dāng)前簇cl,待處理點(diǎn)ploc；

輸出:興趣點(diǎn)序列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興趣區(qū)域提取

目前，興趣區(qū)域提取的算法較多，參考文獻(xiàn)[3]采用K-means算法，參考文獻(xiàn)[17]運(yùn)用OPTICS算法，參考文獻(xiàn)[18]采用基于格網(wǎng)的聚類算法(Grid-based Clustering)。由于K-means算法需要預(yù)先指定聚類數(shù)目，而基于格網(wǎng)的聚類算法是與個(gè)性化推薦應(yīng)用相關(guān)聯(lián)的，因此本文選用基于密度的聚類算法；又由于DBSCAN算法在異常數(shù)據(jù)抗干擾性上優(yōu)于OPTICS算法，因此本文選用DBSCAN算法進(jìn)行興趣區(qū)域提取。

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

3實(shí)驗(yàn)

3.1數(shù)據(jù)準(zhǔn)備

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

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

3.2興趣點(diǎn)與興趣區(qū)域提取

本文運(yùn)用Java語言進(jìn)行算法實(shí)現(xiàn)，以最大空間范圍Dmax，最短停留時(shí)間Tmin，最少點(diǎn)數(shù)目Nmin，路面Rroad，路口緩沖區(qū)Rbuffer作為輸入?yún)?shù)提取興趣點(diǎn)。取2009年472條車輛軌跡進(jìn)行算法測(cè)試，得出Dmax,Tmin與興趣點(diǎn)聚類的簇?cái)?shù)目C的對(duì)應(yīng)關(guān)系，如圖3所示。

圖3　Dmax,Tmin與C關(guān)系折線圖

在參數(shù)選取上,若Dmax太大,會(huì)將多個(gè)興趣點(diǎn)粗略地合并為一個(gè),而太小又會(huì)割裂興趣點(diǎn)；同理，Tmin太大會(huì)遺漏許多興趣點(diǎn)，而太小又會(huì)將低速行駛的子軌跡納入興趣點(diǎn)序列。參照?qǐng)D3并結(jié)合Google Earth的GPS軌跡可視化效果可知，在該應(yīng)用中Dmax∈[100,150]，Tmin∈[180,240]，Nmin=3時(shí)興趣點(diǎn)提取效果最佳。

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

圖4　軌跡T的興趣點(diǎn)提取結(jié)果

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

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

圖5　語義相同的簇合并

圖6　北京市北三環(huán)附近興趣區(qū)域的簇質(zhì)心分布

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

表1　興趣區(qū)域RA～RK詳細(xì)信息表

4結(jié)束語

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

參考文獻(xiàn)：

[1]周國眾,夏青.移動(dòng)位置服務(wù)中增強(qiáng)現(xiàn)實(shí)技術(shù)的應(yīng)用[J].測(cè)繪工程.2012,10,21(5):63-68.

[2]朱曉東，張慶全，周源.北斗二代衛(wèi)星導(dǎo)航系統(tǒng)在生產(chǎn)車輛管理中的應(yīng)用[J].測(cè)繪與空間地理信息，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.

[責(zé)任編輯：李銘娜]

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

中圖分類號(hào)：P228

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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