通常时序数据的异常值主要分为三类:
,其中观测值
,与该时间序列的期望值(即
)不同。
,异常时间序列
是在X 上与大多数时间序列值不一致的部分
时序数据常见特征
用于建模实验的常见指标,衡量模型好坏
主要分为三大类:
基于数据,构建一个概率分布模型,得出模 型的概率密度函数。通常,异常点的概率是很低的。
假设数据集由一个正态分布产生,该分布用
表示(如图 11 -1 所示),其中,
和
分别表示均值和标准差 。 数据落在士3 个
之外的区域的概率仅有 0.27%,落在±4 个也
之外的 区域的概率仅有 001%,几乎不可能发生,故将其判定为异常点 。 可以看出,异常点的判定与 我们所选定的标准(几个
)有关,不是固定的。
对于多元高斯分布检测,我们希望使用类似于一元高斯分布的方法。 例如,如果点关于估计的数据具有低概率,那么就把它们分类为异常点。
实际上马氏距离也是统计算法,点到基础分布的Mahalanobis距离与点的概率直接相关
综上所述,两种基于统计模型的异常点检测方法,需要建立在标准的统计学技术(如分布 参数的估计)之上。这类方法对于低维数据效果可能较好,但是对于高维数据,数据分布非常 复杂,基于统计模型的检测效果会比较差。
对于一个多维数据集D,假设至是均值向量,那么对于数据集D 中的其他对象x ,从x
到数据均值(质心)的 Mahalanobis 距离(马氏距离)为:
其中,x 为数据集D 中的元素,Z为数据均值,S为协方差矩阵。
容易证明: 点到基础分布的Mahalanobis距离与点的概率直接相关,等于点的概率密度的对数加上一个常数。因此,可以对Mahalanobis距离进行排序,距离大的,就可以认为是异常点。
KNN 算法是基于邻近度的算法, 不需要对数据集进行统计模型的拟合,可以直接用距离来识别异常点。但是,这种基于距离的算法也有其明显的缺点:①时间复杂度为
, 这意味着如果数据量比较大,会导致计算代价过高,效率低下:②对k 值的选取非常敏感, 并且k 值的选取是全局的,不能处理具有不同密度区域的数据集。
从基于密度的观点来说,异常点是低密度区域中的对象。
定义密度的方法有以下三种。
一个对象的密度为该对象周围k个最近邻的平均距离的倒数。
其中,
是x的k个最近邻的集合,
是该集合的大小 。
即一个对象周围的密度等于该对象指定半径 d 内对象的个数。d是人为选择的,那么这个d的选择就很重要了。
即用点 x 的密度与它最近邻 y 的平均密度之比作为相对密度。
其中,
是x的k个最近邻的集合,n是该集合的大小 。
首先,要理解独立森林,就必须了解什么是独立树,下文简称 iTree 。 iTree 是一种随机二 叉树,每个节点要么有两个子节点(称为左子树和右子树),要么没有子节点(称为叶子节点)。 给定数据集D,这里 D 的所有属性都是连续型变量, iTree 的构成如下:
iTree 构造完成后,接下来对数据进行预测。预测的过程就是把测试记录从 iTree 根结点开始搜索,确定测试记录落在哪个叶子节点上。 iTree 能检测异常的假设是:异常点一般都是非常稀有的,在 iTree 中很快会被分到叶子节点上。也就是说,在 iTree 中,异常值一般表现为叶子 节点到根节点的路径 h(x)很短。因此,可以用 h(x)来判断一条记录是否属于异常值。
再定义一个关于h(x)的异常指数,
就是记录 x 在由 n 个样本的训练数据构成的 iForest 的异常值得分:
其中, n 为样本的大小, h(x)为记录 x 在 iTree 上的高度,
表 示记录x 在每棵树的高度均值,。
的取值范围为
,越接近 1 表示是异常点的可能性越高,越接近 0 表示是正常点的可能性越高,如果大部分训练样本的
都接近0.5 ,则说明整个数据集没有明显的异常值。
实现中还有注意的点:
综上所述,独立森林本质上是一种非监督算法,不需要先验的类标签。在处理高维数据时,不是把所有的属性都用上,而是通过峰度系数(峰度小,长尾太长了,比较难判断异常;峰度大,则大部分数据集中,方便判断)挑选一些有价值的属性,然后再进行 iForest 的构造,算法效果会更好。
颜色越深代表异常值得分越高, 颜色越浅代表异常值得分越低。可以看出,模型预测效果不错,颜色分布规律与 test 和 outlier 数据集完全吻合。
常见的开源的异常监测系统
EGADS是 Yahoo 公司开发的一个灵活的、准确的、可扩展的异常检测综合系统。 EGADS 框架与异常检测基准数据一起开源 (https://github.corn/yahoo/egads)