吴恩达机器学习作业翻译8——anomaly detection and recommendation

程序设计练习8:异常检测和推荐系统

介绍

在本练习中,你将实现异常检测算法,并将其应用于检测网络中的故障服务器。在第二部分中,你将使用协同过滤来构建电影推荐系统。在开始编程练习之前,我们强烈建议观看视频课程并完成相关主题的复习问题。

要开始练习,你需要下载起始代码并将其内容解压缩到你希望完成练习的目录中。如果需要,请在开始本练习之前使用Octave/MATLAB中的cd命令更改到此目录。

你也可以在课程网站的“环境设置说明”中找到安装Octave/MATLAB的说明。

本练习中包含的文件

ex8.m - 用于第一部分练习的Octave / MATLAB脚本
ex8_cofi.m - 用于第二部分练习的Octave / MATLAB脚本
ex8data1.mat - 用于异常检测的第一个样本集
ex8data2.mat - 用于异常检测的第二个样本集
ex8_movies.mat - 电影评论数据集
ex8_movieParams.mat - 提供用于调试的参数
multivariateGaussian.m - 计算高斯分布的概率密度函数
visualizeFit.m - 高斯分布和数据集的2D图
checkCostFunction.m - 梯度检查协同过滤
computeNumericalGradient.m - 以数字方式计算梯度
fmincg.m - 函数最小化例程(类似于fminunc)
loadMovieList.m - 将电影列表加载到单元格数组中
movie_ids.txt - 电影列表
normalizeRatings.m - 协同过滤的均值归一化
submit.m - 提交脚本
[*] estimateGaussian.m - 用对角协方差矩阵估计高斯分布的参数
[*] selectThreshold.m - 找到异常检测的阈值
[*] cofiCostFunc.m - 实现协同过滤的代价函数

* 表示必须完成的文件

在整个练习的第一部分(异常检测)中,你将使用脚本ex8.m。对于协同过滤的第二部分,你将使用ex8_cofi.m。这些脚本为问题设置数据集,并调用你要编写的函数。 你只需按照此作业中的说明修改其他文件中的函数。

在哪里寻求帮助

本课程的练习使用非常适合数值计算的高级编程语言Octave或MATLAB。如果你没有安装Octave或MATLAB,请参阅课程网站上“环境设置说明”中的安装说明。

在Octave/MATLAB命令行中输入help紧跟函数名称会显示内建的函数说明。比如输入help plot会显示绘图函数的帮助信息。更多Octave和MATLAB的函数说明请在Octave官网MATLAB官网查阅。

我们也非常鼓励使用在线讨论与其他学生讨论练习。但是,不要查看任何源代码或与他人共享源代码。


1、异常检测

在本练习中,你将实现一个异常检测算法来检测服务器计算机中的异常行为。这些特性度量每个服务器的吞吐量(mb/s)和响应延迟(ms)。在你的服务器运行时,你收集了m = 307个关于它们行为的样本,因此有一个未标记的数据集$\{x^{(1)},…,x^{(m)}\}$。你怀疑这些样本中的绝大多数都是正常运行的服务器的“正常”(非异常)样本,但是也可能有一些服务器在这个数据集中异常运行的样本。

你将使用高斯模型来检测数据集中的异常样本。 你将首先开始使用2D数据集,以便可视化算法正在执行的操作。 在该数据集上,你将拟合高斯分布,然后找到概率非常低的值,因此可以认为是异常。之后,你将异常检测算法应用于具有多个维度的较大数据集。你将使用ex8.m进行这部分练习。

ex8.m的第一部分将可视化数据集,如图1所示。

 

 

Figure 1: The first dataset.

 

1.1 高斯分布

要执行异常检测,首先需要根据数据的分布匹配模型。

给定训练集$\{x^{(1)},...,x^{(m)}\}$(其中$x^{(i)}∈R^n$),你想估计每个特征$x_i$的高斯分布。 对于每个特征 i=1,,,n,你需要找到适合第i维$\{x^{(1)}_i,...,x^{(m)}_i\}$(每个样本的第i维)的数据的参数$μ_i$$σ^2_i$

给出的高斯分布如下:

p(x;μ,σ^2)=\frac{1}{\sqrt{2πσ^2}}e^{-\frac{(x-μ)^2}{2σ^2}}

其中μ是平均值,$σ^2$控制方差。

1.2 估计高斯分布的参数

你可以使用下面的方程估计第i个特征的参数$(μ_i,σ^2_i)$。估计平均值你可以使用:

μ_i = \frac{1}{m}\sum^m_{j=1}x^{(j)}_i,

估计方差可以使用:

