k近邻模型

Last updated 7 years ago

k近邻模型

$k$ 近邻（k-Nearest Neighbor，简称kNN）学习是一种常用的监督式学习方法，其工作机制非常简单：

给定测试样本，基于某种距离度量找出训练集中与其最靠近的 $k$ 个训练样本，然后基于这 $k$ 个“邻居”的信息来进行预测。通常，在分类任务中可使用“投票法”，即选择这 $k$ 个样本中出现最多的类别标记作为预测结果；在回归任务中可以使用“平均法”，即将这 $k$ 个样本的实值输出标记的平均值作为预测结果；还可以基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

$k$ 近邻有个明显的不同之处：它似乎没有显示的训练过程。事实上，它是“懒惰学习”（lazy learning）的著名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为0，待收到测试样本后再进行处理，这种称为“急切学习”。

1.距离度量

特征空间中两个实例点的距离是两个实例点的相似度的反映。 $k$ 近邻模型的特征空间一般是 $n$ 维实数向量空间 $R^n$ 。使用的距离是欧式距离，但也可以使其他距离，比如更一般的 $L_p$ 距离（ $L_p$ distance），或Minkowski距离。

设特征空间 $X$ 是 $n$ 维实数向量空间 $R^n$ ， $x^{(i)},x^{(j)}\in X$ ， $x=(x_0, x_1, x_2, ..., x_n)^T$ ， $x^{(i)},x^{(j)}$ 的 $L_p$ 距离定义为：

L_p(x^{(i)},x^{(j)})=\big( \displaystyle\sum_{k=1}^n|x^{(i)}_k-x^{(j)}_k|^p\big)^{\frac{1}{p}}

这里 $p \geqslant 1$ 。当 $p=2$ 时，称为欧式距离（Euclidean distance），即

L_2(x^{(i)},x^{(j)})=\big( \displaystyle\sum_{k=1}^n|x^{(i)}_k-x^{(j)}_k|^2\big)^{\frac{1}{2}}

当 $p=1$ 时，称为曼哈顿距离（Manhanttan distance），即

L_1(x^{(i)},x^{(j)})=\displaystyle\sum_{k=1}^n|x^{(i)}_k-x^{(j)}_k|

当 $p=\infty$ 时，它是各个坐标距离的最大值，即：

L_\infty(x^{(i)},x^{(j)})=\max_k|x^{(i)}_k-x^{(j)}_k|

下图给出了 $p$ 取不同值时，与原点的 $L_p$ 距离为 $1$ （ $L_p=1$ ）的图形。

2. k近邻算法

输入：训练集

T=\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(m)},y^{(m)})\}

其中 $x^{(i)}\in X= R^n$ 为实例的特征向量， $y^{(i)}\in Y=\{c_1, c_2, ...,c_t\}$ 为实例的类别， $i=1,2,...,m$ 。某个实例特征向量 $x$ 。

输出：实例 $x$ 的所属类别 $y$

1）根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最邻近的 $k$ 个点，涵盖这 $k$ 个点的邻域记作 $N_k (x)$ ；

2）在 $N_k (x)$ 中根据分类决策规则（如多数表决）决定 $x$ 的类别：

y=arg \max_{c_j} \displaystyle\sum_{x_i\in N_k (x)} I(y_i=c_j)

其中 $i=1,2,...,m$ ， $j=1,2,...,t$ ， $I$ 为指示函数，即当 $y_i=c_j$ 时为 $1$ ，否则为 $0$ 。

$k$ 近邻的特殊情况是 $k=1$ 的情形，称为最近邻算法。对于输入的实例点 $x$ ，最近邻算法将训练数据集中与 $x$ 最近的类作为 $x$ 的类。

$k$ 值的选择会对 $k$ 近邻法的结果产生重大影响。

如果选择较小的 $k$ 值，“学习”的估计误差（estmation error）会增大，预测的结果会对近邻的节点比较敏感。

