PCA降维

维度劫难

当样本数据的维度较高时,可能会面临维度劫难问题。https://zhuanlan.zhihu.com/p/87389704。概括来说,当数据的维度越高,要找到最优解甚至达到稍低维度时模型的等同performance,所须要的数据越多,而且是成几何数增长的。
一种无效的解决办法是降维。

样本均值和样本协方差

给定样本数据$X=(x_1,x_2,\cdots,x_N)^T_{N\times P}$,其中$N$示意样本个数,$P$示意样本的维度,$x_i=(x_{i,1},\cdots,x_{i,P})^T$,$x_i \in \mathbb{R}^P,i=1,\cdots,N$。

样本均值为,
$$\begin{equation}\begin{aligned}\overline{x}_{P\times 1}&=\frac{1}{N}\sum_{i=1}^N x_i\\&=\frac{1}{N}\underbrace{(x_1,x_2,\cdots,x_N)}_{X^T}\begin{pmatrix}1 \\1\\\vdots\\1\end{pmatrix}_{N\times 1}\\&=\frac{1}{N}X^T\mathbf{1}_{N}\end{aligned}\tag{1}\end{equation}$$

样本协方差为
$$\begin{equation}\begin{aligned}S_{P\times P}&=\frac{1}{N}\sum_{i=1}^{N}(x_i -\overline{x})(x_i – \overline{x})^T\\&=\frac{1}{N}\underbrace{(x_1-\overline{x},x_2-\overline{x},\cdots,x_N-\overline{x})}_{X^T-\frac{1}{N}X^T\mathbf{1}_N\mathbf{1}_N^T}\begin{pmatrix}(x_1-\overline{x})^T \\(x_2-\overline{x})^T\\\vdots\\(x_N-\overline{x})^T\end{pmatrix}_{N\times P}\\&=\frac{1}{N}X^T\underbrace{(I_N-\frac{1}{N}\mathbf{1}_N\mathbf{1}_N^T)}_{H}\underbrace{(I_N-\frac{1}{N}\mathbf{1}_N\mathbf{1}_N^T)^T}_{H^T}X\\&=\frac{1}{N}X^THH^TX\\&=\frac{1}{N}X^THX\end{aligned}\tag{2}\end{equation}$$
其中,$H$称为centering matrix,易证实$H^T=H,H^n=H$。

原始特色空间的重构

PCA将为的次要思维是:对原始特色空间进行重构,具体做法是找到一组线性无关的基(主成分)代替原来的线性相关的基。

角度一:最大投影方差


以二维空间空间为例,将数据投影到$u_1$和$u_2$方向上,显然在$u_1$方向上的投影方差大于在$u_2$方向上的投影方差。如果样本的维度为$P$,心愿降维到$Q$维,则就是要找到投影方差最大的$Q$个方向(互相正交),也称为主成分。
假如由向量$\mathbf{a}$和方向向量$\mathbf{b}$,并且$\mathbf{b}$的模为1,即$\mathbf{b}^T\mathbf{b}=1$,则$\mathbf{a}$在$\mathbf{b}$上的投影为$\mathbf{a}^T\mathbf{b}$。
假如心愿找到方向$u$,使得投影方差最大,则最大化下式
$$\begin{equation}\begin{aligned}J&=\frac{1}{N}\sum_{i=1}^{N}((x_i-\overline{x})^Tu)^2\\&=\sum_{i=1}^N\frac{1}{N}u^T(x_i-\overline{x})(x_i-\overline{x})^Tu\\&=u^T(\sum_{i=1}^N\frac{1}{N}(x_i-\overline{x})(x_i-\overline{x})^T)u\\&=u^T Su\end{aligned}\tag{3}\end{equation}$$
最大化带束缚的指标函数
$$\begin{equation}\begin{cases}\hat{u}=\arg\max_{u}J \\ s.t.u^Tu=1\end{cases}\tag{4}\end{equation}$$
应用拉格朗日乘子法,
$$\begin{equation}\mathscr{L}(u,\lambda)=u^TSu+\lambda(1-u^Tu)\tag{5}\end{equation}$$
对$u$求导,令其等于0
$$\begin{equation}\frac{\partial \mathscr{L}}{\partial u}=2Su-\lambda\cdot 2u=0\tag{6}\end{equation}$$
即求u满足$Su=\lambda u$,能够看出$u$实际上就是样本协方差矩阵的特征向量,$\lambda$是其对应的特征值。将$Su=\lambda u$代入式(3),失去$J=u^T\lambda u=\lambda$,因而如果心愿将原始维度由$P$降到$Q$,及抉择前Q大的特征值对应的特征向量作为主成分,重构原始的数据。
对于原始数据$x_i$,能够用新失去的线性无关的基示意
$$\begin{equation}x_i=\sum_{k=1}^P((x_i-\overline{x})^Tu_k)u_k\tag{7}\end{equation}$$
假如主成分为$u1,\cdots,u_Q$,依据主成分重构数据,
$$\begin{equation}\hat{x}_i=\sum_{k=1}^Q((x_i-\overline{x})^Tu_k)u_k\tag{8}\end{equation}$$

