吴恩达机器学习作业翻译7——kmeans and PCA

程序设计练习7:k均值聚类与主成分分析

介绍

    在本练习中,你将实现K均值聚类算法并将其应用于压缩图像。在第二部分中,你将使用主成分分析来寻找人脸图像的低维表示。在开始编程练习之前,我们强烈建议观看视频课程并完成相关主题的复习问题。

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

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

本练习中包含的文件

ex7.m - K-means上第一个练习的Octave/MATLAB脚本 
ex7_pca.m - PCA上第二个练习的Octave/MATLAB脚本
ex7data1.mat - PCA样本集
ex7data2.mat - K-means样本集
ex7faces.mat - 人脸数据集
bird_small.png - 样本图片
displayData.m - 展示存储在矩阵中的2D数据
drawLine.m - 在现有的图形上画一条线
plotDataPoints.m - 初始化k-means中心
plotProgresskMeans.m - 绘制k-means的每一步
runkMeans.m - 运行K-means算法
submit.m - 提交脚本
[*] pca.m - 进行主成分分析
[*] projectData.m - 将数据集投射到较低维度空间
[*] recoverData.m - 从投影中恢复原始数据
[*] findClosestCentroids.m - 寻找最近的聚类中心(在K-means中使用)
[*] computeCentroids.m - 计算聚类中心平均值(K-means中使用)
[*] kMeansInitCentroids.m - 初始化k-means聚类中心

* 表示必须完成的文件

    在第一部分练习中,你将使用脚本ex7.m,第二部分你将使用ex7_pca.m脚本。这些脚本为题目设置数据集并调用你将要编写的函数。你不需要修改这两个脚本其中任何一个,只需要按照本作业中的说明修改其他文件中的函数。

在哪里寻求帮助

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

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

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


1、K均值聚类

    在这个练习中,你将实现K均值算法并将它用于图像压缩。你将首先从一个2D样本数据集开始,它将帮助你直观了解K-means算法的工作原理。之后,你将使用K-means算法进行图像压缩,方法是将图像中出现的颜色数量减少到该图像中最常见的颜色数量。 你将使用ex7.m进行这部分练习。

1.1 实现K-means

    K-means算法是一种自动将相似的数据样本聚在一起的方法。具体地说,你有一个训练集$\{x^{(1)},...,x^{(m)}\}$,(其中$x^{(i)} ∈R^n$),并想将数据分为几个内聚的“簇”。它背后的知识是猜测一个初始化中心点开始,然后反复将样本分配到最接近的聚类中心,然后根据已经分配的结果重新计算聚类中心来改进这个猜测。

    K-means算法如下:

    % Initialize centroids
    centroids = kMeansInitCentroids(X, K);
    for iter = 1:iterations
        % Cluster assignment step: Assign each data point to the
        % closest centroid. idx(i) corresponds to cˆ(i), the index
        % of the centroid assigned to example i
        idx = findClosestCentroids(X, centroids);
        % Move centroid step: Compute means based on centroid
        % assignments
        centroids = computeMeans(X, idx, K);
    end

    该算法的内环重复执行两个步骤:(i)将每个训练实例$x^{(i)}$分配到其最近的聚类中心,(ii)使用分配给它的点重新计算每个聚类中心的均值。K-means算法总是收敛到中心点的最终均值集。注意,收敛解可能并不总是理想的,它依赖于聚类中心的初始设置。因此,在实际操作中,K-means算法通常会运行几次,并具有不同的随机初始化。从不同的随机初始化中选择这些不同解的一种方法是选择成本函数值(失真)最低的解。

    在下一节中,你将分别实现K-means算法的两个阶段。

1.1.1 寻找最近的聚类中心

    在K-means算法的“集群分配”阶段,给定当前聚类中心的位置,该算法将每个训练样本$x^{(i)}$分配到其最近的中心。具体来说,对于我们设置的每个样本i设置$c^{(i)}:= j$,然后最小化$||x^{(i)} − µ_j||^2$,其中$c^{(i)}$是最靠近$x^{(i)}$的中心下标,$µ_j$是第j个聚类中心的坐标值。注意,$c^{(i)}$对应于启动代码中的idx(i)。

    你的任务是完成findClosestCentroids.m中的代码。该函数接受数据矩阵X和聚类中心内所有中心的位置,并应输出一个一维数组idx,其中包含索引(值在{1,…, K},其中K为距离每个训练样本最近中心的总数)。

    你可以通过每个训练样本和每个中心的循环来达到此目的。

    一旦你完成了findClosestCentroids.m中的代码,脚本ex7.m将调用你的代码,应该看到与前3个样本的中心分配对应的输出[1 3 2]。

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

