k近邻是一种基本分类与回归方法，书中只讨论分类情况。输入为实例的特征向量，输出为实例的类别。k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。
给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。
k近邻法没有显示的学习过程。
一般为欧式距离，Lp距离、Minkowski距离等
由不同的距离度量所确定的最近邻点是不同的。
k值小时，k近邻模型更复杂，容易发生过拟合；k值大时，模型更简单。k值的选择反映了对近似误差与估计误差之间的权衡，通常由交叉验证选择最优的k。
常用的分类决策规则是多数表决，对应与经验风险最小化。
构造kd树算法如下：
搜索kd树即回溯法：
原文：https://www.cnblogs.com/wwf828/p/9769440.html