

16 空间数据挖掘

“时间和空间是我们思考的模式，而不是我们生活的条件。” - 艾尔伯特爱因斯坦

16.1 介绍

空间数据通常在地理数据挖掘应用程序中出现。与气象数据，地球科学，图像分析和车辆数据有关的许多应用在本质上是空间的。在很多情况下，空间数据与时间分量相结合。这些数据被称为时空数据。其中出现空间数据的应用程序的一些示例如下：

1. 气象资料：重要天气特征的量化，如温度和压力，通常在不同的地理位置进行测量。可以对这些进行分析以发现基础数据中的有趣事件。

2. 移动对象：移动对象通常会创建轨迹。 这些轨迹可以分析各种各样的见解，例如特征趋势或物体的异常路径

3. 地球科学数据：不同空间位置的土地覆盖类型可以表示为行为属性。 这种模式的异常提供了有关人类活动异常趋势的见解，如森林砍伐或其他异常植被趋势。

4. 疾病暴发数据：有关疾病暴发的数据通常由空间位置（例如邮政编码和县）汇总。 分析这些数据的趋势可以提供关于暴发因果关系的信息。

5. 医学诊断：磁共振成像（MRI）和正电子发射断层扫描（PET）扫描是2维或3维空间数据。在这些数据中检测到异常的局部区域可以帮助检测诸如脑瘤，阿尔茨海默病的发作和多发性硬化病变等疾病。通常，任何形式的图像数据都可以被认为是空间数据。对这些数据的形状分析在各种应用中具有相当重要的意义。

6. 人口统计学数据：诸如年龄，性别，种族和工资等人口统计学（行为）属性可以与空间（上下文）属性相结合，以提供关于分布中的人口学模式的见解。 这些信息对于目标营销应用程序非常有用。

大多数形式的空间数据可以被分类为上下文数据类型，其中属性被划分为上下文属性和行为属性。 这种划分与时间序列和离散序列数据的划分类似：

• 上下文属性：这些代表提供进行测量的背景的属性。 换句话说，上下文属性提供了衡量行为值的参考点。 在大多数情况下，上下文属性包含数据点的空间坐标。 在某些情况下，上下文属性可能是逻辑位置，例如建筑物或状态。 在时空数据的情况下，上下文属性可以包括时间。 例如，在特定位置的传感器测量海面温度的应用中，上下文属性可以包括传感器的位置和进行测量的时间。

• 行为属性：这些代表参考点处的行为值。例如，在上述海面温度应用中，这些值对应于温度属性值。

在大多数形式的空间数据中，空间属性是上下文的，并且可以可选地包括时间属性。轨迹数据的例外情况是空间属性是行为的，而时间是唯一的上下文属性。实际上，轨迹数据可以被认为等同于多元时间序列数据。这一等同性在16.3小结有更详细的讨论。

本章分别研究空间属性是上下文的情况，以及空间属性是行为的情况。后一种情况通常对应于轨迹数据，其中上下文属性对应于时间。因此，轨迹数据是时空数据的一种形式。在其他形式的时空数据中，空间和时间属性都是上下文的。

本章的结构安排如下。第16.2节介绍了空间属性是上下文的数据挖掘场景。在这方面，本章研究了几个重要的问题，如模式挖掘，聚类，异常值检测和分类。 第16.3节讨论了挖掘轨迹数据的算法。第16.4节讨论了总结。

16.2 空间上下文属性的挖掘

在许多形式的气象数据中，各种（行为）属性（如温度，压力和湿度）都在不同的空间位置进行测量。 在这些情况下，空间属性是上下文的。图16.1举例说明了海面温度等值线图。 图表中不同的阴影代表不同的海面温度。这些对应于不同行为属性的值空间位置。另一个例子是图像数据的情况，其中图像的强度以像素为单位进行测量。这些数据通常用于捕获诊断图像。 图16.2说明了认知健康人和阿尔茨海默病患者的PET扫描示例。在这种情况下，像素的值表示行为属性，这些像素的空间位置表示上下文属性。空间数据中的行为属性可能以各种方式呈现，具体取决于应用程序域：

1. 对于某些类型的空间数据，例如图像，可以对从数据中提取的特定形状的轮廓执行分析。例如，在图16.3中，可以提取昆虫的轮廓，并相对于数据中的其他图像进行分析。
2. 对于其他类型的空间数据，如气象应用，行为属性可能是抽象的数量，如温度。 因此，可以根据这些抽象数量的趋势进行分析。 在这种情况下，需要将空间数据视为具有与空间坐标相对应的多个参考点的上下文数据类型。 这种分析通常比较复杂。

数据挖掘方法的具体选择通常取决于手头的应用程序。在分析之前，这些形式的数据通常会转换为其他数据类型，例如时间序列或多维数据。

16.2.1 形状与时间序列的转换

在诸如图像的许多空间数据集中，数据可能由特定形状支配。 由于尺寸和方向的变化，对这种形状的分析具有挑战性。 分析空间数据的一种常用技术是将其转换为更容易分析的不同格式。 特别是，一个形状的轮廓通常会转换为时间序列以供进一步分析。 例如，图16.3中昆虫形状的轮廓由于其复杂性而难以直接分析。 但是，可以通过将数据转换为时间序列来创建对数据处理友好的表示。 常用的方法是使用对象从质心到边界的距离，并计算在顺时针扫描边界时得到的实数序列。这产生实时数字的时间序列，并被称为质心距离签名。这种转换可用于将挖掘形状的问题映射到挖掘时间序列的问题。后一个域更容易分析。例如，考虑图16.4a所示的椭圆形状。然后，图16.4b说明了使用360个不同的等间距角样本表示与质心距离的时间序列，如图16.4b所示。请注意，此处的上下文属性是度数，但可以“假装”它表示时间戳。这有助于使用可用于时间序列分析的所有强大的数据挖掘技术。在这种情况下，采样点从椭圆的一个主轴开始。如果采样点从不同的位置开始，或者如果形状被旋转（具有相同的角度起点），那么这导致时间序列的循环转换。这是非常重要的，因为形状的精确定位可能不会事先知道。例如，图16.3b和c从图16.3a的形状旋转。图16.3d中的形状是图16.3a形状的镜像。虽然旋转会导致循环翻译，但镜像会导致系列翻转。 图16.4c表示图16.4a形状的旋转45°。相应地，图16.4d中的时间序列表示是图16.4b中时间序列表示的（循环）转换。类似地，形状的镜像对应于时间序列的逆转。稍后将明显的是，旋转或镜像的影响需要明确地结合到手边应用的距离或相似度函数中。时间序列被提取后，可能会根据应用程序的需要以不同的方式进行标准化：

