异常检测

顾名思义,异常检测是利用机器学习的方法,从一堆样本数据中选择出异常的个体。例如我们高中数学学习的3$\sigma$原则,就是异常检测的一个基础范例。

异常检测在生活中有重要的应用,如生产线产品质量控制、反恐任务、互联网异常用户检测等。

异常检测和分类任务

如果将0设定为正常样本,1设定为异常样本,异常检测又可以看做一个二分类的任务,那么它们之间有什么区别呢?

  1. 异常检测实际是一种非监督学习,而一般的分类任务是监督学习
  2. 异常检测通常有大量负样本(正常),没有或只有很少正样本(异常),而一般的监督学习一般同时有大量的正负样本
  3. 异常检测中的异常多种多样而且样本稀少,无法对异常进行学习。而监督学习可以通过大量的样本

算法前提

假设

异常检测算法有一个假设,即对于样本的每一个属性$x_i^j$(代表第i个样本的第j个属性),它都满足高斯分布(正态分布):

$$x_i^j \sim \frac {1} {\sqrt{2\pi}\sigma} {e^{-\frac {(x-\mu)^2} {2\sigma^2}}}$$

高斯分布

预处理

显然,并不是所有样本属性都符合上述假设的,所以,要利用一定的预处理技术将样本属性变为正态分布。可以对属性值进行常见的变换,例如

  • 平方根变换
  • 对数变换
  • $arcsin(\sqrt x)$变换

这些变换并没有特殊的规律,可以尝试变换,之后检验是否符合正态分布,然后选择其中最好的变换方法。

更多数据变换预处理可以参考这篇文章,文中提到了一种方法:

  1. 首先根据数据样本画出均值和方差曲线
  2. 如果均值和方差不相关,则不需要转换
  3. 如果方差正比于均值,则进行square root transformation转换
  4. 如果标准差正比于均值,则进行logarithmic transformation转换

数据处理示例如下:

高斯分布

样本划分

之前说过,异常检测是一种可能带标记的非监督学习,其样本划分和普通学习任务不大一样,假设有10000个正常样本和20个异常样本,可以进行如下划分:

  • 训练集:6000个正常样本(不需要异常样本,所以可以认定为非监督学习)
  • 交叉验证集:2000个正常样本,10个异常样本
  • 测试集:2000个正常样本,10个异常样本

可以看出,训练本身是不需要异常样本的,只需要根据正常样本学习出正常样本是什么样的,与之不同的就是异常样本。

算法详情

算法流程

如果假设样本各属性之间相互独立,对于一个样本而言,其出现的概率等于其不同属性出现概率的乘积:

$$P(x_i)=\prod_{j=1}^nP(x_i^j)=\prod_{j=1}^{n} \frac {1} {\sqrt{2\pi}\sigma_j} {e^{-\frac {(x-\mu_j)^2} {2\sigma_j^2}}}$$

故只需要知道$\mu_j和\sigma_j$即可算出一个样本的概率。

根据所有样本的$x^j$属性,通过极大似然法可以算出:

$$u_j = \frac 1m\sum_{i=1}^{m} {x_i^j}​$$

$$\sigma_j=\frac 1m\sum_{i=1}^{m} {(x_i^j-u_j)^2} $$

于是,我们利用上述公式算出每个属性的$\mu和\sigma$,得到了每个属性的概率分布,然后通过乘积得到了每个样本的出现概率,这里需要设定一个阈值$\epsilon$,小于阈值记为异常样本。

$$P(x_i)<\epsilon$$

通过该方法,便实现了异常检测。

上述流程中唯一不确定的是$\epsilon$,该参数是不可以直接确定的,一般取决于想要控制的标准,标准越高,则该参数越小。标准越低,该参数越大。

算法解释

该算法为什么可以工作呢?其实很简单,和$3\sigma$原则一样,出现概率太小的样本可以视为不存在,如果他一旦出现,必定是出现了异常。如下图为两个属性的样本出现概率:

高斯分布

图中高度代表出现概率,若样本点所在位置的高度过低,低于阈值,则可能出现了异常。

算法优化

该算法有一个重要的前提——样本各属性之间相互独立,但是实际任务中,个属性往往不独立,例如一个用户登录次数多,那么浏览时间很可能就比较长,则不符合我们的模型,需要对算法进行优化。

如果你有概率统计的知识,就可以知道存在依赖关系的多变量高斯分布的公式:

$$P(x|\mu,\sum)=\frac 1 {(2\pi)^{\frac n2}|\sum|^{0.5}}e^{(-\frac12(x-\mu)^T\sum^{-1}(x-\mu))}$$

其中x为n维向量,$\mu$为n维向量,$\sum$为协方差矩阵,$|\sum|$为矩阵的行列式。

$\sum$描述的便是不同属性之间的相关关系,原算法是$\sum$为单位矩阵时的特例

该算法的任务仍然是算出参数$\mu和\sum$,同样由极大似然法可得:

$$\mu = \frac 1m \sum_{i=1}^m x_i$$

$$\sum = \frac 1m \sum_{i=1}^m {(x_i-\mu)(x_i-\mu)^T}$$

注意,其中$\mu,x_i$等都为n维向量。

算出参数之后,对于任一样本,带入$P(x|\mu,\sum)=\frac 1 {(2\pi)^{\frac n2}|\sum|^{0.5}}e^{(-\frac12(x-\mu)^T\sum^{-1}(x-\mu))}$进行计算,和阈值进行比较即可,其余流程和原始算法相同。

查看更多

所有的文章都会在我的博客和我的知乎专栏同步进行更新,欢迎阅读


本文结束啦感谢您的阅读
生活不易,求打赏
0%