使用sklearn进行异常检测

sklearn提供了一些机器学习方法,可用于奇异(Novelty)点或异常(Outlier)点检测,包括OneClassSVM、Isolation Forest、Local Outlier Factor (LOF) 等。其中OneClassSVM可用于Novelty Detection,而后两者可用于Outlier Detection。

  • novelty detection:当训练数据中没有离群点,我们的目标是用训练好的模型去检测另外新发现的样本
  • outlier detection:当训练数据中包含离群点,模型训练时要匹配训练数据的中心样本,忽视训练样本中的其它异常点

OneClassSVM

OneClass SVM 是一個非监督学习的算法,顾名思义训练数据只有一个分类。透过这些正常样本的特征取学习一个决策边界,再透过这个边界去判别新的数据是否与训练数据类似。超出边界即视为异常。

OneClass SVM的训练集不应该掺杂异常点,因为模型可能会去匹配这些异常点。但在数据维度很高,或者对相关数据分布没有任何假设的情况下,OneClassSVM也可以作为一种很好的outlier detection方法。在one-class classification中,仅仅只有一类的信息是可以用于训练,其他类别的(总称outlier)信息是缺失的,也就是区分两个类别的边界线是通过仅有的一类数据的信息学习得到的。

那么没有类别标签,我们如何寻找划分的超平面以及寻找支持向量呢?One Class SVM这个问题的解决思路有很多。这里只讲解一种特别的思路SVDD, 对于SVDD来说,我们期望所有不是异常的样本都是正类别,同时它采用一个超球体而不是一个超平面来做划分,该算法在特征空间中获得数据周围的球形边界,期望最小化这个超球体的体积,从而最小化异常点数据的影响。

假设产生的超球体参数为中心o和对应的超球体半径 r>0 ,超球体体积 V(r) 被最小化,中心o 是支持向量的线性组合;跟传统SVM方法相似,可以要求所有训练数据点$x_i$到中心的距离严格小于 r,但同时构造一个惩罚系数为 C 的松弛变量$\xi_i $,优化问题如下所示:

$$\underbrace{min}_{r,o}V(r) + C\sum\limits_{i=1}^m\xi_i$$

$$||x_i-o||_2 \leq r + \xi_i,\;\; i=1,2,…m$$

$$\xi_i \geq 0,\;\;i=1,2,…m$$

和之前讲的支持向量机类似的求解方法,在采用拉格朗日对偶求解之后,可以判断新的数据点 z 是否在类内,如果z到中心的距离小于或者等于半径r,则不是异常点,如果在超球体以外,则是异常点。

在sklearn中,我们可以用svm包里面的OneClassSVM来做异常点检测。OneClassSVM也支持核函数,所以普通SVM里面的调参思路在这里也适用。

代码示例:

参考链接:

Isolation Forest(隔离森林)

Isolation Forest(以下简称iForest)主要是利用集成学习的思路来做异常点检测,目前几乎成为异常点检测算法的首选项。iForest适用于连续数据(Continuous numerical data)的异常检测,将异常定义为“容易被孤立的离群点(more  likely to be separated)可以理解为分布稀疏且离密度高的群体较远的点。用统计学来解释,在数据空间里面,分布稀疏的区域表示数据发生在此区域的概率很低,因此可以认为落在这些区域里的数据是异常的。通常用于网络安全中的攻击检测和流量异常等分析,金融机构则用于挖掘出欺诈行为。对于找出的异常数据,然后要么直接清除异常数据,如数据清理中的去噪数据,要么深入分析异常数据,比如分析攻击,欺诈的行为特征。

算法本身并不复杂,主要包括第一步训练构建随机森林对应的多颗决策树,这些决策树一般叫iTree,第二步计算需要检测的数据点x最终落在任意第t颗iTree的层数ht(x)。然后我们可以得出x在每棵树的高度平均值h(x)。第三步根据h(x)判断x是否是异常点。

  • 第一步构建决策树的过程,方法和普通的随机森林不同。首先采样决策树的训练样本时,普通的随机森林要采样的样本个数等于训练集个数。但是iForest不需要采样这么多,一般来说,采样个数要远远小于训练集个数。原因是我们的目的是异常点检测,只需要部分的样本我们一般就可以将异常点区别出来了。另外就是在做决策树分裂决策时,由于我们没有标记输出,所以没法计算基尼系数或者和方差之类的划分标准。这里我们使用的是随机选择划分特征,然后在基于这个特征再随机选择划分阈值,进行决策树的分裂。直到树的深度达到限定阈值或者样本数只剩一个。
  • 第二步计算要检测的样本点在每棵树的高度平均值h(x)。首先需要遍历每一颗iTree,得到检测的数据点x最终落在任意第t颗iTree的数层数$h_t(x)$。这个$h_t(x)$代表的是树的深度,也就是离根节点越近,则$h_t(x)$越小,越靠近底层,则$h_t(x)$越大,根节点的高度为
  • 第三步是据h(x)判断x是否是异常点。我们一般用下面的公式计算x的异常概率分值:$s(x,m) = 2^{-\frac{h(x)}{c(m)}}$,s(x,m)的取值范围是[0,1],取值越接近于1,则是异常点的概率也越大。其中,m为样本个数。的表达式为:$c(m) =2\ln(m-1) + \xi – 2\frac{m-1}{m}$,$\xi$是欧拉常数。

