吴恩达机器学习(三):无监督学习

无监督学习

一、无监督学习

1.1 聚类

1.1.1 什么是聚类

聚类（Clustering）是无监督学习中的一种技术，旨在将数据集中的样本根据其特征相似度进行分类，使得同一组中的样本相似度较高，而不同组之间的样本相似度较低。
在监督学习中，我们使用的数据集中每个样本都包括输入特征x和标签y，但在无监督学习中我们使用的数据集样本只有特征x而没有标签y，我们想要算法做的是找到样本之间的一些相似处与不同之处，然后将其分类开来。

聚类目前有很多应用场景，包括客户细分、图像压缩、文档分类、生物信息学等等。

1.1.2 k-means算法

k-means算法是最经典的聚类算法之一，它旨在将数据集划分为k个簇，每个簇均由其均值（质心）表示。
我们用一个简单的例子来展示一下k-means算法的实现过程。
首先这是一个包含了30个无标记样本的数据集，每一个点都表示一个样本：

假如我们想把这些数据分为两组，那么k-means算法第一步要做的就是在图中随机选取两个点，作为两个簇的初始质心：

下一步k-means算法会开始移动质心，移动的过程具体如下：
首先k-means算法会计算每个样本点到两个质心的距离，然后将该点分配给离它最近的质心：

当所有点都被分配完之后，k-means算法会分别计算所有红色点与所有蓝色点的平均值，也就是所有红色点的质心和所有蓝色点的质心，计算完后将红蓝质心分别移动到计算得到的位置，成为新的质心：

得到新的质心后，再重复上面两步，当两个簇的质心位置不再变化时，就说明k-means算法已经收敛，数据集也就被我们分为了两个簇：

1.1.3 k-means算法的具体实现

k-means算法实现的具体过程是：

1. 随机初始化K个簇质心$\mu_1,\mu_2,...,mu_K$，其中K是我们想要最终得到的组数
2. 重复以下过程：
   1. 将样本点分配给离它最近的簇质心(Assign points to cluster centroids)
      for i = 1 to m
      c^(i) = index(from 1 to K) of cluster centroid closest to x^(i)
      其中m为数据集中样本个数，$c^{(i)}$表示离样本$x^{(i)}$最近的簇质心的编号，比如1号样本点$x^{(1)}$距离最近的簇质心为$\mu_2$，那么就说明将1号样本点分配给2号簇质心，表示为$c^{(1)}=2$。
   2. 移动簇质心(Move cluster centroids)
      for k = 1 to K
      mu_k = average(mean) of points assigned to cluster k
      计算k号簇中所有点的平均值，然后将该簇质心移动到该位置。
      比如1、5、6、10号样本分配给了1号簇，那么新的簇质心$\mu_1={1 \over 4}[x^{(1)}+x^{(5)}+x^{(6)}+x^{(10)}]$。
      需要注意的是这里的$x^{(i)}$不一定是一维的，$x^{(i)}$实际是一个向量，其维度取决于样本数据有多少个特征，如果有两个特征，那么$x^{(i)}$就是二维向量。
      我们之前看的几个例子都是样本点有明显分离的数据集，但事实上，k-means算法也适用于样本数据没有很好分离的数据集，比如右侧这种有关区分T恤型号的数据集：
      它包含两个特征：身高和体重，可以看到该数据集中的样本数据没有很明显的分离，但是如果我们想把其分为S\M\L三个型号，那么我们就可以初始化3个簇质心，通过运行k-means算法来将其分为三个部分，从而帮助我们更好的通过身高体重来选择合适的衣服大小：
      

1.1.4 优化目标

1.1.4.1 k-means成本函数

与监督学习中相同，在k-means算法中我们也在使用成本函数来优化算法。
k-means算法的成本函数是失真函数：

$$J(c^{(1)},...,c^{(m)},\mu_1,...,\mu_K)={1 \over m}{\displaystyle\sum_{i=1}^m}||x^{(i)}-\mu_c^{(i)}||^2$$