1.1.2 计算聚类中心均值

    给定每个中心点的赋值,算法的第二阶段对每个中心点重新计算赋值点的均值。具体地说,对于每个中心点k我们设置

µ_k := \frac{1}{|C_k|}\sum_{i∈C_k}x^{(i)}

其中$C_k$是分配给中心k的一组样本。具体地说,如果两个样本$x^{(3)}$$x^{(5)}$被分配给中心 k = 2,那么你应该更新 $µ_2 := \frac{1}{2}(x^{(3)} + x^{(5)})$

    现在你应该在computeCentroids.m完成代码。你可以使用中心上的循环来实现这个函数。你还可以对样本使用循环;但是,如果你可以通过不使用这种循环的向量化实现,你的代码可能运行得更快。

    完成computeCentroids.m中的代码后,脚本ex7.m将运行你的代码并在K-means的第一步之后输出中心。

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

1.2 样本集上的K-means

    在完成两个函数(findClosestCentroids和computeCentroids)之后,ex7.m中的下一步将在2D数据集上运行K-means算法,以帮助你了解K-means的工作原理。 你的函数是从runKmeans.m脚本中调用的。我们鼓励你查看函数以了解其工作原理。请注意,代码调用你在循环中实现的两个函数。

    当你运行下一个步骤时,K-means代码将生成一个可视化图像,在每次迭代中引导你了解算法的过程。多次按enter键,查看K-means算法的每个步骤如何更改中心和集群分配。最后,你的图形应该如图1所示。


Figure 1: The expected output.

1.3 随机初始化

    设计ex7.m样本数据集的聚类中心的初始分配,以便你将看到与图1中相同的图。实际上,初始化质心的一个好策略是从训练集中选择随机样本。

    在本练习的这一部分中,你应该使用以下代码完成函数kMeansInitCentroids.m:

    % Initialize the centroids to be random examples
    % Randomly reorder the indices of examples
    randidx = randperm(size(X, 1));
    % Take the first K examples as centroids
    centroids = X(randidx(1:K), :);

    上面的代码首先随机遍历示例的索引(使用randperm)。然后,根据指标的随机排列选择前K个样本。这允许随机选择示例,而不用冒两次选择相同示例的风险。

            ==这部分练习不需要做任何提交==

1.4 用K-means进行图像压缩


Figure 2: The original 128×128 image.

    在这个练习中,你会将K-means应用到图像压缩上。在直观的24位彩色图像表示中,每个像素表示为三个8位无符号整数(范围从0到255),指定红、绿和蓝强度值。这种编码通常称为RGB编码。我们的图像包含成千上万种颜色,在这部分练习中,你将把颜色的数量减少到16种颜色。

    通过进行这种缩小,可以以有效的方式表示(压缩)照片。具体来说,你只需要存储16种所选颜色的RGB值,并且对于图像中的每个像素,你现在只需要在该位置存储颜色的索引(其中只需要4位来表示16种可能性)。
通过进行这种缩小,可以以有效的方式表示(压缩)照片。 具体来说,你只需要存储16种所选颜色的RGB值,并且对于图像中的每个像素,你现在只需要在该位置存储颜色的索引(其中只需要4位来表示16种可能性)。

    在本练习中,你将使用K-means算法来选择将用于表示压缩图像的16种颜色。具体来说,你将把原始图像中的每个像素作为一个数据样本,并使用K-means算法找到在三维RGB空间中对像素进行最佳分组(集群)的16种颜色。一旦你计算了图像上的集群中心,你将使用16种颜色替换原始图像中的像素。

