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

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

James Biagioni1 and John Krumm2

1 Department of Computer Science, University of Illinois at Chicago, Chicago, IL, USA jbiagi1@uic.edu 2 Microsoft

Research, Microsoft Corporation, Redmond, WA, USA jckrumm@microsoft.com

摘要。我们开发和测试的算法是基于GPS记录的个人日常位置轨迹的相似度的评估。一份精确的 相似度评估可以被用来发现异常行为，聚类相似的天数，并且预测未来的旅程。我们根据30 名志愿测试者的46天的GPS轨迹，收集了一份平均数据。每个测试者每天随机匹配并且被要求评 估它们的相似度。我们测试了8种不同的相似度算法以准确再现我们的测试者的评估结果，并且 我们的统计测试发现有2种算法比其他算法优秀。我们也成功的运用其中一种相似度算法于通过 使用位置轨迹聚集相似的天数。

关键词：位置轨迹，相似度，异常检测，聚类。

1 介绍

消费者和企业都意识到了通过位置轨迹来了解日常习惯和预测临时的需求的价值，并且安装了GPS的智能手机的大量使用使得这些更容易收集。这些轨迹可以帮助我们了解日常活动；特别的是，我们可以使用位置轨迹发现异常的天和聚类相似的天，以使得更好的了解我们的日常行程。这两个任务都需要一种方法来比较这些天和其他的不同。

本文开发和测试算法测算相似天数来表示位置轨迹，从真实用户的相似性评估测试。通过可靠的方法测算相似度，我们可以发现与其它截然不同的异常天数，比如暗示混淆（一个重要的在人群中检测到认知障碍的用户的现象）或者某种习惯的改变。我们也可以将属于一起的天数做出合理的归类来获取他们的变化并且预测一天会如何发展，为未来适应系统的影响力提供有用的基础知识。我们相信这是第一次使用位置轨迹以人类的评估的方式来测算天数的相似度。

各种各样的传感器可以用来描述一天的数据，比如测算一个人的手机，台式电脑，车辆，社交网站，生物识别传感器等等活动。我们的工作是针对位置轨迹，通常使用GPS来测算。这样的一个好处是，位置是一个持续存在的状态（如果不是总是可以测量的话），而不是基于事件的活动，比如短信活动，这只是偶尔发生。大多数人的位置也是不断变化的并且在户外是易于使用GPS来测算的。这些特征使得位置成为一个很方便的测算天数之间的相似度的变量。地理信息系统社区已经广泛的关注位置轨迹的相似度，比如，【1】，但是这些努力主要是机器处理过程。我们感兴趣的是匹配人类评估的相似度，这似乎更常见于异常检测的研究中。在【2】中，Ma从GPS轨迹中检测到的异常首先呈现一个正常轨迹作为地面矩阵序列的结果。如果一个新的矩阵轨迹与其他正常轨迹完全不同，那么一个异常会被申明。这里的相似度测算是明确的，它依赖于一个在正常行程和查询行程之间的地理差异的数量测算。同时它也忽略的时间。在【3】中，Patterson等进行了基于GPS跟踪的异常行为检测。他们基于一个人的历史GPS轨迹建立了一个动态的概率模型。如果建立的模型的不准确度超过了一般先验模型，那么系统就会申明一个异常。这是一个隐含的相似度测算的例子。【2】和【3】的目的都在于检测生活中认知障碍的异常。【4】中Giroux等人的系统也是同样的目的，只有他们在家中使用传感器检测与预定义日常行程不同的异常，比如制作咖啡。如果违反了事件的正常序列或者该序列的时间与正常有所不同，那么一个异常会被申明。研究人员也在录像中检测到异常比如Xian和Gong【5】，他们的系统能自动建立正常的模型。

所有这些技术都依赖于从观察学会某种正常行为的模型，这意味着他们必须接受新的训练。我们的目标之一就是找到一个单一的相似度量测算工作是否适合多人，且不需要经过任何培训。此外，以前的技术检测基于研究者设计的算法或阀值的不同行为。相反，我们的另一个目标就是找到一个相似度量能近似估算一个人类主题的数据。实现这些目标将使我们能够提供一种未来的自适应系统的方法来准确地再现评估

人类一天的相似度且对一般人效果很好不需要任何训练，也许有助于缓解相关应用领域的冷启动问题。为此，我们从30名支援测试者中收集了他们的GPS数据并让他们评估他们每天的相似度。有了这些真实数据，我们进行了各种相似度测算并且找出了2种方法能够较好的再现测试者的评估结果。我们先论述如何从实验中收集到数据。

