基本思想

主成分分析(Principal Components Analysis,PCA)指的是利用正交变换来对可能相关的数据进行线性变换,从而投影为线性不相关的数据,这些不相关变量(特征)称为 主成分(Principal Components)。通过保留包含信息最多的若干个特征,我们可以实现对数据的降维。

PCA 有以下特点:

  • (+) 降维,缓解维度灾难。
  • (+) 特征独立,有利于特征筛选。
  • (+) 降噪,噪声的方差(包含的信息量)往往较小。
  • (-) 丢失了一些特征,这些特征只是包含的信息少,并不意味着它对任务的帮助小。

理论推导

不能只知其然不知其所以然。本节我们做一步步推导,跟着问题寻找答案。

(1) 方差

对于变量(或特征)$x$,我们用 方差 表示数据的离散程度,方差越大,该特征所蕴含的信息就越多。方差的计算如下: $$ \begin{aligned} \operatorname{Var}(x) &= \frac{1}{m} \sum_{i=1}^m (x_i - \mu)^2 \end{aligned} $$ 为了方便处理,我们对所有特征都进行 0 均值化,因此上式转化为: $$ \begin{aligned} \operatorname{Var}(x) &= \frac{1}{m} \sum_{i=1}^m x_i^2 \end{aligned} $$ 当前目标:寻找一个一维基,使得原始数据变换为这个基上的坐标表示后,方差值最大。

(2) 协方差

事实上,我们不仅要考虑单个特征,我们还要考虑选取的特征之间的关系。如果两个特征的相关性很高,那么即使它们具有较大方差,也是比较无用的特征。

因此,我们在选取特征的时候,不仅要考虑单个特征的方差,还要考虑它与其他特征的相关性,而这相关性,则可以用两两维度之间的 协方差 来表示。协方差越小,维度的相关性越低,它们重叠的信息就越少,当两个变量 $x$、$y$ 的协方差为 0 时,我们认为这两个变量线性无关。协方差的计算公式如下: $$ \begin{aligned} \operatorname{Cov}(x,y) &= \frac{1}{m} \sum_{i=1}^m (x_i - \mu_x) (y_i - \mu_y) \end{aligned} $$

由于我们对所有特征都进行了 0 均值化,因此上式转化为: $$ \begin{aligned} \operatorname{Cov}(x,y) &= \frac{1}{m} \sum_{i=1}^m x_iy_i \end{aligned} $$ 最新目标:选择 $k$ 个正交基,使得原始数据变换到该空间之后,变量两两之间协方差为 0,自身方差尽可能大(在正交的约束下,取最大的 $k$ 个方差)。

(3) 协方差矩阵

上面的目标还是有点难搞,既要考虑方差又要考虑协方差,能不能将他们统一在一起。

因为已经 0 均值化过,因此无论方差的计算还是协方差的计算其实都简化为了两个特征向量的点积,所以我们很自然地想到将这些特征向量组成矩阵,再通过矩阵乘法将他们统一。

具体来说,假设我们有 $n$ 维特征 $x_1, x_2, \cdots, x_n$,那么按行组合之后可以得到 $n \times m$ 维矩阵 $\mathbf{X}$: $$ \mathbf{X} = \left[\begin{matrix} x_1 &x_2 &\cdots &x_n \end{matrix}\right]^\mathrm{T} $$

我们计算 $\mathbf{X}$ 的协方差矩阵 $\mathbf{C}$(维度 $n \times n$): $$ \begin{aligned} \mathbf{C} &= \frac{1}{m} \mathbf{X}\mathbf{X}^\mathrm{T} \\ &= \left[\begin{matrix} x_1\cdot x_1 &x_1\cdot x_2 &\cdots &x_1\cdot x_n \\ x_2\cdot x_1 &x_2\cdot x_2 &\cdots &x_2\cdot x_n \\ \vdots &\vdots &\ddots &\vdots \\ x_n\cdot x_1 &x_n\cdot x_2 &\cdots &x_n\cdot x_n \\ \end{matrix}\right] \\ &= \left[\begin{matrix} \operatorname{Var}(x_1) &\operatorname{Cov}(x_1,x_2) &\cdots &\operatorname{Cov}(x_1,x_n) \\ \operatorname{Cov}(x_2,x_1) &\operatorname{Var}(x_2) &\cdots &\operatorname{Cov}(x_2,x_n) \\ \vdots &\vdots &\ddots &\vdots \\ \operatorname{Cov}(x_n,x_1) &\operatorname{Cov}(x_n,x_2) &\cdots &\operatorname{Var}(x_n) \\ \end{matrix}\right] \\ \end{aligned} $$

我们可以看到,协方差矩阵 $\mathbf{C}$ 是一个对称矩阵,对角线元素为每个特征的方差,而其他元素则为两两特征之间的协方差。

最新目标:最小化协方差矩阵 $\mathbf{C}$ 的非对角线元素(协方差),将对角线元素(方差)从大到小排列,选取最大的 $k$ 个值。

(4) 矩阵对角化

上面这个目标不就是线性代数里面的 矩阵对角化 吗?OK,那下一步我们就应该要找怎么对原始数据 $\mathbf{X}$ 进行映射,从而允许我们对映射后的特征的协方差矩阵进行矩阵对角化。

