降维与度量学习
1 k近邻学习
k近邻学习是一种常用的监督学习算法，工作机制为：给定训练样本，基于某种距离度量找出训练集中与其最近的k个训练样本，然后基于这些邻居的信息进行预测。
在分类任务中可以使用投票法。
在回归任务中可以使用平均值法。
还可以根据距离的远近进行加权。
k近邻学习没有显式的训练过程，是惰性学习的代表算法之一。
这类算法在训练阶段只是将样本保存起来，训练开销为0，收到测试样本时才进行处理。
假设样本独立分布，且任意x与任意小整数δ，在x附近δ距离内总能找到一个训练样本。c*表示贝叶斯最优分类器结果，则k近邻错误率表示为：
可见最近邻分类器虽然简单，但是泛化误差率不超过贝叶斯最优分类器错误率的两倍。
2 低维嵌入
之前有一个重要的假设：任意x与任意小整数δ，在x附近δ距离内总能找到一个训练样本，即训练样本采样密度够大。然而在显示任务中，这一点很难满足。
若δ = 0.001，仅考虑单个属性，则需要1000个样本点平均分配到取值空间。若属性为20维，则需要（103）20个样本，显然很难达成。
高维情况下出现的样本稀疏，距离计算困难等问题是所有机器学习方法共同面临的障碍，称为维数灾难。其主要解决手段就是降维。
降维也称为维数约简，是通过某种数学变化将高维属性空间变为低维“子空间”，在子空间中，样本密度大幅度提高，计算也变得容易。
之所以可以进行降维是因为，很多时候，人们观测到的数据虽然是高维的，但是学习任务密切相关的也许仅是一个低维分布。
若要保持原样本空间中样本之间的距离得到保持，即得到多维缩放MDS，这是一种经典的降维方法。
一般而言，为了获得低维子空间，最简单的是对原高维空间进行线性变化。对于给定的d维空间样本X：
变换矩阵W可以看作d‘个d维基向量，zi = WTxi是第i个样本与这d’个基向量分别做内积得到的d‘维属性向量。换言之，zi是原属性向量xi在新坐标系{w1,w2,...,wd'}中的坐标系。
显然，新空间中的属性是原空间的属性的线性组合。
基于线性变换来进行降维的方法称为线性降维方法，他们都符合10.13的基本形式，不同之处是对低维空间的性质有不同的要求，相当于对W施加了不同的约束。
对降维效果的评估，通常是比较学习器降维前后的性能，过性能有提高则认为降维起到了作用。
若要求低维子空间对样本具有最大可分性，则可以得到一种常用的线性降维方法PCA。
3 主成分分析
PCA是最常用的一种降维方法。
先考虑这样的一个问题：对于正交属性空间中的样本点，如何使用一个超平面对所有的样本进行表示。
显然，这样的超平面应该具有以下性质：
最近重构性：样本点到这个超平面的距离足够近。
最大可分性：样本点在这样的超平面上尽可能的分开。
根据最近重构性，PCA优化目标为：
根据最大可分性，PCA优化目标为：
因此，对协方差矩阵XXT进行特征值分解，将求得的特征值排序：
λ1 ≥ λ2 ≥ λ3 ≥...，选择前d’个特征值对应的特征向量构成W。这就是PCA的解。
PCA舍弃了d - d‘个特征值，使得样本的采样密度增大；同时，当数据受到噪声影响时，最小的特征值对应的特征向量往往与噪声有关，将他们舍弃可以在一定程度上起到去噪的效果。
4 核化线性降维
线性降维假设从高维空间到低维空间的映射是线性的，然而很多现实例子需要非线性映射才能找到恰当的低维度嵌入。
非线性降维的一种方法是基于核方法，对线性降维方法进行核化。
以核化主成分分析KPCA做为演示。
核函数：两个x在映射空间的内积等于其原始空间中通过k函数计算的结果。这个k函数就是核函数。
通过映射Ф将原始属性空间的样本x映射到高维空间，再在高维空间进行PCA。一般情况下我们不清楚Ф的形式，所以引入核函数：
通过核函数完成高维映射，然后进行PCA，这就是核化主成分分析。
KPCA需要对所有样本求和，因此其计算需求较大。
5 流形学习
流形学习是一种借鉴了拓扑流形概念的降维方法。“流形”是局部与欧氏空间同胚的空间，在局部具有欧氏空间的特性。
若低维流形嵌入到高维空间，则数据样本在高维空间上虽然看起来复杂，但是在局部仍然具有欧式空间的性质，因此可以容易的在局部建立降维映射关系。随后再将局部推广到全局。
- 等度量映射Isomap
观点：低维空间嵌入到高维空间后，直接在高维空间计算直线距离是具有误导性的，因为高维空间的直线距离在低维嵌入流形上是不可达的。
低维嵌入流形上的两点距离是测地线距离。
所以，我们借助流形在局部上与欧式空间同胚的性质，对每个点基于欧式距离找到其近邻点，然后建立近邻连接图，从而获得测地线距离的近似。
在得到任意两个点的距离后，可以通过多维缩放MDS算法获得样本点在低维空间的坐标。
Isomap仅得到了训练样本在低维空间的坐标，对于新样本，需要训练一个学习器进行映射：
将训练样本的高维空间坐标作为输入，低维空间坐标作为输出，训练一个回归学习器来对新样本的低维空间坐标进行预测。
近邻图的构建有两种方法，指定k数和指定阈值ε。
- 局部线性嵌入
与Isomap试图保存近邻样本间的距离不同，局部线性嵌入LIE试图保持邻近样本之间的线性关系。
6 度量学习
降维的目的是找到一个低维空间，使得在此空间上的学习效果能比原空间更好。
本质上每个空间对应了在样本属性上定义的一个距离度量，而寻找合适的空间实质上是寻找一个合适的距离度量。
度量学习的动机就是直接学习出一个合适的距离度量。
上式的W可以通过学习获得，然而W的非对角元素为0，意味着属性之间无关，这一点与现实相悖。因此，我们应该使得对应的坐标轴不再正交，将W替换为普通的半正定对此矩阵M，得到了马氏距离。
其中M为度量矩阵。
对M的学习需要设置一个目标，假定我们希望提高KNN模型的性能，则可将M嵌入到近邻分类器的评价指标中去，通过优化指标求的M。
