吴恩达教授的机器学习课程的第八周相关内容：

1、聚类(Clustering)

1.1、无监督学习：简介

在一个典型的监督学习中，我们有一个有标签的训练集，我们的目标是找到能够区分正样本和负样本的决策边界，在这里的监督学习中，我们有一系列标签，我们需要据此拟合一个假设函数。与此不同的是，在非监督学习中，我们的数据没有附带任何标签，我们拿到的
数据就是这样的：
在这里我们有一系列点，却没有标签。因此，我们的训练集可以写成只有 x(1) , x(2) ……
一直到 x(m ) ，我们没有任何标签 y。因此，图上画的这些点没有标签信息。也就是说，在非监督学习中，我们需要将一系列无标签的训练数据，输入到一个算法中，然后我们告诉这个算法，快去为我们找找这个数据的内在结构给定数据。我们可能需要某种算法帮助我们寻找一种结构。图上的数据看起来可以分成两个分开的点集（称为簇），一个能够找到我圈出的这些点集的算法，就被称为聚类算法。
小结：聚类是无监督学习的一种，无监督学习只有示例没有标记。

1.2、K-均值算法

K-均值是最普及的聚类算法，算法接受一个未标记的数据集，然后将数据聚类成不同的
组。K-均值是一个迭代算法，假设我们想要将数据聚类成 n 个组，其方法为:
首先选择 k 个随机的点，称为聚类中心（cluster centroids） ；
对于数据集中的每一个数据，按照距离 K 个中心点的距离，将其与距离最近的中心点关
联起来，与同一个中心点关联的所有点聚成一类。
计算每一个组的平均值，将该组所关联的中心点移动到平均值的位置。
重复上述步骤，直到聚类中心不再变化。
小结：K均值算法是很好用的聚类算法，算法分为两个步骤，第一个 for 循环是赋值步骤， 即： 对于每一个样例 i，计算其应该属于的类。 第二个 for 循环是聚类中心的移动，即： 对于每一个类 k，重新计算该类的图心。

1.3、优化目标

K-均值最小化问题，是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和，
因此 K-均值的代价函数（又称畸变函数 Distortion function）为：

其中$\mu _{c^{i}}$μci​代表与 x( i) 最近的聚类中心点。 我们的的优化目标便是找出使得代价函数最小的 c(1) ,c(2) ,…, c(m )和 $\mu _{1}$μ1​ ,$\mu _{2}$μ2​,…$\mu _{k}$μk​,回顾刚才给出的K-均值迭代算法，我们知道，第一个循环是用于减小c( ) i 引起的代价，而第二个循环则是用于减小 $\mu _{i}$μi​引起的代价。迭代的过程一定会是每一次迭代都在减小代价函数，不然便是
出现了错误。
小结：总结出我们优化的目标。

1.4、随机初始化

在运行 K-均值算法的之前，我们首先要随机初始化所有的聚类中心点，下面介绍怎样
做：

1. 我们应该选择 K<m，即聚类中心点的个数要小于所有训练集实例的数量
2. 随机选择 K 个训练实例，然后令 K 个聚类中心分别与这 K 个训练实例相等
   K-均值的一个问题在于，它有可能会停留在一个局部最小值处，而这取决于初始化的情
   况
   为了解决这个问题，我们通常需要多次运行 K-均值算法，每一次都重新进行随机初始
   化，最后再比较多次运行 K-均值的结果，选择代价函数最小的结果。这种方法在 k 较小的时候（2–10）还是可行的，但是如果 k 较大，这么做也可能不会有明显地改善。
   小结：聚类中心位置的选取，当k较小时，可以通过选择代价函数最小的结果来比较。

1.5、选择聚类数

没有所谓最好的选择聚类数的方法，通常是需要根据不同的问题，人工进行选择的。选
择的时候思考我们运用 K-均值算法聚类的动机是什么，然后选择能最好服务于该目的标聚
类数。关于“肘部法则”，我们所需要做的是改变 k 值，也就是聚类类别数目的总数。我们用一个聚类来运行 K 均值聚类方法。
我们可能会得到一条类似于这样的曲线。像一个人的肘部。这就是“肘部法则”所做的，但有时不会起作用。
小结：关于聚类数的选择，首先要明确自己的目标，肘部法则的原理就是选择一个代价函数减少最快时对应的k值。

