

14 挖掘时间序列数据

时间存在的意义就是就是任何事都不可能立刻实现——阿尔伯特•爱因斯坦

14.1引言

时间数据在数据挖掘应用中很常见。 通常，这是由硬件或软件监控设备收集数据的连续发生过程的结果。 领域的多样性非常重要，并且从医疗领域延伸到金融领域。 这些数据的一些例子如下：

• 传感器数据：传感器数据通常由各种硬件和其他监控设备收集。 通常，此数据包含有关底层数据对象的连续读数。 例如，环境数据通常采用不同种类的测量温度，压力，湿度等的传感器来收集。 传感器数据是时间序列数据最常见的形式。

• 医疗设备：许多医疗设备如心电图（ECG）和脑电图（EEG）会产生连续的时间序列数据流。 这些代表人体功能的测量值，如心跳，脉率，血压等。实时数据也是从患者监护病房（ICU）收集的，以监测他们的病情。

• 金融市场数据：财务数据，如股票价格，通常是暂时的。 其他形式的时间数据包括商品价格，工业趋势和经济指标。

通常，时间数据可以是离散的或连续的。 例如，Web日志数据包含一系列与用户点击对应的离散事件，而环境数据可能包含一系列连续值，例如温度。 连续的时间数据集被称为时间序列，而离散的时间数据集被称为序列。 本章重点介绍连续时间序列数据。 接下来的章节将研究离散序列数据的数据挖掘方法。 虽然时间序列和离散序列数据在概念上是相似的，但每个域中使用的算法方法存在显着差异。 然而，在很多情况下，时间序列数据通过离散化转换为离散序列数据，以便于应用丰富的序列挖掘技术。 本章还讨论了这种情况。

与多维数据的所有属性都被同等对待不同，时间序列数据被视为上下文数据表示。 在上下文数据表示中，属性有两种类型:

• 上下文属性：这些属性表示提供测量所在上下文的属性。 换句话说，上下文属性提供了衡量行为值的参考点。 对于时间序列数据的情况，单个上下文属性对应于时间维度。 某些数据类型（如空间数据）可能包含与空间坐标相对应的多个上下文属性。 时间戳可以对应于测量数据点的实际时间值，或者它们可以对应于测量这些值的连续指数（或滴答）。

• 行为属性：它们代表参考点处的行为值。 例如，在环境传感器中，这可以对应于温度属性。 通常，每个上下文属性值（例如，时间戳）具有相应的行为属性值（例如，温度）。 行为属性通常是从应用程序特定的角度来看有趣的属性，但是如果不了解上下文属性，就无法正确解释行为属性。 当每个系列有多个行为属性时，相应的系列被称为多元时间序列。

对上下文数据类型的分析更加困难，因为不使用上下文属性就无法有效地解释行为属性值。 例如，连续时间戳（上下文属性）之间的行为属性的突然变化通常表示异常行为。 因此，与多维数据不同，问题的定义取决于情景和行为属性之间相互关系的组合。 因此，需要对集群，分类和异常值检测等问题进行重大修改，以考虑上下文属性的影响。 后续章节讨论的几种数据类型属于这一类。 其他例子包括序列数据和空间数据。

​时间序列数据的更大复杂性使得更多的问题定义成为可能。 大多数模型可以分为两种类型之一：

1. 实时分析：在实时分析中，实时分析一个或多个序列中的数据点，进行预测。 通常，在不同的数据流上使用近期历史的小窗口进行分析。 这种分析的例子包括预测，偏差检测或事件检测。 当多个系列可用时，通常以时间同步的方式分析它们。 即使在诸如聚类的数据挖掘应用被应用于这些问题的情况下，分析通常也是实时进行的。
2. 回顾性分析：在回顾性分析中，时间序列数据已经可用，随后进行分析。 数据库中不同时间序列的分析有时不会随时间同步。 例如，在ECG读数的时间序列数据库中，数据可能已经在不同时期记录。

这两种分析形式都适用于不同的应用。 此外，这两种情况对于相同的应用程序（例如聚类或异常值检测）有不同的解释。 这些问题将在后面的章节中详细讨论。

本章安排如下。 下一节介绍时间序列准备和相似性的方法。 由于时间序列相似性的方法已经在第三章中详细讨论过。 本章只对它们进行概述。 读者可以参考Chap3的相关章节， 对不同的时间序列的相似性措施。 时间序列预测的问题在14.3讨论。 时间序列主题发现在14.4节讨论。 第14.5节讨论聚类时间序列的问题。 离群值检测在14.6节讨论。 时间序列分类在14.7节中讨论。 本章的内容摘录在14.8节。

14.2 时间序列准备和相似性

时间序列数据可以是单变量也可以是多变量。 在单变量时间序列数据中，单个行为属性与每个时刻相关联。 在多元时间序列数据中，多个行为属性与每个时刻相关联。 因此，时间序列的维度是指被跟踪的行为属性的数量。

**定义14.2.1（多元时间序列数据）**长度为n和维度d的时间序列在每个时间戳$t~1~$处包含d个数字特征$t_n$。 每个时间戳都包含每个d系列的组件。 因此，在时间戳$t_i$处接收的值集合为 $\overline{Y_i}=（y^1_i… y^d_i）$。 时间戳$t_i$处的第j个序列的值是$y^j_i$

在一个单变量时间序列中，d的值为1。在这种情况下，一系列长度n被表示为一组与时间戳$t_1$……$t_n$相关联的标量行为值$y_1$ …… $y_n$。

14.2.1 缺失值处理

时间序列数据常常包含缺失值。 此外，当由独立传感器收集时，该系列的值可能无法及时同步。 时间序列值在数据处理的不同行为属性间是等间隔和同步的，这通常很方便。 用于处理缺失，不等间隔或非同步值的最常用方法是线性插值。 这个想法是在所需的时间戳创建估计值。 这些可用于生成同步，等距，并且没有缺失值的多变量时间序列。

考虑yi和yj分别是时间ti和tj时间序列的值，其中i <j。 设t是从区间（$t_i$，$t_j$）中抽取的时间。 然后，该系列的内插值由下式给出：

$y=y_i+(\frac{t-t_i}{t_j-t_i})·(y_j-y_i)\tag{14.1}$

这是简单的线性插值，但也可以使用其他更复杂的方法，如多项式插值或样条插值。 然而，这样的方法在估计的时间窗口中需要大量的数据点。 在很多情况下，这种方法不能提供比直接线性插值法更好的结果。

14.2.2 噪音消除

易受噪音影响的硬件（如传感器）通常用于时间序列数据收集。 大多数噪音消除方法使用的方法是消除短期波动。 应该指出的是，噪声和有趣的异常值之间的区别往往是很难做出的。 有趣的离群值是由数据生成过程的特定方面引起的波动，而不是数据收集过程的人为因素。 因此，这种清理和平滑方法有时不适用于异常点检测等问题。 称为分箱和平滑的两种方法通常用于消除噪音。

分档

合并的方法将数据划分为由[$t_1，t_k$]，[$t_{k+1}，t_2k$]等表示的大小为k的时间间隔。假定时间戳等距分隔。 因此，每个垃圾箱尺寸相同，并且包含相同数量的点。 每个间隔中的数据点的平均值报告为平滑值。 令$y_{i·k+1}… y_{i·k+k}$是时间戳$t_{i·k + 1 }… t_{i·k + k}$的值。 然后，新的分箱值将是$y'_{i+ 1}$，其中

$y'_{i+ 1}=\frac{\sum^{k}_{r=1}y_{i·k+r}}{k}$

因此，此方法使用分箱中值的平均值， 也可以使用行为属性值的中位数。 通常情况下，中位数提供比平均值更强的估计值，因为异常点不会以不成比例的方式影响中位数。 分箱的主要问题是它将可用数据点的数量减少了k倍。 分类也被称为分段聚合近似（PAA）。 尽管对于快速距离计算[309]它也可能是有利的，因为它提供了压缩表示，这种方法对于较大的k值可能是相当有损的。

移动平均平滑

移动平均方法通过使用重叠箱来减少箱的损失，在箱上计算平均值。 就分箱而言，平均值是在时间序列的窗口上计算的。 主要区别在于，在系列中的每个时间戳处开始构建一个bin，而不是仅在分档边界处的时间戳。 因此，仓间隔被选择为$[t_1，t_k]，[t_2，t_{k + 1}]$等。这导致一组重叠间隔。 时间序列值在这些间隔中的每一个上被平均。 移动平均线也称为滚动平均线，由于平均线的平滑效应，它们可以减少时间序列中的噪音。

在实时应用程序中，移动平均数只有在窗口的最后一个时间戳之后才可用。 因此，移动平均线会在分析中引入滞后因素，并且由于边界效应而在系列开始时会丢失一些点。 此外，由于平滑，有时会损失短期趋势。 较大的文件夹大小会导致更大的平滑和滞后。 由于滞后的影响，移动平均有可能包含原始序列中出现峰值（或上升趋势）的谷底（或下跌趋势），反之亦然。 这有时会导致对最近趋势的误解。

图14.1：2013年9月5日至2014年9月4日期间适用于IBM股票价格的各种平滑方法

指数平滑

在指数平滑中，平滑值$y'_i$被定义为当前值$y_i$和先前平滑值$y'_{i-1}$的线性组合。 平滑参数α∈（0,1）用于此目的。

$y'_i=\alpha·y_i+(1-\alpha)·y'_{i-1}\tag{14.1}$

y0'的值通常设置为序列中的第一个点。 当α的值为1时，不存在平滑效果，平滑序列与原始序列相同。 当α的值为0时，整个系列变为平滑到$y'_0$的常数值。 该方法被称为指数平滑，因为$y'_i$的值可以表示为系列值的指数衰减总和。 通过递归地将上述等式代入其自身，可以显示以下内容：

$y'_i=(1-\alpha)^i·y'_0+\alpha·\sum^{i}_{j=1}{y_j·(1-\alpha)^{i-j}\tag{14.1}}$

$\alpha$的选择调节衰减因子。 与移动平均值不同，指数平滑对最近的数据点提供了更多的重要性。 数据点在系列开始时不会丢失，并且在相同的平滑水平下，滞后的影响会降低。 移动平均和指数平滑的例子分别如图14.1a，b所示。 显而易见，指数平滑在系列开始时不会丢失任何点，并且通常对较低的滞后提供稍好的平滑。

14.2.3 正常化

通常需要对时间序列进行归一化，特别是在同时分析多个序列时。 例如，一个序列可能测量温度，而另一个序列可能测量压力。 因为这些数值是以不同的尺度衡量的，所以它们不能被有意义地比较。 因此，通常使用两种归一化方法来调整这种变化。

