近邻法是一种基本分类与回归方法（这里只讨论分类问题）。
近邻法通过训练样本对特征空间进行划分，形成模型，之后对新的实例，根据与其最近的
个实例的类别，通过多数表决等方式进行预测，即这
个实例的多数属于某个类，那么这个新的实例就被分为这个类。
近邻法的 算法 为：
- Input：训练数据集
，实例的特征向量
；
- Output：实例
；
-
根据距离找出训练集
个点，涵盖这
；
-
在
其中，
为指示函数，即当
时
近邻法有特殊情况
，称为 最近邻算法。对于输入的实例
，最近邻法将训练集中与
最近的点的类作为
的类。
这里分类决策规则一般为多数表决规则，要使其误分类概率最小化，则相当于经验风险最小化。
近邻模型
近邻模型由三个基本要素决定：距离度量、
值的选择和分类决策规则。当这三个要素确定后，每一个实例都可以确定唯一的分类。
特征空间中，对每一个训练样本 ，距离该点比其他点更近的所有点组成一个区域，叫做单元（cell）。每个样本（只）拥有一个单元，所有训练样本的单元构成对特征空间的一个划分。每个单元中所有点的类
称为类标记（class label）。
距离度量
近邻法的距离度量一般为_欧氏距离_，但也可以是
距离或 Minkowski 距离。
距离
设特征空间中两个实例 ，
，则
和
的
距离为
这里 。当
时，称为 欧氏距离。
当 时，称为曼哈顿距离。
当 时，
距离是
和
各个坐标距离的最大值，即
由不同的距离度量所确定的最近邻点是不同的。
值的选择
值的选择对
近邻法的结果影响很大。
如果 值较小，学习的近似误差会减小，估计误差会增大，即与输入实例比较近的点才会起比较大的作用。如果比较近的点是噪声，预测就会出错。也就是说，
值较小的模型容易过拟合。
如果 值较大，学习的近似误差会增大，估计误差会减小，即与输入实例距离较远的点也会影响预测结果，使预测发生错误。
如果 （
是训练样本的数量），那么输入实例会被预测为训练样本中最多点的类，这个模型过于简单，不可取。
值一般取一个较小的数，通常用_交叉验证法_选取。
树
为提高 近邻搜索的效率 ，我们需要用特殊的结构存储训练数据，以减少计算距离的次数，这就是
树方法。
构造 树
树是一种对
维空间中的点进行存储以便对其进行快速检索的树形数据结构。
树是二叉树，树种每一个节点对应于一个
维超矩形区域。
构造 树的方法：
-
构造根节点（根节点对应
-
递归切分
- 在超矩形区域（节点）上选择一个坐标轴和在此坐标轴上的一个切分点；
- 确定一个超平面通过切分点并垂直于坐标轴；
- 将当前超矩形区域切分为左右两个子区域（子节点）
直到子区域内没有实例时终止。在这个过程中，将实例保存在相应的节点上。
通常依次选择坐标轴，切分点选择坐标轴的中位数，这样得到的 树是平衡的（但效率未必是最优的）。
构造平衡 树的算法 为：
- Input：数据集
（在
；
- Output：
-
开始：
构造根节点（根节点对应
选择
为坐标轴，以
由根节点生成深度为 1 的左右子节点：左子节点对应坐标
将落在切分超平面上的实例点保存在根节点。
-
重复：
对深度为
的节点，选择
为切分坐标轴，
，以该节点的区域中所有实例的
由该节点生成深度为
的左右子节点：左子节点对应坐标
将落在切分超平面上的实例点保存在该节点。
-
直到两个子区域没有实例存在时停止。完成
搜索 树
给定一个目标点，搜索其最近邻：
- 找到包含目标点的叶节点；
- 从该叶节点出发，依次回退到父节点；
- 不断查找与目标点最邻近的节点，当确定不可能存在更近的节点时终止。
树的最近邻搜索算法：
- Input：
- Output：
-
在
从根节点出发，递归向下访问
若在当前维度目标点
-
以此叶节点为“当前最近点”。
-
递归向上回退，在每个节点：
- 如果该节点保存的实例点比“当前最近点”离目标点更近，则以该实例点为“当前最近点”；
- 检查该节点的兄弟节点对应的区域是否有更近的点，即，检查兄弟节点对应区域是否与以目标点为中心、以目标点与“当前最近点”间的距离为半径的超球体相较：
- 若相交，则可能存在更近的点，去该兄弟节点，递归进行近邻搜索；
- 若不相交，向上回退。
-
当回退到根节点时，搜索结束。最后的“当前最近节点”即为
如果实例随机分布， 树搜索的平均计算复杂度为
（这里
是训练实例数）。
树更适用于训练实例数远大于空间维度时的
近邻搜索。
我用 Python(3.8) 实现了构造平衡 树和
树的最近邻搜索算法，完整代码在 我的 Github。kNN 算法比较简单，先不做实现。
参考文献
[1] 《统计学习方法（第二版）》李航
[2] 李航《统计学习方法》的代码实现 （from：CSDN 博主 Ooo。）