1.4.1 像素上的K-means

    在Octave/MATLAB中,图片可以用下面的方式读取:

    % Load 128x128 color image (bird small.png)
    A = imread('bird small.png');
    % You will need to have installed the image package to used
    % imread. If you do not have the image package installed, you
    % should instead change the following line to
    %
    % load('bird small.mat'); % Loads the image into the variable A

    这将创建一个三维矩阵A,其前两个索引标识一个像素位置,其最后一个索引代表红色,绿色或蓝色。 例如,A(50,33,3)给出第50行第33列的像素的蓝色强度。

    ex7.m中的代码首先加载图像,然后将其再改造以创建m×3像素颜色矩阵(其中m=16384=128×128),并在其上调用K-means函数。

    在找到表示图像的K = 16个颜色后,现在可以使用findClosestCentroids函数将每个像素位置分配给其最近的聚类中心。这允许你使用每个像素的聚类中心分配来表示原始图像。注意,你已经显著减少了描述图像所需的bit数。原始图像在128×128像素的位置上每一个位置都需要24位,因此总大小为128×128×24 = 393 216位。新的表示需要一些开销存储,以16种颜色的字典的形式,每种颜色都需要24位,但是图像本身每个像素位置只需要4位。因此,最终使用的比特数是16×24 + 128×128×4 = 65,920位,相当于将原始图像压缩约6倍。

    最后,你可以通过仅基于质心分配重构图像来查看压缩的效果。具体地说,可以用分配给每个像素位置的聚类中心的平均值替换它。图3显示了我们得到的重建结果。尽管生成的图像保留了原始图像的大部分特征,但我们也看到了一些压缩伪影。


Figure 3: Original and reconstructed image (when using K-means to compress
the image).

            ==这部分练习不需要做任何提交==

1.5 可选练习(不评分):使用你自己的图片

    在本练习中,修改我们提供的代码,以便在你自己的图片上运行。注意,如果你的图片非常大,那么K-means可能需要很长时间才能运行。因此,我们建议你在运行代码之前将图像的大小调整为可管理的大小。你还可以尝试改变K以查看对压缩的影响。


2、主成分分析

    在本练习中,你将使用主成分分析(PCA)来执行降维。你将首先使用一个示例2D数据集进行实验,以直观了解PCA如何工作,然后在5000个人脸图像数据集的更大数据集上使用它。

    提供的ex7_pca.m脚本会指导你完成前半部分练习。

2.1 样本集

    为了帮助你了解PCA的工作原理,你将首先从一个2D数据集开始,该数据集具有一个大变化方向和一个较小变化方向。 脚本ex7_pca.m将绘制训练数据(图4)。 在本练习的这一部分中,你将可视化使用PCA将数据从2D减少到1D时发生的情况。实际上,你可能希望将数据从256维减少到50维; 但是在这个例子中使用低维数据可以让我们更好地可视化算法。


Figure 4: Example Dataset 1

2.2 实现PCA

    在本部分练习中,你将实现PCA。PCA由两个计算步骤组成:首先,计算数据的协方差矩阵。然后,使用Octave/MATLAB的SVD函数计算特征向量$U_1, U_2,…,U_n$。这些将与数据变化的主要组成部分相对应。

    在使用PCA之前,首先通过从数据集中减去每个要素的平均值来标准化数据,然后缩放每个维度以使它们处于相同的范围内,这一点很重要。在提供的脚本ex7_pca.m中,已使用featureNormalize函数为你执行此规范化。

    规范化数据后,你可以运行PCA来计算主成分。 你的任务是完成pca.m中的代码以计算数据集的主成分。 首先,你应该计算数据的协方差矩阵,其由下式给出:

Σ = \frac{1}{m}X^TX

其中X是数据矩阵,其中包含行中的样本,m是样本的数量。 注意,Σ是n×n矩阵而不是求和运算符。

    计算协方差矩阵后,可以在其上运行SVD来计算主成分。在Octave/MATLAB中,你可以使用以下命令运行SVD:[U, S, V] = svd(Sigma),其中U将包含主成分,S将包含对角矩阵。

    完成pca.m后,ex7_pca.m脚本将在示例数据集上运行PCA并绘制找到的相应主成分(图5)。 该脚本还将输出找到的顶部主成分(特征向量),你应该会看到输出约为[-0.707 -0.707]。 (Octave/MATLAB可能会输出负数,因为U1和-U1对于第一个主成分是同等有效的选择。)


Figure 5: Computed eigenvectors of the dataset

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

2.3 使用PCA降维

    在计算主成分之后,你可以通过将每个样本投影到较低维度空间$x^{(i)}→z^{(i)}$(例如,将数据从2D投影到1D)来使用它们来减少数据集的要素维度。 在本练习的这一部分中,你将使用PCA返回的特征向量,并将示例数据集投影到一维空间中。

    实际上,如果你使用的是学习算法,如线性回归或神经网络,你现在可以使用投影数据而不是原始数据。 通过使用投影数据,你可以更快地训练模型,因为输入中的维度较少。

