一、异常检测

1.1 目的

在接下来的一系列视频中，我将向大家介绍异常检测(Anomaly detection）问题。这是机器学习算法的一个常见应用。这种算法的一个有趣之处在于：它虽然主要用于非监督学习问题，但从某些角度看，它又类似于一些监督学习问题。什么是异常检测呢？为了解释这个概念，让我举一个例子吧：
假想你是一个飞机引擎制造商，当你生产的飞机引擎从生产线上流出时，你需要进行QA（质量控制测试），而作为这个测试的一部分，你测量了飞机引擎的一些特征变量，比如引擎运转时产生的热量，或者引擎的振动等等。这样一来，你就有了一个数据集，你将这些数据绘制成图表，如下图。

这时，有一个新的引擎，想知道这个引擎是否有异常，那么我们可以观察这个引擎在图表中的位置，得到其属于正常数据的概率 $p(x)$ 。如下图所示，越偏离蓝色圈的出现异常的概率越大。所以我们可以通过判断是否 $p(x)<\varepsilon$ ，来判断是否异常。

1.2 高斯分布

若随机变量服从一个位置参数为 $\mu$ 尺度参数为 $\sigma$ 的正态分布（高斯分布），记为： $X \sim N\left(\mu, \sigma^{2}\right)$ ，其概率密度函数为 $\frac{1}{\sigma \sqrt{2 \pi}} \exp \left(-\frac{(x-\mu)^{2}}{2 \sigma^{2}}\right)$ ，不同参数的图形如下图所示，其中 $\mu$ 决定图形中心点的位置， $\sigma$ 为图像距离中心的偏离程度，即决定图像的宽度，并且整个图像的积分恒为1（概率密度为1）。

对于一个数据集，我们可以预测其概率分布，参数的计算方法为， $\mu=\frac{1}{m} \sum_{i=1}^{m} x^{(i)}$ ， $\sigma^{2}=\frac{1}{m} \sum_{i=1}^{m}\left(x^{(i)}-\mu\right)^{2}$ 。

1.3 异常检测算法

对于给定的数据集 $x^{(1)} x^{(2)}...x^{(m)}$ ，我们要针对每一个特征 $x_j$ 计算 $μ$ 和 $σ^2$ 的估计值：

一旦我们获得了 $μ$ 和 $σ^2$ 的估计值，给定新的一个训练实例，根据模型计算：

当 $p(x)<\varepsilon$ 时，为异常。
当 $p(x)\ge\varepsilon$ 时，为正常。

如下图是一个由两个特征的训练集，以及特征的分布情况：

下面的三维图表表示的是密度估计函数，z 轴为根据两个特征的值所估计 p(x) 值：

我们选择一个 $ε$ ，将 $p(x)=ε$ 作为我们的判定边界，当 $p(x)>ε$ 时预测数据为正常数据，否则则为异常。

1.4 开发和评价异常检测系统

有一个可以量化的指标对于学习算法的评估是十分重要的，通过某些数值指标，我们可以很方便地判断当前系统的优劣。对于异常检测算法，我们先获得一些带标签的数据（ $y=0$ 表示正常， $y=1$ 表示异常），然后将数据分为三类：训练集、测试集、验证集。其中，训练集中的数据都是被认为是正常的数据，而在验证集和测试集中存在一些异常数据。

还是以飞机引擎为例，假设我们有10000个好引擎的数据以及20个异常引擎的数据，我们可以将数据集按照如下方式划分：

训练集：6000个好引擎
验证集：2000个好引擎+10个异常引擎
测试集：2000个好引擎+10个异常引擎

加下来我们可以进行系统的评估了：

在测试集上训练，得到模型 $p(x)$
在验证集/测试集上进行预测
得到混淆矩阵，由于数据有很大的偏斜，所以一般不用准确率来衡量，可以计算得到测准率和召回率，得到 $F_1$ 值。

1.5 异常检测和监督学习的对比

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

1.6 特征选择

对于异常检测算法，影响系统好坏的主要因素就是特征的选取，下面给出一些特征变量的设计和选择的建议。

异常检测假设特征符合高斯分布，如果数据的分布不是高斯分布，异常检测算法也能够工作，但是最好还是将数据转换成高斯分布，例如使用对数函数： $x = log(x+c)$ ，其中 c 为非负常数；或者 $x=x^c$ , c 为 0-1 之间的一个分数。

一个常见的问题是一些异常的数据可能也会有较高的 p(x) 值，因而被算法认为是正常的。这种情况下误差分析能够帮助我们，我们可以分析那些被算法错误预测为正常的数据，观察能否找出一些问题。我们可能能从问题中发现我们需要增加一些新的特征，增加这些新特征后获得的新算法能够帮助我们更好地进行异常检测。我们通常可以通过将一些相关的特征进行组合，来获得一些新的更好的特征（异常数据的该特征值异常地大或小）。

1.7 多元高斯分布

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

下图中是两个相关特征，洋红色的线（根据 ε 的不同其范围可大可小）是一般的高斯分布模型获得的判定边界，很明显绿色的 X 所代表的数据点很可能是异常值，但是其 p(x) 值却仍然在正常范围内。

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

$\mu$ 是一个向量，其每一个单元都是原特征矩阵中一行数据的均值。最后我们计算多元高斯分布的 p(x):

$|Σ|$ 是定矩阵（行列式）， $\Sigma^{-1}$ 表示逆矩阵，在 Matlab 中用 det(sigma) 计算，下面我们来看看协方差矩阵是如何影响模型的：

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

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

多元高斯分布模型与原高斯分布模型的关系：
可以证明的是，原本的高斯分布模型是多元高斯分布模型的一个子集，即像上图中的第1 、 2 、 3 个例子所示，如果协方差矩阵只在对角线的单位上有非零的时，即为原本的高斯分布模型了。

1.8 使用多元高斯分布进行异常检测

对于一组样本，按照下列方式估计 $\mu$ 和 $\Sigma$ ，其中 $\mu$ 为一个 n 维向量， $\Sigma$ 为协方差矩阵。

然后我们使用公式得到某个待检测样本的 $p(x)$ ，依此来预测是否出现异常。

原始高斯模型和多元高斯模型的对比：

二、推荐系统

2.1 产生目的

推荐系统，是机器学习中的一个重要的应用。大思想，并和大家分享。对机器学习来说，特征是很重要的，你所选择的特征，将对你学习算法的性能有很大的影响。因此，在机器学习中有一种大思想，对于某些问题，存在一种算法可以为你自动学习一套好的特征。因此，你不用手动设计特征，而目前为止我们通常是自己手动选择特征的。而推荐系统就是这样一种算法，可以学习得到数据的特征。

下面我们将以一个电影评分的例子来介绍推荐系统，首先对于这个例子进行一些定义。假使我们是一个电影供应商，我们有 5 部电影和 4 个用户，我们要求用户为电影打分，结果如下图所示，"?" 表示没有进行打分。我们希望构建一个算法来预测他们每个人可能会给他们没看过的电影打多少分，并以此作为推荐的依据。

下面引入一些标记：

$n_u$ 代表用户的数量，此例子中为4

$n_m$ 代表电影的数量，此例子中为5

$r(i,j)$ 表示如果用户 $i$ 给电影 $j$ 评过分则 $r(i,j)=1$

$y^(i,j)$ 代表用户 $i$ 给电影 $j$ 的评分

$m_j$ 代表用户 $j$ 评过分的电影的总数

2.2 基于内容的推荐系统

假设每个电影有两个属性 $x_1 x_2$ ，其中 $x_1$ 表示电影中的爱情元素， $x_2$ 表示电影中的动作元素。那么每一部电影都有一个特征向量，如 $x^{(1)}$ 表示第一部电影的特征向量，其值为 $\left[\begin{array}{l}1 \\0.9 \\0\end{array}\right]$ ，其中的 1 表示偏置项，不算入特征项。接着对于每个用户，我们都计算出一个 $\theta^{(j)} \in \R^3$ ，然后我们用 $(\theta^{(j)})^Tx^{(i)}$ 即可表示用户 $j$ 对于电影 $i$ 的预测评分。

而学习 $\theta$ 的过程就是一个线性回归的过程，即学习得到一个 $\theta$ 使得 $(\theta^{(j)})^Tx^{(i)}$ 更接近真实分数。具体来说，对于一个用户 $j$ ，求 $\theta^{(j)}$ 的代价函数如下：

对于整个系统来说，我们需要学习所有的 $\theta$ ,则：

上面是通过电影的特征向量去预测每个用户的评分，同样，我能可以利用用户的评分去预测出电影的特征，具体可以用下面的式子：

于是我们可以从 $\theta$ 开始或者从 $x$ 开始，循环更新，比如用 $\theta$ 得到 $x$ ,再用新的 $x$ 得到 $\theta$ 如此反复得到一个较好的结果。

2.3 协同过滤

在之前的基于内容的推荐系统中，对于每一部电影，我们都掌握了可用的特征，使用这些特征训练出了每一个用户的参数。相反地，如果我们拥有用户的参数，我们可以学习得出电影的特征。但是如果我们既没有用户的参数，也没有电影的特征，这两种方法都不可行了。协同过滤算法可以同时学习这两者。我们的优化目标便改为同时针对 $x$ 和 $θ$ 进行：

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

注：在协同过滤从算法中，我们通常不使用偏差项，即没有 $x_0 = 0$ ，因为我们现在是在学习所有的特征，所以没有必要将等于1的特征值固定死，如果算法真的需要一个特征值为1，那么他会自己学习到的。

协同过滤算法使用步骤如下：

初始 $x^{(1)}x^{(2)}...x^{(n_m)},\theta^{(1)}\theta^{(2)}...\theta^{(n_m)}$ 为一些随机小值。
使用梯度下降算法最小化代价函数。
在训练完算法后，我们预测 $(\theta^{(j)})^Tx^{(i)}$ 为用户 $j$ 给电影 $i$ 的评分。

通过这个学习过程获得的特征矩阵包含了有关电影的重要数据，这些数据不总是人能读懂的，但是我们可以用这些数据作为给用户推荐电影的依据。例如，如果一位用户正在观看电影 $x^{(i)}$ 我们可以依据两部电影的特征向量之间的距离的大小寻找另一部电影 $x^{(j)}$ ，然后推荐给他。

2.4 算法向量化及实现

向量化

推荐系统可以实现下面这样的功能：

当给出一件产品时，你能否找到与之相关的其它产品。

一位用户最近看上一件产品，有没有其它相关的产品，你可以推荐给他。

继续以电影推荐为例，我们有关于五部电影的数据集，首先将这些用户的电影评分，进行分组并存到一个矩阵 $Y$ 中。假设我们有五部电影，以及四位用户，那么这个矩阵 $Y$ 就是一个 5 行 4 列的矩阵，它将这些电影的用户评分数据都存在矩阵里。

接着，我们借助这个矩阵利用协同过滤，得到 $\theta$ 和 $x$ ，然后就可以进行预测，可以得到一个下面的矩阵，其中第 i 行第 j 个表示第 i 个电影根据第 j 个用户的评分，可以表述为 $\left(\theta^{(j)}\right)^{\top}\left(x^{(i)}\right)$ 。

现在将计算方法进行向量化，令 $X=\left[\begin{array}{c} -\left(x^{(1)}\right)^{\top}- \\ -\left(x^{(2)}\right)^{\top}- \\ \vdots \\ -\left(x^{\left(n_{m}\right)}\right)^{\top}- \end{array}\right]$ ， $\Theta=\left[\begin{array}{c} -\left(\theta^{(1)}\right)^{\top}- \\ -\left(\theta^{(2)}\right)^{\top}- \\ \vdots \\ -\left(\theta^{\left(n_{u}\right)}\right)^{\top}- \end{array}\right]$ ，那么上面的矩阵就可以用向量化的计算，即 $X\Theta^T$ 。

实现细节

现在假设我们有一个新的用户 Eve 没有给任何电影评分，我们来分析一下，推荐系统会预测什么评分。

首先给出代价函数：

由于他没给任何电影打分，所以 $\frac{1}{2} \sum_{(i, j): r(i, j)=1}\left(\left(\theta^{(j)}\right)^{T} x^{(i)}-y^{(i, j)}\right)^{2}$ 这一项就为0了，所以用户Eve的 $\theta$ 只由后面的正则项 $\frac{\lambda}{2} \sum_{j=1}^{n_{u}} \sum_{k=1}^{n}\left(\theta_{k}^{(j)}\right)^{2}$ 决定，由于是要最小化函数值，所以 $\theta^{(5)}$ 为一个零向量，所以预测的得分也都为0。这是不太希望的，因为对于一个没有打分的用户，也希望能推荐他一些电影。

所以我们就用均值归一化来实现，具体来说如下：

首先我们根据每个电影已有的打分记录来计算每个电影得分的平均值，记录在 $\mu$ 中，然后我们将 $Y$ 中的每个得分都减去对应电影的均值。接着用这个新的 $Y$ 进行训练并预测，预测的时候需要将之前减去的均值 $\mu_i$ 加回去，这样对于一个没有打分的用户的得分也不为0了。