第十章 降维与度量学习

k近邻(k-Nearest Neighbor)学习

• 工作机制
  

给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后根据这k个“邻居”的信息来进行预测。

最近邻分类器
最近邻分类器(1NN,即k=1)出错的概率为：

其中，x为测试样本，其最近邻样本为z。通过推导可得结论：
最近邻分类器虽然简单，但它的泛化错误率不超过贝叶斯最优分类器的错误率的两倍。

低维嵌入

• 维度灾难
  在高维情形下出现的数据样本稀疏，距离计算困难等问题，是所有机器学习方法共同面临的严重障碍。

缓解维数灾难的一个重要途径是降维，亦称“维数约简”。通过某种数字变换将原始高维属性空间转变为一个“子空间”，在这个子空间中样本密度大幅提高，距离计算也变得更容易。

• MDS算法
  多维缩放(MDS)是一种经典的降维算法。
  假定m个样本在原始空间的距离矩阵D∈Rm×m，其第i行j列的元素distij为样本xi到xj的距离。我们的目标是获得样本在dt维空间的表示Z∈Rdt×m,d′≤d,且任意两个样本在d′维空间中的欧氏距离等于原始空间中的距离。
  

主成分分析

主成分分析(PCA)是最常用的一种降维方法。对于一个能够将所有样本进行恰当表达的超平面，基于其最近重构性（样本点到这个超平面的距离都足够近）主成分分析的优化目标为

基于其最大可分性（样本点在这个超平面上的投影能尽可能分开）主成分分析的优化目标为：

对上述两个式子使用拉格朗日乘子法得：

于是，只需对协方差矩阵XXT进行特征值分解，将求得的特征值排序：λ1≥λ2≥...≥λd，再取前d′个特征值对应的特征向量构成W∗=(ω1,ω2,...,ωd′)，这就是主成分分析的解。

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

降维导致的结果

对应于最小的d−d′个特征值的特征向量被舍弃了。但这种舍弃往往是必要的：
- 舍弃这部分信息之后能使样本的采样密度增大
- 当数据收到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，将它们舍弃能在一定程度上起到去噪的效果。