数据降维

PCA(Principal components analysis)

设输入数据\(X=\begin{bmatrix}x_1&\cdots&x_m\end{bmatrix}\in R^{n\times m},x_i(i\in[1,m])\in R^{m\times 1}\)，即\(m\)组数据，每组数据\(n\)个特征，经过矩阵\(P\in R^{k\times n}\)，特征降到了\(k\)维： \[ Y=PX \in R^{k\times m} \] 要让降维后数据更有效，要让其方差最大化（样本最分散）、协方差最小化（样本相关性最小）

求方差，为了方便计算，这里将数据预处理，减去均值\(\mu\)，即： \[ x_{ij}=x_{ij}-\mu_i=x_i-\frac{1}{m}\sum\limits_{j=1}^{m}x_{ij}~~\text{for each }x_i \in X \]

\[ var(x_i)=\frac{1}{m}\sum\limits_{j=1}^{m}x_{ij}^2 \]

求协方差： \[ cov(a,b)=\frac{1}{m}\sum\limits_{i=1}^{m}a_i b_i \] 若只有\(a、b\)两个特征的数据\(m\)组，即\(X=\begin{bmatrix}a_1&\cdots &a_m\\b_1&\cdots &b_m \end{bmatrix}\in R^{2\times m}\)，记矩阵\(C\)(称协方差矩阵)为： \[ C=\frac{1}{m}XX^{\top}=\frac{1}{m}\begin{bmatrix} \sum\limits_{i=1}^{m}a_i^2&\sum\limits_{i=1}^{m}a_i b_i\\ \sum\limits_{i=1}^{m}a_i b_i&\sum\limits_{i=1}^{m}b_i^2 \end{bmatrix} =\begin{bmatrix} var(a)&cov(a,b)\\cov(a,b)&var(b) \end{bmatrix} \] \(C\)为对称矩阵，对角线为方差，其它位置为协方差

目标为： \[ max[var(a)]\and max[var(b)]\and cov(a,b)=0 \] 这与让\(M\)对角化等价，通常会让\(M\)对角化后的元素按大小顺序从上到下排列

记\(X、Y\)的协方差矩阵为\(C_X、C_Y\)，有： \[ C_Y=\frac{1}{n}Y Y^{\top}=\frac{1}{n}(PX)(PX)^{\top} =\frac{1}{n}PXX^{\top}P^{\top} =P(\frac{1}{n}XX^{\top})P^{\top} =PC_XP^{\top} \] 需要求出\(P\)使\(C_X\)对角化，且对角元素从上到下按从大到小排列，用\(P\)的前\(k\)行为基组成的矩阵能将初始数据集特征从\(n\)维降到\(k\)

要方差最大化，即： \[ max[tr(C_Y)]=max[tr(PC_XP^{\top})] \] 这里： \[ PP^{\top}=E\in R^{k\times k} \] 由拉格朗日法求极值： \[ F(P)=tr(PC_XP^{\top})+\lambda (PP^{\top}-E) \] 令\(\frac{\partial F}{\partial P}=0\)，由矩阵的迹求导公式，\(\frac{\partial (tr(AXBX^{\top}))}{\partial X}=AXB+A^{\top}XB^{\top}\)，令\(A=E\)，有： \[ \frac{\partial (tr(PC_XP^{\top}))}{\partial P}=PC_X+PC_X^{\top} \] 注意到\(C_X\)为对称矩阵，因此： \[ \frac{\partial (tr(PC_XP^{\top}))}{\partial P}=2PC_X \]

由于：\(\frac{\partial (X^{\top})}{\partial X}=E，\frac{\partial AX}{\partial (X^{\top})}=A\) \[ \frac{\partial (\lambda PP^{\top}))}{\partial P}=2\lambda P \]

因此： \[ 2PC_X+2\lambda P=0 \]

转化一下，有： \[ (PC_X)^{\top}+(\lambda P)^{\top}=0 \] 化简有： \[ C_X P^{\top}=-\lambda P^{\top} \] 因此要对\(C_X\)进行特征分解，对其特征值进行排序，取\(P\)的前\(\acute{k}\le k\)行组成的矩阵\(\acute{P}\)，则有： \[ \acute{Y}=\acute{P}X \in R^{\acute{k} \times m} \] 将数据特征从\(n\)维降到了\(\acute{k}\)维

SVD(Singular value decomposition)

对方阵\(A\in R^{n\times n}\)： \[ Aw_i=\lambda_i w_i \] 其特征值\(\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n\)，对应特征向量\(w_1、w_2\cdots 、w_n\)，特征分解表示\(A\)： \[ A=W\Sigma W^{-1} \] 这里\(W=\begin{bmatrix}w_1&w_2&\cdots&w_n\end{bmatrix}\in R^{n\times n}\)，\(\Sigma=diag[\lambda_1,\lambda_2,\cdots,\lambda_n]\)，将\(n\)个特征向量标准化： \[ ||w_i||_2=w_i^{\top}w_i=1\text{ for each }w_i \in W \] 此时\(n\)个特征向量为标准正交基： \[ W^{\top}W=E\Longleftrightarrow W^{-1}=W^{\top} \] 因此\(A\)的分解为： \[ A=W\Sigma W^{\top} \] 对于正常矩阵\(A\in R^{m\times n}\)，分解表示为： \[ A=U\Sigma V^{\top} \] \(U\in R^{m\times m}、\Sigma \in R^{m\times n}、V\in R^{n\times n}\)满足： \(U^{\top}U=E,V^{\top}V=E\)

\(\Sigma\)主对角线元素为奇异值，主对角线外元素为0。对矩阵\(M\in R^{m\times n}\)主对角线元素为： \[ \{m_{ii}\}\text{ for i }\in[1,\mathop{min}(m,n)] \] 由于\(AA^{\top}\in R^{m\times m}\)为方阵，有： \[ (AA^{\top})u_i=\lambda_i u_i \] 即\(U=\begin{bmatrix}u_1&u_2&\cdots&u_m\end{bmatrix}\)

同理\(A^{\top}A\in R^{n\times n}\)为方阵，有： \[ (A^{\top}A)v_i=\lambda_i v_i \] 即\(U=V=\begin{bmatrix}v_1&v_2&\cdots&v_n\end{bmatrix}\)

简单证明： \[ A=U\Sigma V^{\top}\Longleftrightarrow A^{\top}=V\Sigma^{\top}U^{\top} \]

\[ AA^{\top}=U\Sigma (V^{\top}V) \Sigma^{\top}U^{\top} =U(\Sigma \Sigma^{\top})U^{\top} \]

因此\(AA^{\top}\)的所有特征向量标准化后的组合即为\(U\)

同理\(A^{\top} A\)的所有特征向量标准化后的组合即为\(V\)

注意到特征值\(\lambda_i\)与奇异值\(\sigma_i\)满足关系： \[ \sigma_i=\sqrt{\lambda_i} \] 因此可以计算\(AA^{\top}(m\le n)\)或\(A^{\top}A(m\ge n)\) 的特征值再开根号来计算奇异值

可以用最大的\(k\)个的奇异值和对应的左右奇异矩阵来近似描述原矩阵（降维）： \[ A_{m\times n}=U_{m\times m}\Sigma_{m\times n}V_{n\times n}^{\top} \approx U_{m\times k}\Sigma_{k\times k}V_{k\times n}^{\top} \]