31.jpg

1. 异常检测

1.1 问题的动机

异常检测，Anomaly detection，常用于非监督学习，让我们用一个飞机引擎的异常检测例子来说明。

假想你是一个飞机引擎制造商，当你生产的飞机引擎从生产线上流出时，你需要进行QA(质量控制测试)，而作为这个测试的一部分，你测量了飞机引擎的一些特征变量，比如引擎运转时产生的热量，或者引擎的振动等等。假设此处有2个特征x1,x2。m个数据样本从，将样本和特征的关系绘制成图表如下：

1.png

这个图表有什么用途呢？大意上给定一个新的测试数据（上图中的绿点），如果此样本在红色样本的中间，则我们可以认为其是正常的，否则我们认为这个引擎室异常的(下面那个绿点)。具体点说，这种方法叫做密度估计，表达式如下：

2.png

其中p(x)为概率密度分布函数，为划定的概率值，且通常这个p(x)分布选用正态分布(高斯分布)。我们可以设定= 0.001，则当新的引擎样本经过时，我们就可以判定此引擎为不合格。

其他应用：

异常检测主要用来识别欺骗。例如在线采集而来的有关用户的数据，一个特征向量中可能会包含如：用户多久登录一次，访问过的页面，在论坛发布的帖子数量，甚至是打字速度等。尝试根据这些特征构建一个模型，可以用这个模型来识别那些不符合该模式的用户。
再一个例子是检测一个数据中心，特征可能包含：内存使用情况，被访问的磁盘数量，CPU 的负载，网络的通信量等。根据这些特征可以构建一个模型，用来判断某些计算机是不是有可能出错了。

1.2 正态分布/高斯分布

异常检测假设特征符合正太分布/高斯分布，如果数据的分布不是高斯分布，异常检测算法也能够工作，但是最好还是将数据转换成高斯分布，所以我们需要掌握正太分布的知识。

正态分布(Normal Distribution)也叫高斯分布(Gaussian Distribution),我们先回归一下正太分布的基本知识：

如果，我们认为变量x服从正态分布，则其可以表示为：服从正态分布的函数，其有两个重要指标：,其中：

整个分布的概率密度函数为：

整个概率密度函数的累加和为1，即表示100%。不同期望和方差的高斯分布图像如下：

3.png

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

1.3 异常检测算法

假设，我们有一组无标签(没有y)的训练集，这些训练集有n个特征，我们将用这些数据利用正太分布，构造出异常检测算法。其实，很简单，无非是算出训练集所有样本在每个特征上的的期望和方差，然后所有的概率相乘，即可得到总体概率密度函数。我们根据得到的p(x)和设定的判断边界即可对未知样本经行异常检测，这便是一个简单的异常检测算法。具体如下：

4.png

这样，一个简单的异常检测算法便开发完成了。下面看一个例子的概率分布例子，以及如何用它来进行异常检测的。

5.png

在这里，我们有两个特征x1,x2，左上角是训练集中所有的样本点(红色)和特征关系图；右上角是单个特征的概率密度分布图，左下角是总体的分布图。

这时，我们通过概率密度分布可以对新的样本点经行异常检测了，此处设定的为0.02(判定边界)。经过计算，可以发现x_test1样本点的概率 > 0.02,正常；x_test1概率 < 0.02,故被判断为异常。

1.4 异常检测系统

异常检测系统是基于异常检测算法开发的，其不仅包含异常检测算法，还增加了开发和评价过程，主要是在真实环境下，对样本的划分(训练集、交叉验证集、测试集)、对系统的评价等。

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

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

6000 台正常引擎的数据作为训练集

2000 台正常引擎和 10 台异常引擎的数据作为交叉检验集

2000 台正常引擎和 10 台异常引擎的数据作为测试集

具体的评价方法如下：

1.根据测试集数据，我们估计特征的平均值和方差并构建p(x)函数

2.对交叉检验集，我们尝试使用不同的值作为阀值，并预测数据是否异常，根据 F1 值或者查准率与查全率的比例来选择

3.选出后，针对测试集进行预测，计算异常检验系统的F1值，或者查准率与查全率之比。

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

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

1.6 特征选择

1.6.1 数据转换

在选择特征之前，我们要尽量确保数据是基本符号高斯分布的，否则我们需要将其转化成近似高斯分布的形态。例如使用对数函数： 其中c为非负数,范围在0-1之间。在 python 中，通常用 np.log1p()函数。

6.png

1.6.1 误差分析

误差分析的目的在于：

从已有的模型和特征中开始跑样本，通过对预测结果中判断错误的数据(误差)经行分析，从而发现和挑选更适合的特征，从而改进模型。

