k近邻法不具有显式的学习过程。k近邻法利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。
k值的选择，距离度量及分类决策规则是k近邻法得三个基本要素。

k近邻算法

k近邻法

1. 根据给定的距离度量，在训练集T中找出与x最领进的k个点，涵盖这k个点的x的邻域记作 <nobr> Nk(x) </nobr>；
2. 在 <nobr> Nk(x) </nobr>中根据分类决策规则（如多数表决）决定x的类别y：
   <nobr> y=argmaxcjI(yi=cj),i=1,...,N;j=1,...,K(3.1) </nobr>
   式(3.1)中， <nobr> I </nobr>为指示函数，即当 <nobr> yi=cj </nobr>时 <nobr> I </nobr>为1，否则 <nobr> I </nobr>为0。

距离度量

闵科夫斯基距离
<nobr> Lp(xi,xj)=(∑l=1N|x(l)i−x(l)j|p)1p </nobr>
这里 <nobr> p≥1 </nobr>。当p=2时，称为欧式距离。
当 <nobr> p=1 </nobr>时，称为曼哈顿距离。
当 <nobr> p=∞ </nobr>时，它是各个坐标举例的最大值，即
<nobr> L∞(xi,xj)=maxl|x(l)i−x(l)j| </nobr>

k值的选择

k值小，整体模型复杂，容易过拟合。

分类决策规则

多数表决规则等价于经验风险最小化。

k近邻法的实现：kd树

参考文献

《统计学习方法》第3章