机器学习数据预处理——降维

在机器学习的训练过程中，总是会碰到样本大、特征多的数据集。而这些数据集里面的数据有些是用处很小甚至完全无用的。如果一组数据中的无用数据占比较大时，一方面会使得模型的训练时间变长，另一方面模型容易出现欠拟合现象；而如果一组数据中作用较小的数据，即在训练中不能较好体现数据集中样本特征的数据，这类数据占比较大时，除了会提升模型训练的时间以外，还容易引起模型的过拟合现象。
针对这种情况，我们需要对这组数据集进行数据的预处理，其主要的方法有降噪、特征选择以及降维处理，而这次主要讲解如何进行降维处理以及降维处理的一些算法。

降维在机器学习中实际上就是采用某种映射方法，将数据从高维度的空间映射到低维度的空间中去，同时又尽可能的保留原始数据信息。
在许多算法中，降维成为了数据预处理的一部分。事实上，有一些算法如果没有先进行降维处理的话，其模型训练效果会较差。

降维在模型训练中的作用

1、新的数据在保留原数据大部分信息的基础上，较大地减少了数据量，从而减低了计算的复杂度
2、减少了冗余信息所造成的识别误差,提高了识别的精度
3、将数据的维数降低到2D或3D可以允许我们绘制和可视化它
4、降低模型的总体复杂度——太多的特征或太复杂的模型可能导致过拟合

降维方法

降维方法分为线性和非线性降维，非线性降维又分为基于核函数和基于特征值的方法。

1、线性降维方法:PCA 、ICA、LDA、LFA、LPP(LE的线性表示)

2、非线性降维方法:

(1) 基于核函数的非线性降维方法:KPCA 、KICA、KDA

(2) 基于特征值的非线性降维方法(流型学习):ISOMAP、LLE、LE、LPP、LTSA、MVU

主成分分析 (Principal Component Analysis ，简称 PCA)是最常用的一种降维方法

PCA的思想很简答，它是想找到一个超平面，使得这样一个超平面能够对所有的样本进行恰当的表达。这便如同二维空间中的曲线拟合一样，它致力于寻找一条曲线，使得所有点到这条曲线的距离最短，不同的是，这样的数据从二维空间拓展到了高维空间。
我们在返回来看一下，我们想要找到这样一个超平面，那么势必要让它满足我们的要求，而我们的要求也很简单：
1、最近重构性：样本点到这个超平面的距离都足够近;
就前面所说，我们想要一个能够对所有样本进行恰当表达的超平面，那么这个超平面应该要尽可能的体现原本数据的特征、信息。所以，我们要使得样本点到这个超平面的距离都足够近，这样，样本点到超平面的投影才能较大的体现它们原本的特征
2、最大可分性：样本点在这个超平面上的投影能尽可能分开.

我们除了想要新数据尽可能多的保留原数据的信息以外，其最终的目的还是放回模型中进行训练，使得模型的整体效果有一个提升。而要想新数据能够在模型训练上优于原数据，那么在拥有原数据大部分信息的同时，也要使各个样本之间有较大的区分度，所以我们要让样本点在这个超平面的投影尽可能的分开

基于最近重构性和最大可分性，我们能得到主成分分析的两种推导式，有趣的是，这两种推导是等价的。
我们先从最近重构性来推导：
假定数据样本进行了中心化，即 ∑ i x i = 0 {\textstyle \sum_{i}^{}} x_{i}=0 ∑i ​x i ​=0；再假定投影变换后得到的新坐标系为{ w 1 , w 2 , ⋯ , w d } \left { w_{1},w_{2},\cdots ,w_{d} \right }{w 1 ​,w 2 ​,⋯,w d ​}，其中w i w_{i}w i ​是标准正交基向量，∥ w i ∥ 2 = 1 \left \| w_{i} \right \|{2}=1 ∥w i ​∥2 ​=1，w i T w j = 0 w{i}^{T}w_{j}=0 w i T ​w j ​=0 ( i ≠ j ) \left ( i\ne j \right )(i ​=j ).若丢弃新坐标系中的部分坐标，即将维度降低到 d ′ < d d^{‘}，则样本点x i x_{i}x i ​在低维坐标系中的投影是z i = ( z i 1 ; z i 2 ; ⋯ ; z i d ′ ) z_{i}=\left ( z_{i1};z_{i2};\cdots ;z_{id^{‘}} \right )z i ​=(z i 1 ​;z i 2 ​;⋯;z i d ′​)，其中z i j = w j T w i z_{ij}=w_{j}^{T}w_{i}z i j ​=w j T ​w i ​是x i x_{i}x i ​在低维坐标系下第j j j维的坐标.若基于z i z_{i}z i ​来重构x i x_{i}x i ​，则会得到x ^ i = ∑ j = 1 d ′ z i j w j . \hat {x}{i}=\textstyle \sum{j=1}^{d^{‘}}z_{ij}w_{j}.x ^i ​=∑j =1 d ′​z i j ​w j ​.

