吴恩达《机器学习》课程学习笔记(十)—— K-Means聚类算法与PCA主成分分析

吴恩达《机器学习》课程学习笔记(十)—— K-Means聚类算法与PCA主成分分析

一、无监督学习简介(Unsupervised Learning: Introduction)

无监督学习与监督式学习相反,它的训练集数据并没有进行标记。也就是说,我们没有用来划分结果的y轴,只有一些可以尝试寻找其特征的数据集。

聚类算法可以用于:

  • 市场划分
  • 社会关系网络分析
  • 计算机集群聚类
  • 天文数据聚类

 

二、K-Means算法

1.算法概述

K-Means算法是时下最流行且应用广泛的自动聚类算法。它的实现流程基本如下:

  1. 随机设置两个初始点,称作聚类中心(cluster centroids)
  2. 聚类分配:将每一个样本归入到离它最近的聚类中心所属的分类中。
  3. 移动中心:对于每一个聚类中心,计算它集合中所有的样本点的平均值,然后将该聚类中心移动到平均值的位置。
  4. 重复(2)和(3)直到实现聚类。

在K-Means算法中,我们的主要变量有:

  • K(聚类的数量)
  • 训练集 x^​\( x^{(1)}, x^{(2)},…, x^{(m)} \)(1),x(2),,x(m)
  • 其中每个样本的维度​\( x^{(i)} \in \mathbb{R}^n \)

要注意的是,这里并没有使用\( x^{(0)}=1 \)

算法伪代码如下:

其中的第一层循环是聚类分配。我们使用了向量c,其中​\( c^{(i)} \)​代表的是第i个样本\( x^{(i)} \)所属的聚类中心的索引(这里就是并查集的使用)。

我们可以用更加数学化的方法表示\( c^{(i)} \)

\[ c^{(i)} = argmin_k\ ||x^{(i)} – \mu_k||^2 \]

方便起见,我们将等号右边进行了平方处理,这使得我们尝试最小化的那个函数上升得更快。由于欧氏距离需要开平方根,所以进行平方处理有助于减少计算负担。

没有平方:

\[ ||x^{(i)} – \mu_k|| = ||\quad\sqrt{(x_1^i – \mu_{1(k)})^2 + (x_2^i – \mu_{2(k)})^2 + (x_3^i – \mu_{3(k)})^2 + …}\quad|| \]

进行了平方:

\[ ||x^{(i)} – \mu_k||^2 = ||\quad(x_1^i – \mu_{1(k)})^2 + (x_2^i – \mu_{2(k)})^2 + (x_3^i – \mu_{3(k)})^2 + …\quad|| \space\space\space\space\space\space(2.1) \]

由此可见,进行平方有两个好处:使最小化速度更快,以及使计算量更少。

其中的第二层循环是“移动聚类中心”,按照每一个数据簇的平均值来移动其聚类中心。

我们将其公式化地表示如下:

\[ \mu_k = \dfrac{1}{n}[x^{(k_1)} + x^{(k_2)} + \dots + x^{(k_n)}] \in \mathbb{R}^n \space\space\space\space\space\space(2.2) \]

其中每一个​\( x^{(k_1)}, x^{(k_2)}, \dots, x^{(k_n)} \)​是训练集中属于​\( \mu_k \)​所在数据簇的那些样本。

如果你发现存在某个聚类中心所属的数据簇没有样本,那么你可以随机地重新初始化该聚类中心到一个新的点。你也可以直接把这个数据簇删除

在多次迭代之后,算法将会汇集(converge),此时再进行新的迭代也不会再改变数据簇的划分。

还有一个特殊的情况,这种情况下数据集内的样本之间并没有真正分开。K-means算法在这种情况下仍能把数据集划成K类。

2.优化目标(Optimization Objective)

回顾一下我们在算法中使用的参数:

  • \( c^{(i)}= \)​样本​\( x^{(i)} \)​最近所属的数据簇编号(1,2,…,K)
  • \( \mu_k= \)​聚类中心k(μk∈ℝn)
  • \( \mu_{c^{(i)}}= \)​样本\( x^{(i)} \)所属的聚类中心

使用上面这些变量,我们可以得到代价函数如下:

\[ J(c^{(i)},\dots,c^{(m)},\mu_1,\dots,\mu_K) = \dfrac{1}{m}\sum_{i=1}^m ||x^{(i)} – \mu_{c^{(i)}}||^2 \space\space\space\space\space\space(2.3) \]

我们的优化目标就是使用代价函数来最小化我们的参数:

\[ min_{c,\mu}\ J(c,\mu) \]

也就是说,对于每一个样本,我们要找到其所属的数据簇c,以及聚类中心μ的坐标,以此实现最小化所有训练样本到对应聚类中心的平均距离之和。

上面的代价函数通常被称作训练样本的畸变(distortion)。

 

聚类分配这一步中,我们的目标是:

改变​\( c^{(1)},\dots,c^{(m)} \)​来最小化代价函数J(…)。(保持​\( \mu_1,\dots,\mu_K \)​固定)

