coursera-斯坦福-机器学习-吴恩达-第8周笔记-无监督学习

无监督学习主要涉及聚类算法和降维技术。聚类算法中，K-means是一种广泛使用的无监督学习方法，通过将数据点聚类到k个簇中，利用目标函数优化簇中心。K-means的初始化方法多样，随机初始化和类别中心的初始化是常见策略。选择k值的方法包括肘部法则、轮廓分析和交叉验证。PCA则是一种降维技术，通过计算协方差矩阵的特征值和特征向量，找到主成分以降低数据维度。PCA在图像压缩和可视化中表现出色，但需要注意过拟合的风险。两种方法各有优劣，K-means适用于聚类，PCA适用于降维。

Coursera - Stanford University - Machine Learning course materials, including notes from Andrew Ng's 8th week on Unsupervised Learning.

文章目录

Coursera-斯坦福-机器学习-吴恩达课程第8周笔记：无监督学习

1. 聚类算法简介

1.1 聚类算法概述

1.2 K-Means算法

1.2.1 K-means的目标函数

1.2.2 随机选择初始质心以避免陷入局部最优解

1.2.3 选择合适的类别数量：基于肘部法则的K值选择

1.3 课程练习：无监督学习应用案例

* 2 维数约减 (dimensionality reduction)
* * 2.1数据压缩
  * 2.2数据可视化

* 3维度约简-主成分分析法PCA
* * 3.1 PCA是做什么的
  * 3.2PCA的计算过程❤❤❤

* 4应用PCA
* * 4.1PCA反向压缩
  * 4.2怎么选择维度k
  * 4.3使用PCA的场景

• 总复习quiz与编程课程
  • 5.1 quiz主成份分析部分
    • 5.2 编程题模块
    • 1节 K-means聚类算法
  • 2 主成分分析章节

对于无监督学习我们主要学习两种算法：聚类（K-means）和维度约简（PCA法）。

1聚类算法clutering

1.1聚类算法简介

无监督学习：在无监督学习中，我们处理的是一组无标签的训练数据。这些数据之间没有关联的标记信息。如图所示：