• 如果没有执行规范化，那么数据挖掘方法对基础对象的绝对大小敏感。许多医学图像如MRI扫描都可能出现这种情况，其中所有空间物体都被绘制成相同的比例。
• 如果所有的时间序列值乘以相同的因子乘以单位平均值，则这种方法将允许匹配不同尺寸的形状，但是可以区分形状的不同水平的相对变化。例如，具有非常不同的主轴和副轴比率的两个椭圆将很好地被区分。
• 如果所有的时间序列都被标准化为零均值和单位方差，那么这种方法将匹配形状中相对局部变化相似的形状，但是整体形状可能非常不同。例如，这种方法不能很好地区分具有非常不同的主轴和副轴比率的两个椭圆，但是将区分具有不同边界中的相对局部偏差的两个这样的形状。唯一的例外是呈现为直线的圆形形状。此外，轮廓中的噪声效应将在不太拉长的形状中得到不同的增强。例如，对于在边界处具有相似噪声偏差但具有不同延伸水平（主轴至副轴比）的两个椭圆，时间序列的整体形状将类似，但是所提取时间序列中的局部噪声偏差将是在细长形状中差异化压制。这有时会从形状分析的角度提供扭曲的图像。由于诸如图像光栅化效应之类的微小变化，完美的圆形形状可能在所提取的时间序列中显示出不稳定和大的噪声偏差。因此，时间序列分析的通常均值和方差标准化常常导致意想不到的结果。

通常，建议以特定于应用程序的方式选择规范化方法。在形状转换为时间序列后，它们可以用于各种应用场合。例如，时间序列中的图案对应于空间形状中的频繁轮廓。类似地，通过确定时间序列中的聚类可以发现类似形状的聚类。类似的观察结果适用于异常值检测和分类问题。

图16.1：海面温度的等值线图：图片由NOAA卫星和信息服务提供

图16.2：认知健康人与阿尔茨海默病患者大脑的PET扫描。（图片由国家老龄研究所/美国国立卫生研究院提供）

图16.3：旋转和镜像对形状匹配的影响

图16.4：从形状到时间序列的转换

16.2.2 小波空间到多维变换

对于其中行为属性值在整个空间域内变化的气象数据等数据类型，基于轮廓的形状可能无法用于分析。 因此，在这些情况下，时间序列转换的形状是不合适的。 小波是将时间序列数据转换为多维数据的流行方法。 空间数据与时间序列数据有许多相似之处。时间序列数据具有单个上下文属性（时间），沿着该上下文属性（时间），行为属性（例如，温度）可以呈现平滑变化。相应地，空间数据具有两个上下文属性（空间坐标），沿着该上下文属性（空间坐标），行为属性（例如，海面温度）可以呈现平滑变化。由于这种类比，有可能通过适当修改将基于小波的方法概括为多个上下文属性的情况。 假设空间数据以尺寸为$q×q$的二维网格的形式表示。因此，网格的每个坐标都包含行为属性的一个实例，例如温度。正如在第三节中讨论的时间序列案例。章节2.4.4.1。如图2所示，差分操作通过以时间序列以分层方式连续分割而在时间序列的连续分段上应用。相应的基向量在相关位置处具有+1和-1。二维情况是完全类似的，其中空间网格的连续区域被用于连续的划分。这些分区沿着不同的轴交替进行。相应的基本向量是尺寸为q×q的二维矩阵，用于调节差分运算的执行方式。图16.5提供了一个空间数据集中海面温度如何转换为多维表示的例子。这将导致总共$q^2$小波系数，尽管只有大系数需要保留用于分析。有关空间小波系数生成的更详细描述可参见第2章的2.4.4.1小节上述描述是针对单个行为属性和多个上下文属性（空间坐标）的情况。多个行为属性也可以通过分别为每个行为属性执行分解来解决，并且为每个行为属性创建一组单独的维度。

像时间序列小波一样，空间小波是一个多分辨率表示。系数表示不同空间粒度级别的趋势。高层次系数代表较大空间区域的趋势，而较低层次系数代表较小空间区域的趋势。因此，这种方法非常强大，并且对于许多空间应用具有广泛的可用性。空间小波可以有效地用于许多图像聚类和分类应用，其中（上下文）空间数据可以被转换为（非上下文）多维数据。一旦转换完成，几乎所有在Chaps中讨论的多维方法。这种表示可以使用4到11。这种方法打开了使用各种多维数据挖掘方法的大门。

图16.5：包含海表温度的网格中空间数据的小波分解的顶层图示（第2章重新讨论的图2.7）

16.2.3 空间共定位模式

在这个问题中，上下文属性是空间的，而行为属性通常是布尔和非空间的。非布尔行为属性可以通过离散化或二值化使用类型转换来解决。空间主体模式挖掘的目标是发现在相同空间位置发生的特征组合。考虑一个生态数据集，其中一个具有行为属性，如火源，针状植物类型和干旱指标。这些特征的空间位置往往可能是森林火灾的一个风险因素。因此，这种模式的发现在数据挖掘分析中很有用。在许多情况下，感兴趣的空间事件指标（例如疾病暴发，植被事件或气候事件）被添加到其他行为属性。包含此感兴趣指标的有用模式的发现可用于发现事件因果关系。这个问题也与基于规则的空间分类密切相关，其中事件发生在先前未见过的测试区域中的可能性可以从所得到的模式中估计。 挖掘过程中的一个挑战是不同的行为属性可能来自不同的数据源，因此在其测量中可能不具有完全相同的上下文（空间）属性值。 因此，适当的数据预处理至关重要。 数据可以通过将空间区域划分成更小的区域来均化。对于每个区域，每个行为属性的值都是从原始数据源中的值中启发式导出的。例如，如果布尔属性的值比空间区域中的预定义时间部分多1，则其值设置为1.可以将上下文（空间）属性设置为该区域的质心。 可以在这个预处理的数据上执行挖掘。 总体方法如下：

1. 预处理数据以在同一组空间位置创建行为属性值。

2. 对于每个空间位置，创建一个包含相应的布尔值组合值。

3. 使用任何频繁模式挖掘算法来发现这些事务中的相关模式。

4. 对于每个发现的模式，将其映射回包含该模式的空间区域。如果需要进行汇总，请将每个模式的相关空间区域进行聚类。

