Coursea-吴恩达-machine learning学习笔记（十五）【week 9之Anomaly Detection】

异常检测：
存在样本集{x(1),x(2),⋯,x(m)}$\{x^{(1)},x^{(2)},\cdots ,x^{(m)}\}$，通常假设这m$m$个样本都是正常的或者不异常的，对训练集数据建一个模型p(x)$p(x)$，即对x$x$的分布概率建模，当建立完概率模型后，对新的样本xtest$x_{test}$来说，如果p(xtest)<ε$p(x_{test})<\epsilon$，标记为不正常，否则，标记为正常。
异常检测最常见的应用：

1. 欺诈检测
   x(i)$x^{(i)}$为用户活动的特征值；
   利用数据建立模型p(x)$p(x)$，用来表示用户做出各种行为的可能性，即对应特征变量出现的概率；
   检测用户的p(x)$p(x)$是否小于ε$\epsilon$来定义行为异常用户。
2. 工业生产领域
3. 数据中心的计算机监控

高斯分布(正态分布)：
设x∈R$x\in R$，如果x$x$的概率分布服从高斯分布(均值为μ$\mu$，方差为σ2${\sigma }^2$)，则记做x∼N(μ,σ2)$x\sim N(\mu ,{\sigma }^2)$，高斯分布的概率密度公式：

该公式的图形表示如下图：

μ$\mu$控制图中曲线的中心位置，σ$\sigma$控制该曲线的宽度。
不同μ$\mu$与σ$\sigma$取值的概率密度曲线如下图所示：


因为这是一个概率分布曲线，所以曲线下的面积积分一定为1。

参数估计：
假设有一个数据集{x(1),x(2),⋯,x(m)}$\{x^{(1)},x^{(2)},\cdots ,x^{(m)}\}$，x(i)∈R$x^{(i)}\in R$，如下图：

猜测每个样本x(i)$x^{(i)}$服从高斯分布N(μ,σ2)$N(\mu ,{\sigma }^2)$
则

基于高斯分布的异常检测算法：
存在训练集{x(1),x(2),⋯,x(m)}$\{x^{(1)},x^{(2)},\cdots ,x^{(m)}\}$，x(i)∈Rn$x^{(i)}\in R^n$
设x1∼N(μ1,σ21),x2∼N(μ2,σ22),x3∼N(μ3,σ23),⋯,xn∼N(μn,σ2n)$x_1\sim N({\mu }_1,{\sigma }_1^2),x_2\sim N({\mu }_2,{\sigma }_2^2),x_3\sim N({\mu }_3,{\sigma }_3^2),\cdots ,x_n\sim N({\mu }_n,{\sigma }_n^2)$
则模型P(x)=p(x1;μ1,σ21)p(x2;μ2,σ22)p(x3;μ3,σ23)⋯p(xn;μn,σ2n)=∏j=1np(xj;μj,σ2j)$P(x)=p(x_1;{\mu }_1,{\sigma }_1^2)p(x_2;{\mu }_2,{\sigma }_2^2)p(x_3;{\mu }_3,{\sigma }_3^2)\cdots p(x_n;{\mu }_n,{\sigma }_n^2)=\prod _{j=1}^{n}p(x_j;{\mu }_j,{\sigma }_j^2)$

异常检测算法步骤：

1. 选择可以表征异常样本的特征值xi$x_i$，得到样本集{x(1),x(2),⋯,x(m)}$\{x^{(1)},x^{(2)},\cdots ,x^{(m)}\}$；
2. 拟合出参数μ1,⋯,μn,σ21,⋯,σ2n${\mu }_1,\cdots ,{\mu }_n,{\sigma }_1^2,\cdots ,{\sigma }_n^2$
   
   μj=1m∑i=1mx(i)jσ2j=1m∑i=1m(x(i)j−μj)2$${\mu }_j=\frac{1}{m}\sum _{i=1}^m{x}_j^{(i)}{\sigma }_j^2=\frac{1}{m}\sum _{i=1}^m(x_j^{(i)}-{\mu }_j{)}^2$$
