降维：主成分分析

简介

降维的作用通常是为了数据压缩和可视化。数据压缩不仅可以节省存储空间，而且可以加速机器学习算法。高维数据需要约减到3维或2维空间，以便观测其特性。

PCA

本节的主要内容来自Andrew NG的机器学习课程[1]。

降维最常用的方法是主成分分析（PCA，Principal Component Analysis）。PCA可以理解为在高维空间中寻找一个低维的面，使得高维空间中的点到该面上的距离之和最小，这个距离也叫投影误差。

利用PCA将维数从$n$维约减到$k$维，需要寻找$n$维空间中的$k$个向量$\mathbf u^{(1)}, \mathbf u^{(2)},\ldots,\mathbf u^{(k)}\in\mathbb R^n$，使空间中的点到这$k$个向量确定的面的投影误差最小。事实上，$n$维空间中的这$k$个向量是样本协方差矩阵最大的$k$个特征值对应的特征向量。

####PCA降维算法

1. 数据作均值为$0$的规范化（mean normalization），确保每维均值为$0$，若取值范围差异过大，还需尺度规范化（feature scaling）：$x_j^{(i)}:=\frac{x_j^{(i)}-\mu_j}{ \sigma_j}$（$\mu_j$表示均值，$\sigma_j$表示标准差）；
2. 计算协方差矩阵（covariance matrix）：$\Sigma = \frac{1}{m}\sum_{i=1}^m\mathbf x^{(i)}\left(\mathbf x^{(i)}\right)^T$；
3. 利用特征向量将$n$维向量$\mathbf x$映射到$k$维向量$\mathbf z$： \begin{equation} \mathbf z^{(i)} = \mathbf U_{reduce}^T\mathbf x^{(i)}。 \label{eq:pca-mapping} \end{equation}

[U, S, V] = svd(Sigma);
Ureduce = U(:, 1:k);
z = Ureduce’ * x;

在应用中，只需要在训练集上做PCA，交叉检验和测试集上可以直接应用训练集的均值$\boldsymbol\mu$、标准差$\mathbf s$和映射矩阵$U_{reduce}$计算约减后的向量。

Matlab中svd和eig函数都可以得到相同的特征值和特征向量，但是svd更稳定。

从$k$维数据$\mathbf z$重构$n$维数据$\mathbf x$的方法为

\begin{equation} \mathbf x_{approx}^{(i)} = \mathbf U_{reduce}\mathbf z^{(i)}。 \label{eq:pca-reconstruction} \end{equation}

约减后的维数$k$（主成分个数）通过方差保留的比率确定，选择满足下列条件的最小$k$

\begin{equation*} \frac{\frac{1}{m}\sum_{i=1}^m\left\lVert\mathbf x^{(i)}-\mathbf x_{approx}^{(i)}\right\rVert^2}{\frac{1}{m}\sum_{i=1}^m\left\lVert\mathbf x^{(i)}\right\rVert^2}\leq 0.01， \end{equation*}

此时方差保存比率为$99\%$。但是该方法计算复杂，可以通过特征值更简单的计算，选择满足下列条件的最小$k$

\begin{equation} \frac{\sum_{i=1}^kS_{ii}}{\sum_{i=1}^nS_{ii}}\geq 0.99， \end{equation}

$S_{ii}$是SVD得到的特征值。

####谨慎使用PCA

1. PCA不是解决过拟合的好方法，正则化是更好的策略（PCA或多或少损失了有助于分类的信息）；
2. 不得滥用PCA，除非有证据表明PCA的价值，比如在有训练时间和存储空间的限制的时候。

理解PCA

图 1：［左］规范化的数据；［中］PCA坐标变换；［右］PCA降维。

一、PCA是一种坐标变换方法

如果PCA变换之后的维数$k = n$，也就是没有降维，没有任何信息损失，这相当于坐标变换。上图左，经过规范化处理后的数据；上图中，利用公式\eqref{eq:pca-mapping}的PCA坐标变换，$k=n$，大概相当于左边的数据顺时针旋转$45$度再绕$Y$轴镜像；上图右，红色的点是经过$k=1$的降维处理后，再利用公式\eqref{eq:pca-reconstruction}重构回的数据。

协方差矩阵的特征向量，相当于新坐标系的基，原始数据到基上的投影就是新坐标系中的坐标。从这个角度理解降维，就相当于新坐标系中，只用前$k$维的坐标表示一个点，上图右重构回来的数据就会只在新坐标系的某个坐标轴上。

