主成分分析

打开本页,如果不能显示公式,请刷新页面。

基本概念

主成分分析(Principal Components Analysis, PCA)是一种统计分析、简化数据集的方法。它利用正交变换来对一系列可能相关的变量的观测值进行线性变换,从而投影为一系列线性无关的变量的值,这些不相关变量称为主成分(Principal Components)

主成分分析经常用于减少数据集的维数(降维),同时保留数据集中对方差贡献最大的特征。

主成分分析有卡尔·皮尔逊(Karl Pearson) 于1901年提出,后经哈罗德·霍特林(Harold Hotelling) 独立发展并命名。

在信号处理中,主成分分析也称为离散K-L转换(Discrete Karhunen-Loeve Transform,KLT)。

降维

实现数据集降维的方法有多种,它们分别依赖不同的统计量:

  • 主成分分析(Principal Component Analysis,PCA)(线性降维):方差
  • 多维标度(Multidimensional Scaling,MDS)(非线性降维):距离
  • ISOMap(非线性降维):测地距离
  • 局部线性嵌入(Local Linear Embedding,LLE):local geometry
  • 拉普拉斯映射(Laplacian Eigenmaps)(非线性降维):基于图
  • 线性判别分析(Linear Discriminant Analysis,LDA):类间的距离(有监督)

简而言之,降维的目的就是找到能够代表原始数据的维,且此时的维数要小于原始数据的维数。

如下图所示,分布在二维空间中的点表示一个数据集,此数据集有两个特征 ,通过观察发现,如果将二维数据点投影到特征 方向上,则投影后的数据最大限度地接近于原二维空间的数据,或者说 可以作为从二维空间降到一维空间后的一维空间的基。

图 1

很显然,在二维空间中,特征 的样本方差更大。换言之,找到了最大方差的样本,忽略较小方差的样本,能最小化信息丢失(关于信息的度量,请参阅参考资料【4】第7章有关内容)。

若二维空间的数据是下图分布样式,那么就不能降维到 或者 ,而是要找到其他的基,依据上述所发现的基本原理:找到方差最大的样本分布方向,可已经 作为降维后的空间的基。

图 2

PCA 数学原理

假设样本数量为 ,维数为 的数据集 。每一行表示一个数据点,其中第 行即为第 个数据点,用向量 表示,此向量共有 个维度(亦即 个特征),则

如果想要用一个向量 代表整个数据集 ,可以使用最小二乘法来找这个向量(即最小均方误差)。

注意,上式中以 为分母,请参阅参考资料 [4] 的 6.1.2 节“统计量”有关介绍。

上式其实是要寻找一个中心向量,该中心向量能够使得上式有最小的均方误差。根据参考资料 [4] 的 6.1.2 节内容可以猜测,该中心向量应该是所有数据点的样本平均,即:

下面证明上述猜测:

上式运算中的 是样本均值,由于 ,所以 ,即上式最后一项等于 0 。

又因为 ,所以:

时,取等号式。这样就得到Lee代表数据集的中心向量,即样本平均 ,注意,此处的样本平均是刻画所有数据点的向量 的集中量。

表示一个样本的数据点 与样本均值 的差 ,称为该数据点的偏差(deviation)。

在样本空间中,假设有一条直线(记作:L)过样本均值 ,如下图所示。那么直线 L 上的任意一点(可能是一个样本点,也可能不是) 的关系是: ,其中 是沿着直线 L 的向量。若设 ,其中 是与向量 同方向,且 ,通常称之为指向向量 是一个标量,表示数据点 与样本均值 之间的距离(如下图所示)。

图 3

于是直线 L 上的任意一个数据点可以表示为:

假设样本空间中的数据点 ,如果要在直线 L 上找一个非常接近于它的数据点(记作: ),由参考资料【4】第3章3.4.4节“投影”内容可知, 应该是 在直线 L 上的他投影。

为了对上述推论有深刻理解,下面根据参考资料【4】的3.4.4节和参考资料【6】的有关内容,对上述结论给予证明。

假设 给定,即直线 L 的方向是确定的。

数据点 的偏差为: ,如下图所示,它与 越接近,则 也越接近,即通过调解 ,使得