1. 基于范围的归一化：在基于范围的归一化中，确定时间序列的最小值和最大值。 让这些值分别用min和max表示。 然后，时间序列值$y_i$被映射到范围（0,1）中的新值$y'_1$，如下所示：$<span><span class="MathJax_Preview">y'_i=\frac{y_i-min}{max-min}\tag{14.4}</span><script type="math/tex">y'_i=\frac{y_i-min}{max-min}\tag{14.4}$
2. 标准化：在标准化中，序列的平均值和标准差用于标准化。 这实际上是时间序列的Z值。 令μ和σ表示时间序列中的值的平均值和标准差。 然后，时间序列值yi如下映射到新的值$z_i$：$<span><span class="MathJax_Preview">z_i=\frac{y_i-\mu}{\sigma}\tag{14.5}</span><script type="math/tex">z_i=\frac{y_i-\mu}{\sigma}\tag{14.5}$

标准化通常是首选的方法。 但是，它不能保证时间序列值的特定范围。

14.2.4数据转换和压缩

存在各种预处理方法用于将时间序列数据转换和缩减为简化表示。 其中一些方法将数据转换为数量较少的数字系数，而其他方法将数据转换为离散值。

14.2.4.1离散小波变换

离散小波变换（DWT）将时间序列转换为多维数据。虽然通过将不同时间戳的值作为维度查看可以被视为多维数据的时间序列，但是连续时间戳中的值彼此高度相关。多维方法的直接应用忽略了数据值的时间连续性。在小波中，系数描述该系列的不同连续时间区域的特性。每个系数等于一系列仔细选择的系列连续片段之间的行为属性平均值差异的一半。得到的表示可以像多维数据一样更容易分析，因为时间局部性已经包含在系数中。通过仅使用最大的表示系数，可以准确地重建整个时间序列。通常，保留系数的数量远小于原始时间序列的长度。因此，该方法也是一种降维方法。 DWT在章节2.4.4.1中有详细描述。

14.2.4.2 离散傅立叶变换

当序列中的大部分变量都可以在序列的特定局部区域捕获时，小波最有效。 在该序列包含全局周期性的情况下，离散傅里叶变换（DFT）更为有效。 图14.2提供的其中任何一种方法都能很好地执行的情景示例。 基本的想法是任何系列长度n可以表示为平滑周期正弦级数的线性组合。 除了一个常数项外，n - 1个正弦级数的周期数是从n，n / 2，n / 3，... n /（n - 1）给出的。 使用这种分解可以压缩数据，因为只有少数这些组成序列有足够大的贡献被包括在内。 考虑一个时间序列$x_0$……$x_{n-1}$。 傅立叶变换的每个系数$<span><span class="MathJax_Preview">X_k</span><script type="math/tex">X_k$是一个复数值，其定义如下：$<span><span class="MathJax_Preview">X_k=\sum^{n-1}_{\gamma=0}x_\gamma·e^{-i\gamma\omega k}=\sum^{n-1}_{\gamma=0}x_\gamma·cos(\gamma\omega k)-i\sum^{n-1}_{\gamma=0}x_\gamma·sin(\gamma\omega k)\forall k\in{0……n-1}.\tag{14.6}</span><script type="math/tex">X_k=\sum^{n-1}_{\gamma=0}x_\gamma·e^{-i\gamma\omega k}=\sum^{n-1}_{\gamma=0}x_\gamma·cos(\gamma\omega k)-i\sum^{n-1}_{\gamma=0}x_\gamma·sin(\gamma\omega k)\forall k\in{0……n-1}.\tag{14.6}$

这里，将$\omega$设定为2π/n弧度，并且记号i表示虚数$\sqrt{-1}$。 因此，$X_k$是一个复杂的值。 傅立叶系数的一个性质是$X_{n-k}$可以是通过翻转虚数部分的符号使得k≥1（参见练习7）,这个过程从Xk导出。 因此，只需要保留前n / 2个复系数。 此外，只需要保留具有大能量$a^2_k + b^2_k$的系数$X_k = a_k + ib_k$。 m最高的系数（连同它们的指数k）可用于以紧凑的方式拟合时间序列。 系数的实部和虚部都可以存储在实向量数据结构中。 该矢量提供了该序列的简化表示。 原始序列可以从系数重建如下：$<span><span class="MathJax_Preview">x_\gamma=\frac{1}{n}\sum^{n-1}_{k=0}X_k·e^{i\gamma\omega k}=\frac{1}{n}(\sum^{n-1}_{k=0}X_k·cos(\gamma\omega k)+i\sum^{n-1}_{k=0}X_k·sin(\gamma\omega k))\forall \gamma\in{0……n-1}.</span><script type="math/tex">x_\gamma=\frac{1}{n}\sum^{n-1}_{k=0}X_k·e^{i\gamma\omega k}=\frac{1}{n}(\sum^{n-1}_{k=0}X_k·cos(\gamma\omega k)+i\sum^{n-1}_{k=0}X_k·sin(\gamma\omega k))\forall \gamma\in{0……n-1}.$

请注意，每个$X_k$都是一个复杂的值。 然而，这个方程右边的虚部总是计为零，以产生实际的系列值$x_r$。

DFT有几个属性，这对数据挖掘应用程序很有用。 它满足可加性属性; 两个系列的和（或差）的傅立叶系数可以作为它们的傅立叶系数的和（或差）被获得。 它也满足了Parseval的定理，它表明如果$X_k = a_k + ib_k$是第k个傅立叶系数，那么我们有$\sum^{n-1}_{r=0}x^2_r=\frac{1}{n}\sum^{n-1}_{k=0}(a^2_k+b^2_k)$。 由于这些性质，可以计算通过计算它们的傅立叶系数之间的欧几里德距离来计算两个时间序列之间的欧几里德距离（压缩的)。 与DWT类似，除了每个基矢量$B_k = [1，e^{i\omega k}，e^{2i\omega k}，…，e^{(n-1)i\omega k}]$以外，DFT也可以看作是时间序列转换为新的（旋转的）正交基系统 ，其中$B_k$的傅立叶系数是一个复矢量。 因此，可以按照相互正交的基底矢量$\overline{B_0}…\overline{B_{n-1}}$来分解时间序列如下：$<span><span class="MathJax_Preview">(x_0…x_{n-1})=\frac{1}{n}\sum^{n-1}_{k=0}X_k\overline{B_k}\tag{14.7}</span><script type="math/tex">(x_0…x_{n-1})=\frac{1}{n}\sum^{n-1}_{k=0}X_k\overline{B_k}\tag{14.7}$

通常，现成的数学软件包可用于使用快速傅立叶变换（FFT）计算系数。 被称为离散余弦变换（DCT）的紧密相关的变换提供了更好的压缩。

14.2.4.3 符号集合逼近（SAX）

这种方法将时间序列转换为离散序列数据。基本思想是通过在时间序列的连续和等间隔窗口上平均行为属性值来确定分段聚合近似。所得到的连续值被离散化为少量的离散值。根据应用情况，断点数可能在3到10之间变化。该方法选择离散化的断点，以便每个符号值具有大致相等的表示频率。一种可能性是使用连续值的等深度离散化，但对于长串或串流系列而言这可能是不切实际的或不可行的。对于长序列或串流序列，使用得到的平均值的高斯分布假设来确定离散化断点。这个想法是选择高斯曲线上的点，以便连续断点之间的区域相等，因此不同的符号具有大致相同的频率。

时间序列相似性度量

时间序列相似性度量通常是针对特定的应用程序的目标而设计的。时间序列相似度计算的最常见方法是欧几里德距离和动态时间规整（DTW）。欧几里德距离和多维数据定义方式相同，其中不同时间戳处的行为属性值被解释为维度。欧氏距离只能在两个序列具有相同长度时才能使用，并且数据点之间存在一一对应关系。这在不同步的时间序列中是不恰当的，数据可能在时间序列的不同部分以不同的速率产生。 DTW方法在其中一个系列的不同部分以不同方式拉伸和缩小时间维度，以创建最佳匹配。正如16.3.4.1章节讨论。如图16所示，DTW也可以扩展到多变量时间序列，例如轨迹数据。其他两个相似/距离函数包括编辑距离和最长公共子序列。这些测量更常用于离散序列，而不是连续的时间序列。所有这些措施都详细描述在3.4.1 3章节。

14.3时间序列预测

预测是时间序列分析最常见的应用之一。 对未来趋势的预测可应用于零售业，经济指标，天气预报，股票市场以及其他许多应用场景。 在这种情况下，我们有一个或多个数据值序列，并且希望使用先前值的历史来预测该序列的未来值。

图14.3：不同操作对平稳和非平稳序列的影响

时间序列可以是静止的也可以是非静止的。平稳随机过程是指其参数（如均值和方差）不随时间变化的过程。非平稳过程是其参数随时间变化的过程。某些时间序列如白噪声是静止的。白噪声是平稳性最强的一种形式，具有零均值，常数方差和以固定滞后间隔的序列值之间的零协方差。另一方面，考虑这种情况，其中行为属性对应于诸如原油之类的工业商品的价格水平。这通常是非平稳的，因为由于通货膨胀，平均价格水平可能会随着时间而增加。事实上，实际应用中的大多数时间序列都是非平稳的。平稳序列通常被表征为不同序列值之间的水平趋势，恒定方差和零协方差的噪声序列。例如，在图14.3a中，两个系列都是非平稳的，因为平均值随时间增加。另一方面，在图14.3b中，虚曲线是平稳的，因为趋势不随时间显着变化。严格平稳的时间序列定义如下：

**定义14.3.1（严格平稳时间序列）**一个严格平稳的时间序列是其中任何时间区间[a，b]中的值的概率分布与移位区间[a + h，b + h ]为时间偏移h的任何值。

换句话说，变量子集的所有多变量分布必须与它们的移位对应物相匹配。静止时间序列的基于窗口的统计参数可以用一种有意义的方式进行估计，因为这些参数在不同的时间窗口中不会变化。在这种情况下，估计的统计参数是未来行为的良好预测指标。另一方面，该系列的当前均值，方差和统计相关性并不一定是未来行为的非平稳序列回归预测模型的良好预测因子。因此，在预测分析之前将非平稳序列转换为固定序列通常是有利的。在对固定序列进行预测后，使用逆变换将预测值转换回原始表示。然而，定义14.3.1的严格平稳性概念太严格，不适合在实际应用中使用。例如，甚至很难确定一个时间序列是否严格来自一个实例，因为我们必须全面地表征变量子集的所有多变量分布。