经过基于PCA的坐标变换之后，消除了特征之间的相关性，协方差矩阵是对角阵。如果对于基于多元高斯分布的异常检测，经过基于PCA的坐标变换之后，用一维高斯分布的方法就可处理。

二、PCA是一种特征提取方法

图 2：特征脸

协方差矩阵的特征向量可以看作是特征空间，在这个空间中投影，可视为特征提取。上图展示了人脸数据集协方差矩阵的前$36$维特征向量，如果人脸在这个特种空间中投影，相当于利用这$36$张特征脸的线性组合来表示人脸。向左上角靠近的特征脸，表现的是人脸的主要信息；向右下角靠近的特征脸，表现的是人脸的细节信息¹。

上图可以视为PCA坐标变换的新坐标系，灰色的表示系数接近0，意味着新的坐标系的坐标轴靠近原坐标系的某些轴。

用少量特征维表示人脸，可认为是人脸的一种稀疏表示。这是一种目的很明确的表示方法，将对象特征从主要到次要，根据需要依次表示出来。

图 3：［左］原图；［右］PCA降维后重构的人脸

三、其它角度理解PCA

• 傅立叶变换、小波变换、PCA特征向量空间的变换、稀疏表示……
• 特征学习：神经网络权值、PCA特征向量空间、深度学习……

KPCA

图 4：Kernel PCA

Kernel PCA 原理和演示

2DPCA[2]

简介

令$\mathbf X$是$n$维的单列向量，$m\times n$的图像$\mathbf A$投影到$\mathbf X$上[3][4]

\begin{equation} \mathbf Y = \mathbf A\mathbf X， \end{equation}

可得$m$维的投影向量$\mathbf Y$，称之为图像$\mathbf A$的投影特征向量（projected feature vector）。如何确定好的向量$\mathbf X$？可用投影所得样本估计$\mathbf X$的区分能力。样本的全散度（total scatter）可用投影特征向量协方差矩阵的迹刻画，采用如下准则

\begin{equation} J(\mathbf X) = \mathrm{tr}\left(\mathbf S_x\right)， \label{eq:max-scatter} \end{equation}

其中$\mathbf S_x$表示训练样本的投影特征向量协方差矩阵，$\mathrm{tr}\left(\mathbf S_x\right)$表示$\mathbf S_x$的迹。最大化准则\eqref{eq:max-scatter}就是找到投影方向$\mathbf X$，最大化投影样本的全散度。协方差矩阵$\mathbf S_x$由下式确定

\[ \begin{aligned} \mathbf S_x &= E\left[\left(\mathbf Y-E\mathbf Y\right)\left(\mathbf Y-E\mathbf Y\right)^\top\right]\\ &=E\left(\left[\mathbf{AX}-E\left(\mathbf{AX}\right) \right]\left[\mathbf{AX}-E\left(\mathbf{AX}\right) \right]^\top\right)\\ &=E\left(\left[\left(\mathbf{A}-E\mathbf{A}\right)\mathbf X\right]\left[\left(\mathbf{A}-E\mathbf{A}\right)\mathbf X\right]^\top\right)。 \end{aligned} \]

那么有

\begin{equation} \mathrm{tr}\left(\mathbf S_x\right)= \mathbf X^\top E\left[\left(\mathbf{A}-E\mathbf{A}\right)^\top\left(\mathbf{A}-E\mathbf{A}\right)\right]\mathbf X。 \end{equation}

令$\mathbf G_t = E\left[\left(\mathbf{A}-E\mathbf{A}\right)^\top\left(\mathbf{A}-E\mathbf{A}\right)\right]$，这称之为图像协方差（散度）矩阵。

容易验证，$\mathbf G_t$是$n\times n$的非负正定矩阵（nonnegative definite matrix），可以直接通过训练样本计算。第$j$幅训练图像记为$\mathbf A_j\;(j=1,2,\ldots,M)$，所有训练样本的平均图像记为$\bar{\mathbf A}$，那么可得

\begin{equation} \mathbf G_t = \frac{1}{M}\sum_{j=1}^M\left(\mathbf A_j - \bar{\mathbf A}\right)^\top\left(\mathbf A_j - \bar{\mathbf A}\right)。 \end{equation}

因此，\eqref{eq:max-scatter}的准则可表示为

\begin{equation} J(\mathbf X)=\mathbf X^\top\mathbf G_t\mathbf X。 \end{equation}

该准则称为泛化的全散度准则（generalized total scatter criterion），最大化该准则的的$\mathbf X$称为最优投影轴（optimal projection axis）。

最佳投影轴$\mathbf X_{opt}$最大化$J(\mathbf X)$，也就是对应着$\mathbf G_t$最大特征值的特征向量[5]。只有一个最佳投影轴通常不够。通常选择满足正交约束的一组投影轴$\mathbf X_1,\ldots,\mathbf X_d$，最大化$J(\mathbf X)$，也就是

\begin{equation} \begin{aligned} &\left\{\mathbf X_1,\ldots,\mathbf X_d \right\} = \arg\max J(\mathbf X)\\ &\mathbf X_i^\top\mathbf X_j = 0,\quad i\neq j,\;i,j=1,\ldots,d。 \end{aligned} \end{equation}

实际上，最佳投影轴$\mathbf X_1,\ldots,\mathbf X_d$是$\mathbf G_t$最大$d$个特征值对应的特征向量。

应用

一、特征提取

给定图像$\mathbf A$，令

\begin{equation} \mathbf Y_k = \mathbf{AX}_k,\quad k=1,2,\ldots,d。 \end{equation}

那么可得一组投影特征向量$\mathbf Y_1,\ldots,\mathbf Y_d$，称其为图像$\mathbf A$的主成分（向量）。2DPCA的每个主成分是一个向量，而PCA的每个主成分是一个数。

主成分向量构成$m\times d$矩阵$\mathbf B=\left[\mathbf Y_1,\ldots,\mathbf Y_d\right]$，称之为图像$\mathbf A$的特征矩阵（feature matrix）或特征图像（feature image）。

二、分类

经过2DPCA，每幅图得到一个特征矩阵，然后可用最近邻分类器分类。令$\mathbf B_i=\left[\mathbf Y_1^{(i)},\mathbf Y_2^{(i)},\ldots,\mathbf Y_d^{(i)}\right]$和$\mathbf B_j=\left[\mathbf Y_1^{(j)},\mathbf Y_2^{(j)},\ldots,\mathbf Y_d^{(j)}\right]$，两个任意特征矩阵间的距离为

\begin{equation} d\left(\mathbf B_i,\mathbf B_j\right)=\sum_{k=1}^d\left\Vert\mathbf Y_k^{(i)}-\mathbf Y_k^{(j)}\right\Vert_2， \end{equation}

其中，$\left\Vert\mathbf Y_k^{(i)}-\mathbf Y_k^{(j)}\right\Vert_2$表示两个主成分向量间的欧氏距离。

三、图像重建

令$\mathbf V=\left[\mathbf Y_1,\ldots,\mathbf Y_d\right]$、$\mathbf U=\left[\mathbf X_1,\ldots,\mathbf X_d\right]$，那么

\begin{equation} \mathbf V=\mathbf{AU}。 \end{equation}

由于$\mathbf X_1,\ldots,\mathbf X_d$正交，容易得到$\mathbf A$的重建图像

\begin{equation} \tilde{\mathbf A}=\mathbf V\mathbf U^\top=\sum_{k=1}^d\mathbf Y_k\mathbf X_k^\top。 \end{equation}

令$\tilde{\mathbf A}_k=\mathbf Y_k\mathbf X_k^\top\;(k=1,2,\ldots,d)$，其尺寸与图像$\mathbf A$相同，表示重建$\mathbf A$的子图。也就是，图像$\mathbf A$能通过累加前$d$幅子图重建。特别地，当$d=n$时（$n$是$\mathbf G_t$全部特征向量的个数），可得$\tilde{\mathbf A}={\mathbf A}$，也就是图像能无损的完全重建。

理解2DPCA

2DPCA分可分为两部分：第一部分是寻找坐标变换的基$\mathbf U$（新的空间）；第二部分是将原图像在新空间投影，计算坐标。

对于$1\times n$的单行图像，2DPCA与PCA完全等价。从PCA的角度看，需要$m$个$\mathbf U$矩阵才能做到重构意义下的最佳变换，事实上此处只有一个，显然不是PCA意义下的最佳变换。只要$\mathbf U$是正交的（或者线性无关向量组），总能保证完全重构。

