K-Nearest Neighbors Algorithm

2019-03-24 本文已影响0人 shenghaishxt

k 近邻法（K-Nearest Neighbors Algorithm，k-NN）是一种基本分类与回归方法，通过多数表决等方式进行预测，因此不具有显式的学习过程。

k 近邻算法

输入：训练数据集 $T = \left\{ \left( x_{1}, y_{1} \right), \left( x_{2}, y_{2} \right), \cdots, \left( x_{N}, y_{N} \right) \right\}$ ，其中 $x_{i} \in \mathcal{X} \subseteq R^{n}$ 是实例的特征向量， $y_{i} \in \mathcal{Y} = \left\{ c_{1}, c_{2}, \cdots, c_{K} \right\}$ 是实例的类别， $i = 1, 2, \cdots, N$ ；实例特征向量 $x$ ；

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

根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最近邻的 $k$ 个点，涵盖这 $k$ 点的 $x$ 的邻域记作 $N_{k} \left( x \right)$ ；
在 $N_{k} \left( x \right)$ 中根据分类决策规则决定 $x$ 的类别 $y$ ：
$\begin{align*} \\ & y = \arg \max_{c_{j}} \sum_{x_{i} \in N_{k} \left( x \right)} I \left( y_{i} = c_{j} \right), \quad i=1,2, \cdots, N; \quad j=1,2,\cdots,K \end{align*}$

k 近邻模型

k 近邻法使用的模型实际上对应于特征空间的划分。模型由三个基本要素——距离度量、k值的选择和分类决策规则决定。

特征空间中，对每个训练实例点 $x_i$ ，距离该点比其他点更近的所有点组成一个区域，叫做单元。下图是二维特征空间划分的一个例子。

距离度量

设特征空间 $\mathcal{X}$ 是 $n$ 维实数向量空间 $R^{n}$ ， $x_{i},x_{j} \in \mathcal{X},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}$ ， $x_{i},x_{j}$ 的 $L_{p}$ 距离定义为
$\begin{align*} \\ & L_{p} \left( x_{i},x_{j} \right) = \left( \sum_{l=1}^{N} \left| x_{i}^{\left(l\right)} - x_{j}^{\left( l \right)} \right|^{p} \right)^{\dfrac{1}{p}}\end{align*}$
其中， $p \geq 1$ 。当 $p=2$ 时，称为欧氏距离，即
$\begin{align*} \\ & L_{2} \left( x_{i},x_{j} \right) = \left( \sum_{l=1}^{N} \left| x_{i}^{\left(l\right)} - x_{j}^{\left( l \right)} \right|^{2} \right)^{\dfrac{1}{2}}\end{align*}$
当 $p=1$ 时，称为曼哈顿距离，即
$\begin{align*} \\ & L_{1} \left( x_{i},x_{j} \right) = \sum_{l=1}^{N} \left| x_{i}^{\left(l\right)} - x_{j}^{\left( l \right)} \right| \end{align*}$
当 $p=\infty$ 时，是各个坐标距离的最大值，即
$\begin{align*} \\ & L_{\infty} \left( x_{i},x_{j} \right) = \max_{l} \left| x_{i}^{\left(l\right)} - x_{j}^{\left( l \right)} \right| \end{align*}$
下图给出了二维空间中 $p$ 取不同值时，与原点的 $L_p$ 距离为1的点的图形：

k 值的选择

如果选择较小的k值：

学习的近似误差减小，但学习的估计误差增大
噪声敏感
整体模型变复杂，容易发生过拟合

如果选择较大的k值：

学习的估计误差减小，但学习的近似误差增大
整体模型变简单

分类决策规则

多数表决规则：如果分类的损失函数为0-1损失函数，分类函数为
$\begin{align*} \\ & f: R^{n} \to \left\{ c_{1}, c_{2}, \cdots, c_{K} \right\} \end{align*}$
则误分类的概率是
$\begin{align*} \\ & P \left( Y \neq f \left( X \right) \right) = 1 - P \left( Y = f\left( X \right) \right) \end{align*}$
对给定的实例 $x \in \mathcal{X}$ ，其最近邻的 $k$ 个训练实例点构成的集合 $N_{k} \left( x \right)$ 。如果涵盖 $N_{k} \left( x \right)$ 的区域的类别是 $c_{j}$ ，则误分类率是
$\begin{align*} \\ & \dfrac{1}{k} \sum_{x_{i} \in N_{k} \left( x \right)} I \left( y_{i} \neq c_{j}\right) = 1 -\dfrac{1}{k} \sum_{x_{i} \in N_{k} \left( x \right)} I \left( y_{i} = c_{j}\right) \end{align*}$
要使误分类率最小即经验风险最小，就要使 $\sum_{x_{i} \in N_{k} \left( x \right)} I \left( y_{i} = c_{j}\right)$ 最大，所以多数表决规则等价于经验风险最小化。

k 近邻法的实现：kd 树

构造 kd 树

平衡kd树构造算法：
输入： $k$ 维空间数据集 $T = \left\{ x_{1}, x_{2}, \cdots, x_{N} \right\}$ ，其中 $x_{i} = \left( x_{i}^{\left(1\right)}, x_{i}^{\left(1\right)},\cdots,x_{i}^{\left(k\right)} \right)^{T}, i = 1, 2, \cdots, N$ ；
输出：kd树

开始：构造根结点，根结点对应于包涵 $T$ 的 $k$ 维空间的超矩形区域。
选择 $x^{\left( 1 \right)}$ 为坐标轴，以 $T$ 中所欲实例的 $x^{\left( 1 \right)}$ 坐标的中位数为切分点，将根结点对应的超矩形区域切分成两个子区域。切分由通过切分点并与坐标轴 $x^{\left( 1 \right)}$ 垂直的超平面实现。
由根结点生成深度为1的左、右子结点：坐子结点对应坐标 $x^{\left( 1 \right)}$ 小于切分点的子区域，右子结点对应于坐标 $x^{\left( 1 \right)}$ 大与切分点的子区域。
将落在切分超平面上的实例点保存在跟结点。
重复：对深度为j的结点，选择 $x^{\left( l \right)}$ 为切分坐标轴， $l = j \left(\bmod k \right) + 1$ ，以该结点的区域中所由实例的 $x^{\left( l \right)}$ 坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{\left( l \right)}$ 垂直的超平面实现。
由根结点生成深度为 $j+1$ 的左、右子结点：坐子结点对应坐标 $x^{\left( l \right)}$ 小于切分点的子区域，右子结点对应于坐标 $x^{\left( l \right)}$ 大与切分点的子区域。
将落在切分超平面上的实例点保存在跟结点。
直到两个子区域没有实例存在时停止。

下面给出一个例子：

搜索 kd 树

kd树的最近邻搜索算法：
输入：kd树；目标点 $x$ ；
输出： $x$ 的最近邻。

在kd树中找出包含目标点 $x$ 的叶结点：从跟结点出发，递归地向下访问kd树。若目标点 $x$ 当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。
以此叶结点为“当前最近点”。
递归地向上回退，在每个结点进行以下操作：
3.1 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。
3.2 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。
如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索；
如果不相交，向上回退。
当回退到根结点时，搜索结束。最后的“当前最近点”即为 $x$ 的当前最近邻点。