一个关键的观察结果是，获得或转换为展现弱平稳性质的序列要容易得多。在这种情况下，与白噪声不同，序列的平均值和近似相邻时间序列值之间的协方差可能是非零的，但随时间变化是恒定的。这被称为协变平稳性。这种弱稳定性可以相对容易地进行评估，对于预测依赖于特定参数（如平均值和协方差）的模型也很有用。在其他非平稳序列中，序列的平均值可以用趋势线来描述，该趋势线不一定是水平的，如固定序列所要求的那样。周期性地，该系列将偏离趋势线，可能是因为生成过程发生了一些变化，然后返回到趋势线。这被称为趋势平稳系列。这种弱稳定形式对于创建有效的预测模型也非常有用。下面将讨论常用于将非平稳序列转换为平稳序列的一些实用方法。

差分

用于将时间序列转换为静止形式的常用方法是差分。 在差分中，时间序列值被其与前一个值之间的差值替换。 因此，新值$y'_i$如下：$<span><span class="MathJax_Preview">y'_i=y_i-y_{i-1}.\tag{14.8}</span><script type="math/tex">y'_i=y_i-y_{i-1}.\tag{14.8}$

如果在差分之后该序列是固定的，那么该数据的适当模型是：$<span><span class="MathJax_Preview">y_{i+1}=y_i+e_{i+1}.\tag{14.9}</span><script type="math/tex">y_{i+1}=y_i+e_{i+1}.\tag{14.9}$

这里，$e_{i + 1}$对应于零均值的白噪声。 差分时间序列对于一系列长度t将具有t-1个值，因为不可能将第一个值反映在经过变换的序列中。

高阶差分可用于实现二阶变化的平稳性。 因此，高阶差值y“定义如下：

$$y''_i=y'_i-y'_{i-1}.\tag{14.10}$$

​ $<span><span class="MathJax_Preview">=y_i-2·y_{i-1}+y_i-2\tag{14.11}</span><script type="math/tex">=y_i-2·y_{i-1}+y_i-2\tag{14.11}$

这个模型允许该系列随时间漂移，因为噪音具有非零平均值。该相应的模型如下：$<span><span class="MathJax_Preview">y_{i+1}=y_i+c+e_{i+1}.\tag{14.12}</span><script type="math/tex">y_{i+1}=y_i+c+e_{i+1}.\tag{14.12}$

这里，c是一个非零常数，它说明了漂移。 一般来说，使用二阶以外的差异是很少见的。

一种不同的方法是在季节差异后知道该序列是平稳的时使用季节差异。 季节性差异定义如下：$<span><span class="MathJax_Preview">y'_i=y_i-y_{i-m}.\tag{14.13}</span><script type="math/tex">y'_i=y_i-y_{i-m}.\tag{14.13}$

这里m是一个大于1的整数。

在某些情况下，如几何级数增加的系列，则应用对数函数到差分操作之前的系列值。 例如，考虑以大致恒定的通货膨胀因子增加的价格时间序列。 在这种情况下，在差分操作之前将对数函数应用于时间序列值可能很有用。 图14.3a提供了一个例子，其中通货膨胀的变化是随时间变化的。 很明显，差分操作不能使序列静止不动。 在图14.3b中，对数函数应用于差分操作之前的序列。 在这种情况下，差分运算后该序列变为静止。

下面将讨论一些单变量时间序列预测模型。 这些模型在时间序列模式的不同假设下有效地工作。 其中一些模型假设一个固定的时间序列，而另一些则不。

14.3.1 自回归模型

单变量时间序列包含使用自相关预测的单个变量。 自相关表示一系列相邻时间戳之间的相关性。 通常，位于相邻时间戳的行为属性值是正相关的。 时间序列中的自相关是根据滞后L的特定值来定义的。因此，对于时间序列y1，...，yn，滞后L处的自相关被定义为$y_t$和y之间的Pearson相关系数$y_{t+L}$。$<span><span class="MathJax_Preview">Autocorrelation(L)=\frac{Covariance_t(y_t,y_{t+L})}{Variance_t(y_t)}\tag{14.14}</span><script type="math/tex">Autocorrelation(L)=\frac{Covariance_t(y_t,y_{t+L})}{Variance_t(y_t)}\tag{14.14}$

自相关始终位于[-1,1]的范围内，尽管对于非常小的L值，该值几乎总是正的，并且随着滞后L的增加而逐渐下降。正相关是由于大多数时间序列的相邻值非常相似，尽管相似性随着距离的增加而下降。自相关的高（绝对）值意味着该系列中给定位置处的值可以作为紧前面的窗口中的值的函数来预测。事实上，这是使用自回归模型的关键特性。例如，图14.4a说明了IBM库存实例（图14.1）中自动关联与滞后的变化。这样的数字被称为自相关图，并且在AR模型中被普遍使用。虽然自相关通常是正面的并且会随着滞后而下降，但精确的行为具有很高的应用特定性。对于周期序列，自相关可能是周期性的，并且在某些滞后期间为负值。图14.4b给出了周期正弦波自相关的一个例子。

在自回归模型中，时间t处的$y_t$的值被定义为长度为p的前一个窗口中的值的线性组合。$<span><span class="MathJax_Preview">y_t=\sum^{p}_{i=1}a_i·y_{t-i}+c+\epsilon_t \tag{14.15}</span><script type="math/tex">y_t=\sum^{p}_{i=1}a_i·y_{t-i}+c+\epsilon_t \tag{14.15}$

使用前面的长度为p的窗口的模型被称为AR（p）模型。回归系数$a_1$…… $和c的值，需要从训练数据中学习。 p的值越大，愿意加入自相关的滞后就越大。 p的选择应该由方程的自相关水平来指导。 14.14。由于自相关通常随着滞后L值的增加而减小，因此应选择p的值，使得滞后L = p处的自相关小。在这种情况下，进一步增加回归窗口可能无助于建模过程的准确性，有时可能导致过拟合。通常，自相关图（图14.4）用于识别窗口。而不是使用14.15公式中的系数窗口，也可以选择具有特定滞后值的系数。具体而言，可以选择自相关图中具有高绝对自相关性的滞后值。这种方法对预测周期系列也有帮助。

图14.4：各种序列的自相关图

时间序列数据在过去历史记录中的每个时间戳都会创建时间序列变量之间的线性方程。系数之间的一组线性方程可以通过使用训练数据中每个时间戳的值以及其紧接的前一个长度为p的窗口来创建。当可用时间戳的数量远大于p时，这是一个超定的方程组，这是不可行的。因此，任何（不可行）的解决方案都会有一个与之相关的错误。系数$a_1… a_p$，c可以用最小二乘回归近似，以使超定系统的平方误差最小（参见第11章第11.5节）。请注意，只有当时间序列的关键属性（如均值，方差和自相关）不随时间显着变化时，该模型才能有效用于预测未来值。许多现成的商业求解器可用于这些模型。预测模型的有效性可以通过使用估计系数中的噪声水平来量化。具体而言，R2值也称为确定系数，用于测量白噪声与系列变化的比率：$<span><span class="MathJax_Preview">R^2=1-\frac{Mean_t(\epsilon^2_t)}{Variance_t(y_t)}\tag{14.16}</span><script type="math/tex">R^2=1-\frac{Mean_t(\epsilon^2_t)}{Variance_t(y_t)}\tag{14.16}$

决定系数量化序列中由回归解释的可变部分，而不是随机噪声。 因此希望该系数尽可能接近1。

14.3.2 自回归移动平均模型

虽然自相关是时间序列的有用预测属性，但它并不总是解释所有的变化。 事实上，这些变化的意想不到的部分（冲击）确实会影响时间序列的未来值。 可以使用移动平均模型（MA）捕获此组件。 因此，通过将自回归模型与MA结合，可以使自回归模型更加优良。 在讨论自回归移动平均模型（ARMA）之前，MA将被引入。

移动平均模型根据过去偏离预测值的历史来预测后续的系列值。 与预测值的偏差可被视为白噪声或电击。 此模型最适用于时间戳中的行为属性值取决于时间序列中的冲击历史记录而非实际系列值的情况。 移动平均模型定义如下：$<span><span class="MathJax_Preview">y_t=\sum^{q}_{i=1}b_i·\epsilon_{t-i}+c+\epsilon_t</span><script type="math/tex">y_t=\sum^{q}_{i=1}b_i·\epsilon_{t-i}+c+\epsilon_t$

上述模型也被称为MA（q）。参数c是时间序列的平均值。 $b_1…… b_q$的值是需要从数据中学习的系数。移动平均模型与自回归模型完全不同，因为它将当前值与系列的平均值以及之前偏离预测的历史相关，而不是实际值。这里$ε_t$的值被假设为白噪声误差项，彼此不相关。这里的一个问题是误差项$ε_t$不是观测数据的一部分，但也需要从预测模型中导出。这个圆形性意味着当纯粹用系数和观测值yi表示时，方程组是固有的非线性的。通常，使用迭代非线性拟合程序而不是线性最小二乘法来确定移动平均模型的解。很少有人能够仅用冲击来预测系列值，而不是自相关。自相关在时间序列分析中非常重要，因为时间序列数据具有固有的时间连续性。同时，冲击的历史确实会影响该系列未来的价值。因此，自回归和移动平均模型都不能完全捕获单独预测所需的所有相关性。

通过结合自回归模型和移动平均模型的功能，可以获得更一般的模型。 这个想法是在预测时间序列值时学习自相关和冲击的适当影响。 这两个模型可以结合p自回归项和q移动平均项。 这个模型被称为ARMA模型。 在这种情况下，不同术语之间的关系可以表示如下：$<span><span class="MathJax_Preview">y_t=\sum^{p}_{i=1}a_i·y_{t-i}+\sum^{q}_{i=1}b_i·\epsilon_{t-i}+c+\epsilon_t</span><script type="math/tex">y_t=\sum^{p}_{i=1}a_i·y_{t-i}+\sum^{q}_{i=1}b_i·\epsilon_{t-i}+c+\epsilon_t$

上述模型是ARMA（p，q）模型。 这里关键的问题是在这些模型中选择参数p和q。 如果p和q的值设置得太小，那么模型将不能很好地拟合数据。 另一方面，如果p和q的值设置得太大，那么模型可能会过度拟合数据。 一般来说，建议选择尽可能小的p和q的值，以便模型很好地拟合数据。 和前面的情况一样，自回归移动平均模型最适用于平稳数据。

