【数学】主成分分析(PCA)的详细深度推导过程

pca · 浏览次数 : 101

小编点评

**目标函数:** \\(-2x^TDc+c^Tc\) **编码矩阵 D 的求解:** 1. 定义矩阵 \\(X\\in \\mathbb{R}^{m\\times n}\\),其中 \\(m\\) 是数据点的数量, \\(n\\) 是特征数量。 2. 确定 D 的第 \\(i\\) 行,即特征向量 \(\mathbf{d}_i\) 的值。 3. 计算矩阵 \\(X^TXd\\)。 4. 确定 D 的最大特征值 \(\lambda'\) 和对应的特征向量 \(\mathbf{d}_i\)。 5. 确定 D 的最大特征值对应的特征向量 \(\mathbf{d}_i\) 的值。 **拉格朗日乘子法求解 D:** ```python # 定义拉格朗日函数 def lagrangian(d, lambda): return d.T @ X.T @ d + lambda * (d.T @ d - 1) # 求解 D 的最大特征值和特征向量 d, lambda_ = maximize(lagrangian, (0, 0)) ```

正文

Based on Deep Learning (2017, MIT) book.

本文基于Deep Learning (2017, MIT),推导过程补全了所涉及的知识及书中推导过程中跳跃和省略的部分。
blog

1 概述

现代数据集,如网络索引、高分辨率图像、气象学、实验测量等,通常包含高维特征,高纬度的数据可能不清晰、冗余,甚至具有误导性。数据可视化和解释变量之间的关系很困难,而使用这种高维数据训练的神经网络模型往往容易出现过拟合(维度诅咒)。
主成分分析(PCA)是一种简单而强大的无监督机器学习技术,用于数据降维。它旨在从大型变量集中提取一个较小的数据集,同时尽可能保留原始信息和特征(有损压缩)。PCA有助于识别数据集中最显著和有意义的特征,使数据易于可视化。应用场景包括:统计学、去噪和为机器学习算法预处理数据。

  • 主成分是什么?
    主成分是构建为原始变量的线性组合的新变量。这些新变量是不相关的,并且包含原始数据中大部分的信息。

2 背景数学知识

这些知识对下一节的推导很重要。

  • 正交向量和矩阵:
    • 如果两个向量垂直,则它们是正交的。即两个向量的点积为零。
    • 正交矩阵是一个方阵,其行和列是相互正交的单位向量;每两行和两列的点积为零,每一行和每一列的大小为1。
    • 如果\(A^T=A^{-1}\)\(AA^T=A^TA=I\),则\(A\)是正交矩阵。
    • 在机器人学中,旋转矩阵通常是一个\(3\times3\)的正交矩阵,在空间变换中它会旋转向量的方向但保持原始向量的大小。
  • 矩阵、向量乘法规则:
    • \((AB)^T=B^TA^T\),两个矩阵的乘积的转置。
    • \(\vec{a}^T\vec{b}=\vec{b}^T\vec{a}\),两个结果都是标量,标量的转置是相同的。
    • \((A + B)C = AC + BC\),乘法是可分配的。
    • \(AB \neq{} BA\),乘法一般不满足交换律。
    • \(A(BC)=(AB)C\),乘法满足结合律。
  • 对称矩阵:
    • \(A=A^T\)\(A\)是对称矩阵。
    • \(X^TX\)是对称矩阵,因为\((X^TX)^T=X^TX\)
  • 向量导数规则(\(B\)是常量矩阵):
    • \(d(x^TB)/dx=B\)
    • \(d(x^Tx)/dx=2x\)
    • \(d(x^TBx)/dx=2Bx\)
  • 矩阵迹规则:
    • \(Tr(A)=Tr(A^T)\)
    • \(Tr(AB)=Tr(BA)\)
    • \(Tr(A)=\sum_i{\lambda_i}\),其中\(\lambda\)\(A\)的特征值。
    • 迹在循环移位下不变:\(Tr(ABCD)=Tr(BCDA)=Tr(CDAB)=Tr(DABC)\)
  • 向量和矩阵范数:
    • 向量的\(L^2\)范数,也称为欧几里得范数:\(||x||_2=\sqrt{\sum_i|x_i|^2}\)
    • 通常使用平方的\(L^2\)范数来衡量向量的大小,可以计算为\(x^Tx\)
    • Frobenius范数用于衡量矩阵的大小:\(||A||_F=\sqrt{\sum_{i,j}A^2_{i,j}}\)
    • Frobenius范数是所有矩阵元素的绝对平方和的平方根。
    • Frobenius范数是矩阵版本的欧几里得范数。
  • 特征值分解和特征值:
    • 方阵\(A\)的特征向量是一个非零向量\(v\),使得\(A\)的乘法仅改变\(v\)的比例:\(Av=\lambda v\)\(\lambda\)是特征值,\(v\)是特征向量。
    • 假设矩阵\(A\)\(n\)个线性无关的特征向量\(v^{(i)}\),我们可以将所有特征向量连接起来形成一个矩阵\(V=[v^{(1)},\ldots,v^{(n)}]\),并通过连接所有特征值\(\lambda=[\lambda_1,\ldots,\lambda_n]^T\)形成一个向量,那么\(A\)特征分解\(A=Vdiag(\lambda)V^{-1}\)
    • 每个实对称矩阵都可以分解为\(A=Q\Lambda Q^T\),其中\(Q\)是由\(A\)的特征向量组成的正交矩阵,\(\Lambda\)(读作'lambda')是一个对角矩阵。
  • 拉格朗日乘数法:
    • 拉格朗日乘数法是一种在方程约束下寻找函数局部最大值和最小值的策略。
    • 一般形式:\(\mathcal{L}(x,\lambda)=f(x)+\lambda\cdot g(x)\)\(\lambda\)称为拉格朗日乘子。

3 详细PCA推导

需求描述

我们有\(m\)个点的输入数据,表示为\({x^{(1)},...,x^{(m)}}\)\(\mathbb{R}^{n}\)的实数集中。因此,每个点\(x^{(i)}\)是一个列向量,具有\(n\)维特征。

需要对输入数据进行有损压缩,将这些点编码以表示它们的较低维度版本。换句话说,我们想要找到编码向量\(c^{(i)}\in \mathbb{R}^{l}\)\((l<n)\)来表示每个输入点\(x^{(i)}\)。我们的目标是找到产生输入的编码向量的编码函数\(f(x)=c\),以及相应的重构(解码)函数\(x\approx g(f(x))\),根据编码向量\(c\)计算原始输入。

解码的\(g(f(x))\)是一组新的点(变量),因此它与原始\(x\)是近似的。存储\(c^{(i)}\)和解码函数比存储\(x^{(i)}\)更节省空间,因为\(c^{(i)}\)的维度较低。

解码矩阵

我们选择使用矩阵\(D\)作为解码矩阵,将编码向量\(c^{(i)}\)映射回\(\mathbb{R}^{n}\),因此\(g(c)=Dc\),其中\(D\in \mathbb{R}^{n\times l}\)。为了简化编码问题,PCA将\(D\)的列约束为彼此正交。

衡量重构的表现

在继续之前,我们需要弄清楚如何生成最优的编码点\(c^{*}\),我们可以测量输入点\(x\)与其重构\(g(c^*)\)之间的距离,使用\(L^2\)范数(或欧几里得范数):\(c^{*}=\arg\min_c||x-g(c)||_2\)。由于\(L^2\)范数是非负的,并且平方操作是单调递增的,所以我们可以转而使用平方的\(L^2\)范数:

\[c^{*}={\arg\min}_c||x-g(c)||_2^2 \]

向量的\(L^2\)范数是其分量的平方和,它等于向量与自身的点积,例如\(||x||_2=\sqrt{\sum|x_i|^2}=\sqrt{x^Tx}\),因此平方的\(L^2\)范数可以写成以下形式:

\[||x-g(c)||_2^2 = (x-g(c))^T(x-g(c)) \]

由分配率:

\[=(x^T-g(c)^T)(x-g(c))=x^Tx-x^Tg(c)-g(c)^Tx+g(c)^Tg(c) \]

由于\(x^Tg(c)\)\(g(c)^Tx\)是标量,标量等于其转置,\((g(c)^Tx)^T=x^Tg(c)\),所以:

\[=x^Tx-2x^Tg(c)+g(c)^Tg(c) \]

为了找到使上述函数最小化的\(c\),第一项可以省略,因为它不依赖于\(c\),所以:

\[c^*={\arg\min}_c-2x^Tg(c)+g(c)^Tg(c) \]

然后用\(g(c)\)的定义\(Dc\)进行替换:

\[={\arg\min}_c-2x^TDc+c^TD^TDc \]

由于\(D\)的正交性和单位范数约束:

\[c^*={\arg\min}_c-2x^TDc+c^TI_lc \]

\[= {\arg\min}_c-2x^TDc+c^Tc \]

目标函数

现在目标函数是\(-2x^TDc+c^Tc\),我们需要找到\(c^*\)来最小化目标函数。使用向量微积分,并令其导数等于0:

\[\nabla_c(-2x^TDc+c^Tc)=0 \]

根据向量导数规则:

\[-2D^Tx+2c=0 \Rightarrow c=D^Tx \]

找到编码矩阵 \(D\)

所以编码器函数是 \(f(x)=D^Tx\)。因此我们可以定义 PCA 重构操作为 \(r(x)=g(f(x))=D(D^Tx)=DD^Tx\)

因此编码矩阵 \(D\) 也被重构过程使用。我们需要找到最优的 \(D\) 来最小化重构误差,即输入和重构之间所有维度特征的距离。这里使用 Frobenius 范数(矩阵范数)定义目标函数:

\[D^*={\arg\min}_D\sqrt{\sum_{i,j}(x_j^{(i)}-r(x^{i})_j)^2},\quad D^TD=I_l \]

从考虑 \(l=1\) 的情况开始(这也是第一个主成分),\(D\) 是一个单一向量 \(d\),并使用平方 \(L^2\) 范数形式:

\[d^*={\arg\min}_d{\sum_{i}||(x^{(i)}-r(x^{i}))}||_2^2, ||d||_2=1 \]

\[= {\arg\min}_d{\sum_{i}||(x^{(i)}-dd^Tx^{(i)})||_2^2}, ||d||_2=1 \]

\(d^Tx^{(i)}\) 是一个标量:

\[= {\arg\min}_d{\sum_{i}||(x^{(i)}-d^Tx^{(i)}d)}||_2^2, ||d||_2=1 \]

标量等于其自身的转置:

\[d^*= {\arg\min}_d{\sum_{i}||(x^{(i)}-x^{(i)T}dd)}||_2^2, ||d||_2=1 \]

使用矩阵形式表示

\(X\in \mathbb{R}^{m\times n}\) 表示所有描述点的向量堆叠,即 \(\{x^{(1)^T}, x^{(2)^T}, \ldots, x^{(i)^T}, \ldots, x^{(m)^T}\}\),使得 \(X_{i,:}=x^{(i)^T}\)

\[X = \begin{bmatrix} x^{(1)^T}\\ x^{(2)^T}\\ \ldots\\ x^{(m)^T} \end{bmatrix} \Rightarrow Xd = \begin{bmatrix} x^{(1)^T}d\\ x^{(2)^T}d\\ \ldots\\ x^{(m)^T}d \end{bmatrix} \]

\[\Rightarrow Xdd^T = \begin{bmatrix} x^{(1)^T}dd^T\\ x^{(2)^T}dd^T\\ \ldots\\ x^{(m)^T}dd^T\\ \end{bmatrix} \]

\[\Rightarrow X-Xdd^T = \begin{bmatrix} x^{(1)^T}-x^{(1)^T}dd^T\\ x^{(2)^T}-x^{(2)^T}dd^T\\ \ldots\\ x^{(m)^T}-x^{(m)^T}dd^T\\ \end{bmatrix} \]

矩阵中的一行的转置:

\[(x^{(i)^T}-x^{(i)^T}dd^T)^T=x^{(i)}-dd^Tx^{(i)} \]

由于 \(d^Tx^{(i)}\) 是标量:

\[=x^{(i)}-d^Tx^{(i)}d=x^{(i)}-x^{(i)^T}dd \]

所以我们知道 \(X\) 的第 \(i\) 行的 \(L^2\) 范数与原始形式相同,因此我们可以使用矩阵重写问题,并省略求和符号:

\[d^*={\arg\min}_{d}||X-Xdd^T||_F^2, \quad d^Td=1 \]

利用矩阵迹规则简化 Frobenius 范数部分如下:

\[{\arg\min}_{d}||X-Xdd^T||_F^2 \]

\[={\arg\min}_{d}Tr((X-Xdd^T)^T(X-Xdd^T)) \]

\[={\arg\min}_{d}-Tr(X^TXdd^T)-Tr(dd^TX^TX)+Tr(dd^TX^TXdd^T) \]

\[={\arg\min}_{d}-2Tr(X^TXdd^T)+Tr(X^TXdd^Tdd^T) \]

由于 \(d^Td=1\)

\[={\arg\min}_{d}-2Tr(X^TXdd^T)+Tr(X^TXdd^T) \]

\[={\arg\min}_{d}-Tr(X^TXdd^T) \]

\[={\arg\max}_{d}Tr(X^TXdd^T) \]

由于迹是循环置换不变的,将方程重写为:

\[d^*={\arg\max}_{d}Tr(d^TX^TXd), \quad d^Td=1 \]

由于 \(d^TX^TXd\) 是实数,因此迹符号可以省略:

\[d^*={\arg\max}_{d}d^TX^TXd,\quad d^Td=1 \]

寻找最优的 \(d\)

现在的问题是找到最优的 \(d\) 来最大化 \(d^TX^TXd\),并且有约束条件 \(d^Td=1\)

使用拉格朗日乘子法来将问题描述为关于 \(d\) 的形式:

\[\mathcal{L}(d,\lambda)=d^TX^TXd+\lambda(d^Td-1) \]

\(d\) 求导数(向量导数规则):

\[\nabla_d\mathcal{L}(d,\lambda)=2X^TXd+2\lambda d \]

令导数等于0,\(d\) 将是最优的:

\[2X^TXd+2\lambda d=0 \]

\[X^TXd=-\lambda d \]

\[X^TXd=\lambda' d,\quad(\lambda'=-\lambda) \]

