EN中文

Journal of Geo-information Science >

2014 , Vol. 16 >Issue 5: 720 - 726

DOI: https://doi.org/10.3724/SP.J.1047.2014.00720

Orginal Article

Research on the LBS Matching Based on Stay Point of the Semantic Trajectory

  • QI Lingyan , 1, 2 ,
  • CHEN Rongguo , 1, * ,
  • WEN Xin 1, 2
Expand
  • 1. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China
  • 2. University of Chinese Academy of Sciences, Beijing 100049, China
*Corresponding author: CHEN Rongguo, E-mail:

Received date: 2013-10-14

  Request revised date: 2013-12-04

  Online published: 2014-09-04

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

Location Based Service (LBS), with the support of GIS, is a thriving service for users related with coordinates received by wireless communication network or GPS. The trajectories composed with a set of received coordinates mainly express the character and habit of user’s behavior. Through analyzing and mining users’ trajectories, we will improve the efficiency of location based service. In this paper, firstly, the trajectories data including location coordinates and semantic fields are collected through GPS signal by the self-developed software installed in the terminal. The semantic fields contain the ID of user, current speed, nearby landmark and so on. Then the mistakes incorporated in raw trajectories due to the GPS instability should be filtered to enhance data accuracy. A method has been applied to filter the “jitter” points and to calculate the angle (angle threshold is 15°) and time interval (time threshold is 3s). Different from the conventional method that calculates mean value as the stay point’s coordinate directly, we divide the points in sub-trajectory into different groups based on semantic information. Afterwards, on the basis of the number of points in each group, we acquire weighted coordinate of the stay point. Finally, we match the stay points with POIs, which have ample information, like opening hours, special offers, etc., and then get a set of matched POIs around the stay point. In addition, through analyzing the interest and job of user, it could retrieve the more appropriate service and send it to user accordingly.

Key words： semantic trajectory; stay point; LBS; POI

Cite this article

QI Lingyan , CHEN Rongguo , WEN Xin . Research on the LBS Matching Based on Stay Point of the Semantic Trajectory[J]. Journal of Geo-information Science, 2014 , 16(5) : 720 -726 . DOI: 10.3724/SP.J.1047.2014.00720

1 引言

LBS（Location Based Service）是通过移动通讯网络获得用户位置信息,并最终为用户提供相应位置服务的增值业务[1]。近年来,人们可便捷地获取用户位置信息,将一段连续时刻的用户位置信息“串联”起来,就可形成该用户在该时间段内的行为轨迹数据[2]。在行为轨迹研究中,若用户在某一距离范围停留超过一定时间,则表示用户可能在某地游览或驻足,而非简单经过。此时,我们认为用户在这种停留状态下,接纳周围位置服务的可能性较高。而在位置服务中,如何有效地匹配服务是关键问题[3]。因此,本文旨在利用用户停留点信息,匹配周围的POI（Point of Interest）,向用户推送符合其潜在需求的位置服务。
很多学者都研究了轨迹停留点的计算方法。文献[4]中使用SmoT（Stops and Moves of Trajectories）算法提取停留点;文献[5]中采用CBSMOT提取轨迹停留点;文献[2]中根据时间阈值和距离阈值的线性聚簇法筛选出用户停留子轨迹。这些不同的方法在提取停留子轨迹后,都将子轨迹坐标的算术平均值作为轨迹停留点坐标[6]。然而,直接使用算术平均值作为停留点坐标,忽略了轨迹点本身所包含的有用信息,往往会出现偏离用户实际停留区域的情况。2007年Alvares等提出语义轨迹概 念[7-8],认为语义轨迹上的点包含除经纬度坐标、时间以外的语义信息,且这些语义信息隐含了在轨迹中可能发生的用户活动信息[9-10]。本文将语义信息融入到用户行为轨迹中,计算出包含地标等语义信息的语义轨迹停留点,精确度有所提高。此外,用户在停留的时候,对周围POI产生兴趣及响应请求的几率较大。利用停留点匹配POI可一定程度上满足用户的潜在服务需求。但是相关文献缺乏此类研究,忽略了停留点在位置服务推送方面的利用价值。如文献[11]采用了Voronoi图算法[12],通过计算轨迹与各关联区域的交点,可以推算出最匹配的POI点及轨迹受该POI点影响的持续时间,但没有进一步考虑轨迹停留点与POI的关系,本文对此进行了详细描述。