3. 给出新样本x$x$，计算p(x)$p(x)$：
   
   P(x)=∏j=1np(xj;μj,σ2j)=∏j=1n12π−−√σjexp(−(xj−μj)22σ2j)$$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})$$
   
   如果P(x)<ε$P(x)<\epsilon$，标注为异常。

当使用某个学习算法开发一个具体的机器学习应用时，常需要作出许多决定，如选择特征值等，如果找到某种评价算法的方式，直接返回一个数字来评价算法的好坏，那么做决定将会容易很多。
异常检测问题是一个非监督学习问题，使用无标签数据，但如果有一些带标签的数据可以指出异常/非异常样本，这就是可以评价异常检测算法的标准方法。

假设存在一些带标签数据(包含异常/非异常样本)，如果正常y=0$y=0$，否则y=1$y=1$；
训练集为无标签数据{x(1),x(2),⋯,x(m)}$\{x^{(1)},x^{(2)},\cdots ,x^{(m)}\}$(假设均为正常/非异常样本)
交叉验证集：{(x(1)cv,y(1)cv),⋯,(x(mcv)cv,y(mcv)cv)}$\{(x_{cv}^{(1)},y_{cv}^{(1)}),\cdots ,(x_{cv}^{(m_{cv})},y_{cv}^{(m_{cv})})\}$
测试集：{(x(1)test,y(1)test),⋯,(x(mtest)test,y(mtest)test)}$\{(x_{test}^{(1)},y_{test}^{(1)}),\cdots ,(x_{test}^{(m_{test})},y_{test}^{(m_{test})})\}$
交叉验证集和测试集中包含异常样本。

举例：以飞机引擎为例
有10000$10000$个正常引擎，20$20$个异常引擎
(注：根据经验，通常y=1$y=1$的样本数为2∼50$2\sim 50$个，y=0$y=0$的样本很多)

一种典型的数据分类：
训练集：6000$6000$个正常引擎；
交叉验证集：2000$2000$个正常引擎(y=0$y=0$)，10$10$个异常引擎(y=1$y=1$)；
测试集：2000$2000$个正常引擎(y=0$y=0$)，10$10$个异常引擎(y=1$y=1$)；
正常引擎的划分比例为6:2:2$6:2:2$，异常引擎的划分比例为0:1:1$0:1:1$。

接下来：
在训练集{x(1),x(2),⋯,x(m)}$\{x^{(1)},x^{(2)},\cdots ,x^{(m)}\}$上拟合模型p(x)$p(x)$
在交叉验证集或测试集样本x$x$上，预测：

因为该类样本比较偏斜，所以用到的评价度量指标为：

• 查准率/召回率
• F1−score$F_1-score$

用交叉验证集选择参数ε$\epsilon$，尝试不同的ε$\epsilon$值，选出使F1−score$F_1-score$最大的那个ε$\epsilon$。

异常检测VS$VS$监督学习：

应用场景：

• 异常检测：正样本(y=1$y=1$)的数量很少(通常为0∼20$0\sim 20$)，负样本(y=0$y=0$)的数量很多；
• 监督学习：正、负样本的数量都很多。

补充说明：

• 异常检测：存在多种不同的异常情况，对于任何学习算法，都很难从少量的正样本中学习到异常的全部情况，很多未知的异常无法从现有样本中学到；
• 监督学习：对算法来说，有充足的正样本来学习正样本的样子，未来的正样本类似于训练集中的样本。

应用举例：

• 异常检测：欺诈检测、工业生产、数据中心的计算机监控；
• 监督学习：垃圾邮件分类、天气预测、癌症分类。

异常检测算法的特征变量选择：
当应用异常检测时，对它的效率影响最大的因素之一是使用什么特征变量。
在使用异常检测算法之前，可以通过画出特征变量取值来看其是否服从高斯分布(注：虽然不是高斯分布，算法也可以正常运行)

Octave$Octave$中画直方图用hist()$hist()$命令
如果数据不服从高斯分布，可以对数据进行一些转换，使其更像高斯分布。

例：
原特征变量分布如下图：

对其取log(x)$log(x)$转换，特征分布如下：

常见的转换方式：log(x)$log(x)$、log(x+1)$log(x+1)$、x−−√$\sqrt{x}$、x−−√3$\sqrt[3]{x}$等

