🎍 异常检测 Anomaly Detection

一、什么是异常检测

在接下来的一系列视频中，我将向大家介绍异常检测(Anomaly detection)问题。这是机器学习算法的一个常见应用。这种算法的一个有趣之处在于：它虽然主要用于非监督学习问题，但从某些角度看，它又类似于一些监督学习问题。

❓ 什么是异常检测呢？为了解释这个概念，举一个例子吧：

假想你是一个飞机引擎制造商，当你生产的飞机引擎从生产线上流出时，你需要进行QA(质量控制测试)，而作为这个测试的一部分，你测量了飞机引擎的一些特征变量，比如引擎运转时产生的热量，或者引擎的振动等等。

这样一来，你就有了一个数据集，从$x^{(1)}$到$x^{(m)}$，如果你生产了$m$个引擎的话，你将这些数据绘制成图表，看起来就是这个样子：

这里的每个点、每个叉，都是你的无标签数据。这样，⭐ 异常检测问题可以定义如下：我们假设后来有一天，你有一个新的飞机引擎从生产线上流出，而你的新飞机引擎有特征变量$x_{test}$。所谓的异常检测问题就是：我们希望知道这个新的飞机引擎是否有某种异常，或者说，我们希望判断这个引擎是否需要进一步测试。如果它看起来像一个正常的引擎，那么我们可以直接将它运送到客户那里，而不需要进一步的测试。

给定数据集 $x^{(1)},x^{(2)},..,x^{(m)}$，我们希望知道新的数据样本 $x_{test}$ 是不是异常的。我们要采取的方法是对数据进行建模 p(x) ，即对 x 的分布概率进行建模，x 就是这些特征变量。⭐ 如果 $p(x_{test}) < ε$ 或者说 $x_{test}$ 出现的概率较低，我们就认为这个数据是异常的，如果$p(x_{test}) >= ε$ 或者说 $x_{test}$ 出现的概率较高，我们就认为这个数据是正常的。

🚩 如下图，在第一层蓝色圈内出现数据的概率最高，第二层蓝色圈其次...... 而越是偏远的数据，出现的可能性就越低。

这种方法称为密度估计，表达如下：

🔊 异常检测最常见的应用是欺诈检测 Fraud detection

🚩 欺诈检测：

$x^{(i)} = {用户的第i个活动特征}$
模型$p(x)$ 用来表示用户表现出各种行为的可能性，或者说用来表示用户行为对应的特征向量出现的概率。通过$p(x) < \varepsilon$检测非正常用户。

异常检测主要用来识别欺骗。例如在线采集而来的有关用户的数据，一个特征向量中可能会包含如：用户多久登录一次，访问过的页面，在论坛发布的帖子数量，甚至是打字速度等。尝试根据这些特征构建一个模型，可以用这个模型来识别那些不符合该模式的用户。

再一个例子是检测一个数据中心，特征可能包含：内存使用情况，被访问的磁盘数量，CPU的负载，网络的通信量等。根据这些特征可以构建一个模型，用来判断某些计算机是不是有可能出错了。

二、高斯分布 Gaussian Distribution

本节将介绍高斯分布（也称为正态分布），回顾高斯分布的基本知识：

通常如果我们认为变量 $x$ 符合高斯分布 $x \sim N(\mu, \sigma^2)$，则其概率密度函数为： $p(x,\mu,\sigma^2)=\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)$ 我们可以利用已有的数据来预测总体中的 $μ$ 平均值和 $σ^2$ 方差的计算方法如下：

平均值：$\mu=\frac{1}{m}\sum\limits_{i=1}^{m}x^{(i)}$
方差：$\sigma^2=\frac{1}{m}\sum\limits_{i=1}^{m}(x^{(i)}-\mu)^2$ （方差表示的是一组数据相对于平均数 μ 的离散程度）

⭐ 高斯分布的意义：根据距离中心值(平均值)的距离，对应图像的面积即是对应的概率

💬 高斯分布样例：

🚩 机器学习中对于方差我们通常只除以$m$而非统计学中的$(m-1)$。

在实际使用中，到底是选择使用$1/m$还是$1/(m-1)$其实区别很小，只要你有一个还算大的训练集，在机器学习领域大部分人更习惯使用$1/m$这个版本的公式。这两个版本的公式在理论特性和数学特性上稍有不同，但是在实际使用中，他们的区别甚小，几乎可以忽略不计。

💡 高斯分布高的意义：离散程度（σ）大一点，那么这个纵轴就需要配合着降低点高度。因为图形面积（概率密度）要保证在距离中心位置（μ）的 σ 标准差范围内是一个固定值；这里也是体现正态分布纵轴（高度）的意义。