2、降维(Dimensionality Reduction)

2.1、动机一：数据压缩

第二种类型的无监督学习问题，称为降维。有几个不同的的原因使你可能想要做降维。一是数据压缩，后面我们会看了一些视频后，数据压缩不仅允许我们压缩数据，因而使用较少的计算机内存或磁盘空间，但它也让我们加快我们的学习算法。
关于降维：依照一定的规则把降低数据的维度
二维降成一维
三维降成二维

小结：降维用于数据压缩。

2.2、动机二：数据可视化

在许多及其学习问题中，如果我们能将数据可视化，我们便能寻找到一个更好的解决方
案，降维可以帮助我们。

假使我们有有关于许多不同国家的数据，每一个特征向量都有 50 个特征（如， GDP，
人均 GDP，平均寿命等）。如果要将这个 50 维的数据可视化是不可能的。使用降维的方法
将其降至 2 维，我们便可以将其可视化了。
这样做的问题在于，降维的算法只负责减少维数，新产生的特征的意义就必须由我们自己去发现了。
小结：降维用于数据可视化。

2.3、主成分分析问题

主成分分析（PCA）是最常见的降维算法。
在 PCA 中，我们要做的是找到一个方向向量（Vector direction），当我们把所有的数据
都 投射到该向量上时，我们希望投射平均均方误差能尽可能地小。方向向量是一个经过原
点的向量，而投射误差是从特征向量向该方向向量作垂线的长度。
下面给出主成分分析问题的描述：
问题是要将 n 维数据降至 k 维，目标是找到向量u(1) ,u(2) ,…,u (k) 使得总的投射误差最
小。主成分分析与线性回顾的比较：
主成分分析与线性回归是两种不同的算法。主成分分析最小化的是投射误差（Projected
Error） ， 而线性回归尝试的是最小化预测误差。线性回归的目的是预测结果，而主成分分析不作任何预测。
上图中，左边的是线性回归的误差（垂直于横轴投影），右边则是主要成分分析的误差
（垂直于红线投影）。
CA 将 n 个特征降维到 k 个，可以用来进行数据压缩，如果 100 维的向量最后可以用 10
维来表示，那么压缩率为 90%。同样图像处理领域的 KL 变换使用 PCA 做图像压缩。但 PCA要保证降维后，还要保证数据的特性损失最小。
PCA 技术的一大好处是对数据进行降维的处理。我们可以对新求出的“主元”向量的重
要性进行排序，根据需要取前面最重要的部分，将后面的维数省去，可以达到降维从而简化
模型或是对数据进行压缩的效果。同时最大程度的保持了原有数据的信息。
PCA 技术的一个很大的优点是，它是完全无参数限制的。在 PCA 的计算过程中完全不
需要人为的设定参数或是根据任何经验模型对计算进行干预，最后的结果只与数据相关，与
用户是独立的。
但是，这一点同时也可以看作是缺点。如果用户对观测对象有一定的先验知识，掌握了
数据的一些特征，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高。
小结：降维的PCA算法的优缺点。

2.4、主成分分析算法

PCA 减少 n 维到 k 维：
第一步是均值归一化。 我们需要计算出所有特征的均值， 然后令 xj= xj -μj。 如果特征是
在不同的数量级上， 我们还需要将其除以标准差 σ2。
第二步是计算协方差矩阵（covariance matrix） Σ：

第三步是计算协方差矩阵 Σ 的特征向量（eigenvectors） :
在 Octave 里我们可以利用奇异值分解（singular value decomposition）来求解， [U, S, V]=
svd(sigma)。
对于一个 n×n 维度的矩阵，上式中的 U 是一个具有与数据之间最小投射误差的方向向
量构成的矩阵。如果我们希望将数据从 n 维降至 k 维，我们只需要从 U 中选取前 K 个向量，获得一个 n×k 维度的矩阵，我们用U reduce 表示，然后通过如下计算获得要求的新特征向量
其中 x 是 n×1 维的，因此结果为 k×1 维度。注，我们不对方差特征进行处理。
小结：PCA算法的步骤。

