多维数据降维方法

文/戴云翔 路东东

1 引言

数据降维是一个过程，在数据降维过程是要保证在降低数据集维度的过程后，数据不丢失、不失真，降维后的数据依然要包含数据的原有信息。在科技发展的今天，数据的采集益发容易，采集的数据的量越来越大，很多时候数据量均在G量级上。在机器学习中，在数据量过少时容易引发数据的“欠拟合”；但如果特征值（维度）过多，会引起维度灾难。维度灾难最直接的后果就是“过拟合”，进而导致分类错误，这也是数据降维研究的初衷。

特征降维的方法根据特征提取方式的不同可以分为：特征选择和特征抽取；根据样本信息可利用可分为：监督降维、半监督降维和无监督降维；根据处理数据属性类别的不同可分为：线性降维和非线性降维。本文就处理数据类别方面对多维数据降维方法进行阐述。

2 线性降维方法

常用的线性降维方法主要有主成分分析降维和稀疏主成分降维。这两种降维方法均能够获得原始数据中的数据的主要成分，但两种方法在数据的可解释性上又有所区别。

2.1 主成分分析降维

主成分分析（Principle Component Analysis, PCA）降维的目标是找到数据中最主要的元素和结构，去除噪声和冗余，对原有的复杂数据进行降维，揭示处隐藏在复杂数据背后的简单数据。

主成分分析的步骤为：

（3）计算累积贡献率，求出恰当的主成分个数。

主成分分析方法对原始数据进行线性降维，降维后的数据保留原有数据的特征，但原有数据的内在结构将不复存在。

2.2 稀疏主成分分析

稀疏主成分分析（Sparse Principle Compenent Analysis, SPCA) 是在PCA分析基础上，将载荷矩阵转化为Lesso惩罚回归问题得到稀疏载荷。与PCA相比，基于SPCA获得的主成分有很强的解释能力，能够解释数据内在的结构，直观来说就是在应用稀疏主成分分析方法进行数据降维后，可以直接获得对原始数据贡献率大的原始数据中的具体项。

稀疏主成分分析的步骤为：

（2）在所给的A矩阵的条件下，求解弹性网回归问题：

其中，λ和λj为弹性惩罚系数。

（4）重复步骤（2）和（3）至B收敛

（5）标准化βj后即可得到稀疏载荷向量

3 非线性降维方法

非线性降维方法有局部线性嵌入方法（Locally Linear Embedding，LLE）、核主成分分析（Kernel Principal Component Analysis，KPCA）和等距特征映射（Isometric Feature Mapping，Isomap）。

其中，LLE算法几何意义直观、待定参数少可以学习任意维数的高维流形、有整体解析最优解、适用于非线性数据的要求流形上点分布均匀且稠密采样；当流形呈卷曲状，可能造成流形结构在重构过程扭曲；当流形为封闭式流形（球形、椭球形）时，方法失效；LLE对噪声敏感，对多流形数据局部线性化差。

KPCA算法：PCA的非线性提升，适于解决非线性特征提取问题，能提供比PCA更多的特征数目，可以最大限度的提取特征信息。同PCA一样，存储空间大、计算复杂度高，提取的特征意义不明确。

ISOMAP算法：参数设定简单、保证全局最优；计算速度快；计算高维数据数据点间的距离时，使用测地线距离而不是欧式距离，很好的保持了数据的内部几何结构。然而该方法对内部曲率较大的流形展开能力较差，不能对训练数据以外的数据进行降维。

对于非线性降维方法，本文将着重介绍等距特征映射方法和局部线性嵌入方法。

3.1 等距特征映射

3.1.1 构建邻接图 G

定义邻接图G覆盖所有数据点，数据点与其近邻点有边相连，边的长度为两点之间的距离dx(i,j)。计算近邻点有如下两种方法：

（1）基于欧氏距离寻找离样本点最近的K个近邻点，基于此方法的等距特征映射叫K-Isomap；

（2）将样本点选定半径为常数δ的圆内所有点都作为样本点的近邻点，基于此方法的等距特征映射叫

3.1.2 计算节点相互之间的最短路径

（1）初始化dG(i,j)。若G中结点i、j之间有边相连，则否则

3.1.3 计算低维嵌入

使用多尺度变换计算方法计算流形的低维嵌入，选择低维空间的任意两个嵌入坐标yi、yj，最小化代价函数如公式（3）所示，di,j为两点之间的最短路径。

3.2 局部线性嵌入方法

LLE算法的思想是：假设数据的结构在局部意义下是线性的，通过局部的线性来逼近全局的非线性。对于数据集中任意一点xi，都可以寻找它的K个近邻点线性组合表示，具体组合的权重需要通过最小化重构误差得到。最后将样本点映射到低维空间的同时尽量保持各样本点与其近邻点的关系不变。LLE算法的具体步骤如下：

3.2.1 选取邻域

3.2.2 计算样本的邻域重构

对于每个点xi，LLE算法局部特性描述方法和ISOMAP不同。LLE算法需要计算每个点xi在其邻域集合内的重构权值，构建所有样本点间的重构权值矩阵W。在这里认为非近邻点间的重构权值Wi,j=0。

为了求得最佳的重构权值，定义重构误差为：

这里的重构权值反映了近邻点对中心点的贡献程度。为了使重构权值具有平移不变形，对于任意样本点xi与其邻域点的重构权值给以约束最后利用拉格朗日乘子法，可对式（5）求解。

3.2.3 计算低维嵌入

最后求取低维嵌入坐标的代价函数为：

为了使得低维嵌入坐标 的具有平移、旋转、缩放不变性，还需要对式（6）添加一些约束条件：

这样，式（6）可写为：

式中Ii和表示单位阵I和WT的第i列，根据矩阵迹的性质

可将式（6）进一步写成：

LLE算法的优点是利用了局部线性关系有效的记录了数据的内蕴几何结构，相比于ISOMAP

算法计算复杂度更低，且无需迭代。算法的最终求解可归结为稀疏矩阵的特征值计算问题。

LLE算法只是保持局部近邻关系，而不是样本点间的测地线距离关系，所以不能很好的保持具有等距特性的数据的流形结构。LLE 算法假设样本是均匀稠密分布的，对于噪声较为敏感。

4 结束语

本文对数据降维方法进行了简要概述，同时对线性降维方法中常用的PCA降维方法、稀疏主成分分析方法的步骤进行了具体阐述。在非线性降维方面对Isomap算法、LLE算法的具体步骤进行了详细的介绍。四种降维方法各有利弊，在应用数据降维方法进行数据降维时，鉴于数据类型的多样性及需要提取的特征的差异，在具体特征提取时，需要进行具体分析，以便获得最好的降维效果。