σ^2_i = \frac{1}{m}\sum^m_{j=1}(x^{(j)_i – μ_i})^2.

你的任务是完成estimateGaussian.m中的代码。这个函数以数据矩阵X为输入,应该输出一个n维向量mu,其包含所有n个特征的均值;另一个n维向量sigma2包含所有特征的方差。你可以在每个特征和每个训练样本上使用for循环来实现这一点(尽管向量化实现可能更有效;如果你愿意,可以随意使用向量化实现)。 请注意,在Octave / MATLAB中,当计算$σ^2_i$时,var函数将(默认情况下)使用$\frac{1}{m-1}$而不是$\frac{1}{m}$

完成estimateGaussian.m中的代码后,ex8.m的下一部分将可视化拟合高斯分布的轮廓。你应该得到类似于图2的图。从你的图中,你可以看到大多数样本都位于具有最高概率的区域中,而异常样本位于概率较低的区域中。

 

 

Figure 2: The Gaussian distribution contours of the distribution fit to the
dataset.

 

==你现在应该提交答案==

1.3 选择阈值ε

现在你已经估计了高斯参数,你可以研究哪些样本在给定此分布时具有非常高的概率,哪些样本具有非常低的概率。低概率样本更可能是我们数据集中的异常。 确定哪些样本是异常的一种方法是基于交叉验证集选择阈值。 在本练习的这一部分中,你将实现一个算法,使用交叉验证集上的$F_1$分数选择阈值ε。

你现在应该完成selectThreshold.m中的代码。在此我们将使用一个交叉验证集$\{(x^{(1)}_{cv},y^{(1)}_{cv}),...,(x^{(m_{cv})}_{cv},y^{(m_{cv})}_{cv})\}$,其中标签y = 1对应于异常样本,y = 0对应于正常示样本。对于每个交叉验证样本,我们计算$p(x^{i}_{cv})$。所有这些概率的向量$p(x^{(1)}_{cv}),...,p(x^{(m_{cv})}_{cv})$会在向量pval中传递给selectThreshold.m函数。相应的标签$y^{(1)}_{cv},...,y^{(m_{cv})}_{cv}$会在向量yval中传递给selectThreshold.m函数。

函数selectThreshold.m应该返回两个值;第一个是选定的阈值ε。如果样本x具有低概率p(x)<ε,则认为它是异常的。该函数还应该返回$F_1$分数,该分数告诉你在给定某个阈值时你在查找真实异常方面的表现如何。对于许多不同的ε值,你将通过计算当前阈值正确和错误分类的样本数来计算得到的$F_1$分数。

$F_1$分数使用精度(prec)和召回率(rec)计算:

F_1 = \frac{2·prec·rec}{prec+rec},

计算prec和rec:

prec = \frac{tp}{tp+fp}

rec = \frac{tp}{tp+fn}

其中:

  • tp是真阳性的数量:真实值标注这是一个异常,我们的算法正确地将其归类为异常。
  • fp是假阳性的数量:真实值标注它不是异常,但我们的算法错误地将其归类为异常。
  • fn是假阴性的数量:真实值标注它是一个异常,但我们的算法错误地将其归类为不是异常的。

在提供的代码selectThreshold.m中,已经存在一个循环,它将尝试许多不同的ε值并根据$F_1$分数选择最佳ε。

你现在应该在selectThreshold.m中完成代码。你可以在所有交叉验证样本上使用for循环实现F1分数的计算(以计算值tp,fp,fn)。你应该看到epsilon的值约为8.99e-05。

实现注意:为了计算tp,fp和fn,你可以使用向量化实现而不是遍历所有样本。这可以通过向量和单个数字之间的Octave / MATLAB相等测试来实现。如果在n维二元向量中有几个二进制值$v∈\{0,1\}^n$,你可以通过使用:sum(v==0)找出这个向量中有多少个值是0。 你还可以将逻辑和运算符应用于此类二进制向量。 例如,让cvPredictions是交叉验证集数量大小的二进制向量,如果算法认为$x^{(i)}_{cv}$是异常,则第i个元素为1,否则为0。 然后,你可以使用以下方法计算误报数:fp = sum((cvPredictions == 1) & (yval == 0))。

 

 

Figure 3: The classified anomalies.

 

完成selectThreshold.m中的代码后,ex8.m中的下一步将运行异常检测代码并圈出绘图中的异常(图3)。

==你现在应该提交答案==

1.4 高维数据集

脚本ex8.m的最后一部分将运行你在更现实和更难的数据集上实现的异常检测算法。 在此数据集中,每个示例由11个特征描述,捕获计算服务器的更多属性。

