28.异常检测

一、异常检测的概念和应用

1.1 异常检测的概念

• 异常检测(Anomaly detection)问题——这是机器学习算法的一个常见应用。这种算法的一个有趣之处在于：它虽然主要用于非监督学习问题，但从某些角度看，它又类似于一些监督学习问题

• 所谓的异常检测问题就是：我们希望知道这个新的飞机引擎是否有某种异常，或者说，我们希望判断这个引擎是否需要进一步测试

• 异常检测是指在给定的一组无标签数据集$x^{(1)},x^{(2)},...,x^{(m)}$，针对这组数据集训练一个模型$p(x)$，来判定某个数据和数据集中大多数数据之间的相似程度(某个数据落在给定数据集中心区域的概率)，

  • 若某个数据$x_{test}$和大多数给定数据之间很相似，则$p(x_{test})\ge ϵ$,说明数据无明显异常情况；
  • 否则$p(x_{test})<ϵ$，说明数据$x_{test}$和大多数数据之间差异很大，说明给定的数据可能是一个异常数据

  

  • 在上图中，蓝色圈内的数据属于该组数据的可能性较高；而越偏远，属于该组数据的可能性就越低。 这种方法称为密度估计，表达式如下:

    

• 即若某个数据不落在大多数数据所在的范围之内，则这种数据出现的概率比较小，将检测出的这种数据视为异常数据

1.2 异常检测的应用

1. 飞机引擎检测：给定一系列正常的引擎参数，要求确定一个新生产的引擎是否正常，或者说，我们希望判断这个引擎是否需要进一步测试；
2. 异常检测主要用来识别欺骗，异常用户检测：网站检测用户刷新频率，登录次数、登陆位置等信息，判断用户行为是否异常；根据特征构建一个模型，可以用这个模型来识别那些不符合该模式的用户
3. 数据中心的计算机检测：检测计算机内存消耗、硬盘容量等信息，判断计算机是否异常；

二、高斯分布

• 高斯分布，也称为正态分布

• 通常如果我们认为变量 $x$ 符合高斯分布 $x\sim N(\mu ,{\sigma }^2)$则其概率密度函数为：
  $p(x,\mu ,{\sigma }^2)=\frac{1}{\sqrt{2\pi }\sigma }\exp \left(-\frac{(x-\mu {)}^2}{2{\sigma }^2}\right)$

  • $\mu$ 是均值
  • σ是标准差，确定了高斯分布概率密度函数的宽度
  • σ2就是方差
  • 概率密度函数与x轴的面积为1，即积分值=1

  

• 可以利用已有的数据来预测总体中的$\mu$和${\sigma }^2$的计算方法如下：

  • $\mu =\frac{1}{m}\sum _{i=1}^m{x}^{(i)}$
  • ${\sigma }^2=\frac{1}{m}\sum _{i=1}^m(x^{(i)}-\mu {)}^2$

• 高斯分布样例如下图（其中 μ 决定中心点的位置， σ2 决定曲线的高度）：

  

• 机器学习中对于方差我们通常只除以$m$而非统计学中的$(m-1)$

  • 在实际使用中，到底是选择使用$1/m$还是$1/(m-1)$其实区别很小，只要你有一个还算大的训练集，在机器学习领域大部分人更习惯使用$1/m$这个版本的公式
  • 这两个版本的公式在理论特性和数学特性上稍有不同，但是在实际使用中，他们的区别甚小，几乎可以忽略不计

三、异常检测算法

• 利用高斯分布开发异常检测算法

3.1 密度估计

• 对于给定的数据集 x ，针对每一个特征计算均值 μ 和方差 σ2 的估计值。然后，当出现一个新的训练实例，可以根据模型计算其对应的 p(x)，这个过程也叫做密度估计(Density estimation)，公式如下:

  

  （注：每个特征 xi 都对应不同的高斯分布）

​

3.2 异常检测算法