移动聚类中心这一步中,我们的目标是:

改变​\( \mu_1,\dots,\mu_K \)​来最小化代价函数J(…)

在使用K-means算法的情况下,不可能会出现代价函数上升的情况。它总是下降的。

 

3.随机初始化(Random Initialization)

上一节我们说的是随机选出聚类中心,那么到底怎么随机比较合适呢?这里有一些关于随机初始化的建议:

  1. 一般K < m. 也就是聚类的数量一般要小于训练样本的数量(否则很奇怪)。
  2. 随机地选取K个训练样本。(上一节没提到,但是一般推荐使用这个方式)
  3. 让​\( \mu_1,\dots,\mu_K \)​这些聚类中心等于这K个训练样本。

K-means算法有可能被困在局部最优解中。为了尽可能避免这些事情发生,你需要用不同的随机初始化多运行几次算法。一般建议K<10.

 

4.选取数据簇的数量(Choosing the Number of Clusters)

如何选择数据簇的数量K非常的主观和模糊。

手肘方法:画出代价函数J随着数据簇数量K而变化的图像。代价函数会随着数据簇数量上升而减少,最后会趋于平稳。如果在某一个点开始明显地趋于平稳,那么我们选择代价函数刚开始变平稳的那个点K;但如果代价函数是平滑地趋于平稳的话,那这个方法就失效了。

有时候,我们的聚类是为下游处理决策服务的,这时候就可以根据实际权衡来设定K。比如说你可以把衣服尺寸分为S\M\L三类出售,由于尺寸较少,所以成本便宜,但是顾客穿起来不一定合身。你也可以选择把衣服尺寸分为XS\S\M\L\XL五类,此时尺寸较多,成本较高,但是顾客的满意度可能会变高。这样就根据你的权衡来选择分三类还是五类了。

 

三、降维处理(Dimensionality Reduction)

1.动机-数据压缩(Data Compression)

  • 由于可能存在许多冗余特征量,所以需要减少特征量的数量。(比如同时有英寸和米的数据)
  • 为了实现这个目的,我们找出两种高度相关的特征量,将它们画出来,然后尝试画一条线,用新的特征量准确描述那两个特征量。我们将所有新的特征量都在那条线上表述出来。

同样,对于三维特征量降为二维特征量也一样:

进行数据降维后,剔除了冗余,就减少了需要处理的特征量。这样就实现了加快算法学习的速度。

2.动机-数据可视化(Visualization)

进行数据降维处理,我们可以容易地实现高维数据可视化——将其降为三维甚至二维。这种情况下我们需要找到新的特征量​\( z_1,z_2(and \space perhaps\space z_3) \)​来概括其他特征量。

例如:有一百多种关于国家经济的特征量,我们也许可以把它们概括为新的特征量“经济活跃度”

3.主成分分析概述(Principal Component Analysis)

最流行的降维算法是主成分分析(PCA)

给定两个特征量​\( x_1 \)​和​\( x_2 \)​,我们想要用一条直线来一次性表述两个特征量。这样我们需要把原来的特征量映射到新的直线上得到一个新的特征量。

对于三个特征量来说,我们也可以进行同样的操作,把它们映射到一个平面上。

PCA的目标是降低每一个特征量到投影直线的距离,也就是降低投影误差

 

从二维降到一维:找到一个方向(一个向量​\( u^{(1)} \in \mathbb{R}^n \)​)能够使得投影误差最小。

推广一下,从n维降到k维:找到k个向量​\( u^{(1)}, u^{(2)}, \dots, u^{(k)} \)​能够使得投影误差最小。

如果我们想从三维降到二维,那么我们需要将数据投影到两个方向上,所以k是2.

4.PCA不是线性回归(PCA is not linear regression)

  • 在线性回归问题中,我们最小化的是每一点到投影直线的平方误差,这是垂直距离。
  • 在PCA中,我们最小化的是最短距离,或者说最短的正交距离。

或者说,在线性回归问题中,我们用训练样本x来训练参数θ来预测y。

在PCA中,我们使用一系列的特征量​\( x_1, x_2, \dots, x_n \)​来找出一个最接近的通用数据集。我们并不尝试预测任何结果,也不会对特征量设置任何权重θ。

5.数据预处理(Data preprocessing)

  • 给定一个训练集x(1),x(2),…,x(m)
  • 预处理(特征缩放、均值归零):

    \[ \mu_j = \dfrac{1}{m}\sum^m_{i=1}x_j^{(i)} \]

  • 用​\( x_j^{(i)} – \mu_j \)​来替代​\( x_j^{(i)} \)
  • 如果不同的特征量是不同量度的(例如x1是房屋尺寸,x2是卧室数量),那么将其化为具有可比较范围的值

总的来说,我们先从每一个特征量数据中减去该特征量的平均值。然后实现特征量的标准化​\( x_j^{(i)} = \dfrac{x_j^{(i)} – \mu_j}{s_j} \)

