详细推导pca算法（包括算法推导必备的知识） -ag凯发k8国际

文章目录

• 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
自己做了点修订

---

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

2.1 矩阵换基底

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

$\because$ 向量 $a$ 在向量 $u$ 上的投影距离 $\mathrm{s}:$
$$s=\Vert a\Vert \cdot \cos \theta =\genfrac{}{}{0ex}{}{a\cdot u}{\Vert u\Vert }=a\cdot u$$
其中： $\theta$ 表示两个向量之间的夹角
$$\therefore a^u=u^t\cdot a,a^v=v^t\cdot a$$
$\therefore$ 向量 $a$ 在新坐标系中的坐标可以表示为:
$$a^{new}={\left[\begin{array}{ll}u& v\end{array}\right]}^t\cdot a=\left[\begin{array}{l}{u}^t\cdot a\\ v^t\cdot a\end{array}\right]$$
如果矩阵 $\mathrm{a}$ 的列向量分别表示原来坐标系中的点, 那么在新坐标系中的坐标为：
$$a^{new}={\left[\begin{array}{ll}u& v\end{array}\right]}^t\cdot a$$

2.2 拉格朗日乘子法

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

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

2.3 协方差矩阵

假设有一组数据：
$$\begin{array}{cccc}\text{ 样本编号 }& \text{ 变量 }x\text{ (如发传单数量) }& \text{ 变量 }y\text{ (如购买数量) }& \text{ 变量 }z\text{ (如购买总价 })\\ 1& 1& 2& 3\\ 2& 35& 25& 55\\ \cdots & \cdots & \cdots & \cdots \end{array}$$
协方差研究的目的是变量 (特征) 之间的关系, 也就是上表中的发传单数量、购买数量、购买总额之间的相关情况 上表数据用矩阵表示为:
$$x=\left[\begin{array}{lll}1& 35& \cdots \\ 2& 25& \cdots \\ 3& 55& \cdots \end{array}\right]$$
那么两两变量之间的关系：
$$\begin{array}{l}\mathrm{cov}(x,y)=e[(1-e(x))(2-e(y))(35-e(x))(25-e(y))\cdots ]\\ \mathrm{cov}(x,z)=e[(1-e(x))(3-e(z))(35-e(x))(55-e(z))\cdots ]\end{array}$$
如果 $e(x)=e(y)=e(z)=0$ (可以通过数据初始化实现，即减去平均值)，那么上述的协方差关系可以用如下矩阵乘法表示:
$$\mathrm{cov}(x)=\genfrac{}{}{0ex}{}{1}{m}x{x}^t=\left[\begin{array}{lll}\mathrm{cov}(x,x)& \mathrm{cov}(x,y)& \mathrm{cov}(x,z)\\ \mathrm{cov}(y,x)& \mathrm{cov}(y,y)& \mathrm{cov}(y,z)\\ \mathrm{cov}(z,x)& \mathrm{cov}(z,y)& \mathrm{cov}(z,z)\end{array}\right]$$

2.4 特征向量和奇异值分解

2.4.1 特征向量

假设：左侧矩形由 $\left[\begin{array}{ll}i& j\end{array}\right]=\left[\begin{array}{ll}1& 0\\ 0& 1\end{array}\right]$ 定义, 右侧矩形由 $\left[\begin{array}{ll}{i}^{\prime }& j^{\prime }\end{array}\right]=\left[\begin{array}{cc}2& 0\\ 0& 0.5\end{array}\right]$ 定义。
根据 2.1 矩阵拉伸变换的结果, 变换矩阵 $a=\left[\begin{array}{c}{u}^t\\ v^t\end{array}\right]=\left[\begin{array}{cc}2& 0\\ 0& 0.5\end{array}\right],$ 即 :
$$a\cdot \left[\begin{array}{ll}i& j\end{array}\right]=\left[\begin{array}{ll}{i}^{\prime }& j^{\prime }\end{array}\right]$$
在应用变换矩阵变换时，我们发现存在与上图中红色向量平行的向量$a,$ 他们总满足：
$$a\cdot a//a$$
即：
$$a\cdot a=\lambda \cdot a$$
所以：红色的特征向量不受变换矩阵的影响, 仍保持原来的方向, 我们称这类向量为变换矩阵a的特征向量, 对应的 vambda 为特征值。又因为特征向量有很多个, 即 :
$$a\cdot a^i={\lambda }^i\cdot a^i$$
所以:
$$a\cdot \left[\begin{array}{lll}{a}^1& a^2& \cdots \end{array}\right]=\left[\begin{array}{lll}{a}^1& 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}$$
其中：q的列向量都是a变换矩阵的特征向量
另外，在做旋转变换时，要求变换前后的坐标维度不发生改变, 即a须为方阵
综上：如果方阵a满足 $a=q\cdot \sigma \cdot q^{-1},$ 那么q为特征向量,$\sigma$ 为对应的特征值