考虑到整个训练集，原样本点x i x_{i}x i ​与基于投影重构的样本点x ^ i \hat {x}{i}x ^i ​之间的距离为∑ i = 1 m ∥ ∑ j = 1 d ′ z i j w j − x i ∥ 2 2 = ∑ i = 1 m z i T z i − 2 ∑ i = 1 m z i T W T x i + c o n s t α − t r ( W T ( ∑ i m x i x i T ) W ) \sum{i=1}^{m} \left \| \sum_{j=1}^{d^{‘}}z_{ij}w_{j}-x_{i} \right \| {2}^{2} =\sum{i=1}^{m} z_{i}^{T}z_{i}-2\sum_{i=1}^{m}z_{i}^{T}W^{T}x_{i}+const\alpha -tr\left ( W^{T}\left ( \sum_{i}^{m}x_{i}x_{i}^{T} \right ) W \right )i =1 ∑m ​∥∥∥∥∥∥​j =1 ∑d ′​z i j ​w j ​−x i ​∥∥∥∥∥∥​2 2 ​=i =1 ∑m ​z i T ​z i ​−2 i =1 ∑m ​z i T ​W T x i ​+c o n s t α−t r (W T (i ∑m ​x i ​x i T ​)W )其中c o n s t const c o n s t为一个常数
根据最近重构性，上式应被最小化，考虑到w j w_{j}w j ​是标准正交基，∑ i x i x i T \sum_{i}x_{i}x_{i}^{T}∑i ​x i ​x i T ​是协方差矩阵，有
m i n W − t r ( W T X X T W ) (1) \underset{W}{min} -tr\left ( W^{T}XX^{T}W \right ) \tag{1}W min ​−t r (W T X X T W )(1 ) s . t . W T W = I s.t. \quad W^{T}W=I s .t .W T W =I 这就是主成分分析的优化目标
从最大可分性出发，能得到主成分分析的另一种解释.我们知道，样本点x i x_{i}x i ​在新空间中超平面上的投影是W T x i W^{T}x_{i}W T x i ​，若所有样本点的投影尽可能分开，则应该使投影后样本点的方差最大化
投影后样本点的方差是∑ i W T x i x i T W \sum_{i}W^{T}x_{i}x_{i}^{T}W ∑i ​W T x i ​x i T ​W，于是优化目标可写为m a x W t r ( W T X X T W ) (2) \underset{W}{max}\quad tr\left ( W^{T}XX^{T}W \right ) \tag{2}W ma x ​t r (W T X X T W )(2 ) s . t . W T W = I s.t. \quad W^{T}W=I s .t .W T W =I 显然，式（1）和（2）等价
对式（1）或（2）使用拉格朗日乘子法可得X X T W = λ W XX^{T}W=\lambda W X X T W =λW 于是，只需对协方差矩阵X X T XX^{T}X X T进行特征值分解，将求得的特征值排序：λ 1 ≥ λ 2 ≥ ⋯ ≥ λ d \lambda {1} \ge \lambda {2} \ge \cdots \ge \lambda_{d}λ1 ​≥λ2 ​≥⋯≥λd ​，在取前d ′ d^{‘}d ′个特征值对应的特征向量构成W = ( w 1 , w 2 , ⋯ , w d ′ ) . W=\left ( w_{1},w_{2},\cdots ,w_{d^{‘}} \right ).W =(w 1 ​,w 2 ​,⋯,w d ′​).这就是主成分分析的解

优点
1、得到的主成分之间是不相关的
2、用较少综合变量保留尽可能多的原始信息
3、简化计算过程
缺点
1、所提取的前几个主成分的累计贡献率需达到一个较高水平
2、通过主成分所得新数据的各特征解释性差
3、主成分分析法只能应用于数据的线性降维

假定m m m个样本在原始空间的距离矩阵为D ∈ R m × m D\in \mathbb{R} ^{m\times m}D ∈R m ×m，其第i i i行j j j例的元素d i s t i j dist_{ij}d i s t i j ​为样本x i x_{i}x i ​到x j x_{j}x j ​的距离.我们的目标是获得样本在d ′ d^{‘}d ′维空间的表示Z ∈ R d ′ × m \mathrm {Z} \in \mathbb{R} ^{d^{‘}\times m}Z ∈R d ′×m，d ′ ≤ d d^{‘}\le d d ′≤d，且任意两个样本在d ′ d^{‘}d ′维空间中的欧式距离等于原始空间中的距离，即∥ z i − z j ∥ = d i s t i j \left \| z_{i}-z_{j} \right \| =dist_{ij}∥z i ​−z j ​∥=d i s t i j ​.

