第10章 降维与度量学习

这章包含了经典算法KNN、经典数据降维处理方法PCA，以及流行学习和度量学习的简单介绍。

10.1 k近邻学习（KNN）

KNN属于懒惰学习，就是训练时间开销为零，需要测试的时候直接处理。

重要结论：KNN虽然简单，但是它的泛化错误率不超过贝叶斯最优分类器的两倍。

10.2 低维嵌入

高维特征容易出现样本稀疏和距离计算困难的问题，被称为“维数灾难”。于是就有了“降维”。

多维缩放（MDS）这种经典降维方法可以在低维空间中保持样本在原始空间中的距离。

10.3 主成分分析（PCA）

若用一个超平面有所有样本的投影，怎样的超平面是最适合降维的？

需要满足两个性质：

• 最近重构性：最小化所有样本点到超平面的距离

• 最大可分性：最大化样本投影点的距离方差

10.4 核化线性降维

略。

10.5 流形学习

流形学习借鉴了拓扑流形概念的降维方法。

我认为这个思想和微积分有异曲同工之妙，都是积少成多。等度量映射就是通过局部的空间与欧氏空间同胚的性质来计算低维中的测地线距离的。

找近邻点是等度量映射的关键。找近邻点的指标可分为两类，一类是控制近邻个数，另一类是找近邻距离。

计算两点的最短路径，可以使用图论中的经典算法：Dijkstra算法或Floyd算法。

10.6 度量学习

不降维了，直接修改度量公式！

近邻成分分析（NCA）把KNN中的直接投票法改成了概率投票法。近邻的投票是有不一样的权重的。