在特定行为属性是感兴趣事件（例如，疾病暴发）的情况下，对于该属性分别包含0和1的值的交易可以被单独处理以发现其他行为属性上的两组模式。这两组模式之间的差异可以提供洞察在每个空间位置感兴趣事件的判别因子。这种模式对于先前未见过的测试区域的空间分类也很有用。这种方法与第10章中的关联分类器的方法相同。 该模型还可以以无缝方式处理时间变化的数据。在这种情况下，时间成为除空间属性之外的另一个上下文属性。使用上述方法可以在不同的瞬时快照中发现模式。随着时间的推移，这些模式的关键变化可以提供洞察空间演变的本质。

16.2.4 空间共定位模式

在许多应用中，可能需要在分析之前对相似的形状进行聚类。假定有N个形状的数据库可用，并且需要创建总共k组相似的形状。这在许多形状分类应用中可能是一个有用的预处理任务。在这种情况下，一旦形状被转换为一个时间序列，许多在第14章的14.5小节中讨论过讨论的时间序列聚类算法可以有效地使用。k-medoids，层次结构和基于图的方法特别合适，因为它们只需要为相应的时间序列设计适当的相似度函数。这是一个将在后面更详细讨论的问题。 基于形状的聚类的主要步骤如下：

1. 使用16.2.1小节中讨论的基于质心的扫描方法，将每个形状转换成时间序列。这导致产生了N个不同时间序列的数据库。

2. 使用14.5小节讨论过的任何时间序列聚类算法，如时间序列数据上的分层，k-medoids或基于图表的方法。这将把N个时间序列分为k组。

3. 将k组时间序列聚类映射到k组形状聚类，通过将时间序列映射到相应的形状中。

前述的聚类算法仅取决于距离函数的选择。 第三节讨论的任何时间系列措施。 3.4.1小节中的理论可以被使用，取决于匹配中允许的误差容限或失真（变形）的期望程度。 另一个重要问题是通过不同形状的旋转来调整距离函数。下面以欧几里得距离为例，虽然一般原则可以应用于任何距离函数。 从图16.4的例子中可以明显看出，形状的旋转导致了通过使用形状的质心到形状的轮廓的距离而产生的时间序列的线性循环移位。对于由$a_1a_2...a_n$表示的长度为n的时间序列，由$i$单位进行的循环翻译导致时间序列$a_{i+1} a_{i+2}...a_n a_1 a_2...a_i$。 然后，两个时间序列$T_1=a_1...a_n$和$T_2=b_1...b_n$之间的旋转不变欧几里得距离$RIDist（T_1，T_2）$由$T_1$与$T_2$的所有可能的旋转平移之间的最小距离给出（反之亦然）。因此，旋转不变距离表示如下：

$$RIDist（T_1，T_2）=min^n_{i=1}\Sigma^n_{j=1} (a_j-b_{1+(j+1)mod_n})^2$$

通常，如果时间序列T2以i为单位的循环移位由T2i表示，则使用任何距离函数$Dist（T_1，T_2）$的旋转不变距离可以表示如下：

$$RIDist（T_1，T_2）=min^n_{i=1}Dist（T_1，T^i_2）\tag{16.1}$$

需要注意的是，时间序列的反转对应于底层形状的镜像。因此，通过将距离函数中的序列逆转（及其旋转）并入，也可以使用这种方法来处理镜像。这将使计算增加2倍。所使用的距离函数的精确选择是高度专用的，取决于是需要旋转还是镜像转换。

16.2.5 离群值检测

在空间数据的情况下，异常值可以是点异常值和异常值。这两种异常值也会在时间序列数据中遇到，并且会以离散序列出现。 在空间数据的情况下，这两种异常值定义如下：

1. 点离群点：这些离群点是在具有各种空间和行为属性的单个空间物体上定义的。例如，天气图是包含空间位置和这些位置处的环境测量值（行为值）的空间对象。违反空间连续性的行为属性的突然变化提供了关于潜在的上下文异常的有用信息。例如，考虑测量海面温度和压力的气象应用。在一个非常小的局部区域中异常高的海面温度是热点，可能是地表下火山活动的结果。同样，在一个小的局部地区，异常低压或高压可能表明形成飓风或旋风。在所有这些情况下，空间连续性被感兴趣的属性侵犯。这些属性通常在日常气象应用中进行跟踪。图16.6给出了空间数据异常点的一个例子.

2. 形状异常值：这些异常值的应用设置是完全不同的。这些异常值在多个形状的数据库中定义。 例如，可以从不同的图像中提取形状。在这种情况下，不同物体中不寻常的形状需要报告为异常值。

本小节将研究以上两种参数公式。

图16.6：空间数据的点异常点示例

16.2.5.1点异常值

基于邻域的算法通常用于发现点离群点。在这些算法中，数据点的空间邻域中的突然变化被用于诊断异常值。 因此，第一步是定义一个空间邻域的概念。给定数据点的空间邻域内的行为值被组合以创建行为属性的预期值。然后使用此预期值来计算数据点与预期值的偏差。这提供了异常值。 空间数据中点异常值的定义与时间序列数据中的类似。 直观地说，行为属性值在小的空间局部范围内突然变化是不常见的。例如，这种方法会检测到小空间区域内温度的突然变化。邻里可以用许多不同的方式来定义：

• 多维邻域：在这种情况下，使用数据点之间的多维距离来定义邻域。当上下文属性被定义为坐标时，这种方法是合适的。
• 基于图的邻域：在这种情况下，邻域由空间对象之间的链接关系来定义。 在空间对象的位置可能不对应于确切坐标（例如，县或邮政编码）的情况下，这样的邻域可能更有用。 在这种情况下，基于图表的表示提供了更一般的建模工具。

