无监督学习

与监督学习相对，无监督学习是从不带标签的数据中学习的一种技术。聚类 Clustering属于无监督学习中的一种。其主要思想是将没有标签的数据集根据各个样本之间的相似程度进行分类，如下图：

一、聚类问题

K-Means 算法

K-Means 算法为什么要叫 K-Means？

K-Means 算法属于聚类算法中的一种，能够自动地将数据分成若干个 cluster ，该算法的工作方式就是不断迭代。其工作过程分为两步，首先随机生成若干个聚类中心 cluster centroids ：

1. 数据集中的每个样本点都会找到与自己最近的那个聚类中心，然后会与该聚类中心划为一类。就好比是找老大，刚开始会随机生成几个老大，小喽啰们找到离自己最近的那个老大，加入它的帮派。

2. 在所有样本点都找到自己的老大后，聚类中心会计算所有在同一个cluster的样本点的平均位置，之后会将自己更新到这个平均位置。

重复迭代第一个步骤和第二个步骤，直到聚类中心的位置稳定下来不再改变为止。

K-Means 算法会接收两个输入：参数 K 和一个无标签的训练集 $\{x^{(0)},x^{(1)},\cdots,x^{(m)}\}${x(0),x(1),⋯,x(m)} 。这里 K 指的是希望将样本分成几类，如 K = 2，表示希望将所有样本分成 2 个 cluster 。训练集中的每个样本，如 $x^{(1)}$x(1) ，都是 n 维向量，即有 n 个特征。

下面的图是 K-Means 算法的原理：

对于上图解释如下：

首先 K-Means 算法会随机生成 K 个聚类中心，并分别表示为 $\mu_1, \mu_2,\cdots,\mu_k$μ1​,μ2​,⋯,μk​ 。对于 $\mu_k$μk​ 可以理解成一个坐标点，并且是个 n 维的坐标点。然后会进入一个迭代过程。迭代过程的第一步是遍历数据集中的每个样本点，$c^{(i)}$c(i) 的值等于离第 $i$i 个样本点最近的那一个聚类中心的数值，比如，若 $x^{(1)}$x(1) 离 $u_2$u2​ 最近，则 $c^{(1)}=2$c(1)=2 ，计算方法是计算 $x^{(1)}$x(1) 与各个聚类中心之间的距离，然后选择最小的那一个。

第二步，更新每个聚类中心的位置，即更新 $\mu_k$μk​ 的坐标，这个坐标的值为与该聚类中心在同一个 cluster 的所有样本点的平均位置。如，假设与 $\mu_2$μ2​ 在同一个 cluster 的点只有 $x^{(1)},x^{(2)},x^{(4)}$x(1),x(2),x(4)，则更新 $\mu_2$μ2​ 时， $\mu_2=\frac{1}{3}(x^{(1)}+x^{(2)}+x^{(4)})$μ2​=31​(x(1)+x(2)+x(4)) 。

除了可以将无标签的样本进行分类以外，K-Means 算法还可用于 non-separated clusters 的分类问题，即分离不佳的 cluster 的问题，如：

对于这类问题，K-Means 算法仍能对这些样本点进行分类。假如对于这个问题，我们需要将所有样本点分成 S，M，L （衣服的小号、中号和大号）这三类，K-Means 算法的一个分类效果如下：

随机初始化 K-Means 算法

之前提到使用 K-Means 算法时，会生成 K 个随机聚类中心，那么如何选择 K 这个数值的大小呢？对此，吴恩达给出的建议是，K 应当小于 m，即 K 要小于样本总数。在随机初始化 K 均值算法时，随机选择 K 个样本点作为聚类中心，但这样的方法存在一些问题，假如只初始化一次的话，很有可能陷入局部最优的情况，即如下图：

而我们真正希望得到的结果是，下图：

对于这个问题，解决方式就是，多次随机初始化，这个次数一般在 50 到 1000 之间。这个解决方式适用于聚类数目比较少的情况下，比如最终要分成 2 类、3 类等。具体步骤如下：

对上图解释如下：

首先随机初始化 K-Means 算法，即随机选择 K 个聚类中心，然后运行 K-Means 算法，得出一组 $c^{(1)},\cdots,c^{(m)},\mu_1,\cdots,\mu_K$c(1),⋯,c(m),μ1​,⋯,μK​，将其代入一个 cost function（或者称为畸变函数 distortion？）中得出一个数值。

重复上述步骤指定次，最终选择 cost function 计算结果最小的那一次。

K 值的选择

对于聚类数量 K 这个值的选择，并没有很好的自动化的方法，在大多数情况下，我们是用手动选择的方式或者按照过往经验来选择 K 这个值。当然也有一个有时会比较有效的方法——Elbow Method。

Elbow Method 的思想：在有些情况下，当我们增加 K 这个值的选取时，K 与 cost function 的关系会像下图左边那样，成一个“手肘”的形状，这时候选择肘部的那个 K 值会是一个比较好的选择。但是在很多情况下，这个方法并没有什么用，在大多数情况下，K 与 cost function 之前的关系如右图所示：

总归而言，K 值的选择得看具体问题的需要。

二、降维问题

dimensionality reduction

什么是降维？每个样本点有若干的特征，每个特征代表了一个维度，但有时候有些特征其实是冗余的，这些特征的相关度很高，举个比较夸张的例子，比如在一个关于预测房价的样本点中一个特征是以厘米为单位的宽度，另一个特征是以米为单位的宽度，显然这两个特征的相关度很高，是冗余的，这时候完全可以将这两个特征合并为一个特征。特征数减少了，维度自然减少，这就是降维。上面提到的是降维一个应用——数据压缩 compressing the data 。降维有几点好处，一是能够节省存储空间，二是能够让学习算法运行得更快。

比如上图这个例子中，特征 $x_1$x1​ 和 $x_2$x2​ 所代表的数据点基本上都在一条直线上，通过这一个发现就可以考虑进行降维，将平面上的点都转化到数轴上。

再比如上图这个例子，最左边图中的数据点基本上都在一个平面上，这时候就可以考虑将数据点都转化到平面上。

主成分分析 PCA

principal components analysis，目前降维问题中最常用的算法。

上图中就是PCA的工作过程。左图是从 2 维降到 1 维的例子，PCA 会试图找到一个合适的向量，这个向量通过计算数据点与向量所在直线的距离来进行选择，选择距离最小的那一个。图中为蓝色的向量，将黑叉数据点投影到蓝色向量 $u^{(1)}$u(1) 所在的直线上，这样子原来的数据点就变成了新的在直线上的数据点，从而实现降维。

右图 3 维到 2 维的例子，这里需要找到 2 个合适的向量，即图中红色的向量 $u^{(1)}$u(1) 和 $u^{(2)}$u(2) ，或者说找到一个平面，将三维空间中的数据点投影到这个平面上，于是三维空间中的数据点就都变成了平面上的数据点。

推广开来，从 n 维降到 k 维，则需要找到 k 个向量 $u^{(1)},u^{(2)},\cdots,u^{(k)}$u(1),u(2),⋯,u(k) 。

PCA 与线性回归是有区别的：

左图为线性回归，右图为 PCA 。