令B = Z T Z ∈ R m × m \mathrm {B}=\mathrm {Z}^{T}\mathrm {Z}\in \mathbb{R} ^{m\times m}B =Z T Z ∈R m ×m，其中B \mathrm {B}B为降维后样本的内积矩阵，b i j = z i T z j b_{ij}=z_{i}^{T}z_{j}b i j ​=z i T ​z j ​，有d i s t i j 2 = ∥ z i ∥ 2 + ∥ z j ∥ 2 − 2 z i T z j dist_{ij}^{2}=\left \| z_{i} \right \| ^{2}+\left \| z_{j} \right \| ^{2}-2z_{i}^{T}z_{j}d i s t i j 2 ​=∥z i ​∥2 +∥z j ​∥2 −2 z i T ​z j ​ = b i i + b j j − 2 b i j (3) =b_{ii}+b{jj}-2b{ij}\tag {3}=b i i ​+b j j −2 b i j (3 )
为便于讨论，令降维后的样本Z \mathrm {Z}Z被中心化，即∑ i = 1 m z i = 0 {\textstyle \sum_{i=1}^{m}z_{i}}=0 ∑i =1 m ​z i ​=0.显然，矩阵B \mathrm {B}B的行与列之和均为零，即∑ i = 1 m b i j = ∑ j = 1 m b i j = 0. 易 知 {\textstyle \sum_{i=1}^{m}b_{ij}}={\textstyle \sum_{j=1}^{m}b_{ij}}=0.易知∑i =1 m ​b i j ​=∑j =1 m ​b i j ​=0 .易知 ∑ i = 1 m d i s t i j 2 = t r ( B ) + m b j j (4) \sum {i=1}^{m}dist{ij}^{2}=tr\left ( \mathrm {B} \right ) +mb_{jj}\tag {4}i =1 ∑m ​d i s t i j 2 ​=t r (B )+m b j j ​(4 ) ∑ j = 1 m d i s t i j 2 = t r ( B ) + m b i i (5) \sum {j=1}^{m}dist{ij}^{2}=tr\left ( \mathrm {B} \right ) +mb_{ii}\tag {5}j =1 ∑m ​d i s t i j 2 ​=t r (B )+m b i i ​(5 ) ∑ i = 1 m ∑ j = 1 m d i s t i j 2 = 2 m t r ( B ) (6) \sum {i=1}^{m}\sum {j=1}^{m}dist_{ij}^{2}=2mtr\left ( \mathrm {B} \right ) \tag {6}i =1 ∑m ​j =1 ∑m ​d i s t i j 2 ​=2 m t r (B )(6 )
其中t r ( ⋅ ) tr\left ( · \right )t r (⋅)表示矩阵的迹(trace)，t r ( B ) = ∑ i = 1 m ∥ z i ∥ 2 tr\left ( \mathrm {B} \right )={\textstyle \sum_{i=1}^{m}\left \| z_{i} \right \|}^{2}t r (B )=∑i =1 m ​∥z i ​∥2.令d i s t i ⋅ 2 = 1 m ∑ j = 1 m d i s t i j 2 (7) dist_{i·}^{2}=\frac{1}{m} \sum {j=1}^{m}dist{ij}^{2}\tag {7}d i s t i ⋅2 ​=m 1 ​j =1 ∑m ​d i s t i j 2 ​(7 ) d i s t ⋅ j 2 = 1 m ∑ i = 1 m d i s t i j 2 (8) dist_{·j}^{2}=\frac{1}{m} \sum {i=1}^{m}dist{ij}^{2}\tag {8}d i s t ⋅j 2 ​=m 1 ​i =1 ∑m ​d i s t i j 2 ​(8 ) d i s t ⋅ ⋅ 2 = 1 m 2 ∑ i = 1 m ∑ j = 1 m d i s t i j 2 (9) dist_{··}^{2}=\frac{1}{m^{2}} \sum {i=1}^{m}\sum {j=1}^{m}dist_{ij}^{2}\tag {9}d i s t ⋅⋅2 ​=m 2 1 ​i =1 ∑m ​j =1 ∑m ​d i s t i j 2 ​(9 )
由式(3)和式(4)~(9)可得b i j = − 1 2 ( d i s t i j 2 − d i s t i ⋅ 2 − d i s t ⋅ j 2 + d i s t ⋅ ⋅ 2 ) (10) b_{ij}=-\frac{1}{2}\left ( dist_{ij}^{2}-dist_{i·}^{2}-dist_{·j}^{2}+dist_{··}^{2} \right )\tag {10}b i j ​=−2 1 ​(d i s t i j 2 ​−d i s t i ⋅2 ​−d i s t ⋅j 2 ​+d i s t ⋅⋅2 ​)(1 0 )
由此即可通过降维前后保持不变的距离矩阵D \mathrm {D}D求取内积矩阵B \mathrm {B}B.

