非线性降维

高维数据，意味着数据需要多于两个或三个维度来表示，一般很难被解释。一种简化的方法是假设数据嵌在高维空间的一个非线性流形上。如果这个流形维数足够低，那么数据可以在低维空间中被可视化。

非线性降维的应用[编辑]

考虑以矩阵（或数据库）表示的数据集，其中每行都代表描述某物特定实例的一组属性（或特征）。如果属性的数量很大，那么可行行空间的增长速度是指数级的（例如有 $f$ 个属性，每个属性均具有 $k$ 种可能的选择，则所有可能的属性为 $k^{f}$ ）。维度越大，对空间进行采样就越困难。这导致了处理高维数据的算法时间复杂性非常高。许多机器学习算法在处理高维数据时很吃力，而将数据缩降维会使算法更有效率，并能帮助机器学习算法做出更准确的预测。

人类往往难以理解高维数据。因此将数据减进行降维对于可视化非常有用。

数据的降维表示通常被称为 "内在变量"，即它们是数据产生的价值。例如，考虑一个包含字母 "A" 经过缩放和旋转的图像的数据集，每张图片有32×32像素，可以表示为长度为1024的向量。每一行都是1024维的空间（汉明空间（英语：Hamming_space））中，二维流形上的一个样本。由于数据仅通过缩放和旋转得到，所以本质维度是2；而字母 "A" 的形状或外观则不是内在变量（因为数据集中所有元素该特征均相同）。非线性降维将抛弃相关的信息（字母 "A"），只保留变化的信息（缩放和旋转）。右图展示了该数据集的部分样本，及通过使用非线性降维算法（Manifold Sculpting）将数据降到二维的结果散点图。

作为对比，右图使用线性降维算法PCA（主成分分析），将同样的数据集降为二维，可以发现结果并没有采用非线性降维算法好。这表明从该流形上采样得到的高维向量以一种非线性的方式变化。

非线性降维在计算机视觉领域有所应用。例如一个使用相机在封闭的静态环境中导航的机器人，相机得到的图像可以视为从高维空间流形采样得到的样本，该流形的内在变量代表机器人的位置和朝向。

下面列举了一些非线性降维算法。

流形学习算法[编辑]

Sammon映射[编辑]

自组织映射[编辑]

主曲线和流形[编辑]

自编码器[编辑]

自编码器是一个前馈神经网络，其训练目标为恒等映射，即从一个向量映射到同一个向量。用于降维时，其部分隐藏层只包含少量神经元。此时，网络必须学会用较少的维度编码向量，并同时能将将其解码。因此，网络的前半部分（编码器，Encoder）从高维空间映射到低维空间，后半部分（解码器，Decoder）从低维空间映射到高维空间。

高斯过程潜变量模型[编辑]

曲线成分分析[编辑]

曲线距离分析[编辑]

微分同胚降维[编辑]

核方法的主成分分析[编辑]

核主成分分析（Kernel Principal Component Analysis，KPCA）是最常用的降维算法之一。^[1]PCA首先计算 $m\times n$ 矩阵 $\mathbf {X}$ 的协方差矩阵：

C={\frac {1}{m}}\sum _{i=1}^{m}{\mathbf {x} _{i}\mathbf {x} _{i}^{\mathsf {T}}}.

然后将数据投影到协方差矩阵的前k个特征向量上。而KPCA首先将数据变换到更高维的空间，然后计算变换后数据的的协方差矩阵：

C={\frac {1}{m}}\sum _{i=1}^{m}{\Phi (\mathbf {x} _{i})\Phi (\mathbf {x} _{i})^{\mathsf {T}}}.

然后和PCA一样，将数据投影到协方差矩阵的前k个特征向量上。该方法使用了核方法来避免大量的运算，整个过程可以在没有实际计算 $\Phi (\mathbf {x} )$ 的情况下执行（当然， $\Phi$ 必须被选择）。不幸的是，为特定问题选择一个合适的核函数并不容易，在使用普通核函数时，KPCA的表现不一定好；例如在瑞士卷流形（Swiss roll manifold）上的表现不佳。有部分方法通过构造依赖于数据的核矩阵达成较好的表现（例如 Laplacian Eigenmaps），该类方法可以看作KPCA的特殊情况。^[2]

KPCA有一个内部模型，因此它可以用来将不在训练集中的点映射到嵌入。

等距特征映射[编辑]

局部线性嵌入[编辑]

拉普拉斯特征映射[编辑]

流形对齐[编辑]

散射映射[编辑]

Hessian局部线性映射[编辑]

局部线性嵌入·改 [编辑]

关系透视图[编辑]

局部切空间对齐[编辑]

局部多维标度[编辑]

最大方差展开[编辑]

非线性PCA[编辑]

数据驱动的高维缩放[编辑]

Manifold sculpting[编辑]

t-distributed stochastic neighbor embedding[编辑]

RankVisu[编辑]

Topologically constrained isometric embedding[编辑]

基于距离矩阵的方法[编辑]

参见[编辑]

Discriminant analysis
Elastic map^[3]
Feature learning
Growing self-organizing map (GSOM)
Pairwise distance methods
Self-organizing map (SOM)

引用[编辑]

^ B. Schölkopf, A. Smola, K.-R. Müller, Nonlinear Component Analysis as a Kernel Eigenvalue Problem. Neural Computation 10(5):1299-1319, 1998, MIT Press Cambridge, MA, USA, doi:10.1162/089976698300017467
^ Jihun Ham, Daniel D. Lee, Sebastian Mika, Bernhard Schölkopf. A kernel view of the dimensionality reduction of manifolds. Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2004. doi:10.1145/1015330.1015417
^ ELastic MAPs. [2016-05-30]. （原始内容存档于2011-07-20）.

外部链接[编辑]

Isomap
Generative Topographic Mapping
Mike Tipping's Thesis （页面存档备份，存于互联网档案馆）
Gaussian Process Latent Variable Model
Locally Linear Embedding （页面存档备份，存于互联网档案馆）
Relational Perspective Map （页面存档备份，存于互联网档案馆）
Waffles （页面存档备份，存于互联网档案馆） is an open source C++ library containing implementations of LLE, Manifold Sculpting, and some other manifold learning algorithms.
Efficient Dimensionality Reduction Toolkit homepage^{[永久失效連結]}
DD-HDS homepage
RankVisu homepage
Short review of Diffusion Maps
Nonlinear PCA by autoencoder neural networks （页面存档备份，存于互联网档案馆）

[1] B. Schölkopf, A. Smola, K.-R. Müller, Nonlinear Component Analysis as a Kernel Eigenvalue Problem. Neural Computation 10(5):1299-1319, 1998, MIT Press Cambridge, MA, USA, doi:10.1162/089976698300017467

[2] Jihun Ham, Daniel D. Lee, Sebastian Mika, Bernhard Schölkopf. A kernel view of the dimensionality reduction of manifolds. Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2004. doi:10.1145/1015330.1015417

[3] ELastic MAPs. [2016-05-30]. （原始内容存档于2011-07-20）.

[1]

[2]

[3]

相关的线性分解的方法[编辑]