outlier detection- part2

第九章 时间序列和多维流异常诊断
9.1 引言
首先时间序列具有连续性，即数据中的模式不会突然变化, 除非有异常的进程在起作用。

1. 时序突变诊断：数据随时间连续变化，而异常点或异常段表现为对前期数据的突然偏离。在整个时间序列可脱机使用的情况下, 可以利用后视的优势来识别异常时序值或形状。在有多个序列可用的情况下, 可以利用交叉关联, 尽管它们通常对每个序列的分析起次要作用。这是因为时间序列数据是上下文的, 这就对序列值施加了强大的时间局部性。
2. 多维数据中的新颖性和变化检测：在这种情况下, 数据包含彼此独立的多维点, 与时间序列数据相比, 时间连续性问题要弱得多。例如, 在从传感器数据时间序列中, 两个连续的数据值通常几乎相同。另一方面, 新闻流中的单个文本文档 (多维数据点) 通常可能与前一篇文章有很大的不同。为了构造一个鲁棒的异常值模型, 需要将数据点与文档的历史记录进行比较。多维流数据中的异常可能与总体趋势发生变化或单个数据点第一次出现的时刻相对应(The anomalies in multidimensional streaming data could correspond to either time-instants at which aggregate trends have changed or novelties in individual data points. )。后者要求识别流中传入的与以前看到的有很大不同的点。这种情况几乎与脱机异常值分析相同。在这种情况下, 记录的所有方面都被视为一个单元, 并通过汇总这些单位的时间趋势来确定异常情况，这种类型的分析是水平的。
   例如, 文本流中特定主题的第一个故事被视为新奇异常值, 而文本流中主题的聚合趋势的变化是一个变化异常值。在稍后阶段, 类似的数据点可能不再被认为是新奇的, 可能成为数据的正常部分。因此, 总体趋势的重大变化很重要。
   
   时间序列中的异常值是上下文异常或集体异常。上下文异常是指特定时间戳中的值与其时间相邻值不同，发生突变的情况, 而集体异常指整个时间序列或时间序列中的子序列具有不寻常的形状。例如, 考虑图 9.1(a) 和 (b) 中说明的两种情况。第一个时间序列说明了S & p 500在2010年5月16日, 也就是股市崩盘的相对行为，不管从股票价值下跌的偏差的角度来看, 还是从时间序列形状的角度来看，都是不同寻常的。另一方面，9.1b是S & p 500在2001年的行为，这一年有两次重大下跌, 既是因为股市疲软, 也是因为911恐怖袭击。虽然下降的特定时间戳可能会被认为有些不正常, 但这个时间序列的形状并不罕见。在不同类型的应用中, 可能有不寻常的时间点或异常形状的异常识别需求。
   时间数据允许多种方法定义异常，"数据越复杂, 分析师就越需要事先对被认为是正常的东西进行推断“。例如传感器数据, 有时使用偏差检测方法进行噪声异常滤波, 而在其他情况下, 医疗流中的异常形状可以诊断心脏状况, 如心律失常。
   离线和联机 (流式) 设置有区别。流式分析只有截至当前时间的流可用，而离线分析使用整个历史记录，同时后视的优势允许更复杂模型进行更好的异常识别。
   可以使用标签来监督时间序列或多维异常点检测过程。在时间序列设置中, 标签可能与时刻、时间间隔或者整个时间序列相关联；在多维设置中, 标签与各个数据点相关联。在这种情况下, 问题简化为异常类检测的特殊情况 (参见第7章)。一般来说, 监督方法几乎总是比无监督方法表现得更好, 因为它们能够发现特定应用的异常。一般建议有监督的情况下使用监督学习方法。
   尽管时间数据可以包含连续数据或离散序列,本章侧重于连续数据以保持同质性。因为离散数据与连续数据在对时间连续性概念的定义不同。在离散数据的情况下, 数据值中缺乏排序会显著影响异常分析方法。离散数据的情况将在下一章中单独讨论。这两章是关于基于时间和序列的异常检测。
   本章的组织结构如下。在下一节中, 将介绍流时间序列中异常检测算法，基于实时进行数值与预测值的偏差检测的方法，异常是上下文异常。在第9.3 节中, 将介绍检测时间序列中异常形状的方法，即集体异常值。第9.4 节讨论了多维流异常点检测的方法。第9.5 节提出了结论和摘要。

9.2 时间序列流基于预测的异常诊断
时间异常检测最常见的是利用基于回归的预测模型检测异常偏离时刻点。这些异常是上下文异常, 因为它们根据相邻时刻的数值关系来定义数据异常时刻。这种方法可以用来检测突变, 也可以过滤底层流的噪声。时间序列中基于偏差的异常值与时间序列预测问题密切相关，这一观点与第7章第7.7 节关于预测和异常检测的关系密切相关。
在这些方法中, 时间连续性发挥着重要作用, 因为假定时间序列数据值在连续时刻具有高度相关性, 并且时间趋势不会突然变化。基于偏差的异常值通过各种回归模型预测下一个时间戳的值，使用单个时间序列或多个序列中的相关性来进行预测。因此, 使用两种类型的相关性：

• 单个时间序列的相关性：这与时间连续性的原理相同, 通常是使用自回归建模和预测来实现的。与预测值存在重大偏差被定义为异常值。
• 跨序列的相关性：多个传感器的时间序列往往彼此密切相关。例如, 在一个传感器处的鸟叫声通常也会被附近的传感器记录。在这种情况下, 可以经常使用一个序列来预测另一个。与此类预测值的偏差可以认定为异常值。

本章将研究回归技术在时序数据中的应用, 在数据规范和建模方面具有许多独特的特点。
9.2.1 自回归模型
自回归模型 (AR) 在单变量时间序列的上下文中特别有用。假设单变量时间序列： $X_1...X_t...$，在自回归模型中, $X_t$ 是根据长度 p 的前一个窗口中的值定义的：$X_t={\sum }_{i=0}^p{a}_i\ast X_{t-i}+c+{ϵ}_t\dots \dots (9.1)$
使用前一个长度为p 窗口的模型称为 $AR(p)$模型。回归系数的值$a_1...a_p,c$ 需要从训练数据（时间序列的历史数据）中学习。${ϵ}_t$为误差项, 它们彼此不相关。由于这些误差项代表了意想不到的行为, 它们可以用于量化异常得分。

通过在训练数据的每个时刻使用公式 9.1, 可以创建系数之间的线性方程组。因此, 长度 n 的时间序列可以提取 (n−p) 个线性方程组。当这个数字远远大于变量的数量 (p + 1) 时, 这个方程组没有精确的解。系数$a_1...a_p,c$ 可以用最小二乘回归近似，从而最小化过度确定系统的平方误差。 可以生成具有 (p + 1) 维度 (包括常量项) 和 (n-p) 点的 (n−p)×(p+1) 独立变量矩阵 D，用于回归建模。矩阵 D 的行包含大小为 p 的窗口中的行为属性值, 以及代表常量项在末尾追加的值 1：
(N-p)维列向量 $\vec{y}$ 包含因变量, 它们是每个 (n-p)在p + 1…n时刻的行为属性值。列向量 $\vec{y}$ 的定义如下：

