居民出行停留目的識別模型框架

劉　春，曹　凱，于　云, 黃肖肖

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

?

居民出行停留目的識別模型框架

劉春，曹凱，于云, 黃肖肖

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

摘要：居民出行軌跡通常以樣本數據點的形式呈現出來，未經語義信息化處理的樣本數據點無法理解出行者的目的.提出了一種新的算法，從居民出行樣本數據中挖掘居民出行GPS軌跡的語義，通過解釋出行軌跡的停止與運動，對出行軌跡進行活動識別，推斷出行停留目的.該算法通過分析軌跡數據點的物理幾何特性(停留時長、轉角、速度)，判斷軌跡中的停留，然后，利用領域知識建立的判別信息庫進行對比，推斷出居民停留目的.實驗數據驗證了算法的可行性.

關鍵詞：語義軌跡; 運動行為; 運動與停留; 判別信息庫; 算法

隨著GPS和RFID等移動設備的廣泛應用，大量的出行移動數據得以產生.這些數據為我們尋找運輸管理、動物遷徙以及居民出行等的規律提供了新的途徑[1].在對居民出行目的和行為進行研究時，通常的做法是對其出行軌跡數據進行采集和分析研究，挖掘其中隱藏語義和運動規律.

目前，針對軌跡數據的語義分析和挖掘已展開一些相關工作，如Guc等通過增加軌跡的條件信息，開發了一種讓使用者可以對興趣點手動標注軌跡語義的方法[2].Spaccapietra在2008年提出了第一個從概念的角度觀察軌跡特性的SMoT數學模型.在該模型中，只能根據數據搜集地區的多種地理信息，確定一條軌跡上一系列停止的重要地點[3].另一種常用的CB-SMOT 方法只能發現低速度區，如果這些區域不相交于一個已知的地理位置，就會被標記為未知停止.Alvares等人只依據軌跡方向的變換提出了一種停止實例化的算法[4].文獻[5]通過尋找低于軌跡平均速度的地點，計算軌跡中被關注的重要地點.在國內，張治華，鄧中偉等人對相關背景信息類型進行了歸納和定義，利用機器學習數據挖掘技術(主要為C5.0算法)，建立了出行目的與多屬性變量的關系，進行出行目的的智能化提取[6-7].

已有各國學者對居民出行軌跡的相關研究，大都以軌跡的宏觀背景信息，如出行起訖點、出行者個人等信息為依據，作為居民出行目的判斷的基本條件.軌跡的基本宏觀信息可以從GPS軌跡數據中直接提取，宏觀信息中包含經緯度以及速度、方向等，其表面含義簡單而明了.但結合相應的領域知識和算法挖掘隱藏在軌跡內部的居民出行目的語義卻是一件富有挑戰的工作.為此，本文著眼于GPS軌跡信息中的微觀活動分析研究，提出新的算法以便辨識GPS軌跡信息中的停留點，即停留和子停留，挖掘各停留點活動特性(時長、速度、轉角)，分析居民出行活動的內在停止行為，應用相關領域知識自動理解和推斷居民出行活動的未來趨勢軌跡，從而推斷出行者的出行目的.

1定義及子停留辨識

1.1相關定義

定義1軌跡(Trajectory)：移動對象位置變化的表征，由一系列的時空點集組成，即移動對象為抵達目的地所進行的空間移動的集合.

定義2軌跡背景(Trajectory Background)：用來判斷為什么在給定的時間間隔內移動的物體會停止的一組影響因素.

定義3停留(Stop)：軌跡中表征出行者達成出行目的的特殊子軌跡，由數組(∑[]，minΔt)表示.其中集合∑[]為任意拓撲閉多邊形，minΔt≥0表示最小停留時間[8].

定義4子停留(Sub-stops)：停留中表征某一出行目的的一段子軌跡，由數組([],Δv,Δt)表示.其中[]?∑[]，[]為某一拓撲閉多邊形，max(v) ≥Δv≥0,max(t) ≥Δt≥0,max(v),max(t)表示速度和時間閥值，Δv，Δt為速度和時間的變化量[8].

1.2停留及子停留的辨識