如果寻则较大的 $k$ 值，“学习”的近似误差（approximation error）会增大，与输入实例较远的训练实例也会对预测起作用，使预测发生错误。

实际中， $k$ 一般取一个比较小的数值，并采用交叉验证法来选取最优的 $k$ 值。

k近邻法最简单的办法就是线性扫描（linear scan），这时要计算输入实例和每一个训练实例的距离，当训练集很大时，非常耗时，这种方法不可行。

下面介绍 $kd$ 树（ $kd$ tree）方法。

PreviousK近邻法 Nextkd树方法

Last updated 7 years ago

$k$ 近邻（k-Nearest Neighbor，简称kNN）学习是一种常用的监督式学习方法，其工作机制非常简单：

pic source：

1.距离度量

设特征空间 $X$ 是 $n$ 维实数向量空间 $R^n$ ， $x^{(i)},x^{(j)}\in X$ ， $x=(x_0, x_1, x_2, ..., x_n)^T$ ， $x^{(i)},x^{(j)}$ 的 $L_p$ 距离定义为：

L_p(x^{(i)},x^{(j)})=\big( \displaystyle\sum_{k=1}^n|x^{(i)}_k-x^{(j)}_k|^p\big)^{\frac{1}{p}}

这里 $p \geqslant 1$ 。当 $p=2$ 时，称为欧式距离（Euclidean distance），即

L_2(x^{(i)},x^{(j)})=\big( \displaystyle\sum_{k=1}^n|x^{(i)}_k-x^{(j)}_k|^2\big)^{\frac{1}{2}}

当 $p=1$ 时，称为曼哈顿距离（Manhanttan distance），即

L_1(x^{(i)},x^{(j)})=\displaystyle\sum_{k=1}^n|x^{(i)}_k-x^{(j)}_k|

当 $p=\infty$ 时，它是各个坐标距离的最大值，即：

L_\infty(x^{(i)},x^{(j)})=\max_k|x^{(i)}_k-x^{(j)}_k|

下图给出了 $p$ 取不同值时，与原点的 $L_p$ 距离为 $1$ （ $L_p=1$ ）的图形。

2. k近邻算法

输入：训练集

T=\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(m)},y^{(m)})\}

其中 $x^{(i)}\in X= R^n$ 为实例的特征向量， $y^{(i)}\in Y=\{c_1, c_2, ...,c_t\}$ 为实例的类别， $i=1,2,...,m$ 。某个实例特征向量 $x$ 。

输出：实例 $x$ 的所属类别 $y$

1）根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最邻近的 $k$ 个点，涵盖这 $k$ 个点的邻域记作 $N_k (x)$ ；

2）在 $N_k (x)$ 中根据分类决策规则（如多数表决）决定 $x$ 的类别：

y=arg \max_{c_j} \displaystyle\sum_{x_i\in N_k (x)} I(y_i=c_j)

其中 $i=1,2,...,m$ ， $j=1,2,...,t$ ， $I$ 为指示函数，即当 $y_i=c_j$ 时为 $1$ ，否则为 $0$ 。

$k$ 近邻的特殊情况是 $k=1$ 的情形，称为最近邻算法。对于输入的实例点 $x$ ，最近邻算法将训练数据集中与 $x$ 最近的类作为 $x$ 的类。

$k$ 值的选择会对 $k$ 近邻法的结果产生重大影响。

如果选择较小的 $k$ 值，“学习”的估计误差（estmation error）会增大，预测的结果会对近邻的节点比较敏感。

如果寻则较大的 $k$ 值，“学习”的近似误差（approximation error）会增大，与输入实例较远的训练实例也会对预测起作用，使预测发生错误。

实际中， $k$ 一般取一个比较小的数值，并采用交叉验证法来选取最优的 $k$ 值。

k近邻法最简单的办法就是线性扫描（linear scan），这时要计算输入实例和每一个训练实例的距离，当训练集很大时，非常耗时，这种方法不可行。

下面介绍 $kd$ 树（ $kd$ tree）方法。