如何得到异常检测算法的特征变量？
先完整的训练出一个学习算法，然后在一组交叉验证集上运行算法，找出那些预测出错的样本，再看看能否找到一些其他的特征变量，来帮助学习算法在那些交叉验证集判断出错的样本中表现得更好。

为异常检测算法选择特征变量时，选取那些通常取值不会特别大也不会特别小的特征变量。

多元高斯分布
存在特征x∈Rn$x\in R^n$，不要把p(x1),p(x2)⋯$p(x_1),p(x_2)\cdots$分开，而是建立一个p(x)$p(x)$整体的模型。

多元高斯分布的参数包括μ∈Rn$\mu \in R^n$，Σ∈Rn×n$\mathrm{\Sigma }\in R^{n\times n}$(协方差矩阵)
概率密度公式为：

|Σ|$|\mathrm{\Sigma }|$为Σ$\mathrm{\Sigma }$的行列式，Octave$Octave$中用det(Sigma)$det(Sigma)$实现。

不同μ$\mu$与Σ$\mathrm{\Sigma }$取值的概率密度曲线如下：

多元高斯分布的参数估计：
训练集{x(1),x(2),⋯,x(m)}$\{x^{(1)},x^{(2)},\cdots ,x^{(m)}\}$，x(i)∈Rn$x^{(i)}\in R^n$

基于多元高斯分布的异常检测算法：

1. 用训练集拟合模型p(x)$p(x)$
   
   μ=1m∑i=1mx(i)Σ=1m∑i=1m(x(i)−μ)(x(i)−μ)T$$\mu =\frac{1}{m}\sum _{i=1}^m{x}^{(i)}\mathrm{\Sigma }=\frac{1}{m}\sum _{i=1}^m(x^{(i)}-\mu )(x^{(i)}-\mu {)}^T$$
2. 对于一个新样本，计算
   
   p(x)=1(2π)n2|Σ|12exp(−12(x−μ)TΣ−1(x−μ))$$p(x)=\frac{1}{(2\pi {)}^{\frac{n}{2}}|\mathrm{\Sigma }{|}^{\frac{1}{2}}}exp(-\frac{1}{2}(x-\mu {)}^T{\mathrm{\Sigma }}^{-1}(x-\mu ))$$
   
   如果p(x)<ε$p(x)<\epsilon$，标记为异常。

原始模型：P(x)=p(x1;μ1,σ21)p(x2;μ2,σ22)⋯p(xn;μn,σ2n)$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 }_n^2)$
对应一种多元高斯分布模型：p(x;μ,Σ)=1(2π)n2|Σ|12exp(−12(x−μ)TΣ−1(x−μ))$p(x;\mu ,\mathrm{\Sigma })=\frac{1}{(2\pi {)}^{\frac{n}{2}}|\mathrm{\Sigma }{|}^{\frac{1}{2}}}exp(-\frac{1}{2}(x-\mu {)}^T{\mathrm{\Sigma }}^{-1}(x-\mu ))$
当Σ=⎡⎣⎢⎢⎢⎢⎢σ21σ22⋱σ2n⎤⎦⎥⎥⎥⎥⎥$\mathrm{\Sigma }=\left[\begin{array}{cccc}{\sigma }_1^2& & & \\ & {\sigma }_2^2& & \\ & & \ddots & \\ & & & {\sigma }_n^2\end{array}\right]$时。

原始模型VS$VS$多元高斯分布：
特征关联：

• 原始模型：手动新建一个特征值来捕捉x1,x2$x_1,x_2$不正常组合值的异常情况；
• 多元高斯分布：自动捕捉不同特征量之间的相关性。

运算量：

• 原始模型：运算量小，适用于特征变量很多(n$n$很大)的情况；
• 多元高斯分布：运算量大。

适用情况：

• 原始模型：当训练集很小(m$m$很小)时也适用；
• 多元高斯分布：m$m$必须大于n$n$(最好m⩾10n$m⩾10n$)，即样本数量一定要大于特征变量的数量。

当使用多元高斯分布时，如果发现Σ$\mathrm{\Sigma }$是不可逆的，通常有两种情况：

1. 不满足m>n$m>n$的条件；
2. 有冗余特征变量。