我们想得到最优系数$a_1...a_p,c$，最大限度地减少的最小二乘误差。
请注意约等于"≈", 因为我们省略了公式9.1中的误差项。如第3章3.2.1 节所述, 需要转置大小为(p+1)×(p+1) 的矩阵$D^{T}D$, 以确定系数$a_1...a_p,c$，将近似的最小二乘误差最小化。相应的解决方案如下所示：
在时间戳数量不明显大于 p 的情况下, 矩阵$D^{T}D$可能不是可逆的，正则化是很有帮助的。 如果使用正则化, 对于大于零的较小正则化参数值$\alpha$, 矩阵$(D^{T}D+\alpha I)$被转置。值得注意的是, 随着新时间戳的增加, 新行被添加到 D 和 $\vec{y}$ 中, 矩阵$D^{T}D$和$D^T\vec{y}$可以增量地保持。但是, 在每次迭代中仍必须执行矩阵$D^{T}D$的转置。通过使用matrix-inversion lemma, 可以以增量的方式更有效地执行此操作。
在公式9.1 中,${ϵ}_t$表示与预期值的偏差, 对应于每个时间戳的异常值。人们可以使用学习的系数来估计这些偏差, 其中绝对值较大的偏差对应于异常。为了简化分析, 假定这些值是独立同分布, 并且来自正态分布的随机变量 (i. i. d.)。这一假设可用于假设检验, 将异常得分转换为时间戳上的异常标签。
通过将自回归模型与移动平均模型 (MA 模型) 相结合, 可以使其更加稳健。该模型预测时间序列中的后续值是历史偏差的函数。移动平均模型的定义如下：

换句话说, 利用时间序列中过去的冲击历史来预测值。上述模型也称为 MA (q)。$\mu$是时间序列的平均值。$b_1...b_t$是需要从数据中学习的系数。移动平均模型与自回归模型有很大的不同, 因为它将当前值与序列的平均值和以前的偏差历史联系起来, 而不是以前的历史值。请注意, ${\sum }_{i=1}^q{b}_i\ast {ϵ}_{t-i}$表示历史冲击或异常得分的线性组合。从这个意义上说, 移动平均模型非常有趣, 因为它将序列的当前值表示为意外行为的函数。同时, ${ϵ}_{t-i}$不是观察值, 而是与预期值的偏差 (这些值本身是根据历史偏差计算的)。因此, 这个特殊的方程组本质上是非线性的。一般来说, 这类系统找不到闭式解, 使用迭代非线性拟合求解。
实际上, 以前的偏差历史和值对于计算预期值可能都很重要。然后, 可以将这两个模型与 p 自回归项和 q 移动平均项组合成为自回归移动平均 (ARMA) 模型：

上述模型是 ARMA (p, q) 模型。关键问题是这些模型中参数 p 和 q 的选择。如果p 和 q 的值太小, 则模型将不适合数据, 所有噪声项的绝对值将太大, 无法提供有关真实异常的信息。 如果p 和 q 的值太大, 则模型可能会拟合，所有噪音项都将接近0。一般情况下, 选择尽可能小的 p 和 q 值, 这样模型就能很好地适应数据。如果选择使用较大的 p 和 q 值, 则在线性回归中使用正则化很重要。通过利用leave-one-out 交叉验证最小化预测误差, 可以确定模型和最佳参数。
在某些情况下, 时间序列可能会有一些持久的趋势, 因此可能偏离均值。随机游走时间序列就是这样，这称为时间序列的非稳定性。从预测的角度来看, 不稳定是一个问题, 因为随着时间的推移, 较旧的数据变得陈旧, 并且可能不再与基于回归的建模相关。例如, 人们不能指望使用基于窗口的回归模型, 根据百年前的价格预测今天的价格。这是因为价格呈现出明显的趋势。在这种情况下, 可以通过在 ARMA 建模之前首先对时间序列进行差分。这种建模方法被称为自回归集成移动平均模型 (ARIMA)。 在其他情况下, 在差异操作之前, 将对数等函数应用于序列。
9.2.2 多个时间序列回归模型
在许多应用中, 可以使用多个时间序列, 以便以更可靠的方式进行时间序列预测。其想法是, 不同的时间序列通常可能包含相同的信息, 有时可能包含滞后相关性。例如, 附近的传感器也会听到一个传感器的鸟叫, 尽管有一点滞后，这种滞后相关性可以用来做出更稳健的预测。基于标准回归的模型通过定义变量$X_t^j$以及其他时间序列的历史，可以推广。下面讨论了一些常用的方法：
9.2.2.1 自回归模型的直接泛化
多元自回归模型的基本思想是用过去的长度p的窗口预测每个时间戳的值。与单变量回归模型的主要区别是每个时间戳 (对于任何特定序列) 的值被预测为长度为p 的上一个窗口所有流中所有 dp 值的线性函数。因此, 通过滑动窗口，可以生成一些列含dp个系数的线性方程组。系数$a_i^{kj}$表示序列k第i前时间戳 (从当前时间戳) 对第j序列当前时间戳的预测能力。假设t是当前时间戳，如果 $X_t^1...X_t^d$ 表示所有 d 不同序列的第t个值, 简单的自回归模型表示 $X_t^j$如下所示：
请注意, 公式9.1 和9.8 之间的主要区别在于, 前者将时间序列表示为其自身直接历史的线性函数, 而后者表示的时间序列不仅是其自身直接历史，还包括其他时间序列的线性函数。因此, 对于 n 个时间戳, 可以构造一个大小 $(n-p)\ast [(d\cdot p)+1]$的矩阵D, 其中D的第i行是以下$(d\cdot p)+1$维向量：

