201119西瓜书系列博客---10、降维与度量学习
一、总结
一句话总结：
【降维】是【将原高维空间嵌入到一个合适的低维子空间中】，接着在低维空间中进行学习任务；
【度量学习】则是【试图去学习出一个距离度量来等效降维的效果】，两者都是为了解决维数灾难带来的诸多问题。
也许大家最后心存疑惑，那kNN呢，为什么一开头就说了kNN算法，但是好像和后面没有半毛钱关系？正是因为在降维算法中，低维子空间的维数d’通常都由人为指定，因此我们需要使用一些低开销的学习器来选取合适的d’，kNN这家伙懒到家了根本无心学习，在训练阶段开销为零，测试阶段也只是遍历计算了距离，【因此拿kNN来进行交叉验证就十分有优势了】~同时降维后样本密度增大同时距离计算变易，更为kNN来展示它独特的十八般手艺提供了用武之地。
10.1 k近邻学习
10.2 低维嵌入
经典降维方法：多维缩放(MDS)
10.3 主成分分析
10.4 核化线性降维
核化主成分分析(KPCA)
10.5 流形学习
10.5.1 等度量映射
Isomap算法基本过程
10.5.2 局部线性嵌入（LLE）
LLE算法基本过程
10.6 度量学习
1、【10.1、k近邻学习】 ？
【k近邻学习（knn）】是一种监督学习算法，它直接使用测试样本和训练样本，没有显示的训练过程
工作机制如下：【给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个邻居的信息来进行预测】。
knn为【懒惰学习】的著名代表，此类学习在训练阶段仅仅是把训练样本保存起来，训练时间开销为0，待收到测试样本之后再进行处理。
2、【10.1、k近邻学习】 knn算法的核心？
knn算法的核心在于【k值的选取和距离的度量】，心中有图
3、【10.2、低维嵌入】 ？
上一小节的讨论是基于一个重要假设：【任意测试样本x附近任意小的θ距离范围内总能找到一个训练样本】，即训练样本的采样密度足够大。但是，这种假设在现实任务中常常很难满足，若属性维数较多时，要保证每个测试样本都有对应的训练样本，对样本数量的要求非常大。
这种在高维情形下出现的【样本稀疏、距离计算困难等问题】，是所有机器学习方法共同面临的严重阻碍，被称为【维数灾难】。
一个重要途径是【降维】，即通过某种数学变换【将原始高维属性空间转变为一个低维子空间】，这个子空间中样本密度大幅度提高，距离计算也更为容易。
高维数据样本中，与学习任务密切相关的某个低维分布即为【高维空间的一个低维嵌入(embedding)】。
4、【10.2、低维嵌入】 经典降维方法：多维缩放(MDS)？
不管是使用核函数升维还是对数据降维，我们都希望【原始空间样本点之间的距离在新空间中基本保持不变】，这样才不会使得原始空间样本之间的关系及总体分布发生较大的改变。
“多维缩放”（MDS）正是基于这样的思想，【MDS要求原始空间样本之间的距离在降维后的低维空间中得以保持】。
5、【10.3、主成分分析】 ？
主成分分析(PCA)是一种【最常用的降维方法】。
不同于【MDS采用距离保持】的方法，【主成分分析直接通过一个线性变换】，将原始空间中的样本投影到新的低维空间中。
简单来理解这一过程便是：PCA采用一组新的基来表示样本点，其中【每一个基向量都是原来基向量的线性组合】，【通过使用尽可能少的新基向量来表出样本】，从而达到降维的目的。
假设使用d’个新基向量来表示原来样本，实质上是【将样本投影到一个由d’个基向量确定的一个超平面上（即舍弃了一些维度）】。
6、【10.3、主成分分析】 要用一个超平面对空间中所有高维样本进行恰当的表达，最理想的情形是：【若这些样本点都能在超平面上表出且这些表出在超平面上都能够很好地分散开来】？
但是【一般使用较原空间低一些维度的超平面来做到这两点十分不容易】，因此我们退一步海阔天空，要求这个超平面应具有如下两个性质：
【最近重构性】：【样本点到超平面的距离足够近】，即尽可能在超平面附近；
【最大可分性】：样本点在超平面上的【投影尽可能地分散开来】，即投影后的坐标具有区分性。
7、【10.4、核化线性降维】 ？
之前在支持向量机那一章中，【SVM在处理非线性可分的样本时，使用核函数将样本投影到高维特征空间，再对样本在高维特征空间中使用超平面划分】。
这里也是同样的问题：若我们的样本数据点本身就不是线性分布，那还如何用一个超平面去近似表出呢？因此也就引入核函数，【即先将样本映射到高维空间，再在高维空间寻找线性降维的方法】。
8、【10.4、核化线性降维】 核化主成分分析(KPCA)？
【核化】：样本映射到【高维空间】
【主成分分析】：在高维空间使用的线性降维的方法
若核函数已知，【即知道如何将低维的坐标变换为高维坐标】，这时我们只需先将数据映射到高维特征空间，再在高维空间中运用PCA即可。
一般情况下，我们并不知道核函数的具体的映射规则，例如Sigmoid、高斯核等，我们【只知道如何计算高维空间中的样本内积】，这就引出了KPCA的一个重要创新之处：【空间中的任一向量，都可以由该空间的所有样本表示】。
9、【10.5、流形学习】 ？
【流形学习】是一类借鉴了【拓扑流形概念的降维方法】，流形是指在局部与欧氏空间同胚的空间，即它在局部具有欧氏空间的性质，能用欧氏距离进行距离计算。
这样即使高维空间的分布十分复杂，但是在局部上依然满足欧式空间的性质，基于流形学习的降维正是这种【邻域保持】的思想。
其中【等度量映射（Isomap）】试图在降维前后保持邻域内【样本之间的距离】，而【局部线性嵌入（LLE）】则是保持邻域内【样本之间的线性关系】
10、【10.5、流形学习】 等度量映射？
等度量的基本出发点是：认为低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维嵌入流形上是不可达的。
【因此利用流形在局部上与欧式空间同胚的性质，可以使用近邻距离来逼近测地线距离】，即对于一个样本点，它与近邻内的样本点之间是可达的，且距离使用欧式距离计算，这样整个样本空间就形成了一张近邻图，高维空间中两个样本之间的距离就转为计算近邻连接图上两点间的【最短路径问题】。
可采用著名的Dijkstra算法或Floyd算法计算最短距离，【得到高维空间中任意两点之间的距离后便可以使用MDS算法来其计算低维空间中的坐标】。
11、【10.6、度量学习】 ？
前面讨论的降维方法都是为了【应对维数灾难而提出的方法】，即都试图将原空间投影到一个合适的低维空间中，接着在低维空间中进行学习任务从而产生比较好的性能。
寻找合适的空间，实质上就是在寻找一个合适的距离度量。事实上，【不管高维空间还是低维空间都潜在对应着一个距离度量，那可不可以直接学习出一个距离度量来等效降维呢】？这便是【度量学习(metric learning)的基本动机】。
二、10、降维与度量学习
转自或参考：西瓜书学习笔记——第十章：降维与度量学习_Andrewings-CSDN博客
https://blog.csdn.net/shichensuyu/article/details/95355529