• 异常检测的具体流程：

  • 首先针对$m$个数据样本选择出$n$个可能出现异常的特征$x_j,j\in n$；

  • 之后针对所有样本计算每一个特征的均值${\mu }_j,j\in n$和方差${\sigma }_j^2,j\in n$；

  • 针对新给定的某个数据$x$计算$p(x)$，若$p(x)<ϵ$，则判定数据为异常数据

    

3.3 具体例子

• 下图2D 图形是一个具有两个特征的训练集及其两个特征的分布情况，3D 图形表示密度估计函数，z轴为根据两个特征对$x_{test}$估计出的$p(x)$值

  

• 选择一个 ε=0.02，将p(x) = ε作为决策边界，当p(x) > ε时预测为正常数据，否则为异常

四、开发和评价一个异常检测系统

4.1 数据的划分

• 异常检测算法是一个无监督学习算法

• 但事实上，如果我们拥有一些带标记的数据，为了检验算法是否有效

• 可以在最开始将其看作一个监督学习算法将已有数据分开

  • 从中选择一部分正常数据作为训练集，

  • 剩下的正常数据和异常数据混合构成交叉检验集和测试集

    

4.2 具体的算法评估方法

1. 根据测试集数据，我们估计特征的平均值和方差并构建$p(x)$函数

2. 对交叉检验集，我们尝试使用不同的$\epsilon$值作为阀值，并预测数据是否异常，根据**$F1$值或者查准率与查全率的比例来选择 $\epsilon$**

3. 选出 $\epsilon$ 后，针对测试集进行预测，计算异常检验系统的$F1$值，或者查准率与查全率之比

   

4.3 具体例子

• 我们有10000台正常引擎的数据，有20台异常引擎的数据。 我们这样分配数据：

  • 6000台正常引擎的数据作为训练集
  • 2000台正常引擎和10台异常引擎的数据作为交叉检验集
  • 2000台正常引擎和10台异常引擎的数据作为测试集

• 还有一些人把同样一组数据既用作交叉检验CV集，也用作测试Test集，但不推荐这样做

  

五、异常检测与监督学习对比

• 通常来说，正样本的数量很少，甚至有时候是0，也就是说，出现了太多没见过的不同的异常类型，那么对于这些问题，通常应该使用的算法就是异常检测算法

六、特征选择

6.1 特征转换

• 异常检测假设特征符合高斯分布，如果数据的分布不是高斯分布，异常检测算法也能够工作，但是最好还是将数据转换成高斯分布

• 例如使用对数函数：$x=log(x+c)$，其中 $c$ 为非负常数； 或者 $x=x^c$，$c$为 0-1 之间的一个分数等方法(注：在python中，通常用np.log1p()函数，$log1p$就是 $log(x+1)$，可以避免出现负数结果，反向函数就是np.expm1())

  

6.2 误差分析

• 一个常见的问题是一些异常的数据可能也会有较高的$p(x)$值，因而被算法认为是正常的

• 误差分析能够帮助我们，我们可以分析那些被算法错误预测为正常的数据，观察能否找出一些问题。我们可能能从问题中发现我们需要增加一些新的特征，增加这些新特征后获得的新算法能够帮助我们更好地进行异常检测

• 通常可以通过将一些相关的特征进行组合，来获得一些新的更好的特征(异常数据的该特征值异常地大或小)。例如增加两个特征值的比例

• 误差分析步骤： 同监督学习，先简单地搞出一套完整的算法，然后用验证集对其进行验证，然后对判断错误的验证集样本进行分析，看能不能找到一些其他的特征，让这些判断出错的样本能表现得更好

  

6.3 具体例子

• 例如，在检测计算机状况的例子中，可以用 CPU负载与网络通信量的比例作为一个新的特征，如果该值异常地大，便有可能意味着该服务器是陷入了一些问题中。如下图：

  

七、多元高斯分布