以下部分将讨论多维和基于图的方法。 多维方法 虽然传统的多维方法也可用于检测空间数据中的异常值，但此类方法不能区分上下文属性和行为属性。 因此，这些方法并未针对空间数据中的异常值检测进行优化。 这是因为（上下文）空间属性应该与行为属性区别对待。基本思想是将k-最近邻居异常检测方法适用于空间数据的情况。 数据的空间邻域通过对空间（上下文）属性使用多维距离来定义。因此，上下文属性被用于确定k个最近的邻居。行为属性值的平均值为行为属性提供了预期值。预期值和真值之间的差异用于预测异常值。可以在多维空间数据上使用各种距离函数来确定邻近度。距离函数的选择很重要，因为它定义了用于计算行为属性偏差的邻域选择。整个数据挖掘过程如图1.1所示。 请注意，图1.1中的分析块显示了代表特定应用解决方案设计的多个构建块。 算法设计的这一部分取决于分析师的技能，并经常将四个主要问题中的一个或多个作为构建块。 当然，情况并非总是如此，但在本书中，对这四个问题进行特殊处理已经足够频繁了。 为了解释数据挖掘过程，我们将使用推荐场景中的一个示例。对于具有行为属性值$f(o)$的给定空间对象$o$，令$o_1...o_k$ 可以是它的k最近的邻居。 然后，可以使用各种方法来计算对象o的预测值$g(o)$。 最直接的方法是平均值： $<span><span class="MathJax_Preview">g(o)=\Sigma^k_{i=1} f(o_i)/k</span><script type="math/tex">g(o)=\Sigma^k_{i=1} f(o_i)/k$ 或者，可以将$g(o)$计算为$f(o_i)$的周围值的中值，以减小极值的影响。然后，对于每个数据对象$o$，$f(o)$,$-g(o)$的值表示与预测值的偏差。这些偏差中的极值可以使用多种方法计算单变量极值分析。这些在第8章讨论。由此法产生的极值将被报告为异常值。

基于图形的方法 在基于图的方法中，空间邻近度利用空间区域的图表表示中的节点之间的链接来建模。因此，节点与行为属性相关联，并且相邻节点之间的行为属性的强烈变化被识别为异常值。当单个节点不与点特定坐标相关联时，基于图形的方法特别有用，但它们可能对应于任意形状的区域。在这种情况下，节点之间的链接对应于不同区域之间的邻域关系。基于图的方法以更一般的方式定义空间关系，因为语义关系也可以用来定义邻域。例如，如果两个对象位于相同的语义位置（如建筑物，餐馆或办公室），则可以通过边连接两个对象。在许多应用中，可以基于邻近关系的强度对链路进行加权。例如，考虑一种疾病暴发应用，其中空间对象对应于县区域。在这种情况下，链接的强度可以对应于两个区域之间的边界的长度。多维数据是一种特殊情况，其中链接对应于基于距离的邻近度。因此，图表示允许对上下文属性进行更一般的解释。 设S是给定节点i的邻居集合。然后，可以使用空间连续性的概念来创建基于其（空间）邻居的预测值的行为属性的预测值。我和它的邻居之间的联系的强度也可以用来计算预测，作为k个最近空间邻居的行为属性的加权平均值或中间值。对于具有行为属性值$f(o)$的给定空间对象$o$，让$o_1...o_k$可以是它的k个链接的邻居根据关系图。令链接$(o，oi)$的权重为$w(o，oi)$。然后，可以使用基于联动的加权平均值来计算对象$o$的预测值$g(o)$。

$$ g_{(o)}=\frac{\sum^k_{i=1}w(o，oi)\cdot f(o_i)}{\sum^k_{i=1}w(o，oi)} $$ 或者，可以将相邻值的加权中值用于预测目的。由于行为属性的真实值是已知的，因此可以用它来模拟行为属性与其预测值的偏差。与多维方法一样，$f(o)-g(o)$的值表示与预测值的偏差。 极值分析可用于这些偏差以确定空间异常值。这个过程与多维情况下的过程相同。 具有高标准化偏差值的节点可能被报告为异常值。

16.2.5.2 异常形状

基于形状的异常值在空间数据中相对容易确定，使用在16.2.1小节多次讨论的从空间数据到时间序列的转换。转换完成后，可以将 k-近邻 居离群值检测器应用于所得到的时间序列。到第k个最近的邻居的距离可以被报告为异常值分数。在计算异常值时，需要记住一些关键问题。

1. 距离函数需要修改以说明旋转不变性形状匹配。这是通过比较一个时间序列的所有循环移位到另一个时间序列来实现的。旋转不变距离可以通过公式16.1。

2. 在某些应用中，镜像不变性也需要考虑。在这种情况下，所有的循环移位及其反转都需要包含在上述比较中。 异常值是根据这个增强的数据库确定的。

虽然香草k-近邻检测器可以正确地确定异常值，但通过修剪可以更快地实现该方法。 其基本思想与14章中讨论的Hotsax方法类似。其中使用嵌套循环结构来维持top-n异常值。外部循环对应于不同候选者的选择，并且内部循环对应于这些候选者中的每一个的k个最近邻居的计算。 当k-近邻值小于目前发现的第n个最佳异常值时，内环可以提前终止。为了获得最佳性能，需要对外循环中的候选和内循环中的计算进行适当排序。 该顺序如下执行。 SAX表示和LSH散列的组合用于在候选项上创建群集。 映射到成员较少的簇的候选者首先会在外部循环中进行检查，以在算法执行的早期发现高质量的异常值。 在内部循环中首先检查出现在与外部循环候选相同的集群中的对象，以确保内部循环的快速终止。这有助于更好的修剪性能。书目注释包含指向基于SAX的群集在形状异常值检测中创建的具体细节的指针。

16.2.6 形状分类

假设使用一组N个标记的形状来进行训练。这个训练好的模型用于执行测试实例的分类，标签未知。从空间到时间序列数据的转换是基于距离分类算法的有用工具。如聚类和异常值检测一样，该过程的第一步是将形状转换为时间序列。这将问题转化为时间序列分类问题。有关时间序列分类的许多方法在第14章的14.7节讨论过。与在14.7节中提出的任何基于距离的方法的主要区别是需要考虑形状的旋转不变性。时间序列分类可以在形状被转换成时间序列之后使用。这是因为基于距离的方法可以很容易地通过使用方程式旋转不变如公式16.1。两种主要的基于距离的时间序列分类方法包括最近邻方法和基于图的集体分类方法。最近邻方法相对简单，下面将详细讨论基于图的方法。 基于图形的方法是直观的，因为它要求测试实例在训练时可用。当更多数量的测试实例与训练数据一起可用时，可以使用后一种方法。因此，不同的方法可能更适合不同的场景。 图形分类的总体方法可以描述如下：

1. 通过使用16.2.1小节中描述的质心扫描方法，将训练形状和测试形状转化为时间序列。

2. 使用3.4.13小节中描述的任何距离函数在形状上构建一个邻域图。如果需要，使用距离函数的旋转不变版本，如方程16.1。每个形状代表一个节点，它连接到具有边缘的k个最近的邻居。 标记的形状对应于标记的节点。19.4小节描述的集体分类方法用于将标签分配给未标记的节点（如测试形状）。

