1. 维数灾难

样本的特征数称为维数（dimensionality），当维数非常大时，也就是现在所说的维数灾难。
维数灾难具体表现在：在高维情形下，数据样本将变得十分稀疏，因为此时要满足训练样本为“密采样”的总体样本数目是一个触不可及的天文数字，训练样本的稀疏使得其代表总体分布的能力大大减弱，从而消减了学习器的泛化能力；同时当维数很高时，计算距离也变得十分复杂，甚至连计算内积都不再容易，这也是为什么支持向量机（SVM）使用核函数低维计算，高维表现的原因。

缓解维数灾难的一个重要途径就是降维，即通过某种数学变换将原始高维空间转变到一个低维的子空间。
在这个子空间中，样本的密度将大幅提高，同时距离计算也变得容易。这时也许会有疑问，这样降维之后不是会丢失原始数据的一部分信息吗？这是因为在很多实际的问题中，虽然训练数据是高维的，但是与学习任务相关也许仅仅是其中的一个低维子空间，也称为一个低维嵌入，例如：数据属性中存在噪声属性、相似属性或冗余属性等，对高维数据进行降维能在一定程度上达到提炼低维优质属性或降噪的效果。

2. K近邻学习（kNN）

k近邻算法简称kNN（k-Nearest Neighbor），是一种经典的监督学习方法，数据挖掘十大算法之一。

工作机制非常简单:给定测试样本,基于某种距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个“邻居”的信息来进行预测。

通常,在分类任务中可使用“投票法”,即选择这k个样本中出现最多的类别标记作为预测结果;

在回归任务中可使用“平均法”,即将这k个样本的实值输出标记的平均值作为预测结果;还可基于距离远近进行加权平均或加权投票,距离越近的样本权重越大.

2.1 分析

从上图中我们可以看到，图中有两种类型的样本，一类是蓝色正方形，另一类是红色三角形。而那个绿色圆形是我们待分类的样本。基于kNN算法的思路，我们很容易得到以下结论：

如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形。
如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形。

与前面介绍的学习方法相比, k近邻学习有一个明显的不同之处: 它似乎没有显式的训练过程! 事实上,它是“懒情学习” (lazy learning)的著名代表, 此类学习技术在训练阶段仅仅是把样本保存起来,训练时间开销为零, 待收到测试样本后再进行处理（因此朴素贝叶斯也可以懒惰式学习，此类技术在训练阶段开销为零，待收到测试样本后再进行计算。）; 相应的,那些在训练阶段就对样本进行学习处理的方法, 称为“急切学习” (eager learning).

很容易看出：kNN算法的核心在于k值的选取以及距离的度量。k值选取太小，模型很容易受到噪声数据的干扰，例如：极端地取k=1，若待分类样本正好与一个噪声数据距离最近，就导致了分类错误；若k值太大， 则在更大的邻域内进行投票，此时模型的预测能力大大减弱，例如：极端取k=训练样本数，就相当于模型根本没有学习，所有测试样本的预测结果都是一样的。一般地我们都通过交叉验证法（简单来说，就是一部分样本做训练集，一部分做测试集）来选取一个适当的k值。

对于距离度量，不同的度量方法得到的k个近邻不尽相同，从而对最终的投票结果产生了影响，因此选择一个合适的距离度量方法也十分重要。在上一篇聚类算法中，在度量样本相似性时介绍了常用的几种距离计算方法，包括闵可夫斯基距离，曼哈顿距离，VDM等（距离度量方法总结可参考博客）。在实际应用中，kNN的距离度量函数一般根据样本的特性来选择合适的距离度量，同时应对数据进行去量纲/归一化处理来消除大量纲属性的强权政治影响。

2.2 KNN最近邻分类算法的过程

1. 计算测试样本和训练样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）；
2. 对上面所有的距离值进行排序；
3. 选前 k 个最小距离的样本；
4. 根据这 k 个样本的标签进行投票，得到最后的分类类别；

3. MDS算法

不管是使用核函数升维还是对数据降维，我们都希望原始空间样本点之间的距离在新空间中基本保持不变，这样才不会使得原始空间样本之间的关系及总体分布发生较大的改变。**“多维缩放”（Multiple Dimensional Scaling，MDS）**正是基于这样的思想，MDS要求原始空间样本之间的距离在降维后的低维空间中得以保持。

令降维后的样本坐标矩阵Z被中心化，中心化是指将每个样本向量减去整个样本集的均值向量，故所有样本向量求和得到一个零向量，即

这样易知：矩阵B的每一列以及每一列求和均为0，因为提取公因子后都有一项为所有样本向量的和向量。

根据上面矩阵B的特征，我们很容易得到以下等式：

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

4. 主成分分析（PCA）

该部分可参考博客。

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

在介绍PCA之前,不妨先考虑这样一个问题:对于正交属性空间中的样本点,如何用一个超平面(直线的高维推广)对所有样本进行恰当的表达?
容易想到,若存在这样的超平面,那么它大概应具有这样的性质:

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

• 最大可分性:样本点在这个超平面上的投影能尽可能分开.

这里十分神奇的是：最近重构性与最大可分性虽然从不同的出发点来定义优化问题中的目标函数，但最终这两种特性得到了完全相同的优化问题：

接着使用拉格朗日乘子法求解上面的优化问题，得到：

因此只需对协方差矩阵进行特征值分解即可求解出W，PCA算法的整个流程如下图所示：

5. 核化线性降维