2.4.2 奇异值分解

奇异值分解（svd: singular value decomposition ) 定义：对于任意的矩阵a，存在：
$$a^{m\times n}=u^{m\times m}\cdot {\sigma }^{m\times n}\cdot v^{n\times n}$$其中:
$$\begin{array}{l}{u}^t\cdot u=i^m\\ v^t\cdot v=i^n\end{array}$$即：u的列向量两两正交且模为1， v列向量两两正交且模为1，即：
$$u^t=u^{-1}$$$$v^t=v^{-1}$$

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

对于任意矩阵 $\mathrm{a},$ 对a做svd有：
$$a{a}^t=u\sigma v^t\cdot v\sigma u^t=u{\sigma }^2{u}^{-1}$$
令 ${\sigma }^{\prime }={\sigma }^2,$ 则:
$$a{a}^t=u{\sigma }^{\prime }{u}^{-1}$$
满足 $a=q\sigma q^{-1}$ 特征向量定义
所以 aa^t 能实现特征分解, 又因为：
$$a{a}^t=\stackrel{u^{\prime \prime }{\sigma }^{\prime \prime }{v}^{\prime \prime t}}{svd}$$
所以:
$$\begin{array}{c}u=u^{\prime \prime }\\ {\sigma }^{\prime }={\sigma }^{\prime \prime }\\ u^{-1}=v^{\prime \prime }\Rightarrow u=v^{\prime \prime }\end{array}$$
因此：对 $a{a}^t$ 做svd，那么得到的u"列向量为特征向量 (对应a的u矩阵)， ${\sigma }^{\prime \prime }$ 为特征值对角阵
同理: 对 $a^{t}a$ 做svd，那么得到的u"列向量为特征向量 (对应a的v矩阵)， ${\sigma }^{\prime \prime }$ 为特征值对角矩阵

3.1 pca推导

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