在某些情况下，旋转不变性可能不是特定于应用程序的需求。在这种情况下，距离计算的效率得到提高

16.3轨迹挖掘

轨迹数据出现在各种空间应用中。GPSenabled设备（如手机）的激增使得大规模收集轨迹数据成为可能。 可以对轨迹数据进行分析以获取各种各样的见解，例如确定协同定位模式，群集和异常值。 轨迹数据与本章讨论的其他类型的空间数据在以下几个方面不同：

1. 在本章到目前为止所讨论的空间数据应用中，空间属性是上下文的，而其他类型的属性（例如气象应用中的温度）是行为的。 在轨迹数据的情况下，空间属性是行为的。

2. 轨迹数据中唯一的上下文属性是时间。 因此，轨迹数据可以被认为是时空数据。 尽管在前面部分中讨论的情景也可以通过在上下文属性中包含时间来进一步推广，但在这些情况下空间属性不是行为的。 例如，随着时间的推移跟踪海面温度，空间和时间属性都是上下文相关的。

轨迹分析通常以两种不同方式之一进行：

1. 在线分析：在线分析中，实时分析轨迹，并且在给定时间的轨迹中的模式与分析最相关。

2. 基于形状的分析：在基于形状的分析中，时间变量已经从分析中删除。例如，在不同时期形成的两个相似的轨迹可以有意义地相互比较。例如，一组轨迹是基于它们的形状，而不是它们在运动中的同时性。

轨迹数据中的两种分析类似于时间序列数据。这并不奇怪，因为轨迹数据是时间序列数据的一种形式。

16.3.1轨迹的等价性和多元时间序列

轨迹数据是多元时间序列数据的一种形式。对于二维轨迹来说，轨迹的X坐标和Y坐标构成了多元系列的两个分量。三维轨迹将导致三元系列。由于多变量时间序列和轨迹数据之间的等价性，可以在任一方向执行转换以便于使用为每个域设计的方法。例如，轨迹挖掘方法可以用于非空间应用。特别是，任何n维多变量时间序列都可以转换为轨迹数据。在多变量时间数据中，通常使用多个传感器同时测量不同的行为属性。考虑英特尔研究伯克利传感器数据[556]的例子，该数据在英特尔伯克利实验室随着时间的推移测量不同的行为属性，例如温度，压力和电压。例如，温度和电压传感器在同一段时间内的行为如图16.7a，b所示。 通过消除公共时间属性或创建包含时间和其他两个行为属性的三维轨迹，可以显示两个行为属性的变化。 这些轨迹的例子分别在图16.7c，d中示出。图16.7d说明了这些轨迹中最通用的轨迹。 该图显示了所有三个属性的同时变化。通常，具有$n$个行为属性的多变量时间序列可以映射到$(n+1)$维的轨迹。大多数轨迹分析方法都是在2维或3维的假设下设计的，尽管在需要时它们可以推广到$n$维。

16.3.2 将轨迹转换为多维数据

由于轨迹和多变量时间序列之间的等价性，轨迹也可以转换为多维数据。这是通过对轨迹的时间序列表示使用小波变换来实现的。时间序列的小波变换在2.4.4.1小节介绍过，在这种情况下，时间序列是多变量的，因此有两个行为属性。每个这些行为属性的小波表示都是独立提取的。换句话说，X坐标上的时间序列被转换成小波表示，Y坐标上的时间序列也被转换成小波表示。这产生了两个多维表示，其中一个表示X坐标，另一个表示Y坐标。将这两个表示中的维度组合起来，为轨迹创建单个更高维表示。如果需要，只有较大的小波系数可以被保留以降低维度。将轨迹数据转换为多维数据是使用大量多维方法进行轨迹分析的有效方法。

图16.7：多变量时间序列可以映射到轨迹数据

16.3.3 轨迹模式挖掘

有很多不同的方法可以制定轨迹模式挖掘问题。这是因为轨迹数据的自然复杂性允许多种方式来定义模式。 在下面的章节中，将探讨轨迹模式挖掘的一些常见定义。这些定义绝非详尽无遗，尽管它们确实说明了轨迹分析中的一些最重要的情景。

16.3.3.1频繁的轨迹路径

一个关键问题是确定轨迹数据中频繁的顺序路径。为了从一组轨迹中确定频繁的连续路径，第一步是将多维轨迹（用数字坐标）转换为一维离散序列。一旦执行了此转换，则可以将任何顺序模式挖掘算法应用于转换后的数据。

图16.8：基于网格的轨迹离散化

将多维轨迹转换为离散序列的最有效方法是使用基于网格的离散化。 在图16.8a中，已经说明了轨迹以及基础数据空间的4×4网格表示。 沿着一个维度的网格范围由A，B，C，D和E表示。沿着另一个维度的网格范围由P，Q，R，S和T表示。 2维瓦片由沿着每个维度的范围的组合来表示。 例如，平铺AP表示网格范围A与网格范围P的交点。 因此，每个瓦片具有不同的（离散的）标识符，并且轨迹可以通过它通过的离散标识符的序列来表示。 图16.8a中用于轨迹的阴影贴图如图16.8b所示。 相应的1维序列模式如下： $EP, DQ, CQ, BQ, BR, CS, BT$ 这种变换被称为空间瓦片变换。 原则上，可以通过在每个网格平方花费最少的时间来进一步增强离散化，尽管这里没有考虑这一点。 考虑一个包含N个不同轨迹的数据库。 频繁的顺序路径可以通过使用两步法从这些轨迹确定：

1. 使用基于网格的离散化将N个轨迹中的每一个轨迹转换为离散序列。

2. 应用15章15.2小节中讨论的顺序模式挖掘算法，从结果数据集中发现频繁的序列模式。