从$s(x,m)$表示式可以看出,如果高度$h(x) \to 0$, 则$s(x,m) \to 1$,即是异常点的概率是100%,如果高度$h(x) \to m-1$, 则$s(x,m) \to 0$,即不可能是异常点。如果高度$h(x) \to c(m)$, 则$s(x,m) \to 0.5$,即是异常点的概率是50%,一般我们可以设置$s(x,m)$的一个阈值然后去调参,这样大于阈值的才认为是异常点。

在sklearn中,我们可以用ensemble包里面的IsolationForest来做异常点检测。

示例代码:

IForest目前是异常点检测最常用的算法之一,它的优点非常突出,它具有线性时间复杂度。

  • iForest具有线性时间复杂度,因为是ensemble的方法,所以可以用在含有海量数据的数据集上面,通常树的数量越多,算法越稳定。由于每棵树都是相互独立生成的,因此可以部署在大规模分布式系统上来加速运算。
  • iForest不适用于特别高维的数据。由于每次切数据空间都是随机选取一个维度,建完树后仍然有大量的维度信息没有被使用,导致算法可靠性降低。高维空间还可能存在大量噪音维度或者无关维度(irrelevant attributes),影响树的构建。对这类数据,建议使用子空间异常检测(Subspace Anomaly  Detection)技术。此外,切割平面默认是axis-parallel的,也可以随机生成各种角度的切割平面。
  • IForest仅对Global Anomaly敏感,即全局稀疏点敏感,不擅长处理局部的相对稀疏点(Local Anomaly)。
  • iForest推动了重心估计(Mass Estimation)理论,目前在分类聚类和异常检测中都取得显著效果。

参考链接:

Local Outlier Factor(局部离群因子)

Local Outlier Factor(LOF)是基于密度的经典算法(Breuning et. al. 2000)。在 LOF 之前的异常检测算法大多是基于统计方法的,或者是借用了一些聚类算法用于异常点的识别(比如 ,DBSCAN,OPTICS)。但是,基于统计的异常检测算法通常需要假设数据服从特定的概率分布,这个假设往往是不成立的。而聚类的方法通常只能给出 0/1 的判断(即:是不是异常点),不能量化每个数据点的异常程度。相比较而言,基于密度的LOF算法要更简单、直观。它不需要对数据的分布做太多要求,还能量化每个数据点的异常程度(outlierness)。

LOF算法是一种无监督的异常检测方法,它计算给定数据点相对于其邻居的局部密度偏差。每个样本的异常分数称为局部异常因子。异常分数是局部的,取决于样本相对于周围邻域的隔离程度。确切地说,局部性由k近邻给出,并使用距离估计局部密度。通过将样本的局部密度与其邻居的局部密度进行比较,可以识别密度明显低于其邻居的样本,,这些样本就被当做是异常样本点。

算法原理如下:

  • 计算k-distance of p:计算点p的第k距离,也就距离样本点p第k远的点的距离,不包括p;
  • 计算k-distance neighborhood of p:计算点p的第k邻域距离,就是p的第k距离以内的所有点,包括第k距离;
  • 计算reach-distance:可达距离,若小于第k距离,则可达距离为第k距离,若大于第k距离,则可达距离为真实距离,公式如下(说明:d(p,o)为p到o的距离):$reach-distance_k(p,o)=max\{k-istance(o),d(p,o)\$。点o到点p的第k可达距离,至少是点o的第k距离,或者为o与p间的真实距离。
  • 计算local reachability density:局部可达密度。$d_k(p)=\frac{1}{ \frac{1}{|Nk(p)|} \sum _{o \in Nk(p)}reach-istance_k(p,o)}$。表示点p的第k邻域内点到点p的平均可达距离的倒数。
  • 计算local outlier factor:局部离群因子。$F_k(p)=\frac{1}{ |Nk(p)|} ∑_{o\in Nk(p)} \frac{lrd_k(o) }{lrd_k(p)} = \frac{∑ _{o\in Nk(p)} lrd_k(o)}{|Nk(p)| } \cdot \frac{1}{lrd_k(p)}$ 。表示点p的邻域点Nk(p)的局部可达密度与点p的局部可达密度之比的平均数。

示例代码:

参考链接:

Fitting an elliptic envelope(椭圆模型拟合)

实现异常值检测的一种常见方式是假设内围数据来自已知分布(例如,数据服从高斯分布)。 从这个假设来看,我们通常试图定义数据的 “形状”,并且可以将异常观测定义为足够远离拟合形状的观测。

scikit-learn 提供了covariance.EllipticEnvelope对象,它能拟合出数据的稳健协方差估计,从而为中心数据点拟合出一个椭圆,忽略中心模式之外的点。例如,假设内围数据服从高斯分布,它将稳健地(即不受异常值的影响)估计内围位置和协方差。 从该估计得到的马氏距离用于得出异常度量。 该策略如下图所示:

示例代码:

参考链接:

异常检测算法比较

示例代码:

参考链接:https://scikit-learn.org/stable/modules/outlier_detection.html

微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

分层时间记忆HTM学习笔记

分层时间记忆算法(Hierarchical Temporal Memory),全称HTM Cortical L

Expedia异常检测项目Adaptive Alerting

Adaptive Alerting(AA)是Expedia开源的异常检测项目,整个项目也是完整一套监控体系,包

格兰杰因果关系检验学习笔记

格兰杰因果关系检验简介 格兰杰因果关系检验(英语:Granger causality test)是一种假设检定

发表评论

电子邮件地址不会被公开。 必填项已用*标注