搜索路网空间中时空相似轨迹
开篇：润墨网以专业的文秘视角，为您筛选了一篇搜索路网空间中时空相似轨迹范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要 为了分析移动对象行为特征，需要一种度量轨迹间相似性的方法，虽然在欧氏空间检索移动对象相似轨迹的研究较多，但在路网空间这种研究还不多见。在实际应用方面，大多数移动对象位于路网空间而不是欧氏空间。本文研究了路网空间相似轨迹的特性，并提出了一种在路网空间搜索相似轨迹的度量方法。实验结果表明该方法不仅是搜索相似轨迹的实用技术，也是一种较好的轨迹聚类方法
关键词 移动对象；轨迹；路网空间；相似轨迹
中图分类号 TP311 文献标识码
A
Searching for Spatio-Temporal Similar Trajectories on Road Networks
ZHANG Yan-ling1LIU Jin-peng2
1（Henan School of Light Industry, Zhengzhou , Henan 450006，China）
2(Zhengzhou School of Trade and Industry, Zhengzhou , Henan 450007, China)
【Abstract 】 In order to analyze the behavior of moving objects, a measure for determining the similarity of trajectories needs to be defined. Although research has been conducted that retrieved similar trajectories of moving objects in Euclidean space, vey little research has been conducted on moving objects in the space defined by road networks. In terms of real applications, most moving objects are located in road network space rather than in Euclidean space. In this paper, we investigate the properties of similar trajectories in road network space. And we propose a method to retrieve similar trajectories based on this observation and similarity measure between trajectories on road network space. Experimental results show that this method provides not only a practical method for searching for similar trajectories but also a clustering method for trajectories.
【Key words】Moving Objects;Trajectories;Road Network Space;Similar Trajectories
0 引言
随着移动计算的迅速发展，有效处理移动对象的研究变得越来越重要，该移动对象的动态特性由（x,y,t）空间中的一组线段来描述。移动对象的轨迹包含着大量信息，所以在实际应用领域分析轨迹具有重大意义，其中最重要的需求之一就是搜索具有相似轨迹的对象并对其进行聚类。
近年来涌现出大量的在欧氏空间检索移动对象相似轨迹的研究，而在路网空间该项研究还很少。但是对于大多数的实际应用来说，我们感兴趣的是路网空间中的移动对象而不是欧氏空间中的。为了分析路网空间移动对象的行为特征，需要设计一种度量移动对象相似性的方法，该度量方法可用于相似轨迹检索及聚类。
由于路网空间的特性，能用来搜寻相似轨迹的方法与当前所用的不同[1][2]，当前的方法具有以下不足：
首先，他们应用于欧氏空间。在路网空间中欧几里德距离不再适用，路网距离被相邻公路所限制。其次，以前应用的方法没有充分利用轨迹的时间空间特性，大多数只考虑了空间相似性。例如，在不同时间段经过同一区域的两条轨迹被认为是相似的，尽管它们在时空场景并不相似。
我们的研究由两方面需求所驱动：第一，我们的方法应该基于路网空间移动对象的特性；第二，我们应该同时考虑时空相似性而不仅仅是空间相似性。基于以上观点，我们提出了一种路网空间中移动对象相似轨迹搜索方法。我们的方法基于时空特性并反映了路网的空间特点。
1 路网移动对象轨迹相似性研究
大部分移动对象位于路网空间而不是欧氏空间。图1表示出了欧氏和路网空间中距离的不同定义。在图1中，从a到b的实际距离不是4公里而是9公里。
路网空间移动对象间距离具有一个有意思的特征。假设两条移动轨迹，TRA和TRB在相同时间经过相同点a、b、c，然后它们走向不同道路，如图2（a）所示。那么在点c后它们间的距离迅速增加，如图2（b）所示。在多数情况下，不同路段的两个移动对象间距离相当大，用相似性搜索时会导致超出距离阈值，如图2(b)所示。这意味着计算不同路段上的两个移动对象间的距离是无意义的。
（a）
(b)
2 路网相似轨迹的搜索
2.1 搜索方法分析
为了搜索路网相似轨迹，我们可以应用以下方法：
方法1：基于轨迹间的时空距离搜索相似轨迹。
方法2：先基于时间距离过滤轨迹，再基于空间距离精确找出相似轨迹。
方法3：先基于空间距离过滤轨迹，再基于时间距离精确找出相似轨迹。
方法1看起来简单有效，为了应用该方法我们需要定义一个鲁棒的时空距离，它可以是空间和时间距离的总和，但是不太容易定义时间和空间距离的等价值。例如，如何定义与一分钟时间相等的空间距离？当然在特定的环境下通过设置参数可以定义一个等式，如:dist(1米)=dist(幻)，然而多数情况下，通用的等式不容易定义，要依赖应用的上下文环境。
为了用方法2过滤轨迹需要定义时间或空间相似性，实际应用中难以判断两时间间隔距离的意义。因此，我们采取第三种方法来搜索相似轨迹。
2.2 空间相似性定义及时间距离定义
我们提出一种实用的基于POI（Point Of Interest）的轨迹空间距离计算方法。道路交叉口或重要地点被认为是POIs，如果两条轨迹通过相同的POIs,则根据如下定义认为是相似的：
定义1路网轨迹的空间相似性
假设P是给定路网的一组POIs，则轨迹TRA、TRB的空间相似性定义为：(1)
为了应用方法3来搜索相似轨迹，除了空间相似性外，还需要一种时间相似性的度量标准。时间相似性与时间距离是相反的。当给定了POI后，时间距离就能定义。如下是经过相同的POI的两个移动对象的时间距离：
定义2对于某个POI的轨迹时间距离
假设p∈P, P是某个POI，那么两条轨迹TRA和TRB间的时间距离定义为：
（2）
如果TRA、TRB都不通过p,则认为时间距离无意义。
如果我们认为t(TR,pi)是任一个轨迹TR经过第i个POI的时间，则t(TR)=(t(TR,p1),t(TR,p2),….t(TR,pk)被标示为k维空间的一个点，k是POIs的个数。那么k维时间距离定义为Lp。
定义3对于一组POIs的轨迹时间距离
假设P是一组POIs，TRA、TRB是两条轨迹，则TRA、TRB间的时间距离是：
（3）
2.3 相似轨迹搜索算法
算法1 搜索相似轨迹
输入：轨迹TRIN、阈值δ、查寻轨迹trQ、POI组P
输出：相似轨迹组TROUT
Begin
TRcandidate Ф
Trout Ф
For each tr∈TRIN
If p P, p is ontr
then TRcandidate TRcandidate∪{tr}
For each tr TRcandidate
If distT(trQ,tr,P) < δ
then TROUT TROUT∪{tr}
return TROUT
End
算法1描述了本文所提方法的搜索过程，由两大步骤组成：基于空间相似性的过滤步骤和基于时间距离的精确提取步骤。
注意：本文中我们用L2距离作为相似性测量粒度，但也能应用其他距离类型。当每条轨迹在多维空间表示为一个点时我们能应用聚类方法，称这种多维空间为时间轨迹空间（Temporal Trajectory Space），针对该时间轨迹空间已提出了大量的聚类方法。
3 实验结果
为了验证上述方法的可行性，我们应用某一城市出租车的实际轨迹数据进行实验，并基于前文所提出的搜索方法对轨迹实施聚类。第一步，我们筛选出所有经过4条给定POIs的轨迹，第二步，用Hilbert曲线法聚类时间轨迹空间点。
图3显示了第一步的结果，这些轨迹都通过给定的POIs，x轴是轨迹的偏移量，y轴指通过POIS的时间，标在右边的簇由第二步所发现。可以看出这个结果与我们直观的聚类相对应。
4 总结
路网轨迹相似性分析具有许多潜在应用，如通过分析某一条路上出租车的轨迹来帮助制定市场策略。本文中我们揭示了路网轨迹的重要特性，提出了路网相似轨迹的搜索方法。
我们的方法与以前方法有两方面不同：首先，我们的方法完全利用了路网空间的特性，而以前的方法主要用于欧氏空间；其次，我们的方法考滤了时空相似性，而以前的方法仅考滤空间相似性。
参考文献
[1] 张延玲，刘金鹏，姜保庆.移动对象子轨迹段分割与聚类算法[J].计算机工程与应用，2009（10）:65-68.
[2] Liu Jin-peng, Zhang Yan-ling, Liu Gang. Partition and Density-based Clustering for Moving Objects Trajectories[C]. Proc. 3rd ICCSE, Henan, China, July 2008:182-187.
[3] H.Cao,N.Mamoulis, and D. W. Cheung. Discovery of periodic patterns in spationtemporal sequences. In TKDE’07.
[4] J. Gudmundsson, P. Laube, and T. Wolle. Movement patterns in spatio-temporal data. In Encyclopedia of GIS 2008.
[5] Zhenhui Li, Ming Ji, Jae-Gil Lee. MoveMine:Mining Moving Object Databases. In SIGMOD’10, June 6-11, 2010.
[6] J.-G. Lee, J.han, K.-Y. Whang. Trajectory Clustering: A PartitionCandCGroup Framework. SIGMOD’07, Beijing ,China, June 2007.
[7] M. Nanni ,D. Pedreschi . Time-focused clustering of trajectories of moving objects. J Intell Inf Syst, vol 27,pp.267-289,Nov. 2006.
[8] P. Kalnis, N. Mamoulis,and S. Bakiras. On Discovering Moving Clusters in Spatio-temporal Data. Advances in Spatial and Temporal Databases,Springer Berlin/Heidelberg,volume 3633,2005.
[9] S. Gaffney, A. Robertson, P. Smyth, S. Camargo, and M. Ghil. Probabilistic Clustering of Extratropical Cyclones Using Regression Mixture Models. Technical Report UCI-ICS 06-02, University of California, Irvine, Jan. 2006.