[笔记]9.machine-learning-异常检测

April 13th, 2017

异常检测

在很多时候，我们希望检测一个产品是否正常，常用的一个方式就是异常检测算法。一个直观的感觉是如果这个东西跟其他的差异都好大，这个东西就是有问题的，进一步来说，我们可以看出这个东西出现问题的概率可能是多少，然后设定一个阈值，如果出问题的概率足够大，就能比较有把握的说这个东西已经出了问题。

一般来说，生产线上出现的物品会满足高斯分布(Gaussian Distribution)（或者经过一个变换之后满足高斯分布）：$\mathcal{N}(\mu,\sigma^2)$，所以一般可以用高斯分布绘制出概率密度函数，中间的这部分比较高代表这个物品有很大的概率出现在这个位置，也可以表示出现在这个位置的样本有很大的概率是正常的，反而离中心很远的样本就很有可能说明是有问题的。

20170413_6

高斯分布(Gaussian Distribution)

目前只考虑一维的情况，假设有一堆数字${x_1, x_2, …, x_m}$，按照数学表达，如果X满足高斯分布，可以写成$x \sim \mathcal{N}(\mu, \sigma^2)$，其中$\mu$和$\sigma$是高斯分布的参数，$\mu$代表这个集合的中心

\[\mu = \dfrac{1}{m}\displaystyle \sum_{i=1}^m x^{(i)}\]

$\sigma$代表分布的范围，跟之前课程SVM中高斯kernel里面那个类似，是这个集合的标准差

\[\sigma^2 = \dfrac{1}{m}\displaystyle \sum_{i=1}^m(x^{(i)} - \mu)^2\]

用这两个参数就可以描述一个高斯分布，在这个高斯分布中，样本满足某个x的概率可以写成：

\[\large p(x;\mu,\sigma^2) = \dfrac{1}{\sigma\sqrt{(2\pi)}}e^{-\dfrac{1}{2}(\dfrac{x - \mu}{\sigma})^2}\]

算法

了解了高斯分布，并且知道大部分的集合满足高斯分布或者变换后满足高斯分布，就可以考虑一个算法来检测这个集合中样本正常的概率，然而很多时候一个样本有很多维度，每个维度都会有一个自己的分布，所以我们可以采取另外一种思路，计算每个维度的分布，看这个样本这个feature是否看起来正常，计算正常的概率，然后将所有的feature正常的概率相乘，如果这些概率的乘积小于某一个阈值，我们就会觉得这个样本正常的概率很小。这个算法用数学公式表示为：

\[p(x) = p(x_1;\mu_1,\sigma_1^2)p(x_2;\mu_2,\sigma^2_2)\cdots p(x_n;\mu_n,\sigma^2_n) = \displaystyle \prod^n_{j=1} p(x_j;\mu_j,\sigma_j^2)\]

比较需要注意的一点是这个算法里面的训练集全部都默认是正常的样本，因为这个问题实质上还是一个分类的问题，有时候没有异常样本（生产线上会尽量避免异常产品出现）或者之前就没有区分正常样本和异常样本，只知道在之前这个生产线上产品正常概率很高，异常值比较少，所以异常值其实对整体的概率分布没有太大影响，全部都看作是正常的也没什么关系。在这个算法中训练集的目标其实只是描述一个整体的分布情况，求出每个feature分布的参数$\mu$和$\sigma$，然后通过验证集来决定阈值的选择。

并且这个算法的评判不应该选择准确率作为标准，而是在之前课程中提到的选取$F_1$ score

参照这个笔记 [笔记]6.machine-learning-应用机器学习的建议 中的偏斜类的误差度量

异常检测和监督学习

下面这些情况下推荐使用异常检测算法：

  • 有很少量的$y = 1$的样本（异常值很少，但是正常值很多）
  • 异常的类型有很多，可能未来会有其他样子的异常类型。使用监督学习很难找出这些异常的规律，所以监督学习算法在这个情况下效果会很不好

feature选择

由于我们的算法假设每个feature都是符合高斯分布的，所以当feature实际上不符合高斯分布的时候效果会稍微差一些，虽然对结果不一定有很大的影响，但是让每个feature满足高斯分布的做法还是有好处的。我们可以先观察每个feature的分布，如果不满足就采用一些变换将他变成满足高斯分布的方式：

  • $log(x)$
  • $log(x+1)$
  • $log(x+c)$
  • $\sqrt{x}$
  • $x ^ {1/3}$

在Octave中，使用hist命令可以查看数据集的分布情况，然后尝试上面的这些变换，使用各种参数后查看分布一般就能使数据满足高斯分布。

多元高斯分布(Multivariate Gaussian Distribution)

多元高斯分布的数学表达为：