该脚本将使用你的代码来估计高斯参数($μ_i$$σ^2_i$),评估你估计高斯参数的训练数据X的概率,并对交叉验证集Xval进行评估。 最后,它将使用selectThreshold来找到最佳阈值ε。 你应该看到一个大约1.38e-18的值epsilon,发现了117个异常。

2、推荐系统

在本练习的这一部分中,你将实现协同过滤学习算法并将其应用于电影的数据集。此数据集包含1到5等级的。数据集具有$n_u$ = 943个用户,并且$n_m$ = 1682 电影。对于本练习的这一部分,你将使用脚本ex8_cofi.m。

在本练习的下一部分中,你将实现函数cofiCostFunc.m,该函数计算协作适配目标函数和梯度。 在实现代价函数和梯度之后,你将使用fmincg.m来学习协同过滤的参数。

2.1 电影数据集

脚本ex8_cofi.m的第一部分将加载数据集ex8_movies.mat,在Octave / MATLAB环境中提供变量Y和R。

矩阵Y(电影数 x 用户数的矩阵)存储$y^{(i,j)}$(从1到5)。 矩阵R是二进制值指示符矩阵,其中R(i,j) = 1,如果用户j给出电影i,否则R(i,j) = 0。协同过滤的目的是预测电影用户尚未的电影,即R(i,j) = 0的条目。这将允许我们向用户推荐具有最高预测的电影。

为了帮助你理解矩阵Y,脚本ex8_cofi.m将计算第一部电影(玩具总动员)的平均电影,并将平均输出到屏幕。

在本练习的这一部分中,你还将使用矩阵X和Theta:

    X的第i行对应于第i个电影的特征向量$x^{(i)}$,并且对于第j个用户,Theta的第j行对应于一个参数向量$θ^{(j)}$$x^{(i)}$$θ^{(j)}$都是n维向量。 出于本练习的目的,你将使用n = 100,因此,$x^{(i)}∈R^{100}$$θ^{(j)}∈R^{100}$。相应地,X是$n_m$×100矩阵,并且Theta是$n_u$×100矩阵。

2.2 协同过滤学习算法

现在,你将开始实施协同过滤学习算法。你将从实现代价函数开始(没有正则化)。

电影推荐设置中的协同过滤算法考虑一组n维参数向量$x^{(1)},...,x^{(n_m)}$$θ^{(1)},...,θ^{(n_u)}$,其中模型预测用户j对电影i的为$y^{(i,j)}=(θ^{(j)})^Tx^{(i)}$。给定一些数据集由一些用户在某些电影上产生的一组组成,你希望学习参数向量$x^{(1)},...,x^{(n_m)}$$θ^{(1)},...,θ^{(n_u)}$产生最佳拟合(最小化平方误差)。

你将完成cofiCostFunc.m中的代码以计算协作过滤的代价函数和梯度。请注意,函数的参数(即你尝试学习的值)是X和Theta。为了使用现成的最小化器(如fmincg),已设置代价函数以将参数展开为单个向量参数。你之前在神经网络编程练习中使用过相同的向量展开方法。

2.2.1 协同过滤代价函数

协同过滤代价函数(无正则化)由下式给出:

    你现在应该修改cofiCostFunc.m以在变量J中返回此代价值。请注意,仅当R(i,j)= 1时,你应该累积用户j和电影i的代价值。

完成该函数后,脚本ex8_cofi.m将运行你的代价函数。你应该会看到22.22的输出。

==你现在应该提交答案==

实现注意:我们强烈建议你使用向量化实现来计算J,因为稍后将通过优化包fmincg多次调用。像往常一样,最简单的方法是首先编写一个非向量化的实现(以确保你有正确的答案),并将其修改为向量化实现(检查向量化步骤不会改变算法的输出)。为了提出一个向量化实现,下面的技巧可能会有所帮助:你可以使用R矩阵将所选条目设置为0。例如,R .* M 将在M和R之间进行逐元素乘法; 因为R只有值为0或1的元素,所以只有当R中的对应值为0时才会将M的元素设置为0。因此,sum(sum(R. * M))是M的所有元素,R中的对应元素等于1。

2.2.2 协同过滤梯度

现在,你应该实现梯度(没有正则化)。 具体来说,你应该完成cofiCostFunc.m中的代码以返回变量X_grad和Theta_grad。注意,X_grad应该是与X相同大小的矩阵,并且类似地,Theta_grad是与Theta相同大小的矩阵。 代价函数的梯度由下式给出:

    请注意,该函数通过将它们展开到单个向量中来返回两组变量的梯度。在完成计算梯度的代码之后,脚本ex8_cofi.m将运行梯度检查(checkCostFunction)以数字方式检查梯度的实现。如果你的实现是正确的,你应该发现分析和数值梯度匹配密切合作。