图 4

根据前述的经验,最佳近似的系数 可以通过最小二乘求得:

又因为 ,所以上式为:

为了计算上式的极值,需要计算偏导数 ,并令其为 0 :

解得:

的点积,即数据点相对样本均值的偏差 在直线 L 上的投影大小,此投影的向量为 。此时所得到的 最接近数据点 。也就是说,如果要将数据点 降维到一维空间的直线 L 上,通过 向直线 L 的正交投影得到对应的数据点

以上考虑的是在直线 L 确定的情况下,数据点通过向其上投影,得到了最近似的在直线 L 上的数据点。下面再研究如何确定直线 L 的方向,即指向向量 的方向。所使用方法还是通过 最小化,由前述计算所得到的 ,将已经得到的 代入到该式中:

根据点积运算的交换律,有 ,即 ,并将此结论应用于上述推导中。

令:

有参考资料【4】第5章5.5.4节“协方差矩阵”可知,上述为样本数据的协方差矩阵。

注意,在下面的计算中,将上面表示的数据集 做适当变化,主要是为了适应向量的表示,将每个数据点向量用列向量的形式表示:

样本均值 也用列向量的形式表示:

其中 是维数, 是样本数。

用矩阵运算,将 用上述向量具体表示,目的是观察每个元素的特点。

其中:

显然,矩阵 $\pmb{S}'$ 的第 行第 列元素 为:

其中 分别为样本的两个特征(或属性、变量)。

所以,矩阵 元表示第 个特征(或第 个属性、变量)与第 个特征的样本协方差:

其中 是第 个数据点的第 个特征,即 的第 个值, 是第 个特征的样本数据的平均值,即 的第 个值。

显然 ,故矩阵 是一个 的对称矩阵( 是数据集的维数)。

矩阵 称为样本协方差矩阵

如果用熟悉的方差和协方差符号表示,则为:

其中 是数据集中每个特征的数值。

所以,样本协方差矩阵 的对角线是由样本数据集每个特征的样本方差构成;其他元素是由两两特征间的样本协方差构成,且有

假设 是一个 维向量,则有:

由此可知,协方差矩阵 是半正定矩阵。

再来观察前述得到的

在上式中, 是数据集的样本方差(详见参考资料【4】第6章),它是一个常数。

于是,实现 的最小化,转化为了 的最大化,即转变为如下的最优化问题:

解法:拉格朗日乘数法

根据拉格朗日乘数法,定义拉格朗日函数:

其中 是未定的拉格朗日乘数。计算上式的梯度并设为 0 (求导公式,请参阅参考文献【4】的第4章4.2.4节“矩阵导数”):

可得:

由此可知,直线 L 的指向向量 样本协方差矩阵 的特征向量。

由参考资料【8】中正定矩阵的性质2可知,对于半正定矩阵 有非负的特征值,故可设其特征值为

至此,可以得到如下结论

选择对打特征值 所对应的特征向量作为 ,从而确定了直线 L 的方向,并通过 在此直线上的正交投影 得到代表该数据集的一维数据,即降维到只有一个维度。

举例

以图1所示的数据为例,假设由该数据,得到了协方差矩阵 ,利用参考资料【4】第3章3.1.1节介绍的用程序计算特征值和特征向量的方法,可得:

按照前述结论,可以将 方向可以作为降维数据的主方向,它非常接近于图1中的 方向。

对于图2,其数据的协方差矩阵可假设为 ,计算得到特征值和特征向量:

特征向量 方向即为图2所示的 方向。

以上是将数据集降维到一维空间,这种降维后所得到的的数据相对原数据集而言,略显“粗糙”,如果要求更高精度的近似,可以将 维数据集降维到 维度,其中 ,此时考虑 中的数据点:

其中

目标是要寻找一组单位正交集 ,即 ,此处的 称为克罗内克函数(Kronecker Delta)。为此,还是通过最小化均方误差实现:

根据前面的推导过程可知,系数 是数据点的偏差 向单位向量 的正交投影量,即 。类似于之前的推导,可得:

由样本协方差矩阵: ,得:

