k近邻法是一种基本分类与回归方法，输入特征向量，输出类别（可以取多类）。分类时，对新实例根据其k个最近邻的训练实例的类别，通过多数表决进行预测，不具有显式的学习过程。
k近邻算法
k近邻模型
模型
每个训练实例附近的点组成一个cell，这些cell对特征空间进行划分，每个cell中的类相同。
距离度量
一般是在$R^n$上使用欧氏距离，也可以是更一般的$L_p$距离或Minkowski距离。
- p=1时是曼哈顿距离
- p=2时是欧氏距离
- p=∞时是各个坐标距离的最大值
K值选择
- k较小，近似误差减小——只有与输入相近的点起作用，估计误差增大——对相近的点很敏感，模型变得复杂，易过拟合。
- k较大，近似误差增大，估计误差减小，模型更简单
一般取比较小的k，用交叉验证选取最优的k。
分类决策规则
通常是多数表决
k近邻法的实现：kd树
kd树是二叉树，表示对k维空间的一个划分。
构造kd树
不断用垂直于坐标轴的超平面划分k维空间，构成超矩形区域，每个结点对应一个超矩形。
搜索kd树
