K近邻算法

标签： 统计学习

---

目录

[TOC]

算法

对于新样本，找到最邻近的k个样本，然后根据该k个样本决定新样本的类别
  k近邻法没有显式的学习过程

模型

三个基本要素：距离度量，k值选择，分类决策规则

• 距离度量
  

    Lp距离（Minkowski距离）
    当p=2时，为欧式距离；当p=1时，为曼哈顿距离；当p趋于无穷时，为切比雪夫距离（各个坐标距离的最大值）
• k值选择
• 较小的k值，相当于使用较小的邻域（k值的减少意味着模型的复杂性增加，容易过拟合）：

1. 学习的近似误差（approximation error）小，只有与输入较近的训练样本起作用
2. 学习的估计误差（estimation error）大，结果对近邻的样本非常敏感。若邻近的样本点恰好为噪声，结果就会出错。

• 较大的k值，相当于使用较大的邻域（k值的增加意味着模型会变得简单）：

1. 学习的近似误差会增大与输入较远的训练样本也会起作用
2. 学习的估计误差会减少

应用中通常选择一个小的k值，然后采用交叉验证法选取最优k值

• 分类决策规则
    一般为多数表决（多数表决规则等价于经验风险最小化）