很多情况下，非平稳数据可以通过将差分与自回归移动平均模型相结合来解决。 这导致了自回归整合移动平均模型（ARIMA）。 原则上，可以使用任何顺序的差异，尽管一阶和二阶差异是最常用的。 考虑使用一阶差分值$y'_t$的情况。 那么，ARIMA模型可以表示如下：$<span><span class="MathJax_Preview">y'_t=\sum^{p}_{i=1}a_i·y'_{t-i}+\sum^{q}_{i=1}b_i·\epsilon_{t-i}+c+\epsilon_t</span><script type="math/tex">y'_t=\sum^{p}_{i=1}a_i·y'_{t-i}+\sum^{q}_{i=1}b_i·\epsilon_{t-i}+c+\epsilon_t$

因此，该模型与ARMA（p，q）模型几乎相同，只是模型内使用了差分。 如果差分的阶数是d，那么这个模型被称为ARIMA（p，d，q）模型。

14.3.3 带隐藏变量的多元预测

所有上述模型均为单一时间序列而设计。 在实践中，一个给定的应用程序可能有数千个时间序列，并且不同序列和不同时间都可能存在显着相关性。 因此，要求模型能够将自回归相关与交叉序列相关结合起来进行预测。

虽然有多种不同的多元预测方法，但隐藏变量通常用于实现此目标。这是因为隐藏变量方法能够清晰地将交叉序列相关与建模过程中的自回归相关分开。隐藏变量建模的想法是将大量互相关时间序列转换为少量不相关的时间序列。通常，主成分分析（PCA）用于该转换。由于这些不同的序列彼此不相关，因此可以使用AR，ARMA或ARIMA模型中的任何一个模型来预测隐藏值。然后，将预测值映射回其原始表示。这为使用少量隐藏变量预测的所有不同序列提供了预测值。在进一步阅读讨论PCA之前建议读者重读2.4.3.1章节。

假设有d个同步时间序列的长度为n。在第i个时间戳接收到的d个不同的时间序列值由$\overline{Y_i} =（y^1_i … y^d_i）$表示。目标是从$\overline{Y_1}…\overline{Y_n}$预测$\overline{Y_{n+1}}$。多变量预测方法的步骤如下：

1. 构造多维时间序列的d×d协方差矩阵。 令d×d协方差矩阵由C表示。C的（i，j）项是第i和第j序列之间的协方差。 该步骤与多维数据的情况相同，并且在此阶段不使用$Y_i$的不同值的时间顺序。 因此，协方差矩阵仅捕获关于系列间相关性的信息，而不是跨越时间的相关性。 请注意协方差矩阵也可以在流式传输设置中进行递增维护，使用第20.3.1.4节讨论的方法。

2. .确定协方差矩阵C的特征向量如下：$<span><span class="MathJax_Preview">C=P\wedge P^T\tag{14.17}</span><script type="math/tex">C=P\wedge P^T\tag{14.17}$

这里，P是d×d矩阵，其d列包含正交特征向量。 矩阵Λ是包含特征值的对角矩阵。 设Ptruncated为一个d×p矩阵，通过选择具有最大特征值的P的p«d列获得。 通常，p的值比d小得多。 这代表了变异性最大的隐藏系列的基础。

1. 创建一个带有p个隐藏时间序列变量的新多变量时间序列。 第i个时间戳处的每个d维时间序列数据点Yi用p维隐藏序列数据点表示。 这是通过使用前一步中导出的p个基本向量来实现的。 因此，p维隐藏值$\overline{Z_i} =（z^1_i … z^p_i)$推导如下：$<span><span class="MathJax_Preview">\overline{Z_i}=\overline{Y_i}P_{truncated}\tag{14.18}</span><script type="math/tex">\overline{Z_i}=\overline{Y_i}P_{truncated}\tag{14.18}$

图14.5：2013年9月5日至2014年9月4日期间四种贵金属交易所交易基金（ETF）的标准化价格以及相应的不相关隐变量

Zi的值表示第i个时间戳处的隐藏序列变量的p个不同值。因此，这一步创建了彼此大致相互独立的p个不同的隐藏变量时间序列。请注意，YiP中的其他（d - p）隐变量由于其特征值（方差）小而随时间大致保持不变。这些（d-p）近似恒定值的方法也被记录下来。绝大多数具有常数值的隐藏变量不需要预测建模。在图14.5a中，四个与贵金属有关的交易所交易基金（ETF）的股票价格为1年。每个系列都被倍增地缩放到从1开始的相对值。最上面的两个隐藏变量序列如图14.5b所示。请注意，这些派生系列是不相关的，第一个隐含变量比第二个隐含变量高得多。其余两个隐藏变量未显示，因为它们的方差甚至更小。实际上，图14.5a中的四个相关系列中的每一个都可近似地表示为图14.5b中两个隐变量系列的不同线性组合。因此，预测隐藏变量会得出原始序列的近似预测。

1. 对于每个不相关和高方差序列，使用任何单变量预测模型来预测第（n + 1）时间戳处的p个隐藏变量的值。 一个单变量法可以有效地使用，因为不同的隐变量是不相关的设计。 这提供了一组值$\overline{Z_{n+1}} =（z^1_{n+1} … z^p_{n+1}）$。 附加将剩余的（d-p）隐藏序列的值近似恒定为$\overline{Z_{n+1}}$的方法来创建新的d维隐藏变量向量$\overline{W_{n+1}}$。
2. 通过使用逆变换将预测的隐变量$\overline{W_{n+1}}$变换回原始的d维表示。 这提供了预测值原始序列：$<span><span class="MathJax_Preview">\overline{Y_{n+1}}=\overline{W_{n+1}}P^T\tag{14.19}</span><script type="math/tex">\overline{Y_{n+1}}=\overline{W_{n+1}}P^T\tag{14.19}$

上述说明是SPIRIT框架的简化版本。 它减少了预测的计算量，因为简单的单变量建模仅在少量的独立时间序列上执行。 另一方面，它确实导致了计算特征向量的开销。 隐变序列是许多不同系列的线性组合。 因此，单个序列的噪声影响往往会在隐藏变量内被平滑，这增加了预测过程的稳健性。

图14.6：单个时间序列中的重复图案

14.4 时间序列图案

图案是时间序列中经常出现的模式或形状。图案的发现可以通过多种方式进行制定，具体取决于应用程序特定的要求。这些不同的公式在输入数据和发现的图案的性质方面有所不同。 这些变化如下：

1. 单个系列与多个系列的数据库：第一种情况，单一系列可用，以及系列中特定窗口中经常出现的形状。例如，在图14.6中，突出显示的形状在同一系列中出现三次，因此其计数为3.不同的公式是其中我们有$N$个不同系列的形式，并且形状至少出现一次特定系列被赋予正好为1的分数。因此，频率是根据模式出现的系列数来计算的。 第二个公式更接近离散数据中的顺序模式挖掘。 不同的应用可能需要不同的主题发现定义。
2. 连续与非连续图案：连续图案要求在时间序列的连续窗口上发现图形。不连续的图案可能允许图案的不同元素之间存在差距。时间序列分析的大部分工作都假定图案是在连续的窗口上定义的。不连续的图案在离散序列分析中更常见。尽管如此，不连续的图案可能在某些应用中具有实用性。
3. 多粒度图案：许多公式都可以找到图案的窗口大小。但是，实际上，频繁的图案可能发生在不同尺寸的窗户上。这些图案在许多特定应用场景中非常有用。 例如，在图14.11a的金融市场系列中，一个重要的主题是由一天中的“闪现崩溃”事件引起的。另一方面，在图14.11b中，（衰退）趋势发生在几个月。 在第二种情况下，可能需要消除局部变化以发现图案。因此，需要不同的技术来发现不同类型的图案.

图案何时属于时间序列？ 两种方法通常由不同的应用程序使用。

1. 基于距离的支持：当段与主题之间的距离小于特定阈值时，序列的特定段称为支持主题。

2. 转换到顺序模式挖掘：可以使用各种离散化将时间序列转换为离散序列。 转换后，可以将图案定义为序列的离散子序列。

后一种方法有助于从顺序模式挖掘中获得更丰富的算法。此外，用于离散化的方法可以变化，以发现不同种类的图案。它还允许发现不连续的模式，因为序模式挖掘算法默认情况下不会假设连续性。本节将讨论这两种方法。此外，将引入周期性模式的概念。

14.4.1 基于距离的图案

基于距离的图案总是在时间序列的连续片段上定义。首先，需要定义时间序列中主题和连续片段之间近似距离匹配的概念。

$\bf定义14.4.1(近似距离匹配)$实际值序列（或图案）$S=s_1…s_w$与时间序列（$y_1，…，y_n$）中的长度$w$的连续子序列近似匹配（$w\leq n$) ,如果（$s_1，…，s_\omega$）和($y_i，…，y_i|_{w-1}$)之间的距离至多为$\epsilon$，则从位置i开始。

可以使用各种各样的距离函数，并且欧几里得距离函数是常见的选择。上述定义假定匹配的两个子序列具有相同的长度。这是一个保守的假设，允许使用距离函数，如欧几里德函数。但是，如果使用其他距离函数（如动态时间翘曲），则可能不需要匹配的图案具有相同的长度。单个长序列中的主题出现次数用于量化主题的频率。除了系列本身之外，窗口长度$w$和近似阈值$\epsilon$是该算法的两个主要输入。 　　 $\bf定义14.4.2(Motif\ Count)$时间序列窗口$S=s_1…s_w$与时间序列($y_1，…，y_n$)在阈值级别$\epsilon$的匹配数目等于长度为$w$的窗口数目在($y_1…y_n$)中，对应的子序列之间的距离至多为$\epsilon$。

目标是发现用户定义的参数k的前$k$个图案。此外，为确保发现的$k$个图案彼此之间存在很大差异，必须施加约束条件;在$top-k$图案中发现的任何图案对之间的距离必须至少为2$\epsilon$。在下文中，将描述最频繁发生的单个基序的发现。对顶部$k$个图案的推广是相对简单的。整体方法[356]使用嵌套循环算法来发现最常见的主题。 该方法在图14.7中描述。

图14.7：确定最常见的主题