下图可以看出，在若干倍的 σ 范围内的概率分布。所以高斯分布都是前人准备好的，根据横轴就能得出概率密度了。

三、应用高斯分布开发异常检测算法

对于给定的数据集 $x^{(1)},x^{(2)},...,x^{(m)}$，我们要针对每一个特征利用高斯分布计算 $\mu$ 和 $\sigma^2$ 的估计值：

$\mu_j=\frac{1}{m}\sum\limits_{i=1}^{m}x_j^{(i)}$
$\sigma_j^2=\frac{1}{m}\sum\limits_{i=1}^m(x_j^{(i)}-\mu_j)^2$

一旦我们获得了平均值和方差的估计值，给定新的一个训练实例，根据模型计算 $p(x)$：

⭐ $p(x)=\prod\limits_{j=1}^np(x_j;\mu_j,\sigma_j^2)=\prod\limits_{j=1}^1\frac{1}{\sqrt{2\pi}\sigma_j}exp(-\frac{(x_j-\mu_j)^2}{2\sigma_j^2})$

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

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

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

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

四、开发和评价一个异常检测系统

⭐ 异常检测算法是一个非监督学习算法，意味着我们无法根据结果变量 $ y$ 的值来告诉我们数据是否真的是异常的。我们需要另一种方法来帮助检验算法是否有效。

当我们开发一个异常检测系统时，我们从带标记（异常或正常）的数据着手，从其中选择一部分正常数据用于构建训练集，然后用剩下的正常数据和异常数据混合的数据构成交叉检验集和测试集。

例如：我们有10000台正常引擎的数据，有20台异常引擎的数据。我们这样分配数据：

6000台正常引擎的数据作为训练集
2000台正常引擎和10台异常引擎的数据作为交叉检验集
2000台正常引擎和10台异常引擎的数据作为测试集

⭐ 具体的评价方法如下：

根据测试集数据，我们估计特征的平均值和方差并构建$p(x)$函数
对交叉检验集，我们尝试使用不同的$\varepsilon$值作为阀值，并预测数据是否异常，根据$F1$值或者查准率与查全率的比例来选择 $\varepsilon$
选出 $\varepsilon$ 后，针对测试集进行预测，计算异常检验系统的$F1$值，或者查准率与查全率之比

五、异常检测与监督学习对比

💡 之前我们构建的异常检测系统也使用了带标记的数据，与监督学习有些相似，下面的对比有助于选择采用监督学习还是异常检测：

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

对于很多技术公司可能会遇到的一些问题，通常来说，🚩 正样本的数量很少，甚至有时候是0，也就是说，出现了太多没见过的不同的异常类型，那么对于这些问题，通常应该使用的算法就是异常检测算法。

六、选择特征

🔎 对于异常检测算法，我们使用的特征是至关重要的，下面谈谈如何选择特征：

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

💡 在python中，通常用np.log1p()函数，$log1p$就是 $log(x+1)$，可以避免出现负数结果，反向函数就是np.expm1()

误差分析：

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

异常检测误差分析：

我们通常可以通过将一些相关的特征进行组合，来获得一些新的更好的特征（异常数据的该特征值异常的大或小）。例如，在检测数据中心的计算机状况的例子中，我们可以用CPU负载与网络通信量的比例作为一个新的特征，如果该值异常地大，便有可能意味着该服务器是陷入了一些问题中。

七、多元高斯分布（选修）

八、使用多元高斯分布进行异常检测（选修）

✍ Quiz

① 第 1 题

对于下列哪一个问题，异常检测是一个合适的算法？

给定一张脸的图像，确定它是否是某个特定名人的脸。
✅ 给定信用卡交易的数据集，识别异常交易，将其标记为可能存在欺诈。
给定信用卡交易的数据，根据购买类型对每个交易进行分类（例如：食物、交通工具、衣服）。
✅ 从大量的初级保健患者记录中，找出可能有异常健康状况的个人。

② 第 2 题

假设您已经训练了一个异常检测系统，当 p(x) < ϵ 时标记异常，并且您在交叉验证集中发现它有太多的误报（标记太多的东西为异常）。你该怎么办？

增大 ϵ
✅ 减小 ϵ

③ 第 3 题

假设您正在开发一个异常检测系统来捕获飞机发动机中的制造缺陷。你的模型用 $p(x) = \prod_{j=1}^n p(x_j ; \mu_j, \sigma^2_j)$。有两个特性 x1 = 振动强度，x2 = 产生的热量，x1,x2的值都在0到1之间（并且严格大于0）。对于大多数“正常”发动机，你期望 x1≈x2。其中一个可疑的异常是，即使不产生太多热量，发动机也会剧烈振动（大x1，小x2），即使x1和x2的特定值可能不在其典型值范围之外。您应该构造哪些特征x3来捕获这些类型的异常：

