主成分分析-PCA
1. 概要
主成分分析 (principal component analysis,PCA)
- 无监督学习方法
- 线性降维
- 数据压缩
2. 推导
2.1. 符号说明
- 数据 \(X\in \mathbb{R}^{n\times
p}\)，\(n\) 是样本个数，\(p\) 是特征个数
- 数据需要预处理：去中心化，每个样本减去均值即可
- 投影矩阵 \(W \in \mathbb{R}^{p\times k}\)，\(p\) 同上，\(k\) 是降维后特征个数
- 矩阵 \(A\) 的 \(F\) 范数 \[\|A\|_{F} = \sqrt{\sum_{i}\sum_j|a_{ij}|^2}=\sqrt{\mathrm{Tr}(A^TA)}\nonumber\]
2.2. 最小重构误差
重投影的数据和原始数据之间的误差最小，从而丢失的信息少。
数学描述： \[
\begin{array}{c}
\underset{W}{\min }\ \|X-XWW^T\|_{F}^{2}\\
\text{s.t.}\quad W^TW=I_k
\end{array}
\]
2.3. 最大可分性
数据经过投影矩阵变换到超平面上之后的数据尽可能分开，即投影后数据的方差尽可能的大，从而保留的信息多。
数学描述： \[
\begin{array}{c}
\underset{W}{\max }\ \|XW\|_{F}^{2}\\
\text{s.t.}\quad W^TW=I_k
\end{array}
\]
2.4. 最小重构和最大可分等价
\[\label{优化} \begin{aligned} \underset{W}{\min }\|X-XWW^T\|_{F}^{2} &=\underset{W}{\min } \ \mathrm{Tr}\left(\left(X-XWW^T\right)^T\left(X-XWW^T\right)\right)\\ &={\small \underset{W}{\min } \ \mathrm{Tr}\left(X^TX-X^TXWW^T-WW^TX^TX+WW^TX^TXWW^T \right)}\\ &=\underset{W}{\min } \ \mathrm{Tr}\left(-2W^TX^TXW +W^TX^TXWW^TW\right)\\ &=\underset{W}{\min } \ \mathrm{Tr}\left(-W^TX^TXW\right)\\ &=\underset{W}{\max } \ \mathrm{Tr}\left(W^TX^TXW\right)\\ &=\underset{W}{\max } \ \mathrm{Tr}\left(\left(XW\right)^TXW\right)\\ &=\underset{W}{\max } \|XW\|_{F}^{2} \end{aligned} \]
3. 求解
由 \(\eqref{优化}\) 可知，目标函数为 \[\label{目标函数} \begin{array}{c} \underset{W}{\min }\ -\mathrm{Tr}\left(W^TX^TXW\right)=\underset{W}{\max } \ \mathrm{Tr}\left(W^TX^TXW\right) \\ \text{s.t.}\quad W^TW=I_k \end{array} \]
可以用拉格朗日乘子法求解带约束的优化问题。
拉格朗日函数 \[ \mathcal{L}\left(W,\Lambda\right)=-\mathrm{Tr}\left(W^TX^TXW\right)+\mathrm{Tr}\left(\Lambda^T \left(W^TW-I_k\right)\right) \] 其中 \(\Lambda = diag(\lambda_1,\lambda_2,\dots,\lambda_{k})\in \mathbb{R}^{k\times k}\)
求解 \[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial W}&= -2X^TXW + 2W\Lambda=0\\ \frac{\partial \mathcal{L}}{\partial \Lambda}&=W^TW-I_k=0 \\ \end{aligned} \]
则有 \[\label{显式解} X^TXW=W\Lambda \]
将 \(W,\Lambda\) 展开 \[ \begin{aligned}\nonumber W &= [\boldsymbol{w}_1,\boldsymbol{w}_2,\dots,\boldsymbol{w}_k]\in\mathbb{R}^{p\times k} ,\quad \boldsymbol{w}_i\in\mathbb{R}^{p\times 1}\\ \Lambda &= diag(\lambda_1,\lambda_2,\dots,\lambda_{k})\in \mathbb{R}^{k\times k},\quad \lambda_i \in \mathbb{R} \end{aligned} \] 注意到 \[\label{约束} \boldsymbol{w}_i^T\boldsymbol{w}_i=1 ,\quad \boldsymbol{w}_i^T\boldsymbol{w}_j=0\ \left(i\neq j\right) \] 则有 \[\label{特征解} X^T X \boldsymbol{w}_i = \lambda_i \boldsymbol{w}_i \ ,\quad i=1,2,\dots,k \] 显然，此式为矩阵特征值和特征向量的定义式，其中 \(\lambda_i,w_i\) 分别表示矩阵 \(X^TX\) 的特征值和单位特征向量。
因为 \(X^TX\)
为实对称阵，而实对称阵不同特征值对应的特征向量之间是相互正交的，同一特征值的不同特征向量可以通过施密特正交化使其正交，所以通过
\(\eqref{特征解}\) 求的 \(\boldsymbol{w}_i\) 满足约束 \(\eqref{约束}\)。
根据拉格朗日乘子法的原理可知，此时求得的结果仅是最优解的必要条件，而且
\(X^TX\) 有 \(p\)
个相互正交的单位特征向量，所以还需要从这 \(p\) 个特征向量里找出 \(k\)
个能使得目标函数达到最优值的特征向量作为最优解。
将 \(\eqref{显式解}\) 带入目标函数 \(\eqref{目标函数}\) \[ \begin{aligned} \underset{W}{\max }\ \mathrm{Tr}\left(W^TX^TXW\right) &=\underset{W}{\max }\ \mathrm{Tr}\left(W^T W\Lambda\right)\\ &=\underset{W}{\max }\ \mathrm{Tr}\left(\Lambda\right)\\ &=\underset{W}{\max }\ \sum_{i=1}^{k}\lambda_i \end{aligned} \] 显然此时只需要令 \(\lambda_1,\lambda_2,\dots,\lambda_k\) 和 \(\boldsymbol{w}_1,\boldsymbol{w}_2,\dots,\boldsymbol{w}_k\) 分别为矩阵 \(X^TX\) 的前 \(k\) 大特征值及其对应的特征向量即可使目标函数达到最大值。
4. 算法流程
\[ \begin{array}{r l} \textbf{PCA 算法}\\ \hline \textbf{输入：} &\text{1. 样本数据 } X\in\mathbb{R}^{n\times p},n \text{ 是样本个数},p \text{ 是样本特征个数；}\\ &\text{2. 降维维度 }k \\ \textbf{过程：} &\text{1. 数据预处理，所有样本去中心化；}\\ &\text{2. 计算 }X^T X \text{，并对其特征分解；}\\ &\text{3. 取前 } k \text{ 大个特征值所对应的特征向量 } w_1,w_2,\dots,w_k \text{ ；}\\ \textbf{输出：} &\text{投影矩阵 } W=[w_1,w_2,\dots,w_k] \in \mathbb{R}^{p\times k}\\ \hline \end{array} \]
过程 2、3 也可以使用 SVD 分解，取前 \(k\) 个右奇异向量即可。
5. 方差贡献率
第 \(i\) 个主成分的方差贡献率 \[ \eta_i = \frac{\lambda_i}{\sum_{j=1}^{p}\lambda_j} \]
前 \(k\) 个主成分的方差贡献率 \[ \eta = \frac{\sum_{i=1}^{k}\lambda_i}{\sum_{j=1}^{p}\lambda_j} \]