10.降维和度量学习

10.1k近邻学习

k近邻（k-NearestNeighbor，简称kNN）学习是一种常用的监督学习方法，其原理是：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个邻居的信息来进行预测。在分类任务中，使用投票法，选择k个样本中出现最多的类别标记作为预测结果；在回归任务中，使用平均法，将这k个样本的实值输出标记的平均值作为预测结果。自然，也可基于距离远近进行加权平均或加权投片，距离越近的样本权重越大。

k近邻学习方法，没有显示的训练过程，是懒惰学习（lazy learning），在训练阶段仅把样本保存起来，训练时间开销为零，待收到测试样本后在进行处理；相对应急切学习（eager learning）而言，就是在训练阶段就对样本进行学习处理的方法。

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

 

10.2低维嵌入

k近邻学习方法基于一个重要的假设：任意测试样本x附近任意小的 距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为密采样（dense sample）。不过这在现实任务中一般很难满足，假设 ，在单个属性情况下，仅需1000个样本点平均分布在归一化后的属性取值范围内[0,1]，即可使得任务测试样本在其附近0.001距离范围内总能找到一个训练样本，此时最近邻分类器的错误率不超过贝叶斯最优分类器的错误率的两倍；但若在多个属性情况下，如假定属性维数是20，按照密采样条件要求，至少需要 (〖10〗^3 )^20=〖10〗^60个样本。现实应用中属性维数众多，要满足密采样条件，所需的样本数目将是天文数字。而且还要考虑距离度量计算，高维空间对距离计算来说不是简单的开销，当维数很高时，连计算内积都不容易。

小贴士：宇宙间基本粒子的总数约为〖10〗^80 ，一粒灰尘中含有几十亿个基本粒子。宇宙之宏大，数学之简单，令人瞠目结舌。

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

缓解维数灾难的两个途径：一是特征选择；二是本文要重点介绍的降维（dimension reduction）。思路上，这两种途径都是减少维数，不过一个是在事前，一个是在事中。降维，也称维数约简，通过某种数学变换将原始高维属性空间转变为一个低维子空间（subspace），在子空间中，样本密度可以大幅提高，距离计算也相对容易。事实上，观测或收集到的数据样本虽然是高维的，但与学习任务相关的或许只是某个低维分布，这也是特征选择可以事前根据业务来定义的。

那么问题自然是？为什么可以降维？降维后的是否影响样本距离呢？降维后要求样本空间中样本之间的距离在低维空间中得以保持，多维缩放（multiple dimensional scaling，MDS）是一种经典的降维方法，证明如下。

维属性向量。若w_i与w_j（i≠j）正交，则新坐标系是一个正交坐标系，此时W为正交变换。可见，新空间中的属性是原空间中属性的线性组合。

对降维效果的评估，通常是比较降维前后学习器的性能，若性能有所提高，则认为降维起到了作用。若将维数降至二维或三维，则可通过可视化技术来直观地判断降维效果。

基于线性变换来进行降维的方法称为线性降维方法，符合Z=W^TX形式，不同之处是对低维空间的性质有不同要求，相当于对W施加了不同的约束。若要求低维子空间对样本具有最大可分性，则将得到一种极为常用的线性降维方法，见下节。

10.3主成分分析

主成分分析（PrincipalComponent Analysis,PCA）是最常用的一种降维方法。对于正交属性空间中的样本点，如何用一个超平面（直线的高维推广）对所有样本进行恰当的表达？若存在这样的超平面，应具有如下两点性质：

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

2）最大可分性：样本点在这个超平面上的投影能尽可能分开。

基于最近重构性和最大可分性，能分别得到主成分分析的两种等价推导。

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

10.4核化线性降维

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

 

10.5流形学习

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

对此，我的理解是，在一个曲面上，跨越弯曲的两点，无法用欧式距离，但在曲面的某部分切面是可以用欧式距离来计算。

1）等度量映射

