ML——降维与度量学习

KNN学习

k近邻（KNN）学习是一种常用的监督学习方法，可用于分类与回归任务中。基本思想是：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息进行预测。

KNN分类

通常，在分类任务中使用“投票法”，即选择k个样本中出现最多的类别标记作为预测结果；在回归任务中使用“平均法”，即将k个样本的实值输出标记的平均值作为预测结果。还可基于距离远近加权平均或加权投票。距离越近样本权重越大。

k近邻法三要素

距离度量、k值的选择及分类决策规则是k近邻法的三个基本要素。距离度量可计算测试实例与每个训练实例的距离，根据k值选择k个最近邻点，最后根据分类决策规则将测试实例分类。

距离度量：特征空间中两个样本点的距离可看成是两个样本点相似程度的反映。样本点的距离定义为：

当p=1时，称为曼哈顿距离（Euclidean distance）；当p=2时，称为欧氏距离（Euclidean distance）；当p=∞时，它是各个坐标距离的最大值。

k值选择：k值的选择会对k近邻法的结果产生重大影响。一般k值取一个比较小的数值，通常采用交叉验证法选取最优的k值。

k值选取对knn的影响

分类决策规则：KNN中的分类决策规则往往是多数表决，即由输入样本的k个近邻的训练样本中的多数类，决定输入样本的类。

KNN算法流程：

优点：1）理论成熟，思想简单，既可做回归也可做分类，且适用于非线性分类；2）训练时间复杂度低，仅为O(n)(n为特征数)；3）与NB相比对数据没有假设，准确度高，对异常点不敏感等。

缺点：1）当特征数很多时，计算量巨大；2）样本不平衡时，对稀有类别的预测准确率降低；3）使用懒惰学习，预测时速度要慢于LR之类的算法等。

低维嵌入

样本的特征数称为维数，在高维情形下出现的样本数据稀疏、距离计算困难等问题常会导致“维数灾难”。而缓解维数灾难的一个重要途径就是降维（维数约简），即通过某种数学变换将原始高维属性空间转变为一个低维子空间。在这个子空间中，样本密度大幅提高，同时简化距离计算，高维空间中的样本点在低维嵌入子空间中更易学习。

低维嵌入表示

MDS算法

多维缩放（MDS）算法是一种经典的降维方法，它要求原始空间样本之间的距离在降维后的低维空间中得以保持。

假设m个样本在原始空间距离矩阵为，其第i行j列元素为样本到的距离，要获得样本在d'维空间的表示Z(d'×m维，d'<=d)，且任意两样本在d'维空间的欧氏距离等于原始空间中的距离，。令，其中B为降维后样本的内积矩阵，，有

(1)

为便于讨论，令降维后的样本Z被中心化，即。显有B的行与列之和均为0，即，易知

由上式可得。逐一计算，就得到降维后低维空间中内积矩阵B，只需对B进行特征值分解就可得到Z。MDS算法流程如下：

MDS算法

主成分分析（PCA）

PCA是最常用的一种线性降维方法，如图要将数据从二维降到一维，用某一个维度方向代表这两个维度的数据。图中列出的两个向量方向u1和u2，直观来看u1更好，因为样本点到它的距离更近，或者说样本点在这个直线上的投影能尽可能的分开。这也就得到了PCA两种等价推导：

最近重构性：样本点到这个超平面的距离都足够近；

最大可分性：样本点在超平面上的投影尽可能分散开来。

虽然以上两种方法从不同的出发点来定义优化问题中的目标函数，但最终它们都得到了相同的优化问题：

优化目标

使用Lagrange乘子法求解上述优化问题得：

故只需对协方差矩阵进行特征值分解求解出W。PCA算法流程如下：

PCA算法流程

有时候不指定降维后d'的值，而是指定一个降维到主成分比重阈值t，。若d个特征值为，则d'可通过下式取得：

优点：1）仅以方差衡量信息，不受数据集以外因素的影响；2）各主成分之间正交，消除原始数据成分间相互影响的因素；3）计算方法简单，易于实现。

缺点：1）主成分各特征维度含义解释性差；2）丢弃的方差小的非主成分可能含有样本差异的重要信息。

核化线性降维

线性降维方法假设从高维空间到低维空间的函数映射是线性的，然而现实任务中可能需要非线性映射才能找到恰当的低维嵌入，核主成分分析（KPCA）就是一种基于核技巧的非线性降维方法。

