机器学习第十章

假定m个样本在原始空间的距离矩阵为 $D\in R^{m*m}$ ，其中第i行j列的元素 $dist_{ij}$ 为样本 $x_i$ 到 $x_j$ 的距离，目标是要获取样本在 ${d}'$ 维空间的表示 $Z\in R^{{d}'*m},{d}'\leq d$ ，且任意两个样本在 ${d}'$ 维空间中的欧氏距离等于原始空间中的距离，即 $\left \| z_i-z_j \right \|=dist_{ij}$ 。

令 $B=Z^T Z\in R^{m*m}$ ，其中B为降维后样本的内积矩阵 $b_{ij}=z_i^Tz_j$ ，那么可以得到：

在令降维后的样本Z中心化，那么矩阵B的行和列之和都为0，可以得到：

联立上述式子可以得到

由该式子通过降维前后保持不变的距离矩阵D求取内积矩阵B，在对矩阵B进行特征值分解就可以得到Z。其算法流程为：

基于线性变换来进行降维的方法叫做线性降维方法，和MDS方法的不同之处在于对低维子空间的性质要求不同。对于降维效果的评估一般是比较降维前后学习器的性能。

三、主成分分析

主成分分析（PCA）是一种常见的降维方法。对于正交属性空间中的样本点，如果要用一个超平面多所有样本进行恰当的表达，那么这个超平面应该具有最近重构性：本点到超平面的距离足够近，即尽可能在超平面附近和最大可分性：样本点在超平面上的投影尽可能地分散开来，即投影后的坐标具有区分性。

基于最近重构性来推导，可以得到主成分分析的优化目标为：

从最大可分性出发，可以得到优化目标为：

从上述可以知道，最近重构性与最大可分性虽然从不同的出发点来定义优化问题中的目标函数，但最终这两种特性得到了完全相同的优化问题。接着可以使用拉格朗日乘子法得到 $XX^TW=\lambda W$ ，因此只需对协方差矩阵进行特征值分解即可求解出W。PCA算法的流程如下：

PCA仅需保留W与样本的均值向量即可通过简单的向量减法和矩阵-向量乘法将新样本投影至低维空间中。

四、核化线性降维

线性降维方法假设从高维空间到低维空间的函数映射是线性的，但是在现实任务中，可能需要非线性映射才能找到恰当的低维嵌入。本真低维空间指的是原本采样的低维空间。基于核技巧对线性降维方法进行核化，这是非线性降维常用的方法。

核主成分分析（KPCA）的思想为若核函数的形式已知，即我们知道如何将低维的坐标变换为高维坐标，这时我们只需先将数据映射到高维特征空间，再在高维空间中运用PCA即可。

五、流形学习

流形学习是一类借鉴了拓扑流行概念的降维方法，流形是在局部与欧氏空间同胚的空间，即它在局部具有欧氏空间的性质，能用欧氏距离来进行距离计算。

1.等度量映射

等度量映射的出发点是认为低维流形嵌入到高维空间后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维嵌入流形上是不可达的。因此利用流形在局部上与欧式空间同胚的性质，可以使用近邻距离来逼近测地线距离，即对于一个样本点，它与近邻内的样本点之间是可达的，且距离使用欧式距离计算，这样整个样本空间就形成了一张近邻图，高维空间中两个样本之间的距离就转为最短路径问题。

可采用著名的Dijkstra算法或Floyd算法计算最短距离，得到任意两点之间的距离后便可以使用MDS算法来其计算低维空间中的坐标。Isomap算法的流程如下所示：

Isomap仅得到了训练样本在低维空间的坐标，对于新样本是将训练样本的高维空间坐标作为输入、低维空间坐标作为输出，训练一个回归学习器来对新样本的低维空间坐标进行预测。

对近邻图的构建通常可以使用指定近邻点个数或者指定距离阈值 $\epsilon$ ，距离小于阈值的点被认为是近邻点，得到的近邻图叫做 $\epsilon$ 近邻图。

2.局部线性嵌入

局部线性嵌入（LEE）试图保持邻域内样本之间的线性关系，假定样本点 $x_i$ 的坐标可以通过它的邻域样本 $x_j$ ， $x_k$ ， $x_l$ 的坐标通过线性组合来表示，即 $x_i=w_{ij}x_j+w_{ik}x_k+w_{il}x_l$ ，如下图：

LEE先根据近邻关系计算出所有样本的邻域重构系数w：

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

最后可以将优化问题化简为如下的式子：

LLE算法的流程如下图所示：

六、度量学习

在机器学习中，对高维数据进行降维的主要目的是希望找到一个合适的低维空间，在此空间中进行学习能比原始空间性能更好。度量学习的基本动机是直接学习出一个合适的距离度量。

首先要学习出距离度量必须先定义一个合适的距离度量形式。对两个d维样本 $x_i$ 与 $x_j$ ，它们之间的平方欧式距离为：

若假定不同属性的重要性不同，那么可以引入属性权重w，得到如下的距离表达式：

此时各个属性之间都是相互独立无关的，但现实中往往会存在属性之间有关联的情形，比如西瓜的重量和体积两个属性。因此可以将上式的W替换为一个普通的非正定对称矩阵M，可以得到马氏距离：

M叫做度量矩阵，度量学习就是对M进行学习。对M的学习需要设置一个目标。可以把错误率这样的监督学习的目标作为度量学习的优化目标，其次还可以使用相似性来进行度量。

总结

本章主要讲解了一些经典的降维技术和度量学习，降维是将原高维空间嵌入到一个合适的低维子空间中，接着在低维空间中进行学习任务；度量学习则是试图去学习出一个距离度量来等效降维的效果，两者都是为了解决维数灾难带来的诸多问题。

原文地址:https://blog.csdn.net/zxsdss/article/details/140471967 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1815221745532145664.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部