7.1 多元高斯分布的概念

• 假使我们有两个相关的特征，而且这两个特征的值域范围比较宽，这种情况下，一般的高斯分布模型可能不能很好地识别异常数据。其原因在于，一般的高斯分布模型尝试的是去同时抓住两个特征的偏差，因此创造出一个比较大的判定边界

• 下图中是两个相关特征，洋红色的线（根据ε的不同其范围可大可小）是一般的高斯分布模型获得的判定边界，很明显绿色的X所代表的数据点很可能是异常值，但是其$p(x)$值却仍然在正常范围内

• 如果使用多元高斯分布，获得蓝色曲线所示的判定边界，范围更小，判定结果会更准确

  

• 在多元高斯分布模型中，我们将构建特征的协方差矩阵，用所有的特征一起来计算 $p(x)$。

  • 我们首先计算所有特征的平均值，然后再计算协方差矩阵：

  • $p(x)={\prod }_{j=1}^{n}p(x_j;\mu ,{\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})$

  • $\mu =\frac{1}{m}{\sum }_{i=1}^m{x}^{(i)}$

  • $\Sigma =\frac{1}{m}{\sum }_{i=1}^m(x^{(i)}-\mu )(x^{(i)}-\mu {)}^T=\frac{1}{m}(X-\mu {)}^T(X-\mu )$

  • 注:其中$\mu$ 是一个向量，其每一个单元都是原特征矩阵中一行数据的均值。最后我们计算多元高斯分布的$p\left(x\right)$:

  • $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)$

  • 其中：$|\Sigma |$是定矩阵，在 Octave 中用 det(sigma)计算；${\Sigma }^{-1}$ 是逆矩阵

7.2 协方差矩阵对模型的影响

• 协方差对角线上的值影响图像的平缓程度，逆对角线上的值影响图像的角度（正值为顺时针旋转45度，负值为逆时针45度）

  

  • 图像从左往右:
    a. 一般的高斯分布模型
    b. 令特征 1 拥有较小的偏差，同时保持特征 2 的偏差
    c. 令特征 2 拥有较大的偏差，同时保持特征 1 的偏差
    d. 在不改变两个特征的原有偏差的基础上，增加两者之间的正相关性
    e. 在不改变两个特征的原有偏差的基础上，增加两者之间的负相关性

7.3 均值 µ 对中心点的影响

• 改变μ就是改变中心点的位置，在中心点具有最高的概率值

  

八、 使用多元高斯分布进行异常检测

8.1 使用多元高斯分布来进行异常检测

1. 计算出均值 µ 和协方差矩阵 Σ

   • $\mu$ 是你的训练样本的平均值：$\mu =\frac{1}{m}{\sum }_{i=1}^m{x}^{(i)}$
   • $\Sigma$：$\Sigma =\frac{1}{m}{\sum }_{i=1}^m(x^{(i)}-\mu )(x^{(i)}-\mu {)}^T$

2. 对新实例 x， 根据公式计算其 p(x) 的值，如果小于 ε 则异常
   

8.2 原始高斯分布模型 和 多元高斯分布模型

• 对于一个多元高斯分布模型，如果其协方差矩阵只有正对角线上元素非零，则退化为原始高斯分布模型

• 原高斯分布模型	多元高斯分布模型
  不能捕获特征之间的相关性，但可以通过将特征进行组合的方法来解决	自动捕获特征之间的相关性
  计算代价低，能适应大规模的特征	计算代价高，训练集较小时也同样适应
  	必须要有 m > n , 不然的话协方差矩阵不可逆，通常需要 m > 10n ，另外特征冗余会导致协方差矩阵不可逆

• 两个模型的选择：
  • 原高斯分布模型被广泛使用，如果特征之间在某种程度上相互关联，可以通过构造新特征的方法来捕捉这些相关性
  • 如果训练集不是太大，并且没有太多的特征，可以使用多元高斯分布模型