k近邻模型主要包含三个基本要素：距离度量、k值的选择、分类决策规则
模型：
k近邻法中，当训练集、距离度量、k值及分类决策规则确定后，对于一个新的输入实例，它所属的类唯一确定，这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每一点所属的类。
距离度量：
特征空间中的两个实例点的距离是两个实例点相似程度的反映，k近邻模型的特征空间一般是n维实数向量空间Rn.使用的距离时欧氏距离，但也可以使用其他的距离，如Lp距离。当p=1时，称为曼哈顿距离，相应点的坐标之差的绝对值。当p=2时，是欧氏距离。当p=无穷大时，相应点的坐标之差的最大值。
k值的选择：
k值较小时，就意味着整体模型比较复杂，容易发生过拟合。k值较小时，整体模型比较简单，不能进行很好的预测。一般情况下我们会选择k值较小。
分类决策规则：
如果分类的损失函数为0-1 损失函数，分类函数为： f:Rn--{c1,c2,...ck};
那么误分类的概率为： P（Y=/f(x)）=1-P（Y=f(x)）
对于给定的实例x属于X，其中最邻近的k个实例点构成集合Nk(x).如果涵盖Nk(x)的区域的类别是cj,那么误分类的概率是：
1/k*sum I(yi=/cj)=1-1/k*sum I(yi=cj)
要是误分类的概率最小即经验风险最小，就要使sum I(yi=cj)最大，所以多数表决规则等价于经验风险最小化。
原文：http://www.cnblogs.com/angel1314/p/4738855.html