根据2.1，先考虑一个正交基 $u^j,$ 数据点 $x^i$ 在该基底上的投影距离为 $x^i\cdot u^j,$ 所以所有的$m$个$n$维样本数据在该基底上投影的方差 $j^j$ 为：
$$j^j=\genfrac{}{}{0ex}{}{1}{m}\stackrel{m\sum }{i=1}{\left(x^i{u}^j-x^{\text{center}}{u}^j\right)}^2$$$$j^j=\genfrac{}{}{0ex}{}{1}{m}\stackrel{m\sum }{i=1}{\left(x^i{u}^j\right)}^2=\genfrac{}{}{0ex}{}{1}{m}\stackrel{m\sum }{i=1}\left(u^j{x}^i\cdot x^i{u}^j\right)=u^j\cdot \genfrac{}{}{0ex}{}{1}{m}\stackrel{m\sum }{i=1}\left(x^i{x}^i\right)\cdot u^j$$所以:$$j^j=u^j\cdot \genfrac{}{}{0ex}{}{1}{m}\left(x^1{x}^1{x}^2{x}^2\cdots x^m{x}^m\right)\cdot u^j=u^j\cdot \genfrac{}{}{0ex}{}{1}{m}\left(\left[\begin{array}{lll}{x}^1& \cdots & x^m\end{array}\right]\cdot \left[\begin{array}{c}{x}^1\\ ⋮\\ x^m\end{array}\right]\right)\cdot u^j==\genfrac{}{}{0ex}{}{1}{m}{u}^{j}x{x}^t{u}^j$$
假设 $s^{n\times n}=\genfrac{}{}{0ex}{}{1}{m}x{x}^t,$ 则 $:j^j=u^j\cdot s\cdot u^j,$ 根据pca目标, 我们需要求解 $j^j$ 最大时对应 的 $u^j$ 根据 2.2 中的拉格朗日算子 (求极值) 求解：
$$j^j=u^{j}s{u}^j$$$$\text{ s.t. }{u}^j{u}^j=1$$
则构造函数：
$$f\left(u^j\right)=u^{j}s{u}^j{\lambda }^j\left(1-u^j{u}^j\right)$$
求解 $\genfrac{}{}{0ex}{}{\partial f}{\partial u^j}=0,$ 得:
$$2s\cdot u^j-2{\lambda }^j\cdot u^j=0\Rightarrow s{u}^j={\lambda }^j{u}^j$$
结合2.4.1则：当 $u^j、{\lambda }^j$ 分别为s矩阵的特征向量、特征值时, $j^j$ 有极值, 把上述结果带回公式得$j^j$最大值:
$$j^{j^m}=u^j{\lambda }^j{u}^j={\lambda }^j$$
所以对于任意满足条件的正交基$\left\{u^1,u^2,\cdots ,u^k\right\}$ ，对应的数据在上面投影后的方差值为s矩阵的特征向量, 从而：
$$j^{\max }=\stackrel{k\sum }{j=1}{\lambda }^j,\lambda \text{ 人大到小排序 }$$
所以投影正交基为s的特征向量中的前k个最大特征值对应的特征向量。 接下来对s进行特征分解, 根据2.4.3特征向量和svd的关系结论, s的特征向量集合：
$$u=u\text{ of }\mathrm{svd}(s)=u\text{ of }\mathrm{svd}\left(\genfrac{}{}{0ex}{}{1}{m}x{x}^t\right)$$另外, 由于 $s=\genfrac{}{}{0ex}{}{1}{m}x{x}^t$ 由于x已0均值处理, 根据2.3 协方差矩阵定义：s为数据集x的协方差矩阵。 综上, 即可得到满足投影后数据距离最大的新的正交基 $\left\{u^1,u^2,\cdots ,u^k\right\}$ 因此降维后的数据为：
$$x^{ne{w}^{k\times m}}={\left[\begin{array}{c}{u}^1\\ u^2\\ ⋮\\ u^k\end{array}\right]}^{k\times n}\cdot x^{n\times m}$$

3.2 pca过程总结

pca流程如下：

初始化 $x,$ 使得所有样本之间的特征值均值为0, 同时应用feature scaling, 缩放到-0.5 $\sim 0.5$;

计算x的协方差矩阵s;

对s进行svd分解, u即我们要求的新坐标系集合, $\sigma$ 为特征值集合 (计算时特征值都会大于0, 且结果会从小到大 排列) ;

按照特征值从大到小排序, 要降低为k维, 那么取前k个特征值对应的特征向量, 就是新的k个坐标轴

把x映射到新的坐标系中, 完整降维操作;
根据之前的公式, 做pca投影后, 投影数据的方差：
$$va{r}^{x^{project}}=\stackrel{k\sum }{j=1}{j}^j=\stackrel{k\sum }{j=1}{\lambda }^j$$
又因为：数据从n维投影新的n维的坐标系, 方差不会发生改变 (向量的模长度相等且为1，可以用2d坐标系投影到45-135 度坐标系验证)，即：
$$va{r}^x=va{r}^{x^{\text{project }}}=\stackrel{n\sum }{j=1}{j}^j=\stackrel{n\sum }{j=1}{\lambda }^j$$
即：x的协方差矩阵的特征值和对应x的方差

总结

以上是ag凯发k8国际为你收集整理的详细推导pca算法（包括算法推导必备的知识）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。