等度量映射（IsometricMapping，Isomap）的基本出发点，是认为低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维嵌入流形上是不可达的。S曲面上的测地线距离是两点之间的本真距离，直接在高维空间中计算直线距离是不恰当的，因为跨越了弯曲区域。那么如何计算测地线距离呢？可利用流形在局部上与欧式空间同胚的性质，对每个点基于欧式距离找出其近邻点，然后就能建立一个近邻连接图；图中近邻点之间存在连接，而非近邻点之间不存在连接；于是，两点之间测地线的距离，就转变为计算近邻连接图上两点之间的最短路径问题。

这样理解，在曲面上的一定平滑区域内基于欧式距离找出近邻点，构成一个图，然后求解图中两个点的最短距离，这个思想就是用近邻距离来接近测地线距离。在近邻接图上计算两点间的最短路径，可采用著名的Dijkstra算法或Floyd算法（http://blog.csdn.net/fjssharpsword/article/details/52953640），得到两点距离之后，可用MDS方法来获得样本点在低维空间中的坐标。算法描述如下：

输入：样本集D={x₁,x₂,…,x_m}；

      近邻参数k；       

      低维空间数d*；

过程：fori=1,2,…,m do

          确定x_i的k近邻；

          x_i与k近邻点之间的距离设置为欧式距离，与其他点的距离设置为无穷大；

      end for

      调用最短路径算法计算任意两样本点之间的距离dist(x_i,x_j)；

      将dist(x_i,x_j)作为MDS算法的输入；

      return MDS算法的输出

输出：样本集D在低维空间的投影Z={z₁,z₂,…,z_m}

Isomap得到了训练样本在低维空间的坐标，对于新样本，如何将其映射到低维空间？常用解决方案是，将训练样本的高维空间坐标作为输入、低维空间坐标作为输出，训练一个回归学习器来对新样本的低维空间坐标进行预测。文中说不是最佳之法，却也没有更好的。

对近邻图的构建有两种做法：一种是指定近邻点个数，如欧式距离最近的k个点为近邻点，称为k近邻图；另一种是指定距离阈值 ，距离小于阈值的点被认为是近邻点，称为 近邻图。两种方法均有不足，若近邻范围指定过大，则距离很远的点可能被误认为是近邻，出现短路问题；近邻范围指定过小，则图中有些区域可能与其他区域不存在连接，出现断路问题。断路和短路都会给后续的最短路径计算造成误导。

2）局部线性嵌入

与Isomap试图保持近邻样本之间的距离不同，局部线性嵌入（Locally Linear Embedding,LLE）试图保持邻域内样本间的线性关系。假定样本点x _i的坐标能通过它的邻域样本x _j、x _k、x _l的坐标通过线性组合而重构出来，即：x _i=w _ijx _j+ w _ikx _k+w _ilx _l，自然该式在低维空间中需要保持。

算法中对于不在样本x_i邻域区域的样本x_j，无论其如何变化都对x_i和z_i没有任何影响，这种将变动限制在局部的思想在许多地方都很有用。可以发现算法思想的重要性，如近似、贪心、局部等概念。

10.6度量学习

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

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

其中M称为度量矩阵，度量学习就是对M进行学习。为保持距离非负且对称，M须是半正定对称矩阵，即必有正交基P使得M能写为M=PP^T。

至此，已构建了学习的对象是M这个度量矩阵，接下来就是给学习设定一个目标从而求得M。假定是希望提高近邻分类器的性能，则可将M直接嵌入到近邻分类器的评价指标中去，通过优化该性能指标相应地求得M，以近邻成分分析（Neighbourhood Component Analysis，NCA）进行讨论。

近邻分类器判别时通常采用多数投票法，领域中的每个样本投1票，领域外的样本投0票。将其替换为概率投票法，对任意样本x_j，它对x_i分类结果影响的概率为：

本章的核心是降维，涉及到最基础的PCA及其非线性核化，再而就是流形学习和度量学习，都可起到降维的目标。为什么要降维呢？因为高维无法满足密采样以及计算开销大。