因此, D 是一个$(n-p)\ast [(d\cdot p)+1]$维矩阵。类似地，我们将 Y 定义为 $(n-p)\ast d$ 维度矩阵：
将这个方程与公式9.4 的单变量情况进行比较，使用近似相等 "≈"是因为我们省略了公式9.8 中的误差项，需要通过最小二乘优化将这些误差降至最低。
我们可以用A表示公式9.10 中的系数矩阵。因此, 需要学习 $(d\cdot p+1)\ast d$ 的系数矩阵A, 从而最大限度地减少以下关系的最小二乘误差：$Y\approx DA\dots \dots (9.11)$
$A=(D^{T}D{)}^{-1}{D}^{T}Y\dots \dots (9.12)$
可以通过将$\alpha I$ 添加到 $D^{T}D$来正则化，其中$\alpha >0且数值较小$。
在每时刻, 由${ϵ}_t^j$表示的 d 个不同残差 (对于不同的 j 值), 这些残差与d个不同序列的异常值相对应，其中${ϵ}_t^j$的较大绝对值被认定为异常。请注意, 一个序列中的异常得分相互可比, 但如果预处理步骤序列未进行归一化为单位方差, 那么不同序列的异常得分可能无法相互比较。这是因为在不同的j值 (可能代表不同的物理量, 如温度和压力) 下，${ϵ}_t^j$可能具有不同的均值和标准偏差。在线分析时, 规范化通常是不可能的。因此, 可以使用正态分布假设 (或 t-分布) 来确定不同异常的显著程度。通常, 对于固定值j，${ϵ}_t^j$的不同值假定来自正态分布或 t 分布。
这种广义的公式也可以推广到自回归移动平均 (ARMA) 和自回归综合移动平均 (ARIMA) 模型。为了在学习跨流系数和自回归系数时更加重视近期数据流, 还可以采用指数遗忘机制。这是因为流自动关联和交叉关联也可能随着时间的推移而发生显著变化。
该方法的一个问题是由于大小为$(p+1)\times (d\ast p+1)$ 的矩阵的转置增加了计算复杂度。如何在将复杂性保持在可管理的水平的同时, 使用多元回归的基本原理进行预测？文献中提出了两种这样的方法：

• 可以选择流的子集, 以便对一组较小的变量执行回归。
• 一个根本不同的方法是使用隐藏变量的概念将多变量预测问题分解为一组 (更容易解决的) 单变量预测问题。

9.3 异常形状的时间序列
关于时间序列异常值检测的大部分工作是确定异常变化或与底层序列的非常大的偏差。但是, 某些类型的偏差不仅基于数据点的个别偏差, 而且还基于时间序列中相对于其他部分的形状偏差。如图 9.1(a) 所示的闪崩的情况：股市在多个时刻表现出非常不寻常的行为, 先是在很短的时间内突然下跌, 然后很快恢复到几乎达到原来的水平。这种不寻常的行为与股市的大多数其他下跌有着不同的因果关系。因此, 该序列的形状与其他较大偏差的不同。显然, 确定与以前的时间戳的较大偏差不能发现这种异常, 因为需要从其他正常系列的角度来看待整个系列 (或子序列)。换言之, 这套时间戳必须集体查看, 以了解是否应将其视为异常。
此方法的目标是确定给定序列的数据 (或子序列) 的窗口, 其中给定序列的行为不同于多个序列的数据库。与本章前面讨论的异常值由单个位置定义的情况不同, 此类异常值对应于多个连续的时间戳;在这些时间里, 特定图案的异常共现代表异常值。因此, 以前的情况对应于上下文异常值, 而这种情况对应于集体异常值。在这种异常检测的情况下, 可能存在两种可能性：

• 全序列异常: 在这种情况下, 整个序列的形状被视为异常。将此形状与类似时间序列的数据库进行比较。但是, 在大多数情况下, 除非序列数据库对应于相对较短的时间戳部分, 否则序列中的噪声变化将掩盖异常形状。这类似于在高维数据中检测异常时遇到的噪声问题。

• 基于子序列的异常: 如果时间序列是在很长一段时间内收集的, 那么我们可能有一个较短时间内显示典型趋势的时间序列。因此, 认为与典型趋势有偏差，在时间序列的小窗口上检测到的异常形状为异常。
  这两种问题之间的区别在一定程度上是人为的，子序列异常检测的第一步是从时间序列中提取窗口, 然后将提取的子序列作为整体序列处理,进行异常检测。随后, 可以在提取的窗口上应用基于距离、概率或线性的方法。
  在处理子序列异常时, 必须始终考虑相邻窗口之间的重叠。对于全序列异常, 更长的序列更值得关注。在所有情况下, 假定该序列已归一化为零均值和单位标准偏差, 因为比较不同的均值和振幅的序列没有意义。 此外, 在许多模型中, 假定所有基础序列的长度都相同为n。
  9.3.1 转换为其他表示
  有两种类型的转换用于比较时间序列的各个段：

• 数字多维变换: 在一种情况下, 序列 (或序列的每个子序列) 被转换为多维向量。每个维度的表示对应于标准向量空间中的数值系数。邻近可以通过欧氏距离计算。因此, 本书第4章中讨论的许多方法可以用来确定基于邻近的异常。

• 离散序列转换: 在第二种情况下, 可以使用离散化方法将序列转换为符号表示。在这种情况下, 第10章中讨论的方法可以用来确定时间序列中的异常形状。
  9.3.1.1 数值多维变换
  最简单的转换是将时间序列中长度为n的每个窗口视为长度为n的多维向量。其他方法, 如离散小波变换 (DWT) 和离散傅立叶变换可用于压缩序列到数值系数。最常见的小波类型是 Haar 小波。该序列的全局平均值存储为第一个系数。然后, 对于长度为n的时间序列, 可以按照下述方法递归生成剩余的 (n-1) 小波系数：

1. 报告前半部分和后半部分的平均值之间的差异的一半作为第一个小波系数。这提供了序列前部分与后部分之间最基本的全局趋势。
2. 递归计算每个序列前半部分和后半部分的 (n/2-1)小波系数, 以确定剩余的 (n−2) 系数。这些提供该序列的两个部分的局部趋势。
   请注意, 小波系数的数量与时间序列的长度完全相等。可以看出序列中的每个点都可以用这一组小波系数进行精确地重构。时间序列可以精确地重建为 n 个原始、类似小波的时间序列的系数加权和，每个时间序列看起来都像一个在 {-1, 0, 1} 上绘制的阶跃函数。请注意, 每个系数表示序列的特定段的前半部分和后半部分之间的差值。特定系数的类似小波的原始序列是通过 (i) 将该序列的相关部分的前半部分设置为 + 1 (ii) 将序列相关段的后半部分设置为-1 和 (iii) 设置时间的所有其他部分定义的系列到0。
   例如，时间序列(8,6,2,3)。全局均值是4.75,1级系数是(7-2.5)/2=2.25,2个二级系数分别是(8-6)/2=1和(2-3)/2=-0.5，因此小波表示为(4.75,2.25,1,-0.5)。可以重建原始序列为原始小波级数的加和
   
   
   图9.4 显示了将时间序列分解为小波系数的图形说明。请注意, 基向量是相互正交的, 较高粒度的系数捕获详细 (局部) 趋势, 而较低粒度的系数捕获长期 (全局) 趋势。在这个特定的示例中, 我们只有两个级别的粒度。小波分解本质上是一种多分辨率分解, 其中长度为n的序列的分辨率级别是O(log2(n))。
   对于具有 N 个长度为 n 的时间序列的数据库, 可以利用小波变换创建N个维数为n的新多维数据点。虽然在使用单个序列时丢弃小系数是很常见的, 但在多个序列的数据库中修剪小小波系数要困难得多, 因为在大多数序列中, 特定系数可能很小, 但该系数的值很大。从异常值检测的角度来看, 即使是单个序列也可能是相关的。因此, 将保留所有系数。
   变换前后size相同 (即N*n), 那么小波表示的优点是什么？小波变换的关键点是, 可以将新的表示形式视为多维数据集, 而不是相互依赖的数据集, 因为数据中的短期和长期依赖关系已经编码在小波系数中。 因此, 可以简单地利用传统模型对小波表示的多维数据 (如单类SVM或子空间方法) 进行异常检测。除了一些基于距离的模型之外, 通常不可能 (有效地) 使用具有原始时间序列表示形式的现成模型 (因为它们忽略了数据值之间的基本依赖关系)。使用小波系数而不是时间序列时, 将保留诸如欧氏函数之类的距离函数。这是因为新的基向量集是相互正交的, 而旋转轴系统不会影响欧几里得距离。
   离散傅立叶变换是另一种降维和转换为一种新的表示形式的方法, 其中隐式依赖关系以系数编码。但是, 在傅立叶变换中, 重点是捕获周期性依赖关系, 而不是局部变化。感兴趣的读者可参考 [33] 了解傅立叶变换的详细信息。 这些转换中哪一个更有效, 何时应该每个转换使用？通常, 当只有少量系数在表示中占主导地位时, 变换就更有效。当 (通常) 非主导系数显示较大的值时, 这往往会放大异常值。在选择正确的转换时, 有以下一些一般准则：