2 用户语义轨迹分析流程及预处理

2.1 分析流程

首先,将收集的原始用户轨迹数据进行过滤处理,获得精确度较高的轨迹数据;然后,计算语义轨迹的停留点坐标;结合用户个性化信息（爱好、职业等）,判断用户潜在位置服务需求类别;最后,匹配出用户停留点周围的POI信息,并将相应位置服务信息推送给用户（图1）。

2.2 轨迹预处理

2.2.1 数据来源
图1所示的原始用户语义轨迹数据是由装载着自主研发采集系统的智能手机提供。轨迹数据是通过GPS以及通讯基站信号采集,采集内容包括位置信息（经度、纬度、时间等）,以及语义信息(地标名称、用户编号等)。其中,语义信息中的地标名称是抓取当前位置点缓冲范围内最近的标志性建筑物信息。而用户编号可关联用户个性化信息表,提供该轨迹拥有者的职业、爱好等信息。其数据表结构如表1所示。
Fig.1 Flow Chart of Trajectory Analysis

图1 轨迹分析流程图

Tab.1 Semantic trajectory

表1 语义轨迹表

字段名 数据类型 意义
id int 编号
latitude int 纬度
longitude int 经度
time date 时间
owner int 用户
speed float 速度
landmark varchar(200) 地标
…… …… ……
2.2.2 轨迹过滤
移动终端采集的原始用户历史轨迹数据往往包含一些错误,其产生的原因有：终端网络信号不稳定、GPS信号被屏蔽、终端硬件故障等。在分析轨迹数据之前,必须先过滤这些错误点。过滤错误点的条件如下：
（1）过滤时间戳异常的轨迹点。
（2）过滤速率异常的轨迹点。
（3）过滤与建筑物、池塘等地物重合的轨迹点。即根据地物属性,提取研究区域的地物矢量文件（池塘、高楼等）,将其坐标范围与轨迹线进行叠置分析,判断是否相交,若相交,则不符合实际,予以删除。删除的点作“绕过”处理,即用轨迹与多边形的交点替代原有轨迹点。
（4）过滤“跳点”。即在规律的路径上有某些点突然偏离轨迹,跳到远处又回归轨迹[13]（图2（a）中P点）。“跳点”剔除步骤为：
① 遍历轨迹,除起点和终点以外,每个点P都有2个相邻的点P1,P2,该轨迹区间表示为traj={P1,P,P2};
② 获取P1,P,P2 3点经纬度,根据余弦定理,计算出以P作为顶点的角度∠P1PP2及P1和P2时间差t;
③ 若∠P1PP2小于角度阈值15°且t小于时间阈值3 s,则表示P为“跳点”,删除P点。其中角度阈值和时间阈值是通过观察多条用户轨迹,归纳“跳点”规律得出的经验值。由多次观测可知,实验中 GPS信号不稳定造成的“跳点”均呈现锋利锐角,且历时短暂。进一步计算“跳点”锐角,普遍小于15°（图3）。同时,为了避免轨迹中用户自然运动造成锐角轨迹的情况,引入时间阈值加以界定。即假定在正常状态下,用户不可能在3 s内以任何交通方式造成锋利锐角轨迹。
采用上述计算方法,图2（a）中∠P1PP2为11.9°（小于15°）且时间差为2 s（小于3 s）,符合剔除“跳点”规则,P点予以剔除。图2（b）是过滤“跳点”P后的轨迹数据图。
Fig. 2 Raw trajectory and trajectory after filtering the “jitter”

图2 过滤“跳点”前后轨迹对比

Fig.3 Angles of jitters (partial)

图3 部分跳点角度

3 用户语义轨迹停留分析及应用