\[p(x;\mu,\Sigma) = \dfrac{1}{(2\pi)^{n/2} |\Sigma|^{1/2}} exp(-1/2(x-\mu)^T\Sigma^{-1}(x-\mu))\]

与之前的一个区别主要在于$\Sigma$矩阵，在前面将所有feature各自的分布描述出来，然后所有概率值相乘设置阈值的方式中，$\sigma$的数量和feature的数量是一致的，每个feature对应一个$\mu$和$\sigma$，他们的值都是feature大小n。

但是之前的这个做法实际上默认了每个feature之间是相互独立的，或者说我们需要选取相互独立的feature，尽管在实际操作上不相互独立的feature用这个算法也能获得很好的效果，但是这个和初始设定还是有一点不一样。在多元高斯分布中，$\Sigma$矩阵是一个$n \times n$的矩阵，这个矩阵就描述了每个feature之间的相互影响，之前的算法可以看做是$\Sigma$对角线外的元素都是0（$\Sigma$是单位矩阵(identity matrix)）的一个多元高斯分布，用两个feature的多元高斯分布拟合出来的结果在二维上的投影像是一个椭圆，大小和方向受到$\Sigma$的影响，在$\Sigma$是单位矩阵（之前的算法）的情况下，这个椭圆的轴线与坐标轴的轴线平行，$\mu_j = 0$的情况下椭圆的轴线就是坐标轴。

推荐系统

这部分的课程讲了一个电影推荐系统的实作，首先定义一些变量的概念：

  • $n_u$ 用户数量
  • $n_m$ 电影数量
  • $r(i, j)$ 表示用户j是否评价了电影i的一个矩阵，如果评价了对应的值是1，否则是0
  • $y(i, j)$ 用户j对电影i的评分，如果r矩阵对应的是0（用户没有对这个电影评分），这个值无意义
  • $m^{(j)}$ 用户j评价过的电影数量

然后假设每个电影包含两个方面的特征：$x_1, x_2$ 分别表示电影中爱情和动作部分的程度（两个feature的值都在0到1之间，加起来不一定要等于1）。通过这些就可以为每个用户拟合出一个向量$\theta^{(j)} \in \mathbb{R}^3$，用户j对电影i的评分是$(\theta^{(j)})^Tx^{(i)}$。

然后针对预测的正确性和对参数的惩罚可以写出优化目标：

\[min_{\theta^{(1)}, ...,\theta^{(n_u)}} = \dfrac{1}{2}\displaystyle \sum_{j=1}^{n_u} \sum_{i:r(i,j)=1} ((\theta^{(j)})^T(x^{(i)}) - y^{(i,j)})^2 + \dfrac{\lambda}{2} \sum_{j=1}^{n_u} \sum_{k=1}^n(\theta_k^{(j)})^2\]

然而有个问题就是对于一般的电影，我们并不知道电影内容，电影也不会写出其中的爱情成分有多少动作成分有多少，所以我们还需要拟合出$x^{(1)}, x^{(2)}, …, x^{(n_m)}$的值:

\[min_{x^{(1)}, ...,x^{(n_m)}} \dfrac{1}{2} \displaystyle \sum_{i=1}^{n_m} \sum_{j:r(i,j)=1} ((\theta^{(j)})^T x^{(i)} - y^{(i,j)})^2 + \dfrac{\lambda}{2}\sum_{i=1}^{n_m} \sum_{k=1}^{n} (x_k^{(i)})^2\]

由于有两组不同的变量需要拟合，可以采用先随机这些值，然后在每一步中都固定$\Theta$拟合X的值，然后固定X拟合$\Theta$的值。持续迭代这个步骤直到收敛，或者直接同时迭代这两个值，cost function是：

\[J(x,\theta) = \dfrac{1}{2} \displaystyle \sum_{(i,j):r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \dfrac{\lambda}{2}\sum_{i=1}^{n_m} \sum_{k=1}^{n} (x_k^{(i)})^2 + \dfrac{\lambda}{2}\sum_{j=1}^{n_u} \sum_{k=1}^{n} (\theta_k^{(j)})^2\]

跟之前的做法一样，可以用梯度下降算法，也可以使用更高端一些的方法。

求出了X和 $ \Theta $ 之后就可以用 $ Y = X\Theta^T $ 预测或者验证所有用户对所有电影的评分了，如果想知道两个电影之间的相似度可以看 $ ||x^{(i)} - x^{(j)}|| $ 的值，针对每个新的用户，可以在已知 $ X $ 的情况下计算这个用户的 $ \Theta $

参考

  1. 机器学习 Coursera公开课 by斯坦福大学
  2. 15_Anomaly_Detection
  3. 16_Recommender_Systems
  4. Week 9 Lecture Notes
  5. File:Normal approximation to binomial.png

所有笔记链接