《机器学习》周志华(西瓜书)学习笔记第十章降维与度量学习

机器学习总目录第十章降维与度量学习10.1 K近邻学习k近邻学习是一种监督学习算法，在给定的训练样本集中，基于某种距离度量，找出与训练集最靠近的kkk个训练样本，然后基于这k个邻居信息来进行预测。投票法：通常在分类任务中使用，判别方法是选择这kk个样本中出现最多的类别标记作为预测结果。平均法：通常在回归任务中使用，判别方法是将这kk个样本的实值输出标记的平均值最为预测结果。加权平...

Sundm@lhq

2783人浏览 · 2019-07-10 14:37:26

Sundm@lhq · 2019-07-10 14:37:26 发布

机器学习

总目录

第十章降维与度量学习

10.1 K近邻学习

k近邻学习是一种监督学习算法，在给定的训练样本集中，基于某种距离度量，找出与训练集最靠近的 $k$ 个训练样本，然后基于这k个邻居信息来进行预测。

投票法：通常在分类任务中使用，判别方法是选择这kk个样本中出现最多的类别标记作为预测结果。
平均法：通常在回归任务中使用，判别方法是将这kk个样本的实值输出标记的平均值最为预测结果。
加权平均或加权投票：根据距离远近来决定权重，距离越近，权重越大。

kNN虽然是一种监督学习方法，但是它却没有显式的训练过程，而是当有新样本需要预测时，才来计算出最近的k个邻居，因此kNN是一种典型的懒惰学习方法.

懒惰学习(lazy study)：没有显式训练过程，仅把样本保存，训练时间无开销，待收到测试样本后再进行处理
急切学习(eager learning)：在训练阶段就对样本进行学习处理的方法

k近邻分类器中，k为不同值时，分类结果也就不同；同时，若采用不同的距离计算方式，则找出的近邻也有显著差别，导致分类结果也显著不同。假设距离计算是恰当的，就是不考虑距离导致的差异性，而就从k这个参数的差异就最近邻分类器在二分类问题上的性能进行分析:
在这里插入图片描述

10.2 低维嵌入

高维情形下，样本数的采样以及距离计算问题。在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为维数灾难（curse of dimensionality）

缓解维数灾难的两个途径：

特征选择
降维（dimension reduction）

多维缩放(Multiple Dimensional Scaling, MDS)

目标:要求原始空间样本之间的距离在降维后的低维空间中得以保持

假定：m个样本在原始空间的距离矩阵为 $D\in R^{m*m}$ ，其第i行j列的元素 $dist_{ij}$ 为样本 $\bm{x_i}$ 到 $\bm{x_j}$ 的距离。我们的目标是获得样本在 $d ’$ 维空间的表示 $Z\in\mathbb{R}^{d’*m}，d≤d$ ，且任两个样本在d’维空间中的欧氏距离等于原始空间中的距离，即 $||\bm z_i-\bm z_j||=dist_{ij}∣∣$

降维后样本的内积矩阵
在这里插入图片描述
令将为后的降本Z被中心化

在这里插入图片描述

10.3 主成分分析

不同于MDS采用距离保持的方法，主成分分析（PCA）直接通过一个线性变换，将原始空间中的样本投影到新的低维空间中。简单来理解这一过程便是：PCA采用一组新的基来表示样本点，其中每一个基向量都是原来基向量的线性组合，通过使用尽可能少的新基向量来表出样本，从而达到降维的目的。

假设使用 $d ’$ 个新基向量来表示原来样本，实质上是将样本投影到一个由 $d ’$ 个基向量确定的一个超平面上（即舍弃了一些维度），要用一个超平面对空间中所有高维样本进行恰当的表达，最理想的情形是：若这些样本点都能在超平面上表出且这些表出在超平面上都能够很好地分散开来。但是一般使用较原空间低一些维度的超平面来做到这两点十分不容易，因此我们退一步海阔天空，要求这个超平面应具有如下两个性质：

最近重构性：样本点到超平面的距离足够近，即尽可能在超平面附近；
最大可分性：样本点在超平面上的投影尽可能地分散开来，即投影后的坐标具有区分性。

在这里插入图片描述

降维后低维空间的维数 d’ 通常是由用户事先指定，或通过在 d’ 值不同的低维空间中对 k 近邻分类器(或其他开销较小的学习器)进行交叉验证来选取较好的 d’ 值.对 PCA，还可从重构的角度设置一个重构阔值，例如 t = 95%，然后选取使下式成立的最小 d’ 值:

$\frac{\sum_{i=1}^{d'}\lambda_i}{\sum_{i=1}^d \lambda_i} \ge t$

PCA 仅需保留 W 与样本的均值向量即可通过简单的向量减法和矩阵"向量乘法将新样本投影至低维空间中. 显然，低维空间与原始高维空间必有不同，因为对应于最小的 d-d’ 个特征值的特征向量被舍弃了，这是降维导致的结果. 但舍弃这部分信息往往是必要的- 一方面舍弃这部分信息之后能使样本的采样密度增大，这正是降维的重要动机; 另一方面，当数据受到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关,将它们舍弃能在一定程度上起到去噪的效果.

10.4 核化线性降维

线性降维方法假设从高维空间到低维空间的函数映射是线性的，不过，在现实任务中可能需要非线性映射才能找到恰当的低维嵌入。这一节主要就是说非线性降维，以为保持本真（intrinsic）低维空间。非线性降维方法的一种常用方法，是基于核技巧对线性降维方法进行核化（kernelized）。下文说明核主成分分析（Kernelized PCA，KPCA）。

假定将高维特征空间中把数据投影到由W确定的平面上：
$(\sum_{i=1}^mz_iz_i^T)W=\lambda W$
在这里插入图片描述

10.5 流形学习

流形学习（manifoldlearning）是一类借鉴了拓扑流形概念的降维方法。流形是在局部与欧式空间同胚的空间，换言之，它在局部具有欧式空间的性质，能用欧式距离来进行距离计算。若低维流形嵌入到高维空间中，则数据样本在高维空间的分布虽然看上去非常复杂，但在局部上仍具有欧式空间的性质，如此，可以容易地在局部建立降维映射关系，然后再设法将局部映射推广到全局。当维数被降至二维或三维时，能对数据进行可视化展示。

等度量映射（isomap）

等度量映射的基本出发点是：高维空间中的直线距离具有误导性，因为有时高维空间中的直线距离在低维空间中是不可达的。因此利用流形在局部上与欧式空间同胚的性质，可以使用近邻距离来逼近测地线距离，即对于一个样本点，它与近邻内的样本点之间是可达的，且距离使用欧式距离计算，这样整个样本空间就形成了一张近邻图，高维空间中两个样本之间的距离就转为最短路径问题。可采用著名的Dijkstra算法或Floyd算法计算最短距离，得到高维空间中任意两点之间的距离后便可以使用MDS算法来其计算低维空间中的坐标。
在这里插入图片描述
从MDS算法的描述中我们可以知道：MDS先求出了低维空间的内积矩阵B，接着使用特征值分解计算出了样本在低维空间中的坐标，但是并没有给出通用的投影向量w，因此对于需要降维的新样本无从下手，书中给出的权宜之计是利用已知高/低维坐标的样本作为训练集学习出一个“投影器”，便可以用高维坐标预测出低维坐标。Isomap算法流程如下图：

在这里插入图片描述
对近邻图的构建有两种做法：

一种是指定近邻点个数，如欧式距离最近的k个点为近邻点，称为k近邻图；
另一种是指定距离阈值，距离小于阈值的点被认为是近邻点，称为近邻图。

两种方法均有不足，若近邻范围指定过大，则距离很远的点可能被误认为是近邻，出现短路问题；近邻范围指定过小，则图中有些区域可能与其他区域不存在连接，出现断路问题。断路和短路都会给后续的最短路径计算造成误导。

局部线性嵌入 LLE

与Isomap试图保持近邻样本之间的距离不同，局部线性嵌入（Locally Linear Embedding,LLE）试图保持邻域内样本间的线性关系。假定样本点xi的坐标能通过它的邻域样本 $x_j、x_k、x_l$ 的坐标通过线性组合而重构出来，即： $xi=w_{ij}x_j+ w_{ik}x_k+w_{il}x_l$ ，自然该式在低维空间中需要保持。

在这里插入图片描述

10.6 度量学习

在机器学习中，对高维数据进行降维的主要目的是找到一个合适的低维空间，在该空间中进行学习能比原始空间性能更好。每个空间对应了在样本属性上定义的一个距离度量，而寻找合适的空间，本质上就是寻找一个合适的距离度量。度量学习（metric learning）的基本动机就是去学习一个合适的距离度量。

降维的核心在在于寻找合适空间，而合适空间的定义就是距离度量，所以学习合适的距离度量就是度量学习的目的。要对距离度量进行学习，要有一个便于学习的距离度量表达形式。

对两个样本 $d'维样本x_i与x_j$ ，它们之间的平方欧式距离为：
$dist^2_{ed}(x_i,x_j)=||x_i-x_j||^2_2=dist^2_{i,j,1}+\cdots +dist^2_{i,j,d}$

假定不同属性重要性不同:
$dist^2_{wed}(x_i,x_j)=||x_i-x_j||^2_2=w_1*dist^2_{i,j,1}+\cdots +w_d*dist^2_{i,j,d}\\ =(x_i-x_j)^TW(x_i-x_j)$
将W替换为普通半正定对称阵M得到马氏距离：
$dist^2_{mah}(x_i,x_j)=(x_i-x_j)^TM(x_i-x_j)=||x_i-x_j||^2_M$