3. 其中包含大量季节性或周期性的时间序列通常与 DFT 配合得很好
4. 倾向于显示局部连续性的时间序列 (即, 在小范围内变化不大的值) 通常与 DWT 配合良好。
   因此, 在选择要使用的特定转换之前, 对手头的问题有更深入的理解通常是有用的。图9.5 显示了两种类型的序列示例, 其中这两种转换可以很好地工作。[33] 中提供了一个精确的解释, 说明为什么这种类型的转换在各种情况下更相关。还可以通过适当的修改将其中的一些转换应用于多变量序列和空间数据。
   
   欧氏距离可以用在这些表示上计算异常得分。特别是, 给定两个长度为n的子序列 (或转换表示) ，分别表示为$A=(a_1...a_n)$ 和 $B=(b_1...b_n)$, 它们之间的欧氏距离可以计算如下
   序列的第k近邻距离可以作为其异常得分。一个主要的挑战是, 所有这些方法都需要 $O(N^2)$ 时间来计算成对距离, 其中 N 是子序列的总数。正如第4章所讨论的, 这是所有此类基于距离的模型的问题。与多维数据的情况一样, 9.3.2 节将讨论类似的修剪方法, 以提高计算效率。
   9.3.1.2 离散序列转换
   从理论上讲, 可以将连续时间序列转换为离散数据, 然后使用下一章中讨论的方法来发现异常形状。此转换通常在数据的窗口上执行, 并导致时间序列的压缩和近似表示。这种方法既可用于使用第10章中讨论的方法对离散序列进行独立异常检测, 也可用于通过快速近似表示和修剪提高近邻异常检测效率。后一种情况将在下一小节中讨论。各种离散变换是可能的, 例如 (象征性地离散表示) 在特定窗口平均、倾斜，离散小波系数和傅立叶变换系数。所使用的特定表示形式应取决于当前的应用。
   一种常用的离散化技术是符号聚合近似 (SAX) 。在此方法中, 使用分段聚合近似 (PAA) 来表示时间序列。此方法包括两个步骤：

• 基于窗口的平均: 该系列被划分为长度为w的窗口, 并计算每个窗口上的平均时间序列值。
• 基于值的离散化: (已经平均的) 时间序列值被离散为一个较小的近似深度间隔数。这样做的目的是确保每个符号在时间序列中的频率大致相等。实际区间边界是通过假设时间序列值是以高斯假设分布的来构造的。需要注意的是, 为了构造高斯分布, 需要计算 (窗口的) 时间序列值的均值和标准差。高斯分布的量值用于确定间隔的边界。通常情况下, 这些值被离散为3或4个间隔, 以获得最佳结果。每个这样的等深度间隔都映射到一个符号值。这将创建时间序列的符号表示形式。
  需要注意的是, 符号离散化确实会丢失一些有关基础时间序列的信息。例如, 符号不提供有关不同间隔之间的距离的信息。然而, 这种近似方法在流式传输场景中很有用, 因为它们简单、易于构造, 并且能够方便地使用各种基于模式和规则的模型。下一章将讨论这些模型。
  9.3.1.3 利用时间序列的轨迹表示
  从多元序列中发现不寻常形状的情况更具挑战性。在这里, 不同的行为属性, 如温度、压力或相同的行为属性, 如温度, 可以在同一时刻由不同的传感器测量。因此, 在这种情况下, 需要非常仔细地定义异常形状的问题。从随后的讨论中可以明显看出, 这个问题直接映射到轨迹异常值检测 , 将在第11章中详细讨论。
  在多变量时间数据中, 通常使用多个传感器同时测量不同的行为属性。一个例子是 [427] 中描述的英特尔伯克利研究传感器数据, 它测量不同的行为属性随着时间推移的变化。如图 9.6(a) 和 (b) 分别说明了其中一个温度和压力传感器在同一时间段的行为。
  在这种情况下, 可以利用现有的轨迹异常点检测来检测异常值形状。尽管现有的工作是为空间轨迹而设计的, 但它也可以扩展到 x 坐标和 Y 坐标上具有任意值的非空间情况。在这种情况下, 可以通过消除公共时间属性, 或通过创建包含时间和其他两个行为属性的三维轨迹来可视化这两个行为属性的变化。图 9.6© 和 (d) 分别说明了这类轨迹的例子。图 9.6(d) 显示了所有三个属性之间的同步变化。通常, 具有 n个行为属性的多变量时间序列可以映射到 (n+1) 维轨迹。一个问题是, 当行为属性的数量增加时, 相应轨迹的维数也会增加，这就带来了维度灾难。在这种情况下, 最好探索行为属性的子集, 以确定异常值。这与第5章中讨论的子空间方法相对应。这是一个极其困难的问题, 因为它将轨迹分析与多元时间序列分析结合起来, 在文献中仍然是一个悬而未决的问题。
  TROAD 方法可以用来确定不寻常的形状轨迹, 在这种情况下。第11章第11.4 节详细介绍了这一方法。虽然该方法是为二维空间数据设计的, 但该方法的广义版本可用于包含任何类型属性的高维轨迹数据。需要注意将数据从每个属性规范化到单位方差。 这在非空间情况下尤其重要, 因为轨迹的不同轴可能绘制在非常不同的尺度上。
  9.3.2 基于距离的方法
  Hotsax 方法使用标准欧式距离来定义基于距离的异常值。此外, 它还使用离散近似进行剪枝。为了确定每个子序列的异常得分, 计算K近邻的欧式距离。为了便于剪枝, 假定只需要报告前几名异常得分。
  异常分析是在长度为 p 的窗口上进行的。这些子序列从时间序列中提取, 并确定最近的欧式距离。使用公式9.19 计算两个序列之间的欧式距离。必须注意在非重叠窗口间进行比较, 以最大限度地减少重叠窗口的自相似性偏差。 因此, 在计算 k近邻时不包括重叠窗口。因此, 该方案的基本版本 (不进行修剪) 可描述如下：