$x_3 = x_1^2 \times x_2$
✅ $x_3 = \frac{x_1}{x_2}$
$x_3 = x_1 + x_2$
$x_3 = x_1 \times x_2$

④ 第 4 题

以下哪项是正确的？选择所有正确项

✅ 如果没有任何标记的数据（或者如果所有数据都有标记y=0），则仍然可以学习p(x)，但可能更难评估系统或选择一个好的值。
如果你有一个带有许多正例子和许多负例子的训练集，那么异常检测算法的性能可能与有监督的学习算法（如支持向量机）一样好。
如果您正在开发异常检测系统，则无法使用标记的数据来改进您的系统。
✅ 在为异常检测系统选择特征时，最好为异常示例寻找具有异常大值或小值的特征。

⑤ 第 5 题

您有一个一维数据集 ${x^{(1)}, \ldots, x^{(m)}}$，并且希望检测数据集中的异常值。首先绘制数据集，它如下所示：

假设将高斯分布参数 $\mu_1,\sigma^2_1$ 拟合到此数据集。对于 $\mu_1,\sigma^2_1$，可以得到下列哪个值？

✅ $\mu_1 = -3, \sigma_1^2 = 4$
$\mu_1 = -6, \sigma_1^2 = 4$
$\mu_1 = -3, \sigma_1^2 = 2$

📮 推荐系统 Recommender Systems

一、推荐系统问题形式化

我们从一个例子开始定义推荐系统的问题：

假使我们是一个电影供应商，我们有 5 部电影和 4 个用户，我们要求用户为电影打分。

前三部电影是爱情片，后两部则是动作片，我们可以看出Alice和Bob似乎更倾向与爱情片，而 Carol 和 Dave 似乎更倾向与动作片。并且没有一个用户给所有的电影都打过分。我们希望构建一个算法来预测他们每个人可能会给他们没看过的电影打多少分，并以此作为推荐的依据。

下面引入一些标记：

$n_u$ 代表用户的数量

$n_m$ 代表电影的数量

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

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

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

二、基于内容的推荐系统 Content Based Recommendations

在一个基于内容的推荐系统算法中，我们假设对于我们希望推荐的东西有一些数据，这些数据是有关这些东西的特征。

在我们的例子中，我们可以假设每部电影都有两个特征，如$x_1$代表电影的浪漫程度，$x_2$ 代表电影的动作程度。

则每部电影都有一个特征向量，如$x^{(1)}$是第一部电影的特征向量为 [0.9 0]。

下面我们要基于这些特征来构建一个推荐系统算法。假设我们采用线性回归模型，我们可以针对每一个用户都训练一个线性回归模型，如 ${{\theta }^{(1)}}$ 是第一个用户的模型的参数。于是，我们有：

$\theta^{(j)}$ 表示用户 $j$ 的参数向量
$x^{(i)}$ 表示电影 $i$ 的特征向量

对于用户 $j$ 和电影 $i$，我们预测评分为：$(\theta^{(j)})^T x^{(i)}$

针对用户 $j$，该线性回归模型的代价函数为预测误差的平方和，加上正则化项： ⭐ $$ \min_{\theta (j)}\frac{1}{2}\sum_{i:r(i,j)=1}\left((\theta^{(j)})^Tx^{(i)}-y^{(i,j)}\right)^2+\frac{\lambda}{2}\left(\theta_{k}^{(j)}\right)^2 $$

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

上面的代价函数只是针对一个用户的，为了学习所有用户，我们将所有用户的代价函数求和： $$ \min_{\theta^{(1)},...,\theta^{(n_u)}} \frac{1}{2}\sum_{j=1}^{n_u}\sum_{i:r(i,j)=1}\left((\theta^{(j)})^Tx^{(i)}-y^{(i,j)}\right)^2+\frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}(\theta_k^{(j)})^2 $$ 如果我们要用梯度下降法来求解最优解，我们计算代价函数的偏导数后得到梯度下降的更新公式为：

$$ \theta_k^{(j)}:=\theta_k^{(j)}-\alpha\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_{k}^{(i)} \quad (\text{for} , k = 0) $$

$$ \theta_k^{(j)}:=\theta_k^{(j)}-\alpha\left(\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_{k}^{(i)}+\lambda\theta_k^{(j)}\right) \quad (\text{for} , k\neq 0) $$

三、协同过滤 Collaborative Filtering

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

$$ \mathop{min}\limits_{x^{(1)},...,x^{(n_m)}}\frac{1}{2}\sum_{i=1}^{n_m}\sum_{j{r(i,j)=1}}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^{n}(x_k^{(i)})^2 $$ 。

