英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

---

一种基于聚类的发现轨迹中感兴趣区域的方法

Andrey Tietbohl Palma

摘要：由于移动设备产生了大量的轨迹数据，因此越来越需要从该数据中提取知识的机制。现有的大多数工作都集中在轨迹的几何特性上，但是最近出现了语义轨迹的概念，其中将背景地理信息集成到轨迹采样点。在这个新概念中，轨迹被视为一组停止和移动，其中停止是轨迹的最重要部分。通过测试轨迹与用户提供的一组地理对象的交点来计算停靠点和移动点。在本文中，我们提出了一种替代解决方案，能够找到用户不希望看到的有趣地方。所提出的解决方案是一种基于速度的时空聚类方法，适用于单个轨迹。我们将这两种不同的方法与真实数据实验进行了比较，结果表明，使用速度的概念对停靠点进行计算对于几种应用而言可能是有趣的。

关键词：时空聚类，运动对象，数据挖掘，语义轨迹标注，轨迹

1 引言

在过去的几年中，移动设备产生的移动对象数据激增，涌现出在不同的应用领域中有效分析这些数据的必要性。留在移动物体上的轨迹被视为移动物体在空间和时间上所遵循的路径。轨迹中的每个点都代表移动物体某个时刻在空间中的位置。

现有的用于轨迹数据挖掘和知识发现的方法集中在轨迹的几何特性上，而不考虑背景地理信息。然而，对于许多应用领域，只有在考虑了其语义和背景地理信息的情况下，才可以从轨迹数据中提取有用的信息^[2]。专门针对道路网络作为背景地理信息^{[6，10，12，18]}开展了一些轨迹数据分析工作。

最近^[17]引入了一种新的轨迹推理模型，该模型可以进行强大的语义分析，称为停止和移动。停止点是与应用程序相关的轨迹的语义重要部分并且移动对象停留超过最短停留时间的位置。例如，在旅游应用程序中，停留点可以是旅游场所，旅馆，机场等。在交通管理应用程序中，重要场所可以是交通灯，环形交叉路口，停车场等。根据应用程序，最小停留时间可能会发生显着变化。

在^[2]中，提供了一种名为SMoT的算法，用于从轨迹样本点提取停靠点和移动，并提出了一种评估方法，以显示通过使用此语义模型如何简单地进行轨迹数据分析。在^[1]中，从停止和移动中提取移动模式，并在地理概念图式中对这些模式进行建模，以可视化地理空间中的轨迹模式。

在所有遵循停靠和移动模型的方法中，由于停靠和移动由应用程序定义，用户都必须指定兴趣点。该假设的主要缺点是，如果用户不知道重要点的模式特征则可能会错过这些位置。

图1（1）显示了一个轨迹的示例，其中用户指定了感兴趣的A，B和C的位置。观察图，我们可能会看到轨迹中的两个密集部分似乎是一个停止点：A之前及B和C之间；但用户未将其指定为重要场所。在本文中，我们提出了算法SMoT的替代方法，该方法在^[2]中提出，用于计算停止区域和移动区域。当SMoT搜索轨迹与相关地理对象之间的相交时，我们提出了一种基于速度的时空聚类方法来找到轨迹的重要位置。图1（2）显示了我们方法的一个示例。考虑到最短的停止时间为30分钟，除了A，B和C，我们的方法还将找到了没有被SMoT捕获X和Y。我们的方法可以应用于许多不同的场景，而不是单个应用程序。

图1：单个原始轨迹和单个语义轨迹

本文其余部分的结构如下：在下一节中，我们将介绍停止区域和移动区域的概念。在第3节中，我们介绍新的聚类方法。在第4节中，我们将展示真实数据的实验并与SMoT算法进行比较。在第5节中，我们介绍了相关工作，在第6节中，我们总结了论文并提出了未来研究的一些方向。

2 停止区域和移动区域

在本节中，我们根据^[2]中提供的定义，介绍轨迹、停止区域和移动区域的定义，这些定义将在本文的其余部分中使用。

定义1。轨迹样本：，由时空点组成的列表,其中。

停靠区域代表移动对象停留超过最短时间的轨迹重要位置。这些重要区域是根据应用程序定义的，并且对应于地理数据库中定义的不同空间特征类型^[14]。对于每个相关的空间特征类型，都定义了最短时间，只有与该特征连续相交的轨迹才能被视为一个停止点。我们称这对停止点为候选停止点。

定义2。候选停止点：，其中是中的拓扑封闭多边形，而是严格为正的实数。集合被称为候选停止点的几何形状，而被称为其最短持续时间。候选停靠区域取决于特定的应用，一个应用的候选停靠区域是一个具有不重叠几何形状的由组成的有限集。