其中：$c^{(i)}$表示样本示例$x^{(i)}$被分配到的簇的编号，$\mu_k$表示编号为k的簇质心，$\mu_c^{(i)}$表示样本示例$x^{(i)}$被分配到的簇的质心位置。
比如样本示例$x^{(1)}$被分配到了2号簇，那么$c^{(1)}$=2,$x^{(1)}$所在的簇的质心位置$\mu_c^{(1)}=\mu_2$。
k-means算法所做的就是通过改变样本点的分配情况和簇质心的位置来最小化成本函数。

1.1.4.2 成本函数优化原理

结合我们之前说过的k-means算法的主要过程，我们可以说明成本函数实现算法优化的原理。

在第一步中，我们首先固定了簇质心的位置，然后最小化成本函数。根据成本函数的表达式我们可知，此时$\mu_c^{(i)}$是固定的，所以想要使成本函数最小，就需要使$||x^{(i)}-\mu_c^{(i)}||$尽可能小，也就是让样本点离簇质心最近，这样就实现了将样本点分配给离它最近的簇质心。
在第二步中，我们已经分配完了所有样本点，所以$x^{(i)}$已经固定了，要使成本函数最小，即使$||x^{(i)}-\mu_c^{(i)}||^2$最小，就是让簇质心离属于它这个簇的所有样本点最近，而求平均值就可以实现这一点。

k-means算法通过最小化成本函数$J$来不断迭代，$J$不断减小说明算法正在不断收敛，当成本函数$J$不再随着迭代更新而变化时就说明K-means算法已经收敛。

1.1.5 k-means初始化

k-means算法的第一步是随机选择K个点作为初始的簇质心，而初始化位置也会影响k-means的收敛速度以及最终得到的效果。如果位置选择不当可能会导致最终有些簇内分配不到样本点。所以簇质心初始位置的选择也很重要。
一般情况下，对于有m个样本示例的数据集，我们一般会选择K个示例点作为这K个簇的初始化质心。

在初始化过后我们会运行k-means算法，由于初始化位置不同，所以最后也会得到不同的结果：

虽然这三种情况都是通过最小化成本函数得到的，但是$J_1$要明显优于$J_2$和$J_3$。所以一般情况下我们都会多次随机初始化，然后通过k-means算法得到不同的结果，再从所有结果中选取使得成本函数$J$最小的一种情况。

1.1.6 选择聚类数量

簇的个数k作为k-means算法的一个输入也十分重要。对于同一个数据集，我们可能会有多种k值的选择。比如在下图中，我们可以认为它主要有2个簇，也可以认为它有4个簇，甚至可以认为它有3个簇。

所以k值的选择一般是模棱两可的。
人们常用于选择k值的一种方法是elbow方法，这种方法首先需要构造出不同的k值最后得到的成本函数$J$是多大，然后画出$J$关于K值的图像，我们一般会选择弯曲处作为我们最终选择的k值。

但是在实际中，$J-k$曲线一般是平滑的，很难找出我们想要的弯曲部分，所以我们更为常用的一种方法就是根据实际情况的需要来选择k值。我们一般会选择不同的k值然后运行k-means算法，通过评估模型最终的表现来判断k值是否合适。

比如对于选择T恤的尺寸，我们可以设置3个尺寸：S\M\L，也可以选择设置为5个尺寸：XS\S\M\L\XL。虽然5个尺寸看起来更精细化一些，但是在实际应用时，5个尺寸就会有各种额外的费用，所以最终k值的选择还需要考虑多方面因素的影响。

1.2 异常检测

1.2.1 什么是异常检测

异常检测（Anomaly Detection）也是无监督学习的一种算法，它是一种识别数据中不符合预期模式或统计分布的样本的技术。这些异常样本通常表示潜在的异常事件、错误或罕见的现象。
我们举一个简单的异常检测案例：比如对于飞机发动机的检测包含很多特征，简单起见我们只取两个特征：$x_1$表示发动机产生的热量，$x_2$表示发动机的振动强度。我们的数据集为$x^{(1)},x^{(2)},...x^{(m)}$，现在我们有一个新的发动机$x_{test}$，我们需要判断新的发动机是否正常。
我们首先可以画出数据集在$x_1-x_2$上的位置，然后将新的示例也画在图中，如果该测试示例在非常密集的区域，我们就可以判断这个新的发动机应该没有问题，但是如果测试实例位于非常偏僻的位置，那我们就会认为它很有可能有故障。这就是异常检测算法的工作原理。

