吴恩达机器学习Coursera-week8

Clustering

K-Means算法

从本周开始，我们开始学习无监督学习算法，而clustering分类算法是其中重要的一类算法，而clustering算法中K-Means算法是其中的佼佼者。
在讲K-Means算法时，Andrew首先用一段动画来阐释K-Means算法的分类过程，看完之后已经可以对K-Means如何分类有一个大致的了解，建议看视频。总体来说，首先我们需要有如下输入input:

• select K(即选择要分成几个类）

• sample set(只包含feature x, 而不包含label y）
  然后通过如下训练过程进行训练：

  
  1.1-training steps
• 首先，我们随机初始化cluster centroids(实际就是选择中心点），后续我们会看到不同的选择中心点方式。
• 重复两个步骤，直到J到达min极值。这两个步骤分别是cluster assignment step和move centroid step。关于J参考下一节。
• cluster assignment step是将样本进行分组，依据的是离哪个centroid更近，将该centroid对应的index赋给c⁽ⁱ⁾
• move centroid step是计算每一组的样本的平均值，然后将centroid移动到该平均值所在的点，可以理解为移动到这组样本的中心点。

optimization objective

所有的机器学习算法都会有优化目标，一般就是寻求cost function的极小值，K-Means也有优化目标，如下图：

2.1-K-Means optimization objective

• 可以理解为所有样本到其对应的centoid(中心点)的平均距离，这个平均距离越小，那么说明优化的效果越好。

• 这个cost function有时也叫distortion function
  K-Means的优化过程就是在寻求这个cost function最小值的过程，如下：

  
  2.2-optimization procedure
• assignment step实际就是针对变量c⁽ⁱ⁾ (i从1到m)寻求J的min值
• move centroid step实际就是针对u_k(k从1到K)寻求J的min值
  至此，针对K-Means算法我们已经有了大体的了解，不过目前还遗留两个问题：

1. 如何选择初始的centroid？之前是随机选，那么有没有更好的方法？
2. 如何选择K值，即到底分几个类？
   那么后续的两节主要是解决这两个问题。

Random Initialization

我们之前是通过随机选的centroid点，而通常在实践中，我们是随机从样本集中选择K个centroid点，如下图所示：

3.1-random initialization

这种随机选点有可能会导致J只能获得局部最优解，而无法获得全局最优解，如下图所示：

3.2-local optima
图3.2中下方的两个图展示就是局部最优解，我们看到这个分类并不是非常好。而要解决此类问题，通常的做法就是多次随机选取，这样最终会产生多个J，然后再看哪个J最小，如下图所示：
3.3-get global optima

通常针对K=2~10的情况我们需要进行多次随机选取centroid，再计算其最终的J，然后再看哪个J最小；而对于K>10的情况，通常不需要这么做。

Choose K

选取合适的K值，即到底要分几个类也是我们需要考虑的问题，通常我们有两种方式：

• 一种是所谓的"elbow" 方法
• 另一种是根据我们实际项目中的需求

elbow方法如下图所示，找到K值导致的关键拐点

4.1-elbow method

而很多时候没有此类拐点，如上图右方的图，那么这种情况下，就需要根据我们实际项目的需求，如Andrew举了T-shirt分类的例子，如下图：

4.2-choose K according to purpose

Motivation

这里说的Motivation我理解是说为什么要做feature reduction，这里主要有两个原因：

• 可以压缩数据，加快机器学习的训练
• 可以将机器学习模型视觉化，从而让我们更好地理解模型

Motivation I

此小节主要讲了两个例子，一个是从2D(Dimension)到1D；另一个是从3D到2D的例子

5.1-2D to 1D

实际上就是平面上的点映射到一条直线上，从而可以用一个数来标识这个样本，而不需要两个数来标识，下面的例子是从3D映射到2D，道理一样。

5.2-3D to 2D

Motivation II

第二个我们要做feature reduction的动机是通过这种方式，我们可以使用图形化的方式来展示我们的数据和模型，作者举了一个国家相关的统计数据模型，当我们将50D的数据映射到2D的平面图上的时候，我们发现其实国家的各项数据实际跟两个数据是紧密相关的，一个是人均GDP，另外一个就是总GDP。所以，这就帮助我们更好的理解数据和模型。示例如下图：

5.3-country 2D data

Principal Component Analysis

此章主要讲PCA(Principal Component Analysis)

Principal Component Analysis Problem Formulation

此小节主要定义了什么是PCA问题，PCA问题实际上就是要找到一个direction，在这个方向上所有的样本点都会投射上去，并且这个投射的平均距离最终是最小的。如下图所示，红色的直线就是我们希望要的方向，而紫色方向的线就要差很多。

6.1-PCA problem formulation

PCA更一般的定义如下：

6.2-PCA Problem General Definition
上图给PCA一个更一般化的定义。

• 首先我们要找的这个vector跟样本的维数是一样的，即∈Rⁿ
• 我们要降到几维就使用几个vector，比如我们要降到2维，那么我们就需要2个vector来构筑一个映射平面。

需要注意的是，PCA并不是Linear Regression，如下图所示，Linear Regression是求解平行于y轴的最小距离（要跟y最接近），而PCA是说跟那条线的垂直距离。两者的目标是不一样的，而且在Linear Regression当中我们总是会有y值，但是在PCA中不需要考虑y值，只需要看x。

6.3-PCA is not linear regression

PCA Algorithm

在做PCA计算之前，首先需要做feature scaling/mean normalization，关于此方面知识参考
吴恩达机器学习Coursera-week2

之后，我们需要计算协方差矩阵(Covariance Matrix)，再通过协方差矩阵和SVD(Sigular Value Decompositon奇异值分解)算法计算出U，再通过U的前k个vector来计算z，如下图所示：

6.4-PCA summary
通过U_reduce计算z的过程如下：
6.5-get z

Applying PCA

Reconstruction from compressed representation

当我们需要将压缩后低维度的数据恢复到高维度的数据时，这就是reconstruction。计算过程如下：

7.1-reconstruction

• 核心公式就是使用U_reduce * z
• 需要注意的是使用PCA是有损压缩，因此reconstruction之后的数据只是近似值即x_approx，从右边的坐标图可以看出，其从一维恢复到二维平面图后，跟原先的x并不等同

Choosing number K

了解了PCA之后，我们就会有一个疑问，那么我们该如何选择维数k呢？是不是越小越好呢？但是PCA是有损压缩，那么这种情况下会不会导致与原始数据差异过大呢？

首先，我们需要有一个衡量的标准，如下图所示：

7.2-measure the difference between x and x(approx)

• 公式中分子是衡量x和x_approx的平均距离，也就是差异大小
• 公式中分母是衡量x与原点的平均距离，通过这两个距离的比例来衡量是否有多数的variance被保留，可以理解为主要的特点被保留。（想象描述一个人的长相的时候，我们用主要的特征描述来描述这个人的长相）

那么如何根据这个值来选择k呢？最直接的想法就是选择不同的k，然后按照这个公式计算出一个值，看其是否符合我们的要求(e.g. <0.01)。但是这种方式非常繁琐，我们有更好的方法来计算，如下图所示：

7.3-choosing k

• 上图中的右边部分就是使用svd分解后的S矩阵进行计算，从而可以更加简单直接的计算出是否保留了大多数variance
• 最后我们选择符合要求的最小的k

Advice for applying PCA

首先，作者介绍了实际应用PCA的总体过程，如下图所示：

7.4-applying PCA procedure

接下来，作者介绍了集中不当的使用PCA的方式：

7.5-bad use, to prevent overfit

另外，如果不需要使用PCA就不用PCA，除非有非常强的理由或者说不得不使用PCA的时候才使用，而不是任何时候都使用PCA。