2.5、选择主成分的数量

主要成分分析是减少投射的平均均方误差：

训练集的方差为：

我们希望在平均均方误差与训练集方差的比例尽可能小的情况下选择尽可能小的 k 值。
如果我们希望这个比例小于 1%，就意味着原本数据的偏差有 99%都保留下来了，如果
我们选择保留 95%的偏差，便能非常显著地降低模型中特征的维度了。
我们可以先令 k=1，然后进行主要成分分析，获得Ureduce 和 z，然后计算比例是否小于
1%。如果不是的话再令 k=2，如此类推，直到找到可以使得比例小于 1%的最小 k 值（原因
是各个特征之间通常情况存在某种相关性）。
还有一些更好的方式来选择 k， 当我们在 Octave 中调用“svd”函数的时候， 我们获得三
个参数： [U, S, V] = svd(sigma)。

其中的 S 是一个 n×n 的矩阵，只有对角线上有值，而其它单元都是 0，我们可以使用这
个矩阵来计算平均均方误差与训练集方差的比例：

小结：根据平均均方误差与训练集方差的比例来选择主成分的数量。

2.6、重建的压缩表示

在以前的视频中，我谈论 PCA 作为压缩算法。在那里你可能需要把 1000 维的数据压缩
100 维特征，或具有三维数据压缩到一二维表示。所以，如果这是一个压缩算法，应该能回
到这个压缩表示，回到你原有的高维数据的一种近似。
所以，给定的 z( ) i ，这可能 100 维，怎么回到你原来的表示 x( ) i ，这可能是 1000 维的数
组？
PCA 算法，我们可能有一个这样的样本。如图中样本 x(1) , x(2) 。我们做的是，我们把这
些样本投射到图中这个一维平面。然后现在我们需要只使用一个实数，比如 Z (1)，指定这些点的位置后他们被投射到这一个三维曲面。给定一个点 z(1) ，我们怎么能回去这个原始的二维空间呢？ x 为 2 维， z 为 1 维，

如你所知，这是一个漂亮的与原始数据相当相似。所以，这就是你从低维表示 z 回到未
压缩的表示。我们得到的数据的一个之间你的原始数据 x，我们也把这个过程称为重建原始
数据。
小结：把降维后的数据重新升维。

2.7、主成分分析法的应用建议

错误的主要成分分析情况：一个常见错误使用主要成分分析的情况是，将其用于减少过拟合
（减少了特征的数量）。这样做非常不好，不如尝试正则化处理。原因在于主要成分分析只
是近似地丢弃掉一些特征，它并不考虑任何与结果变量有关的信息，因此可能会丢失非常重
要的特征。然而当我们进行正则化处理时，会考虑到结果变量，不会丢掉重要的数据。
另一个常见的错误是，默认地将主要成分分析作为学习过程中的一部分，这虽然很多时
候有效果，最好还是从所有原始特征开始，只在有必要的时候（算法运行太慢或者占用太多
内存）才考虑采用主要成分分析。
小结：PCA的使用情况分析。

3、第八周编程题

1、findClosestCentroids.m
for i=1:size(X,1)
for j=1:K
distance(j)=sum((centroids(j, : ) - X(i, : )) .^ 2, 2);%求距离
end
[t,idx(i)]=min(distance);%t为值，idx（i）为索引
end
2、computeCentroids.m
for i = 1 : K
centroids(i, : ) = (X’ * (idx == i )) / sum(idx == i);
%(idx ==i）将不是i值的X中对应数据变为0.
end
3、pca.m
Sigma=(X’*X)/m;
[U,S,V]=svd(Sigma);

4、projectData.m
Z = X * U(:, 1 : K);

5、recoverData.m
X_rec = Z * U(:, 1 : K)’;