目录
参考数据挖掘（七）—异常检测
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
comment here..