通过在顺序模式挖掘过程中引入不同类型的约束条件，如时间间隔约束，也可以将这些约束条件应用于轨迹。 这种基于变换的方法的一个优点是它可以利用顺序模式挖掘的所有不同变体的强大优势。 顺序模式挖掘在基于约束的方法方面有丰富的文献资料。 另一个有趣的方面是，可以修改该公式以解决运动模式在相同时间段发生的情况。运动发生的时间段被离散化为由表示的个m周期,例如1...m，时间间隔可以是[8AM，9AM]，[9AM，10AM]，[10AM，11AM]等等。因此，对于每个时间间隔，网格标识符被标记有相关的时间段标识符。 如果距离该时间范围的最小时间量由该轨迹花费在该区域中，则将时间段标识符标记为网格区域。 这将导致一组模式定义在一组新的格式为$<GridId>:<T imeId>$的离散符号上。 在图16.8a的轨迹中，附加时间段标识符的可能序列如下所示： $EP : 1, EP : 2, DQ : 2, DQ : 3, DQ : 4, CQ : 5, BQ : 5, BR : 5, CS : 6, CS : 7, BT : 7$ 这种转换被称为时空瓦片变换。请注意，该序列比图16.8b中的序列更长，因为轨迹可能在相同网格区域中花费多于一个区间。一组N个不同的序列被提取，对应于N个不同的轨迹。可以在这个新的表示上执行顺序模式挖掘。由于添加了时间标识符，生成的模式将与时间上的同时运动相对应。因此，序列模式挖掘方法在检测相似形状的图案或同时运动模式方面具有显着的灵活性。此外，因为顺序模式挖掘公式不需要频繁序列模式中的连续符号在原始序列中连续，所以它可以忽略底层轨迹中的噪声间隙，而挖掘模式。此外，通过使用不同的约束顺序模式挖掘公式，可以发现不同种类的受限轨迹模式。

该方法的一个缺点是离散化的粒度级可能会影响结果的质量。通过使用空间区域的多粒度离散化可以解决这个问题。转换为符号表示的另一种方法是在对象位置的不同时间快照上使用空间聚类。 可以使用不同快照上的每个对象的群集标识符来构建其序列表示。书目注释包含指向若干从轨迹转换和模式发现算法的指针。许多这些方法的更广泛的想法是转换为更有效的模式挖掘的符号序列表示。

16.3.3.2 空间共定位模式

托管模式旨在发现不同个体的轨迹之间的社交关系。托管模式的基本思想是，经常出现在同一时间点的人可能会彼此相关。托管模式挖掘尝试发现个体的模式，而不是空间轨迹路径的模式。 由于此分析的互补性，序列数据库的垂直表示特别方便。 类似的网格离散化（针对频繁轨迹模式设计）可用于预处理。然而，在这种情况下，在不同时间在网格区域中的不同个体的位置使用稍微不同的（垂直）表示。对于每个网格区域和时间间隔对，确定人员标识符（或轨迹标识符）的列表。因此，对于网格区域EP和时间间隔5，如果存在人员3,9和11，则构造相应的集合： $EP : 5 ⇒ {3, 9, 11}$ 请注意，这是一个无序集合，因为它代表了特定（空间，时间）对中存在的个体。 在至少有两个人填充的所有（空间，时间）对上可以构建一个类似的集合。 这可以被视为序列数据库的垂直表示。 在第4章讨论何频繁模式挖掘算法，可以应用于任意结果集的数据库。频繁模式对应于同居个体的频繁集合。 这些人往往可能是社会相关的个人。

16.3.4 轨迹聚类

在下文中，将提供对不同种类的轨迹聚类算法的详细讨论。 由于两个问题之间的密切关系，轨迹聚类算法自然与轨迹模式挖掘相关。 轨迹聚类方法有两种类型。

1. 第一种类型的方法使用传统的聚类算法，使用轨迹之间的距离函数。一旦设计了距离函数，就可以使用许多不同类型的算法，例如 k-medoids或基于图形的方法。
2. 第二种类型的方法使用数据转换和离散将轨迹转换为离散符号序列。可以将不同类型的转换应用于轨迹，例如分段提取或基于网格的离散化。转换之后，将模式挖掘算法应用于所提取的符号序列。

另外，还为轨迹聚类设计了许多其他临时方法。 本节将只关注系统技术。 书目注释包含指向特定方法的指针。

16.3.4.1 计算轨迹之间的相似性

轨迹聚类的一个关键方面是能够计算不同轨迹之间的相似性。乍一看，由于轨迹分析的空间和时间方面，相似函数计算似乎是一项艰巨的任务。然而，在实践中，轨迹之间的相似性计算与时间序列数据的相似性计算没有很大不同。正如在16.3节中所讨论的那样，轨迹数据相当于多元时间序列数据。第3章中讨论了几种动态编程算法。用于单变量时间序列数据中的相似性计算。这些算法可以推广到多变量的情况。在下文中，将讨论动态时间规整算法到多变量情况的扩展。类似的方法可以用于其他动态编程方法。建议读者重读第3章3.4.1.3小节在进一步阅读之前动态时间翘曲。 首先，简要回顾关于单变量时间序列距离的讨论。令$DTW(i，j)$分别为两个单变量时间序列$\overline{X} =(x_1 ... x_m)$和$\overline{Y} =(y_1 ... y_n)$的第一个和第一个j元素之间的最佳距离。然后，递归地定义$DT W(i，j)$的值如下：

$$ DTW(i, j)= distance(x_i, y_j)+min \begin{cases} DT W (i, j − 1), & \text {repeat $x_i$} \ DT W (i − 1, j), & \text{repeat $y_i$} \ DT W (i − 1, j-1), & \text{otherwise} \end{cases} \tag{16.2} $$ 在二维轨迹的情况下，每个轨迹都有一个多变量时间序列，对应于每个轨迹的两个坐标。 因此，第一轨迹具有对应于$\overline{X1} =（x1_1 ... x1_m）和\overline{X2} =(x2_1 ... x2_m)$的两个坐标。第二轨迹具有两个坐标，相对应的$\overline{Y1} =(y1_1 ... y1_m)$和$\overline{Y2} =（y2_1 ... y2_m）$令$\overline{Xi} =(x1_i，x2_i)$表示第i个时间戳处的第一个轨迹的二维位置，并且令$\overline{Y_j} =(y1_j，y2)$表示第j个时间戳处的第二个轨迹的二维位置。然后，与单变量时间序列数据的唯一区别在于用二维距离代替递归中的一维距离。 因此，修改后的多维$DTW$递归$ MDTW(i，j)$如下：

$$M DTW(i, j)= distance(\overline{X_i}, \overline{Y_j})+min \begin{cases} M DTW (i, j − 1), & \text {repeat $\overline{X_i}$} \\ M DTW (i − 1, j), & \text{repeat $\overline{Y_i}$} \\ M DTW (i − 1, j-1), & \text{otherwise} \end{cases} \tag{16.3}$$

请注意，多维$DTW$递归实际上与单变量情况相同，除了术语距离$\overline{X_i}, \overline{Y_j}$，现在是空间坐标之间的多维距离。 例如，可以使用欧几里德距离。 泛化的简单性是由于时间扭曲与时间序列的维数无关。 时间序列中的所有维度都以完全相同的方式进行扭曲。 因此，递归中的一维距离可以用多维距离代替。 还应该指出的是，这个一般原理适用于大部分用于计算时间序列和序列之间的距离的动态编程方法。

