我们的生活：评估日常位置轨迹的相似度

1、我们的生活：评估日常位置轨迹的相似度James Biagioni1 and John Krumm2 1 Department of Computer Science, University of Illinois at Chicago, Chicago, IL, USA 2 Microsoft Research, Microsoft Corporation, Redmond, WA, USA jckrumm 摘要。我们开发和测试的算法是基于GPS记录的个人日常位置轨迹的相似度的评估。一份精确的 相似度评估可以被用来发现异常行为，聚类相似的天数，并且预测未来的旅程。

2、我们根据30 名志愿测试者的46天的GPS轨迹，收集了一份平均数据。每个测试者每天随机匹配并且被要求评 估它们的相似度。我们测试了8种不同的相似度算法以准确再现我们的测试者的评估结果，并且 我们的统计测试发现有2种算法比其他算法优秀。我们也成功的运用其中一种相似度算法于通过 使用位置轨迹聚集相似的天数。 关键词：位置轨迹，相似度，异常检测，聚类。1 介绍 消费者和企业都意识到了通过位置轨迹来了解日常习惯和预测临时的需求的价值，并且安装了GPS的智能手机的大量使用使得这些更容易收集。这些轨迹可以帮助我们了解日常活动；特别的是，我们可以使用位置轨迹发现异常的天和聚类相似的天，以使得更好的了解我们的

3、日常行程。这两个任务都需要一种方法来比较这些天和其他的不同。 本文开发和测试算法测算相似天数来表示位置轨迹，从真实用户的相似性评估测试。通过可靠的方法测算相似度，我们可以发现与其它截然不同的异常天数，比如暗示混淆（一个重要的在人群中检测到认知障碍的用户的现象）或者某种习惯的改变。我们也可以将属于一起的天数做出合理的归类来获取他们的变化并且预测一天会如何发展，为未来适应系统的影响力提供有用的基础知识。我们相信这是第一次使用位置轨迹以人类的评估的方式来测算天数的相似度。 各种各样的传感器可以用来描述一天的数据，比如测算一个人的手机，台式电脑，车辆，社交网站，生物识别传感器等等活动。我们的工作是针对

4、位置轨迹，通常使用GPS来测算。这样的一个好处是，位置是一个持续存在的状态（如果不是总是可以测量的话），而不是基于事件的活动，比如短信活动，这只是偶尔发生。大多数人的位置也是不断变化的并且在户外是易于使用GPS来测算的。这些特征使得位置成为一个很方便的测算天数之间的相似度的变量。地理信息系统社区已经广泛的关注位置轨迹的相似度，比如，【1】，但是这些努力主要是机器处理过程。我们感兴趣的是匹配人类评估的相似度，这似乎更常见于异常检测的研究中。在【2】中，Ma从GPS轨迹中检测到的异常首先呈现一个正常轨迹作为地面矩阵序列的结果。如果一个新的矩阵轨迹与其他正常轨迹完全不同，那么一个异常会被申明。这里的

5、相似度测算是明确的，它依赖于一个在正常行程和查询行程之间的地理差异的数量测算。同时它也忽略的时间。在【3】中，Patterson等进行了基于GPS跟踪的异常行为检测。他们基于一个人的历史GPS轨迹建立了一个动态的概率模型。如果建立的模型的不准确度超过了一般先验模型，那么系统就会申明一个异常。这是一个隐含的相似度测算的例子。【2】和【3】的目的都在于检测生活中认知障碍的异常。【4】中Giroux等人的系统也是同样的目的，只有他们在家中使用传感器检测与预定义日常行程不同的异常，比如制作咖啡。如果违反了事件的正常序列或者该序列的时间与正常有所不同，那么一个异常会被申明。研究人员也在录像中检测到异常比

6、如Xian和Gong【5】，他们的系统能自动建立正常的模型。 所有这些技术都依赖于从观察学会某种正常行为的模型，这意味着他们必须接受新的训练。我们的目标之一就是找到一个单一的相似度量测算工作是否适合多人，且不需要经过任何培训。此外，以前的技术检测基于研究者设计的算法或阀值的不同行为。相反，我们的另一个目标就是找到一个相似度量能近似估算一个人类主题的数据。实现这些目标将使我们能够提供一种未来的自适应系统的方法来准确地再现评估人类一天的相似度且对一般人效果很好不需要任何训练，也许有助于缓解相关应用领域的冷启动问题。为此，我们从30名支援测试者中收集了他们的GPS数据并让他们评估他们每天的相似度。有

