输入:训练数据集
其中,
为实例的特征向量,
; 输出:实例x所属的类y (1)根据给定距离度量,训练集T中找与x最近邻的k个点,涵盖k个点的x的邻域记
(2)根据多数表决规则决定x的类别y
;
;
k近邻模型三要素:距离度量、k值选择、分类决策规则 距离度量:
距离
p=1时,为曼哈顿距离
p=2时,为欧氏距离
p=∞时,为各个坐标距离的最大值
k值选择:通常采用交叉验证确定最优的k值 分类决策规则:多数表决规则 0-1损失函数下,分类函数
误分类概率:
实例
,其最近邻的k个训练实例构成集合
,涵盖
的区域类别是
,则误分类率:
即使
最大,也即多数表决规则等价于经验风险最小化。