深入机器学习系列——异常检测(Anomaly Detection)

2018年10月23日14:24:55数据结构与算法深入机器学习系列——异常检测(Anomaly Detection)已关闭评论22,460 views1字数 2706阅读模式
异常检测(Anomaly Detection), 它是机器学习的一个重要分支,实际应用领域广泛,更与我们的生活息息相关。那么什么是异常检测?其主要方法和目前所面临的技术难题有哪些?本文或许能提供一些参考。
定义
  • 异常值

霍金斯的定义为:“异常值是一个与其他观察结果有很大差异的观察结果, 以此引起人们怀疑它是由不同 的机制产生的”。

  • 异常检测

所谓异常检测就是发现与大部分对象不同的对象,也就是发现离群点。一般规定数据具有“正常”模型,而异常被认为是与这个正常模型的偏差。在实际应用中对异常的定义也是特定的。

深入机器学习系列——异常检测(Anomaly Detection)
应用领域
  • 网络入侵检测
  • 保险/信用卡诈骗检测
  • 保健信息获取/医疗诊断
  • 产业损坏检测
  • 图像处理/视频监控
主要挑战
  • 很难定义具有代表性的“正常”区域
  • 正常行为与异常行为之间的界限往往并不明确
  • 不同的应用领域对异常值的确切定义不同
  • 难以获取用于训练/验证的标记数据
  • 数据可能含有噪声
  • 正常行为并不是一成不变的,会不断发展变化
异常检测方法
一、 图形方法:箱型图二、 统计方法:单变量/多变量高斯分布三、 基于距离的方法

四、 基于密度的方法:LOF

五、 基于模型的方法:孤立森林、RNN

一、图形方法:箱型图
  • 方框的底部和顶部分别为Q1(下四分位数)和Q3(上四分位数)
  • 方框内的线段为第二四分位数(中位数)
  • 大于下四分位数+1.5IQR或小于上四分位数-1.5IQR的值为异常值(四分位距IQR=Q3-Q1)
深入机器学习系列——异常检测(Anomaly Detection)
 二、统计方法:单变量/多变量高斯分布
总体思想

  • 已知某种统计分布(如高斯分布)
  • 假设所有数据点都由该分布生成(如平均值和标准差),进行参数计算
  • 异常值是整体分布产生概率较低的点

基本假设

  • 正常数据点遵循(已知的)分布且出现在该模型的高概率区域中
  • 异常值偏离这种分布

1、单变量高斯分布

(1) 选出可能表示异常实例的特征xj

(2) 与参数u1, …, un, σ12,…, σn2拟合

深入机器学习系列——异常检测(Anomaly Detection)
(3) 已知新实例x,计算出p(x)
深入机器学习系列——异常检测(Anomaly Detection)
(4) 若 p(x) < ε,则该数据为异常值
深入机器学习系列——异常检测(Anomaly Detection)
2. 多变量高斯分布
深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
3. 问题

  • 平均值和标准偏差对异常值非常敏感。
  • 这些值是针对完整数据集(包括潜在异常值)而计算的。
  • 很难选择恰当的ε值。
  • 数据分布未知。
三、基于距离的方法:k近邻算法
总体思想

  • 根据与相邻点的距离来判断一个点是否为异常

基本假设

  • 正常数据点具有密集的邻域
  • 异常值则远离其相邻点,即具有较为稀疏的邻域

实施方法

  • 计算每对数据点间的距离

定义异常值的几种方法

  • 在给定距离D之内相邻点少于p的点为异常值
  • 与第k个相邻点的距离最大的前n个点为异常值
  • 与k个最邻近点的平均距离最大的数据点为异常值

问题

  • 该假设不一定适用于所有情况。
  • 计算每对数据之间的距离花费较大。
  • 维数灾难问题,即随着维数的增加,计算量呈指数倍增长。
深入机器学习系列——异常检测(Anomaly Detection)
四、基于密度的方法:局部异常因子(LOF)
总体思想

  • 将某一点周围的密度与其局部相邻点周围的密度进行比较
  • 该点与其邻相邻点的相对密度计为异常得分

基本假设

  • 正常数据点的密度与其近邻的密度相近
  • 异常点的密度与其近邻的密度相差较大

1. 对于点p的第k距离

