劉　春，曹　凱

(山東理工大學(xué) 交通與車輛工程學(xué)院，山東 淄博255049)

?

基于GPS的出行者停止語義推斷模型

劉春，曹凱

(山東理工大學(xué) 交通與車輛工程學(xué)院，山東 淄博255049)

摘要：傳統(tǒng)的車輛運(yùn)動(dòng)軌跡特性分析通常采用對(duì)其停止點(diǎn)加注語義的方法，該方法存在信息采集繁雜、信息遺漏以及實(shí)時(shí)處理不方便等問題.為此，提出以GPS軌跡數(shù)據(jù)中的語義信息為直接挖掘?qū)ο?，運(yùn)用馬爾可夫鏈方法推斷車輛運(yùn)動(dòng)下一停止點(diǎn)的方法.該方法通過辨識(shí)車輛停留中的子停留，利用車輛運(yùn)動(dòng)軌跡點(diǎn)特征參數(shù)(即時(shí)速度、停留時(shí)長等)進(jìn)行信息量化，并與構(gòu)建的判別信息庫進(jìn)行比對(duì)，從而挖掘車輛停留中的子停留語義信息.此外，通過劃分車輛運(yùn)行狀態(tài)層次，統(tǒng)計(jì)每個(gè)子停留在每個(gè)狀態(tài)層次的出現(xiàn)頻率，以此推斷車輛的未來停止點(diǎn).實(shí)車測試結(jié)果表明，采集數(shù)據(jù)量越大，狀態(tài)層次劃分的越細(xì)，計(jì)算結(jié)果越穩(wěn)定；預(yù)測范圍越小，按照比例還原的電子地圖產(chǎn)生的誤差越小，所得的預(yù)測越準(zhǔn)確.

關(guān)鍵詞：車輛運(yùn)動(dòng)軌跡分析;語義注釋;子停留;馬爾可夫鏈

近年來，GPS被廣泛使用，從而產(chǎn)生了大量的軌跡數(shù)據(jù).軌跡數(shù)據(jù)分析研究的趨勢已從軌跡幾何特性和模式類型分析發(fā)展到軌跡數(shù)據(jù)的語義挖掘，從而實(shí)現(xiàn)對(duì)軌跡的分析更加深入和全面，也為從GPS軌跡數(shù)據(jù)中提取人們出行活動(dòng)信息的研究提供了理論基礎(chǔ)[1].2008年,Spaccapietra[2]提出了第一個(gè)GPS軌跡語義分析模型SMoT(StopsandMovesofTrajectories)，該模型中軌跡由移動(dòng)和停留組成，其中停留是軌跡具有標(biāo)志性的部分.此外，一些典型的研究成果有：Wolf[3]提出了推斷出行者出行目的的兩個(gè)重要思路：其一，以出行者出行起訖點(diǎn)的土地利用性質(zhì)為重要依據(jù)推斷其出行目的；其二，利用采集到的出行者個(gè)人出行信息改善推斷出行者出行目的的效果.Griffin[4]使用C4.5決策樹算法簡單判別規(guī)則，建立起出行特性與出行目的的關(guān)系.我國學(xué)者主要從理論角度歸納和定義與出行目的識(shí)別相關(guān)的語義信息類型，如華東師范大學(xué)的鄧中偉等[5]對(duì)相關(guān)背景信息類型進(jìn)行了歸納和定義，利用機(jī)器學(xué)習(xí)數(shù)據(jù)挖掘技術(shù)(主要為C5.0算法)，依托經(jīng)驗(yàn)建模的思路，建立了出行目的與多屬性變量的關(guān)系，進(jìn)行出行目的的智能化提取；山東理工大學(xué)的竇麗莎等[6]提出利用模糊識(shí)別算法來推斷出行者出行目的.