3.1 语义轨迹停留点分析

原始轨迹过滤错误点之后,数据精确度提高,可进一步作数据分析。用户行为轨迹上的轨迹点分为行走和停留2个状态。行走指的是用户经过一定的区域,继续前行的状态。停留则表示暂时处于某区域,不继续前行。在位置服务领域,研究大多着眼于用户停留状态,因为在此状态下,用户有足够的时间查看位置服务信息,对推送的位置服务接纳度较高。
用户停留通常有2种情况：（1）用户进入建筑物内,在一段时间内失去卫星信号,直至再次到室外恢复信号;（2）用户在一定范围的空间区域内往返徘徊[13]。这2种情况都可以归纳为“在相对较长的时间内,移动范围较小”。
分析语义轨迹停留点过程如下：
语义轨迹（Semantic Trajectory,简写SemaTraj）是由点组成的序列,每个点(pi)包含经度（pi.lngt）、纬度(pi.lat)、速度(pi.v)、时间(pi.t)、用户(pi.owner)、语义信息{地标(pi.landmark)、地址(pi.addr)、联系电话(pi.tel)等}。因此,SemaTraj=p1→p2→⋯→pn,其中pi.t<pi+1.t。
语义停留子轨迹（Semantic Stop Trajectory, SST）：轨迹中表征出行者达成出行目的的特殊子轨迹[14]。即用户停留超过一定时间的子轨迹[15]。抽取子轨迹要考虑3个因素：时间阈值（θt）、距离阈值(θd)、地标(pi.landmark)。如果有一组点序列P={pm,pm+1, ⋯ , pn} , 其中,∀m<i≤n,满足以下条件：
Distance(pm, pi)≤θd并且|pn.t-pm.t|≥θt;
接着,将pi按照pi.landmark分组得到P′,
P′={(p11,p12,p13….p1num1),(p21,p22….p2num2), … ,(pk1,pk2
…pknumk)}。
则停留点Stay Point(Sp)=(lat, lngt, lamak, arvT, levT),即包含纬度、经度、地标、到达时间、离开时间。其中,
Sp.lat = w 1 ∑ w = 11 1 num 1 p w .lat + w 2 ∑ w = 21 2 num 2 p w .lat + … wk ∑ w = k 1 knumk p w .lat / ∑ i = 1 k numi
Sp.l ngt = w 1 ∑ w = 11 1 num 1 p w .long + w 2 ∑ w = 21 2 num 2 p w .long + … wk ∑ w = k 1 knumk p w .long / ∑ i = 1 k numi
传统算法中,停留点的坐标是停留子轨迹的算术平均值,可看成各个子轨迹点的权重均为1/ ∑ i = 1 k numi ,即权重平均分配,与语义特征无关。而本文计算停留点坐标时,将不同语义特征的点分组并赋予相应的权重,权重与该组点数成正比,即权重由下面两式联立可解：
w 1 × num 1 + w 2 × num 2 + … wk × numk = ∑ i = 1 k numi
wk= numk × L (L为常量)
结果为：wk=numk × ∑ i = 1 k numi / ∑ i = 1 k numi 2
除此之外,Sp.arvT=pm.t且Sp.levT = pn.t
Sp.landmark 是在{p1.landmark, p2.landmark, … , pk.landmark}集合中权重最大的语义信息。
轨迹停留点计算伪代码如下：
Algorithm NewStayPointDetection(sema_Traj, θt, θd)
Input: 原始语义轨迹sema_Traj,时间阈值θt,距离阈值θd
Output: 停留点集合S
1. i=0, pointNum=|sema_Traj|;
2. while i < pointNum do
3. for j←i+1 to pointNum do
4. begin
5. dist:= calDistance(Pi, Pj));
6. if dist < θd then
7. time=Pj.t-Pi.t
8. If time>θt then
9. for m←i to j+1 do
10. stayTaj.add(Pm)
11. s.lat = NewComputeLat(stayTaj);
12. s.lngt = NewComputeLngt(stayTaj);
13. S.add(s);
14. i: = j;
15. end
16. i := i + 1;
17. return S
Algorithm NewComputeLat (stayTaj)
Input: 停留轨迹stayTaj
Output: 停留点纬度lat
1. i=0, pointNum=|group_Traj|, result//按语义分组的轨迹集合
2. for i←0 to pointNum-1 do
3. if (!isContain(result,Pi.sema))
4. for j:=0 to pointNum do
5. if ( Pi.sema.equals(Pj.sema)
6. group.add(Pj)
7. result.add(group);
8. for r←0 to pointNum do
9. sum += result.Traj(r).size()*result.Traj(r).size();//计算平方和
10. w= pointNum /sum;//计算单位权重值
11. latSum=0;
12. for r←0 to resultNum do
13. for t←0 to result.Traj(r).size() do
14. groupSum+=result.Traj(r).Pt.latitude);//计算分组后纬度和
15. latSum +=groupSum*a* result.Traj(r).size();//计算分组后纬
度和乘上权重
16. lat= latSum/tempList.size();
17. return lat
将同一条用户轨迹,分别用传统方法与语义停留点方法计算停留点坐标,得到两组停留点坐标结果（表2）。传统方法是直接计算停留子轨迹中所有点的算术平均值作为停留点坐标。利用拾取坐标系统在地图上标绘两组停留点坐标,与用户实际停留区域对比（如图4所示红色矩形框标识）,落入停留区域的停留点表示计算正确,否则表示计算结果存在误差。通过这种方式统计出两种方法计算的正确率分别为76.8%和69.5%。由此可知,新方法计算停留点的正确率高于传统方法。因为传统方法不考虑轨迹点的语义信息,当轨迹点比较分散时,其算术平均值位于所有点的中央,很容易落在实际停留范围之外;而通过语义轨迹方法计算,用户停留时轨迹点比较密集、数目较多、权重较大,得出的结果也会更靠近实际停留区域。
Fig.4 Contrast of stay points by two different methods