16.3.4.2 基于相似性的聚类方法

许多传统的聚类方法（如k-中位数和基于图的方法）都基于数据对象之间的相似性。因此，一旦定义了相似性函数，这些方法可以直接用于任何数据类型。应该指出，这些方法在不同的数据领域非常流行，如时间序列数据或离散序列数据。如14和15章所说，这些方法如何分别用于时间序列和离散序列数据。这里使用的方法与这些章节中的描述完全类似，只是在这种情况下使用多元时间序列相似性度量来进行计算。读者可以参考第6章用于基本描述k-medoids和基于图的方法，适用于多维数据。基于相似性的方法存在的主要问题是，只有当轨迹段相对较短时才能发挥最佳效果。对于更长的轨迹，计算物体对之间的相似性变得更加困难，因为轨迹的很多部分可能是嘈杂的。因此，相似函数的选择变得更加重要。部分讨论的一些相似性函数。第3章3.4.1小节，考虑到相似度计算中的空白。然而，这些方法对多元时间序列和轨迹的有效性具有高度的数据特异性。一般来说，这些相似函数最适用于较短长度的轨迹。

16.3.4.3 作为序列聚类问题的轨迹聚类

轨迹聚类方法可以使用相同的基于网格的离散化方法执行，用于轨迹中的频繁模式挖掘。 采用两步法。 第一步是使用基于网格的离散化将轨迹转换为一维离散序列。 一旦完成了这个转换，就会用到在第15章讨论的序列聚类方法。 整体聚类方法可以描述如下：

1. 使用基于网格的离散化，如在16.3.3.1小节中介绍的，将N个轨迹转换为N个离散序列。
2. 应用15章15.3小节中介绍各种序列聚类方法，从序列中进行聚类。
3. 将序列簇映射回轨迹簇。

正如在16.3.3.1小节中所讲，第一步构建的基于网格的序列可以仅基于网格标识符（空间瓦片变换），或者基于网格标识符和时间区间标识符（时空瓦片变换）的组合。 在第一种情况下，所得到的集群对应于在空间上靠在一起的轨迹，但不一定在时间上。 在第二种情况下，一个星团中的轨迹将在空间上靠近并同时发生。 换句话说，这样的群集代表了在时间上一起移动的对象。 序列聚类方法相对于基于相似性的方法的一个优点是许多序列聚类方法可以忽略聚类过程中序列中不相关的部分。这是因为很多序列聚类方法，如基于子序列的聚类方法（第15章15.3.3节）自然会在聚类过程中允许在轨迹中出现噪音间隙。这一点很重要，因为较长的轨迹通常共享重要的段，但可能有差距或区域不相似。计算这种不匹配区域的能力对于计算轨迹之间距离的相似性函数方法整体而言并不十分有效。

16.3.5 轨迹异常值检测

在这个问题中，假定N个不同的轨迹是可用的，并且需要确定离群轨迹，如与底层数据的趋势显着不同的离群轨迹。与所有数据类型一样，轨迹异常值检测问题与轨迹群集问题密切相关。 特别是，这两个问题都利用了数据对象之间相似性的概念。就数据聚类而言，可以使用基于相似性的方法，也可以使用异常检测的转换方法。

16.3.5.1 基于距离的方法

在轨迹之间设计距离函数的能力提供了使用基于距离的方法来定义异常值的方法。特别是，一旦定义了距离函数，k-近邻方法或任何基于距离的方法都可以很容易地推广到轨迹。例如，可以使用多维时间扭曲距离函数来计算轨迹与N-1个其他轨迹的距离。将第k个最近邻距离报告为异常值分数。其他基于距离的方法（如LOF）也可以扩展到轨迹数据，因为这些方法仅基于距离值，并且与底层数据类型无关。就像聚类一样，这些方法的主要缺点是它可以有效地用于较短的轨迹，但在较长轨迹的情况下效果不佳。这是因为更长的轨迹通常会有许多噪声段，这些噪声段并不能真正反映异常行为，但会破坏潜在的距离函数。

16.3.5.2 基于序列的方法

16.3.3.1节最开始讨论的空间和时空瓦片变换，可用于将轨迹异常值检测转换为序列异常值检测。这种方法的优点是有很多方法可用于序列异常值检测。与其他问题（如轨迹模式挖掘和聚类）一样，该方法由两个步骤组成：

1. 将N个轨迹中的每一个轨迹转换为使用空间分块变换或时空分块变换的序列，如在16.3.3.1小节中讨论的。
2. 使用第15章15.4节中讨论的任何序列异常点检测方法确定异常值序列。
3. 将序列异常值映射到轨迹异常值。

通过改变上述每个步骤中使用的特定子程序，这种方法在它可以找到的异常值类型方面特别丰富。 这种变化的一些例子如下：

• 在序列转换的第一步中，可以使用空间或时空瓦片。 当使用空间贴图时，发现的异常值仅基于轨迹的形状，而不是基于一起移动的对象。 从以应用为中心的角度来看，考虑出租车的轨迹由GPS跟踪的情况，并且需要确定在任何时间段相对于其他出租车采取异常路线的出租车。 这样的应用程序可以很好地解决空间瓷砖。 时空瓦片追踪在线趋势。 例如，对于一群带GPS标记的动物，如果某个特定的动物偏离了它的群体，则报告为异常值。
• 用于序列异常值检测的配方特别丰富。例如，序列异常值检测允许报告位置异常值或异常值组合。 这在第15章15.4节中详细讨论。在变换的序列中放置异常值，映射到轨迹中的异常位置。 例如，一个出租车司机在一个交叉路口发生异常转弯时将被检测到。 另一方面，组合异常值将映射到不寻常的轨迹段。

因此，基于序列的转换在能够检测不同类型异常值的丰富多样性方面特别有用。 它可以根据所有时期或特定时期的运动模式确定离群值。 它还可以发现轨迹任何部分的小部分异常值

16.3.6 轨迹分类

在这个问题中，假设提供了N个标记轨迹的训练数据集。 这些被用来构建轨迹的训练模型。 测试轨迹的未知类别标签是使用该训练模型确定的。 由于分类是聚类问题的监督版本，所以用于轨迹分类的方法使用与轨迹聚类相似的方法。 与聚类方法一样，可以使用基于距离的方法或基于序列的方法。

