K近邻算法
标签： 统计学习
目录
[TOC]
算法
对于新样本，找到最邻近的k个样本，然后根据该k个样本决定新样本的类别
k近邻法没有显式的学习过程
模型
三个基本要素：距离度量，k值选择，分类决策规则
-
距离度量
Lp距离（Minkowski距离）
当p=2时，为欧式距离；当p=1时，为曼哈顿距离；当p趋于无穷时，为切比雪夫距离（各个坐标距离的最大值） - k值选择
- 较小的k值，相当于使用较小的邻域（k值的减少意味着模型的复杂性增加，容易过拟合）：
- 学习的近似误差（approximation error）小，只有与输入较近的训练样本起作用
- 学习的估计误差（estimation error）大，结果对近邻的样本非常敏感。若邻近的样本点恰好为噪声，结果就会出错。
- 较大的k值，相当于使用较大的邻域（k值的增加意味着模型会变得简单）：
- 学习的近似误差会增大与输入较远的训练样本也会起作用
- 学习的估计误差会减少
应用中通常选择一个小的k值，然后采用交叉验证法选取最优k值
- 分类决策规则
一般为多数表决（多数表决规则等价于经验风险最小化）
