数据降维以及相关面试题

数据降维以及相关面试题

降维

所谓的降维就是指采用某种映射方法,将原高维空间中的数据点映射到低维度的空间中。那么为什么我们需要对数据降维?

  • 数据维度太高,样本量稀疏,给机器学习算法带来巨大的时间性能花费。
  • 有些特征之间存在相关关系,增加了分析难度,所以用更少数量的不相关的特征代替。
    接下来介绍一下常用降维方法。

同时对降维性能的评估,一般比较降维前后学习器和性能,进一步如果降维到了二维或者三维,则可以通过可视化技术 来直观判断。

PCA

如果我们要把原数据投影到一个低维空间,怎么衡量我们投影后的数据好坏呢?
我们要认识到数据的方差代表着数据集的区分度,也就是蕴含‘信息’的程度,那么这就可以得到PCA的第一种推导方式,最大化方差。以下过程都假设新坐标为正交基。样本再w下坐标即为《数据降维以及相关面试题》

方差最大化

协方差矩阵可以写为
《数据降维以及相关面试题》
其对角线分别对应各个变量的方差,而第 i 行 j 列和 j 行 i 列元素相同,表示 i 和 j 两个变量的协方差。如果投影后数据的协方差矩阵除对角线外的其它元素化为 0,并且在对角线上将元素按大小从上到下排列(变量方差尽可能大),这样我们就达到了优化目的。
而新的协方差矩阵和旧协方差矩阵关系如下
《数据降维以及相关面试题》
那么要找的 投影矩阵P 是能让原始协方差矩阵对角化的 P。换句话说,优化目标变成了寻找一个矩阵 P,满足 P C P T PCP^T PCPT 是一个对角矩阵,并且对角元素按从大到小依次排列,那么 P 的前 K 行就是要寻找的基,用 P 的前 K 行组成的矩阵乘以 X 就使得 X 从 N 维降到了 K 维并满足上述优化条件。
又因为协方差矩阵是实对称矩阵,拥有如下性质

  • 实对称矩阵不同特征值对应的特征向量必然正交。
  • 设特征值 λ \lambda λ 个数为 r,则必然存在 r 个线性无关的特征向量对应于 λ \lambda λ ,因此可以将这 r 个特征向量单位正交化
    所以

《数据降维以及相关面试题》
E为特征向量构成的矩阵,所以我们要找的投影矩阵 P P P = E T E^T ET

上面我们是基于性质的推导,当然也可以从纯数学的角度推导
《数据降维以及相关面试题》
构造拉格朗日函数
《数据降维以及相关面试题》
对w求导得
《数据降维以及相关面试题》
于是对协方差矩阵特征值分解排序就是w
另外可以得到
《数据降维以及相关面试题》
也就是说方差就是特征值。

重构损失最小

重构性要求投影后得点再还原成原坐标系时和原来的差异最小,那么总距离为
《数据降维以及相关面试题》
最小化上式
《数据降维以及相关面试题》
推导出了和最大方差分析一样的结果。

求解过程

设有 m 条 n 维数据。

1.将原始数据按列组成 n 行 m 列矩阵 X;
2.将 X 的每一行进行零均值化,即减去这一行的均值;
3.求出协方差矩阵 《数据降维以及相关面试题》
4.求出协方差矩阵的特征值及对应的特征向量;
5.将特征向量按对应特征值大小从上到下按行排列成矩阵,取前 k 行组成矩阵 P;
6.《数据降维以及相关面试题》 即为降维到 k 维后的数据。

投影后数据的一些性质

《数据降维以及相关面试题》
推导分析可得出,特征值和方差的关系。
《数据降维以及相关面试题》
也就是说
《数据降维以及相关面试题》

细节

1.零均值化
当对训练集进行 PCA 降维时,也需要对验证集、测试集执行同样的降维。而对验证集、测试集执行零均值化操作时,均值必须从训练集计算而来,不能使用验证集或者测试集的中心向量。那样造成数据泄露,引入了验证集的信息。
2.与SVD的联系
首先认识到一点,特征值和特征向量是针对方阵才有的,而我们上面做的是协方差矩阵得特征分解,而对任意形状的矩阵都可以做奇异值分解。
《数据降维以及相关面试题》
进一步我们还可以看出我们的 A A T AA^T AAT特征值等于 A A A奇异值的平方
pca可以用svd的右奇异矩阵降维,不用直接解 X X T XX^T XXT的特征方程
《数据降维以及相关面试题》
而实际上 Sklearn 的 PCA 就是用 SVD 进行求解的,原因有以下几点:

1.当样本维度很高时,协方差矩阵计算太慢;
2.方矩特征值分解计算效率不高;
3.SVD 出了特征值分解这种求解方式外,还有更高效更准确的迭代求解方式,避免了 X X T XX^T XXT的计算;
4.其实 PCA 与 SVD 的右奇异向量的压缩效果相同。

核化处理

朴素的PCA和既假设函数映射是线性的。实际上我们需要非线性映射才可能找到恰当的低维嵌入。回顾PCA中出现了协方差矩阵,既出现了内积运算,那么很自然的可以引入核函数。把样本先映射到高维空间再实施降维。
设Z为X在高维空间的投影
《数据降维以及相关面试题》
原推导过程变化为
《数据降维以及相关面试题》
这样的降维后坐标为
《数据降维以及相关面试题》
KPCA需要对所有样本求和,计算开销比较大。

LDA

LDA最开始接触是作为一个分类算法。
其思想很朴素,设法将样本投影到一条直线上,使得同类样本尽量靠近,异类样本尽量远离。
《数据降维以及相关面试题》

原理推导

欲使同类数据足够接近,则类内数据的协方差应该足够小;不同类数据应该足够大,那么类的平均值(中心)应该足够远,那么想要最大化的目标就为:
(这个公式与从贝叶斯最优推导出的公式互为倒数)
《数据降维以及相关面试题》
定义类内散度,统计每个类自身分布差异
《数据降维以及相关面试题》
再定义类间散度,考虑类之间的差别。
《数据降维以及相关面试题》
则上式最大化目标可重写为
《数据降维以及相关面试题》
由于分子和分母都是关于w的二次项,不失一般性,我们可以设
《数据降维以及相关面试题》
则原式继续化为
《数据降维以及相关面试题》
拉格朗日乘子法,求导可得
《数据降维以及相关面试题》
那么具体的求解步骤为
《数据降维以及相关面试题》
多分类状况
先定义全局散度
《数据降维以及相关面试题》
均值为全部数据的均值,多分类的类间散度为
《数据降维以及相关面试题》
最后求解仍为
《数据降维以及相关面试题》
因为W可被视为一个投影矩阵,把X投影到N-1维(因为 S b S_b Sb矩阵秩为N-1,总均值和n-1个 u i u_i ui可表示出剩下那个),所以可当作降维算法。

两者对比

两者当数据不是高斯分布时候,效果不好。
原始数据主要是根据均值来划分的,此时LDA降维效果很好,但是PCA效果就很差。
原始数据主要是方差不同,那么PCA降维效果比较好,而LDA降维效果比较差。并且LDA降维后取决于类别数,容易维度过少。

MDS

MDS算法描述如下
《数据降维以及相关面试题》
原理是维持降维前后样本的距离不变,计算出对应的内积矩阵,然后进行特征值分解得到低维坐标。

LLE

ISOMAP

ISOMAP的流程如下
《数据降维以及相关面试题》
不同欧式距离,用迪杰斯特拉算法得到测地线距离再用MDS求解。

对比总结

    原文作者:Sigyc
    原文地址: https://blog.csdn.net/github_31101389/article/details/106738224
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