16.3.6.1 基于距离的方法

诸如最近邻居方法和基于图的集体分类方法等几种分类方法仅取决于数据对象之间距离的概念。 在定义了数据对象之间的距离后，这些分类方法对底层数据类型是不可知的。 k-最近邻法的工作原理如下。 确定给定测试实例的top-k最近邻居。 主导类标签被报告为测试实例的相关标签。时间序列距离函数的任何多元扩展（例如多维DTW）可用于计算过程。 在基于图的方法中，在数据对象上构建k-最近邻图。这是一种半监督方法，因为图形是在标记和未标记对象的混合物上构建的。基于图的方法的基本讨论可在11章11.6.3节中找到。每个节点对应一个轨迹。如果j在i的k个最近邻居之中，则从节点i向节点j添加无向边，或者反之亦然。这产生了一个图表，其中仅标记了对象的子集。目标是使用带标签的节点来推断网络中未标记节点的标签。这是集体分类问题，19章19.4节中将详细讨论。当使用集体分类方法确定未标记节点上的标签时，它们将映射回原始数据对象。当许多测试实例与训练实例同时可用时，这种方法最为有效。

16.3.6.2 基于序列的方法

在基于序列的方法中，第一步是使用基于空间或时空瓦片的方法将轨迹转换为序列。一旦完成了这个转换，就可以使用在第15章中讨论序列分类方法。因此，总体方法可以描述如下： 1. 将N个轨迹中的每一个轨迹转换为使用空间分块变换或时间分块变换的序列，这在16.3.3.1节的开头讨论过。 2. 使用15章15.6节中讨论的任何序列分类方法来确定序列的类别标签。 3. 将序列类标签映射到轨迹类标签

空间瓦片变换和时空瓦片变换方法在将不同的空间和时间特征结合到分类过程中提供了不同的能力。当使用空间瓦片变换时，所得到的分类不是时间敏感的，并且来自不同时期的轨迹可以基于它们的形状一起建模。另一方面，当使用时空瓦片变换时，只能对相同的近似时间段的轨迹进行分类。换句话说，训练和测试轨迹必须来自相同的时间段。在这种情况下，分类模型不仅对轨迹的形状敏感，而且对其运动可能发生的精确时间也很敏感。在这种情况下，即使所有的轨迹具有完全相同的形状，由于各种时间的速度时间差异，标签也可能不同。模型的精确选择取决于具体应用的标准。

16.4 总结

空间数据在各种应用中很常见，例如气象数据，轨迹分析和疾病暴发数据。 这些数据几乎总是一种上下文数据类型，其中数据属性被划分为行为属性和上下文属性。 空间属性可以是上下文或行为。 这些不同类型的数据需要不同类型的处理方法。 在气象数据的情况下出现上下文空间属性，其中在不同的空间位置处测量不同类型的空间属性，例如温度或压力。另一个例子是图像数据的情况，其中不同空间位置处的像素值被用来推断图像的属性。基于形状的空间数据的一个重要转变是可以将形状转换为时间序列的质心扫描方法。另一个重要的转变是可以将空间数据转换为多维表示的空间小波方法。这些转换对于几乎所有的数据挖掘问题都很有用，例如聚类，异常值检测或分类。 在轨迹数据中，空间属性是行为的，唯一的上下文属性是时间。轨迹数据可以被视为多变量时间序列数据。因此，时间序列距离函数可以推广到轨迹数据。这在开发仅依赖于距离函数设计的各种数据挖掘方法中很有用。轨迹数据可以使用基于瓦片的变换转换为序列数据。基于平铺的转换非常有用，因为它们允许将多种序列挖掘方法用于模式挖掘，聚类，异常值检测和分类等应用。

16.5 书目注释

空间数据挖掘问题已经在地理数据挖掘和知识发现的背景下得到了广泛的研究[388]。 有关空间数据库的详细讨论可参见[461]。搜索和索引问题是空间数据中最早的应用之一[443]。 [547]中讨论了形状数据挖掘的质心扫描方法。有关非空间行为属性的空间共置模式发现的讨论见[463]。此方法已成功用于许多数据挖掘问题，如聚类，分类和异常值检测。 [5]详细讨论了空间数据异常检测问题。 本书包含有关空间数据异常值检测的专门章节。 文献中已经设计了许多用于空间和时空异常值检测的方法[145,146,147,254,287,326,369,459,460,462]。 在[510]中提出了异常形状检测算法。 [375]中提出了基于瓦片的轨迹模式挖掘简化。轨迹数据中的模式挖掘与聚类密切相关。[352]中讨论了从轨迹中挖掘周期性行为的问题。移动物体簇被研究为Swarms[351]，Flocks [86]和Convoys [290]。其中，Swarms提供了最宽松的定义，允许有噪音的空隙。在这些嘈杂的间隙期间，来自同一集群的物体可能不会一起移动。[429]中提出了一种在社会感知应用中从轨迹维护实时社区的算法。[338]中提出了一种将较长的轨迹分割成更小的分段以进行基于形状的聚类的方法。[117]研究了运动物体流轨迹的异常监测。 Top Eye方法是一种用于监视运动物体轨迹中的top-k异常的算法，在[226]中提出。 TRAOD算法发现基于形状的轨迹异常值，在[337]中提出。[339]中提出了一种使用基于区域和基于轨迹的聚类进行分类的方法。

16.6 习题

1. 讨论如何将空间小波推广到有n个上下文属性的情况。
2. 使用小波实现算法，从空间数据构建多维表示。
3. 描述将形状转换为多维表示的方法。
4. 实现将形状转换为时间序列数据的算法。
5. 假设您在空间网格上连续时刻有N个不同的海面温度快照。您想要确定连续时间点之间发生重大变化的连续区域。描述使用空间小波识别这些区域和时刻的方法。
6. 假设练习5的快照不是来自连续的时刻。如何使用空间小波识别与其他快照截然不同的空间快照？您如何识别与其余数据截然不同的特定区域？
7. 假设您使用基于瓦片的方法来查找频繁的轨迹模式。讨论序贯模式挖掘的不同约束变体如何映射到顺序轨迹模式的不同约束变体。
8. 提出一种基于快照的聚类方法，将轨迹转换为符号序列。讨论基于瓦片的方法的优缺点。
9. 实现将轨迹转换为符号序列的不同变体，并使用基于瓦片的技术进行频繁轨迹模式挖掘。
10. 讨论如何使用小波在轨迹上执行不同的数据挖掘任务。