1. 从时间序列中提取长度 p 的重叠子序列。对于长度为 n 的时间序列, 可以提取总计 (n-p + 1) 子序列。
2. 将子序列的 k近邻距离作为异常得分上报，同时在计算中排除重叠窗口。

原则上, 时间序列数据还存在各种其他相似性或距离函数, 其中最突出的是动态时间扭曲(DTW)。不同类型的相似函数在不同的应用环境中可能更有效, 尽管欧式距离函数的优点是它可以有效计算并适合于剪枝。因此, 更一般的距离函数可能需要使用复杂的索引来高效检索。
接下来, 我们将讨论在欧式距离函数中使用的剪枝方法。在这种情况下, 假设我们只希望发现排名靠前的异常值 (而不是所有异常得分)。剪枝的目的是提高算法的效率。
采用嵌套循环方法实现：该算法在外部循环中迭代地检查候选子序列，对于每个候选子序列, 在一个内循环中逐步计算距离其他子序列的k 近邻。每个候选子序列要么包含在外部循环迭代结束时的当前最佳 r 异常估计集中, 要么提前退出内部循环而丢弃, 而不计算 k 近邻的确切值。当该候选子序列的当前近似 k近邻距离小于到目前为止发现的第r最佳异常得分时, 提前退出此内部循环。显然, 这个子序列不可能是一个异常值。为了获得最佳的剪枝结果, 需要对子序列进行启发式排序 , 以便在外部循环中检查的最早候选子序列具有最大的异常倾向。此外, 当子序列在内循环中排序, 以便及早发现候选子序列的 k近邻时,剪枝性能也是最有效的。
一种可以测量基础子序列的聚类行为的方法促进了剪枝。聚类分析与异常值分析有互补关系, 因此首先在外部循环中检查这些子序列是很有用的, 因为这些子序列是某个集群的成员。SAX 表示形式用于创建子序列到群集的简单映射。SAX 的分段聚合近似是在长度为w < p 的窗口上进行的。然后, 每个用于异常值分析的窗口检查长度为 p/w 的符号 (或单词) 序列. 映射到唯一单词的子序列比映射到同一个单词的子序列更有可能是异常。这是因为后一种情况对应于属于同一群集的子序列。[311] 中利用了这一观察结果以设计用于异常分析的剪枝机制。在离散的情况下, 由于不同词的数量往往是有限的, 因此可以使用字典树数据结构来保持子序列中不同单词的计数, 并识别更不寻常的单词。此外, 这些序列映射到的实际子序列集的标识也保留在该数据结构中。异常的子序列可以用低频计数的单词来识别。 这提供了一个排序方法, 在其中检查不同的候选子序列。对于每个候选子序列, 映射到同一单词的子序列可以首先计算最近邻距离, 以便在最近邻距离上提供快速而严格的上限。 由于这些距离是一个接一个计算的, 因此最近邻距离的上限越来越紧。当一个候选对象的最近邻距离的上限保证比迄今发现的第r 最佳离群距离要小 (即更相似) 时, 可以修剪候选项。 因此, 对于任何给定的序列, 不需要通过与所有子序列进行比较来确定其确切的最近邻。相反, 在计算最近邻距离时, 通常可以提前终止内部循环。这就是 [311] 中剪枝方法的核心。
SAX 表示形式用于为异常值提供一个良好的候选排序, 以及迭代计算候选的最近邻距离的排序。一个好的候选排序,确保强异常值被较早发现, 因此一个紧密的下限的异常得分也可以较早得到；一个好的计算候选的最近邻距离的排序确保迭代最近邻计算过程在特定候选的异常得分上很早就达到了一个紧密的上限。当候选的上界距离小于第r最佳异常得分的下限时, 可以提前终止候选项的处理。剪枝的有效性取决于近似的紧密程度, 而近似的紧密性又取决于基于SAX的聚类所创建的排序的质量。利用多变量距离函数将这种方法扩展到多变量时间序列相对容易。
9.3.2.1 单序列与多个序列
在某些情况下, 基于子序列的基于序列的异常需要通过同一类型的多个时间序列的数据库来检测。例如, 可能需要从几千例心电图 (ECG) 时间序列的数据库中确定异常。然而, 如果有一个非常长的时间序列, 可能需要从这个大序列中确定该序列的异常部分。单个大序列的情况与多个序列的情况差别不大, 都需要提取长度为p的子序列，从提取的序列的子序列中发现异常序列。尽管某些方法 (如 Hotsax) 在原始问题定义中假定单个长时间序列, 但另一些方法则假定多个序列。
更多序列的存在使建模过程更加稳健。此外, 如果其中一些已知为正常实例 (非异常值), 则数据建模过程应只使用正常序列以提供更干净的模型。例如, 在近邻异常检测器中, 应仅将候选序列与正常序列中的子序列进行比较。
9.3.3 概率模型
概率模型使用生成过程来建立生成一组时间序列的模型。例如, 可以从给定的时间序列中提取一组子序列, 然后对从这种混合物的成分中生成这些时间序列的过程进行建模。聚类时间序列最常见的生成模型是隐马尔可夫模型 (HMM)。HMM 可以被看作是第2章第2.4 节讨论的混合模型的模拟, 只是它允许混合物的不同成分之间的时间依赖关系, 以便在连续的时间戳上生成值。如第2章所述, 可以计算每个子序列相对于概率模型的概率拟合，具有较低拟合水平的数据点为异常值。隐马尔可夫模型通常更适合于离散序列, 尽管它们有时也用于连续数据。
9.3.4 线性模型
可以使用第3章中讨论的线性模型来发现底层时间序列中的异常形状。
9.3.4.1 单变量序列
可以从长度 n 的时间序列中反复提取长度 p 的重叠窗口, 以创建 (n-p + 1) 对象，每个长度 p 窗口都可以被视为 p 维数据点。 因此, 现在可以提取出一个大小为 (n−p+1)×p的矩阵，然后就可以在此基础上构造一个 pxp 协方差矩阵, 以进行PCA。请注意, 协方差矩阵包含有关序列在最大滞后值p的自相关性信息，与特定窗口中的正常自相关模式的偏差应被视为异常窗口。
为了实现这一目标, 可以确定这个协方差矩阵的特征向量, 以确定转换空间中的一个新的 p 维表示。这些 p 方向中的每一个都标准化为零均和单位方差。每个点与转换后的数据的 p 维均值的平方距离提供了异常得分。请注意, 这种方法是第2章2.3.4 节讨论的 Mahalanobis 方法的直接应用 (第3章3.3.1 节提供了基于PCA的解释)
如第3章第3.5 节所述, PCA 方法是矩阵分解的特殊情况，事实上，人们可以使用任何类型的矩阵分解。在这种情况下, 该方法还可用于不完全指定的时间序列中的异常检测。不完全指定的时间序列使用上述转换映射到不完全指定的多维数据集。这种类型的方法非常有用, 因为时间序列通常在许多设置中不完全指定。同样值得注意的是, 矩阵分解为矩阵中的每个条目提供了异常得分，这可以用来标记时间序列中的异常值。因此, 该方法也可用于确定异常点。但是, 此类点异常值不能在线应用, 因为特定位置的异常得分可能来自将来的时间序列。不过, 在离线分析中, 该方法仍可用于标记异常值。
9.3.4.2 多变量序列