本文著眼于出行者的微觀活動(dòng)分析與出行目的挖掘研究.以SMoT模型為基礎(chǔ)，利用出行者的GPS軌跡信息(考慮到GPS軌跡數(shù)據(jù)中隨機(jī)不確定性，以出行者的停留點(diǎn)為觀察點(diǎn))，研究推斷出行者進(jìn)一步移動(dòng)的停止點(diǎn)及相關(guān)語義的挖掘方法.為此，提出基于馬爾可夫鏈的推斷出行者停止點(diǎn)的新算法，即，通過劃分出行者移動(dòng)狀態(tài)層次，統(tǒng)計(jì)GPS軌跡中出行者在停留點(diǎn)處的狀態(tài)層次概率分布，計(jì)算下一停留點(diǎn)的狀態(tài)轉(zhuǎn)移概率，以推斷出行的下一停留點(diǎn).

1　出行者出行軌跡數(shù)據(jù)

1.1出行原始數(shù)據(jù)的獲取

為獲得車輛GPS軌跡數(shù)據(jù)，為試驗(yàn)車輛設(shè)計(jì)安裝了特定的GPS數(shù)據(jù)采集模塊，使其能夠進(jìn)行數(shù)據(jù)存儲(chǔ)和傳輸.為此，實(shí)驗(yàn)數(shù)據(jù)采集選用GeoLogger和NEVEStepLogger進(jìn)行試驗(yàn).對(duì)安裝了特定GPS設(shè)備的試驗(yàn)車進(jìn)行多軌跡數(shù)據(jù)采集，并以此作為實(shí)驗(yàn)數(shù)據(jù).輸出的ExcelFile(.csv)格式的GPS軌跡數(shù)據(jù)包含了軌跡的日期、時(shí)間、經(jīng)緯度、海拔高以及車輛在各個(gè)時(shí)刻的運(yùn)動(dòng)速度等信息.

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

目前全球定位系統(tǒng)使用的是WGS-84坐標(biāo)系，它是一種國際地心坐標(biāo)系，為方便后期數(shù)據(jù)處理，需要進(jìn)行坐標(biāo)系轉(zhuǎn)換，以WGS84的參考橢圓體為基準(zhǔn)進(jìn)行高斯投影，利用EXCEL簡易的進(jìn)行GPS坐標(biāo)轉(zhuǎn)換.

對(duì)GPS軌跡數(shù)據(jù)進(jìn)行語義挖掘，獲取出行者信息的過程中，用到一些基本的數(shù)據(jù)計(jì)算，其中比較基本的兩個(gè)量值是點(diǎn)間距和轉(zhuǎn)向角，它們能夠表征軌跡的基本信息.GPS點(diǎn)間距離使用如下公式進(jìn)行計(jì)算[7]：

Δlat=lat2-lat1

(1)

Δlong=long2-long1

(2)

a=sin2(lat/2)+cos(lat1)*

cos(lat2)*sin2(Δlong/2)

(3)

a=sin2(Δlat/2)+cos(lat1)*

cos(Δlat2)*sin2(Δlong/2)

(4)

(5)

D=R*C

(6)

其中R=6 371km.相鄰軌跡段的轉(zhuǎn)向角反映了軌跡運(yùn)動(dòng)的趨勢，連續(xù)軌跡段在軌跡點(diǎn)處的夾角表示為α，軌跡的轉(zhuǎn)角表示為θ，夾角α和轉(zhuǎn)角θ關(guān)系如圖1所示，計(jì)算公式如下：

(7)

(8)

圖1　軌跡轉(zhuǎn)角示意圖

2　判別信息庫的建立及停留點(diǎn)的辨識(shí)算法

2.1判別信息庫構(gòu)建