从特征提取的角度看，$\mathbf X_k$相当于特征描述子。对于横轴上的Sobel算子，$\mathbf U_{sobel}$相当于

\[ \mathbf U_{sobel} = \begin{bmatrix} -1 & 0 & +1 \\ -2 & 0 & +2 \\ -1 & 0 & +1 \end{bmatrix}^\top。 \]

不过，此处的$\mathbf U_{sobel}$不满足正交约束条件。Haar特征提取满足类似的关系。2DPCA的隐含约束条件是完全重构，而特征提取的条件大多数是为了分类，因此，它们之间的差别显而易见。

2DPCA的$\mathbf U$来自于无监督学习。通过构造监督学习的框架，可以学到更利于分类的基（特征描述矩阵）$\mathbf U$。

xPCA沉思录

xPCA能提高分类性能吗？

xPCA本质上是一种坐标变换，或者重构算法，并没有以提高分类性能作为约束条件，因此无法直接提高分类性能。xPCA是重构约束下的最佳坐标变换（维度约减）。

但是，当分类器受限的情况下，有可能提升分类性能。例如：假设人就是一个分类器，如果给人展示三维及更高维度的数据时，人就很难将其分开。但是，如果将高维数据投影到二维，人就容易分开。并且，xPCA保证了是高维到二维的最佳投影。xPCA将人类不可分问题变为了可能。因此，在这样的情况下，确实可以提高分类器性能。由此可见，PCA是数据可视化的很好手段。

实际上，我们并不容易知道分类器是否受限。这需要用到validation技术。

其它降维技术²

1. 缺失值比率（missing values ratio）：若数据列太多值缺失，则认为不太可能包含很多有用信息。缺失值比率大于设定阈值列的可被移除。
2. 低方差滤波器(low variance filter)：若数据列变化小，则认为包含信息不多。数据列方差小于设定阈值列的可被移除。采用此方法需对数据归一化。
3. 高相关滤波器（high correlation filter）：数据列包含相似趋势，可认为携带信息少。因此，只需保留这些列中的一列。保留两列的相关系数高于设定阈值中的一列。采用此方法需对数据归一化。
4. 随机森林／集成树（random forests / ensemble trees）：生成大量很浅的树，每棵树之用少量特征训练。如果一个特征经常作为最佳分裂，它很可能是需要保留的特征。对随机森林数据属性的统计评分，揭示了与其它属性相比，哪个属性的预测能力最好。
5. 后向特征消除（backward feature flimination）：先在$n$个特征上训练分类器，然后每次移除一个特征，在$n-1$个特征上训练$n$次。移除的某个特征导致的错误率增加最小，则移除该特征。然后在$n-1$个特征上重复上述过程……选择满足错误率要求的最少数目的特征子集。
6. 前向特征构造（forward feature construction）：与后向特征消除相反，从1个特征开始，逐次增加特征1个能最大提升性能的特征。
7. 随机投影（random projections）
8. 非负矩阵分解（NMF）
9. 自编码器（auto-encoders）
10. 卡方或信息增益（Chi-square or information gain）
11. 多维尺度化（multidimensional scaling）
12. 相关分析（correspondence analysis）
13. 因子分析（factor analysis）
14. 聚类（clustering）
15. 贝叶斯模型（bayesian models）

……

参考资料

1. [1]A. Ng, “Dimensionality Reduction.” Coursera, 2014. [Online]
2. [2]J. Yang, D. Zhang, A. F. Frangi, and J.-yu Yang, “Two-dimensional PCA: a new approach to appearance-based face representation and recognition,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 26, no. 1, pp. 131–137, 2004.
3. [3]K. Liu, Y.-Q. Cheng, and J.-Y. Yang, “Algebraic feature extraction for image recognition based on an optimal discriminant criterion,” Pattern Recognition, vol. 26, no. 6, pp. 903–911, 1993.
4. [4]P. N. Belhumeur, J. P. Hespanha, and D. J. Kriegman, “Eigenfaces vs. fisherfaces: Recognition using class specific linear projection,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 19, no. 7, pp. 711–720, 1997.
5. [5]J. Yang and J.-yu Yang, “From image vector to matrix: a straightforward image projection technique—IMPCA vs. PCA,” Pattern Recognition, vol. 35, no. 9, pp. 1997–1999, 2002.

• 浅谈高维数据可视化中的降维方法