2.3.1 将数据投影到主成分上

    你现在应该在projectData.m中完成代码。 具体来说,你将获得一个数据集X,主成分U和要减少到K的所需维数。你应该将X中的每个示例投影到U中的顶部K组件上。请注意,U中的前K个组件是 通过U的前K列,即U_reduce = U(:, 1:K)。

    完成projectData.m中的代码后,ex7_pca.m会将第一个示例投影到第一个维度,你应该看到大约1.481的值(如果得到$-U_1$而不是$U_1$,则可能看到-1.481)。

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

2.3.2 重建数据的近似值

    将数据投影到较低维空间后,你可以通过将数据投影回原始高维空间来近似恢复数据。 你的任务是完成recoverData.m以将Z中的每个样本投影回原始空间并在X_rec中返回恢复的近似值。

    完成recoverData.m中的代码后,ex7_pca.m将恢复第一个样本的近似值,你应该看到值约为[-1.047 -1.047]。

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

2.3.3 可视化投影

    在完成projectData和recoverData之后,ex7_pca.m现在将执行投影和近似重建,以显示投影如何影响数据。 在图6中,原始数据点用蓝色圆圈表示,而投影数据点用红色圆圈表示。投影有效地仅保留$U_1$给出的方向的信息。


Figure 6: The normalized and projected data after PCA.

2.4 面部图像数据集

    在本练习的这一部分中,你将在面部图像上运行PCA,以了解它如何在实践中用于降低尺寸。 数据集ex7faces.mat包含面部图像的数据集X,每个32×32为灰度。 X的每一行对应于一个面部图像(长度为1024的行向量)。 ex7_pca.m的下一步将加载并可视化这些面部图像中的前100个(图7)。


Figure 7: Faces dataset

2.4.1 基于面部图像的PCA

    要在面部数据集上运行PCA,我们首先通过从数据矩阵X中减去每个要素的平均值来规范化数据集。脚本ex7_pca.m将为你执行此操作,然后运行你的PCA代码。 运行PCA后,你将获得数据集的主成分。请注意,U(每行)中的每个主成分都是长度为n的向量(对于面数据集,n = 1024)。事实证明,我们可以通过将每个主成分重新塑造成与原始数据集中的像素对应的32×32矩阵来可视化这些主成分。 脚本ex7_pca.m显示描述最大变化的前36个主成分(图8)。 如果需要,还可以更改代码以显示更多主成分,以了解它们如何捕获越来越多的详细信息。


Figure 8: Principal components on the face dataset

2.4.2 降维

    现在你已经计算了面部数据集的主成分,你可以使用它来减少面部数据集的维度。这允许你使用较小输入尺寸(例如,100维)的学习算法而不是原始1024维度。 这有助于加快学习算法的速度。

    ex7_pca.m的下一部分将仅将面部数据集投影到前100个主成分上。具体地说,现在通过向量$z^{(i)}∈R^{100}$描述每个面部图像。

    要了解降维中丢失的内容,可以仅使用投影数据集恢复数据。在ex7_pca.m中,执行数据的近似恢复,并且原始和投影的面部图像并排显示(图9)。从重建中,你可以观察到面部的一般结构和外观被保留,同时细节丢失。这是数据集大小的显着减少(超过10倍),可以帮助显着加快你的学习算法。例如,如果你正在训练神经网络来执行人物识别(给定面部图片,预测人物的身份),则可以使用仅100维度的尺寸缩减输入而不是原始像素。


Figure 9: Original images of faces and ones reconstructed from only the top
100 principal components.

2.5 可选练习(不评分):可视化PCA

    在前面的K-means图像压缩练习中,你在三维RGB空间中使用了K-means算法。在ex7_pca.m脚本的最后一部分中,我们提供了使用scatter3函数可视化此3D空间中最终像素分配的代码。 每个数据点都根据其分配的群集着色。 你可以在图上拖动鼠标以旋转并以3维方式检查此数据。

    事实证明,在3维或更大维度上可视化数据集可能很麻烦。因此,通常希望仅以丢失一些信息为代价以2D显示数据。 在实践中,PCA通常用于减少数据的维度以用于可视化目的。 在ex7_pca.m的下一部分中,脚本将PCA的实现应用于三维数据,将其缩小为2维,并在2D散点图中显示结果。 可以将PCA投影视为旋转,选择最大化数据传播的视图,这通常对应于“最佳”视图


Figure 10: Original data in 3D


Figure 11: 2D visualization produced using PCA

提交和评分

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

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

点个赞呗:程序员虾说 » 吴恩达机器学习作业翻译7——kmeans and PCA

赞 (8) 打赏

评论 0

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

请作者喝杯咖啡~

支付宝扫一扫打赏

微信扫一扫打赏