To Top
首页 > 机器学习 > 正文

异常检测常用算法

标签:异常检测, anormaly detection, iforest


目录

参考数据挖掘(七)—异常检测

1. 概述

异常对象呗称为离群点(oulier)。异常检测也称偏差检测(deviation detection),因为异常对象的属性值明显偏离期望的或常见的属性值。异常检测也称例外挖掘(exception mining),因为异常在某种意义上是例外的。

1.1 异常的原因

  • 数据来源于不同的类:某个数据对象可能不同于其他数据对象(即异常),因为它属于一个不同的类型或类。 Hawkins 的离群点定义:离群点是一个观测值,它与其他观测值的差别如此之大,以至于怀疑它是由不同的机制产生的。
  • 自然变异:许多数据集可以用一个统计分布建模,如正态(高斯)分布建模,其中数据对象的概率随对象到分布中心距离的增加而急剧减少。换言之,大部分数据对象靠近中心(平均对象),数据对象显著地不同于这个平均对象的似然性很小。
  • 数据测量和收集误差:数据收集和测量过程中的误差是另一个异常源。剔除这类异常是数据预处理(尤其是数据清理)的关注点。

1.2 方法

  • 基于模型的技术:许多异常检测技术首先建立一个数据模型。异常是那些同模型不能完美拟合的对象。
  • 基于邻近度的技术:通常可以在对象之间定义邻近性度量,并且许多异常检测方法都基于邻近度。异常对象是那些远离大部分其他对象的对象,这一邻域的许多技术都基于距离,称作基于距离的离群点检测技术。
  • 基于密度的技术:对象的密度估计可以相对直接地计算,特别是当对象之间存在邻近度度量时。低密度区域中的对象相对远离近邻,可能被看做异常。

1.3 方法

  • 有监督的异常检测:有异常类和正常类的训练集(可能存在多个正常类或异常类)
  • 无监督的异常检测:在许多实际情况下,没有label,目标是将一个得分(或标号)赋予每个实例,反映该实例是异常的程度。注意:许多互相相似的异常的类可能导致他们都被标为正常,或具有较低的离群点得分。
  • 半监督的异常检测:在半监督的情况下,目标是使用有标记的正常对象的信息,对于给定的对象集合,发现异常标号或得分。注意:在这种情况下,被评分对象集中许多相关的离群点的出现并不影响离群点的评估。

2. 无监督算法

2.1 作用于numeric data的方法

这类方法是基于异常数据属于低密度的区域的假设。这些方法都依赖数值数据的一个重要特性:序关系。所以类别数据如果可以将类别属性转换成数据属性,也可以用这类方法。

  • 基于距离的k-NN/LDOF
  • 基于密度的LOF
  • 基于聚类的CBOF
  • 基于Isolation的iForest

假设有\(d\)个样本,大部分方法时间复杂度都是\(O(d^2)\),如kNN/LOF;如果用R*-Tree之类的索引方法,可以达到\(O(dlogd)\),但对于高维数据和类别数据,索引方法是会失效的。

iforest基于子空间和子样本。

2.2 作用于categorical data的方法

学术界对这类数据的研究很少,大都基于异常数据属于低频区域的假设。

  • 基于频率pattern的FPOF
  • 基于infrequent(罕见) pattern的LOADED
  • 基于pattern的压缩算法:KRIMP和COMPREX。KRIMP基于frequent itemset;COMPREX利用Min Description Length原则,自动地从attribute groups(子空间)生成高信息增益的pattern,并且避免了costly frequent itemset search。

上述三类模型都是基于全量训练数据,训练一个model。

2.3 Exact methods v.s. Probalistic methods

Exact methods对于相同的criteria,会给出相同的结果,概率方法则不然。kNN/LOF/FPOF/COMPREX都是exact methods。

  • 许多exact方法由于需要全量的数据集,所以会受困于masking(由于其他异常点的存在,有些异常点被忽略了)或者swamping(由于一些异常点的存在,有些点被误判为异常点了)。但概率方法基于子集,对这两类问题会更鲁棒。
  • exact方法使用了所有属性,相比只使用部分属性的概率方法而言,对不相关和噪音特征会更加敏感
  • 因为不需要进行距离计算或者/且不需要搜索子空间,概率方法的时间复杂度更低,对大数据集尤为如此。
  • 在准确率方面,概率方法至少会和持平,且大部分时间会表现得更好。

iForest

参考https://zhuanlan.zhihu.com/p/25040651

微软的异常检测服务

Time-Series Anomaly Detection Service at Microsoft

时序数据的异常检测在实际生产环境中有着重要且广泛的应用,包括业务指标、DevOps 数据以及 IOT Sensor 数据的监控等。及时地发现异常可以有效降低企业成本,增加服务的稳定性。构建一个准确并实用的异常检测算法主要有以下几点挑战:1)缺乏标注:在系统中有百万级别的时间序列,我们很难对每种类型的数据进行足够的标注;2)泛化:时间序列的模式多种多样,产品要求算法对各式各样的时间序列具备很好的泛化能力;3)效率:线上服务对算法的执行效率有较高要求,一些复杂的模型虽然精度不错,但效率达不到产品的要求。

在微软内部,AI Platform of Cloud+AI 产品组构建了一个异常检测平台,应用于包括 Azure、Office 以及必应在内的多个产品组,同时在微软认知服务上提供 API 供外部客户使用。我们针对该产品面临的挑战,发明了一种准确、高效的异常检测算法,带来了显著的效果提升。


原创文章,转载请注明出处!
本文链接:http://daiwk.github.io/posts/ml-anormaly-detection.html
上篇: 传统ctr预估
下篇: ftrl

comment here..