==你现在应该提交答案==

实现注意:你可以在不使用向量化实现的情况下获得此作业的全部成绩,但你的代码运行速度会慢得多(几个小时),因此我们建议你尝试对你的实现进行向量化。

首先,你可以通过电影上的for循环(用于计算$\frac{∂J}{∂x^{(i)}_k}$)和用户上的for循环(用于计算$\frac{∂J}{∂x^{(j)}_k}$)来实现梯度。当你第一次实现梯度时,你可以从非向量化版本开始,通过实现另一个内部for循环来计算求和中的每个元素。 以这种方式完成梯度计算后,你应该尝试向量化你的实现(向量化内部for循环),这样你只剩下两个for循环(一个电影集上的for循环来针对每一部电影计算$\frac{∂J}{∂x^{(i)}_k}$,以及一个用户集上的for循环针对每个用户计算$\frac{∂J}{∂x^{(j)}_k}$)。

实现提示:要实现向量化,你会发现这个很有用:你应该想办法计算所有与$x^{(i)}_1,x^{(i)}_2,...,x^{(i)}_n$相关的导数(如与特征向量$x^{(i)}$对应的导数)。让我们为第i部电影的特征向量定义导数:

要对上面的表达式进行向量化,你可以从索引Theta和Y开始,只选择感兴趣的元素(即r(i,j)= 1的元素)。直观地说,当你考虑第i部电影的特征时,你只需要关注给电影评分的用户,这样你就可以从Theta和Y中删除所有其他用户。

具体来说,你可以将idx = find(R(i,:)== 1)设置为已电影i的所有用户的列表。这将允许你创建临时矩阵Thetatemp = Theta(idx,:)和Ytemp = Y(i,idx),它们会转换为Theta和Y,只为你提供已评定第i部电影的用户集。这将允许你将导数写为:

X_{grad}(i, 🙂 = (X(i, 🙂 ∗ Theta^T_{temp} − Y_{temp}) ∗ Theta_{temp}.

(注意:上面的向量化计算会返回一个行向量。)

在对$x^{(i)}$进行向量化导数计算之后,你应该使用类似的方法来相对于$θ^{(j)}$对导数进行向量化。

2.2.3 正则化代价函数

具有正则化的协同过滤的代价函数由下式给出

    你现在应该将正则化添加到代价函数J的原始计算中。完成后,脚本ex8_cofi.m将运行你的正则化代价函数,你应该会看到大约31.34的代价值。

==你现在应该提交答案==

2.2.4 正则化梯度

现在你已经实现了正则化代价函数,你应该继续为梯度实现正则化。你应该在cofiCostFunc.m中添加实现,以通过添加正则化项的贡献来返回正则化梯度。请注意,正则化代价函数的梯度由下式给出:

    这意味着你只需要将$λx^{(i)}$添加到前面描述的X_grad(i,:)变量中,并将$λθ^{(j)}$添加到前面描述的Theta_grad(j,:)变量中。

在你完成计算梯度的代码之后,脚本ex8_cofi.m将运行另一个梯度检查(checkCostFunction),对梯度的实现进行数值检查。

==你现在应该提交答案==

2.3 学习电影推荐

完成协作过滤代价函数和梯度后,你现在可以开始训练算法,为自己制作电影推荐。在ex8_cofi.m脚本的下一部分中,你可以输入自己的电影首选项,以便稍后在算法运行时,你可以获得自己的电影推荐! 我们已根据自己的喜好填写了一些值,但你应该根据自己的喜好进行更改。 可以在文件影片idx.txt中找到所有影片列表及其在数据集中的编号。

2.3.1 推荐

在将附加添加到数据集之后,脚本将继续训练协作过滤模型。 这将学习参数X和Theta。 要预测用户j的电影i的,你需要计算$(θ^{(j)})^Tx^{(i)}$。 脚本的下一部分计算所有电影和用户的,并根据之前在脚本中输入的显示它推荐的电影(图4)。请注意,由于不同的随机初始化,你可能会获得一组不同的预测。

 

 

Figure 4: Movie recommendations

 

提交和评分

完成作业的各个部分后,请务必使用提交系统将你的作业提交给我们的服务器。以下是对此练习的每个部分进行评分的细则。

    你可以多次提交作业,但我们只考虑最高分。

点个赞呗:程序员虾说 » 吴恩达机器学习作业翻译8——anomaly detection and recommendation

赞 (12) 打赏

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

请作者喝杯咖啡~

支付宝扫一扫打赏

微信扫一扫打赏