点p的第k距离(k为任意正整数),表示为k-distance(p),其定义为点p到点o∈ D的 距离d(p,o),使得:

(1) 在集合中至少有不包括p在内的k个点o’∈D满足d(p,o,)≤d(p,o) 且

(2) 在集合中最多有不包括p在内的k−1个点o’∈D,满足d(p,o,)<d(p,o)

点p的第k距离邻域Nk(p),就包含了距点p的距离不大于第k距离所有点,即Nk-distance(p)(p) = { q ∈D \ {p} | d(p, q) ≤ k-distance(p)}。

这些点就称为p的k个最近邻点。

 

2. 点p关于点o的可达距离

设k为一个自然数,点p关于点o的可达距离定义为:

reach-distk(p, o) = max { k-distance(o), d(p, o) }

深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
3. 异常得分的分布
深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
观察可知,大多数情况下,判断数据点是否异常的异常得分最佳阈值大约为2。
4. 步骤总结

  • 计算每个点与数据集中其他点之间的(欧几里德)距离。O(n2)
  • 将所得距离排序。O(nlogn)(最近邻问题)
  • 计算每个点的可达距离。
  • 计算每个点的局部可达密度。
  • 计算每个点的局部异常因子。

5. Spark-LOF可视化

深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
6. 问题

  • 运行时间呈指数增长
  • 维度灾难
五、基于模型的方法:孤立森林、RNN
1. 孤立森林(Isolation Forest)大多数现有的异常检测方法首先构建出正常数据的定义,然后将为不符合该定义的识别为异常。这些异常检测功能通常只是某些算法的“附带效果”或副产品,这些算法原本是为异常检测以外的目的而设的(如分类或聚类)。这导致了以下两方面的缺陷:

(i) 这些方法不针对检测异常进行优化,因此,它们的性能通常不尽人意,可能会触发过多错误警报(将正常值检测为异常),也可能检测灵敏性低,遗漏一些异常;

(ii) 由于其原始算法的遗留,许多现有方法受限于低维数据和较小的数据量。

(1) 假设

孤立森林通过孤立实例来检测异常,并不依赖于任何距离或密度度量。

i)检测对象是少数包含几个实例的数据集

ii)它们的属性值与正常实例的属性值相差较大

可通过任何分隔实例的方式实现孤立。

深入机器学习系列——异常检测(Anomaly Detection)
(2) 孤立树设T是孤立树的节点。T是没有子节点的外部节点,或者是具有一个测试的内部节点,并含有恰好两个子节点(T1,Tr)。节点T处的测试由属性q和分割值p组成,测试q <p可确定数据点到T1或Tr的遍历。 (3) 孤立森林:训练阶段

深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
(4)孤立森林:评估阶段
深入机器学习系列——异常检测(Anomaly Detection)
(5) 孤立森林:异常得分
深入机器学习系列——异常检测(Anomaly Detection)
(6) 调节异常得分的粒度
深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
2.复制神经网络(RNNs)(1) 假设RNN尝试在输出中重现输入模式。 在训练期间,调整RNN的权重以最小化所有训练模式的均方误差(或平均重构误差)。

因此,经过训练的RNN更可能很好地再现共同模式,而表示异常值的模式的再现效果则较为逊色,且重构误差较高。

重构误差可用于衡量数据的孤立程度。

深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
中间隐藏层(k = 3)的激活函数呈阶梯式,参数N是步数或激活级别,a3控制从一个级别到下一个级别的转换率。
深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
深入机器学习系列——异常检测(Anomaly Detection)
(2) 成本函数
深入机器学习系列——异常检测(Anomaly Detection)
m是训练集中的记录数,n是特征数,xij是输入值,也是目标输出值(i = 1,2,...,m,j = 1,2, ...,n)和olij是第7次迭代时RNN输出的值。(3) 异常因子(OF)我们将第i条数据记录OFi的异常因子定义为异常的度量。OFi由所有特征(变量)的平均重构误差定义。

深入机器学习系列——异常检测(Anomaly Detection)
其中n为特征数量。使用训练好的RNN评估所有数据记录的OF。
结语
简而言之,异常检测就是要从茫茫数据中找到那些“长的不一样”的数据,但检测过程一般较为复杂,而实际情况下数据一般都没有标签(label),因而很难界定与监测正常与异常,这方面还有很大的突破空间。

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/7017.html