1.同一标签的样本通常有很多相似的特征,所以同一类别的可能有扎堆现象,也就是物以类聚。
2.每进来一个样本,我们查看它周围的样本是什么类别的,那它也有极大可能属于该类别。
首先令 x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \ldots, x_{i}^{(n)}\right), x_{j}=\left(x_{j}^{(1)}, x_{j}^{(2)}, \ldots, x_{j}^{(n)}\right)
欧式距离(也称二范数):
曼哈顿距离(也称一范数):
P范数:
切比雪夫距离(类似于国际象棋的后)
当
时, 它是各个坐标距离的最大值, 即
k值的选择会对k近邻法的结果产生重大影响。 如果选择较小的k值,就相当于用较小的邻域中的训练实例进行预测,“学习”的近似误差(approximation error)会减小,只有与输入实例较近的(相似的)训练实例才会对预测结果起作用。但缺点是“学习”的估计误差(estimation error)会增大,预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声,预测就会出错。换句话说,k值的减小就意味着整体模型变得复杂,容易发生过拟合。
如果选择较大的k值,就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差,但缺点是学习的近似误差会增大。这时与输入实例较远的(不相似的)训练实例也会对预测起作用,使预测发生错误。k值的增大就意味着整体的模型变得简单。
如果k =N,那么无论输入实例是什么,都将简单地预测它属于在训练实例中最多的类。这时,模型过于简单,完全忽略训练实例中的大量有用信息,是不可取的。
在应用中,k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。
k近邻法中的分类决策规则往往是多数表决,即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
多数表决规则(majority voting rule)有如下解释:如果分类的损失函数为0-1损失函数.分类函数为:
那么误分类的概率是
对给定的实例 x \in \mathcal{X} , 其最近邻的 k 个训练实例点构成集合 N_{k}(x) 。如果涵盖 N_{k}(x) 的区域的类别是 c j c_{j} cj , 那么误分类率是
要使误分类率最小即经验风险最小, 就要使 \sum_{x_{i} \in N_{k}(x)} I\left(y_{i}=c_{j}\right) 最大, 所以多数表决规则等价于经验风险最小化。
注意:
为指示函数,即x条件为真,则函数值为1,x条件为假,则函数值为0。