10.1k近邻学习
k k k近邻(k-Nearest Neighbor,简称kNN)，监督学习。
工作机制：给定测试样本，基于某种距离度量找出训练集中与其最靠近的 k k k个训练样本，基于这些”邻居“预测。
{ 分类任务：选择”投票法“。 k 个样本中最多的类别为预测结果 回归任务：选择”平均法“。平均值或加权平均值 \begin{cases} 分类任务：选择”投票法“。k个样本中最多的类别为预测结果 & \\ 回归任务： 选择”平均法“。平均值或加权平均值 \\ \end{cases} {分类任务：选择”投票法“。k个样本中最多的类别为预测结果回归任务：选择”平均法“。平均值或加权平均值
KNN是“懒惰学习”代表，没有训练。训练开销为零。待收到测试样本再进行处理。
在训练阶段对样本进行学习的方式，称为“急切学习”
给定测试样本 x x x，若其最紧邻样本为 z z z，则最近邻分类器出错的概率就是 x x x与 z z z类别，标记不同的概率，即
最近邻分类器虽然简单，但它泛化错误率不超过贝叶斯最优分类器错误率的两倍！
10.2低维嵌入
在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的困难，称为“维数灾难”。
缓解维数灾难的一个重要途径是降维，“维数约简”
“多维缩放”（Multiple Dimensional Scaling，简称MDS）
d i s t i j 2 = ∣ ∣ z i ∣ ∣ 2 + ∣ ∣ z j ∣ ∣ 2 − 2 z i T z j = b i i + b j j − 2 b i j \begin{equation} \begin{aligned} dist_{ij}^2&=||z_i||^2+||z_j||^2-2z_i^Tz_j \\ &=b_{ii}+b_{jj}-2b_{ij} \end{aligned} \tag{10.3} \end{equation} distij2=∣∣zi∣∣2+∣∣zj∣∣2−2ziTzj=bii+bjj−2bij(10.3)
基于线性变换进行降维方法称为线性降维，都符合（10.13）
不同之处在于对低维子空间性质有不同的要求，对 W W W施加了不同约束
10.3主成分分析
对正交属性空间中的样本点，如何用一个超平面对所有样本进行表达？
性质
- 最近重构性：样本点到这个超平面的距离都足够近
- 最大可分性：样本点在这个超平面的投影尽可能分开
从最近重构性推导：
从最大可分性推导：
样本点 x i x_i xi在新空间超平面投影是 W T x i W^Tx_i WTxi
若要使尽可能分开，则使投影后样本点的方差最大化。
10.4核化线性降维
若直接使用线性降维方法对三维空间观察到的样本进行降维，则将丢失原本的低维结构。
“原本采样的”低维空间称为“本真”低维
**非线性降维的一种常见方法是基于核技巧对线性降维方法进行“核化”**以主成分分析KPCA为例：
10.5流形学习
流形学习（manifold learning）是一类借鉴拓补流形概念的降维。“流形”是在局部与欧氏距离空间同胚的空间。局部具有欧氏距离的性质。
10.5.1等度量映射（Isometric Maping，简称Isomap）
低维嵌入流形上的测地线距离不能用高维空间的直线距离计算，但能用近似距离来近似
如何计算测地线距离
利用流形在局部上与欧氏距离同胚这个性质，计算两点之间测地线距离的问题，就转变为计算近邻连接图上两点之间最短路径问题。
在近邻连接图上计算两点之间最短路径，著名的Dijkstra算法或者Floyd算法
I s o m a p Isomap Isomap仅是得到了训练样本在低维空间的坐标，对于新样本，将高维空间坐标作为输入，低维空间坐标作为输出，训练一个回归学习器来对新样本的低维空间坐标进行预测。
近邻图构建的两种方法：
- 指定邻点个数，如欧氏距离最近的 k k k个点为近邻点， k k k近邻图。
- 指定距离阈值 ξ \xi ξ,距离小于 ξ \xi ξ的店被认为是近邻点， ξ \xi ξ近邻图。
10.5.2局部线性嵌入
局部线性嵌入（Locally Liner Embedding，简称LLE）保持样本之间的线性关系。
假定样本点 x i x_i xi能通过邻域样本 x j x_j xj, x k x_k xk, x l x_l xl的坐标经过线性组会重构：
10.6度量学习
假定希望提高近邻分类器的性能，将 M M M嵌入到评价指标中，优化该性能指标相应求 M M M
近邻分类器判别时通常用多数投票法（领域中1票，领域外0票）
替换为概率投票法，对任意样本 x j x_j xj对 x i x_i xi分类影响的概率为：
