k近邻法

输入：训练数据集


其中，为实例的特征向量，为实例的类别，,实例特征向量;
输出：实例所属的类



k近邻模型

模型

近邻模型中，当训练集，距离度量（如欧氏距离），值及分类决策规则，（如多数表决）确定后，对于任何一个新的输入实例，它所属的类唯一确定。

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反应。近邻模型的特征空间一般是维实数向量空间。使用的距离是欧
氏距离，也可以是其他的距离如更一般的距离或者距离。

K值的选择

如果选择较小的K值，学习的近似误差较小，只有与实例相近的训练实例才会起作用。整体模型会复杂，容易过拟合。
如果选择较大的K值，学习的近似误差会变大，使预测发生错误。
在应用中，一般选取一个较小的数值，通才采取交叉验证选取最优的。

分类决策规则

多数表决，也是经验风险最小。

k近邻法的实现－－kd 树

kd 树，一种对k维空间中的实例点进行储存以便对其进行快速检索的树形数据结构。
在这里不做详细解释。