$k$ 近邻法（ $k-NN$ ）

一种基本的分类与回归方法。

$k$ 近邻算法

思想
给定一个训练数据集，对新的输入示例，在训练集中找到与该实例最近邻的 $k$ 个实例，依据这 $k$ 个实例进行分类。
特点
- 监督学习
- 懒惰学习
- 假设——基于样本总能在任意小距离内找到一个训练样本——在现实中可能不成立。
- 算法重点在于距离度量
算法规范表述
- 输入：训练样集 $T$ ，待检测的样本 $x$
- 输出：实例 $x$ 所属的类 $y$
- 计算
  1. 根据给定的距离度量，在训练集 $T$ 中找到与 $x$ 最近的 $k$ 个点，包含这 $k$ 个点的邻域记作 ${N_k}\left( x \right)$
  2. 在 ${N_k}\left( x \right)$ 中根据分类决策规则（如多数表决等）决定 $x$ 的类别 $y$ :
    $y = \arg \mathop {\max }\limits_{{c_j}} \sum\limits_{{x_i} \in {N_k}\left( x \right)} {I\left( {{y_i} = {c_j}} \right),\;i = 1,2,} \cdots ,N;\;j = 1,2, \cdots ,K$
    其中 $I$ 为指示函数，当 $y_i=c_j$ 时为 $1$ ，否则为 $0$ 。
最邻近算法
令 $k=1$ 时，称为最邻近算法。

$k$ 近邻模型

$k$ 近邻法使用的模型实际上对应于特征空间的划分，包括三个基本要素：距离度量、 $k$ 值得选择以及分类决策规则。

模型

在 $k$ 近邻中，如果训练集、距离度量、 $k$ 值以及分类决策确定后，新的输入实例的类也唯一确定。

相当于根据上述要素将特征空间划分为子空间，确定子空间每个点所属的类。

单元：对于每个训练样本 $x_i$ ，距离该点比其他点更近的所有点构成的区域。

距离度量

对于训练样本中的任意两个样本 $x_i,x_j$ ，其特征空间为 $n$ ，即 ${x_i} = {\left( {x_i^{\left( 1 \right)},x_i^{\left( 2 \right)}, \cdots ,x_i^{\left( n \right)}} \right)^T},{x_j} = {\left( {x_j^{\left( 1 \right)},x_j^{\left( 2 \right)}, \cdots ,x_j^{\left( n \right)}} \right)^T}$ ，常用的距离包括以下几种：

$L_p$ 距离
${L_p}\left( {{x_i},{x_j}} \right) = {\left( {\sum\limits_{l = 1}^n {{{\left| {x_i^{\left( l \right)} - x_j^{\left( l \right)}} \right|}^p}} } \right)^{\frac{1}{p}}}$
$p=1$ 时，为曼哈顿距离
${L_1}\left( {{x_i},{x_j}} \right) = \sum\limits_{l = 1}^n {\left| {x_i^{\left( l \right)} - x_j^{\left( l \right)}} \right|}$
$p=2$ 时，为欧式距离
${L_2}\left( {{x_i},{x_j}} \right) = \sqrt {\sum\limits_{l = 1}^n {{{\left| {x_i^{\left( l \right)} - x_j^{\left( l \right)}} \right|}^2}} }$
$p=\infty$ 时，是各个坐标距离的最大值
${L_\infty }\left( {{x_i},{x_j}} \right) = \mathop {\max }\limits_l \left| {x_i^{\left( l \right)} - x_j^{\left( l \right)}} \right|$
下图给了详细的表示（不同算法距离是不同的）。

$k$ 值选择

$k$ 值选择的不同也会产生巨大影响。
两种选择：

选择较小的 $k$ 值：
- 优点
  - 近似误差小（只有与输入实例相近的才会影响结果）
- 缺点
  - 估计误差大（预测结果对临近点非常敏感）

总的来说，随着 $k$ 值减小，整体模型变复杂，易发生过拟合。

选择较大的 $k$ 值：
优缺点正好与选择较小 $k$ 值相反。

通常选择较小的 $k$ ，并使用交叉验证选择最优 $k$ 值。

分类决策规则

$k$ 近邻中使用的往往是多数表决，应该很好理解就不赘述了。
多数表决规则等价于经验风险最小化。

参考文献

《机器学习》
《统计学习方法》

统计学习方法——K近邻法【k-NN】（一）

k近邻法

kkk近邻法（k−NNk-NNk−NN）

kkk 近邻算法

kkk近邻模型

模型