线性降维方法假设从高维空间到低维空间的函数映射是线性的,然而,在不少现实任务中,可能需要非线性映射才能找到恰当的低维嵌入,图10.6给出了一个例子,样本点从二维空间中的矩形区域采样后以S形曲面嵌入到三维空间,若直接使用线性降维方法对三维空间观察到的样本点进行降维,则将丢失原本的低维结构,为了对“原本采样的”低维空间与降维后的低维空间加以区别,我们称前者为“本真”(intrinsic)低维空间。

正如SVM在处理非线性可分时，通过引入核函数将样本投影到高维特征空间，接着在高维空间再对样本点使用超平面划分。这里也是相同的问题：若我们的样本数据点本身就不是线性分布，那还如何使用一个超平面去近似表出呢？因此也就引入了核函数，即先将样本映射到高维空间，再在高维空间中使用线性降维的方法。下面主要介绍**核化主成分分（KPCA）**的思想。

5.1 基本思想

若核函数的形式已知，即我们知道如何将低维的坐标变换为高维坐标，这时我们只需先将数据映射到高维特征空间，再在高维空间中运用PCA即可。但是一般情况下，我们并不知道核函数具体的映射规则，例如：Sigmoid、高斯核等，我们只知道如何计算高维空间中的样本内积，这时就引出了KPCA的一个重要创新之处：即空间中的任一向量，都可以由该空间中的所有样本线性表示。

6. 流形学习

流形学习（manifold learning）是一种借助拓扑流形概念的降维方法，流形是指在局部与欧式空间同胚的空间，即在局部与欧式空间具有相同的性质，能用欧氏距离计算样本之间的距离。这样即使高维空间的分布十分复杂，但是在局部上依然满足欧式空间的性质，基于流形学习的降维正是这种**“邻域保持”的思想。其中等度量映射（Isomap）试图在降维前后保持邻域内样本之间的距离，而局部线性嵌入（LLE）则是保持邻域内样本之间的线性关系**，下面将分别对这两种著名的流行学习方法进行介绍。

6.1 等度量映射（Isomap）

等度量映射(Isometric Mapping, 简称 Isomap) 的基本出发点是：认为低维流形嵌入到高维空间之后,直接在高维空间中计算直线距离具有误导性,因为高维空间中的直线距离在低维嵌入流形上是不可达的。

如图10.7(a)所示,低维嵌入流形上两点间的距离是“测地线”(geodesic)距离: 想象一只虫子从一点爬到另一点,如果它不能脱离曲面行走,那么图10.7(a)中的红色曲线是距离最短的路径,即S曲面上的测地线,测地线距离是两点之间的本真距离,显然,直接在高维空间中计算直线距离是不恰当的.

利用流形在局部上与欧式空间同胚的性质，可以使用近邻距离来逼近测地线距离**，即对于一个样本点，它与近邻内的样本点之间是可达的，且距离使用欧式距离计算，这样整个样本空间就形成了一张近邻图，高维空间中两个样本之间的距离就转为最短路径问题。可采用著名的Dijkstra算法或Floyd算法计算最短距离，得到高维空间中任意两点之间的距离后便可以使用MDS算法来其计算低维空间中的坐标。

从MDS算法的描述中我们可以知道：MDS先求出了低维空间的内积矩阵B，接着使用特征值分解计算出了样本在低维空间中的坐标，但是并没有给出通用的投影向量w，因此对于需要降维的新样本无从下手，书中给出的权宜之计是是将训练样本的高维空间坐标作为输入、低维空间坐标作为输出,训练一个回归学习器来对新样本的低维空间坐标进行预测。

Isomap算法流程如下图：

对近邻图的构建通常有两种做法,一种是指定近邻点个数,例如欧氏距离最近的k个点为近邻点,这样得到的近邻图称为k近邻图；另一种是指定距离阈值$ϵ$，距离小于$阈值ϵ$的点被认为是近邻点,这样得到的近邻图称为$ϵϵ$近邻图。

两种方式均有不足：

若邻域范围指定过大，则会造成“短路问题”，即本身距离很远却成了近邻，将距离近的那些样本扼杀在摇篮。
若邻域范围指定过小，则会造成“断路问题”，即有些样本点无法可达了，整个世界村被划分为互不可达的小部落。

6.2 局部线性嵌入(LLE)

与Isomap试图保持近邻样本之间的距离不同,局部线性嵌入(Locally Linear Embedding, 简称LLE) 试图保持邻域内样本之间的线性关系.如图10.9所示,假定样本点$xj,xk,xlxi$的坐标能通过它的邻域样本$xj,xk,xlxj,xk,xl$的坐标通过线性组合而重构出来,即

7. 度量学习

在机器学习中,对高维数据进行降维的主要目的是希望找到一个合适的低维空间,在此空间中进行学习能比原始空间性能更好,事实上,每个空间对应了在样本属性上定义的一个距离度量,而寻找合适的空间,实质上就是在寻找一个合适的距离度量,那么,为何不直接尝试“学习”出一个合适的距离度量呢?这就是度量学习(metric learning)的基本动机.

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

若各个属性重要程度不一样即都有一个权重，则得到加权的平方欧式距离：

此时各个属性之间都是相互独立无关的，但现实中往往会存在属性之间有关联的情形，例如：身高和体重，一般人越高，体重也会重一些，他们之间存在较大的相关性。这样计算距离就不能分属性单独计算，于是就引入经典的马氏距离(Mahalanobis distance):

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

换句话说：度量学习便是对度量矩阵进行学习。

现在来回想一下前面我们接触的机器学习不难发现：机器学习算法几乎都是在优化目标函数，从而求解目标函数中的参数。同样对于度量学习，也需要设置一个优化目标，书中简要介绍了错误率和相似性两种优化目标，此处不再展开。

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

度量学习则是试图去学习出一个距离度量来等效降维的效果，两者都是为了解决维数灾难带来的诸多问题。