當居民出行處在停留活動狀態時，往往對應著一些顯著的地理位置，因此識別出停留即可獲得居民出行目的的一個大致范圍.在該活動范圍中，居民仍可進行另外的活動，從而產生一些子停留，而這些子停留則對應著居民不同出行目的.如：出行者在進入商城中，可能從事吃飯、購物、看電影等多種活動，如圖1所示.因此，為探究出行者的出行目的，需進一步對出行中的子停留進行辨識(即到底是吃飯、購物，還是看電影等)，并獲取其語義信息.

圖1　軌跡的語義概念描述

本文運用IB-SMoT[5]算法進行停留的識別.該方法主要運用基于路網的經驗探索方法，將軌跡與電子地圖相匹配，尋找二者重合部分，再根據重合時間閥值辨識出停留.為了確定移動對象在停留內的不同子軌跡，本文應用基于方向或速度變化的停留計算聚類算法，產生一個新的停止點，這些新的停止點即為所說的子停留.具體算法過程見表1.

表1停留及子停留辨識算法

INPUT: T//oneGPStrajectoryOUTPUT: S//asetofstops B//asetofsubstopsMETHOD: Stops->IB-Cluster//calculatethestops subStops->CB-SMoT(S)//computelowspeedclustersforallstops subStops->subStops+DB-SMoT(S)//findsubstopswherethedirectionofmovingobjecthaschanged ENDMETHOD

由于上述算法是根據速度的變化和方向變化計算子停留的，為此，需調用函數CB-SMOT[9-10]以便計算所有停止的低速度集群，然后調用能發現集群移動方向發生改變的DB-SMOT算法來確定子停留.

2出行目的推斷算法

2.1k-base的建立

在推斷出行目的時，需要建立由一系列規則組成的判別信息庫(k-base)對子停留進行檢驗.其中，k-base 的每一個規則都對應著不同的活動信息，這樣就可以檢測出移動對象訪問過的地方以及其在這些地方都干了什么.k-base是在大量的出行調查與分析的基礎上得出的一般狀況，其主要判別規則為居民出行的各種目的類型和與之對應的特征參數閾值.將子停留的數據信息與k-base給出的判別規則進行比較，看其是否滿足一個或者多個規則，從而獲知子停留活動類型，見表2.

表2商場k-base

Min-Time/hMax-Speed/km·h-1Max-Direcito/(°)Goal2.500看電影11.530購物80.515工作

2.2出行目的推斷算法

在進行上述子停留的推斷時，如果低速度集群經過DB-SMoT算法處理，生成了非空集合子停留，那么下面的算法會將其生成的子停留運用判別信息庫規則進行判別，推斷其出行目的.在進行目的推斷時，輸入的是一組子停留和判別知識庫規則，輸出的是情景子停留，即出行目的.對每個子停留，運用判別信息庫的規則，將其時間、速度和方向變化與判別信息庫中的時間閥值和速度閥值進行比較，如果子停留的速度變化低于或者等于該規則的速度變化，并且方向變化低于或者等于該規則的方向變化時，就比較子停留的時間與判別信息庫的時間閥值；如果停留時間等于或者大于判別信息庫中的最小時間閥值，那么子停留即為滿足判別信息庫的該規則，其出行目的即為判別信息庫中的相應活動類型，算法見表3.

3實例驗證

在淄博市人民公園進行居民出行數據收集，對每位進入公園的人進行問卷調查，確定人民公園的出行活動判別信息庫，見表4.

表3出行目的推斷算法

INPUT:substops//子停留k-Base//判別信息庫OUTPUTGoal//出行目的METHOD:FOReachsubstopDO//對每個子停留計算如下timesubstop=endTime(s)-startTime(s);//停留時間directionsubstop=getDirectionVariation(s);//平均轉角 speedsubstop=getSpeedVariation(s);//平均速度FOReachrulerinkBaseDO//對每條規則r如下運算 maxDirectionOfRule=getMaxDirection(r);//方向閥值maxSpeedOfRule=getMaxSpeed(r);//速度閥值minTimeRule=getMinTime(r);//時間閥值IF(speedStop<=maxSpeedOfRule ANDdirectionStop<=maxDirectionRule)IF(timeStop>=minTimeRule)s.addGoal(r.getGoal);//停留目的ENDIFENDIFENDFORENDFORENDMETHOD

表4人民公園判別信息庫