GPS記錄的軌跡數(shù)據(jù)中必然有明確的起迄點(diǎn)，其中迄點(diǎn)即為停留.如果為多目的出行，那么在整個(gè)行程中的GPS軌跡數(shù)據(jù)中必然會(huì)有多個(gè)起迄點(diǎn)，整個(gè)行程中的這些迄點(diǎn)即為子停留.無論停留還是子停留都隱含著出行者的某種目的，因此必然對(duì)應(yīng)與目的相關(guān)的地理位置.通過將停留或子停留與GIS相匹配，以停留或子停留點(diǎn)為中心，以適當(dāng)?shù)牟叫芯嚯x(如5~10m)為半徑，尋找停留或子停留附近的實(shí)際地理環(huán)境，以此將沒有語境意義的GPS數(shù)據(jù)點(diǎn)語義化，并根據(jù)子停留語義信息，獲得子停留的活動(dòng)類型.

判別信息庫是停留與子停留語義活動(dòng)類型的集合.為此，根據(jù)GPS數(shù)據(jù)特征，選取Time(時(shí)長)、Speed(平均速度)、Direction(平均轉(zhuǎn)角)3項(xiàng)作為子停留活動(dòng)點(diǎn)的特征參數(shù)來構(gòu)建判別信息庫.通過進(jìn)行大量的出行調(diào)查和分析，獲取居民出行的各種出行目的類型和與之對(duì)應(yīng)的特征參數(shù)值，從而確定判別信息庫的特征參數(shù)閥值.再利用子停留的特征參數(shù)值與確立的特征參數(shù)閥值進(jìn)行對(duì)比，獲知子停留活動(dòng)類型.例如對(duì)辦公大廈進(jìn)行信息庫構(gòu)建時(shí)，通過調(diào)查可得主要的子停留活動(dòng)類型為上班、臨時(shí)辦公.通過GPS和室內(nèi)定位系統(tǒng)獲取的數(shù)據(jù)可得一系列的子停留，將子停留的特征參數(shù)與之前調(diào)查所得的特征參數(shù)閥值相對(duì)比可得：停留時(shí)長大于8h，平均速度為0，平均轉(zhuǎn)角為0，則可判斷為上班；停留時(shí)長大于0.5h，平均速度小于1.5km/h，平均轉(zhuǎn)角小于45°，可以判斷為臨時(shí)辦公(路過)(見表1).

表1辦公大廈判別信息庫

活動(dòng)點(diǎn)特征參數(shù)活動(dòng)類型Min-Time/hMax-Speed/km·h-1Max-Direction/(°)0.581.50450路過上班

2.2算法

利用IB-SMoT算法得到軌跡中的停留后，與電子地圖相結(jié)合選擇合適的判別信息庫k-base，然后運(yùn)用DBSCAN和CB-SMoT算法確定子停留后，將子停留特征參數(shù)與給定的特征參數(shù)閥值進(jìn)行對(duì)比獲知出行目的，算法具體過程見表2.

3　下一停留點(diǎn)推斷

通過以上算法，可以從已有軌跡數(shù)據(jù)中提取出行者的出行目的.由于出行者的出行目的有較大的隨機(jī)性，為此運(yùn)用馬爾科夫模型對(duì)出行者未來活動(dòng)進(jìn)行預(yù)測與推斷，即對(duì)出行者下一停留地進(jìn)行推斷.

3.1模型條件

系統(tǒng)在每一時(shí)刻(或每一步)上的狀態(tài)，僅僅取決于前一時(shí)刻(或前一步)的狀態(tài).這個(gè)性質(zhì)稱為無后效性，即所謂的馬爾可夫假設(shè).具備這個(gè)性質(zhì)的離散型隨機(jī)過程，稱為馬爾可夫鏈[8]. 用數(shù)學(xué)語言來

表2子停留辨識(shí)及目的推斷算法偽代碼