我们通过p(x)来判断一个样本是正常还是异常，且通常情况下，我们希望正常样本的p(x)尽量大，异常样本的p(x)足够小，但，这往往就是通常会出问题的地方，即当一个实际上是异常的样本点，经过异常检测系统判断后p(x)确足够大，即异常检测系统判断失效，导致判断错误。

7.png

这里举个例子：原模型有一个特征x1,经过异常检测算法拟合出来的曲线如上左图，这时候有一个异常样本，用该模型检测时，确发现其x值在正常区间，如上左图中绿点所示，所以我们得到一个信息：该异常检测模型不够完善，可能是由于特征x1不够，不能覆盖样本的总体特征情况。

此时，我们即可构造出新特征，即采用x1和x2两个特征，再重新应用异常检测算法训练模型，新训练的样本特征分布图如上右图，通过这个新的异常检测系统，我们可以成功预测出异常点。

例2：

一个数据中心的例子，数据中心通常是由n台服务器组成的集群，对这n台服务器的运行状态经行监控就显得非常重要。通常情况下，我们可以选出4个特征：

• x1 = 内存占用
• x2 = 磁盘每秒访问次数
• x3 = CPU负载
• x4 = 网络流量

8.png

通常，这些特征能较好的满足异常检测的需求，但实际情况发现，这个模型不能捕获到一类的异常情况，譬如：

当x3和x4都很低时，我们认为某台服务器在经历较大规模的用户访问，计算和网络吞吐都很高，模型将其判为异常，但是当其中只有一个较高时，譬如x3较低，x4较高，模型可能判断为正常，那么就会忽略一种情况：

程序死锁，CPU飙升至很高，但是对外提供服务的网络流量几乎为0，那么为了捕捉这种异常，我们需要建立新的特征，譬如可以用x5，x6。

1.7 多元高斯分布

在1.3小节中，我们发现正常的高斯分布可以同时应对n个特征，那么多元高斯分布存在的意义在哪？正常情况下，普通的高斯分布，要求的n个特征必须特征明确，且互相独立，无相关性，这样才能较好地构建模型，如果特征间可能存在关系，则可能导致模型的不准确，此时我们可以考虑用多元高斯分布。

还是以1.6中数据中心，服务器集群的例子：

9.png

分别用x1 = CPU负载、x2 = 内存使用量作为两个特征，构建出的特征-样本分布图、特征密度函数图如上。根据这两个特征构建的异常检测模型，会认为所有在左图粉色圆圈中的样本都是正常的，但是实际情况下，我们可能会发现其实在左图蓝色小圈中的样本是正常的，而篮圈以外的样本都应该是异常的（如左图中的绿色点）。于是，这个模型便不够好。我们可以用多元高斯分布改造它。
普通高斯分布的概率密度，是各个特征的概率密度公式累乘的，公式如下：

10.png

而多元高斯分布的概率密度公式，不需要分别计算各特征的概率密度再累乘，而是通过求协方差矩阵：

11.png

多元高斯分布的概率密度公式如下：

12.png

1.7.1 注意

• 1.此处的是一个n维向量，其维度n = 特征总数。其中每个值代表了每个特征的期望。
• 2.训练样本数m必须 > 特征维度n，不然的话协方差矩阵不可逆的，通常需要m>10n 另外特征冗余也会导致协方差矩阵不可逆

1.7.2 和原高斯分布的比较

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

2. 推荐系统

2.1 问题规划

在接下来的视频中，我想讲一下推荐系统。我想讲推荐系统有两个原因：
第一、仅仅因为它是机器学习中的一个重要的应用。在过去几年，我偶尔访问硅谷不同的技术公司，我常和工作在这儿致力于机器学习应用的人们聊天，我常问他们，最重要的机器学习的应用是什么，或者，你最想改进的机器学习应用有哪些。我最常听到的答案是推荐系统。现在，在硅谷有很多团体试图建立很好的推荐系统。因此，如果你考虑网站像亚马逊，或网飞公司或易趣，或 iTunes Genius，有很多的网站或系统试图推荐新产品给用户。如，亚马逊推荐新书给你，网飞公司试图推荐新电影给你，等等。这些推荐系统，根据浏览你过去买过什么书，或过去评价过什么电影来判断。这些系统会带来很大一部分收入，比如为亚马逊和像网飞这样的公司。因此，对推荐系统性能的改善，将对这些企业的有实质性和直接的影响。
推荐系统是个有趣的问题，在学术机器学习中因此，我们可以去参加一个学术机器学习会议，推荐系统问题实际上受到很少的关注，或者，至少在学术界它占了很小的份额。但是，如果你看正在发生的事情，许多有能力构建这些系统的科技企业，他们似乎在很多企业中占据很高的优先级。这是我为什么在这节课讨论它的原因之一。

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

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

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