但是如果我们既没有用户的参数，也没有电影的特征，这两种方法都不可行了。协同过滤算法可以同时学习这两者。

我们的优化目标便改为同时针对$x$和$\theta$进行。 $$ J(x^{(1)},...x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)})=\frac{1}{2}\sum_{(i:j):r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^{n}(x_k^{(j)})^2+\frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}(\theta_k^{(j)})^2 $$

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

$$ x_k^{(i)}:=x_k^{(i)}-\alpha\left(\sum_{j:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)}\theta_k^{j}+\lambda x_k^{(i)}\right) $$

$$ \theta_k^{(i)}:=\theta_k^{(i)}-\alpha\left(\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)}x_k^{(i)}+\lambda \theta_k^{(j)}\right) $$

在协同过滤从算法中，我们通常不使用方差项，如果需要的话，算法会自动学得。

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

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

通过这个学习过程获得的特征矩阵包含了有关电影的重要数据，这些数据不总是能读懂的，但是我们可以用这些数据作为给用户推荐电影的依据。

⭐ 协同过滤算法指的是当你执行算法时，要观察大量的用户，来协同地得到更佳的每个人对电影的评分值，因为如果每个用户都对一部分电影做出了评价，那么每个用户都在帮助算法学习出更合适的特征，然后学习出来的特征，又可以被用来更好地预测其他用户的评分

四、协同过滤算法

协同过滤优化目标：

给定$x^{(1)},...,x^{(n_m)}$，估计$\theta^{(1)},...,\theta^{(n_u)}$： $$ \min_{\theta^{(1)},...,\theta^{(n_u)}}\frac{1}{2}\sum_{j=1}^{n_u}\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}(\theta_k^{(j)})^2 $$

给定$\theta^{(1)},...,\theta^{(n_u)}$，估计$x^{(1)},...,x^{(n_m)}$：

同时最小化$x^{(1)},...,x^{(n_m)}$和$\theta^{(1)},...,\theta^{(n_u)}$： $$ J(x^{(1)},...,x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)})=\frac{1}{2}\sum_{(i,j):r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^{n}(x_k^{(i)})^2+\frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}(\theta_k^{(j)})^2 $$

$$ \min_{x^{(1)},...,x^{(n_m)} \ \theta^{(1)},...,\theta^{(n_u)}}J(x^{(1)},...,x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)}) $$

五、向量化：低秩矩阵分解 Low Rank Matrix Factorization

本节中我将会讲到有关协同过滤算法的向量化实现，以及说说有关该算法你可以做的其他事情。

举例子：

当给出一件产品时，你能否找到与之相关的其它产品。
一位用户最近看上一件产品，有没有其它相关的产品，你可以推荐给他。

我将要做的是：实现一种选择的方法，写出协同过滤算法的预测情况。

我们有关于五部电影的数据集，我将要做的是，将这些用户的电影评分，进行分组并存到一个矩阵中。

我们有五部电影，以及四位用户，那么这个矩阵 $Y$ 就是一个5行4列的矩阵，它将这些电影的用户评分数据都存在矩阵里：

Movie	Alice (1)	Bob (2)	Carol (3)	Dave (4)
Love at last	5	5	0	0
Romance forever	5	?	?	0
Cute puppies of love	?	4	0	?
Nonstop car chases	0	0	5	4
Swords vs. karate	0	0	5	?

推出评分：

找到相关影片：

🚩 我们有一个很方便的方法来度量两部电影之间的相似性。例如说：电影 $i$ 有一个特征向量$x^{(i)}$，找到一部不同的电影 $j$，保证两部电影的特征向量之间的距离$x^{(i)}$和$x^{(j)}$很小，那就能很有力地表明电影$i$和电影 $j$ 在某种程度上有相似。至少在某种意义上，某些人喜欢电影 $i$，或许更有可能也对电影 $j$ 感兴趣。总

结一下，当用户在看某部电影 $i$ 的时候，如果你想找5部与电影非常相似的电影，为了能给用户推荐5部新电影，你需要做的是找出电影 $j$ 与电影 $i$ 的距离最小，这样你就能给你的用户推荐几部不同的电影了。

六、实现细节：均值归一化 Mean Normalization

让我们来看下面的用户评分数据：

❓ 如果我们新增一个用户 Eve，并且 Eve 没有为任何电影评分，那么我们以什么为依据为Eve推荐电影呢？

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

然后我们利用这个新的 $Y$ 矩阵来训练算法。如果我们要用新训练出的算法来预测评分，则需要将平均值重新加回去，预测$(\theta^{(j)})^T x^{(i)}+\mu_i$，对于Eve，我们的新模型会认为她给每部电影的评分都是该电影的平均分。