异常检测(Anomaly Detection)

Andrew Ng老师的机器学习入门基础课程算是学完了，所谓”学而不思则惘，思而不学则殆”·，复盘一下学习情况和理解程度还是很有必要的，不过要交毕业论文啦，肝完毕设再来更博。

动机(Motivation)

异常检测主要应用于非监督学习问题，但是却类似于监督学习问题。
给定数据集，我们假使数据集是正常的，我们希望知道新的数据 xtest是不是异常的，即这个测试数据不属于该组数据的几率如何。我们所构建的模型应该能根据该测试数据的位置告诉我们其属于一组数据的可能性$p(x)$。

上图中，在蓝色圈内的数据属于该组数据的可能性较高，而越是偏远的数据，其属于该组数据的可能性就越低。
这种方法称为密度估计

$if \quad p(x) \begin{cases} \leq\epsilon, & \text {anomaly} \\ >\epsilon, & \text{normal} \end{cases}$

高斯分布

高斯分布也称为正态分布。变量$x$符合高斯分布$x~N(\mu,\sigma^2)$则其概率密度函数为:

$p(x,\mu,\sigma^2)=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(x-\mu)^2}{2\sigma^2})$

可以利用已有数据来预测总体中的$\mu$和$\sigma^2$:

$\mu=\frac{1}{m}\sum_{i=1}^{m}x^{(i)}$ $\sigma^2 = \frac{1}{m}\sum\_{i=1}^{m}(x^{(i)}-\mu)^2$

算法

对于给定数据集$x^{(1)},x^{(2)},x^{(3)}$，预测$\mu$和$\sigma^2$的值。给定一个训练实例，根据模型计算$p(x)$。

$p(x) = \prod_{j=1}^np(x_j,u_j,\sigma_j^2)=\prod_{j=1}^n\frac{1}{\sqrt{2\pi}\sigma_j}exp(-\frac{(x_j-u_j)^2}{2\sigma_j^2})$

开发异常检测系统

根据训练集数据，估计特征的平均值和方差并构建$p(x)$函数，一般训练集数据都是正常数据。
对交叉检验集，尝试使用不同的$\epsilon$作于阈值，根据$F_1$或者查准率、查全率的比例来选择$\epsilon$。
选出$\epsilon$后，对测试集进行预测，计算异常检测系统的$F_1$或者查全率、查准率之比。

异常检测监督学习的比较

异常检测	监督学习
少量正向类，大量负向类	同时有大量正向和负向类
有许多不同种类的异常，未来遇到的异常可能与已掌握的异常非常不同根据非常少量的正向类数据来训练算法	有足够多的正向类实例，足够用于训练算法，未来遇到的正向类实例可能与训练集中的非常近似
欺诈行为检测、生产(例如飞机引擎检测)、检测数据中心计算机运行状况	邮件过滤、天气预报、肿瘤分类

选择特征

异常检测特征符合高斯分布，如果数据的分布不是高斯分布，异常检测算法也能工作，但是最好将数据转换为高斯分布，常用对数函数$x=log(x+c)$、$x=x^c(c为0-1之间的一个分数)$。

误差分析：
分析那些被算法错误预测为正常的数据，观察能否找出一些问题。我们可能从问题中发现需要增加一些新的特征，增加这些新特征后获得的新算法能够帮助我们更好地进行异常检测。
通常可以通过将一些相关的特征进行组合，来获得一些新的更好的特征（异常数据的该特征值异常地大或小。

多元高斯分布

假使我们有两个相关的特征，而且这两个特征的值域范围比较宽，这种情况下，一般的高斯分布模型可能不能很好地识别异常数据。其原因在于，一般的高斯分布模型尝试的是去同时抓住两个特征的偏差，因此创造出一个比较大的判定边界。

在一般的高斯分布模型中，我们计算的方法是：通过分别计算每个特征对应的几率然后将其累乘起来，在多元高斯分布模型中，我们将构建特征的协方差矩阵，用所有的特征一起来计算。

