异常检测
由ypyu创建，最终由ypyu 被浏览 14 用户
在本文中，我将介绍机器学习中关于异常检测的算法。
因为知乎中对于markdown的支持太差了，本文不在知乎直接排版，所以阅读体验不是很好，若想获得更好的阅读体验，请点击下文链接进行阅读。
所有的文章都会在我的博客和我的知乎专栏同步进行更新，欢迎阅读
下面是正文：
顾名思义，异常检测是利用机器学习的方法，从一堆样本数据中选择出异常的个体。例如我们高中数学学习的3$\sigma$原则，就是异常检测的一个基础范例。
异常检测在生活中有重要的应用，如生产线产品质量控制、反恐任务、互联网异常用户检测等。
异常检测和分类任务
如果将0设定为正常样本，1设定为异常样本，异常检测又可以看做一个二分类的任务，那么它们之间有什么区别呢？
- 异常检测实际是一种非监督学习，而一般的分类任务是监督学习
- 异常检测通常有大量负样本（正常），没有或只有很少正样本（异常），而一般的监督学习一般同时有大量的正负样本
- 异常检测中的异常多种多样而且样本稀少，无法对异常进行学习。而监督学习可以通过大量的样本
算法前提
假设
异常检测算法有一个假设，即对于样本的每一个属性$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)$变换
这些变换并没有特殊的规律，可以尝试变换，之后检验是否符合正态分布，然后选择其中最好的变换方法。
更多数据变换预处理可以参考这篇文章，文中提到了一种方法：
- 首先根据数据样本画出均值和方差曲线
- 如果均值和方差不相关，则不需要转换
- 如果方差正比于均值，则进行square root transformation转换
- 如果标准差正比于均值，则进行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))}$进行计算，和阈值进行比较即可，其余流程和原始算法相同。
查看更多
所有的文章都会在我的博客和我的知乎专栏同步进行更新，欢迎阅读
- 我的博客
- 知乎专栏
\