9.3.4.3 包含任意相似函数
PCA 经常被忽略, 它所做的隐含假设是不同序列之间的距离由欧式距离表示。在实际应用中, 情况可能并不总是如此。例如, 在单变量的情况下, 可能需要使用edit距离或动态时间扭曲 (DTW)。这种距离函数可以通过使用第3章3.3.8 节中讨论的内核 PCA 方法来解决。从相似矩阵生成直接嵌入，而不是从协方差矩阵创建基系统。考虑从时间序列中提取 (n-p + 1) 多维点的设置，这些步骤如下所示：
8. 在数据点上构造一个 (n-p + 1) x (n−p + 1) 相似矩阵，在距离可用而不是相似性的情况下, 可以在这些距离上应用高斯核将距离值${\delta }_{ij}$转换为相似值$s_{ij}$，生成(n-p + 1) x (n−p + 1) 维相似矩阵S。 其中t是核宽度参数。
9. 提取该相似矩阵的所有严格正特征向量, 并将每个特征向量标准化为零均值和单位方差。这提供了每个 (n-p + 1) 对象的 k 维表示形式。在提取严格正特征向量时, 必须注意排除由于特征向量计算中的数值误差而出现正的零特征向量。一个非常小的阈值, 如特征值上的$10^{-6}$, 通常足以排除这种特征向量。
10. 在这个以均值为中心的表示中, 每个点与原点的平方距离即马氏异常得分。
对于多变量序列， 唯一的区别是距离函数需要使用多变量DTW来计算。 [33]中讨论了这样的距离函数。
9.3.4.4 利用线性模型的核方法
只要定义适当的核函数来度量对象之间的相似性，还可以应用单类支持向量机等方法。一个挑战是核需要是正半定的, 以便在转换空间中存在有效的嵌入。然而, 在启发式水平上, 通常可以使用不满足正半定属性的相似函数来获得相当好的结果 (见3.3.8.3 节)。
核方法通常与线性模型相结合, 因为转换空间中的线性模型对应于原始空间中的复杂边界。单类支持向量机 (参见第3章第3.4 节) 就是这种线性模型的一个例子。另一个例子是对任意数据类型使用核PCA方法, 如3.3.8.3 部分所述。
9.3.5 查找异常时间序列形状的有监督方法
在许多医学应用中, 特征病理特性可能会被底层时间序列的异常形状所捕捉。在这种情况下, 往往可以获得关于正常或病理行为的训练数据, 或两者兼而有之。因此, 这种方法要求以有监督的方式检测时间序列中的异常形状。标签可以与整个时间序列相关联, 或者与时间序列的某些部分 (子序列) 相关联。在这种情况下, 最简单的方法是为正常类和异常类develop子序列profile。对于给定的测试子序列, 可以使用k近邻方法进行分类。查询和分类数据流的方法可以在[171]。
特征提取和转换是时间序列分类的所有监督方法的核心。如果时间序列以判别特征的形式表示, 那么对它进行分类就容易多了。一种可能是将序列转换为离散表示, 然后使用第10章的隐马尔可夫模型 (HMM) 进行分类。由于在离散数据的背景下开发基于模式的分类模型很容易, 因此可用于序列分类的模型数量要大得多。[408, 590] 中提出的第二种可能性是从数据中挖掘形状, 这些是高度区分性的特征。虽然其中许多方法都是为泛型时间序列分类而提出的, 但它们通常可以推广到类不平衡的情况下。
9.4 多维流异常检测
前面几节讨论了这种情况, 即异常值是从时间序列中根据与预期值的偏差或不寻常的形状确定的。即使有多个相关的时间序列可用, 每个时间序列都会作为一个分析单元进行处理。在传统的时间序列分析中, 由于对时间连续性的强烈假设, 自相关在预测和异常计算过程中具有极其重要的意义。
另一方面, 在多维数据的情况下, 每个记录都是不可分割的d维。此外, 在单个序列中观察到非常高的时间连续性。多维数据流的情况不一定如此, 因为在多维数据流中, 时间连续性要弱得多。例如, 在多维文本记录流中, 无法从其前面的记录可靠地预测文本记录中属性的单个频率。另一方面, 可以将文档中存在的单词与流的历史记录进行聚合结果水平的比较, 以便预测异常值。因此, 多维数据流中的异常分析与 (可能是多变量) 时间序列数据中的异常值分析有很大差异, 因为时间连续性预期水平存在差异。 多维流场景更接近于传统的多维异常分析方法。唯一的区别是增加了一个时间分量, 尽管这个时间分量比时间序列数据要弱得多。在多维数据流的背景下, 效率是一个核心问题, 因为需要迅速发现异常值。多维数据流中可能会出现两种类型的异常值：

• 一种是基于对单个记录的异常值检测。例如, 关于特定主题的第一个新闻故事表示此类型的异常值。这样的异常值也被称为新奇点, 因为以前没有见过。

