k近邻算法是一种基本的分类与回归算法 - 根据新实例的k个最近邻的训练实例的类别，通过多数表决等方式进行预测

1. k近邻的几个要素

1. 模型
   • 特征空间被划分成了不同的子空间
   • 对于训练实例点来说，距离该点比其他点更近的所有点组成的区域，叫做单元(cell)，该训练实例点的类型称为该单元的类标记(class label)
2. 距离度量
   • 两个实例之间的距离表示的两个实例之间的相似程度
   • 常用的距离度量方法：$L_{p}$距离（也叫Minkowski距离）$$L_{p}(x_{i},x_{j})=\Big{(} \sum_{l=1}^{n} \Big{|}x_{i}^{(l)}-x_{j}^{(l)}\Big{|}^{p} \Big{)}^{\frac{1}{p}}$$当$p=1$时，称为曼哈顿(Manhattan Distance)$$L_{1}(x_{i},x_{j})= \sum_{l=1}^{n} \Big{|}x_{i}^{(l)}-x_{j}^{(l)}\Big{|}$$当$p=2$时，称为欧氏距离(Euclidean Distance)$$L_{2}(x_{i},x_{j})=\Big{(} \sum_{l=1}^{n} \Big{|}x_{i}^{(l)}-x_{j}^{(l)}\Big{|}^{2} \Big{)}^{\frac{1}{2}}$$当$p=\infty$时，称为切比雪夫距离(Chebyshev Distance)$$L_{\infty}(x_{i},x_{j})=\max_{l}\Big{|} x_{i}^{(l)}-x_{j}^{(l)} \Big{|}$$
3. k值选择

1. 分类决策规则
   • 常用的是多数表决（majority voting rule）的规则
   • 分类函数时0-1损失函数，误分类的概率是$$P\{Y \neq f(X)\}=1-P\{ Y = f(X) \}$$

2. kd树

1. 需要注意的几点
   • kd树中的k指的是数据的维数，并不是k近邻算法中和当前输入节点最近的点的个数。避免影响书中后面的算法的理解。
   • kd树是一个树形结构，在初始化的时候使用递归的方法来创建比较方便。
2. kd树的搜索算法包含两步
   • 第一步，递归的搜索kd树，得到输入点对应的叶节点。
   • 第二步，向上回溯寻找真正的最近邻点
3. 参考实现A simple kd-tree in Python