将最小化 转化为最大化 ,即:

仍然使用拉格朗日乘数法,定义拉格朗日函数:

其中 是待定的拉格朗日乘数。

计算梯度,并令其等于 0 :

时,设 ,则:

是样本协方差矩阵 的最大 个特征值 的对应特征向量时(单位正交),目标函数:

有最大值。

在参考资料【9】和【10】中有两项证明,对应用此结论而提供了更坚实的数学支持。

以上,用 近似数据点 ,样本协方差矩阵 的特征向量 描述了数据集的主要成分,因此称为主成分。特征值 是主成分 的系数 的方差。

下面首先看 的样本平均数是多少:

在计算 的样本方差:

所以,特征值 表示主成分 的权值。

此外,主成分系数 线性无关,即样本协方差 ,其计算如下(当 时):

总结:对样本个数为 ,维数是 的数据集 进行主成分分析,其步骤如下:

  1. 计算样本平均 ,并得到由每个样本点偏差组成的 矩阵

    计算样本协方差矩阵

  2. 正交对角化为:

    其中:

    • 是特征值矩阵, 表示主成分的权值;
    • 是单位正交特征向量构成的 级的正交主成分矩阵,
  3. 计算主成分系数矩阵 ,其中

    上式等号两边右乘 ,得:

    即:数据点 的主成分分解式为:

    主成分系数 是偏差 以单位正交向量 为基的坐标。

注意的问题:

  • 在原始数据集中,如果某个特征的方差较大,则主成分方向会受其影响严重,此时,通常按照如下方式对数据给予处理:

    1. 在进行 PCA 之前,对数据进行标准差标准化处理:

      其中 是第 个特征的样本方差,即

    2. 经过标准化之后,再计算 的协方差矩阵:

      此矩阵也是相关系数矩阵(详见参考资料【4】第5章5.5.2节), 元是第 个特征与第 个特征的相关系数。

      又因为:

      即数据集的总方差等于维数 。(以上计算中使用了 ,且 的主对角线元素都是 1 。)

  • 在应用上述方法进行实际的数值计算时,特别是计算 时,会遇到麻烦,解决方法请延伸阅读参考资料【11】。

注意

PCA 是一种线性方法,如果对于非线性的数据,则不能直接使用上述方法。

参考资料

  1. 维基百科:主成分分析

  2. Kal Pearson

  3. Harold Hotelling

  4. 齐伟. 机器学习数学基础. 电子工业出版社

  5. 测地距离(geodesic distance),是图论中的术语,指图中两节点间的最短路径。注意区分于几何空间中的欧几里得距离。如下图所示:

    表示图中两点之间的欧几里得距离, 为两点之间的测地距离。

  6. 线代启示录:主成分分析

  7. 拉格朗日乘数法

  8. 正定矩阵

  9. 考虑下面的式子:

    ,且:

    则前述方程用矩阵形式表示:

    因为 的列向量是单位正交向量,即 。上式等号两侧左乘 ,得:

    下面正面,对于任何 ,只要满足以上条件,就有一个相同的目标函数值:

    将对称矩阵 正交对角化为: ,其中 是正交矩阵,

    左乘 、右乘 ,可得:

    ,则:

    因为 ,所以 的也有单位正交向量,则 也是一组解。

    从而证明: 所含的两组单位正交向量集合有相同的目标函数值

  10. 假设单位向量 是令 最大化的向量,满足:

    下面找出下一个单位向量 ,且满足 ,即与 正交。

    定义拉格朗日函数:

    其中, 是拉格朗日乘数。计算梯度,并设为 0 :

    上式左乘 ,可得:

    又因为:

    所以:

    即:

    显然 是对应的单位特征向量。

    同理可以推导 等情况。

  11. 比较 SVD 和 PCA

作者: 老齐
链接: http://math.itdiffer.com/pca.html
来源: 老齐教室-机器学习数学基础
本文原创发布于「老齐教室-机器学习数学基础」,转载请注明出处,谢谢合作!

https://gitee.com/qiwsir/images/raw/master/2021-2-15/1613357594979-1.png

results matching ""

    No results matching ""