實驗得到160條軌跡，運用基于密度的活動點聚集法，以15m為最小半徑閾值，以20min為時間閾值，共獲得402個子停留.對獲得的子停留進行特征參數計算，并將獲得的特征參數與判別信息庫中的特征參數閾值進行對比，確定相對應的活動類型.在402個子停留中，有160個能夠被推斷出停止目標，從而獲得具體的活動類型.需要注意的是，當最短停留時間相同的情況下，也會對應著不同的活動類型，如散步和遛狗.由于篇幅限制，本文僅展示一條軌跡的處理結果.如圖2所示為軌跡1及其5個子停留，5個子停留中有3個可以推斷出其活動類型.表5為軌跡1中子停留的特征參數.

圖2　軌跡1中的子停留

表5軌跡1中子停留的特征參數

編號Min-Time/hMax-Speed/km·h-1Max-Direcito/(°)Goal252254.533.8散步253202548未知2544524.6236.8跑步2555024.652.2未知2562517.688.4遛狗

在上述的推斷結果中編號255所對應的活動為未知，而其真實活動為跑步，出現偏差，其余各點的推斷均為正確活動，正確率達到80%.

4結束語

本文基于對移動對象軌跡數據的分析，利用先驗經驗建立起判別信息庫，推斷出移動對象出行軌跡中隱藏的活動類型.該方法打破了傳統的對移動對象出行分析僅限于出行起訖點分析的層次，進一步在整個軌跡中進行微觀活動分析，利用數據挖掘的知識，挖掘隱藏在軌跡內的有用信息.但該方法還存在一定的局限性：(1)為了有利于活動目標的推斷決策，該方法僅與電子地理信息系統相結合，沒有考慮人文社會價值屬性等方面的因素；(2)對于一個子停留對應多個活動目標的情況，在進行活動目標取舍決策時會出現一定的誤差.在以后的研究中需要對以上問題進行進一步探索，提高活動推斷的準確率.

參考文獻：

[1] Moreno B,Times V C,Renso C,etal.Looking inside thestops of trajectories of moving objects[C]//Geoinfo.,2010:9-20.

[2]Guc B, May M, Saygin Y,etal. Semantic annotation of GPS trajectories [C] // 11th AGILE International Conference on Geographic Information Science. Berlin: Springer, 2008:1-9.

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

[4] Alvares L O, Bogomy V, Kuijpers B,etal. A Model for enrichingt trajectories with semantic geographical Information [C]//ACM-GIS'07. Washington:2007:1-8.

[5] Ester M, Kriegel H P, Sander J,etal.A density-based algorithm for discovering clusters in large spatial databases with noise [C]// Proceeding of the Second International Conference on Knowledge Discovery and Data Mining (KDD 96) . 1996,96(34):226-231.

[6] 張治華. 基于GPS軌跡的出行信息提取研究[D]. 上海: 華東師范大學, 2010.

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

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

[9] Palma A T,Bogomy V,Kuijpers B,etal.A clustering based ap-proach for discovering interesting places in trajectories[C]// SAC08 . 2008:863-868.

[10] Nanni M, Pedreschi D. Time-focused clustering of trajectories of moving objects[J]. Journal of Intelligent Information Systems,2006, 27(3):267-289.

(編輯：郝秀清)

A recognition model framework of the purpose of stops for traveler

LIU Chun, CAO Kai, YU Yun, HUANG Xiao-xiao

(School of Transportation and Vehicle Engineering, Shandong University of Technology, Zibo 255049, China)

Abstract:Residents travel trajectories are usually in the form of sample points, without semantic information processing. It is difficult to understand the purpose of the traveler. This paper presents a new algorithm. The semantic information is dogged out from the GPS trajectory by explaining stops and moves and recognizing the activities hidden in the trajectory. Then the goal of the stop can be inferred. This algorithm recognizes the stops of the trajectory in the way of analyzing the physical geometry characteristics (the stay time,angle of rotation, speed, etc.) of the data points. In order to infer the goal of each stop, the stops are compared with the k-base. Experimental data verifies the feasibility of the algorithm.

Key words:semantic trajectory; moving behavior; move and stop; k-base; algorithm

中圖分類號：U121;TP391

文獻標志碼：A

文章編號：1672-6197(2016)02-0023-04

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

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

收稿日期：2015-01-21