PUT: T //一條GPS軌跡數(shù)據(jù) k-base //判別信息庫OUTPUT: Goal //子停留目的METHOD:Stops->IB-Cluster //運(yùn)用IB-SMOT算法得出軌跡T的停留subStops->CB-SMOT //運(yùn)用CB-SMOT算法得出停留中的子停留FOReachsubStopDO //對(duì)于每個(gè)子停留如下計(jì)算timesubStop=endTime-startTime;//停留時(shí)長directionsubStop=getDirectionVariation;//停留的平均轉(zhuǎn)角speedsubStop=getSpeedVariation;//停留平均速度FOReachrulerinkBaseDO //對(duì)于每條規(guī)則r如下運(yùn)算maxDirectionOfRule=getMaxDirection;maxSpeedOfRule=getMaxSpeed;minTimeOfRule=getMinTime;//獲取規(guī)則最小時(shí)長、最大速度、最大轉(zhuǎn)角的量值IF(timeStop≤minTimeOfRuleANDspeedStop≤maxSpeedOfRuleANDdirectionStop≤maxDirectionOfRule) s.addGoal(r.getGoal);//規(guī)則r對(duì)應(yīng)的目的就是子停留s的目的 ENDIFENDFORENDFORENDMETHOD

描述即

如果對(duì)任一n>1，任意i1,i2，…，in-1,j∈S恒有

P{Xn=j|X1=i1,X2=i2,…，Xn-1=in-1}=

P{Xn=j|Xn-1=in-1}

(9)

則稱離散型隨機(jī)過程Xt,t∈T為馬爾可夫鏈.

3.2數(shù)據(jù)處理

原始的車輛GPS軌跡輸出如圖2所示，根據(jù)前面所述可以判斷軌跡點(diǎn)密集區(qū)域?yàn)橥Ａ艉妥油Ａ?，在進(jìn)行模型構(gòu)建時(shí)，將停留與子停留區(qū)域簡化為點(diǎn)集.由于新的點(diǎn)集軌跡高程坐標(biāo)波動(dòng)范圍大，因此軌跡跨越區(qū)域大.在進(jìn)行活動(dòng)狀態(tài)層次劃分時(shí)，如此大區(qū)域跨度，如若劃分較少的狀態(tài)層次，則預(yù)測精確度會(huì)降低；如若劃分較多狀態(tài)層次，則計(jì)算量會(huì)大大增加，給預(yù)測帶來不便.針對(duì)上述問題，需要對(duì)原始GPS軌跡數(shù)據(jù)進(jìn)行預(yù)處理.這里利用前后兩點(diǎn)位置高程坐標(biāo)取平均值法，使得軌跡的跨度范圍縮小，方便進(jìn)行層次劃分，具體方法如圖3所示.

圖2　原始車輛軌跡圖

圖3　模型數(shù)據(jù)處理圖

3.3模型應(yīng)用

選定同一經(jīng)度的4個(gè)點(diǎn)作為實(shí)驗(yàn)的坐標(biāo)原點(diǎn)，令安裝有特定GPS設(shè)備的試驗(yàn)車從距離坐標(biāo)原點(diǎn)一定距離的起點(diǎn)出發(fā)，然后到達(dá)某一終止點(diǎn)(本文選取山東理工大學(xué)西校區(qū)某3處建筑作為試驗(yàn)起點(diǎn)，另選取淄博人民公園附近3處建筑物作為終點(diǎn))，反復(fù)測試，獲得大量運(yùn)動(dòng)軌跡.然后對(duì)運(yùn)動(dòng)軌跡數(shù)據(jù)進(jìn)行預(yù)處理，從中找出運(yùn)動(dòng)軌跡數(shù)據(jù)中最大值與最小值.以最大值和最小值作水平線，并以此為界線將軌跡數(shù)據(jù)區(qū)域劃分為4個(gè)狀態(tài)層次：狀態(tài)1、狀態(tài)2、狀態(tài)3和狀態(tài)4.通過選取一個(gè)小時(shí)的實(shí)驗(yàn)時(shí)間段，以10min為間隔閥值，將實(shí)驗(yàn)時(shí)間段劃分為6個(gè)運(yùn)動(dòng)周期進(jìn)行分析，如圖4所示.

圖4　狀態(tài)層次圖

在進(jìn)行系統(tǒng)預(yù)測時(shí)，首先假定：

(1)預(yù)測期內(nèi)系統(tǒng)狀態(tài)數(shù)保持不變.

(2)系統(tǒng)的狀態(tài)轉(zhuǎn)移概率矩陣不隨時(shí)間而變化.

軌跡在t=0時(shí)處于4個(gè)狀態(tài)的概率是相同的，即起點(diǎn)的選取是隨機(jī)的.因此，初始狀態(tài)概率向量可定義為

P(0)= (p1(0),p2(0),p3(0),p4(0)=

(0.25,0.25,0.25,0.25)

設(shè)軌跡在ti時(shí)刻處于狀態(tài)層次j(j=1，2，3，4)，在ti+1時(shí)刻處于層次kj+1，就說明軌跡進(jìn)行了狀態(tài)轉(zhuǎn)移，記狀態(tài)轉(zhuǎn)移概率為pij,則

pij≥0,i,j,=1,2,3,4

(10)

各個(gè)狀態(tài)轉(zhuǎn)移概率矩陣P為

(11)

轉(zhuǎn)化為矩陣形式為

P(k)=Pk,k≥1

在進(jìn)行7步預(yù)測時(shí)可具體為P(7)=P7.如果已知轉(zhuǎn)移矩陣以及初始狀態(tài)概率向量，則任意時(shí)刻的狀態(tài)概率分布可以確定為

若記向量P(k)=(p1(k),p2(k),…，pN(k)),

則上式可寫為

P(k)=P(0)P(k)=P(0)P(k).此時(shí)，進(jìn)行第7步的狀態(tài)預(yù)測，即對(duì)模型進(jìn)行7步狀態(tài)轉(zhuǎn)移，得到

P(7)=P(0)P(7)

將P(0)和P(7)代入，可得

[0.230 9 0.168 7 0.167 5 0.432 8]

(12)

由上述計(jì)算結(jié)果可知，實(shí)驗(yàn)進(jìn)行至第7步時(shí)，第1層系統(tǒng)狀態(tài)概率為0.230 9，第2層系統(tǒng)狀態(tài)概率為0.168 7，第3層狀態(tài)概率為0.167 5，第4層狀態(tài)概率為0.432 8.第4層次的概率明顯高于前3個(gè)層次，因此可以推斷實(shí)驗(yàn)在第7步時(shí)處于第4個(gè)層次的可能性最大.通過計(jì)算各層次的概率，在電子地圖上按比例將各層次所表示區(qū)域范圍表示出來，找到該范圍內(nèi)實(shí)際語義的地理環(huán)境，即車輛可能的下一目的地.

如圖5所示，根據(jù)上述狀態(tài)層次概率計(jì)算結(jié)果，結(jié)合校園電子地圖可推斷實(shí)驗(yàn)在第8步時(shí)，可能由山東理工大學(xué)東校移動(dòng)到淄博人民公園西側(cè)的豬龍河.

圖5　試驗(yàn)車在第8個(gè)周期時(shí)的停留地

4　結(jié)束語

本文提出的推斷出行目的方法，打破了通常使用軌跡宏觀背景信息的慣例，從軌跡數(shù)據(jù)的語義挖掘中吸取精華，在出行起訖點(diǎn)(停留)基礎(chǔ)上更進(jìn)一步挖掘子停留語義信息，并用活動(dòng)點(diǎn)特征參數(shù)對(duì)信

息進(jìn)行量化，利用子停留語義這一微觀信息推斷出行目的，并結(jié)合馬爾科夫鏈的相關(guān)研究，對(duì)軌跡數(shù)據(jù)進(jìn)行狀態(tài)層次劃分，推斷出行下一停留點(diǎn).該方法與傳統(tǒng)算法相比，對(duì)軌跡的研究更加深入細(xì)致，但其也有局限性：(1)要想獲得較為理想的結(jié)果，應(yīng)在海量數(shù)據(jù)支撐的條件下構(gòu)建判別信息庫，這是一項(xiàng)長期而又浩繁的工作，而且實(shí)現(xiàn)難度較大；(2)準(zhǔn)確性不夠高，因?yàn)橐粋€(gè)子停留也可能符合判別信息庫中的多條規(guī)則，使得出行目的的推斷有時(shí)顯得有些模棱兩可.

