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

劉　春，曹　凱

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

?

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

劉春，曹凱

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

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

關鍵詞：車輛運動軌跡分析;語義注釋;子停留;馬爾可夫鏈

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

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

1　出行者出行軌跡數據

1.1出行原始數據的獲取

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

1.2 數據預處理

目前全球定位系統使用的是WGS-84坐標系，它是一種國際地心坐標系，為方便后期數據處理，需要進行坐標系轉換，以WGS84的參考橢圓體為基準進行高斯投影，利用EXCEL簡易的進行GPS坐標轉換.

對GPS軌跡數據進行語義挖掘，獲取出行者信息的過程中，用到一些基本的數據計算，其中比較基本的兩個量值是點間距和轉向角，它們能夠表征軌跡的基本信息.GPS點間距離使用如下公式進行計算[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.相鄰軌跡段的轉向角反映了軌跡運動的趨勢，連續軌跡段在軌跡點處的夾角表示為α，軌跡的轉角表示為θ，夾角α和轉角θ關系如圖1所示，計算公式如下：

(7)

(8)

圖1　軌跡轉角示意圖

2　判別信息庫的建立及停留點的辨識算法

2.1判別信息庫構建

GPS記錄的軌跡數據中必然有明確的起迄點，其中迄點即為停留.如果為多目的出行，那么在整個行程中的GPS軌跡數據中必然會有多個起迄點，整個行程中的這些迄點即為子停留.無論停留還是子停留都隱含著出行者的某種目的，因此必然對應與目的相關的地理位置.通過將停留或子停留與GIS相匹配，以停留或子停留點為中心，以適當的步行距離(如5~10m)為半徑，尋找停留或子停留附近的實際地理環境，以此將沒有語境意義的GPS數據點語義化，并根據子停留語義信息，獲得子停留的活動類型.

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

表1辦公大廈判別信息庫

活動點特征參數活動類型Min-Time/hMax-Speed/km·h-1Max-Direction/(°)0.581.50450路過上班

2.2算法

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

3　下一停留點推斷

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

3.1模型條件

系統在每一時刻(或每一步)上的狀態，僅僅取決于前一時刻(或前一步)的狀態.這個性質稱為無后效性，即所謂的馬爾可夫假設.具備這個性質的離散型隨機過程，稱為馬爾可夫鏈[8]. 用數學語言來

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

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

描述即

如果對任一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)

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

3.2數據處理

原始的車輛GPS軌跡輸出如圖2所示，根據前面所述可以判斷軌跡點密集區域為停留和子停留，在進行模型構建時，將停留與子停留區域簡化為點集.由于新的點集軌跡高程坐標波動范圍大，因此軌跡跨越區域大.在進行活動狀態層次劃分時，如此大區域跨度，如若劃分較少的狀態層次，則預測精確度會降低；如若劃分較多狀態層次，則計算量會大大增加，給預測帶來不便.針對上述問題，需要對原始GPS軌跡數據進行預處理.這里利用前后兩點位置高程坐標取平均值法，使得軌跡的跨度范圍縮小，方便進行層次劃分，具體方法如圖3所示.

圖2　原始車輛軌跡圖

圖3　模型數據處理圖

3.3模型應用

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

圖4　狀態層次圖

在進行系統預測時，首先假定：

(1)預測期內系統狀態數保持不變.

(2)系統的狀態轉移概率矩陣不隨時間而變化.

軌跡在t=0時處于4個狀態的概率是相同的，即起點的選取是隨機的.因此，初始狀態概率向量可定義為

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

(0.25,0.25,0.25,0.25)

設軌跡在ti時刻處于狀態層次j(j=1，2，3，4)，在ti+1時刻處于層次kj+1，就說明軌跡進行了狀態轉移，記狀態轉移概率為pij,則

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

(10)

各個狀態轉移概率矩陣P為

(11)

轉化為矩陣形式為

P(k)=Pk,k≥1

在進行7步預測時可具體為P(7)=P7.如果已知轉移矩陣以及初始狀態概率向量，則任意時刻的狀態概率分布可以確定為

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

則上式可寫為

P(k)=P(0)P(k)=P(0)P(k).此時，進行第7步的狀態預測，即對模型進行7步狀態轉移，得到

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

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

[0.230 9 0.168 7 0.167 5 0.432 8]

(12)

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

如圖5所示，根據上述狀態層次概率計算結果，結合校園電子地圖可推斷實驗在第8步時，可能由山東理工大學東校移動到淄博人民公園西側的豬龍河.

圖5　試驗車在第8個周期時的停留地

4　結束語

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

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

充分利用現有空間軌跡數據資源，智能化的提取出行信息，是一個前沿的研究領域.出行信息包括大量內容，又因從枯燥的軌跡活動點數據中挖掘語義信息本身就是復雜的系統問題，因此有效利用空間軌跡數據推動交通調查的智能化任重而道遠.

參考文獻:

[1]陳錦陽,劉良旭,宋加濤,等. 基于R-tree的高效異常軌跡檢測算法[J]．計算機應用與軟件,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]．山東理工大學學報：自然科學版，2012, 26(6): 17-22.

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

[8]張衡. 馬爾科夫鏈的一個應用[J].長春光學精密機械學院學報，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

中圖分類號：

文獻標志碼：A

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

通信作者：

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

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

收稿日期：2014-10-23