图4 某个停留点计算结果对比图

Tab.2 Coordinates of stay points

表2 停留点计算结果统计表

序号 语义轨迹方法计算停留点结果 传统方法计算停留点结果
经度 纬度 经度 纬度
1 116.392198 40.009142 116.391907 40.009172
2 116.390877 40.008942 116.390834 40.008923
3 116.374965 40.066685 116.372644 40.065261
4 116.390364 40.008784 116.390368 40.008784
5 116.389654 40.008596 116.389824 40.008608
6 116.388505 40.008383 116.388320 40.008339
7 116.387017 40.008089 116.386879 40.008066
… …… …… …… ……

3.2 基于轨迹停留点的POI匹配应用分析

通常POI至少包含3个方面的信息：名称、类别、地理坐标[16]。其又称为“导航地图信息”,导航地图数据是整个导航产业的基石[17]。研究中扩充了POI信息,使其包含营业时间、特色描述、类别信息、停车信息等。同时,在用户注册时,提供个性化定制操作,引导用户完善个人信息（职业、兴趣爱好等）,并有效地利用这些信息,使得POI匹配结果更合理、准确。
在语义轨迹的停留点分析之后,结合POI信息库,以及用户兴趣、职业等方面信息,可以匹配出轨迹停留点（图5红色气泡点）周围的用户可能感兴趣的POI信息（图5蓝色白心气泡点）。其中,用户爱好及职业等信息可提高位置服务匹配的准确性。例如,某人偏好购物,即可将周围购物类的POI信息推送给用户;某人职业为IT工作者,可以将周围的电子产品POI信息推送给用户。除此之外,扩充后POI具有更加完善的商户信息,在服务推送过程中,其参考价值高于一般POI数据（图6）。例如,用户不仅可参考商户名称,还可据其营业时间、消费水平、停车情况进行合理选择。
Fig.5 POI around the stay point

图5 轨迹停留点周围POI点（右图为红色圆圈处放大图）

Fig.6 Details of POI

图6 匹配POI详细信息

4 结论