我们可以定义从二维到一维意味着什么:

\[ \Sigma = \dfrac{1}{m}\sum^m_{i=1}(x^{(i)})(x^{(i)})^T \]

它在Octave中可以向量化为:

我们使用大写的Sigma来代表协方差矩阵。

注意到​\( x^{(i)} \)​是一个n x 1的向量,​\( (x^{(i)})^T \)​是一个1 x n的向量,X是一个m x n矩阵。它们的积是一个n x n的矩阵,正是Σ的维度。

同样我们还需要计算协方差矩阵的特征值。

svd()是“奇异值分解”,是Octave的一个内置函数。

我们想要得到的是svd()里的U矩阵,代表的是Sigma协方差矩阵:​\( U \in \mathbb{R}^{n \times n} \)​。U包含了​\( u^{(1)},\dots,u^{(n)} \)​,这正是我们想要的。

 

获取矩阵U的前k列并计算z

我们需要将U矩阵的前k列记为Ureduce。这是一个n x k的矩阵,然后我们计算z:

\[ z^{(i)} = Ureduce^T \cdot x^{(i)} \]

\( UreduceZ^T \)​的维度是k x n,x(i)的维度是n x 1.

\( Ureduce^T \cdot x^{(i)} \)​的积维度为k x 1.

总结一下,整个算法在octave中的实现如下:

6.用压缩数据进行重建(Reconstruction from Compressed Representation)

如果我们使用PCA来压缩数据,那么我们该如何解压数据,或者说得到原始数据呢?

从一维到二维,我们做了变换:​\( z \in \mathbb{R} \rightarrow x \in \mathbb{R}^2 \)

我们也能用上面的等式反推回来:​\( x_{approx}^{(1)} = U_{reduce} \cdot z^{(1)} \)

这里要注意的是,我们仅仅能够得到原始数据的近似值

注意:事实证明,U矩阵是酉矩阵。酉矩阵的一个特殊性质是:

\( U^{-1} = U^∗ \)​,其中*表示的是共轭转置。

由于我们处理的是实数,所以可以表示成:\( U^{-1} = U^T \)

7.选择主成分的数量(Choosing the Number of Principal Components)

我们如何选择k,也就是主成分的数量呢?回顾一下k是我们想要降到的维数。

一个选择k的方法是使用下面的等式:

  • 给定一个平均投影平方差:​\( \dfrac{1}{m}\sum^m_{i=1}||x^{(i)} – x_{approx}^{(i)}||^2 \)
  • 也给定数据的总方差:​\( \dfrac{1}{m}\sum^m_{i=1}||x^{(i)}||^2 \)
  • 选择最小的k使得:​\( \dfrac{\dfrac{1}{m}\sum^m_{i=1}||x^{(i)} – x_{approx}^{(i)}||^2}{\dfrac{1}{m}\sum^m_{i=1}||x^{(i)}||^2} \leq 0.01 \)

这样投影平方误差被总方差所除的结果比百分之一小,也就是说99%的方差都被保留了。(注:这个表述方法有点摸不着头脑,我的理解是,其投影误差对于总方差来说很小,所以其影响程度可以接受)

 

选取k的算法:

  1. 用k=1,2,..来尝试运行PCA
  2. 计算​\( U_{reduce}, z, x \)
  3. 检验上面公式的结果,如果并没有保留下99%的方差,就增加k再算一次

这个过程实际上是非常低效的,所以我们采用向量化的方法,同时计算出所有k的投影平方误差,然后查表得到结果。在Octave中可以表示为:

对于给定矩阵S,我们使用下面的方法检验:

\[ \dfrac{\sum_{i=1}^kS_{ii}}{\sum_{i=1}^nS_{ii}} \geq 0.99 \]

8.使用PCA时的一些建议(Advice for Applying PCA)

使用PCA的最常见目的是加快监督学习的速度。

对于具有大量特征量(例如​\( x^{(1)},\dots,x^{(m)} \in \mathbb{R}^{10000} \)​)的训练集,我们使用PCA来减少训练集的特征量数量(例如​\( z^{(1)},\dots,z^{(m)} \in \mathbb{R}^{1000} \)​)

应用:

压缩:

  • 减少数据占用空间
  • 加快算法速度

数据可视化:

  • 选择k=2或k=3

PCA的不良使用目的:

  • 试图用它来避免过拟合。我们可能认为,使用PCA减少了特征量的数量可以有效避免过拟合。这可能有用,但是并不推荐。因为这种做法没有考虑到我们的结果y(可能会导致遗漏与y相关的某些特征)。使用正则化才是更好的做法。

不要一开始就认为需要PCA:你应该先尝试使用原始数据来训练学习模型,然后视情况决定是否需要PCA。

 

四、第七次编程作业

本节内容的重点是代码阅读,任务量比较少。

传送门:https://github.com/YongyiZhou/Andrew-Ng/tree/master/ex7

 



Leave a Reply

Your email address will not be published.

*
*
*

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert