主成分分析-principal component analysis

问题描述

某些高维空间的数据可以嵌入或者近似嵌入在低维空间中。

例子:$\mathbb{R}^2$空间的数据点$\{(1,1),(2,2),…,(5,5)\}$可以看做$\mathbb{R}^1$空间的点$\{1,2,..,5\}$

我们的目的是将一些数据点$\{x_1,x_2,…,x_N\} , x_i \in \mathbb{R}^p$ 变换成$\{y_1,y_2,…,y_N\} , x_i \in \mathbb{R}^q$,其中$q \le p$, 另外要求$\{y_1,y_2,…,y_N\}$的样本协方差矩阵是对角阵。

随机变量才有方差或者协方差,在下面的推导中,我们

  • 将$\{x_1, x_2, …, x_N\}, x_i \in \mathbb{R}^p$ 理解为来自随机变量$x$的样本
  • 将$\{y_1, y_2, …, y_N\}, y_i \in \mathbb{R}^q$ 理解为来自随机变量$y$的样本

$x$的(总体)均值和(总体)协方差分别用$Ex$和$Var(x)=cov(x,x)$表示。

$x$的样本均值和样本协方差分别用$\bar x =\frac{1}{N}\sum_{n=1}^N x_n$和$\frac{1}{N}\sum_{n=1}^N(x_n-\bar x)(x_n-\bar x)^T$表示。


问题分析

高维空间的点,可以通过投影得到低维空间的点。

考虑投影到一维空间$\{ ku_1|k \in \mathbb{R},u_1 \in \mathbb{R}^p \}$,我们希望投影数据能包含原始数据更多的信息。

信息的度量就等于不确定性的多少, 具体可以用熵(entropy)来量化, 熵越大表示信息越多智能时代

假设投影数据服从正太分布 $N(\mu,\sigma^2)$, 其熵(entropy)为 $\frac{1}{2} \ln(2\pi e \sigma^2)$.

从而,分布的方差$\sigma^2$越大,熵也就越大,包含的信息也就越多。

所以,我们需要选择投影数据方差最大的方向$u_1$。

另一种理解方式是最小化投影误差(projection error minimization)PRML.


计算过程

先分析最简单的情形: 把数据投影到一维空间,然后将一维情形得到的结果推广到高维空间。

投影到一维: $\mathbb{R}^p \Rightarrow\mathbb{R}^1$

因为投影数据的方差只与$u_1$的方向有关,而与其大小无关。

所以为了便于计算,我们限制$u_1$为单位向量,即$u_1^T u_1=1$。

  1. 计算$\{x_1,x_2,…,x_N\} $投影在$u_1$上的投影$\{y_1,y_2,…,y_N\} $。
    $x_n$在$u_1$上投影为:

  2. 计算投影数据 $\{y_1,y_2,…,y_N\}$的方差:

    上式中$S$是$\{x_1,x_2,…,x_N\} $的样本协方差矩阵。

  3. 最大化方差,求解$u_1$

    目标函数:

    这是一个有限制条件的优化问题,可以通过拉格朗日乘子法将其转化为无约束优化问题:

    $F(u_1)$取到最大值满足的条件:

    从而,解$u_1$就是$S$的最大特征值$\lambda_1$对应的特征向量。此时,$F(u_1)=\lambda_1$.

$u_1​$称为第一主成分(first principal component), 记为pc1。得到的一维空间 $\mathbb{R}^1 = \{ ku_1|k \in \mathbb{R},u_1 \in \mathbb{R}^p \}​$称为第一主子空间(first principal subspace)。

结果:

  • 投影矩阵为$u_1^T$,投影数据为 $y_i = u_1^Tx_i \in \mathbb{R}^1 \qquad i =1,2,…,N$;

  • $y = u_1^Tx \in \mathbb{R}^1$,其方差为 $\lambda_1$。

投影到多维: $\mathbb{R}^p\Rightarrow\mathbb{R}^q(2\le q\le p)$

当$p=1$时, 我们已经说明了保持方差最大的投影方向是$S$的最大特征值$\lambda_1$对应特征向量$u_1$的方向。

当$p=M$时, 假设保持方差最大的投影方向依次是$S$的前$M$个特征值$\lambda_1 \ge \lambda_2 \ge …\ge\lambda_M$对应的特征向量$u_1,u_2,…,u_M$的方向。

  • $u_1,u_2,…,u_M$分别是 第一主成分(first principal component), …,第M个主成分(M-th principal component). 记为pc1,pc2,…,pcM.

  • $u_1,u_2,…,u_M$构成的空间$\mathbb{R}^M = \{ k_1u_1+…+k_M u_M|k_i \in \mathbb{R},u_i \in \mathbb{R}^p\}$称为M维主子空间(M dimensional principal subspace)。

现证明$p=M+1$时,结论仍然成立。

此时,优化的目标函数为:

约束条件($u_{M+1}^T$为单位向量且与前$M$个主成分正交)为:

同样,这是一个有限制条件的优化问题,可以通过拉格朗日乘子法将其转化为无约束优化问题:

$F(u_{M+1})$取到最大值满足的条件:

在公式(1)上乘以$u_{j}^T, j \in \{1,2,…,M\}$, 得到:

  • $u_{j}^Tu_{M+1}=0$.
  • $j=i$时,$ u_{j}^Tu_i = 1 $;否则$ u_{j}^Tu_i = 0$.
  • $S$是样本协方差矩阵,是对称的。$S^T=S$.
  • $u_{j}^TSu_{M+1}$ 是一个标量,所以$u_{j}^TSu_{M+1}=(u_{j}^TSu_{M+1})^T=u_{M+1}^TSu_j =\lambda_i u_{M+1}^T u_j$.

将$\eta_j=0$代入公式(1),得到$Su_{M+1}=\lambda u_{M+1}$.

因为前$M$个最大的特征值已经使用过,所以只能选择第$M+1$大的特征值$\lambda_{M+1}$及其对于的特征向量$u_{M+1}$.

从而第$M+1$个主成分为$u_{M+1}$。

$M+1$维主子空间($M+1$ dimensional principal subspace) 为.

上面使用数学归纳法证明了数据$\{x_1,x_2,…,x_N\} , x_i \in \mathbb{R}^p$的$q$维主子空间($q$ dimensional principal subspace), 由数据的样本协方差矩阵$S=\frac{1}{N}\sum_{n=1}^N (x_n - \bar{x})(x_n - \bar{x})^T$的前$q$个依次减小的最大特征值$\lambda_1 \ge … \ge \lambda_q$对应的特征向量$u_1,…,u_q$构成。

结果

  • 变换矩阵为$U^T$, 投影数据为:
  • $y=U^Tx$, $y$的协方差矩阵为:


一句话描述

对随机变量$x \in \mathbb{R}^p $, 寻找一个线性变换$y_{q \times 1}=W_{q\times p}x_{p \times 1} \in \mathbb{R}^q$, 使得变换后随机变量$y$的协方差矩阵是对角阵。

具体:设$\{x_1,x_2,…,x_N\} $为来自随机变量总体$x$的样本,其样本协方差矩阵为$S=\frac{1}{N}\sum_{n=1}^N (x_n - \bar{x})(x_n - \bar{x})^T$

$S$的特征值和特征向量关系:$S_{p\times p}U_{p \times q}=U_{p \times q}\Lambda_{q \times q}$

其中

  • $\Lambda$的对角元素为$S$的特征值,$\Lambda=\mathrm{diag}[\lambda_1..,\lambda_p],\lambda_1\ge \lambda_2\ge… \lambda_p $;
  • $U$的相应列对应于$S$的特征向量, 分别称为第一、第二…第$p$个主成分。

此时,$W=U^T$. 即, $y=U^Tx$.


可视化

下面两个例子主要用来展示PCA降维的作用。

CS229: Machine Learning. Lecture 15-Principal Component Analysis.

分析了PCA的几个主要作用:

  1. 压缩(compression)-使用投影后的低维数据替代原始数据,用来聚类等;
  2. 降维(dimension reduce)-使用投影后的低维数据作为机器学习模型(线性回归,逻辑回归)的输入, 减少模型参数的个数,从而降低模型的复杂度,降低模型的方差(variance), 达到避免过拟合(overfitting)的目的;
  3. 去噪(noise reduction)-大特征值对应的主成分子空间表示主要的特征,而小特征值对应的主成分子空间表示次要的特征(在某些情形下, 就是噪音)。所以保留高特征值对应的主子空间的特征就达到了去除噪音的目的。

三维空间数据

:原始数据 $\qquad \qquad \quad \quad$ :原始数据在第一主成分pc1和第二主成分pc2的投影

右上:原始数据取值范围 $\qquad $ 右下:投影数据取值范围

pca3d

image comes from http://setosa.io/ev/principal-component-analysis/

可从得到的结论:

  • PCA可以理解为坐标系的变换;

  • 原始数据在各个主成分投影的方差:pc1最大,pc2次之,pc3最小。

MNIST数据集

MNIST是$28\times28$的图片,转化为向量后,每一张图片是空间$\mathbb{R}^{784}$上的点。

对该数据集做PCA,将其投影到二维主成分空间,结果如下图:

`

​ image comes from https://projector.tensorflow.org/

从图可以看出:

  • 不同的数字还是有聚集效果,比如1集中在左边,0集中在右边;

  • 不标记颜色和数字的话,所有数字集中在一起。

    使用t-SNE(一种非线性降维方法)基本能把这些数字分开t-SNE




智能时代. 《智能时代》, 吴军. 第三章: 思维的革命, 小节: 熵,一种新的世界观。
PRML. Pattern Recognition and Machine Learning, Bishop.
t-SNE. Visualizing High-Dimensional Data Using t-SNE, 2008. First author’s blog: https://lvdmaaten.github.io/tsne/