7、了这些真实数据，我们进行了各种相似度测算并且找出了2种方法能够较好的再现测试者的评估结果。我们先论述如何从实验中收集到数据。2 GPS数据和进程 为了完成基于位置轨迹天数相似度的评估实验的结果，我们收集到的数据来自志愿者的车辆。本节展现了我们为了第三节的实验准备的数据的记录和处理过程。图1.一段间隔10S的 GPS采样点的段序列2.1 志愿者的GPS数据 我们记录了30名志愿者（8名女性）的GPS数据。每位志愿者借了一台RoyalTek RBT-2300 GPS记录器并将它放在他们的车辆上，可由打火器供电。我们所有的测试者受雇于美国华盛顿的微软总部并且大部分是获得一张30美元的食堂消费卡作为补

8、偿。少数测试者选择无任何补偿。我们的目标是从每位测试者那收集到至少6周的数据。最终我们从每个主体那获得了平均四十天的GPS数据，从20天到60天不等，大多数的驾驶记录包括了在当地的工作出行、通勤出行和周末出行。我们相信这组数据很好地归纳了多数人的正常工作路线。每个测试者至少拥有6周的GPS记录，但是有些测试者没有天天记录。为了达到30个测试者的标准，我们最初记录了39个测试者，但后来发现有9名测试者不知何种原因停止了记录，没有提供合适的数据，其中一位拒绝记录，并且他们频繁的交换使用他们的车辆（违反了我们的测量标准），并且有2位意外离职。我们也忽略了2位分别只有14天和18天的记录的测试者的数据

9、。 该记录仪每隔10S记录一次坐标点（经度和纬度）。图一展现了从我们的测试者记录的10S采样间隔的短序列GPS点。自从我们取消了测试者的可充电电池，他们只能在汽车点火器工作时记录。对某些车辆，这只发生在汽车启动时，对另外一些，汽车点火器是持续工作的。下面我们将详细介绍在预处理过程中，我们填补了GPS系统相应的空白记录和其他的限制。2.2 GPS数据处理过程 为了附加一下原始的GPS数据的语义信息，我们第一个预处理步骤是自动检测原始轨迹上的中断点的时间和地点。为了到达我们的目的，一个中断点被定义为在GPS记录中保持在300半径的圆形区域内5分钟及以上的我们检测到的测试者或车辆的位置。这些参数是基

10、于数据集的，它们的测试者不包含在我们最后的评价中。 为了产生候选中断点的初始位置，我们首先通过GOS轨迹数据制作了一个时间序列并标记那些符合上述中断点定义的位置。因为一个中断点位置在GPS轨迹记录过程中会不止一次被访问，因此在我们的数据中会有至少一次的停止表示记录，因此我们可以用最后一个中断点代替多余的。这样做是我们能够将一整套聚合知识同实际停止位置联系起来。例如，考虑到测试者工作地点的情况下，在一个典型的工作周的过程中，他们的跟踪数据最初将表示5个单独的中断点呈现的“工作”（一个表示一天）。通过将这5个中断点表示成一个，我们得到一个代表最初5个中断点的聚合理解的中断点位置（即5天的位置被访问

11、时，测试者达到/离开的时间等），这比观测5个单独的时间/地点显得更为有用。为了合并这些中断点，我们对候选的中断点使用300米距离阀值（如上）作为合并标准而使用聚类【6】。 一点我们确定了中断点的位置，我们就利用包含在其中的聚合信息，将语义标签应用到某一站。具体来说，我们使用来自于American Time Use Survey (ATUS)【7】的数据来归类最有可能成为中断点的位置，无论是家里还是工作地点。由于我们最后的中断点包含了每天的信息以及达到/离开的时间，停留时间以及访问频率，我们建立和训练了完全基于这些标准的分类器来执行可能的家庭/工作的标贴。由于家庭/工作的中断点在很多测试者的GP

