欢迎访问 生活随笔!

生活随笔

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

详细推导PCA算法(包括算法推导必备的知识)

发布时间:2024/10/14 编程问答 103 豆豆
生活随笔 收集整理的这篇文章主要介绍了 详细推导PCA算法(包括算法推导必备的知识) 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

文章目录

  • 1. PCA优化目标
  • 2.理论依据
      • 2.1 矩阵换基底
      • 2.2 拉格朗日乘子法
      • 2.3 协方差矩阵
    • 2.4 特征向量和奇异值分解
      • 2.4.1 特征向量
      • 2.4.2 奇异值分解
      • 2.4.3 特征向量和奇异值分解的关系
  • 3 PCA
    • 3.1 PCA推导
    • 3.2 PCA过程总结


前言
该文章转载自
https://blog.csdn.net/QQ2627866800/article/details/86656237
自己做了点修订


1. PCA优化目标

用较少特征地数据表达较多特征地数据
PCA推导有两种主要思路:
        1 最大化数据投影后的的方差(让数据更分散)
        2 最小化投影造成的损失
        下图中旋转的是新坐标轴,每个数据点在该坐标轴上垂直投影,最佳的坐标轴为数据投影后各点数据之间距离最大。

2.理论依据

2.1 矩阵换基底

坐标变换的目标是,找到一组新的正交单位向量,替换原来的正交单位向量。
假设存在向量 a⃗=[32],要将其变换为以 u⃗=[1212],v⃗=[−1212]为新基底地坐标上, 求在新坐标系中的坐标 \text { 假设存在向量 } \vec{a}=\left[\begin{array}{l} 3 \\ 2 \end{array}\right], \text { 要将其变换为以 } \vec{u}=\left[\begin{array}{l} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{array}\right], \vec{v}=\left[\begin{array}{c} -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{array}\right] \text { 为新基底地坐标上, 求在新坐标系中的坐标 }  假设存在向量 a=[32], 要将其变换为以 u=[2121],v=[2121] 为新基底地坐标上求在新坐标系中的坐标 

∵\because 向量 a⃗\vec{a}a 在向量 u⃗\vec{u}u 上的投影距离 s:\mathrm{s}:s:
s=∥a⃗∥⋅cos⁡θ=a⃗⋅u⃗∥u⃗∥=a⃗⋅u⃗s=\|\vec{a}\| \cdot \cos \theta=\frac{\vec{a} \cdot \vec{u}}{\|\vec{u}\|}=\vec{a} \cdot \vec{u} s=acosθ=uau=au
其中: θ\thetaθ 表示两个向量之间的夹角
∴au=u⃗T⋅a⃗,av=v⃗T⋅a⃗\therefore a_{u}=\vec{u}^{T} \cdot \vec{a}, a_{v}=\vec{v}^{T} \cdot \vec{a} au=uTa,av=vTa
∴\therefore 向量 a⃗\vec{a}a 在新坐标系中的坐标可以表示为:
a⃗new=[u⃗v⃗]T⋅a⃗=[u⃗T⋅a⃗v⃗T⋅a⃗]\vec{a}_{n e w}=\left[\begin{array}{ll} \vec{u} & \vec{v} \end{array}\right]^{T} \cdot \vec{a}=\left[\begin{array}{l} \vec{u}^{T} \cdot \vec{a} \\ \vec{v}^{T} \cdot \vec{a} \end{array}\right] anew=[uv]Ta=[uTavTa]
如果矩阵 A\mathrm{A}A 的列向量分别表示原来坐标系中的点, 那么在新坐标系中的坐标为:
Anew=[u⃗v⃗]T⋅AA_{n e w}=\left[\begin{array}{ll} \vec{u} & \vec{v} \end{array}\right]^{T} \cdot A Anew=[uv]TA

2.2 拉格朗日乘子法

拉格朗日乘子法主要提供了一种求解函数在约束条件下极值的方法。下面还是通过一个例子说明。 假设存在一个函数 f(x,y),f(x, y),f(x,y), 求该函数在 g(x,y)=cg(x, y)=cg(x,y)=c 下的极值 (可以是极大, 也可以极小)

