异常检测(Anomaly Detection)

1.问题的动机

异常检测(Anomaly detection)问题是机器学习算法的一个常见应用。这种算法的一个有趣之处在于：它虽然主要用于非监督学习问题，但从某些角度看，它又类似于一些监督学习问题。
什么是异常检测呢？为了解释这个概念，让我举一个例子吧：

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

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

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

给定数据集 x^(1), x^(2) ,..,x^(m)，我们假使数据集是正常的，我们希望知道新的数据 是不是异常的，即这个测试数据不属于该组数据的几率如何。我们所构建的模型应该能根据该测试数据的位置告诉我们其属于一组数据的可能性 p(x)。

欺诈检测：
寻找网站中操作异常的用户
工业生产领域
计算机机群管理

2.高斯分布

正态分布
两个参数，均值u；方差σ^2
u控制钟形曲线的中心位置，σ控制钟形曲线的宽度

例子：
阴影面积的积分都是1！

参数估计问题：
参数估计问题就是给定数据集，我希望能找到能够估算出u和σ平方的值：
极大似然估计：

注：机器学习中对于方差我们通常只除以m而非统计学中的(m-1)。这里顺便提一下，在实际使用中，到底是选择使用1/m还是1/(m-1)其实区别很小，只要你有一个还算大的训练集，在机器学习领域大部分人更习惯使用1/m这个版本的公式。这两个版本的公式在理论特性和数学特性上稍有不同，但是在实际使用中，他们的区别甚小，几乎可以忽略不计。

3.异常检测算法

基于高斯分布建立异常检测算法：

我们处理异常检测的方法是：我们要用数据集建立起概率模型，p(x)，我们要试图解决哪些特征量出现的概率比较高，哪些特征量的出现概率比较低，因此x就会是一个向量。

x1到xn上的独立假设：

异常算法使用：
1.选择特征量，它能帮我们指出那些反常的样本
2.给出训练集，计算u和σ（向量化公式）
3.计算新样本的p(x)

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

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

如何估计p(x)的值，即x的概率值，检测算法。

即用给定的数据集，拟合了参数，对参数进行评估，来得到参数u和σ的值，然后用新的例子，说明其是否为异常。

4.开发和评估异常检测系统

实验评估的重要性，它的主要思想是当你为某个应用开发一个学习算法时，如果你有一个办法通过返回一个实数，来评估你的算法，那么做这些选择就会简单的多。

为了快速的开发出这样一个算法评估系统，假设我们有一些带标签的数据，来指明哪些是异常样本，哪些是正常样本，这就是我们认为的能评估异常检测算法的标准方法。

选择ε的方法就是尝试许多不同的ε值并从中选择一个表现良好的值。

评估一个异常检测算法的步骤，并且在能够评估一个算法之后，能够用像F1这样的实数进行评估之后，将使你在尝试开发一个异常检测系统时大大提高当你进行决策时的效率。

总结一下：
异常检测算法是一个非监督学习算法，意味着我们无法根据结果变量 y的值来告诉我们数据是否真的是异常的。我们需要另一种方法来帮助检验算法是否有效。当我们开发一个异常检测系统时，我们从带标记（异常或正常）的数据着手，我们从其中选择一部分正常数据用于构建训练集，然后用剩下的正常数据和异常数据混合的数据构成交叉检验集和测试集。

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

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

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

5.异常检测与监督学习对比

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

两者比较：

希望这节课能让你明白一个学习问题的什么样的特征，能让你把这个问题当做是一个异常检测，或者是一个监督学习的问题。另外，对于很多技术公司可能会遇到的一些问题，通常来说，正样本的数量很少，甚至有时候是0，也就是说，出现了太多没见过的不同的异常类型，那么对于这些问题，通常应该使用的算法就是异常检测算法。

6.选择特征

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