• 第二是基于多维数据总体趋势的变化。例如, 恐怖袭击等不寻常事件可能导致就某一特定话题爆发新闻报道。这实质上表示基于特定时间窗口的更高水平的聚合异常值。第二种类型的更改点几乎总是从第一种类型的单个异常值开始。但是, 第一种类型的单个异常值可能不发展成为聚合变化点。
  将在本节中讨论这两种类型的异常值及从多维数据流中检测稀有和新颖类的监督方法。
  9.4.1 单个点异常值
  作为异常值的单个数据点检测问题与无监督新颖性检测问题密切相关, 特别是在使用整个数据流历史记录时。在第一个异常故事检测中, 这个问题在文本领域得到了广泛的研究。这样的新奇往往是潮流的引领者, 最终可能成为正常数据的一部分。但是, 当单个记录在数据点窗口的上下文中被声明为异常值时, 这可能不一定对应于一个新颖性。
  9.4.1 Proximity-Based Algorithms
  [60] 中提出了一种基于距离的异常值检测方法，其中数据点的异常得分是根据其与长度为 w 的时间窗口中的数据点的K近邻距离来定义的。 [60] 中的工作提出了基于距离的异常检测的 STORM 算法。当数据点的整个窗口可以在主内存中维护时, 就很容易确定异常值,但很多时候, 可能无法在主内存中保存数据点的整个窗口。在这种情况方案更具挑战性 , 因为很难为基于距离的剪枝创建高效索引。对于这种情况, 返回近似异常值。值得注意的是, 由于方差缩小效应, 前一个窗口的子样本的平均集成得分通常比精确的异常得分更有效。关于集成方法的第6章详细讨论了这一效果。
  LOF 算法也已扩展到增量方案。此外, 该方法还可以处理数据点的插入和删除。在插入过程中执行两个步骤：

• 相对于现有的 LOF 模型计算新插入的数据点的统计信息。

• 现有的 LOF 模型根据密度、可达距离和基础数据点的异常程度进行更新。换句话说, 许多现有数据点的参数需要更新, 因为它们受到新增数据点的影响。但是, 并非所有点都需要更新, 因为只有新数据点的位置会受到影响。[443] 中的工作以明智的方式执行这些更新, 以便有效地确定异常值。
  基于距离的方法计算成本很高，因此采用基于聚类的方法大大提高异常值检测过程的复杂性。
  当大量数据点可用时, 基于群集的方法尤其有效。在数据流的上下文中, 通常有足够数量的数据点可用, 以便将群集保持在非常高的粒度水平。在流聚类算法的背景下, 新聚类的形成往往与无监督的新颖性联系在一起。当然, 当整个流的历史记录没有反映在当前群集集提供的有限空间summary中时, 情况可能并不总是如此。例如, 当传入的数据点不在数据中现有群集的指定统计半径范围内时, [28] 中的工作明确地规范数据流中新群集的创建。此类数据点可被视为异常值。在许多情况下, 这是一个新趋势的开始, 在算法的后期阶段会向集群中添加更多的数据点；在某些情况下, 这类数据点可能与新颖性相对应；在其他情况下, 这类点可能与很久以前看到的趋势相对应, 但不再反映在集群中，无论哪种情况, 此类数据点都是异常值。但是, 不可能区分这些不同类型的异常值, 除非愿意允许流中的群集数量随着时间的推移而增加。[322] 中的工作利用 [28] 中讨论的聚类分析过程来提高异常分析过程的效率。
  这种方法也被推广到文本数据，用来从一个可能的新趋势更多的故事的主题检测第一个故事。请参考第8章关于如何将这种基于近似值的方法应用于文本流中的一篇文章检测的讨论。这些方法还可以与基于窗口的策略相结合, 以便通过对数据流的特定块执行聚类来检测异常值。
  9.4.1.2 概率算法
  上面讨论的聚类方法也可以在概率学习算法的上下文中使用。正如第2章所讨论的, 在有限数据的情况下, 概率学习算法通常是不可取的。然而, 在数据流的上下文中, 可用于学习的数据量要大得多，只要学习算法能够有效地实现，就不是什么问题。[578] 提出了从混合属性数据集中创建混合模型的方法。这样做的目的是计算数据点添加到模型前后，传入数据点与模型的拟合。这是通过使用EM算法来实现的。
  EM 算法由于其对优化过程的迭代方法适合流式计算。随着新数据点的到来, 使用这些数据点调整参数相对容易。
  9.4.1.3高维场景
  9.4.2 聚合更改点作为异常值
  文献中提出了许多方法来确定多维数据流中的重大变化点。基础数据中局部和全局聚合趋势的突变通常表明数据中出现了异常事件。许多方法还提供了量化基础数据流中变化水平的统计方法。因此, 我们将讨论一些重要的更改检测方法, 这些方法也可用于异常值检测。
  9.4.2.1 速度密度估计方法

9.4.2.2 聚合分布的重大统计变化

描述多维数据流中的聚合变化的另一种方法是估计这些时间窗口中的聚合分布。 这些时间窗口中的重大更改可以作为数据流中的异常点。我们注意到, 速度密度法也使用核密度估计来估计聚合分布，但是在变化检测的背景下, 有时能够直接对基础分布进行统计检验以确定重大的变化点。
[315] 提出了一个用于数据流中的更改检测的非参数框架。这项工作的关键贡献是定义了两个概率分布之间的距离。 为了确定显著的变化点, 使用了威尔科克森和科尔莫戈罗夫-斯米尔诺夫检测的泛化。但是, 这项工作只讨论了一维数据流的情况，未说明对更高维的泛化。
[159] 可以有效地处理多维数据流。此外, 还可以应用于不同的数据类型, 因为问题的计算方面不同于基础数据的类型。由于变化检测本质上与分布之间距离相关, 表示这种距离的一种普遍方法是信息论中的相对熵。即 Kullaber-leibler (或 KL) 距离。
广泛的原则如下：给定一组适于一系列分布的数据, 最大似然估计是最大限度地减少到真实分布的KL距离。 这是许多其他类型的变化分析的普遍形式。例如, t 检验相当于两个正态分布之间的KL距离。KL距离直观可解释, 因此特别适合异常检测。KL距离也与维度或数据类型无关。
9.4.3 多维数据流中的稀有类检测与新类检测
当有监督以指导时间异常检测过程，类标签附加到各个数据点。它们可能对应于新颖的类异常值、稀有类异常值或不经常重复的类异常值。因此, 可能需要组合概念漂移分析、异常值检测和稀疏类检测的方法来确定流的异常值。在入侵检测中经常会出现这样的情况：一些已知的入侵可能被标记, 但随着时间的推移, 也可能会出现新的入侵。因此, 使用监督与非监督相结合的异常检测算法方法至关重要。
在这种情况下, 不同类型的异常值如下所示：