若核函数形式已知，即知晓如何将低维的坐标变换为高维坐标，此时只需先将数据映射到高维特征空间，再在高维空间中运用PCA即可。但一般情形下并不知道核函数具体映射规则，只知如何计算高维空间中的样本内积。对此，KPCA的创新之处在于：空间中的任一向量，都可由该空间中的所有样本线性表示。

假定是由原始特征空间中的样本点通过映射产生，即，高维特征空间中的投影向量可用所有高维样本点线性表出，接着代入PCA求解问题：

由上式发现只需对核矩阵K进行特征分解，便可得出投影向量wi对应的系数向量，因此取K最大的d'个特征值对应的特征向量即可。对新样本x，其降维后的坐标为：

由上式也可以看出，为获得投影后的坐标，KPCA需对所有样本求和，其计算开销较大。

流形学习

设是一个低维流形，是一个光滑嵌入，其中。数据集是随机生成的，且经过f映射为观察空间的数据。流形学习就是在给定观察样本集的条件下重构f和，以实现维数约简或者数据可视化。下面介绍几种代表算法。

等度量映射（Isomap）

Isomap引入测地线距离来表示潜在流形上点与点之间的距离，并在降维过程中保持该距离不变。如图(a)中的红色线段表示的就是流形上的测地线距离。Isomap建立在MDS的基础上，保留的是非线性数据的本质几何结构，即任意点对之间的测地线距离。

为计算测地线距离，可利用流形在局部上与欧式空间同胚的性质，对每个点基于欧式空间距离找出其近邻点，在每个数据点和其近邻点间添加加权边，得到一个连接图。距离较远的数据点间的测地线距离可通过最短距离近似。

Isomap算法流程

在计算近邻时，若近邻范围指定得较大，则距离较远的点可能被误认为近邻，出现“短路”；若近邻范围指定的较小，则图中有些区域可能与其他区域不存在连接，出现“断路”。都会误导后面计算最短路径。

局部线性嵌入（LLE）

与Isomap试图保持近邻样本间的距离不同，LLE试图保持近邻内样本间的线性关系。

高维空间的样本重构关系在低维空间中得以保持

如图，假定样本点xi的坐标能通过其近邻样本线性重构，即，LLE希望该式关系在低维空间中得以保持。

LLE算法分为两步，step1 根据近邻关系计算出所有样本的邻域重构系数w：

step2 根据邻域重构系数不变，求解低维坐标：

利用矩阵M，优化问题可重写为：

对上式进行特征值分解，M最小的d'个特征值对应的特征向量组成的矩阵即为。LLE具体算法流程如下：

LLE具体算法流程

度量学习

在ML中，对高维数据进行降维是希望找到一个合适的低维空间，在此空间中进行学习能比原始空间性能更好。寻找合适的空间，实质上就是找一个合适的距离度量，因此衍生了度量学习。

欲对距离度量进行学习，须有便于学习的距离度量表达形式。对d维样本xi和xj，它们之间的平方欧式距离记做：

其中表示与在第k维上的距离。若假定不同属性重要性不同，可引入属性权重w得：

其中是一个对角矩阵，。

此时各个属性之间都是相互独立无关的，但现实中往往存在属性相关的情形，因此将W替换为半正定对称阵，得到马氏距离：

标准马氏距离中M是协方差矩阵的逆，马氏距离是一种考虑属性相关且尺度无关（无需去量纲）的距离度量：

矩阵M也叫“度量矩阵”，度量学习就是对M进行学习，为保证距离度量的非负性与对称性，M必须为（半）正定对称阵，即必有正交基P使得。

总结

降维是将高维空间嵌入到一个合适的低维子空间中，接着在低维空间中进行学习任务；

度量学习则是试图去学习出一个距离度量来等效降维的效果；

两者都是为了解决维数灾难引发的问题。在降维算法中，低维子空间的维数d’通常人为指定，因此需用一些低开销的学习器选取合适的d’，kNN属于懒惰学习，在训练阶段开销为零，测试阶段也只是遍历计算了距离，因此拿kNN来进行交叉验证就十分有优势，同时降维后样本密度增大同时距离计算变易。

周志华《机器学习》

https://blog.csdn.net/u011826404/article/details/72123031

https://www.cnblogs.com/pinard/category/894692.html