PCA 主成分分析

1. 特征值分解

1.1 特征值分解的前提

矩阵是方阵
矩阵是 可对角化的，即通过相似变化转化为对角矩阵。（相似变换 不会改变矩阵的特征值和特征向量 ）
矩阵的特征向量 线性无关，保证了特征值分解的 唯一性。

1.2 特征值分解

给定一个矩阵 \(A \in \mathbb{R}^{n \times n}\) , 存在非零向量 \(v\) 和系数 \(\lambda\) 使得：

\[Av_i = \lambda_i v_i \]

则称 \(\lambda_i\) 是矩阵 \(A\) 的一个特征值，\(v_i\) 是特征值 \(\lambda\) 对应一个的特征向量。

特征向量具有某种不变性：矩阵 \(A\) 乘特征向量，不会改变特征向量的方向。特征向量同样是线性变换的不变轴，所有输入向量沿着这条轴压缩或延伸。一般来说几阶方阵就有几个特征向量，\(n\) 阶方阵有 \(n\) 个特征向量，每一个特征向量表征一个维度上的线性变换方向。

可以将 \(A\) 的 特征值 和 特征向量 向量化表示为：

特征值

\[\Lambda = \begin{bmatrix} \lambda_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \lambda_n \end{bmatrix} \]

特征向量

\[V = [v_1, v_2, \cdots, v_n] \]

由此：

\[\begin{split} AV & = A[v_1, v_2, \cdots, v_n] \\\\ & = [\lambda_1v_1, \lambda_2v_2, \cdots, \lambda_nv_n] \\\\ & = [v_1, v_2, \cdots, v_n]\Lambda \\\\ & = V\Lambda \end{split} \]

由于矩阵 \(V\) 的 \(n\) 个特征向量线性无关，所以 \(V\) 可逆，由此可以推导出对角化以及特征值分解公式：

\[\begin{split} & V^{-1}AV = \Lambda \\\\ & A = V\Lambda V^{-1} \end{split} \]

此时，可以看成矩阵 \(A\) 被分解了。

一般会将 \(V\) 进行 标准化，满足 \(||v_i||_2 = 1\)，或者 \(v_i^Tv_i = 1\)，此时 \(V\) 的 \(n\) 个特征向量为 标准正交基，满足 \(V^TV = I\)，由此可得 \(V^T = V^{-1}\)，此时 \(V\) 为 酉矩阵，故此时可以将特征分解表达式写为：

\[A = V\Lambda V^T \]

1.3 计算方法

\[Av_i = \lambda_i v_i \rightarrow (\lambda_i I - A)v_i = 0 \]

根据线性方程组理论，只有 \(\text{det}(\lambda_i I - A) = 0\) （det表示行列式），方程才有 非零解。

计算出所有 \(\lambda\) 取值后，再代回 \((\lambda_i I - A)v_i = 0\)，求出最终的 特征向量 \(v_i\)。

2. SVD分解

2.1 奇异值分解

奇异值分解(Singular Value Decomposition) 并 不要求矩阵为方阵。

假设有 \(A \in \mathbb{R}^{m \times n}\)，此时定义矩阵 \(A\) 的 \(\text{SVD}\) 为：

\[A = U\Sigma V^T \]

其中 \(U \in \mathbb{R}^{m \times m}, \Sigma \in \mathbb{R}^{m \times n}, V \in \mathbb{R}^{n \times n}\)。

\(\Sigma\) 除了对角线以外元素都是 0，主对角线上每个元素称为 奇异值。并且 \(U\) 和 \(V\) 都是 酉矩阵，即满足 \(U^TU = I, V^TV = I\)。

2.2 计算方法

求解 \(V\)

构造 \(n \times n\) 的方阵 \(A^TA\)，进行 特征值分解：

\[(A^TA)v_i = \lambda_i v_i \]
由此可以得到 \(A^TA\) 对应的 \(n\) 个特征向量 \(v_i\)，从而得到特征向量矩阵 \(V\)，以及对应的特征值矩阵 \(\Lambda\)。一般称其为 \(A\) 的 右奇异矩阵。
求解 \(\Sigma\)

\[\begin{split} & 由 A = U\Sigma V^T \\\\ & A^T = V\Sigma U^T \\\\ & 由此可得 \; A^TA = V\Sigma U^T U\Sigma V^T \\\\ & 由 \; U^TU = I \\\\ & 得 \; A^TA = V\Sigma^2 V^T \end{split} \]
显然，此时可以发现矩阵 \(A^TA\) 的特征向量构成矩阵 \(V\)，\(\Sigma^2\) 明显是等于 \(\Lambda\) 的，那么显然 \(A^TA\) 的 特征值 与 \(A\) 的 奇异值 满足如下关系：

\[\sigma_i = \sqrt{\lambda_i} \]
求解 \(U\)

在上面两个部分的求解中，得到了由 \(v_i\) 构成的特征向量 \(V\) 和奇异值 \(\sigma_i\) 。

\[\begin{split} & 由 A = U\Sigma V^T \\\\ & AV = U\Sigma V^TV \\\\ & 由于 V^TV = I \\\\ & 可以得出 \; AV = U\Sigma \\\\ & 由此可得 \; Av_i = \sigma_i u_i \\\\ & 故 \; u_i = \frac{Av_i}{\sigma_i} \end{split} \]
从而得到特征向量矩阵 \(U\)。称其为 \(A\) 的 左奇异矩阵。

3. PCA

3.1 特征值分解求解PCA

假设有样本数据集 \(X = \{x_1, x_2, \cdots, x_n\}, X \in \mathbb{R}^{m \times n}\)

去中心化，每一特征 减去各自的平均值
计算 协方差矩阵 \(\frac{1}{n - 1}X^TX\)，协方差矩阵可以满足特征值分解的前提条件（这里乘 \(\frac{1}{n - 1}\) 或者 \(\frac{1}{n}\) 与否不影响最终结果）
特征值分解求出 协方差矩阵 \(\frac{1}{n - 1}X^TX\) 的 特征值 和 特征向量
特征值排序，选取前 \(k\) 大的特征向量，组成特征向量矩阵 \(P\)
将数据转换到 \(k\) 个特征向量构建的空间中，\(Y_k = XV_k\)，得到压缩后的数据。注意 \(0 < k < \text{rank}(A)\)

3.2 SVD分解求解PCA

假设有样本数据集 \(X = \{x_1, x_2, \cdots, x_n\}, X \in \mathbb{R}^{m \times n}\)

去中心化，每一特征 减去各自的平均值
使用 奇异值分解 (SVD) 求出 右奇异矩阵 \(V\) 和 奇异值对角矩阵 \(\Sigma\)，进而推出 左奇异矩阵 \(U\)
选取前 \(k\) 大的奇异值，构成 \(\Sigma_k\)
将数据转换到 \(k\) 个奇异值构建的空间中，\(Y_k = U\Sigma_k\)，得到压缩后的数据。