前面提到 $\mathbf{X}\in\mathbb{R}^{n\times m}$ 是原始数据,假设我们要做的映射 $\mathbf{P}\in\mathbb{R}^{k\times n}$ 是一组基按行组成的矩阵,那么变换之后的数据为 $\mathbf{Y}=\mathbf{P}\mathbf{X}\in\mathbb{R}^{k\times m}$,那么 $\mathbf{Y}$ 的协方差矩阵 $\mathbf{D}$ 计算为: $$ \begin{aligned} \mathbf{D} &= \frac{1}{m} \mathbf{Y} \mathbf{Y}^\mathrm{T} \\ &= \frac{1}{m} (\mathbf{P}\mathbf{X}) (\mathbf{P}\mathbf{X})^\mathrm{T} \\ &= \frac{1}{m} \mathbf{P} \mathbf{X} \mathbf{X}^\mathrm{T} \mathbf{P}^\mathrm{T} \\ &= \mathbf{P} (\frac{1}{m} \mathbf{X} \mathbf{X}^\mathrm{T}) \mathbf{P}^\mathrm{T} \\ &= \mathbf{P} \mathbf{C} \mathbf{P}^\mathrm{T} \\ \end{aligned} $$ 注意,$\mathbf{C}$ 是原数据特征的协方差矩阵,$\mathbf{P}$ 是从原数据特征到新数据特征的映射矩阵,$\mathbf{D}$ 是映射后的特征的协方差矩阵。

最新目标:寻找一个矩阵 $\mathbf{P}$,使得 $\mathbf{P}\mathbf{C}\mathbf{P}^\mathrm{T}$ 是一个对角矩阵,并且主对角线上元素从大到小排列,此时的 $\mathbf{P}$ 就是我们找到的特征映射。

完整步骤

假设我们有 $m$ 条 $n$ 维数据。

  1. 将原始数据按列组成 $n$ 行 $m$ 列矩阵 $\mathbf{X}$(将特征放在第一维是为了方便最后左乘降维矩阵);
  2. 将 $\mathbf{X}$ 的每一维(即每一行)进行零均值化;
  3. 求出协方差矩阵 $\mathbf{C}=\frac{1}{m}\mathbf{X}\mathbf{X}^\mathrm{T}$;
  4. 求出协方差矩阵的特征值 $[\begin{matrix}\lambda_1&\lambda_2&\cdots&\lambda_n\end{matrix}]$ 及对应的特征向量 $[\begin{matrix}\vec{v_1}&\vec{v_2}&\cdots&\vec{v_n}\end{matrix}]$;
  5. 将特征向量按对应特征值大小从上到下按行排列成矩阵,取前 $k$ 行组成矩阵 $\mathbf{P}$,其维度为 $k \times n$;
  6. $\mathbf{Y} = \mathbf{P} \mathbf{X}$ 即为降维到 $k$ 维后的数据。

EVD or SVD

调用 Demo

Python

1

Matlab

1

参考


  1. preprocess
    • mean normalization
    • feature scaling
    • ...
  2. compute covariance matrix
    • $\Sigma=\frac{1}{m}A^TA\in R^{n\times n}$
  3. SVD
    • $[U,S,V]=\operatorname{svd}(\Sigma)$
    • $U\in R^{m\times m}$, $S\in R^{m\times n}$, $V\in R^{n\times n}$
  4. select the first $k$ columns of matrix $U$
    • $U_{reduce}=U(:,1:k)$
    • $U_{reduce}\in R^{m\times k}$
  5. how to choose $k$?
    • $\frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^n S_{ii}} \ge 0.85$, here $0.85$ means retaining 85% variance
  6. result
    • $z=(U_{reduce})^Tx\in R^{k\times 1}$

Pseudo Code

1
2
3
4
Sigma = X' * X / m;
[U, S, V] = svd(Sigma);
U_reduce = U(:, 1:k);
Z = X * U_reduce

Steps

From n-dimensions to k-dimensions:

  1. data $$ X \in R^{m\times n} $$

  2. preprocess

    • feature scaling
    • mean normalization
  3. compute covariance matrix $$ \Sigma = \frac{1}{m}X^TX \in R^{n\times n} $$

  4. compute eigenvectors {%raw%} $$\begin{align} [U, S, V] &= \operatorname{svd}(\Sigma) \\ U, S &\in R^{n\times n} \end{align}$$ {%endraw%} PS: $S$ is a diagonal matrix like {%raw%}$ \left[\begin{array}\ 521.34 &&&&\ & 489.17 &&&\ && 463.85 &&\ &&& \ddots & \ &&&& 0.24 \ \end{array}\right] ${%endraw%}, which denotes the principal component ratio of $n$ columns (vectors) of matrix $U$

  5. select the first $k$ columns of matrix $U$ {%raw%} $$\begin{align} U_{reduce} &= U(:, 1:k) \\ U_{reduce} &\in R^{n\times k} \end{align}$$ {%endraw%}

  6. How to choose $k$? Choose the smallest value which satisfies {%raw%}$$\frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^n S_{ii}} \ge 0.85$${%endraw%} Here $0.85$ means retaining 85% variance.

  7. result $$z = (U_{reduce})^T x \in R^{k\times 1}$$