角度二:最小重构间隔

应用PCA降维后失去的重构数据,要尽量与原始数据类似。
$$\begin{equation}\begin{aligned}J&=\frac{1}{N}\sum_{i=1}^N||x_i-\hat{x}_i||^{2}\\&=\frac{1}{N}\sum_{i=1}^N||\sum_{k=Q+1}^P((x_i-\overline{x})^Tu_k)u_k||^2\\&=\frac{1}{N}\sum_{i=1}^N\sum_{k=Q+1}^P((x_i-\overline{x})^Tu_k)^2\\&=\sum_{k=Q+1}^P\frac{1}{N }\sum_{i=1}^Nu_k^T(x_i-\overline{x})(x_i-\overline{x})^Tu_k\\&=\sum_{k=Q+1}^Pu_k^TSu_k\end{aligned}\tag{9}\end{equation}$$
又因为u是线性无关的,因而最小化式(9)能够别离对$u_k^TSu_k,u_k^Tu_k=1,k=Q+1,\cdots,P$进行最小化,因而就等价于找到最小的$P-Q+1$个特征值对应的特征向量,残余的Q个特征向量作为主成分。

PCA和SVD的关系

实对称矩阵的特征值合成

对于一个mxm的实对称矩阵$A$,能够合成为如下模式,

$$
\begin{equation}A = Q\Sigma Q^T=
Q\left[
\begin{matrix}
\lambda_1 & \cdots & \cdots & \cdots\\
\cdots & \lambda_2 & \cdots & \cdots\\
\cdots & \cdots & \ddots & \cdots\\
\cdots & \cdots & \cdots & \lambda_m\\
\end{matrix}
\right]_{m \times m}Q^T
\tag{10}
\end{equation}
$$

其中$Q$为规范正交阵,即有$QQ^T=I$,$I$为单位阵,$\lambda_i$为特征值,$q_i$是特色矩阵$Q$的列向量,为特征向量。

奇怪值合成定义

对于一个$m\times n$的实数矩阵$A$,能够合成为如下模式
$$\begin{equation}A=U\Sigma V^T=U\left[\begin{matrix}\sigma_1 & 0 & 0 & 0 & 0\\0 & \sigma_2 & 0 & 0 & 0\\0 & 0 & \ddots & 0 & 0\\0 & 0 & 0 & \ddots & 0\\\end{matrix}\right]_{m\times n}V^T\tag{11}\end{equation}$$

其中,$U$和$V$为单位正交阵,即$UU^T=I$,$VV^T=I$,$U$称为左奇怪矩阵,$V$称为右奇怪矩阵,$\Sigma$为对角矩阵,主对角线上的值称为奇怪值(主对角线上的元素非负,且不为0的个数取决于A的秩)。

对$HX$进行奇怪值合成(SVD),
$$\begin{equation}HX=U\Sigma V^T\tag{12}\end{equation}$$
样本协方差矩阵$S_{P\times P}=X^THX=X^TH^THX$,将式(12)代入,失去
$$\begin{equation}S_{P\times P}=(U\Sigma V^T)^T U\Sigma V^T=V\Sigma^2V^T\tag{13}\end{equation}$$
假如$T=HXX^TH^T$,则代入式(12),失去
$$\begin{equation}T_{N\times N}=U\Sigma V^T(U\Sigma V^T)^T =U\Sigma^2U^T\tag{14}\end{equation}$$
能够看出,式(11)和(12)是对$S$和$T$的矩阵合成,两者的特征值雷同。$V$的列向量为$S$的特征向量,$U$的列向量为$T$的特征向量。有上文可知样本协方差矩阵的特征向量形成主成分,且原始数据应用新的基示意的坐标为$H^TXV=U\Sigma V^TV=U\Sigma$,而$TU\Sigma=U\Sigma^2U^TU\Sigma=U\Sigma \Sigma^2$,显然$U\Sigma$由$T$的特征向量组成,联合式(12),坐标能够通过规范正交阵$U$缩放失去。

因而,$S$的特色合成间接失去准成分,而后计算$HXV$失去坐标;而$T$的特色合成则能够间接失去坐标。

参考

  1. https://www.bilibili.com/vide…
  2. https://www.cnblogs.com/endle…
  3. https://zhuanlan.zhihu.com/p/…

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据