用户的移动轨迹在一定程度上体现了用户个人的行为模式, 而且也反映了不同人之间品味、爱好和生活习性的相似性[18-20]。本文对用户移动轨迹进行深入挖掘,采用新的加权算法计算用户停留点,相较传统的算术平均值计算方法,具有更高的精确性。获得停留点之后,匹配周围POI信息,为用户提供相应的POI详情推送服务,可以满足用户一定程度上的位置服务需求。在未来的研究工作中,可以在停留点研究的基础上,研究轨迹预测模型,即通过统计过去一段时间停留点序列的重叠度,预测用户即将到达的位置,这可在用户到达之前推送相应的服务信息,满足用户不同程度的服务请求。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
彭华. 移动位置服务[J].中国电子商情,2003(2):22-23.

[2]
陈康,黄晓宇,王爱玉,等.基于位置信息的用户行为轨迹分析与应用综述[J].电信科学,2013(4):118-123.

[3]
张德干,王冬.面向LBS的服务匹配方法研究[J].计算机科学,2012(3):19-22.

[4]
Alvares L O, Bogorny V, Kuijpers B, et al.A model for enriching trajectories with semantic geographical information[C]. Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems, New York, USA, 2007.

[5]
Tietbohl A, Bogorny V, Kuijpers B.A clustering based approach for discovering interesting places in trajectories[C]. SAC’08 March 1620, Fortaleza, Cear´a, Brazil, 2008.

[6]
Zheng Y, Zhang L, Ma Z, et al.Recommending friends and locations based on individual location history[J]. ACM Transactions on the Web (TWEB), 2011,5(1):3-9.

[7]
Alvares L O, Bogorny V, Kuijpers B, et al.Towards semantic trajectory knowledge discovery[J]. Data Mining and Knowledge Discovery, 2007.

[8]
Bogorny V, Kuijpers B and Alvares L O. ST-DMQL: A semantic trajectory data mining Query language[J]. International Journal of Geographical Information Science, 2009,23(10):245-1276.

[9]
Liu J, Wolfson O, Yin H.Extracting semantic location from outdoor positioning systems[C]. IEEE 7th International Conference on Mobile Data Management, 2006:73-73.

[10]
Josh Jia-Ching Ying, Wang-Chien Lee, Tz-Chiao Weng. Semantic trajectory mining for location prediction[C]. ACM SIGSPATIAL GIS '11,Chicago, IL,USA, 2011.

[11]
陈典全. LBS中基于轨迹的用户行为特征分析[J].全球定位系统,2011,36(6):58-61.

[12]
Xie K, Deng K, Zhou X.From trajectories to activities: A spatio-temporal join approach[C]. Proceedings of the 2009 International Workshop on Location Based Social Networks, ACM, 2009:25-32.

[13]
Kirmse A, Udeshi T, Bellver P.Extracting Patterns from Location History[C]. ACM SIGSPATIAL GIS '11, Chicago, IL, USA,2011.

[14]
窦丽莎,曹凯.出行者子停留语义推断模型框架[J].山东理工大学学报,2012,26(2):17-21.

[15]
Zheng Y, Zhang L, Xie X, et al.Mining interesting locations and travel sequences from GPS trajectories[C]. Proceedings of the 18th International Conference on World Wide Web, ACM, 2009:791-800.

[16]
周春辉,朱欣焰,苏科华,等.基于LBS的兴趣点查询与更新机制研究[J].微计算机信息,2009(25):143-145.

[17]

[18]
Eagle N, Pentland A.Reality mining: Sensing complex social systems[J]. Personal and Ubiquitous Computing, 2006,10(4):255-268.

[19]
Hung C, Chang C, Peng W.Mining trajectory profiles for discovering user communities[C]. Proc of the 2009 Int Workshop on Location Based Social Networks, New York, 2009.

[20]
Giannotti F, Nanni M, Pedreschi D, et al.Trajectory pattern mining[C]. Proc of the 13th ACM SIGKDD Int Conf on Konwledge Discovery and Data Mining, New York, 2007.

Options
Outlines

/

〈 〉