居民出行停留目的识别模型框架

刘　春，曹　凯，于　云, 黄肖肖

(山东理工大学 交通与车辆工程学院，山东 淄博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