12、S记录集上发生的很频繁，能够区分我们的测试者最后的评价数据是非常重要的。具体来说，这些标签能帮助我们的测试者迅速明确方向并且适应他们正在观察的日子(例如，工作日/周末），并且能更容易区分正常和异常天数。 最后，作为最终的处理步骤，我们创建了一个象征着原始GPS轨迹的每一天的数据的中断点（定义一天从早上4:00到下午3：59）。具体来说，在原始GPS数据的每个位置，我们更换了与其相关联的中断点的标识（与每个中断点绑定的唯一的标识），并及时插入那些刚被启动的车辆的记录位置。如果一个给定的坐标对与中断点位置是不相关的，那么它就被一个From Stop ID-To Stop ID pair替换，以此来

13、表示中断点之间的行程。用一系列的符号表示花在中断点中间的时间来简化原始轨迹数据，不仅为我们提供了一个更简要的轨迹数据的呈现，也更抽象的用于呈现评估算法，而不是依靠地理表示（见第4节）。3 日常相似度评价 我们的目标是找到一种算法使得天数相似度的评价可以达到人类评价的程度。为此，我们要求每位测试者对他们自己的位置数据进行相似度评估。由我们的作者之一引导，我们的位测试者被邀请运行一个显示程序并要求他们对自己近期的数据记录作相似度评估。该程序首先显示一个日历，标识了我们有可用的GPS数据的天数供测试者评估。对于选定的一天，该程序以3种不同的方式展示了一天的位置轨迹。1.地图 在图2（a）中展示的交互

14、式地图显示了我们发现的中断点（在2.2节中描述的），每个都有其独特的ID号码。它同时也显示了中断点之间的GPS轨迹。这样 的 可视化展示强调了在空间布局上每天的行程和中断点。2.图表 在图2（b）中的一个交互式图表以节点和他们的行程作为直边的方式展示了测试者的中断点。较厚的边标识在2个中断点间有更多的行程。我们发现的家庭和工作点被标贴，否则中断点仅仅被标上他们唯一的ID以匹配它们在地图上的号码。点击图表上的一个点或者一条边将在地图上突出显示相关的中断点或者GPS轨迹，这使得研究更方便。这个可视化强调了中断点的数量和它们之间的转换。3.时间轴 如图3所示的时间轴以不同的颜色块显示了每一个中断点，

15、沿一条水平线展示。在中断点之间的时间段表示行程，被涂上黑色。这给出了其它2种可视化显示缺少的对天数的时间看法。 (a)GPS数据的交互式地图 (b)GPS数据的图表视图，以及中断点和它 它们之间的行程 图2.为我们的测试者准备的2种可视化方式图3.时间轴视图，用颜色块标识中断点，用黑色窄条带标识中断点之间的行程 启动程序后，我们要求每个测试者都熟悉可视化，测试者要挑选一天并结合可视化简要的对我们描述。 我们的用户研究的主要部分来到了下一：每个测试者被要求评估他们几天的相对的相似度。也就是说，每个测试者随机选择4天并用上面提到的可视化来描述它们，这已经在图4中展示。然后，我们要求测试者表述哪2对

16、是最相似的。例如，2对天数为A和B，C和D，我们要求测试者表述A和B是否比C和D彼此之间更相似，反之亦然。在第一次测试一个不同的方式，要求测试者给出每对天数的相似度等级后，我们选择了这种简单的评估方式。这个证明太难了，所以我们又回到了这个更简单的问题，关于天数对的相对相似度。图4所示的例子是一个代表我们的测试者的比较典型的问题，具有很好的代表性：平均每天5个中断点，最左边的天数对代表了一个简单的例子，而最右边的则代表了更为复杂的情况。每个测试者评定30对天数对，平均每个测试者花费了大约30分钟。 有了这些部分的排名，下一步我们尝试了几种不同的算法评估一天的相似度以达到准确再现我们的测试者的评估

17、结果的要求。图4.我们用户研究的主要部分，我们要求测试者表述哪几对是相似度最高的4 评估日常相似度的算法 为了找到一个算法估算天数对的数值相似度（或者说距离比分），且与我们的测试者的相似度划分等级相匹配，我们实施和评估了4种轨迹评估算法的标准型和改进型。每个算法的标准型采用其最初定义，在下面的子节中描述。每个算法的改进型由其原来的标准型更加适用于Dynamic Time Warping (DTW) 8，技术允许我们放宽假设，对天数对之间的以时间排列。例如，考虑2天A和B组成一个简单的“家工作地点家”的活动模式。在A天，测试者在早上8：30离家，9：00上班，下午6：00下班，6：30到家。在B

18、天，测试者早上8：00离开家，8：30上班，下午5：30下班那，6：00到家。因此A天和B天同时包含了9小时的工作时间和半小时的往返时间。主观上来说它们实际上是相同的。但是，由于2者有30分钟的时间差，它们必然会招致一个客观相似度评估的惩罚。因此，我们改进各个DTW算法背后的动机就是我们的测试者是否忽略了这些变化的时间，如果是，、那么我们就要建立更加准测地捕捉和还原测试者的主观性评估。 就形式而言，在每个算法的改进上我们通过引导每个算法定义相应的函数测量了DTW距离（DTW）。A天和B天之间的DTW距离计算如下，当并且每个对应一个中断点ID或坐标对取决于算法是否被修改（B也类似）： 实际上，动

19、态时间整合扭曲了2个序列，因此使它们匹配最佳。下面我们描述4个标准轨迹相似度算法。4.1 校对距离 校对距离测算了需要将一串字符串符号转换为另一个字符串的编辑操作的数量。在我们的例子中，该算法操作的中断点符号代表了我们的轨迹数据（在2.2节中讨论的），因此，这里的符号应与中断点ID和中断点之间的对数相符合。4.2 灵敏距离校对 标准的校对距离算法（4.1节中描述的）完全用一个中断点符号代表给定的一天，而没有考虑到中断点的地理位置。为了说明为中断点的地理位置，我们修改了标准Levenshtein算法【9】，使用了大圆形的距离，采用Haversine公式【10】来衡量，代价是为每个函数校对操作。这

20、意味着，例如，执行2个中断点#60和#157的替代操作的代价不再是1，而是2个中断点#60和#157之间根据它们坐标位置的距离。这个度量评估结果可以在图5中看到。图5.八个相似度算法的精确结果。在所有测试者中误差在+/-1的标准偏差内。4.4 距离对的和 此度量【12】计算基于原始位置轨迹的天数之间的距离，而不是上述使用的中断点符号。其结果是，这个度量不考虑任何相关的语义信息。距离对的和测算了每对轨迹位置（坐标点）之间的大圆环的和。由于这个度量要求A天和B天的轨迹长度相等，我们首先执行简单的线性插值，然后计算它们的距离。这个度量评估的结果可以在图5中看到。5 结果 我们同时在匹配我们的测试者的

21、相似度评估结果和聚类2个方面评估我们的相似度算法。5.1 匹配测试者的相似度评估 我们以30个测试者的数据运行8种相似度算法。记得每个测试者看了30组，每组4天。每组4天被分成了2对，然后测试者选择那一对更加相似。我们将这些相同的天数组给我们的相似度算法，然后记录下它们评估哪几天相似度最高的结果。我们报告的精确结果表明了我们的算法能够正确再现人类决策的比例。 精确结果如图5所示。忽略统计学的意义，最好的执行算法是Sum of Pairs Distance with Dynamic Time Warping (w/DTW)，平均精确度为75.5%(SD=10.4%)。这个算法注重在2个位置轨迹的

22、中断点之间的大圆环距离，并随时间变化局部作调整。排在第2位的是Distance Sensitive Edit Distance w/DTW，整体平均度为74.2%(SD=9.3%)。实际上，我们的2个最佳执行算法都是基于在实际的地理距离已知的度量距离上来说的，显然地，我们的测试者将天数相似度与地理位置联系起来了。 由于我们为每位测试者计算了精确度，这为每个算法提供了30个精确度样本，使得我们可以进行统计分析。我们最初使用一个单向的，重复测算的ANOVA测试，其结果为。这证明了算法的选择在统计上有重要的精确度影响。我们接下来在每个算法之间进行了one-tailed, paired-sample

23、t-tests的方法，并用Holm-Bonferroni【13】校正多个t-tests。在28个可能的算法对中，16对在统计学意义上的精确度差异在0.05个等级。表1清点了各算法的胜利和失败次数。最佳性能记录算法是Distance Sensitive Edit Distance w/DTW，有5次胜利记录并且0失败记录。次好的算法是Sum of Pairs Distance w/DTW，有4次胜利记录并且0失败记录。这2种算法之间的性能差异没有统计学上的意义。这2者中，Sum of Pairs Distance w/DTW更易实现，因为它不需要在位置轨迹中识别中断点。虽然这2种最好的算法都使用

24、了DTW，但只对Distance Sensitive Edit Distance算法产生了统计学意义上的性能的显著改，而非它的非DTW对应上。 总体来说，就精确度和易实现性，我们倾向于推荐Sum of Pairs Distance w/DTW作为我们测试过的评估天数相似度的算法中最好的。表1.统计学意义上的相似度算法的成功和失败次数5.2 聚类的应用 我们的相似度测算的一个应用就是用聚类来找到相似天数的组。我们通过30位测试者评估他们自己的天数的聚类来测试。我们使用一个谱聚类算法（随机游动的Laplacian特征向量的k均值【14】）。我们计算聚类的距离度量使用了Edit Distance w

25、/o DTW算法。Edit Distance w/o DTW的平均精度为66.2%(SD=12.5%)，略低于最好的精确度算法Sum of Pairs Distance w/DTW的75.5%。我们的调查使用Edit Distance w/o DTW是因为当我们进行我们的研究时，还没有能力测试表现最好的算法。 为了调查的聚类部分，我们要求每个测试者从2个开始定期增加k聚类。对每个k聚类，该程序在第3节中显示了使用相同的可视化手段展现聚类天数组。如图6显示的一个例子，1条时间线上显示了3个聚类，而天数组又每行左手边的彩色标签表示。每个测试者都被要求选择最佳的k，然后为Likert量表上的聚类评级

26、来表明他们对于申明的认同程度，“我的天数已经被分成合情合理的组。”这个问题的结果如图7所示，我们看到30名测试者中有20名的回答不是“认可”就是“强烈认可”，表明聚类通常是成功的。反过来看，这进一步支持了dit Distance w/o DTW相似度算法更接近与匹配人类相似度评估。我们可以期望Sum of Pairs Distance w/DTW表现的更好，因为它是我们在5.1节中分析的最精确的算法。图6.这是1条时间线上显示的3个聚类。每行一天。在聚类顶部表示的那一天是一个异常值。主要的中央聚类显示了32个工作日，在聚类的底部显示了19个非工作日。图7.大多数测试者对聚类结果感到满意6 总结

27、 根据30名测试者的调查，我们基于他们的位置轨迹评估了8种不同的相似度算法的精确度。我们发现这2种算法Sum of Pairs Distance w/DTW和Distance Sensitive Edit Distance w/DTW在相似天数上最能匹配人类的评估结果。根据我们的测试者的评估，我们也发现我们测试的相似度算法中的一种在位置轨迹的聚类天数上有很好的效果。 除了聚类，这些相似度算法也可能用在发现异常以及帮助预测行为上。我们的算法没有依赖与培训，即它们对用户来说是通用的，因此，它们相对更容易使用。 我们设想未来的工作在这方面可能会探索其他的相似度算法，以及采用实验来发现异常。我们可以预

28、计异常检测效果不错，因为我们的算法在匹配相似度天数人类评估的结果上有很好的表现。参考1. Deng, K., et al.: Trajectory Indexing and Retrieval. In: Zheng, Y., Zhou, X. (eds.) Computing with Spatial Trajectories, Springer, New York (2011) 2. Ma, T.-S.: Real-Time Anomaly Detection for Traveling Individuals. In: Eleventh International ACM SIGACCES

29、S Conference on Computers and Accessibility (ASSETS 2009), Pittsburgh, PA USA, pp. 273274 (2009) 3. Patterson, D.J., et al.: Opportunity Knocks: a System to Provide Cognitive Assistance with Transportation Services. In: Mynatt, E.D., Siio, I. (eds.) UbiComp 2004. LNCS, vol. 3205, pp. 433450. Springe

30、r, Heidelberg (2004) 4. Giroux, S., et al.: Pervasive Behavior Tracking for Cognitive Assistance. In: 1st International Conference on PErvasive Technologies Related to Assistive Environments (PETRA 2008). ACM (2008) 5. Xiang, T., Gong, S.: Video Behavior Profiling for Anomaly Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence 30(5), 893908 (2008) 6. Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning, pp. 520528. Springer, New