通过观察我们发现,在极值点的时候两个函数必然相切, 即此时各自的导数成正比, 从而:
∂f∂x=λ∂g∂x∂f∂y=λ∂g∂yg(x,y)=c\begin{array}{l} \frac{\partial f}{\partial x}=\lambda \frac{\partial g}{\partial x} \\ \frac{\partial f}{\partial y}=\lambda \frac{\partial g}{\partial y} \\ g(x, y)=c \end{array} xf=λxgyf=λygg(x,y)=c
通过联立上述三个公式, 既可以求出最终结果。拉格朗日算子的主要思路同上, 不过他假设了一个新的函数:
F(x,y,λ)=f(x,y)+λ[c−g(x,y)]F(x, y, \lambda)=f(x, y)+\lambda[c-g(x, y)] F(x,y,λ)=f(x,y)+λ[cg(x,y)]
然后分解求:
∂F∂x=0∂F∂y=0∂F∂λ=0\begin{array}{l} \frac{\partial F}{\partial x}=0 \\ \frac{\partial F}{\partial y}=0 \\ \frac{\partial F}{\partial \lambda}=0 \end{array} xF=0yF=0λF=0
从而完成求解过程

2.3 协方差矩阵

假设有一组数据:
样本编号 变量 x(如发传单数量) 变量 y(如购买数量) 变量 z(如购买总价 )11232352555⋯⋯⋯⋯\begin{array}{c|ccc} \text { 样本编号 } & \text { 变量 } x \text { (如发传单数量) } & \text { 变量 } y \text { (如购买数量) } & \text { 变量 } z \text { (如购买总价 }) \\ \hline 1 & 1 & 2 & 3 \\ 2 & 35 & 25 & 55 \\ \cdots & \cdots & \cdots & \cdots \end{array}  样本编号 12 变量 x (如发传单数量135 变量 y (如购买数量225 变量 z (如购买总价 )355
协方差研究的目的是变量 (特征) 之间的关系, 也就是上表中的发传单数量、购买数量、购买总额之间的相关情况 上表数据用矩阵表示为:
X=[135⋯225⋯355⋯]X=\left[\begin{array}{lll} 1 & 35 & \cdots \\ 2 & 25 & \cdots \\ 3 & 55 & \cdots \end{array}\right] X=123352555
那么两两变量之间的关系:
cov⁡(x,y)=E[(1−E(x))(2−E(y))+(35−E(x))(25−E(y))+⋯]cov⁡(x,z)=E[(1−E(x))(3−E(z))+(35−E(x))(55−E(z))+⋯]\begin{array}{l} \operatorname{cov}(x, y)=E[(1-E(x))(2-E(y))+(35-E(x))(25-E(y))+\cdots] \\ \operatorname{cov}(x, z)=E[(1-E(x))(3-E(z))+(35-E(x))(55-E(z))+\cdots] \end{array} cov(x,y)=E[(1E(x))(2E(y))+(35E(x))(25E(y))+]cov(x,z)=E[(1E(x))(3E(z))+(35E(x))(55E(z))+]
如果 E(x)=E(y)=E(z)=0E(x)=E(y)=E(z)=0E(x)=E(y)=E(z)=0 (可以通过数据初始化实现,即减去平均值),那么上述的协方差关系可以用如下矩阵乘法表示:
cov⁡(X)=1mXXT=[cov⁡(x,x)cov⁡(x,y)cov⁡(x,z)cov⁡(y,x)cov⁡(y,y)cov⁡(y,z)cov⁡(z,x)cov⁡(z,y)cov⁡(z,z)]\operatorname{cov}(X)=\frac{1}{m} X X^{T}=\left[\begin{array}{lll} \operatorname{cov}(x, x) & \operatorname{cov}(x, y) & \operatorname{cov}(x, z) \\ \operatorname{cov}(y, x) & \operatorname{cov}(y, y) & \operatorname{cov}(y, z) \\ \operatorname{cov}(z, x) & \operatorname{cov}(z, y) & \operatorname{cov}(z, z) \end{array}\right] cov(X)=m1XXT=cov(x,x)cov(y,x)cov(z,x)cov(x,y)cov(y,y)cov(z,y)cov(x,z)cov(y,z)cov(z,z)

2.4 特征向量和奇异值分解

2.4.1 特征向量

假设:左侧矩形由 [ij]=[1001]\left[\begin{array}{ll}i & j\end{array}\right]=\left[\begin{array}{ll}1 & 0 \\ 0 & 1\end{array}\right][ij]=[1001] 定义, 右侧矩形由 [i⃗′j⃗′]=[2000.5]\left[\begin{array}{ll}\vec{i}^{\prime} & \vec{j}^{\prime}\end{array}\right]=\left[\begin{array}{cc}2 & 0 \\ 0 & 0.5\end{array}\right][ij]=[2000.5] 定义。
根据 2.1 矩阵拉伸变换的结果, 变换矩阵 A=[u⃗Tv⃗T]=[2000.5],A=\left[\begin{array}{c}\vec{u}^{T} \\ \vec{v}^{T}\end{array}\right]=\left[\begin{array}{cc}2 & 0 \\ 0 & 0.5\end{array}\right],A=[uTvT]=[2000.5], 即 :
A⋅[ij⃗]=[i⃗′j⃗′]A \cdot\left[\begin{array}{ll} i & \vec{j} \end{array}\right]=\left[\begin{array}{ll} \vec{i}^{\prime} & \vec{j}^{\prime} \end{array}\right] A[ij]=[ij]
在应用变换矩阵变换时,我们发现存在与上图中红色向量平行的向量a⃗,\vec a ,a, 他们总满足:
A⋅a⃗//a⃗A \cdot \vec{a} / / \vec{a} Aa//a
即:
A⋅a⃗=λ⋅a⃗A \cdot \vec{a}=\lambda \cdot \vec{a} Aa=λa
所以:红色的特征向量不受变换矩阵的影响, 仍保持原来的方向, 我们称这类向量为变换矩阵A的特征向量, 对应的 Vambda 为特征值。又因为特征向量有很多个, 即 :
A⋅a⃗i=λi⋅a⃗iA \cdot \vec{a}_{i}=\lambda_{i} \cdot \vec{a}_{i} Aai=λiai
所以:
A⋅[a⃗1a⃗2⋯]=[a⃗1a⃗2⋯]⋅[λ1λ2⋱]⇒A=Q⋅Σ⋅Q−1A \cdot\left[\begin{array}{lll} \vec{a}_{1} & \vec{a}_{2} & \cdots \end{array}\right]=\left[\begin{array}{lll} \vec{a}_{1} & \vec{a}_{2} & \cdots \end{array}\right] \cdot\left[\begin{array}{lll} \lambda_{1} \\ & \lambda_{2} \\ & & \ddots \end{array}\right] \Rightarrow A=Q \cdot \Sigma \cdot Q^{-1} A[a1a2]=[a1a2]λ1λ2A=QΣQ1
其中:Q的列向量都是A变换矩阵的特征向量
另外,在做旋转变换时,要求变换前后的坐标维度不发生改变, 即A须为方阵
综上:如果方阵A满足 A=Q⋅Σ⋅Q−1,A=Q \cdot \Sigma \cdot Q^{-1},A=QΣQ1, 那么Q为特征向量,Σ\SigmaΣ 为对应的特征值

2.4.2 奇异值分解

奇异值分解(svd: singular value decomposition ) 定义:对于任意的矩阵A,存在:
Am×n=Um×m⋅Σm×n⋅Vn×nTA_{m \times n}=U_{m \times m} \cdot \Sigma_{m \times n} \cdot V_{n \times n}^{T} Am×n=Um×mΣm×nVn×nT其中:
UT⋅U=ImVT⋅V=In\begin{array}{l} U^{T} \cdot U=I_{m} \\ V^{T} \cdot V=I_{n} \end{array} UTU=ImVTV=In即:U的列向量两两正交且模为1, V列向量两两正交且模为1,即:
UT=U−1U^{T}=U^{-1} UT=U1VT=V−1V^{T}=V^{-1} VT=V1

2.4.3 特征向量和奇异值分解的关系

对于任意矩阵 A,\mathrm{A},A, 对A做svd有:
AAT=UΣVT⋅VΣUT=UΣ2U−1A A^{T}=U \Sigma V^{T} \cdot V \Sigma U^{T}=U \Sigma^{2} U^{-1} AAT=UΣVTVΣUT=UΣ2U1
Σ′=Σ2,\Sigma^{\prime}=\Sigma^{2},Σ=Σ2, 则:
AAT=UΣ′U−1A A^{T}=U \Sigma^{\prime} U^{-1} AAT=UΣU1
满足 A=QΣQ−1A=Q \Sigma Q^{-1}A=QΣQ1 特征向量定义
所以 AA^T 能实现特征分解, 又因为:
AAT=U′′Σ′′V′′T⏟svdA A^{T}=\underbrace{U^{\prime \prime} \Sigma^{\prime \prime} V^{\prime \prime T}}_{s v d} AAT=svdUΣVT
所以:
U=U′′Σ′=Σ′′U−1=V′′⇒U=V′′\begin{array}{c} U=U^{\prime \prime} \\ \Sigma^{\prime}=\Sigma^{\prime \prime} \\ U^{-1}=V^{\prime \prime} \Rightarrow U=V^{\prime \prime} \end{array} U=UΣ=ΣU1=VU=V
因此:对 AATA A^{T}AAT 做SVD,那么得到的U"列向量为特征向量 (对应A的U矩阵), Σ′′\Sigma^{\prime \prime}Σ 为特征值对角阵
同理: 对 ATAA^{T} AATA 做SVD,那么得到的U"列向量为特征向量 (对应A的V矩阵), Σ′′\Sigma^{\prime \prime}Σ 为特征值对角矩阵

3 PCA

3.1 PCA推导

PCA的目标是找到一组新的正交基 {u1,u2,⋯,uk}\left\{u_{1}, u_{2}, \cdots, u_{k}\right\} \quad{u1,u2,,uk} (从n维下降到k维), 使得n维数据点在该正交基构成的平面上投影后,投影数据点间的距离最大, 即数据间的方差最大。如果数据在每个正交基上投影后的方差最大, 那么同样满足在正交基所构成的平面上投影距离最大。

根据2.1,先考虑一个正交基 uj,u_{j},uj, 数据点 xix_{i}xi 在该基底上的投影距离为 xiT⋅uj,x_{i}^{T} \cdot u_{j},xiTuj, 所以所有的mmmnnn维样本数据在该基底上投影的方差 JjJ_{j}Jj 为:
Jj=1m∑i=1m(xiTuj−xcenterTuj)2J_{j}=\frac{1}{m} \sum_{i=1}^{m}\left(x_{i}^{T} u_{j}-x_{\text {center}}^{T} u_{j}\right)^{2} Jj=m1i=1m(xiTujxcenterTuj)2Jj=1m∑i=1m(xiTuj)2=1m∑i=1m(ujTxi⋅xiTuj)=ujT⋅1m∑i=1m(xixiT)⋅ujJ_{j}=\frac{1}{m} \sum_{i=1}^{m}\left(x_{i}^{T} u_{j}\right)^{2}=\frac{1}{m} \sum_{i=1}^{m}\left(u_{j}^{T} x_{i} \cdot x_{i}^{T} u_{j}\right)=u_{j}^{T} \cdot \frac{1}{m} \sum_{i=1}^{m}\left(x_{i} x_{i}^{T}\right) \cdot u_{j} Jj=m1i=1m(xiTuj)2=m1i=1m(ujTxixiTuj)=ujTm1i=1m(xixiT)uj所以:Jj=ujT⋅1m(x1x1T+x2x2T+⋯+xmxmT)⋅uj=ujT⋅1m([x1⋯xm]⋅[x1T⋮xmT])⋅uj==1mujTXXTujJ_{j}=u_{j}^{T} \cdot \frac{1}{m}\left(x_{1} x_{1}^{T}+x_{2} x_{2}^{T}+\cdots+x_{m} x_{m}^{T}\right) \cdot u_{j}=u_{j}^{T} \cdot \frac{1}{m}\left(\left[\begin{array}{lll} x_{1} & \cdots & x_{m} \end{array}\right] \cdot\left[\begin{array}{c} x_{1} ^{T}\\ \vdots \\ x_{m}^{T} \end{array}\right]\right) \cdot u_{j}==\frac{1}{m} u_{j}^{T} X X^{T} u_{j} Jj=ujTm1(x1x1T+x2x2T++xmxmT)uj=ujTm1[x1xm]x1TxmTuj==m1ujTXXTuj
假设 Sn×n=1mXXT,S_{n\times n}=\frac{1}{m} X X^{T},Sn×n=m1XXT,:Jj=ujT⋅S⋅uj,: J_{j}=u_{j}^{T} \cdot S \cdot u_{j},:Jj=ujTSuj, 根据PCA目标, 我们需要求解 JjJ_{j}Jj 最大时对应 的 uju_{j}uj 根据 2.2 中的拉格朗日算子 (求极值) 求解:
Jj=ujTSujJ_{j}=u_{j}^{T} S u_{j} Jj=ujTSujs.t. ujTuj=1\text { s.t. } u_{j}^{T} u_{j}=1 s.t. ujTuj=1
则构造函数:
F(uj)=ujTSuj+λj(1−ujTuj)F\left(u_{j}\right)=u_{j}^{T} S u_{j}+\lambda_{j}\left(1-u_{j}^{T} u_{j}\right) F(uj)=ujTSuj+λj(1ujTuj)
求解 ∂F∂uj=0,\frac{\partial F}{\partial u_{j}}=0,ujF=0, 得:
2S⋅uj−2λj⋅uj=0⇒Suj=λjuj2 S \cdot u_{j}-2 \lambda_{j} \cdot u_{j}=0 \Rightarrow S u_{j}=\lambda_{j} u_{j} 2Suj2λjuj=0Suj=λjuj
结合2.4.1则:当 uj、λju_{j} 、 \lambda_{j}ujλj 分别为S矩阵的特征向量、特征值时, JjJ_{j}Jj 有极值, 把上述结果带回公式得JjJ_{j}Jj最大值:
Jjm=ujTλjuj=λjJ_{j_{m}}=u_{j}^{T} \lambda_{j} u_{j}=\lambda_{j} Jjm=ujTλjuj=λj
所以对于任意满足条件的正交基{u1,u2,⋯,uk}\left\{u_{1}, u_{2}, \cdots, u_{k}\right\} \quad{u1,u2,,uk} ,对应的数据在上面投影后的方差值为S矩阵的特征向量, 从而:
Jmax⁡=∑j=1kλj,λ人大到小排序 J_{\max }=\sum_{j=1}^{k} \lambda_{j}, \lambda \text { 人大到小排序 } Jmax=j=1kλj,λ 人大到小排序 
所以投影正交基为S的特征向量中的前k个最大特征值对应的特征向量。 接下来对S进行特征分解, 根据2.4.3特征向量和svd的关系结论, S的特征向量集合:
U=Uof svd⁡(S)=Uof svd⁡(1mXXT)U=U \text { of } \operatorname{svd}(S)=U \text { of } \operatorname{svd}\left(\frac{1}{m} X X^{T}\right) U=U of svd(S)=U of svd(m1XXT)另外, 由于 S=1mXXTS=\frac{1}{m} X X^{T}S=m1XXT 由于X已0均值处理, 根据2.3 协方差矩阵定义:S为数据集X的协方差矩阵。 综上, 即可得到满足投影后数据距离最大的新的正交基 {u1,u2,⋯,uk}\left\{u_{1}, u_{2}, \cdots, u_{k}\right\}{u1,u2,,uk} 因此降维后的数据为:
Xnewk×m=[u1T′u2T⋮ukT]k×n⋅Xn×mX_{n e w_{k \times m}}=\left[\begin{array}{c}u_{1}^{T^{\prime}} \\u_{2}^{T} \\\vdots \\u_{k}^{T} \end{array}\right]_{k \times n} \cdot X_{n \times m} Xnewk×m=u1Tu2TukTk×nXn×m

3.2 PCA过程总结

PCA流程如下:

  • 初始化 X,X,X, 使得所有样本之间的特征值均值为0, 同时应用feature scaling, 缩放到-0.5 ∼0.5\sim 0.50.5;
  • 计算X的协方差矩阵S;
  • 对S进行SVD分解, U即我们要求的新坐标系集合, Σ\SigmaΣ 为特征值集合 (计算时特征值都会大于0, 且结果会从小到大 排列) ;
  • 按照特征值从大到小排序, 要降低为k维, 那么取前k个特征值对应的特征向量, 就是新的k个坐标轴
  • 把X映射到新的坐标系中, 完整降维操作;
    根据之前的公式, 做PCA投影后, 投影数据的方差:
    VarXproject=∑j=1kJj=∑j=1kλjV a r_{X_{p r o j e c t}}=\sum_{j=1}^{k} J_{j}=\sum_{j=1}^{k} \lambda_{j} VarXproject=j=1kJj=j=1kλj
    又因为:数据从n维投影新的n维的坐标系, 方差不会发生改变 (向量的模长度相等且为1,可以用2D坐标系投影到45-135 度坐标系验证),即:
    VarX=VarXproject =∑j=1nJj=∑j=1nλjV a r_{X}=V a r_{X_{\text {project }}}=\sum_{j=1}^{n} J_{j}=\sum_{j=1}^{n} \lambda_{j} VarX=VarXproject =j=1nJj=j=1nλj
    即:X的协方差矩阵的特征值和对应X的方差
  • 总结

    以上是生活随笔为你收集整理的详细推导PCA算法(包括算法推导必备的知识)的全部内容,希望文章能够帮你解决所遇到的问题。

    如果觉得生活随笔网站内容还不错,欢迎将生活随笔推荐给好友。