$\mu=\frac{1}{m}\sum_{i=1}^{m}x^{(i)}$ $\Sigma=\frac{1}{m}(x^{(i)}-\mu)(x^{(i)}-\mu)^T=\frac{1}{m}(X-\mu)^T(X-\mu)$ $p(x) = \frac{1}{(2\pi^{\frac{n}{2}})|\Sigma|^{\frac{1}{2}}}exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))$

$|\Sigma|$是定矩阵，在Octave中用det(sigma)计算

协方差矩阵如何影响模型

上图是5个不同的模型，从左往右依次分析：

是一个一般的高斯分布模型；
通过协方差矩阵，令特征1拥有较小的偏差，同时保持特征2的偏差；
通过协方差矩阵，令特征2拥有较大的偏差，同时保持特征1的偏差；
通过协方差矩阵，在不改变两个特征的原有偏差的基础上，增加两者之间的正相关性；
通过协方差矩阵，在不改变两个特征的原有偏差的基础上，增加两者之间的负相关性。

多元高斯分布与原高斯分布模型的比较

原高斯分布模型	多元高斯分布模型
不能捕捉特征之间的相关性，但可以通过将特征进行组合的方法来解决	自动捕捉特征之间的相关性
计算代价低，能适应大规模的特征	计算代价较高训练集较小时也同样适用
-	必须满足 m>n，不然协方差矩阵不可逆。通常须 m > 10n。另外，特征冗余也会导致协方差矩阵不可逆

原高斯分布模型被广泛使用着，如果特征之间在某种程度上存在相互关联的情况，我们可以通过构造新新特征的方法来捕捉这些相关性。如果训练集不是太大，并且没有太多的特征，我们可以使用多元高斯分布模型。

推荐系统

基于内容的推荐

变量描述

$\theta^{(j)}$用户j的参数向量
$x^{(i)}$电影i的特征向量
对于用户j和电影i，我们预测评分为$(\theta^{(j)}x^{(i)})$
$n_u$用户的数量
$n_m$电影的数量
$r(i,j)$评分记录
$y(i,j)$用户i给电影j评分
$m_j$用户j评分过的电影总数

代价函数

$min\frac{1}{2}\sum\_{i:r(i,j)=1}((\theta^{(j)})^Tx^i-y^{(i,j)})^2 + \frac{\lambda}{2}(\theta_k^{(j)})^2$

其中 i :r(i,j) 表示我们只计算那些用户j评过分的电影。在一般的线性回归模型中，误差项和正则项应该都是乘以1/2m，在这里我们将m去掉。并且我们不对方差项进行正则化处理。
为了学习所有用户的参数，代价函数为：

梯度下降更新公式为：

$\theta_k^{(j)}:=\theta_k^{(j)}-\alpha\sum\_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)} \quad k=0$ $\theta_k^{(j)}:=\theta_k^{(j)}-\alpha(\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)} + \lambda\theta_k^{(j)} \quad k\neq0$

协同过滤

在之前的基于内容的推荐系统中，对于每一部电影，我们都掌握了可用的特征，使用这些特征训练出了每一个用户的参数。相反地，如果我们拥有用户的参数，我们可以学习得出电影的特征。

但是如果我们既没有用户的参数，也没有电影的特征，这两种方法都不可行了。协同过滤算法可以同时学习这两者。
我们的优化目标便改为同时针对$x$和$\theta$进行：

对代价函数求偏导的结果如下：

初始 $x$,$\theta$为一些随机小值；
使用梯度下降算法最小化代价函数；
在训练完算法后，我们预测$(\theta^{(j)})^Tx^{(i)}$为用户 j 给电影 i 的评分。
如果一位用户正在观看电影，我们可以寻找另一部电影，依据两部电影的特征向量之间的距离$||x^{(i)}-x^{(j)}||$ 的大小来判断电影的相似度。

均值归一化

如果已有数据如图

我们首先需要对结果 Y 矩阵进行均值归一化处理，将每一个用户对某一部电影的评分减去所有用户对该电影评分的平均值：

然后我们利用这个新的 Y，矩阵来训练算法。对于Eve，我们的新模型会认为她给每部电影的评分都是该电影的平均分。