对矩阵B \mathrm {B}B做特征分解，B = V Λ V T \mathrm {B}=\mathrm {V}\mathrm {\Lambda }\mathrm {V}^{T}B =V ΛV T，其中Λ = d i a g ( λ 1 , λ 2 , ⋯ , λ d ) \Lambda =diag\left ( \lambda {1},\lambda {2},\cdots ,\lambda_{d} \right )Λ=d i a g (λ1 ​,λ2 ​,⋯,λd ​)为特征值构成的对角矩阵，λ 1 ≥ λ 2 ≥ ⋯ ≥ λ d \lambda {1} \ge \lambda {2}\ge \cdots \ge \lambda_{d}λ1 ​≥λ2 ​≥⋯≥λd ​，Λ \Lambda Λ为特征向量矩阵.假定其中有d ∗ d^{}d ∗个非零特征值，它们构成对角矩阵Λ ∗ = d i a g ( λ 1 , λ 2 , ⋯ , λ d ∗ ) \Lambda _{}=diag\left ( \lambda {1},\lambda {2},\cdots ,\lambda_{d^{}} \right )Λ∗​=d i a g (λ1 ​,λ2 ​,⋯,λd ∗​)，令V ∗ V_{}V ∗​表示相应的特征向量矩阵，则Z \mathrm {Z}Z可表达为Z = Λ ∗ 1 / 2 V ∗ T ∈ R d ∗ × m (11) \mathrm {Z}=\Lambda_{}^{1/2}\mathrm {V}_{}^{T}\in \mathbb{R} ^{d^{*}\times m}\tag {11}Z =Λ∗1 /2 ​V ∗T ​∈R d ∗×m (1 1 )
在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必严格相等.此时可取d ′ ≪ d d^{‘}\ll d d ′≪d个最大特征值构成对角矩阵Λ ~ = d i a g ( λ 1 , λ 2 , ⋯ , λ d ′ ) \tilde{\Lambda} =diag\left ( \lambda {1},\lambda {2},\cdots ,\lambda_{d^{‘}} \right )Λ~=d i a g (λ1 ​,λ2 ​,⋯,λd ′​)，令V ~ \tilde{\mathrm {V}}V ~表示相应的特征向量矩阵，则Z \mathrm {Z}Z可表达为Z = Λ ~ 1 / 2 V ~ T ∈ R d ′ × m (12) \mathrm {Z}=\tilde{\Lambda}^{1/2}\tilde{\mathrm{V}}^{T}\in \mathbb{R} ^{d^{‘}\times m}\tag {12}Z =Λ~1 /2 V ~T ∈R d ′×m (1 2 )

优点
1、计算效率快
缺点
1、对于流形复杂的数据，MDS降维会损失较多原数据信息

等度量映射(Isometric Mappin ，简称 somap)的基本出发点，是认为低维流嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维嵌入流行上是不可达的.如图1所示，低维嵌入流行上两点间的距离是”测地线”（geodesic）距离：想象一只虫子从一点爬到另一点，如果它不能脱离曲面行走，那么图1（a）中红色曲线是距离最短的路径，即环形曲面上的测地线，测地线距离是两点之间的本真距离.显然，直接在高维空间中计算直线距离是不恰当的.

(a)测地线距离与高维直线距离

(b)测地线距离与近邻距离 图1 低维嵌入流形上的测地线距离(红色)不能用高维空间的直线距离计算，但能用近邻距离来近似

那么，如何计算测地线距离呢？这时我们可利用流行在局部上与欧式空间同胚这个性质，对每个点基于欧式距离找出近邻点，然后就能建立一个近邻连接图，图中近邻点之间存在连接，而非近邻点之间不存在连接，于是，计算两点之间测地线距离的问题，就转变为计算近邻连接图上两点之间的最短路径问题.如图1(b)可看出，基于近邻距离逼近能获得低维流行上测地线距离很好的近似.

计算两点间的最短路径（在近邻连接图上计算两点间的最短路径，可采用著名的Dijkstra算法或Floyd算法），在得到任意两点的距离后，就可通过MDS方法来获得样本点在低维空间中的坐标.

优点
1、当数据各个特征线性不可分时，Isomap降维通常会有一个较好的结果
2、对于低维流形复杂的数据进行降维时，Isomap能保留较多原数据的信息
缺点
1、计算效率低下

Original: https://blog.csdn.net/woor_/article/details/122488350
Author: woor_
Title: 机器学习数据预处理——降维