该方法从时间序列中提取所有长度为$w$的候选图案，并计算到所有长度为$\omega$的窗口的距离。计算匹配发生的窗口数量。注意排除计数中的微小匹配。平凡匹配被定义为匹配大致相同（重叠）窗口的那些匹配。例如，当$i = j$的情况是平凡的匹配。此外，在$i<j$的情况下，如果从$i$开始的窗口与从$i+1，i+2...j$开始的所有窗口匹配，那么在$j$处的匹配也是微不足道的。在$i>j$的情况下，如果从i开始的窗口与从$i-1，i-2...j$开始的所有窗口匹配，则j中的匹配是微不足道的。因此，在计数中明确检查了这种情况。在算法的过程中跟踪最佳候选人，并在终止时报告。如图14.7所示，该方法需要一个嵌套循环，每个循环中的迭代次数几乎等于系列$n$的大小。因此，该方法需要$O(n^2)$距离计算。原则上，任何时间序列距离函数（如$DTW$）都可用于计算，但它通常更昂贵。
大部分时间用于距离计算。在很多情况下，可以使用距离下界的快速计算来加速该方法。 如果计算出的一对窗口之间的下界大于$\epsilon$，那么该对保证与添加候选图元计数无关。因此，距离计算不需要明确执行。分段聚合近似$（PAA）$可用于加速距离计算。考虑在长度为m的窗口上执行$PAA$的场景。由此产生的系列已被压缩了$m$倍，因此距离计算速度更快。如果系列$X^\prime$是$X =(x_1 ...x_n)$的$PAA$，$Y^\prime$是$Y=(y_1...y_n)$的PAA，则可以表明：
$<span><span class="MathJax_Preview">Dist(X,Y)\geq\sqrt{m}\cdot Dist(X^\prime,Y^\prime)\tag{14.20}</span><script type="math/tex">Dist(X,Y)\geq\sqrt{m}\cdot Dist(X^\prime,Y^\prime)\tag{14.20}$
这个结果的证明如下。考虑时间序列$Z=X-Y$。在$m$个数据点的任意窗口中，该窗口中$Z$的元素的第二个时刻至少等于相同元素的平均值的平方的$m$倍。其他更快的近似方法也存在，例如使用$SAX$表示法。使用$SAX$表示法时，可以为所有离散值对保留一个预先计算的距离表，于较低的边界，则需要进行简单的表查找。此外，一些其他时间序列距离函数（如动态时间扭曲）也可以从下面限定。书目注释包含指向这些边界的指针。基本方法的许多变体都可以通过添加另一层嵌套来解决，这个嵌套层解决了窗口大小的变化。

14.4.2 向顺序模式挖掘转化

在时间序列中发现图案的一种特别方便的方法是将问题转换为顺序模式挖掘问题。 这种情况下的设置有些不同，其中有$N$系列的数据库可用，并且需要在特定的最低支持级别确定所有频繁模式。由于主题（模式）挖掘更加自然地在离散情况下定义，因此这种转换有助于使用各种可用于离散情景的工具。此外，这种方法还可以在时间序列中发现不连续的模式。这是因为顺序模式挖掘中的子序列允许不连续。 第一步是将时间序列转换为离散序列，通过离散化时间戳的行为特征值和时间戳分类值。可以将离散化与分箱结合以创建强健的序列表示。应该指出的是，根据应用特定的目标，将时间序列转换为离散序列有许多不同的方法。例如，连续时间戳之间行为属性值的差异的离散化等同于使用最详细粒度级别的离散小波系数。低阶小波系数将提供对时间序列中较大段的趋势的深入了解。因此，甚至可以通过使用不同次序的离散化小波系数来执行多分辨率基序分析，并为每个次序的小波创建单独的基本序列。一般来说，将时间序列转换为离散序列的方法将严重影响所发现图案的性质。
对于所有这些方法，离散化的最终结果是数据库中$N$个时间序列中的每一个的一系列离散值。在构建了这个新的序列数据库之后，可以应用任何顺序模式挖掘算法。GSP算法会在15.2节介绍。重要的是要注意15章中的算法允许序列的连续元素之间的间隔。然而，通过在顺序模式挖掘算法中增加最大间隙约束，可以将这些算法简单推广到邻近的情况。有约束的顺序模式挖掘算法简要地在第15.2.2章讨论。应该指出的是，15.2.2章中讨论了对应于不同种类图案的不同约束。由于可以通过改变离散化方法或顺序模式挖掘方法发现各种图案的广泛变化，因此这种方法非常灵活，并且可以针对许多不同的应用场景量身定制。

14.4.3 周期性模式

正如$DWT$用于发现时间序列中的局部模式一样，$DFT$通常用于发现周期性模式。 回忆14.2.4.2节时间序列$x_0...x_{n-1}$的第$r$个分量可以用$n$个复数傅立叶系数$X_0 ... X_{n-1}$表示如下：
$<span><span class="MathJax_Preview">x_r=\frac{1}{n}(\sum_{k=0}^{n-1}X_k\cdot\cos(r\omega k))　\forall r\in\lbrace0,…n-1\rbrace</span><script type="math/tex">x_r=\frac{1}{n}(\sum_{k=0}^{n-1}X_k\cdot\cos(r\omega k))　\forall r\in\lbrace0,…n-1\rbrace$
这里$\omega$设置为$\frac{2π}{n}$弧度。由于这个求和的虚数部分对于$x_r$的实际值总是0，所以让我们通过假设$X_k = a_k + ib_k$来扩展实部：
$<span><span class="MathJax_Preview">x_r=\frac{1}{n}(\sum_{k=0}^{n-1}(a_k+ib_k)\cdot\cos(r\omega k)+(a_k+ib_k)\cdot\sin(r\omega k))　\forall r\in\lbrace0,…n-1\rbrace</span><script type="math/tex">x_r=\frac{1}{n}(\sum_{k=0}^{n-1}(a_k+ib_k)\cdot\cos(r\omega k)+(a_k+ib_k)\cdot\sin(r\omega k))　\forall r\in\lbrace0,…n-1\rbrace$
通过忽略虚部，我们得到： $$ \begin{align*} x_r=&\frac{1}{n}(\sum_{k=0}^{n-1}a_k\cdot\cos(r\omega k)-b_k\cdot\sin(r\omega k))　\forall r\in\lbrace0,…n-1\rbrace\ =&\frac{1}{n}\sqrt{a_k^2+b_k2}\sum_{k=0}^{n-1}\cos(r\omega k+\theta_k)　\forall r\in\lbrace0,…n-1\rbrace \end{align*} $$

这里，我们有$\theta_k=cos^{-1}(\frac{a_k}{\sqrt{a_k^2+b_k^2}})$.所有$k\geq1$的项都是周期性的。换句话说，时间序列可以被分解成$n-1$个周期性正弦分量，从而第$k$个分量具有$\frac{n}{k}$的周期和$\sqrt{a_k^2+b_k^2}$的幅度。因此，如果周期性分量相对于其他分量具有非常高的幅度，则整个序列将受其周期性行为支配。为了检测这些分量，确定所有n个振幅的平均值和标准偏差。任何振幅$\sqrt{a_k^2+b_k^2}$，至少比平均值大$\delta$个标准偏差。这样的分量具有周期性$\frac{n}{k}$，并且由于其高振幅，其周期性将在该序列中显而易见。请注意，较小的傅立叶系数在维数降低的情况下也会被丢弃。然而，当更积极地选择阈值$\delta$时（例如非常大的正值如3），只剩下2或3个系数，并且残差序列的周期性变得明显。此外，只有$k\in(\beta,\frac{n}{\alpha})$的值与发现至少具有$\alpha\geq2$的周期并且在该序列中出现至少$\beta\geq2$次的模式相关。书目注释包含发现部分周期性模式的方法的指针。

14.5时间序列聚类

时间序列数据聚类可以通过两种不同的方式进行定义，具体取决于具体应用情况。

1. 在第一种方法中，实时聚类是按时间序列同时进行的。例如，在金融市场应用中，可能希望将该系列分成随时间进化的群组。在这种情况下，不同时间序列中的值以近似同步的方式相互比较。通常，分析是在近期历史的一个小窗口上进行的。时间序列根据窗口中的序列之间的相关性聚类为组。此外，聚类以在线方式进行，不同系列可能会跨越不同的聚类。例如，$IBM$的股票报价可能会在某一天与微软一起移动，但不是下一个。
2. 在第二种方法中，可以使用时间序列数据库。这些不同的时间序列可能在同一时刻收集或不收集。根据它们的形状，将这些系列聚类是理想的。例如，在包含心电图$（ECG）$时间序列的应用程序中，不同患者可能在不同时刻向数据库提供时间序列。形状匹配通常需要使用第3章的3.4.1节中讨论的时间序列相似性函数。因此，取决于相似性函数的性质，上下文属性和行为属性都可以被扭曲或缩放。 在这种情况下，不同的时间序列甚至可能不等长。

在本节中，将详细讨论不同种类的聚类方法。当基于形状的聚类应用于多元时间序列时，问题变得更加困难。一种解决方案是将相似度函数推广到多元情况。时间序列相似性函数可以推广到多变量情形，尽管对这个主题的完整讨论超出了本书的范围。相关指针可以在书目注释中找到。

对于基于形状的聚类，双变量和三变量序列的特殊情况也可以通过使用轨迹聚类来解决。在第１章的1.3.2.3节中找到了一个多元系列如何转换为轨迹数据的例子。轨迹聚类的方法在16章的16.3.4节讨论。

14.5.1 凝聚系列的在线聚类

在线聚类凝聚系列的问题是基于确定整个系列的相关性，以在线方式。这对于金融市场等许多实时应用程序非常有用，因为它提供了对系列总体趋势的理解。 在这些情况下，时间序列根据长度为$p$的窗口中的相关性进行聚类。由于使用相关性来定义相似性，这种方法被称为时间序列相关性聚类。第七章讨论了多维数据的$ORCLUS$相关聚类算法。多维数据的相关聚类算法。类似的原则适用于时间序列数据，除了相关性是在多元时间序列的不同组成部分（行为维度）之间测量的。相同的时间窗口用于不同的时间序列以计算相关性。因此，对不同流的分析在时间上是同步的。
一种自然的方法是使用基于回归的相似度函数来计算不同流之间的相似度。这两个流不必是正相关的。相反，这些流可能是高度负相关的。这里的关键问题是不同时间序列相对于彼此的可预测性。例如，在图14.8中，系列$A$和$B$非常相似，因为它们彼此完全负相关。这是因为这两个系列可以互相预测。另一方面，$C$系列是非常不同的，并且对于任何一个流都具有较低的可预测性，并且在希望最大化集群代表的预测能力的应用中是有用的。一个例子是传感器选择，其中需要选择传感器的子集，其最大化预测所有其他传感器的值的能力。因为预测是实时时间序列分析中最基本的问题之一，所以在这种情况下使用基于回归的相似性是很自然的。这与基于形状的分析有所不同，其中使用了更多传统的时间序列相似性函数，如$DTW$。直接使用回归分析进行实时时间序列聚类的方法称为在线时间序列相关聚类。

图14.8：时间序列相关聚类