这个方程是典型的矩阵特征值分解形式,\(d\) 是矩阵 \(X^TX\) 的特征向量,\(\lambda'\) 是对应的特征值。

利用上述结果,让我们重新审视原方程:

\[d^*={\arg\max}_{d}d^TX^TXd, \quad d^Td=1 \]

\[={\arg\max}_{d}d^T\lambda' d \]

\[={\arg\max}_{d}\lambda'd^T d \]

\[={\arg\max}_{d}\lambda' \]

现在问题已经变的非常清楚了,\(X^TX\) 的最大特征值会最大化原方程的结果,因此最优的 \(d\) 是矩阵 \(X^TX\) 对应最大特征值的特征向量。

这个推导是针对 \(l=1\) 的情况,只包含第一个主成分。当 \(l>1\) 时,\(D=[d_1, d_2, \ldots]\),第一个主成分 \(d_1\) 是矩阵 \(X^TX\) 对应最大特征值的特征向量,第二个主成分 \(d_2\) 是对应第二大特征值的特征向量,以此类推。


4 总结

我们有一个数据集,包含 \(m\) 个点,记为 \({x^{(1)},...,x^{(m)}}\)
\(X\in \mathbb{R}^{m\times n}\) 为将所有这些点堆叠而成的矩阵:\([x^{(1)^T}, x^{(2)^T}, \ldots, x^{(i)^T}, \ldots, x^{(m)^T}]\)

主成分分析(PCA)编码函数表示为 \(f(x)=D^Tx\),重构函数表示为 \(x\approx g(c)=Dc\),其中 \(D=[d_1, d_2, \ldots]\) 的列是 \(X^TX\) 的特征向量,特征向量对应的特征值大小为降序排列。\(D^Tx\)即是降维度之后的数据。

与【数学】主成分分析(PCA)的详细深度推导过程相似的内容:

【数学】主成分分析(PCA)的详细深度推导过程

Based on Deep Learning (2017, MIT) book. 本文基于Deep Learning (2017, MIT),推导过程补全了所涉及的知识及书中推导过程中跳跃和省略的部分。 blog 1 概述 现代数据集,如网络索引、高分辨率图像、气象学、实验测量等,通常包含高维特征,

聊聊基于Alink库的主成分分析(PCA)

概述 主成分分析(Principal Component Analysis,PCA)是一种常用的数据降维和特征提取技术,用于将高维数据转换为低维的特征空间。其目标是通过线性变换将原始特征转化为一组新的互相无关的变量,这些新变量称为主成分,它们按照方差递减的顺序排列,以保留尽可能多的原始数据信息。 主

主成分分析(PCA)介绍

目录计算过程投影分量计算 假设你有一家理发店,已经记录了过去一年中所有顾客的头发长度和发型偏好的数据。现在你想从这些数据中提取一些主要的信息,比如顾客最常选择的发型类型,以及不同发型之间的相关性等。这对于你未来开展有针对性的营销活动很有帮助。 具体来说,我们可以将每个顾客的发型偏好用一个多维向量来表

算法金 | 再见,PCA 主成分分析!

​大侠幸会,在下全网同名[算法金] 0 基础转 AI 上岸,多个算法赛 Top [日更万日,让更多人享受智能乐趣] 1. 概念:数据降维的数学方法 定义 主成分分析(PCA)是一种统计方法,通过正交变换将一组可能相关的变量转换为一组线性不相关的变量,这组新的变量称为主成分。 大白话,PCA能够从数据

解密数仓高可用failover流程

摘要: Gaussdb的HA采用主备从的架构实现数据可靠性。当主DN发生故障时,备DN走failover流程,升级成为新主DN,保证集群不因单DN故障而中断业务。 本文分享自华为云社区《【玩转PB级数仓GaussDB(DWS)】dws高可用之failover流程大解密》,作者:fxy0224。 众所

python入门基础(15)--模块和python中数学、日期、时间类模块。

接上篇,当我们创建了很多类,比如 图书馆里的藏书,分社会科学类,艺术类、生活类、农业类、工业类等,而工业类又分为轻工业、重工业、信息工业,然后再细分。当分的越来越细时,程序就会越来越大。如何管理,便成了程序开发过程中一个重要的环节。于是可以按照图书馆分类管理的思想,对程序代码进行管理。 将一个应用程

C# 12 中的新增功能

新的 C# 12 功能在预览版中已经引入. 您可以使用最新的 Visual Studio 预览版或最新的 .NET 8 预览版 SDK 来尝试这些功能。以下是一些新引入的功能: 主构造函数 集合表达式 默认 Lambda 参数 任何类型的别名 内联数组 拦截器 使用nameof访问实例成员 主构造函

6.1 KMP算法搜索机器码

KMP算法是一种高效的字符串匹配算法,它的核心思想是利用已经匹配成功的子串前缀的信息,避免重复匹配,从而达到提高匹配效率的目的。KMP算法的核心是构建模式串的前缀数组Next,Next数组的意义是:当模式串中的某个字符与主串中的某个字符失配时,Next数组记录了模式串中应该回退到哪个位置,以便继续匹...

17岁中专女生勇夺2024阿里全球数学赛12名好成绩,今天,站在程序员的视角,我们来聊聊数学对编程的价值与意义...

大家好,我是程序员陶朱公,一个认真生活,总想超越自己的程序员。 前言 相信这两天,大家都刷屏到了一个比较热度的新闻——17岁中专女生在今年这届阿里举办的全球数赛中,勇夺第12名的好成绩。 ↓↓↓ 看到这里,可能有小伙伴会觉得有点疑惑:又不是第一名,不明白第12名的她,为什么会引起社会这么大的一个反响

讯飞星火大模型 与New Bing实测对比

昨天科大讯飞发布了讯飞星火认知大模型,在发布会现场实测大模型的7种核心能力,并发布了它在教育、办公、汽车、数字员工领域的应用成果。科大讯飞董事长刘庆峰表示:认知大模型展示了通用人工智能的曙光,讯飞星火认知大模型已在文本生成、知识问答、数学能力3种能力上超越ChatGPT。NewBing 也全面开放给