1.png

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

下面引入一些标记：

• 代表用户数量
• 代表电影数量
• 如果用户j给电影i评过分，则记为1
• 用户j给电影i评分的数值，从0~5
• 代表用户评过分的电影总数

2.2 基于内容的推荐系统

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

在我们的例子中，我们可以假设每部电影都有两个特征，如x1代表电影的浪漫程度,x2代表电影的动作程度。这样，对于每部电影，我们都可以给这两个特征打分(0~1)，用于表现每个电影的特征。

2.png

则每部电影都有一个特征向量，如表示第一部电影的特征向量，其爱情程度0.9，动作程度0，故其特征向量为：[0.9,0]

下面我们要基于以上特征构建一个推荐算法，顾名思义推荐算法就是用于给观众推荐电影的，简单的推荐算法大意如下：给观众推荐电影之前，我们首先需要遍历电影库，用算法来评估观众可能打分的分值，最后取高打分的电影推荐给观众。那么问题就转化为了，我们需要一个模型，输入用户和电影，模型将输出观众可能打分的分值。

假设我们采用线性回归模型，我们需要对每个用户建立线性回归模型，参数说明如下：

1. 表示用户j的参数向量
2. 表示电影i的特征向量
3. 表示用户j对电影i的预估评分

针对用户j，模型的代价函数：

3.png

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

4.png

如果我们要用梯度下降法来求解最优解，我们计算代价函数的偏导数后得到梯度下降的更新公式为：

5.png

2.3 协同过滤

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

我们通过用户对电影的评论(θ)可以同样建立模型来评估电影的特征，模型的损失函数如下：

6.png

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

简单来说我们可以随机初始化一些θ然后学习出特征x，再由x学习改进新的θ,从而不断地学习和收敛，协同过滤算法有点像练武，左右手互博，从而学会一招一式.....(但实际应用时，其实可以二者同时学习和优化)

7.png

2.4 协同过滤算法

在2.3中介绍的概念，是方便理解的，实际应用过程中，我们其实没有必要先计算θ再计算x再计算θ....如此循环往复，我们可以同时对二者进行优化，所以这也是协同过滤算法名字的意义所在。

8.png

那合在一起的代价函数 =

9.png

此时，我们的优化目标，变成了：

10.png

2.5 向量化：低秩矩阵分解

矩阵的秩r(A)，r(A)<=min(m,n),A是m*n型矩阵，举个例子：

r(A) = r(B) = 1,因为B矩阵中两列之间可以简化，故实际矩阵的秩为1。

低秩矩阵即表示r(A)较小的矩阵。在前面的协同过滤例子中，我们通过模型可以预测出一个用户对所有电影的评分，这个评分矩阵即一个低秩矩阵。

11.png

如图，给定所有用户对电影的评分矩阵Y，我们可以算出用户对电影的评分矩阵（上图右），这个矩阵中表示第1个用户对第2部电影的评分。矩阵的size：（行列），但由于矩阵间行列存在关系，可以被分解，故实际上矩阵的秩为,即此矩阵可以被看做是低秩矩阵。分解过程如下：
我们令：

则矩阵可以表示为。这种将低秩矩阵分开表示的行为，即可称为低秩矩阵分解Low Rank Matrix Factorization*

相似推荐
如果一个用户在看电影i，我们想要给他推荐和i相似的电影，那么怎么办？其实，很简单，如果我遍历电影库，找到了某部电影j，从而使电影i的特征和电影j的特征之间差异最小，那么j即是我需要推荐的电影。
同理，如果根据电影i推荐5部电影，则同样遍历电影库，找到Δ最小的前5部电影即可。

12.png

2.6 均值归一化

在协同过滤算法中，有时候均值归一化会让算法运行的更好

13.png

还是使用之前电影推荐的例子，这次多加了一个观众Eve，但是他对这5部电影都没有看过，于是协同过滤算法预测他给这5部电影打分都为同样的0分，这样，就无法给其推荐电影了，显然这样是不太妥当的。这就是可以用均值归一化来处理的典型例子。

我们可以计算出每部电影在每个用户评分下的均值，记为矩阵 ，然后用户评分矩阵Y = 原矩阵 - ，得到归一化的矩阵Y，这样做的结果是：即使Eve没有看过任何一部电影，推荐算法任然可以根据每部电影平均得分来为其推荐。

14.png