为了便于讨论，我们将$d$时间序列看作是具有$d$行为属性的单个多元系列。长度$t$的多元时间序列由$\overline{Y_1}...\overline{Y_t}$表示。第$t$个$tick$中每个$d$流的值$\overline{Y_t}$是$（y^1_t...y^d_t）$。因此，我们的目标始终是维护$d$系列的一个分区，以便将高度相关的组件分配给相同的分区。基于代表性的方法用于聚类。基本思想是实时从$d$系列增量维护一组k代表性时间序列。由$J$表示的这个代表性集合类似于$k-medoids$算法的代表性集合。代表确定之后，所有的时间序列流都可以使用时间序列相似度函数分配给其中一位代表。每个系列都可以分配给最近的代表。这个相似性函数将在后面更详细地讨论。　　 一种自然的方法是逐步维护代表，并在必要时向流J添加或删除流。通过将$d$时间序列分配给最近的代表来隐式定义聚类。因此，当新的时间序列数据点到达时，需要更新当前代表$J$的集合。流在当前的集群代表和非代表之间迭代交换，以基于最小化错误来优化质量标准。代表性流$i$和非代表性流$j$之间的相似性是从流i预测流j的回归误差。这个想法是，真正的集群代表可以用来准确预测其他流。 为了预测来自流$i$的流$j$，除了使用流i的元素来预测流$j$而不是其自己的元素之外，使用与自回归模型相似的模型。因此，回归模型如下： $<span><span class="MathJax_Preview">y_t^j=\sum_{r=1}^{p}a_r\cdot y_{t-r}^i+c+\epsilon_t</span><script type="math/tex">y_t^j=\sum_{r=1}^{p}a_r\cdot y_{t-r}^i+c+\epsilon_t$
这与$AR（p）$模型类似，不同之处在于流i的元素被用于预测流$j$的元素。和$AR（p）$模型一样，最小二乘回归可以用来学习$p$系数。此外，训练数据被限制在一个大小为$\omega>p$的窗口，以允许流的演变。白噪声误差项的平均值或者尺寸$\omega>p$窗口上的$R^2$统计量可以用作两个流之间的距离（相似性）。请注意，回归系数也可以增量维护，因为它们在前一个时间戳处已经是已知的，并且只需要添加单个数据点即可更新模型。大多数用于最小二乘回归的迭代优化方法（如梯度下降）在以近似最优解开始时收敛非常快。

图14.9：动态维护集群代表

这种基于回归的相似性函数是不对称的，因为从流$i$预测流$j$的误差与从流$j$预测流$i$的误差不同。代表性集合$J$也可用于通过将每个流分配给代表来创建流的聚类$C$，以最好地预测它。因此，在每个步骤中，在更新模型之后，可以递增地报告代表组$J$和组$C$。在线流聚类方法的伪代码如图14.9所示。这种方法对于金融市场的趋势分析非常有用，在这些市场中需要从庞大的股票领域中追踪一组代表性的股票。另一个相关应用是传感器选择，其中需要确定代表性传感器的子集以降低传感器网络的运营成本。本节中的描述基于简化基于成本的动态传感器选择算法[50]。

14.5.2 基于形状的聚类

第二种类型的聚类来自基于形状的聚类。在这种情况下，不同时间序列可能无法及时同步。时间序列是根据整个系列形状的相似性聚类的。第一步是设计一个基于形状的相似度函数。这种情况下的一个主要挑战是，不同系列可能会被缩放，翻译或拉伸不同。这个问题在第3章的3.4.1节中讨论。图3.7的图示被复制到图14.10中。该图显示了不同的假设股票代号。在这些情况下，三种股票表现出相似的模式，但具有不同的比例和随机变化。此外，在某些情况下，时间维度也可能会变形。例如，在图14.10中，股票A的整个值集合被拉伸了，因为分析师没有提供时间粒度信息。这被称为时间扭曲。幸运的是，在第3章的3.4.1节讨论的动态时间扭曲$（DTW）$相似性函数，可以解决这些问题。因此，有效相似函数的设计是时间序列聚类中最关键的步骤之一。

图14.10：缩放，平移和噪声对聚类的影响（重新审视图3.7）

许多现有的方法可以适应基于形状的时间序列聚类，并使用不同的时间序列相似度函数。$ k-medoids$和基于图的方法可以用于几乎任何相似性函数。也可以使用诸如$k-means$的方法，尽管以更有限的方式。这是因为不同的时间序列需要具有相同的长度才能使群集的均值有意义地被定义。

14.5.2.1 $k-Means$

多维数据的k均值方法在第6章的6.3.1节中讨论。这种方法可以通过改变相似函数和计算时间序列的方法改写时间序列数据。相似函数的计算可以从第3章的3.4.1节得到改进。相似性函数的精确选择可能取决于手头的应用，尽管$k-means$方法针对欧几里德距离函数进行了优化。这是因为$k-means$方法可以被看作是一个优化问题的迭代解决方案，其中目标函数是用欧几里得距离构造的。这方面在第6章中有更详细的讨论。
时间序列上的欧几里得距离函数的定义方式与多维数据相同。不同时间序列的方法也以类似于多维数据的方式定义。$k-means$方法最适用于时间点之间具有一一对应关系的相同长度的数据库。因此，每个时间点的质心可以用对应关系来定义。 考虑到时间序列数据点之间的一一对应关系，时间扭曲通常很难以有意义的方式用于k均值算法。对于更通用的距离函数（如$DTW$），时间序列聚类的其他方法更合适。

14.5.2.2 $k-Medoids$

具有$k-Means$的主要结果表明不能合并任意相似（或距离）函数。在这种情况下，$k-medoids$方法可以更有效地使用，因为它不会对不同时间序列的相对长度做任何假设。该方法的细节在第6章的6.3.4节进行描述，与本节提供的描述的主要区别在于选择相似性函数。可以使用在第3章的3.4.1节描述的任何相似性函数，在第7章的7.3.1节中讨论$CLARANS$方法也可以推广到这种情况。

14.5.2.3 分层方法

在第6章6.4节讨论的分层方法也可以推广到任何数据类型，因为它们可以处理不同数据对象之间的成对距离。在这些方法中，主要的挑战是需要所有时间序列对之间的距离计算。许多时间序列距离和相似度函数需要昂贵的动态编程方法。 这是使用分层方法的主要缺点。尽管如此，在时间序列总数很少的情况下，仍然可以有效地使用这种方法。

14.5.2.4 基于图形的方法

基于图的方法为时间序列数据聚类提供了转换方法。这个想法是将时间序列数据集转换为一个单一的大图，社区检测算法可以应用于该图上。正如在第2章的2.2.2.9节讨论的，一旦相似度函数被定义，任何数据类型都可以转换为相似度图。该图中的每个节点对应一个数据对象。每个节点连接到它的$k$个最近邻居，并且边的权重等于对应的一对对象之间的相似度。一旦定义了相似度图，任何在第19章19.3节中讨论的图聚类算法都可以用来确定节点簇。19.3.4节描述的的谱方法是最常用的。然后可以通过使用节点与时间序列数据对象之间的对应关系将节点的群集（社区）映射回时间群集。

14.6 时间序列异常值检测

就时间序列聚类而言，时间序列中异常值检测的问题可以用两种不同的方式来定义。

1. 点异常值：点异常值是给定时间戳的时间序列值的突然变化。这个问题与预测密切相关，因为异常值被定义为与预期（或预测）值有显着的偏差。这些异常值被称为上下文异常值，因为它们在其近期历史的背景下是异常值。
2. 异常形状：在这种情况下，连续窗口中连续的数据点模式可能被定义为异常。例如，在$ECG$系列中，当一起考虑时，不规则心脏跳动可被认为是异常，但该系列中的个别点可被认为是异常。这些异常值被称为集合异常值，因为它们是通过组合来自多个数据项的模式来定义的。

图14.11：标准普尔500在闪电当天（2010年5月6日）（a）和2001年（b）

为了说明这两种异常之间的区别，我们将使用来自金融市场的一个例子。图14.11a，b所示的两种情况显示了标普500在不同时间段的走势。图14.11a展示了2010年5月16日标普500指数的走势。这是股票市场崩溃的日期。这是一个非常不寻常的事件，从跌落时的点偏移角度以及跌落形状的角度来看。图14.11b说明了一种不同的情况。在这里，说明了2001年标普500指数的变化。由于股市疲软，以及9/11恐怖袭击事件，今年有两次重大的下跌。虽然特定的下降时间戳可能被认为是一些基于正态分布的背景分析关于特定的窗口，但这些时间序列的实际形状并不罕见，因为它经常在熊市（市场疲软时期）遇到。因此，这两种异常值需要专门的分析方法。应该指出的是，两种异常值之间的类似区别可以在许多上下文数据类型中定义，例如离散序列数据。对于离散序列数据的情况，这些分别被称为点离群点和组合离群点。离散序列数据中的组合异常值类似于在连续时间序列数据中形成异常值。这一点在第15章中有更详细的讨论。

14.6.1 点异常值

点异常值与时间序列数据预测问题密切相关。如果数据点与其预期（或预测）值显着偏离，则认为该数据点是异常值。这种异常值对应于基础数据中的无监督事件。事件检测通常被认为是实时执行时间异常检测的同义词。
可以为单变量或多变量数据定义点异常值。单变量数据和多变量数据的情况几乎相同。因此，将讨论更一般的多变量数据的情况。如前面部分所述，假设要检测异常值的多变量序列用$\overline{Y_1} ... \overline{Y_n}$表示。 整体方法包括四个步骤：

1. 确定每个时间戳的时间序列的预测值。根据基本系列的性质，可以使用在第14.3节中讨论任何单变量或多变量方法。设第$r$个时间戳$t_r$处的预测值由$W_r$表示。
2. 计算（可能多变量）时间序列的偏差$\Delta_1...\Delta_r....$换句话说，对于第$r$时间戳$t_r$，偏差计算如下： $<span><span class="MathJax_Preview">\overline{\Delta_r}=\overline{W_r}-\overline{Y_r}\tag{14.21}</span><script type="math/tex">\overline{\Delta_r}=\overline{W_r}-\overline{Y_r}\tag{14.21}$
3. 将$\overline{\Delta_r}$的不同分量表示为$（\delta_r^1...\delta_r^d）$。这些可以分解成d个不同的沿每个维度的单变量系列偏差。第$i$个系列的值由$\delta_1^i ...\delta_n^i$表示。假设第$i$个系列偏差的平均值和标准偏差用$\mu_i$和$\sigma_i$表示。
4. 计算归一化偏差$\delta z^i_r$如下： $<span><span class="MathJax_Preview">\delta z^i_r=\frac{\delta^i_r-\mu_i}{\sigma_i}\tag{14.22}</span><script type="math/tex">\delta z^i_r=\frac{\delta^i_r-\mu_i}{\sigma_i}\tag{14.22}$ 产生的偏差基本上等于正态分布的$Z$值。这种方法为多元时间序列的每个$d$维提供连续的异常值评分。可以通过对这些分数使用阈值来检测异常时刻。由于Z值解释，绝对阈值3通常被认为是足够的。

