共计 7527 个字符，预计需要花费 19 分钟才能阅读完成。
异样检测：摸索数据深层次背地的神秘《上篇》
1、什么是异样检测
异样检测（Outlier Detection），顾名思义，是辨认与失常数据不同的数据，与预期行为差别大的数据。
辨认如信用卡欺诈，工业生产异样，网络流里的异样（网络侵入）等问题，针对的是多数的事件。
1.1 异样的类别
点异样（point anomalies）指的是多数个体实例是异样的，大多数个体实例是失常的，例如正常人与病人的衰弱指标；
条件异样（conditional anomalies），又称上下文异样，指的是在特定情境下个体实例是异样的，在其余情境下都是失常的，例如在特定工夫下的温度忽然回升或降落，在特定场景中的疾速信用卡交易；
群体异样（group anomalies）指的是在群体汇合中的个体实例出现异常的状况，而该个体实例本身可能不是异样，在入侵或欺诈检测等利用中，离群点对应于多个数据点的序列，而不是单个数据点。例如社交网络中虚伪账号造成的汇合作为群体异样子集，但子集中的个体节点可能与实在账号一样失常。
1.2 异样检测工作分类
有监督：训练集的正例和反例均有标签
无监督：训练集无标签
半监督：在训练集中只有正例，异样实例不参加训练
1.3 异样检测场景
- 故障检测：次要是监控零碎，在故障产生时能够辨认，并且精确指出故障的品种以及呈现地位。次要应用领域包含银行欺诈、挪动蜂窝网络故障、保险欺诈、医疗欺诈。
- 医疗日常检测：在许多医疗利用中，数据是从各种设施收集的，如磁共振成像（MRI）扫描、正电子发射断层扫描（PET）扫描或心电图（ECG）工夫序列。这些数据中的异样模式通常反映疾病情况。
- 网络入侵检测：在许多计算机系统中，都会收集无关操作系统调用、网络流量或其余用户操作的不同类型的数据。因为歹意流动，此数据可能显示异样行为。对此类流动的辨认称为入侵检测。
- 欺诈检测：信用卡欺诈越来越广泛，因为信用卡号码等敏感信息更容易被泄露。在许多状况下，未经受权应用信用卡可能体现出不同的模式，例如从特定地点疯狂购买或进行十分大的交易。这种模式可用于检测信用卡交易数据中的异样值。
- 工业异样检测
- 工夫序列异样检测
- 视频异样检测
- 日志异样检测
1.4 异样检测的难点
1. 数据量少。异样检测工作通常状况下负样本（异样样本）是比拟少的，有时候依赖于人工标签，属于样本不均衡问题。
2. 乐音。异样和乐音有时候很难分清，如下图，图 a 的 A 点位于数据的稠密区域，与其余数据十分不同，因而能够判定为异样，然而像图 b 的 A 点，四周有也有很多点散布，咱们很难把 A 点辨认进去。
2、异样检测办法简介
2.1 根底办法
2.1.1 基于统计学的办法
统计学办法对数据的正常性做出假设。它们假设失常的数据对象由一个统计模型产生，而不恪守该模型的数据是异样点。统计学办法的有效性高度依赖于对给定数据所做的统计模型假设是否成立。
异样检测的统计学办法的个别思维是：学习一个拟合给定数据集的生成模型，而后辨认该模型低概率区域中的对象，把它们作为异样点。
即利用统计学办法建设一个模型，而后思考对象有多大可能合乎该模型。
假设输出数据集为 $\{x^{(1)}, x^{(2)}, …, x^{(m)}\}$，数据集中的样本遵从正态分布，即 $x^{(i)}\sim N(\mu, \sigma^2)$，咱们能够依据样本求出参数 $\mu$ 和 $\sigma$。
$\mu=\frac 1m\sum_{i=1}^m x^{(i)}$
$\sigma^2=\frac 1m\sum_{i=1}^m (x^{(i)}-\mu)^2$
2.1.2 线性模型
典型的如 PCA 办法，Principle Component Analysis 是主成分剖析，简称 PCA。它的利用场景是对数据集进行降维。降维后的数据可能最大水平地保留原始数据的特色（以数据协方差为衡量标准）。其原理是通过结构一个新的特色空间，把原数据映射到这个新的低维空间里。PCA 能够进步数据的计算性能，并且缓解 ” 高维劫难 ”。
2.1.3 基于邻近度的办法
这类算法实用于数据点的汇集水平高、离群点较少的状况。同时，因为类似度算法通常须要对每一个数据别离进行相应计算，所以这类算法通常计算量大，不太实用于数据量大、维度高的数据。
基于类似度的检测办法大抵能够分为三类：
-
基于集群（簇）的检测，如 DBSCAN 等聚类算法。
聚类算法是将数据点划分为一个个绝对密集的“簇”，而那些不能被归为某个簇的点，则被视作离群点。这类算法对簇个数的抉择高度敏感，数量抉择不当可能造成较多正常值被划为离群点或成小簇的离群点被归为失常。因而对于每一个数据集须要设置特定的参数，才能够保障聚类的成果，在数据集之间的通用性较差。聚类的次要目标通常是为了寻找成簇的数据，而将异样值和噪声一起作为无价值的数据而疏忽或抛弃，在专门的异样点检测中应用较少。 -
基于间隔的度量，如 k 近邻算法。
k 近邻算法的基本思路是对每一个点，计算其与最近 k 个相邻点的间隔，通过间隔的大小来判断它是否为离群点。在这里，离群间隔大小对 k 的取值高度敏感。如果 k 太小（例如 1），则大量的邻近离群点可能导致较低的离群点得分；如果 k 太大，则点数少于 k 的簇中所有的对象可能都成了离群点。为了使模型更加稳固，间隔值的计算通常应用 k 个最近邻的均匀间隔。
-
基于密度的度量，如 LOF（部分离群因子）算法。
部分离群因子（LOF）算法与 k 近邻相似，不同的是它以绝对于其街坊的部分密度偏差而不是间隔来进行度量。它将相邻点之间的间隔进一步转化为“邻域”，从而失去邻域中点的数量（即密度），认为密度远低于其街坊的样本为异样值。
2.2 集成办法
集成是进步数据挖掘算法精度的罕用办法。集成办法将多个算法或多个基检测器的输入联合起来。其根本思维是一些算法在某些子集上体现很好，一些算法在其余子集上体现很好，而后集成起来使得输入更加鲁棒。集成办法与基于子空间办法有着人造的相似性，子空间与不同的点集相干，而集成办法应用基检测器来摸索不同维度的子集，将这些基学习器集合起来。
罕用的集成办法有 Feature bagging，孤立森林等。
feature bagging ：
与 bagging 法相似，只是对象是 feature。
孤立森林：
孤立森林假如咱们用一个随机超平面来切割数据空间，切一次能够生成两个子空间。而后咱们持续用随机超平面来切割每个子空间并循环，直到每个子空间只有一个数据点为止。直观上来讲，那些具备高密度的簇须要被切很屡次才会将其拆散，而那些低密度的点很快就被独自调配到一个子空间了。孤立森林认为这些很快被孤立的点就是异样点。
用四个样本做简略直观的了解，d 是最早被孤立进去的，所以 d 最有可能是异样。
2.3 机器学习
在有标签的状况下，能够应用树模型（gbdt,xgboost 等）进行分类，毛病是异样检测场景下数据标签是不平衡的，然而利用机器学习算法的益处是能够结构不同特色。
- 参考资料
[1]《Outlier Analysis》——Charu C. Aggarwal
[2] https://zhuanlan.zhihu.com/p/260651151
3. 异样检测——基于统计学的办法
次要内容包含：
- 高斯分布
- 箱线图
- HBOS
统计学办法对数据的正常性做出假设。它们假设失常的数据对象由一个统计模型产生，而不恪守该模型的数据是异样点。统计学办法的有效性高度依赖于对给定数据所做的统计模型假设是否成立。
异样检测的统计学办法的个别思维是：学习一个拟合给定数据集的生成模型，而后辨认该模型低概率区域中的对象，把它们作为异样点。
即利用统计学办法建设一个模型，而后思考对象有多大可能合乎该模型。
依据如何指定和学习模型，异样检测的统计学办法能够划分为两个次要类型：参数办法和非参数办法。
参数办法 假设失常的数据对象被一个以 $\Theta$ 为参数的参数散布产生。该参数散布的概率密度函数 $f(x,\Theta)$ 给出对象 $x$ 被该散布产生的概率。该值越小，$x$ 越可能是异样点。
非参数办法 并不假设先验统计模型，而是试图从输出数据确定模型。非参数办法通常假设参数的个数和性质都是灵便的，不预先确定（所以非参数办法并不是说模型是齐全无参的，齐全无参的状况下从数据学习模型是不可能的）。
3.1、参数办法
2.1 基于正态分布的一元异样点检测
仅波及一个属性或变量的数据称为一元数据。咱们假设数据由正态分布产生，而后能够由输出数据学习正态分布的参数，并把低概率的点辨认为异样点。
假设输出数据集为 $\{x^{(1)}, x^{(2)}, …, x^{(m)}\}$，数据集中的样本遵从正态分布，即 $x^{(i)}\sim N(\mu, \sigma^2)$，咱们能够依据样本求出参数 $\mu$ 和 $\sigma$。
$\mu=\frac 1m\sum_{i=1}^m x^{(i)}$
$\sigma^2=\frac 1m\sum_{i=1}^m (x^{(i)}-\mu)^2$
求出参数之后，咱们就能够依据概率密度函数计算数据点遵从该散布的概率。正态分布的概率密度函数为
$p(x)=\frac 1{\sqrt{2\pi}\sigma}exp(-\frac{(x-\mu)^2}{2\sigma^2})$
如果计算出来的概率低于阈值，就能够认为该数据点为异样点。
阈值是个经验值，能够抉择在验证集上使得评估指标值最大（也就是成果最好）的阈值取值作为最终阈值。
例如罕用的 3sigma 准则中，如果数据点超过范畴 $(\mu-3\sigma, \mu+3\sigma)$，那么这些点很有可能是异样点。
这个办法还能够用于可视化。箱线图对数据分布做了一个简略的统计可视化，利用数据集的高低四分位数（Q1 和 Q3）、中点等造成。异样点常被定义为小于 Q1-1.5IQR 或大于 Q3+1.5IQR 的那些数据。
用 Python 画一个简略的箱线图：
import numpy as np
import seaborn as sns
import matplotlib.pyplot as plt
data = np.random.randn(50000) * 20 + 20
sns.boxplot(data=data)2.2 多元异样点检测
波及两个或多个属性或变量的数据称为多元数据。许多一元异样点检测办法都能够裁减，用来解决多元数据。其核心思想是把多元异样点检测工作转换成一元异样点检测问题。例如基于正态分布的一元异样点检测裁减到多元情景时，能够求出每一维度的均值和标准差。对于第 $j$ 维：
$\mu_j=\frac 1m\sum_{i=1}^m x_j^{(i)}$
$\sigma_j^2=\frac 1m\sum_{i=1}^m (x_j^{(i)}-\mu_j)^2$
计算概率时的概率密度函数为
$p(x)=\prod_{j=1}^n p(x_j;\mu_j,\sigma_j^2)=\prod_{j=1}^n\frac 1{\sqrt{2\pi}\sigma_j}exp(-\frac{(x_j-\mu_j)^2}{2\sigma_j^2})$
这是在各个维度的特色之间互相独立的状况下。如果特色之间有相关性，就要用到多元高斯分布了。
1.3 多个特色相干，且合乎多元高斯分布
$\mu=\frac{1}{m}\sum^m_{i=1}x^{(i)}$
$\sum=\frac{1}{m}\sum^m_{i=1}(x^{(i)}-\mu)(x^{(i)}-\mu)^T$
$p(x)=\frac{1}{(2 \pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}} \exp \left(-\frac{1}{2}(x-\mu)^{T} \Sigma^{-1}(x-\mu)\right)$
ps: 当多元高斯分布模型的协方差矩阵 $\sum$ 为对角矩阵，且对角线上的元素为各自一元高斯分布模型的方差时，二者是等价的。
3. 应用混合参数散布
在许多状况下假设数据是由正态分布产生的。当理论数据很简单时，这种假设过于简略，能够假设数据是被混合参数散布产生的。
3.2、非参数办法
在异样检测的非参数办法中，“失常数据”的模型从输出数据学习，而不是假设一个先验。通常，非参数办法对数据做较少假设，因此在更多状况下都能够应用。
例子：应用直方图检测异样点。
直方图是一种频繁应用的非参数统计模型，能够用来检测异样点。该过程包含如下两步：
步骤 1：结构直方图。应用输出数据（训练数据）结构一个直方图。该直方图能够是一元的，或者多元的（如果输出数据是多维的）。
只管非参数办法并不假设任何先验统计模型，然而通常的确要求用户提供参数，以便由数据学习。例如，用户必须指定直方图的类型（等宽的或等深的）和其余参数（直方图中的箱数或每个箱的大小等）。与参数办法不同，这些参数并不指定数据分布的类型。
步骤 2：检测异样点。为了确定一个对象是否是异样点，能够对照直方图查看它。在最简略的办法中，如果该对象落入直方图的一个箱中，则该对象被看作失常的，否则被认为是异样点。
对于更简单的办法，能够应用直方图赋予每个对象一个异样点得分。例如令对象的异样点得分为该对象落入的箱的容积的倒数。
应用直方图作为异样点检测的非参数模型的一个毛病是，很难抉择一个适合的箱尺寸。一方面，如果箱尺寸太小，则许多失常对象都会落入空的或稠密的箱中，因此被误辨认为异样点。另一方面，如果箱尺寸太大，则异样点对象可能渗入某些频繁的箱中，因此“假扮”成失常的。
3.3、基于角度的办法
基于角度的办法的次要思维是：数据边界上的数据很可能将整个数据突围在一个较小的角度内，而外部的数据点则可能以不同的角度围绕着他们。如下图所示，其中点 A 是一个异样点，点 B 位于数据外部。
如果数据点与其余点离得较远，则潜在角度可能越小。因而，具备较小角度谱的数据点是异样值，而具备较大角度谱的数据点不是异样值。
思考三个点 X,Y,Z。如果对于任意不同的点 Y,Z，有：
$$
W \operatorname{Cos}(\overrightarrow{X Y}, \overrightarrow{X Z})=\frac{\langle\overline{X Y}, X Z\rangle}{\|X Y\|\|X Z\|}
$$
其中 $||\space||$ 代表 L2 范数 , $< · > $ 代表点积。
这是一个加权余弦，因为分母蕴含 L2- 范数，其通过间隔的逆加权进一步减小了异样点的加权角，这也对角谱产生了影响。而后，通过扭转数据点 Y 和 Z，放弃 X 的值不变计算所有角度的办法。相应地，数据点 X 的基于角度的异样分数（ABOF）∈ D 为：
$$
A B O F(X)=\operatorname{Var}_{\{Y, Z \in D\}} W \operatorname{Cos}(\overrightarrow{X Y}, \overrightarrow{X Z})
$$
3.4、HBOS
HBOS 全名为：Histogram-based Outlier Score。它是一种单变量办法的组合，不能对特色之间的依赖关系进行建模，然而计算速度较快，对大数据集敌对。其根本假如是数据集的每个维度互相独立。而后对每个维度进行区间 (bin) 划分，区间的密度越高，异样评分越低。
HBOS 算法流程：
1. 为每个数据维度做出数据直方图。对分类数据统计每个值的频数并计算绝对频率。对数值数据依据散布的不同采纳以下两种办法：
- 动态宽度直方图：规范的直方图构建办法，在值范畴内应用 k 个等宽箱。样本落入每个桶的频率（绝对数量）作为密度（箱子高度）的预计。工夫复杂度：$O(n)$
-
2. 动静宽度直方图：首先对所有值进行排序，而后固定数量的 $\frac{N}{k}$ 个间断值装进一个箱里，其中 N 是总实例数，k 是箱个数；直方图中的箱面积示意实例数。因为箱的宽度是由箱中第一个值和最初一个值决定的，所有箱的面积都一样，因而每一个箱的高度都是可计算的。这意味着跨度大的箱的高度低，即密度小，只有一种状况例外，超过 k 个数相等，此时容许在同一个箱里超过 $\frac{N}{k}$ 值。
工夫复杂度：$O(n\times log(n))$
2. 对每个维度都计算了一个独立的直方图，其中每个箱子的高度示意密度的预计。而后为了使得最大高度为 1（确保了每个特色与异样值得分的权重相等），对直方图进行归一化解决。最初，每一个实例的 HBOS 值由以下公式计算：
$$
H B O S(p)=\sum_{i=0}^{d} \log \left(\frac{1}{\text {hist}_{i}(p)}\right)
$$
推导过程：
假如样本 p 第 i 个特色的概率密度为 $p_i(p)$，则 p 的概率密度能够计算为：
$$
P(p)=P_{1}(p) P_{2}(p) \cdots P_{d}(p)
$$
两边取对数：
$$
\begin{aligned}
\log (P(p)) &=\log \left(P_{1}(p) P_{2}(p) \cdots P_{d}(p)\right) =\sum_{i=1}^{d} \log \left(P_{i}(p)\right)
\end{aligned}
$$
概率密度越大，异样评分越小，为了不便评分，两边乘以“-1”：
$$
-\log (P(p))=-1 \sum_{i=1}^{d} \log \left(P_{t}(p)\right)=\sum_{i=1}^{d} \frac{1}{\log \left(P_{i}(p)\right)}
$$
最初可得：
$$
H B O S(p)=-\log (P(p))=\sum_{i=1}^{d} \frac{1}{\log \left(P_{i}(p)\right)}
$$
- 小结
1. 异样检测的统计学办法由数据学习模型，以区别失常的数据对象和异样点。应用统计学办法的一个长处是，异样检测能够是统计上无可非议的。当然，仅当对数据所做的统计假设满足理论束缚时才为真。
2.HBOS 在全局异样检测问题上体现良好，但不能检测部分异样值。然而 HBOS 比规范算法快得多，尤其是在大数据集上。
- 参考资料
[1] Goldstein, M. and Dengel, A., 2012. Histogram-based outlier score (hbos):A fast unsupervised anomaly detection algorithm . InKI-2012: Poster and Demo Track, pp.59-63.
[2] http://speech.ee.ntu.edu.tw/~tlkagk/courses.html
[3] http://cs229.stanford.edu/
[4]《Outlier Analysis》——Charu C. Aggarwal
更多优质内容请关注公号：汀丶人工智能；会提供一些相干的资源和优质文章，收费获取浏览。