定义3。停止区域：相对于应用程序的轨迹的停止点,即轨迹的最大子轨迹,其中是的几何形状并且。

定义4。移动区域：轨迹相对于应用程序的移动区域为：(1)的两个时间连续的停止区域之间的最大连续子轨迹；(2)在的起点和的第一个停止区域之间的最大连续子轨迹；(3)在的最后一个停止区域和的最后一个点之间的最大连续子轨迹；(4)轨迹本身，如果没有停止区域的话。

换句话说，轨迹的每个不停的点都在移动。移动区域没有最短持续时间，并且可能相交，也可能不会停止。如果是这样，则相交时间间隔必须小于候选停止点的最小持续时间。重要的是要注意，应该在考虑到轨迹时间点的平均周期性的情况下指定最小持续时间，以保证有足够的点来表征停止。

在^[2]中提出的算法SMoT用于提取停止区域和移动区域，搜索轨迹样本点和候选停止点之间的交点。在以下部分中，我们提出一种基于聚类的算法来识别轨迹的停止和移动，称为CB-SMoT。

3 CB-SMOT算法

我们的方法的思路是，同一轨迹中速度低于其他部分的轨迹部分对应于有趣的地方。例如，在旅游应用程序中，让我们假设一个游客正在游览一个新城市。他的轨迹将类似于：参观重要的纪念碑，参观博物馆，前往他的酒店，前往酒吧，然后返回酒店。在这些地方，他的轨迹速度可能比他从一个地方移到另一个地方的轨迹的其他部分低。例如，在交通管理应用中，在交通拥堵，交通灯，回旋处和电子速度控制区中，汽车轨迹的速度将较低。根据这种推理，我们提出了一种基于聚类的算法来发现低速区域。

3.1 定义

DBSCAN^[7]是一种众所周知的基于密度的聚类算法。在DBSCAN中，邻域定义为点周围的区域（在二维空间中）。因为我们对在单个轨迹中查找聚类特别感兴趣，并且还考虑了时间，所以我们更改了DBSCAN的某些概念。第一个是邻域的概念，应该指包含所考虑的轨迹中的点。此外，还应考虑轨迹上的距离而不是两点之间的直接距离。因此，我们将点的线性邻域定义为轨迹中与的距离小于或等于Eps（最小点的个数）的轨迹中该点前后的点集。

定义5。Eps线性邻域：令是一条轨迹，其中。点的线性邻域是点的最大集合：,其中。

Eps是一个正数，表示点与轨迹上的相邻点之间的最大距离。我们将使用最小时间的概念代替使区域密集的最小点数。在下面的定义中，我们保留与^[7]中提供的定义相同的名称，但要考虑时间的概念。

定义6。核心点：如果，点称为轨迹的核心点。其中是的最后一个点，是第一个点（邻域按时间排序）。

该定义对应于最大速度条件。之比给出了各个邻域的最大平均速度（速度极限）。通过增加参数，相关速度会降低。此外，使用时间代替点数还可以避免诸如由于某些设备故障以及采样率的时间差异而导致缺少点之类的问题。

定义7。直接密度可达：如果点并且是相对于和的核心点，则点可以直接密度达到点。

定义8。密度可达：如果存在一个链，当并且直接密度可达，则点相对于和密度可达点。

定义9。密度相关：如果存在点，并且和都与密度可达，则两个点和相对于和密度相关。

如果非核心点具有相同的核心点，就可以将它们密度相关。有了这些定义，轨迹簇可以定义如下。

定义10。轨迹聚类：相对于和的轨迹的簇是由一组连续的时空点形成的的非空子轨迹：

1.：如果并且与相对于和密度可达，那么。

2.：和相对于和密度相关。

DBSCAN算法中有三种主要的修改方法，可以对单个轨迹进行聚类：（i）我们搜索最小持续时间，而不是在邻域内搜索最小数量的点；（ii）我们用定义5之后的算法替换了返回点邻域的原始函数；（iii）我们使用分位数函数来计算Eps，这将在下一节中进行解释。

3.2 Eps参数

Eps参数指示用于计算点邻域的绝对距离。但是，由于它是绝对值，因此用户很难在不充分了解每个轨迹的特性的情况下为此参数指定一个合适的值。 考虑到这一点，我们为用户精心设计了一个替代方案，以调整此参数。