异常检测假设特征符合高斯分布，如果数据的分布不是高斯分布，异常检测算法也能够工作，但是最好还是将数据转换成高斯分布，例如使用对数函数：x= log(x+c)，其中 c 为非负常数； 或者 x=x^c，c为 0-1 之间的一个分数，等方法。(编者注：在python中，通常用np.log1p()函数，log1p就是 log(x+1)，可以避免出现负数结果，反向函数就是np.expm1()。

误差分析：

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

异常检测误差分析：

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

我平常在做异常检测选择特征向量时的思考：

在这段视频中，我们介绍了如何选择特征，以及对特征进行一些小小的转换，让数据更像正态分布，然后再把数据输入异常检测算法。同时也介绍了建立特征时，进行的误差分析方法，来捕捉各种异常的可能。希望你通过这些方法，能够了解如何选择好的特征变量，从而帮助你的异常检测算法，捕捉到各种不同的异常情况。

7.多元高斯分布（选修）

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

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

只能是圆形检测，很多异常值检测不出来，所以改良版（多元高斯分布）：

∑是一个协方差矩阵，它衡量的是方差，或者说特征变量x1和x2的变化量。

下面我们来看看协方差矩阵是如何影响模型的：

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

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

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

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

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

如果训练集不是太大，并且没有太多的特征，我们可以使用多元高斯分布模型。

8.使用多元高斯分布进行异常检测（可选）

在我们谈到的最后一个视频，关于多元高斯分布，看到的一些建立的各种分布模型，当你改变参数，u和∑。在这段视频中，让我们用这些想法，并应用它们制定一个不同的异常检测算法。

要回顾一下多元高斯分布和多元正态分布：

首先，我们把我们的训练集，和我们的拟合模型，我们计算p(x)，要知道，设定u和描述的一样∑。

如图，该分布在中央最多，越到外面的圈的范围越小。
并在该点是出路这里的概率非常低。
原始模型与多元高斯模型的关系如图：
其中：协方差矩阵∑为：

原始模型和多元高斯分布比较如图：

推荐系统(Recommender Systems)

9.问题形式化

我想讲推荐系统有两个原因：

第一、仅仅因为它是机器学习中的一个重要的应用。在过去几年，我偶尔访问硅谷不同的技术公司，我常和工作在这儿致力于机器学习应用的人们聊天，我常问他们，最重要的机器学习的应用是什么，或者，你最想改进的机器学习应用有哪些。我最常听到的答案是推荐系统。现在，在硅谷有很多团体试图建立很好的推荐系统。因此，如果你考虑网站像亚马逊，或网飞公司或易趣，或iTunes Genius，有很多的网站或系统试图推荐新产品给用户。如，亚马逊推荐新书给你，网飞公司试图推荐新电影给你，等等。这些推荐系统，根据浏览你过去买过什么书，或过去评价过什么电影来判断。这些系统会带来很大一部分收入，比如为亚马逊和像网飞这样的公司。因此，对推荐系统性能的改善，将对这些企业的有实质性和直接的影响。

推荐系统是个有趣的问题，在学术机器学习中因此，我们可以去参加一个学术机器学习会议，推荐系统问题实际上受到很少的关注，或者，至少在学术界它占了很小的份额。但是，如果你看正在发生的事情，许多有能力构建这些系统的科技企业，他们似乎在很多企业中占据很高的优先级。这是我为什么在这节课讨论它的原因之一。

我想讨论推荐系统地第二个原因是：这个班视频的最后几集我想讨论机器学习中的一些大思想，并和大家分享。这节课我们也看到了，对机器学习来说，特征是很重要的，你所选择的特征，将对你学习算法的性能有很大的影响。因此，在机器学习中有一种大思想，它针对一些问题，可能并不是所有的问题，而是一些问题，有算法可以为你自动学习一套好的特征。因此，不要试图手动设计，而手写代码这是目前为止我们常干的。有一些设置，你可以有一个算法，仅仅学习其使用的特征，推荐系统就是类型设置的一个例子。还有很多其它的，但是通过推荐系统，我们将领略一小部分特征学习的思想，至少，你将能够了解到这方面的一个例子，我认为，机器学习中的大思想也是这样。因此，让我们开始讨论推荐系统问题形式化。

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

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

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

下面引入一些标记：
u 代表用户的数量
m 代表电影的数量
r(i, j) 如果用户j给电影 i 评过分则 r(i,j)=1
y^(i, j) 代表用户 j 给电影i的评分
mj代表用户 j 评过分的电影的总数

10.基于内容的推荐系统

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

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

11.协同过滤

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

12.协同过滤算法

协同过滤优化目标：

13.向量化：低秩矩阵分解

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

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

我将要做的是：实现一种选择的方法，写出协同过滤算法的预测情况。
我们有关于五部电影的数据集，我将要做的是，将这些用户的电影评分，进行分组并存到一个矩阵中。
我们有五部电影，以及四位用户，那么 这个矩阵 就是一个5行4列的矩阵，它将这些电影的用户评分数据都存在矩阵里：

找到相关影片：

现在既然你已经对特征参数向量进行了学习，那么我们就会有一个很方便的方法来度量两部电影之间的相似性。例如说：电影 i 有一个特征向量x^(i)，你是否能找到一部不同的电影 j，保证两部电影的特征向量之间的距离x^(i) 和 x^(j)很小，那就能很有力地表明电影i和电影 j在某种程度上有相似，至少在某种意义上，某些人喜欢电影 i，或许更有可能也对电影 j 感兴趣。总结一下，当用户在看某部电影 i 的时候，如果你想找5部与电影非常相似的电影，为了能给用户推荐5部新电影，你需要做的是找出电影 j，在这些不同的电影中与我们要找的电影 i 的距离最小，这样你就能给你的用户推荐几部不同的电影了。

通过这个方法，希望你能知道，如何进行一个向量化的计算来对所有的用户和所有的电影进行评分计算。同时希望你也能掌握，通过学习特征参数，来找到相关电影和产品的方法。

14.推行工作上的细节：均值归一化

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

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

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

然后我们利用这个新的 Y 矩阵来训练算法。 如果我们要用新训练出的算法来预测评分，则需要将平均值重新加回去，预测

对于Eve，我们的新模型会认为她给每部电影的评分都是该电影的平均分。