在某些情况下，需要创建一个统一的偏差分数警报级别，而不是为每个系列创建单独的警报级别。这个问题与第9章的9.4节讨论的异常值集合分析密切相关。时间戳$r$处的统一警报级别$U_r$可以报告为多变量系列不同组件中最大的得分： $<span><span class="MathJax_Preview">U_r=max_{i\in1…d}\delta z^i_r\tag{14.23}</span><script type="math/tex">U_r=max_{i\in1…d}\delta z^i_r\tag{14.23}$ 不同检测器的得分可以通过其他方式进行组合，例如通过使用不同系列的平均或平方集合。

14.6.2 异常形状

$Hotsax$方法是寻找基于形状的异常值的最早方法之一。在这种方法中，异常值被定义在时间序列的窗口上。使用$k$最近邻方法来确定离群值分数。具体而言，数据点与其第$k$个最近邻居的欧几里得距离用于定义离群值分数。
异常值分析在长度为$W$的窗口上执行。因此，该方法从时间序列的数据点报告异常形状的窗口。第一步是使用滑动窗口方法从时间序列中提取长度为$W$的所有窗口。 然后对这些新创建的数据对象执行分析。对于每个提取的窗口，计算与其他非重叠窗口的欧几里得距离。具有最高的$k$最近邻距离值的窗口被定为异常值。使用不重叠窗口的原因是为了最小化平凡匹配对重叠窗口的影响。尽管蛮力$k$最近邻居方法可以确定异常值，但复杂度将随着数据点数量的平方而缩放。 因此，修剪方法用于提高效率。虽然这种方法可以优化效率，但它不会影响该方法报告的最终结果。
修改在最近邻方法中更有效的异常值检测的一般原则在第8章的8.5.1.2节中介绍。这个算法在外部循环中迭代地检查候选子序列。对于每个这样的候选子序列，在内部循环中逐步计算$k$个最近邻居，其中距离计算到其他子序列。每个候选子序列或者被包括在外循环迭代结束时的当前最佳$n$个异常值估计中，或者通过早期放弃内循环而被丢弃而不计算$k$最近邻的精确值。当候选子序列的当前近似的$k$最近邻距离小于到目前为止发现的第$n$个最佳异常值的得分时，可以提前终止该内循环。显然，这样的子序列不可能是异常值。为了获得最佳的修剪结果，需要对子序列进行试探性排序，以便在外部循环中检查的最早的候选子序列最有可能是异常值。此外，当真正的异常值被发现时，修剪性能也是最有效的。它仍然需要解释如何实现良好修剪所需的启发性排序。 一种可以测量潜在子序列的聚类行为的方法促进了修剪。聚类与异常值分析具有众所周知的互补关系。因此，首先在外环中检查那些包含非常少（或一个）成员的聚类的成员的子序列是有用的。$SAX$表示用于创建子序列到群集的简单映射.映射到相同SAX字的子序列被假定属于单个集群。$SAX$的分段聚合近似在长度$w <W$的窗口上执行。因此，$SAX$字的长度是$W/w$，如果$W/w$很小，$SAX$字的不同可能性的数量很小。这些不同的单词对应于不同的集群。多个子序列映射到同一个群集。因此，候选的排序是基于同一集群中数据对象的数量。首先检查具有较少对象的簇中的候选者，因为它们更可能是异常值。 这种基于群集的排序用于设计异常值分析的有效修剪机制。在外部循环中逐个检查簇中的候选者。在内部循环中计算这些候选者的$k$最近邻居距离。对于每个候选子序列，映射到与候选词相同单词的那些子序列可能被首先考虑用于计算内部循环中的最近邻距离。这为最近的相邻距离提供了快速和紧密的上限。随着这些距离逐个计算，在内部循环的进程上计算最接近的高度上的更紧密和更紧密的上限。当最近的相邻距离的上限保证比迄今发现的第$n$个最佳离群距离更小（或更相似）时，可以修剪候选者。因此，对于任何给定的候选序列，没有必要通过比较所有子序列来确定它的确切最近邻。相反，在计算最近的相邻距离期间，通常可以提前终止内部回路。这构成了$Hotsax$修剪方法的核心，在原理上类似于第8章8.5.1.2中讨论的嵌套循环修剪方法。关于多维异常值分析。主要区别在于如何使用SAX表示来对外部循环中的候选者进行排序以及对内部循环中的距离计算进行排序。

14.7时间序列分类

时间序列分类可以通过几种方式进行定义，具体取决于底层类别标签与单个时间戳或整个系列的关联。

1. 点标签：在这种情况下，类标签与各个时间戳相关联。在大多数情况下，感兴趣的类别在性质上很少见，并且与该时间戳处的不寻常活动相对应。这个问题也被称为事件检测。这个版本的事件检测问题可以与14.6节中讨论的无监督异常值检测问题区分开来。因为它是由标签监督的。
2. 全系列标签：在这种情况下，类标签与整个系列相关联。因此，该系列需要根据其内部的形状进行分类。

这两个问题都将在本章中讨论。

14.7.1 监督事件检测

监督式事件检测的问题是类标签与时间戳相关联而不是整个系列。在大多数情况下，一个或多个类别标签很少见，其余标签对应于“正常”期间。虽然原则上可以通过均衡分配标签来定义问题，但在特定于应用程序的设置中很少出现这种情况。 因此，本小节中的讨论将只关注不平衡的标签分发场景。
　　这些罕见的类标签对应于基础数据中的事件。例如，考虑使用传感器跟踪机器性能的情景。在某些情况下，例如机器故障等罕见事件可能会导致传感器读数异常。这种不寻常的事件需要及时跟踪。因此，这个问题类似于点异常检测，除了它是以监督的方式完成的。

图14.12：由于管道破裂（a，b）以及压力传感器故障（c，d）引起的温度和压力传感器行为

在许多特定应用情况下，时间序列数据采集的内在设计方式使得异常事件反映在时间序列的意外偏差中。许多基于传感器的收集机制尤其如此。虽然这可以通过无监督的方法来捕获，但监督的增加有助于消除可能具有不同潜在原因的虚假事件。例如，考虑一个环境监控应用程序的情况。许多偏差可能是传感器设备故障或导致传感器值偏差的其他虚假事件的结果。这可能不一定反映出一个感兴趣的异常。虽然异常事件通常对应于传感器流值的极端偏差，但不同类型偏差的精确因果关系可能非常不同。这些其他嘈杂或虚假的异常可能对分析师没有任何兴趣。例如，考虑图14.12所示的情况，其中说明了包含加热流体的加压管道内的温度和压力值。图14.12a和b说明了管道破裂场景中两个传感器的值。图14.12c和d显示了在压力传感器发生故障的情况下两个传感器的值，并且这导致压力传感器中每个时间戳的值为0。在第一种情况下，压力和温度传感器的读数受故障影响，尽管最终压力值不为零，但它们反映了外部环境中的压力。第二种情况下，温度传感器的读数完全不受影响，因为故障特定于压力传感器。
因此，关键是要在多元情景中区分不同行为属性的偏差。监督的使用非常有用，因为它可以用来确定不同流之间偏差的差异行为。在上述的管道破裂情况下，两次事件的相对偏差是非常不同的。在标签输入中，假定大部分时间戳标记为“正常”。一些地面实况时间戳$T_1，T_r$被标记为“罕见”。这些用于监督。 这些被称为主要异常事件。另外，虚假事件也可能导致很大的偏差。这些时间戳被称为次要异常事件。在某些应用特定的情况下，可能会提供次要异常事件的时间戳，尽管这里没有假设。书目注释包含了这些增强方法的指针。

1. （批处理）了解最能区分真实周期和正常周期的系数$\alpha_1...\alpha_d$。本节稍后会讨论此步骤的详细信息。
2. （实时）使用14.3节讨论的任何预测方法，确定每个时间序列数据流的（绝对）偏差水平。这些对应于白噪声误差项的绝对值。假设时间戳$n$处的流$j$的绝对偏差水平由$z^j_n$表示。
3. （实时）结合不同流的偏差水平如下，创建综合报警水平： $<span><span class="MathJax_Preview">Z_n=\sum^d_{i=1}\alpha_iz_n^i\tag{14.24}</span><script type="math/tex">Z_n=\sum^d_{i=1}\alpha_iz_n^i\tag{14.24}$ $Z_n$的值在时间戳$n$处报告为警报级别。阈值可用于警报级别以生成离散标签。

最后一节中尚未讨论过的主要步骤是判别系数$\alpha_1...\alpha_d$。应在训练阶段选择这些参数，以便使主要事件与正常时段之间的警报级别差异最大化。 为了了解训练阶段的系数$\alpha_1...\alpha_d$，对于所有感兴趣的主要事件，综合报警水平在时间戳$T_1...T_r$的平均值。请注意，每个时间戳$T_i$处的综合报警水平是一个代数表达式，它是根据公式14.24的系数$\alpha_1...\alpha_d$所写出的线性函数。这些表达式被累加在时间戳$T_1...T_r$上以创建作为$(\alpha_1，...alpha_d)$的函数的警报水平$Q^p(\alpha_1...\alpha_d)$。
$<span><span class="MathJax_Preview">Q^p(\alpha_1...\alpha_d)=\frac{\sum{_{i=1}^r}Z_{T_i}}{r}\tag{14.25}</span><script type="math/tex">Q^p(\alpha_1...\alpha_d)=\frac{\sum{_{i=1}^r}Z_{T_i}}{r}\tag{14.25}$ 通过使用所有可用时间戳也计算正常警报级别$Q^n(\alpha_1...\alpha_d)$的类似代数表达式，其中大多数时间戳被假定为正常。 $<span><span class="MathJax_Preview">Q^n(\alpha_1...\alpha_d)=\frac{\sum{_{i=1}^r}Z_i}{n}\tag{14.26}</span><script type="math/tex">Q^n(\alpha_1...\alpha_d)=\frac{\sum{_{i=1}^r}Z_i}{n}\tag{14.26}$ 与事件签名一样，正常的警报级别也是$\alpha_1...\alpha_d$的线性函数。然后，最优化问题是确定$\alpha_i$的最优值，增加主要事件和正常警报水平之间的差异签名。这个优化问题如下： $<span><span class="MathJax_Preview">Maximize\ Q^p(\alpha_1...\alpha_d)=Q^n(\alpha_1...\alpha_d)\\\text{subject to:}\sum^d_{i=1}\alpha^2_i=1</span><script type="math/tex">Maximize\ Q^p(\alpha_1...\alpha_d)=Q^n(\alpha_1...\alpha_d)\\\text{subject to:}\sum^d_{i=1}\alpha^2_i=1$ 这个优化问题可以使用任何现成的迭代优化求解器来解决。实际上，在遇到新事件时，在线事件检测和各种学习过程将同时执行。在这种情况下，$\alpha_i$的值可以在迭代优化求解器中递增更新。综合报警级别可以作为事件评分报告。或者，可以使用警报级别上的阈值来生成预测事件的离散时间戳。阈值的选择将调节预测事件的精确度和召回率之间的交易。

