《统计学习方法》极简笔记P3：k-NN数学推导

k近邻算法

输入：训练数据集

其中，

为实例的特征向量，

; 输出：实例x所属的类y (1)根据给定距离度量，训练集T中找与x最近邻的k个点，涵盖k个点的x的邻域记

(2)根据多数表决规则决定x的类别y

;

;

k近邻模型

k近邻模型三要素：距离度量、k值选择、分类决策规则 距离度量：

距离

p=1时，为曼哈顿距离

p=2时，为欧氏距离

p=∞时，为各个坐标距离的最大值

k值选择：通常采用交叉验证确定最优的k值 分类决策规则：多数表决规则 0-1损失函数下，分类函数

误分类概率：

实例

,其最近邻的k个训练实例构成集合

,涵盖

的区域类别是

,则误分类率：

即使

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