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

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

?

居民出行停留目的識(shí)別模型框架

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

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

摘要：居民出行軌跡通常以樣本數(shù)據(jù)點(diǎn)的形式呈現(xiàn)出來(lái)，未經(jīng)語(yǔ)義信息化處理的樣本數(shù)據(jù)點(diǎn)無(wú)法理解出行者的目的.提出了一種新的算法，從居民出行樣本數(shù)據(jù)中挖掘居民出行GPS軌跡的語(yǔ)義，通過解釋出行軌跡的停止與運(yùn)動(dòng)，對(duì)出行軌跡進(jìn)行活動(dòng)識(shí)別，推斷出行停留目的.該算法通過分析軌跡數(shù)據(jù)點(diǎn)的物理幾何特性(停留時(shí)長(zhǎng)、轉(zhuǎn)角、速度)，判斷軌跡中的停留，然后，利用領(lǐng)域知識(shí)建立的判別信息庫(kù)進(jìn)行對(duì)比，推斷出居民停留目的.實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了算法的可行性.

關(guān)鍵詞：語(yǔ)義軌跡; 運(yùn)動(dòng)行為; 運(yùn)動(dòng)與停留; 判別信息庫(kù); 算法

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

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

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

1定義及子停留辨識(shí)

1.1相關(guān)定義

定義1軌跡(Trajectory)：移動(dòng)對(duì)象位置變化的表征，由一系列的時(shí)空點(diǎn)集組成，即移動(dòng)對(duì)象為抵達(dá)目的地所進(jìn)行的空間移動(dòng)的集合.

定義2軌跡背景(Trajectory Background)：用來(lái)判斷為什么在給定的時(shí)間間隔內(nèi)移動(dòng)的物體會(huì)停止的一組影響因素.

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

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

1.2停留及子停留的辨識(shí)

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

圖1　軌跡的語(yǔ)義概念描述

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

表1停留及子停留辨識(shí)算法

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

由于上述算法是根據(jù)速度的變化和方向變化計(jì)算子停留的，為此，需調(diào)用函數(shù)CB-SMOT[9-10]以便計(jì)算所有停止的低速度集群，然后調(diào)用能發(fā)現(xiàn)集群移動(dòng)方向發(fā)生改變的DB-SMOT算法來(lái)確定子停留.

2出行目的推斷算法

2.1k-base的建立

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

表2商場(chǎng)k-base

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

2.2出行目的推斷算法

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

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

在淄博市人民公園進(jìn)行居民出行數(shù)據(jù)收集，對(duì)每位進(jìn)入公園的人進(jìn)行問卷調(diào)查，確定人民公園的出行活動(dòng)判別信息庫(kù)，見表4.

表3出行目的推斷算法

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

表4人民公園判別信息庫(kù)

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

圖2　軌跡1中的子停留

表5軌跡1中子停留的特征參數(shù)

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

在上述的推斷結(jié)果中編號(hào)255所對(duì)應(yīng)的活動(dòng)為未知，而其真實(shí)活動(dòng)為跑步，出現(xiàn)偏差，其余各點(diǎn)的推斷均為正確活動(dòng)，正確率達(dá)到80%.

4結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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]. 上海: 華東師范大學(xué), 2010.

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

[8]竇麗莎，曹凱.出行者子停留語(yǔ)義推斷模型框架[J].山東理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，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

中圖分類號(hào)：U121;TP391

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

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

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

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

收稿日期：2015-01-21