异常检测算法通常使用密度估计技术来实现。当我们拿到一个数据集时，我们首先需要根据这个数据集创建一个模型$Model\ p(x)$，这个模型就是为了判断每个数据出现的可能性的高低。当我们输入一个测试集示例$x_{test}$时，我们可以通过该模型得到$x_{test}$出现的概率$p(x_{test})$，如果$p(x_{test})$小于某个值$\epsilon$时，我们就认为$x_{test}$异常，反之则没有异常发生。

1.2.2 高斯分布

为了构建异常检测模型，我们需要使用到高斯分布，也叫做正态分布。高斯分布是一条根据事件$x$发生概率$p(x)$所得到的曲线。

其中$\mu$是数据集的期望值，$\sigma$是数据集的标准差。它们的计算表达式如下：

$$\begin{align*} \mu = {1 \over m}\displaystyle\sum_{i=1}^mx^{(i)} \\ \sigma^2 = {1 \over m}\displaystyle\sum_{i=1}^m(x^{(i)}-\mu)^2 \end{align*}$$

曲线的表达式为：

$$p(x)={1 \over \sqrt{2\pi}\sigma}e^{-(x-\mu)^2 \over 2\sigma^2}$$

期望值$\mu$决定了曲线的位置，标准差$\sigma$决定了曲线的幅度。$\sigma$越大，曲线越宽，$\sigma$越小，曲线越窄。

1.2.3 构建异常检测算法

1.2.3.1 多特征值密度估计

我们已经知道了高斯分布是如何对只有一个特征的数据集起作用的，现在我们来看如何构建多特征值的异常检测算法。
密度估计最重要的就是计算出样本$x^{(i)}$出现的概率。假设我们现在有一个训练集：$x^{(1)},x^{(2)},...,x^{(m)}$，其中每个样本$x^{(i)}$都包含n个特征。我们知道对于n个互不干扰的事件，计算它们同时出现的概率时就是将它们每一个出现的概率相乘，事实证明，即使这n个特征之间有一些联系，这种计算方法仍然有用。所以概率计算公式为：

$$\begin{align*} p(x) &= p(x_1;\mu_1,\sigma_1^2) * p(x_2;\mu_2,\sigma_2^2) * p(x_3;\mu_3,\sigma_3^2) * ... * p(x_n;\mu_n,\sigma_n^2) \\ &= \displaystyle\prod_{j=1}^np(x_j;\mu_j,\sigma_j^2) \end{align*}$$

比如在之前的飞机发动机检测案例中，假如发动机产生高热量的概率$p(x_1=high\ temp)=1/10$，发动机产生高振动强度的概率$p(x_2=high vibra)=1/20$，那么发动机出现异常情况的概率就是$p(x_1,x_2)=p(x_1)*p(x_2)={1 \over 10}*{1 \over 20}={1 \over 200}$

1.2.3.2 构建异常检测算法

构建异常检测算法一般分3步：

1. 选择n个你认为对异常检测有用的特征值$x_i$
2. 计算参数$\mu_1,...,\mu_n,\sigma_1^2,...,\sigma_n^2$
   其中：

   $$\begin{align*} \mu_j = {1 \over m}{\displaystyle\sum_{i=1}^m}x_j^{(i)} \\ \sigma_j^2 = {1 \over m}{\displaystyle\sum_{i=1}^m(x_j^{(i)}-\mu_j)^2} \end{align*}$$

3. 使用新的示例$x$，计算其出现的概率$p(x)$：

   $$p(x)=\displaystyle\prod_{j=1}^np(x_j;\mu_j,\sigma_j^2)=\displaystyle\prod_{j=1}^n{1 \over \sqrt{2\pi}\sigma_j}e^{-(x_j-\mu_j)^2 \over 2\sigma_j^2}$$

   如果结果$p(x)<\epsilon$，那么就判定为异常。