2 GPS数据和进程

为了完成基于位置轨迹天数相似度的评估实验的结果，我们收集到的数据来自志愿者的车辆。本节展现了我们为了第三节的实验准备的数据的记录和处理过程。

图1.一段间隔10S的 GPS采样点的段序列

2.1 志愿者的GPS数据

我们记录了30名志愿者（8名女性）的GPS数据。每位志愿者借了一台RoyalTek RBT-2300 GPS记录

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

该记录仪每隔10S记录一次坐标点（经度和纬度）。图一展现了从我们的测试者记录的10S采样间隔的短序列GPS点。自从我们取消了测试者的可充电电池，他们只能在汽车点火器工作时记录。对某些车辆，这只发生在汽车启动时，对另外一些，汽车点火器是持续工作的。下面我们将详细介绍在预处理过程中，我们填补了GPS系统相应的空白记录和其他的限制。

2.2 GPS数据处理过程

为了附加一下原始的GPS数据的语义信息，我们第一个预处理步骤是自动检测原始轨迹上的中断点的时间和地点。为了到达我们的目的，一个中断点被定义为在GPS记录中保持在300半径的圆形区域内5分

钟及以上的我们检测到的测试者或车辆的位置。这些参数是基于数据集的，它们的测试者不包含在我们最后的评价中。

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

一点我们确定了中断点的位置，我们就利用包含在其中的聚合信息，将语义标签应用到某一站。具体来说，我们使用来自于American Time Use Survey (ATUS)【7】的数据来归类最有可能成为中断点的位置，无论是家里还是工作地点。由于我们最后的中断点包含了每天的信息以及达到/离开的时间，停留时间以及访问频率，我们建立和训练了完全基于这些标准的分类器来执行可能的家庭/工作的标贴。由于家庭/工作的中断点在很多测试者的GPS记录集上发生的很频繁，能够区分我们的测试者最后的评价数据是非常重要的。具体来说，这些标签能帮助我们的测试者迅速明确方向并且适应他们正在观察的日子(例如，工作日/周末），并且能更容易区分正常和异常天数。

最后，作为最终的处理步骤，我们创建了一个象征着原始GPS轨迹的每一天的数据的中断点（定义一天从早上4:00到下午3：59）。具体来说，在原始GPS数据的每个位置，我们更换了与其相关联的中断点的标识（与每个中断点绑定的唯一的标识），并及时插入那些刚被启动的车辆的记录位置。如果一个给定的坐标对与中断点位置是不相关的，那么它就被一个From Stop ID-To Stop ID pair替换，以此来表示中断点之间的行程。用一系列的符号表示花在中断点中间的时间来简化原始轨迹数据，不仅为我们提供了一个更简要的轨迹数据的呈现，也更抽象的用于呈现评估算法，而不是依靠地理表示（见第4节）。

3 日常相似度评价

我们的目标是找到一种算法使得天数相似度的评价可以达到人类评价的程度。为此，我们要求每位测

试者对他们自己的位置数据进行相似度评估。由我们的作者之一引导，我们的３０位测试者被邀请运行一个显示程序并要求他们对自己近期的数据记录作相似度评估。该程序首先显示一个日历，标识了我们有可用的GPS数据的天数供测试者评估。对于选定的一天，该程序以3种不同的方式展示了一天的位置轨迹。

1.地图 — 在图2（a）中展示的交互式地图显示了我们发现的中断点（在2.2节中描述的），每个都有其独特的ID号码。它同时也显示了中断点之间的GPS轨迹。这样 的 可视化展示强调了在空间布局上每天的行程和中断点。

2.图表 — 在图2（b）中的一个交互式图表以节点和他们的行程作为直边的方式展示了测试者的中断点。较厚的边标识在2个中断点间有更多的行程。我们发现的家庭和工作点被标贴，否则中断点仅仅被标上他们唯一的ID以匹配它们在地图上的号码。点击图表上的一个点或者一条边将在地图上突出显示相关的中断点或者GPS轨迹，这使得研究更方便。这个可视化强调了中断点的数量和它们之间的转换。

3.时间轴 — 如图3所示的时间轴以不同的颜色块显示了每一个中断点，沿一条水平线展示。在中断点之间的时间段表示行程，被涂上黑色。这给出了其它2种可视化显示缺少的对天数的时间看法。