[外链图片转存失败(img-VKkgpvIU-1566960756437)(http://oqy7bjehk.bkt.clouddn.com/17-12-16/62891890.jpg)]

通过分析收集到的数据，我们观察到的数据集包含大量未标注的数据样本。这些样本仅由一组输入变量 x 的值构成，而无法获得对应的输出变量 y 的信息。在训练过程中，我们只能获取输入变量 x 的值，而无法获得对应的输出变量 y 的信息。

就其数据而言，其中一种可能的结构是其所有数据可以大致分为两个类别或组别。由此可见，该算法通过将数据划分为类别或组别来实现，被归类为聚类算法。属于无监督学习范畴的第一种算法。

注意，聚类算法仅限于无监督学习的一种形式，而并非所有的无监督学习都属于聚类算法这一范畴。

1.2K-means

K-means也是聚类算法中最简单的一种。但是里面包含的思想却是不一般。

K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下：

随机选取k个聚类质心点（cluster centroids）为

。

重复下面过程直到收敛 {

• 对于每一个样例i，计算其应该属于的类

• 对于每一个类j，重新计算该类的质心

}

下图展示了对n个样本点进行K-means聚类的效果，这里k取2。

一个练习题：

[外链图片转存失败(img-F2eVM398-1566960756443)(http://oqy7bjehk.bkt.clouddn.com/17-12-16/7484812.jpg)]

1.2.1kmeans的目标函数

在大多数现有的 监督学习方法中。 大部分监督学习模型都具有一个目标函数 或损失函数（又称为损失函数）需要通过算法进行最小化处理。

事实上 K均值也有 一个优化目标函数或者 需要最小化的代价函数。

注意，这个值只会随着迭代下降，不会上升。

1.2.2随机初始化

这一节我们讨论： 如何避开局部最优来构建K均值聚类方法 。

存在多种不同的方法可用于随机 初始化聚类中心，然而实证研究表明，其中一种方法在实证研究中被发现显著优于其他大多数方法。

[外链图片转存失败(img-vBXgequh-1566960756446)(http://oqy7bjehk.bkt.clouddn.com/17-12-18/20474706.jpg)]

可以避免 可能局部，获得全局最优的结果 。

1.2.3选择类别数

探讨K-均值聚类的最后一个细节：我想寻找选择聚类数目更有效的方法。或者探讨选择参数K值的方式。

说实话 这个问题上没有一个 非常标准的解答 、或者能自动解决它的方法。

通过观察可视化图形、分析聚类算法的输出结果以及其他因素来手动确定聚类数目，这是目前决定聚类数目 最主要 的方法，也是最常用 的手段。

两种常见方法：

1. 肘部法则

例如下面的例子，分别考虑3和5，画出loss图像。

[外链图片转存失败(img-FTukxHBG-1566960756447)(http://oqy7bjehk.bkt.clouddn.com/17-12-18/26571725.jpg)]

2. 从后续需求（生意）角度考虑

[外链图片转存失败(img-zzShPOzB-1566960756449)(http://oqy7bjehk.bkt.clouddn.com/17-12-18/6770429.jpg)]

下面有个练习题：

[外链图片转存失败(img-l4rl1wkt-1566960756450)(http://oqy7bjehk.bkt.clouddn.com/17-12-18/21753139.jpg)]

1.3考试quiz

Among the following tasks, which could be appropriate for K-means clustering? Select all that apply.

• 通过分析网站用户的使用模式，识别出不同类型的用户群体。

• 基于历史天气数据，预测明天的天气状况。

• 对于大量收到的邮件，需要判断其是否为垃圾邮件。

• 通过分析来自多个新闻网站的新闻文章集合，确定主要涵盖的主题内容。

第二题：
[外链图片转存失败(img-JQP9TP0N-1566960756451)(http://oqy7bjehk.bkt.clouddn.com/17-12-18/43376572.jpg)]

K-means operates as an iterative process, and two of the following steps are iteratively carried out within its inner loop.

K-means是一种迭代算法，以下两个步骤在其内部循环中重复执行。哪两个？

The clustering assignment process, where the parameters c(i) are being updated.
Adjust the positions of the cluster centroids, where the centroids μk are being updated.

Assume you have an unlabeled dataset {x(1),…,x(m)}. When applying the K-means algorithm with 50 distinct random initializations, you obtain 50 different clusterings of the dataset. What is the recommended approach for selecting the most suitable clustering among these 50?答案C

Visualize the data distribution and the corresponding cluster centroids, and select the clustering configuration that exhibits the most cohesive cluster centroids. Manually inspect the various clusterings generated, and choose the one that appears most coherent. Calculate the distortion function J(c(1),…,c(m),μ1,…,μk), and select the configuration that achieves the lowest value of this function. Use the elbow method to determine the optimal number of clusters.

5. 第 5 个问题 请判断以下哪些陈述是正确的？请全部选择。正确选项为BC

• Since K-Means is an unsupervised learning algorithm, it cannot overfit the data, and thus it is always better to have as large a number of clusters as is computationally feasible.
• If we are worried about K-means getting stuck in bad local optima, one way to ameliorate (reduce) this problem is if we try using multiple random initializations.-
• For some datasets, the “right” or “correct” value of K (the number of clusters) can be ambiguous, and hard even for a human expert looking carefully at the data to decide.
• The standard way of initializing K-means is setting μ1=⋯=μk to be equal to a vector of zeros.

2 维数约减 (dimensionality reduction)

在本节中，我们具体阐述第二类无监督学习问题，即维数约减技术，一种用于降低数据维度的技术。

我们希望使用维数约简 的原因有以下几个 ：

1. 数据压缩是其中一个主要原因。
   数据压缩不仅通过压缩数据，使得其占用更少的计算机内存和硬盘空间，还能提高算法的运行速度。

2. 另一个原因就是可视化。通过降维进行可视化，进而更好地理解数据。

2.1数据压缩

在实际工作中，数据的维度往往达到100+。因此，进行数据维度约简是十分必要的。

举一个例子：3维降成2维：

[外链图片转存失败(img-mvrgTTXe-1566960756452)(http://oqy7bjehk.bkt.clouddn.com/17-12-18/95447653.jpg)]

2.2数据可视化

该研究面临的数据维度挑战，具体表现为该国家的GDP数据具有50维特征，这使得传统的可视化方法难以直接呈现。为解决这一问题，研究采用了降维技术，通过二维图表大致反映数据分布特征。具体而言，横轴维度可选取国家面积、GDP总量等指标，纵轴则可设置人均GDP、幸福度等指标，从而实现多维数据的简明展示。

在本节中，我们将介绍这个算法，PCA（主成分分析法）。如何确定能够有效地表达其他特征的特征？

3维度约简-主成分分析法PCA

在降维问题领域，主成分分析法（Principal Component Analysis, PCA）如今已广泛应用于多个学科，被视为解决降维问题的常见方法。

3.1 PCA是做什么的

PCA是一种方法，能够找到一个低维子空间，将数据投影到该子空间中，以最小化投影误差的平方（即最小化各数据点与其在低维空间中的投影点之间的距离平方和）

定义：将数据从n维空间投影至k维空间（k < n），在该空间中寻找k个单位向量来表示数据，使得数据点在该面上的投影误差最小。例如，二维降到一维和三维降到二维。

[外链图片转存失败(img-Mu4fVQMr-1566960756457)(http://oqy7bjehk.bkt.clouddn.com/17-12-19/36897107.jpg)]

下面介绍 线性回归与2维PCA的区别：虽然都是找一条直线去拟合但是，

1. 计算loss的方式不同（垂直）。
2. PCA没有标签Y（非监督）。

[外链图片转存失败(img-SKPv75TO-1566960756458)(http://oqy7bjehk.bkt.clouddn.com/17-12-19/18002544.jpg)]

3.2PCA的计算过程❤❤❤

设有m条n维数据。将原始数据按列组成n行m列矩阵X

1. 对X中的每行（每个字段属性）进行零均值归一化处理，即为每行数据减去该行的均值。
2. 计算协方差矩阵。

通过使用svd函数，计算协方差矩阵的特征值及其对应的特征向量。这些特征向量能够充分地代表原始数据的信息。将特征向量按照其对应特征值的大小，从上到下按行排列成矩阵，并选取前k行组成矩阵U_r。通过计算Y=U^T \times X，即可得到降维至k维后的数据。

例子如下： 假设我们得到的2维数据如下：

行代表了样本，列代表了属性，这里共有10个样本，每个样本包含两个属性。可以认为，有10篇学术论文，x是每篇论文中"学习"一词的TF-IDF值，y是"学习"与"研究"主题之间的相关性评分。同样地，也可以认为有10辆汽车，x是车辆的平均行驶速度（km/h），y是车辆的燃料效率（mpg），以此类推。

1. 第一步均值归一化

分别计算x和y的平均值，接着对所有样例进行处理，去除各自对应的均值。其中，x的均值为1.81，y的均值为1.91。经过均值去除后，一个样例的值变为（0.69,0.49），得到的结果是...

2. 计算协方差矩阵

求特征协方差矩阵，如果数据是3维，那么协方差矩阵是

这里只有x和y（两维），求解得

在对角线位置上，分别记录着变量x和y的方差值；而非对角线元素则代表协方差。当协方差数值为正时，表明x和y呈现出正相关关系，即一个变量增加，另一个变量也会随之增加；当协方差为负时，x和y之间则呈现负相关关系，一个变量增加，另一个变量会减少；若协方差为零，则说明x和y之间不存在线性相关性。协方差的绝对值越大，说明x和y之间的相互影响程度越高；反之，绝对值越小，说明两者之间的相互影响越弱。

3. 求协方差的特征值和特征向量，得到

在上文中，我们有两个特征值，每个特征值对应一个特征向量。特征值0.0490833989对应一个特征向量。在本研究中，所有特征向量均被归一化为单位向量。

4. 取前k个最有代表意义的特征向量：

通过从大到小的顺序对特征值进行排序操作，随后选取其中最大的k个特征值。接着，将这些特征值对应的k个特征向量作为列向量排列，从而形成特征向量矩阵。

在本例中，仅有两个特征值，我们选择了其中最大的那个特征值，其值为1.28402771，对应的特征向量为 (0.677873399, 0.735178656)。

5. 得到最后的数据

将样本点投影至所选特征向量空间中。假设样例数为m，特征数为n，则减去均值后的样本矩阵DataAdjust为m×n维，协方差矩阵为n×n维。选取的k个特征向量构成的矩阵EigenVectors为n×k维。经过投影变换后，得到的数据FinalData为(0.677873399, 0.735178656)。

通过某种方式，将原始样例的n维特征空间转换为k维空间，其中这k维特征正是原始特征在k维空间中的投影。

4应用PCA

4.1PCA反向压缩

通过主成分分析法，高维数据被降维至低维空间；逆向应用主成分分析法，低维数据得以恢复至高维空间。

因为Y=U^T \times X，所以换算一下 U\times Y= X这里的X只是近似值。

那么当n和k相同的时候会发生什么呢？看下题：

[外链图片转存失败(img-YrUQw4X4-1566960756466)(http://oqy7bjehk.bkt.clouddn.com/17-12-19/34785784.jpg)]

1. U的维度为方阵
2. 反着求x，为原值
3. 保存率为100%

4.2怎么选择维度k

在PCA算法中，我们通过降维技术将n维特征变量转换为k维特征变量。这个数字k被定义为主成分的数量，或者说是保留的主成分的数量。在本次视频中，我将向大家提供一些参考信息，阐述人们在选择PCA参数k时的思考过程。

我们先来思考两个值：

1. 第一个是：PCA 所做的是 尽量最小化 平均平方映射误差 (Average Squared Projection Error) 。
2. 第二个是：我还要定义一下 数据的总变差 (Total Variation) 。 它的意思是 “平均来看 我的训练样本 距离零向量多远？

我们把两个数的比值作为衡量PCA算法的有效性，比如

[外链图片转存失败(img-B3RSTuap-1566960756466)(http://oqy7bjehk.bkt.clouddn.com/17-12-19/74910273.jpg)]

一种有效的方法是设定一个阈值，然后测试k值，观察最小的k值是否合适。具体步骤如下：首先，根据问题需求设定一个初始阈值；其次，通过迭代计算测试k值；最后，记录并分析测试结果，以确定最小的k值是否合适。

[外链图片转存失败(img-PRqEN8lX-1566960756468)(http://oqy7bjehk.bkt.clouddn.com/17-12-19/85328785.jpg)]

这个技巧在于，svd函数会返回一个对角矩阵S，其中的元素可以快速计算这个阈值。

4.3使用PCA的场景

主成份分析法主要有以下用途：

1. 数据压缩
   1. 减少内存的占用、存储硬盘
   2. 加速算法的运转

2. 数据可视化：3维2维

有些人认为PCA也可以用来防止过拟合，但这种方法并不奏效。另一种更有效的方法是使用正则化技术。正则化通过最小化损失函数来利用y标签信息，从而保留了更多的数据特征。相比之下，PCA仅基于x的分布剔除了部分特征，导致大量信息丢失。

总结一下PCA的用法：

[外链图片转存失败(img-ltVgJDjT-1566960756468)(http://oqy7bjehk.bkt.clouddn.com/17-12-19/98230239.jpg)]

5总复习quiz与编程

5.1quiz主成份分析：

Given a 2D dataset, which of the following figures correspond to possible values that PCA may return for u₁ (the first eigenvector or first principal component)? Check all that apply (you may have to check more than one figure). 答案：AB

Which of the following is a reasonable approach to determine the number of principal components k? (Recall that n is the dimensionality of the input data and m is the number of input examples.)答案：C

C. Select k as the minimal number such that 99% of the variance is preserved.

Imagine someone tells you that they conducted PCA in such a way that 95% of the variance was preserved. What equivalent statement can they make?答案：C

• \frac{ \frac{1}{m} \sum_{i=1}^m ||x^{(i)}- x^{(i)}_{approx}||^2}{\frac{1}{m} \sum_{i=1}^m ||x^{(i)}||^2} \leq 0.05

第4个问题：从以下陈述中，哪些是正确的？请勾选所有适用的选项。

Even when all the input features have very similar scales, it is still necessary to perform mean normalization (to ensure that each feature has a zero mean) prior to conducting PCA.

Given input data x∈Rn, running PCA is meaningful only when k satisfies k≤n. (Especially, running PCA with k=n is feasible but not beneficial, while values of k>n are not appropriate.)

4. 第 5 个问题 Which of the following are considered recommended applications of PCA? Select all that apply.答案为AC

Data compression: This technique enables lowering the dimensionality of your data, thereby reducing the memory or disk space it occupies.
Data compression: By applying dimensionality reduction to the input data x(i), which will be used in a supervised learning context (e.g., applying PCA will accelerate the training of your supervised learning algorithm).

5.2编程题

在本次练习中，您将应用K均值聚类算法于图像压缩任务中。在第二部分，您将进行主成分分析以提取面部图像的低维表示。

1 K-means clustering

先从二维的点开始，使用K-means进行分类。

1.1 Implement K-means

K-means算法的步骤如上所述，在每次迭代过程中，首先，对所有数据点重新分配至最近的簇中，然后，更新每一类的中心坐标位置。

1.1.1 Finding closest centroids

对每个example，根据公式：

确定与之最近的centroid，并进行标记。当存在多个具有相同最小距离的centroid时，可任选其中一个进行标记。

打开findClosestCentroids.m代码如下：

    for i=1:size(X,1)  
    adj=sqrt((X(i,:)-centroids(1,:))*(X(i,:)-centroids(1,:))');  
    idx(i)=1;  
    for j=2:K  
        temp=sqrt((X(i,:)-centroids(j,:))*(X(i,:)-centroids(j,:))');  
        if(temp<adj)  
            idx(i)=j;  
            adj=temp;  
        end  
    end  
    end

1.1.2 Compute centroid means

对每个centroid，根据公式：

求出该类所有点的平均值（即中心点）进行更新。

打开computeCentroids.m写入：

    for i=1:K  
    if(size(find(idx==i),2)~=0)  
        centroids(i,:)=mean(X(find(idx==i),:));  
    else  
        centroids(i,:)=zeros(1,n);  
    end  
    end

1.2 K-means on example dataset

ex7.m中提供了一个例子，其中中 K 已经被手动初始化过了。

将数据集划分为三个类别，迭代次数设置为10次。三个类别各自的中心点初始化坐标为(3,3)、(6,2)和(8,5)。生成如下所示的图像。原始状态的图像如下所示：

进行10次迭代后的图像：

通过观察，三堆点被精确地分成了三类。在图像中，同时描绘了中心点的运动路径。

1.3 Random initialization

为了确保结果的正确性，便于后续分析和验证，我们在ex7.m中采用了K的初始化方法。而在实际应用中，我们应随机进行初始化以确保算法的收敛性和稳定性。

    randidx = randperm(size(X, 1));
    % Take the first K examples as centroids
    centroids = X(randidx(1:K), :);

1.4 Image compression with K-means

采用K-means算法进行图像压缩。以128×128像素的图像为例，使用RGB颜色模式，该图像占用128×128×24=393216个bit的空间。在对图像进行压缩时，我们将图像的颜色空间划分为16个类别。每个类别中的颜色将被其质心（centroid）对应的颜色所替代，从而将图像的空间压缩至16×24 + 128×128×4=65920个bit。通过题目中的示例，我们可以观察到压缩后的效果，具体实现方式如下：

2主成分分析

在这个练习中，您将应用主成分分析（PCA）来实现降维。 您将首先使用2D数据集来直观理解PCA的工作原理，接着将其应用于包含5000张面部图像的大规模数据集。

所提供的脚本ex7 pca.m将帮助您逐步完成练习的前半部分。

先对例子中的二维向量实现降低到一维。
绘制散点图如下：

2.2 Implementing PCA

首先在开始阶段需要计算出数据的协方差阵（covariance matrix）然后在接下来的步骤中调用Octave或MATLAB中的SVD函数以求取特征向量（eigenvector）

首先，我们对数据实施归一化处理和特征缩放。 协方差矩阵的具体计算方式如下：

然后用SVD函数求特征向量。
故完成pca.m如下：

    [U,S,V] = svd(1/m * X' * X);

把求出的特征向量绘制在图上：

2.3 Dimensionality reduction with PCA

将高维的examples投影到低维上。

2.3.1 Projecting the data onto the principal components

完成projectData.m如下：

    Ureduce = U(:,1:K);
    Z = X * Ureduce;

2.3.2 Reconstructing an approximation of the data

从投影过的低维恢复高维recoverData.m：

    Ureduce = U(:, 1:K);
    X_rec = Z * Ureduce';

2.3.3 Visualizing the projections

通过观察上图，可以发现恢复后的图仅包含了一个特征向量上的信息，而垂直方向的信息则完全丢失。

2.4 Face image dataset

对人脸图片进行降维处理。在ex7faces.mat文件中存储了大量的灰度人脸图像，每张图像的尺寸为32 × 32像素。因此，每个向量的维度为32 × 32，总计1024维。

2.4.1 PCA on faces

通过主成分分析法提取主成分，将其还原为32×32的矩阵，对结果进行可视化展示，具体如下：仅展示前36个。

2.4.2 Dimensionality reduction

取前100个特征向量进行投影，

可以观察到，当对人脸部进行降维处理时，其大致轮廓特征得以保留，但细节信息则有所缺失。这让我们想到，在使用神经网络进行人脸识别训练时，适当采用降维技术可以有效提升运算速度。