• 稀有类异常值: 此类异常值的识别与静态监督方案类似, 只是需要在流式传输设置中更有效地执行。在这种情况下, 一小部分记录可能属于一个罕见的类别, 但从时间的角度来看, 它们不一定以非均匀的方式分布。
• 新奇类异常值: 在数据流的早期没有遇到这些类，因此它们可能根本没有反映在训练模型中。最终, 随着时间的推移, 此类可能会成为数据的正常部分。此场景在某种程度上类似于静态方案中的半监督异常值检测, 尽管添加时间成分带来了许多与之相关的挑战。
• 非频繁出现的类异常值: 这些类已经有一段时间没有遇到过, 但可能会重新出现在流中。该类不同于第一类异常值, 因为它们是在短暂的时间内罕见爆发。由于大部分数据流分类算法使用某种形式的discounting来解决概念漂移, 它们可能会遗忘旧类信息。如果不频繁出现的类没有反映在训练模型中, 则无法识别这些类。因此, 模型更新和discounting问题非常重要。
  我们将在下面讨论上述每个案例。
  9.4.3.1 稀有类检测
  9.4.3.2 新奇类检测
  9.4.3.3 非频繁出现类检测
  9.5 结论和小结
  本章研究了流式时间序列数据和多维数据流中的异常点检测问题。在这两种情况下, 异常值的性质差别很大, 因为时间序列数据需要将每个序列作为一个单元进行分析, 而多维数据则需要将每个多维点作为一个单元进行分析。 还可以在时间序列数据中定义不同类型的异常值, 具体取决于是需要识别序列中的偏离点, 还是需要识别异常形状子序列。对于多维数据, 单个数据点可以归类为新奇点, 数据中的聚合变化点可以定义为异常值。在标签可用的情况下, 可以将监督和无监督的方法结合起来进行新奇点和稀有类检测。因此, 时间异常值检测领域提供了各种各样不同的问题定义。
  9.6 Bibliographic Survey
  在传统时间序列数据分析, 特别是从基础数据去除噪声的角度, 对异常值检测进行了广泛的研究。大部分工作都集中在消除噪声和平滑时间时间序列, 以促进更准确的回归和预测。在这种情况下, 异常值被定义为与预测值的偏差。关于时间数据中异常检测的详情间 [231, 232] 。
  时间序列趋势的重大变化可以诊断为数据变化点和异常值。这包括许多传统的回归建模方法, 如自回归建模 (AR)、自回归移动平均 (ARMA) 和自回归集成移动平均模型 (ARIMA)。为了跟踪多个流之间的相关性, 通常使用主成分分析等方法。预测过程的鲁棒性有助于精确的异常值检测。许多方法可以加快大量数据流和实时数据的回归建模。[284] 中提出了一种确定时间序列异常点的信息理论方法, 将异常值定义为时间序列中的一个点, 其去除后可获得更好的直方图表示。 在时间序列中, 监督方法可用于对不同类型的偏差和异常值进行判别分析。
  时间序列异常检测通常被理解为实时变化检测和偏差, 而在时间序列中查找异常形状的问题则是完全不同的情况。前者与极值分析有关, 而后者需要在数据的不同窗口上仔细分析序列中的规律性。[157] 提出了利用免疫学思想检测时间序列异常：偏差的总体大小比总体时间序列的形状重要性低。
  为了计算不寻常的形状, 可以使用多种方法。[205] 中探讨了 Haar 变换在时间序列中的应用。最常见的方法 [311] 是在时间序列的固定窗口上使用欧几里得距离。使用符号聚合近似可以进一步加速解决这个问题。 这些方法已进行了扩展可处理TB级别数据集。[76] 提出的方法是确定时间序列数据的异常制度, 其中不同时间序列之间的相关性和依赖关系随着时间的推移而发生变化。
  第10章讨论了在离散序列中查找异常的方法。离散案例的详情见 [126] ，离散数据和连续数据的综合视角可以在 [231, 232] 中找到。文献中还提出了一些对异常形状检测进行半监督和有监督的方法。在半监督方案中, 假定有正常时间序列的示例可用。在有监督的方案中, 正常形状和异常形状的示例都需要有。向离散的转换还允许使用基于有监督基于字符串的模型, 如隐马尔可夫模型 (HMM) 。其他转换方法如特征转换方法在基础时间序列上构造相关的形状。这些模式可以区分不同类别的实例。另一种众所周知的方法是使用距离函数, 如动态时间扭曲 [289]。
  多变量时间数据也可以表示为轨迹。在许多应用中, 如飓风跟踪 [117], 轨迹方向的重大变化都很有用。在这种情况下, 轨迹可以被视为双变量时间数据, 基于预测的偏差检测技术可以应用于这种表示形式。[102, 215] 通过检查演化模式来实时确定运动物体流的异常。另一方面, 异常轨迹形状的检测是一个完全不同的问题。一种方法通过使用一组描述轨迹元信息的要素, 将轨迹转化为点数据。[409, 347] 研究了无监督轨迹异常值检测方法**, 这些方法实际上明确地使用了序列信息** 。[409] 使用傅立叶变换来表示主导系数的轨迹并发现异常。[347]中，轨迹被划分为不同的线段, 并确定异常模式, 以确定异常值。[355] 使用有监督方法。这些方法将数据转换为离散序列, 并训练分类器, 以便将轨迹与类标签相关联。
  传感器数据流是异常检测在时间数据中最常见的应用之一。由于数据收集和传输过程中的错误和偏差, 传感器数据也会出现噪声。因此, 异常值检测包括消除底层噪声和检测传感器流中的异常。监督学习有时可以用来区分噪声和异常。由于涉及大量数据, 一些独特的技术问题会浮现。因此, 为了最大限度地减少延迟和通信成本实时和在线处理非常重要。
  针对不同类型的多维数据和文本数据，研究了多维数据流中的异常检测问题。[476] 提出了一种称为 RS-Hash 的子空间直方图技术 (参见第5章5.2.5 节)。此技术平均不同大小和形状的网格区域中的log-density, 以便提供最终分数。该方法使用随机哈希来提高效率, 并且需要线性时间。该方法适用于高维数据中的子空间异常值检测, 效率显著。新奇点检测问题也与流场景中的聚类密切相关, 许多技术使用聚类分析或基于距离的方法来检测新奇点。 例如, [322] 使用流聚类算法提高异常分析效率。[414] 使用数据编辑技术, 逐步删除距离最近的数据点。这减少了数据的大小, 同时保留了某些理想的属性来检测异常值。

数据流中聚合变化的确定是另一种类型的多维异常值检测 [193]。 这就需要确定多维数据的聚合分布是否发生了显著的变化。 [19] 描述速度密度等高线形式变化的方法。使用不同形式的统计检验进行变化检测的其他方法, 如KL距离、Wilcoxon 和 Komomoorov-smirnoff 检验, 可以在 [159, 315] 中找到。其他一些统计方法 [333, 504] 使用对数似然标准来量化变化。[267] 提出了用于数据流中的变化检测的马丁格尔框架。这种变化点对于确定股票市场订单分布 [372] 或时间网络流量数据流 [334、335、372] 中的异常非常有用。
关于半监督的新奇点检测的传统方法的详见[388, 389]。[379] 利用支持向量回归模型进行在线新奇点检测。通过使用类标签, 可以提高新奇点检测的有效性。[46, 391, 391] 中提出了流分类和聚类模型的组合, 用于区分正常类、新奇类、稀有类和很少重复的类。