充分利用現(xiàn)有空間軌跡數(shù)據(jù)資源，智能化的提取出行信息，是一個(gè)前沿的研究領(lǐng)域.出行信息包括大量內(nèi)容，又因從枯燥的軌跡活動(dòng)點(diǎn)數(shù)據(jù)中挖掘語義信息本身就是復(fù)雜的系統(tǒng)問題，因此有效利用空間軌跡數(shù)據(jù)推動(dòng)交通調(diào)查的智能化任重而道遠(yuǎn).

參考文獻(xiàn):

[1]陳錦陽,劉良旭,宋加濤,等. 基于R-tree的高效異常軌跡檢測算法[J]．計(jì)算機(jī)應(yīng)用與軟件,2011, 28(10): 34-37.

[2]Spaccapietra S, Parent C, Damiani M L,etal. A conceptual view on trajectories[J]. Data and Knowledge Engineering,2008, 65(1):126-146.

[3]Wolf J L. Using GPS data loggers to replace travel diaries in the collection of travel data[D]. Atlanta: Georgia Institute of Technology, 2000.

[4] Griffin T, Huang Y, Halverson R. Computerized trip classification of GPS data[C]//2006-3rd International Conference on Cybernetics and Information Technology Systems and Applications. Orlando:CITSA，2006:20-23.

[5] 鄧中偉,季民河. GPS軌跡中出行目的提取的一種智能算法[J]．中國科技論文在線,2011, 4(12):1 064-1 070.

[6]竇麗莎,曹凱. 出行者子停留語義推斷模型框架[J]．山東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2012, 26(6): 17-22.

[7]竇麗莎. GPS軌跡信息的語義挖掘[D]. 淄博：山東理工大學(xué), 2013.

[8]張衡. 馬爾科夫鏈的一個(gè)應(yīng)用[J].長春光學(xué)精密機(jī)械學(xué)院學(xué)報(bào)，1994,17(3):44-49.

(編輯：郝秀清)

AsemanticinferencemodelforstopoftravelerbasedonGPS

LIUChun,CAOKai

(SchoolofTransportationandVehicleEngineering,ShandongUniversityofTechnology,Zibo255049,China)

Abstract:Traditional methods for vehicle trajectory characteristic analysis usually adopt filling the semantic information for the stop point. In this way, many problems have been caused such as making information collection complicate, leaving out information and making inconvenience in real-time processing. Aiming at this problem, on the basis of the above method, this paper puts forward the method of using Markov chain to infer the next stop point of the moving vehicle, based on mining the semantic information hiding in the GPS trajectory data directly. In this method, sub-stops are identified. The characteristic parameters (instant speed, the stay time, etc.) of the points in the vehicle moving trajectory are analyzed. Then, the above information is compared with the k-base to dig the semantic information of the sub-stops. In addition, the next stop point of the moving vehicle is inferred by dividing the vehicle running state level and counting the frequency of the sub-stops in each state level. Real vehicle test results show that the stability of the calculation results is improved by collecting more test data and dicing more state levels. The smaller the predicted range is, the less errors are produced when restoring the electronic map according to the percentage.

Key words:vehicle trajectory characteristic analysis; semantic information; sub-stops; Markov chain

中圖分類號(hào)：

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-6197(2015)04-0048-05

通信作者：

作者簡介：劉春，女，liuchun891229@126.com； 曹凱，男，caokailiu@sdut.edu.cn

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61074140)；山東省自然科學(xué)基金資助項(xiàng)目(ZR2010FM007)

收稿日期：2014-10-23