14.7.2 全系列分类

在全系列分类中，标签与整个系列相关联，而不是与单个时间戳相关联的事件。假设有一个$N$个不同系列的数据库可用，每个系列的长度为$n$。每个系列都与从$\{1 ... k\}$绘制的类标签相关联。
许多基于邻近的分类器是在时间序列相似度函数的帮助下设计的。因此，相似函数的有效设计在分类中至关重要，正如许多其他时间序列数据挖掘应用中的情况一样。
下面将讨论三种分类方法。其中两种方法是归纳方法，其中只有训练实例用于构建模型。 然后用它们进行分类。第三种方法是传导半监督方法，其中训练和测试实例一起用于分类。半监督方法是一种基于图的方法，其中将未标记的测试实例用于更有效的分类。

14.7.2.1 基于小波的规则

时间序列分类中的一个主要挑战是很多系列可能是嘈杂且不相关的。分类属性只能在系列中不同长度的时间片段中展现。例如，考虑图14.11中的系列向学习者提供标签的场景。在标签对应衰退的情况下(图14.11a),对于学习者来说，分析几周或几个月的趋势以确定正确的标签非常重要。另一方面，如果标签对应于发生闪烁碰撞(图14.11b)，学习者必须能够提取一天中的趋势。
对于一个给定的学习问题，可能并不知道应该在学习过程中使用哪种粒度级别。$Haar$小波方法提供时间序列数据的多粒度分解以处理这种情况。正如在14.4节讨论的，在时间序列图案上，小波是一种有效的方法来确定不同粒度级别的频繁趋势。因此将多颗粒主题发现与关联分类器结合是很自然的。
建议读者参考第2章的2.4.4.1节讨论小波分解方法。阶$i$的$Haar$小波系数分析一段时间内的趋势，其与$2^{-i}\cdot n$成比例，其中$n$是该系列的全长。具体而言，系数值等于长度为$2^{-i}\cdot n$的时间段的前半部分和后半部分的平均值之差的一半。由于哈尔小波表示转换中不同阶次的系数，它会自动考虑不同粒度的趋势。事实上，系列中任何特定窗口中的任意形状通常可以通过小波系数的适当子集很好地近似。这些可以被认为是特定类别标签特有的签名。基于规则的方法的目标是发现特定类别标签特有的签名。因此，基于规则的方法的整体训练方法如下：

1. 生成$N$个时间序列中的每一个的小波表示以创建$N$个数字多维表示。
2. 分解小波表示以创建时间序列小波变换的分类表示。因此，每个分类属性值表示小波系数的数值范围。
3. 使用第10章10.4节中描述的任何基于规则的分类器生成规则集。规则前提中小波系数的组合对应于时间序列中与分类相关的“签名”形状。

一旦生成了规则集，它就可以用来对任意时间序列进行分类。给定的测试序列被转换成其小波表示。本系列文章中的规则已确定。这些用于分类测试实例。 有关使用规则集来分类测试实例的方法，请参见第10章的10.4节，当已知类别标签对周期性而非局部趋势敏感时，此方法应与傅立叶系数一起使用，而不是小波系数。

14.7.2.2 最近邻分类器

最近邻分类器在第10章的10.8节中有过介绍。只要有适当的距离函数可用，最近邻居分类器可以用于几乎任何数据类型。时间序列数据的距离函数已经在第3章的3.4.1节中介绍过了。可以使用任何这些距离（相似性）函数，具体取决于领域特定的情况。基本方法与多维数据的情况相同。对于任何测试实例，确定训练数据中的$k$个最近邻居。来自这些最近邻居的主要标签被报告为相关类别标签。$k$的最优值可以通过使用一次性交叉验证来确定。

14.7.2.3 基于图形的方法

相似图可用于几乎任何数据类型的聚类和分类。第11章11.6.3节中介绍了半监督分类相似图的使用，基本方法根据训练和测试实例构造相似度图。因此，这种方法是一种传导性方法，因为测试实例与训练实例一起用于分类。构造图$G =(N，A)$，其中$N$中的节点对应于训练和测试实例中的每一个。$G$中的节点的子集被标记。这些对应于训练数据中的实例，而未标记的节点对应于测试数据中的实例。$N$中的每个节点都连接到它的k个最近的邻居，并且在$A$中具有一个无向边。相似度是使用上第3章的3.4.1或3.4.2节中讨论的任何距离函数来计算的。然后使用N中节点的指定标签为节点未知的节点派生标签。这个问题被称为集体分类。许多用于集体分类的方法在第19章的19.4节中讨论。

14.8 总结

时间序列数据在很多领域都很常见，例如传感器网络，医疗保健和金融市场。通常情况下，时间序列数据需要进行归一化处理，并且需要对缺失值进行有效处理。在时间序列分析中使用许多数据缩减技术，例如傅立叶和小波变换。相似性函数的选择是时间序列分析最关键的方面，因为许多数据挖掘应用程序（如聚类，分类和异常值检测）都依赖于此选择。 　　预测是时间序列分析中的一个重要问题，因为它可用于对未来的数据点进行预测。大多数时间序列应用程序使用点式或形状式分析。例如，在聚类的情况下，逐点分析产生时间相关聚类，其中聚类包含许多不同系列一起移动。另一方面，形状分析着重于确定具有大致相似形状的时间序列组。 　　点分离异常值检测问题与预测密切相关。如果时间序列数据点与预期值（或预测值）存在显着差异，则它是异常值。在时间序列数据中使用相似性函数定义形状异常值。当将监督结合在逐点异常值检测中时，问题被称为事件检测。许多现有的分类技术可以扩展到基于形状的分类。

14.9 书目注释

统计学家和计算机科学家对时间序列分析问题进行了广泛的研究。关于时间数据挖掘和时间序列分析的详细书籍可以在[134,467,492]中找到。数据准备和规范化是时间序列分析的重要方面。分箱方法也被称为分段聚合近似$（PAA）$[309]。$SAX$方法在[355]中描述。$DWT，DFT和DCT$变换在[134,467,475,492]中进行了讨论。时间序列相似性度量在第5章详细讨论。本书的第3章，以及$Gunopulos$和$Das$[241]的早期教程。
[151,394,395,418,524]中讨论了时间序列发现的问题。本章基于距离的主题讨论基于[356]中的描述。在[51]中讨论了基于小波的多分辨基元发现方法。 发现的图案用于分类。关于周期性模式挖掘的进一步讨论可参见[251,411,467]。 时间序列预测的问题在[134]中详细讨论。距离函数的下界对于快速修剪和索引是有用的。 在[309]中已经显示了$PAA$的下限。已经显示如何在[308]中对DTW执行下边界。
最近一项关于时间序列数据聚类的调查可以在[324]中找到。在线聚类时间序列数据流的问题与传感器选择问题有关。[527]中引入了选择性$MUSCLES$方法，可以用来从一组时间序列中选择代表。本章讨论的在线相关方法基于[50]中的讨论。传感器数据的代表性选择算法的调查可以在[414]中找到。许多这些算法也可以用于在线相关聚类。
关于时态数据异常值检测的调查可参见[237]。关于时间异常值检测的章节也可以在最近的异常值检测书中找到[5]。时间戳的在线检测被称为事件检测。 这个问题的监督版本与罕见的类别检测有关。监督事件检测方法讨论部分。[52]中提出了14.7.1。本书讨论的$Hotsax$方法在[306]中提出。在[51]中讨论了基于小波的序列分类方法。这一方法已经适用于本章中的时间序列数据。时间数据分类调查可以在[33,516]中找到。后面的调查是关于序列分类的，但它也讨论了时间序列分类的许多方面。

14.10 习题

1. 对于时间序列（2,7,5,3,3,5,5,3），确定分箱选择的长度为2的分箱时间序列。
2. 对于练习1的时间序列，构建一个窗口大小为2个单位的滚动平均数列。将结果与前一个练习中获得的结果进行比较。
3. 对于习题1的时间序列，构造指数平滑序列，平滑参数$\alpha=0.5$。将初始平滑值$y_0$设置为序列中的第一个点。
4. 实现分箱，移动平均和指数平滑方法。
5. 考虑一个序列，其中连续值如下相关： $<span><span class="MathJax_Preview">y_{i + 1} = y_i\cdot(1 + R_i)\tag{14.27}</span><script type="math/tex">y_{i + 1} = y_i\cdot(1 + R_i)\tag{14.27}$ 这里$R_i$是一个随机变量，取自[0.01,0.05]。你会采用什么样的转变来使这个系列保持静止？
6. 考虑将yi定义如下的系列： $<span><span class="MathJax_Preview">y_i = 1 + i + i^2 +R_i\tag{14.28}</span><script type="math/tex">y_i = 1 + i + i^2 +R_i\tag{14.28}$ 这里$R_i$是一个从[0.01,0.05]中抽取的随机变量。你会采用什么样的转变来使这个系列保持静止？
7. 对于具有傅里叶系数$X_0...X_{n-1}$的实值时间序列$x_0...x_{n-1}$,证明$X_k + X_{n-k}$对于每个$k\in\{1…n-1\}$。
8. 假设你想对一组时间序列实现$k-means$算法，并且每个维数减少的序列给出了相同的复数傅里叶系数子集。在原始时间序列上使用$k-means$会如何不同？
9. 使用$Parseval$的定理和加法性来表明两个系列的点积与真实部分的点积和这两个系列的傅里叶系数的虚部的点积之和成正比。什么是比例因子？
10. 为时间序列数据实现一个基于形状的k-最近邻分类器。
11. 将基于距离的图案发现算法推广到本章讨论的图案允许的任意长度[a，b]，并且曼哈顿段距离用于距离比较的情况。曼哈顿距离之间的曼哈顿段距离与曼哈顿距离相同，只是它将距离与主题长度相除以进行归一化。
12. 假设你有一个$N$系列的数据库，并且计算出$motifs$的频率，所以它们在任何系列中的出现次数都是1。讨论一个算法的细节，该算法可以使用小波来确定不同分辨率下的图案。

​
​
​
​