主成分分析
From Ufldl
| Line 1: | Line 1: | ||
| - | + | == 引言 == | |
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
主成分分析（PCA）是一种能够极大提升无监督特征学习速度的数据降维算法。更重要的是，理解PCA算法，对实现'''白化'''算法有很大的帮助，很多算法都先用白化算法作预处理步骤。 | 主成分分析（PCA）是一种能够极大提升无监督特征学习速度的数据降维算法。更重要的是，理解PCA算法，对实现'''白化'''算法有很大的帮助，很多算法都先用白化算法作预处理步骤。 | ||
假设你使用图像来训练算法，因为图像中相邻的像素高度相关，输入数据是有一定冗余的。具体来说，假如我们正在训练的16x16灰度值图像，记为一个256维向量 <math>\textstyle x \in \Re^{256}</math> ，其中特征值 <math>\textstyle x_j</math> 对应每个像素的亮度值。由于相邻像素间的相关性，PCA算法可以将输入向量转换为一个维数低很多的近似向量，而且误差非常小。 | 假设你使用图像来训练算法，因为图像中相邻的像素高度相关，输入数据是有一定冗余的。具体来说，假如我们正在训练的16x16灰度值图像，记为一个256维向量 <math>\textstyle x \in \Re^{256}</math> ，其中特征值 <math>\textstyle x_j</math> 对应每个像素的亮度值。由于相邻像素间的相关性，PCA算法可以将输入向量转换为一个维数低很多的近似向量，而且误差非常小。 | ||
| + | |||
== 实例和数学背景 == | == 实例和数学背景 == | ||
| + | |||
在我们的实例中，使用的输入数据集表示为 <math>\textstyle \{x^{(1)}, x^{(2)}, \ldots, x^{(m)}\}</math> ，维度 <math>\textstyle n=2</math> 即 <math>\textstyle x^{(i)} \in \Re^2</math> 。假设我们想把数据从2维降到1维。（在实际应用中，我们也许需要把数据从256维降到50维；在这里使用低维数据，主要是为了更好地可视化算法的行为）。下图是我们的数据集： | 在我们的实例中，使用的输入数据集表示为 <math>\textstyle \{x^{(1)}, x^{(2)}, \ldots, x^{(m)}\}</math> ，维度 <math>\textstyle n=2</math> 即 <math>\textstyle x^{(i)} \in \Re^2</math> 。假设我们想把数据从2维降到1维。（在实际应用中，我们也许需要把数据从256维降到50维；在这里使用低维数据，主要是为了更好地可视化算法的行为）。下图是我们的数据集： | ||
| Line 52: | Line 46: | ||
在本例中，向量 <math>\textstyle u_1</math> 和 <math>\textstyle u_2</math> 构成了一个新基，可以用来表示数据。令 <math>\textstyle x \in \Re^2</math> 为训练样本，那么 <math>\textstyle u_1^Tx</math> 就是样本点 <math>\textstyle x</math> 在维度 <math>\textstyle u_1</math> 上的投影的长度（幅值）。同样的， <math>\textstyle u_2^Tx</math> 是 <math>\textstyle x</math> 投影到 <math>\textstyle u_2</math> 维度上的幅值。 | 在本例中，向量 <math>\textstyle u_1</math> 和 <math>\textstyle u_2</math> 构成了一个新基，可以用来表示数据。令 <math>\textstyle x \in \Re^2</math> 为训练样本，那么 <math>\textstyle u_1^Tx</math> 就是样本点 <math>\textstyle x</math> 在维度 <math>\textstyle u_1</math> 上的投影的长度（幅值）。同样的， <math>\textstyle u_2^Tx</math> 是 <math>\textstyle x</math> 投影到 <math>\textstyle u_2</math> 维度上的幅值。 | ||
| + | |||
== 旋转数据 == | == 旋转数据 == | ||
| + | |||
至此，我们可以把 <math>\textstyle x</math> 用 <math>\textstyle (u_1, u_2)</math> 基表达为： | 至此，我们可以把 <math>\textstyle x</math> 用 <math>\textstyle (u_1, u_2)</math> 基表达为： | ||
:<math>\begin{align} | :<math>\begin{align} | ||
| Line 65: | Line 61: | ||
这就是把训练数据集旋转到 <math>\textstyle u_1</math>，<math>\textstyle u_2</math> 基后的结果。一般而言，运算 <math>\textstyle U^Tx</math> 表示旋转到基 <math>\textstyle u_1</math>,<math>\textstyle u_2</math>, ...,<math>\textstyle u_n</math> 之上的训练数据。矩阵 <math>\textstyle U</math> 有正交性，即满足 <math>\textstyle U^TU = UU^T = I</math> ，所以若想将旋转后的向量 <math>\textstyle x_{\rm rot}</math> 还原为原始数据 <math>\textstyle x</math> ，将其左乘矩阵<math>\textstyle U</math>即可： <math>\textstyle x=U x_{\rm rot}</math> , 验算一下： <math>\textstyle U x_{\rm rot} = UU^T x = x</math>. | 这就是把训练数据集旋转到 <math>\textstyle u_1</math>，<math>\textstyle u_2</math> 基后的结果。一般而言，运算 <math>\textstyle U^Tx</math> 表示旋转到基 <math>\textstyle u_1</math>,<math>\textstyle u_2</math>, ...,<math>\textstyle u_n</math> 之上的训练数据。矩阵 <math>\textstyle U</math> 有正交性，即满足 <math>\textstyle U^TU = UU^T = I</math> ，所以若想将旋转后的向量 <math>\textstyle x_{\rm rot}</math> 还原为原始数据 <math>\textstyle x</math> ，将其左乘矩阵<math>\textstyle U</math>即可： <math>\textstyle x=U x_{\rm rot}</math> , 验算一下： <math>\textstyle U x_{\rm rot} = UU^T x = x</math>. | ||
| + | |||
== 数据降维 == | == 数据降维 == | ||
| + | |||
数据的主方向就是旋转数据的第一维 <math>\textstyle x_{{\rm rot},1}</math> 。因此，若想把这数据降到一维，可令： | 数据的主方向就是旋转数据的第一维 <math>\textstyle x_{{\rm rot},1}</math> 。因此，若想把这数据降到一维，可令： | ||
| Line 106: | Line 104: | ||
[[File:PCA-xtilde.png | 600px]] | [[File:PCA-xtilde.png | 600px]] | ||
| - | 然而，由于上面 <math>\textstyle \tilde{x}</math> 的后<math>\textstyle n-k</math>项均为零，没必要把这些零项保留下来。所以，我们仅用前 <math>\textstyle | + | 然而，由于上面 <math>\textstyle \tilde{x}</math> 的后<math>\textstyle n-k</math>项均为零，没必要把这些零项保留下来。所以，我们仅用前 <math>\textstyle k</math> 个（非零）成分来定义 <math>\textstyle k</math> 维向量 <math>\textstyle \tilde{x}</math> 。 |
这也解释了我们为什么会以 <math>\textstyle u_1, u_2, \ldots, u_n</math> 为基来表示数据：要决定保留哪些成分变得很简单，只需取前 <math>\textstyle k</math> 个成分即可。这时也可以说，我们“保留了前 <math>\textstyle k</math> 个PCA（主）成分”。 | 这也解释了我们为什么会以 <math>\textstyle u_1, u_2, \ldots, u_n</math> 为基来表示数据：要决定保留哪些成分变得很简单，只需取前 <math>\textstyle k</math> 个成分即可。这时也可以说，我们“保留了前 <math>\textstyle k</math> 个PCA（主）成分”。 | ||
| + | |||
== 还原近似数据 == | == 还原近似数据 == | ||
| - | 现在，我们得到了原始数据 <math>\textstyle x \in \Re^n</math> 的低维“压缩”表征量 <math>\textstyle \tilde{x} \in \Re^k</math> ， 反过来，如果给定 <math>\textstyle \tilde{x}</math> ，我们应如何还原原始数据 <math>\textstyle x</math> 呢？查看[[#旋转数据|以往章节]]以往章节可知，要转换回来，只需 <math>\textstyle x = U x_{\rm rot}</math> 即可。进一步，我们把 <math>\textstyle \tilde{x}</math> 看作将 <math>\textstyle x_{\rm rot}</math> 的最后 <math>\textstyle n-k</math> 个元素被置0所得的近似表示，因此如果给定 <math>\textstyle \tilde{x} \in \Re^k</math> ，可以通过在其末尾添加 <math>\textstyle n-k</math> 个0来得到对 <math>\textstyle x_{\rm rot} \in \Re^n</math> 的近似，最后，左乘 <math>\textstyle U</math> 便可近似还原出原数据 。具体来说，计算如下： | + | |
| + | 现在，我们得到了原始数据 <math>\textstyle x \in \Re^n</math> 的低维“压缩”表征量 <math>\textstyle \tilde{x} \in \Re^k</math> ， 反过来，如果给定 <math>\textstyle \tilde{x}</math> ，我们应如何还原原始数据 <math>\textstyle x</math> 呢？查看[[#旋转数据|以往章节]]以往章节可知，要转换回来，只需 <math>\textstyle x = U x_{\rm rot}</math> 即可。进一步，我们把 <math>\textstyle \tilde{x}</math> 看作将 <math>\textstyle x_{\rm rot}</math> 的最后 <math>\textstyle n-k</math> 个元素被置0所得的近似表示，因此如果给定 <math>\textstyle \tilde{x} \in \Re^k</math> ，可以通过在其末尾添加 <math>\textstyle n-k</math> 个0来得到对 <math>\textstyle x_{\rm rot} \in \Re^n</math> 的近似，最后，左乘 <math>\textstyle U</math> 便可近似还原出原数据 <math>\textstyle x</math> 。具体来说，计算如下： | ||
:<math>\begin{align} | :<math>\begin{align} | ||
| Line 125: | Line 125: | ||
在训练自动编码器或其它无监督特征学习算法时，算法运行时间将依赖于输入数据的维数。若用 <math>\textstyle \tilde{x} \in \Re^k</math> 取代 <math>\textstyle x</math> 作为输入数据，那么算法就可使用低维数据进行训练，运行速度将显著加快。对于很多数据集来说，低维表征量 <math>\textstyle \tilde{x}</math> 是原数据集的极佳近似，因此在这些场合使用PCA是很合适的，它引入的近似误差的很小，却可显著地提高你算法的运行速度。 | 在训练自动编码器或其它无监督特征学习算法时，算法运行时间将依赖于输入数据的维数。若用 <math>\textstyle \tilde{x} \in \Re^k</math> 取代 <math>\textstyle x</math> 作为输入数据，那么算法就可使用低维数据进行训练，运行速度将显著加快。对于很多数据集来说，低维表征量 <math>\textstyle \tilde{x}</math> 是原数据集的极佳近似，因此在这些场合使用PCA是很合适的，它引入的近似误差的很小，却可显著地提高你算法的运行速度。 | ||
| + | |||
== 选择主成分个数 == | == 选择主成分个数 == | ||
| + | |||
我们该如何选择 <math>\textstyle k</math> ，即保留多少个PCA主成分？在上面这个简单的二维实验中，保留第一个成分看起来是自然的选择。对于高维数据来说，做这个决定就没那么简单：如果 <math>\textstyle k</math> 过大，数据压缩率不高，在极限情况 <math>\textstyle k=n</math> 时，等于是在使用原始数据（只是旋转投射到了不同的基）；相反地，如果 <math>\textstyle k</math> 过小，那数据的近似误差太太。 | 我们该如何选择 <math>\textstyle k</math> ，即保留多少个PCA主成分？在上面这个简单的二维实验中，保留第一个成分看起来是自然的选择。对于高维数据来说，做这个决定就没那么简单：如果 <math>\textstyle k</math> 过大，数据压缩率不高，在极限情况 <math>\textstyle k=n</math> 时，等于是在使用原始数据（只是旋转投射到了不同的基）；相反地，如果 <math>\textstyle k</math> 过小，那数据的近似误差太太。 | ||
| Line 149: | Line 151: | ||
对其它应用，如不介意引入稍大的误差，有时也保留90-98%的方差范围。若向他人介绍PCA算法详情，告诉他们你选择的 <math>\textstyle k</math> 保留了95%的方差，比告诉他们你保留了前120个（或任意某个数字）主成分更好理解。 | 对其它应用，如不介意引入稍大的误差，有时也保留90-98%的方差范围。若向他人介绍PCA算法详情，告诉他们你选择的 <math>\textstyle k</math> 保留了95%的方差，比告诉他们你保留了前120个（或任意某个数字）主成分更好理解。 | ||
| + | |||
== 对图像数据应用PCA算法 == | == 对图像数据应用PCA算法 == | ||
| Line 167: | Line 170: | ||
<math>x^{(i)}_j := x^{(i)}_j - \mu^{(i)}</math>, for all <math>\textstyle j</math> | <math>x^{(i)}_j := x^{(i)}_j - \mu^{(i)}</math>, for all <math>\textstyle j</math> | ||
| + | |||
请注意：1）对每个输入图像块 <math>\textstyle x^{(i)}</math> 都要单独执行上面两个步骤，2）这里的 <math>\textstyle \mu^{(i)}</math> 是指图像块 <math>\textstyle x^{(i)}</math> 的平均亮度值。尤其需要注意的是，这和为每个像素 <math>\textstyle x_j</math> 单独估算均值是两个完全不同的概念。 | 请注意：1）对每个输入图像块 <math>\textstyle x^{(i)}</math> 都要单独执行上面两个步骤，2）这里的 <math>\textstyle \mu^{(i)}</math> 是指图像块 <math>\textstyle x^{(i)}</math> 的平均亮度值。尤其需要注意的是，这和为每个像素 <math>\textstyle x_j</math> 单独估算均值是两个完全不同的概念。 | ||
如果你处理的图像并非自然图像（比如，手写文字，或者白背景正中摆放单独物体），其他规整化操作就值得考虑了，而哪种做法最合适也取决于具体应用场合。但对自然图像而言，对每幅图像进行上述的零均值规整化，是默认而合理的处理。 | 如果你处理的图像并非自然图像（比如，手写文字，或者白背景正中摆放单独物体），其他规整化操作就值得考虑了，而哪种做法最合适也取决于具体应用场合。但对自然图像而言，对每幅图像进行上述的零均值规整化，是默认而合理的处理。 | ||
| + | |||
== 参考文献 == | == 参考文献 == | ||
| Line 176: | Line 181: | ||
| - | + | ==中英文对照== | |
| + | |||
Principal Components Analysis 主成份分析 | Principal Components Analysis 主成份分析 | ||
| + | |||
whitening 白化 | whitening 白化 | ||
| + | |||
intensity 亮度 | intensity 亮度 | ||
| + | |||
mean 平均值 | mean 平均值 | ||
| + | |||
variance 方差 | variance 方差 | ||
| + | |||
covariance matrix 协方差矩阵 | covariance matrix 协方差矩阵 | ||
| + | |||
basis 基 | basis 基 | ||
| + | |||
magnitude 幅值 | magnitude 幅值 | ||
| + | |||
stationarity 平稳性 | stationarity 平稳性 | ||
| + | |||
normalization 归一化 | normalization 归一化 | ||
| + | |||
eigenvector 特征向量 | eigenvector 特征向量 | ||
| + | |||
eigenvalue 特征值 | eigenvalue 特征值 | ||
| + | |||
| + | |||
| + | ==中文译者== | ||
| + | |||
| + | 郭亮（guoliang2248@gmail.com），张力（emma.lzhang@gmail.com），金峰（jinfengb@gmail.com）, @破破的桥（新浪微博）, 谭晓阳（x.tan@nuaa.edu.cn） | ||
| + | |||
| + | |||
| + | {{预处理：主成分分析与白化}} | ||
| + | |||
| + | |||
| + | {{Languages|PCA|English}} | ||
