异常检测
异常检测(Anomaly detection)问题是机器学习算法的一个常见应用。这个算法的一个有趣之处在于：它虽然主要用于非监督学习问题，但从某些角度看，它又类似于一些监督学习问题。
何为异常检测？
假想你是一个飞机引擎制造商，当你生产的飞机引擎从生产线上流出时，你需要进行QA(质量控制测试)，而作为这个测试的一部分，你测量了飞机引擎的一些特征变量\(x_j\)，比如引擎运转时产生的热量，或者引擎的振动等等。
收集了m个样本：\(x^1,...,x^m\)
这里的每个样本，都是无标签的数据。
这样，异常检测问题可以定义如下：我们假设后来有一天，你有一个新的飞机引擎（新的样本）从生产线上流出，而你的新飞机引擎（新的样本）有特征变量\(x_{test}\)。所谓的异常检测问题就是：我们希望知道这个新的飞机引擎（新的样本）是否有某种异常，或者说，我们希望判断这个引擎是否需要进一步测试。因为，如果它看起来像一个正常的引擎，那么我们可以直接将它运送到客户那里，而不需要进一步的测试。
一般化的描述是：
给定一个无标签数据集：\(\{x^1,...,x^m\}\)，我们假使数据集是正常的，我们希望知道新样本的特征\(x_{test}\)是不是异常的，即这个测试数据不属于该组数据的几率有多大。
那么我们就需要对这些样本构建一个分布概率模型p(x)。
当\(p(x_{test})\lt{\epsilon}\)时标记为异常，当\(p(x_{test})\ge{\epsilon}\)时标记为正常，\(\epsilon\)是给定的一个阈值。
上图中，在蓝色圈内的数据属于该组数据的可能性较高，而越是偏远的数据，其属于该组数据的可能性就越低。
异常检测常用领域
欺诈检测：
假设有很多个用户，每个用户都在从事不同的活动，可以对不同的用户活动计算特征。
我们用\(x^i\)表示用户的第i个活动的特征，可以看出一个活动就类似于一个样本。
构建模型p(x)表示某个活动（样本）属于某组数据的可能性。
当\(p(x)\lt{\epsilon}\)时表示用户活动异常。
也可以用在制造业上，如前面所说的飞机引擎。
还可以用于检测数据中心的计算机：
\(x^i\)表示第i台机器的特征。
也许特征\(x_1\)表示内存占用，特征\(x_2\)表示磁盘写入率，特征\(x_3\)表示CPU负载，特征\(x_4\)表示更为复杂的特征，如CPU负载和网络流量的比值。
根据这些特征可以构建一个模型，用来判断某些计算机是不是有可能出错了。
高斯分布（正态分布）
这一节主要回顾一下高斯分布的一些基本知识，考虑到考完研已经很长时间了。
随机变量x服从高斯分布（正态分布）表示为\(x~N(\mu，\sigma^2)\)
其概率密度函数为:\(p(x;\mu,\sigma^2)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{{(x-\mu)}^2}{2\sigma^2}}\)
服从高斯分布的变量的均值为\(\mu\)，方差为\(\sigma^2\)
\(\mu\)的几何意义即使密度函数图像取最大值的点
\(\sigma\)表示函数图像的宽度
\(\mu，\sigma\)对函数图像的影响如下图所示：
参数估计
假设有这样一个数据集\(\{x^1,...,x^m\}\quad{x^i}\in{R}\)
我们猜测这些个\(x^i\)样本服从正态分布，\(x~N(\mu，\sigma^2)\)，参数估计要做的就是，给定数据集，去找出\(\mu，\sigma^2\)的值。
根据概率论的知识，容易得到：
均值\(\mu=\frac{1}{m}\sum^m_{i=1}x^i\)，方差\(\sigma^2=\frac{1}{m}\sum^m_{i=1}{(x^i-\mu)}^2\)
机器学习中，对于参数估计通常使用\(\frac{1}{m}\)，而非统计学中的\(\frac{1}{m-1}\)。
在实际的应用当中，\(\frac{1}{m}\)还是\(\frac{1}{m-1}\)其实区别很小，只要有一个比较大的训练集，在机器学习领域大部分人更习惯使用这个版本的公式。
以\(\frac{1}{m}\)和\(\frac{1}{m-1}\)为系数的公式在理论特性和数学特性上稍有不同，但是在实际使用中，他们的区别非常小。
算法
异常检测算法的效力是以高斯分布（正态分布）为基础的。
高斯分布是自然界最为普遍的分布（或许没有之一）。
高斯分布之所以如此普遍，由统计学的知识可略窥一二，根据中心极限定理，如果一个变量受到若干独立因素的共同影响，且每个因素不能产生决定性的影响，那么这个变量服从中心极限定理，最终会收敛到高斯分布。
那么给定一个数据集\(\{x^1,...,x^m\}\quad{x^i}\in{R}\)，对每个特征（\(x_j\)）计算其均值\(\mu_j=\frac{1}{m}\sum^m_{i=1}x^i_j\)，方差\(\sigma^2_j=\frac{1}{m}\sum^m_{i=1}{(x^i_j-\mu_j)}^2\)。
完成了参数估计之后，引入一个新的样本，也就是欲检测是否异常的样本。计算如下式子的值：
当\(p(x)\lt\epsilon\)时，说明该样本异常。
捋一下异常检测算法的流程：
- 选择你认为会表明样本异常的特征\(x_j\)
- 进行参数估计
- 给出欲检测的样本，计算p(x)的值，选择合适的\(\epsilon\)值进行判断。
下面是一个有两个特征的数据集的例子：
特征\(x_1\)对应的\(\mu_1=5,\sigma_1=2\)
特征\(x_2\)对应的\(\mu_2=3,\sigma_2=1\)
因为是二维高斯分布，所以可以作出三维的密度函数图像：
开发和评估异常检测算法
异常检测算法是一个无监督学习算法，意味着将没有y值来给我们判断结果是否正确合理。
以飞机引擎为例子：
假设我们有一些经标识的，可以区分异常与否的数据（y=0表示正常，y=1表示异常），比如说有10000个正常的引擎，20个异常的引擎。我们这样划分为3个集合：
训练集：6000正常 0异常
交叉验证集：2000正常 10异常
测试集：2000正常 10异常
按照6：2：2的比例划分
评估异常检测的过程如下：
- 用训练集数据去拟合分布模型p(x)
- 对交叉验证集或者测试集上的任一样本预测其y值\(y=\begin{cases}1&{p(x)\lt\epsilon}\\\\0&{p(x)\ge\epsilon}\end{cases}\)
- 考虑到这是一个偏斜类，因为实际生产中，异常的总是少数，所以考虑到之前学过的查准率和召回率的应用，或者\(F_1\)值
- 根据评估度量查准率和召回率的应用，或者\(F_1\)值，来选择参数\(\epsilon\)
异常检测与监督学习
在评估异常检测算法的时候，我们用到了经标记的数据，而只有监督学习算法才会使用带标签的数据。这样就出现了问题，假如数据集中出现了“正确答案”，那么异常检测算法为何还要划分为无监督学习算法？
| 异常检测 | 监督学习 |
|---|---|
| 非常少量的正类（异常y=1）, 大量的负类（正常y=0） | 同时有大量的正类和负类 |
| 存在许多不同种类的异常，很难从极少量的正类中学习异常到底是什么。尤其是未来遇到的异常可能与已掌握的异常、非常的不同。 | 有足够多的正类，足够用于训练算法。未来遇到的正类可能与训练集中的非常近似。 |
| 例如： 欺诈行为检测 、生产（例如飞机引擎）、检测数据中心的计算机运行状况 | 例如：邮件过滤器、天气预报、肿瘤分类 |
总之，我个人理解就是，异常检测的数据集是非常非常偏斜的，正类数量和负类数量极其不平衡。
对于异常检测中的欺诈检测，其实如果在网站上有很多欺诈行为的样本，那么是可以转换成类似邮件分类的监督学习问题的。
特征的选择
对于异常检测算法，特征的选用是至关重要的，下面谈谈如何选择特征：
在异常检测中，我们所使用的特征常常都是服从高斯分布的，如果特征不服从，异常检测算法也可以正常工作，但是如果将数据转换为高斯分布的话，从感觉上或者经验上来说，算法会运行得更好。
业内常使用原特征作为对数函数\(x_j=\log(x_j+c)\quad{c为非负常数}\)或者\(x_j=x_j^c\quad{c为0-1之间的实数}\)，那么函数图像也许会变得更像高斯分布密度函数图像：
误差分析
一个常见的问题是一些异常的数据可能也会有较高的p(x)值，因而被算法认为是正常的。
这种情况下误差分析能够帮助我们，我们可以分析那些被算法错误预测为正常的数据，思考能够能从问题中发现我们需要增加一些新的特征，增加的新特征能够提高学习算法的性能。
我们通常可以通过将一些相关的特征进行组合，来获得一些新的更好的特征（异常数据的该特征值异常地大或小），例如，在检测数据中心的计算机状况的例子中，我们可以用CPU负载与网络通信量的比例作为一个新的特征，如果该值异常地大，便有可能意味着该服务器是陷入了一些问题中。
多元高斯分布
假使我们有两个相关的特征，而且这两个特征的值域范围比较宽，这种情况下，一般的高斯分布模型可能不能很好地识别异常数据。其原因在于，一般的高斯分布模型尝试的是去同时抓住两个特征的偏差，因此拟合出一个比较大的判定边界。
（一般的高斯分布模型会尝试拟合出如洋红色圈那样的一个判定边界）
在一般的高斯分布模型中，我们计算 的方法是： 通过分别计算每个特征对应的几率p(x)然后将其累乘起来。
而在多元高斯分布中，首先要计算出所有特征的均值，然后计算协方差矩阵：
\(\mu_j=\frac{1}{m}\sum^m_{i=1}x^i_j\)
\(\Sigma=\frac{1}{m}\sum^m_{i=1}{(x^i-\mu)}{(x^i-\mu)}^T=\frac{1}{m}{(X-\mu)}^T{(X-\mu)}\)
其中：\(\mu=\begin{bmatrix}\mu_1\\\\\mu_2\\\\...\\\\\mu_n\end{bmatrix}\quad{x}=\begin{bmatrix}x_1\\\\x_2\\\\...\\\\x_n\end{bmatrix}\quad{x^i}=\begin{bmatrix}x^i_1\\\\x^i_2\\\\...\\\\x^i_n\end{bmatrix}\)
上图是3个不同的模型，从左往右依次分析：
- 是一个一般的高斯分布模型
- 通过协方差矩阵，令特征2拥有较小的偏差，同时保持特征1的偏差
- 通过协方差矩阵，令特征2拥有较大的偏差，同时保持特征1的偏差
可以证明的是，原本的高斯分布模型是多元高斯分布模型的一个子集，即像上图中3个例子所示，如果协方差矩阵只在对角线的单位上有非零的值时，即为原本的高斯分布模型了。
下图反映了改变\(\mu\)值对密度函数图像的影响。
异常检测with多元高斯分布
- 通过参数估计求出均值和方差来拟合模型p(x)：
\(\mu_j=\frac{1}{m}\sum^m_{i=1}x^i_j\)
\(\Sigma=\frac{1}{m}\sum^m_{i=1}{(x^i-\mu)}{(x^i-\mu)}^T=\frac{1}{m}{(X-\mu)}^T{(X-\mu)}\) - 给定一个新样本x，计算p(x)的值：
- 如果\(p(x)\lt\epsilon\)，则样本异常。
原高斯分布模型和多元高斯分布模型的比较：
| 原高斯分布模型 | 多元高斯分布模型 |
|---|---|
| 不能捕捉特征之间的相关性，但可以通过将特征进行组合的方法来解决 | 自动捕捉特征之间的相关性 |
| 计算代价低，能适应大规模的特征 | 计算代价较高，训练集较小时也同样适用 |
| 必须要有 \(m\gt{n}\),不然的话协方差矩阵 不可逆的，通常需要\(m\gt{10n}\)另外特征冗余也会导致协方差矩阵不可逆 |
原高斯分布模型使用广泛，但是如果特征之间在某种程度上存在相互关联的情况，我们可以通过使用构造新特征的方法来捕捉这些相关性。
如果训练集不是太大，并且没有太多的特征，我们可以使用多元高斯分布模型。