轨迹可以看作是两个连续点和之间的距离的列表。这些距离具有算术平均值和标准偏差。使用这两个参数，可以绘制适当的高斯曲线。该曲线表示有关轨迹的一些属性，可用作一种缩放工具。因此，我们可以利用分位数功能来利用此功能，以避免对轨迹领域的了解。它是累积分布函数的反函数，其中分位数函数：。分位数函数定义为：

;

;

其中，是平均值，是标准偏差，并且。

目的是要有一个与平均值和标准偏差有关的相对参数，而不是用户定义的绝对Eps值。用户需要相对于轨迹中的点的总数大致知道产生潜在停止的点的比例。因此，作为输入，我们使用一个名为area的参数，其值在0到1之间，并根据该值计算Eps参数。

3.3 CB-SmoT算法

我们提出了一种提取停止区域和移动区域的两步算法，称为CB-SMoT，如表1的伪代码所示。第一步，使用改进的DBSCAN算法来识别轨迹的较慢部分，我们称为潜在停止点，该算法考虑了一维线（轨迹）和速度，如第3.1节所述。在第二步中，算法会考虑到轨迹后面的地理位置，从而确定在第一步中发现的这些潜在停靠点（簇）的位置

CB-SMoT会获取每个潜在的停止区域（集群），并与候选停止区域一起测试交叉点和最小停留时间。由于潜在停止点不与任何候选停停点相交，它仍然可能是一个有趣的地方。为了向用户提供此信息，算法将诸如这种位置标记为未知停止区域。

定义11。未知停止区域：相对于应用程序，和而言，轨迹的未知停止区域簇在至少时不与的任何相交，其中是候选停止区域。

图2说明了此概念。在图2中,轨迹有四个潜在停止区域，簇。在此示例中，用户指定了4个候选停靠点，由。簇与候选停止区域相交的时间大于，则轨迹的第一个停止点为。簇也发生同样的情况，考虑到轨迹的第二个停止区域。对于簇和不与任何候选停止点相交。因此，和是未知停止区域。

图2：具有2个停靠点和2个未知停靠点的轨迹示例

每个未知的停靠站都会收到一个标识符。如果两个或多个未知的站彼此相交，它们将获得相同的标识。图3给出了一个示例，其中轨迹T₁具有不与任何候选停止点相交的簇G₁。类似地，轨迹T₂具有不与任何候选停止点相交的簇G₂。当G₁与G₂相交时，它们都位于同一区域，因此它们将获得相同的标识。

图3：具有相同未知停止区域的两条轨迹

表1：CB-SMoT算法

4 实验与评估

为了在实际应用中同时完成轨迹和地理数据的实验，我们扩展了工具Weka-GDPM^[5]以支持地理数据和轨迹。Weka-GDPM是Weka^[8]的扩展，Weka是一种数据挖掘工具包，实现了几种用于关联规则挖掘，聚类和分类的算法。我们已经在该工具中实现了SMoT和CB-SMoT算法，它们的输出（停止区域和移动区域）存储在地理数据库中。因此，该工具中可用的任何经典数据挖掘方法都可以直接应用于停止区域和移动区域。

我们使用在阿姆斯特丹市收集的轨迹数据进行一些初步实验。这些轨迹对应于一个教育游戏^[16]，包含487个不同学生轨迹的约125000点。

第一个实验是考虑一组建筑物作为候选对象而进行的，参数MinTime为120秒。应用了3次聚类算法，area分别为0.3、0.35和0.4。SMoT算法找到了6个停靠点，如表1所示。对于area参数的所有不同值，CB-SMoT发现的几乎所有簇都是未知停靠点。大量未知的停止通过可视化图4中所示的数据可以理解，其中候选停靠点只有几座建筑物（黑色的小多边形）。建筑物数据集约有4.2万座建筑物，但是在收集轨迹的区域中只有少数建筑物。这是SMoT仅找到几个停靠点，而CB-SMoT发现几个未知停靠点的原因之一。

图4：轨迹样本和建筑

此实验中的另一个观察结果是CB-SMoT仅发现了1个已知的停止点，而SMoT发现了6个。这之所以发生是因为CB-SMoT是基于速度的，并且SMoT发现的停止点中的轨迹速度不足以使被CB-SMoT视为停止点。

表2中显示了第二个实验，该实验是使用与覆盖轨迹所在大多数位置的区域相对应的地理数据进行的。考虑到最小时间为300s，SmoT算法发现357个停止，而CB-SMoT发现对于area参数的不同值的停止区域少得多。在本实验中，与上一个实验相反。如图5所示，候选停靠区域密集且覆盖整个区域。因为所

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[240217]，资料为PDF文档或Word文档，PDF文档可免费转换为Word