k 近邻法

k 近邻算法

给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的 k 个实例，这 k 个实例的多数属于某个类，就把该输入实例分为这个类。

算法：k 近邻法

输入：训练数据集 T= {$(x_1, y_1), (x_2, y_2), ... , (x_N, y_N)$}，其中 $x_i$ 为实例的特征向量，$y_i$ 为实例的特征类别，i = 1, 2, ... , N；实例特征向量 x；

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

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

(2) 在 $N_k(x)$ 中根据分类决策规则决定 x 的类别 y： $$ y=arg\underset{c_j}{max}\underset{{x_i\in N_k(x)}}{\Sigma}I(y_i=c_i),\ \ i=1, 2,...,N;\ j=1,2,...,K $$

k 近邻法的特殊情况是 k=1 的情形，称为最近邻算法。k 近邻法没有显示的学习过程。

k 近邻模型

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

距离度量

设特征空间 $\mathcal{X}$ 是 n 维实数向量空间 $\mathcal{R}^n$，$x_i, x_j \in \mathcal{X}, x_i = (x_i^{(1)}, x_i^{(2)}, ..., x_i^{(n)})^T$，$x_i, x_j$ 的 $L_p$ 距离定义为

\[ L_p(x_i,x_j)= \left(\Sigma_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p \right)^{1 \over p} \]

这里 $p \ge 1$.

当 $p=2$ 时，称为欧氏距离，即

\[ L_2(x_i,x_j)= \left(\Sigma_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^2 \right)^{1 \over 2} \]

当 $p=1$ 时，称为曼哈顿距离，即

\[ L_1(x_i,x_j)= \Sigma_{l=1}^n|x_i^{(l)}-x_j^{(l)}| \]

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

\[ L_{\infty}(x_i, x_j) = max_l\ |x_i^{(l)}-x_j^{(l)}| \]

k 值的选择

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

k 值的减小意味着整体模型变得复杂，容易发生过拟合；k 值的增大意味着整体模型变得简单，学习的近似误差增大.

在应用中，k 值一般取一个比较小的数值，通常采用交叉验证法来选取最优的 k 值.

分类决策规则

k 近邻法中的分类决策规则往往是多数表决，即有输入实例的 k 个邻近的训练实例中的多数类决定输入实例的类：如果分类的损失函数为 $0-1$ 损失函数，分类函数为

\[ \mathcal{f}:\mathcal{R}^n \rightarrow \{c_1, c_2, ..., c_K\} \]

误分类的概率为

\[ P(Y \ne f(X)) = 1 - P(Y=f(X)) \]

对给定的实例 $x \in \mathcal{X}$，其最近邻的 k 个训练实例点构成集合 $N_k(x)$. 如果涵盖 $N_(x)$ 的区域的类别是 $c_j$，那么误分类率是

\[ {1\over k} \Sigma_{x_i \in N_k(x)}\ I(y_i \ne c_i)=1 - {1 \over k}\Sigma_{x_i \in N_k(x)} \ I(y_i=c_i) \]

要使误分类率最小即经验风险最小，就要使 $\Sigma _{x_i \in N_kl(x)} \ I(y_i = c_j)$ 最大，所以多数表决规则等价于经验风险最小化.

k-d 树

构造

构造根结点，使根结点对应于 k 维空间中包含所有实例点的超矩形区域
通过下面的递归方法，不断地对 k 维空间进行切分：
1. 生成子结点在超矩形区域 (结点) 上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面
2. 这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域 (子结点)：这时，实例被分到两个子区域
3. 这个过程直到子区域内没有实例时终止 (终止时的结点为叶结点)。在此过程中，将实例保存在相应的结点上。

算法: 构造平衡 kd 树

输入: $T= {(x_1, y_1), (x_2, y_2), ... , (x_N, y_N)}$, 其中 $x_i = (x_i^{(1)}, x_i^{(2)}, ..., x_i^{(n)})^T$, $i=1, 2,...,N$;

输出: kd 树.

开始: 构造根结点，根结点对应于包含T的k维空间的超矩形区域。

选择 $x^{(1)}$ 为坐标轴，以 $T$ 中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(1)}$ 垂直的超平面实现。

由根结点生成深度为 1 的左、右子结点:左子结点对应坐标 $x^{(1)}$ 小于切分点的子区域，右子结点对应于坐标 $x^{(1)}$ 大于切分点的子区域。将落在切分超平面上的实例点保存在根结点。

重复: 对深度为 $j$ 的结点，选择 $x^{(l)}$ 为切分的坐标轴, $l=j(mod\ k)+1$，以该结点的区域中所有实例的 $x^{(l)}$ 坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(l)}$ 垂直的超平面实现。

由该结点生成深度为 $j+1$ 的左、右子结点: 左子结点对应坐标 $x^{(l)}$ 小于切分点的子区域，右子结点对应坐标 $x^{(l)}$ 大于切分点的子区域。

将落在切分超平面上的实例点保存在该结点。

直到两个子区域没有实例存在时停止。从而形成 $kd$ 树的区域划分.

搜索

利用 kd 树可以省去对大部分数据点的搜索, 从而减少搜索的计算量.

如果实例点是随机分布的, kd 树搜索的平均计算复杂度是 $O(logN)$, 这里 $N$ 是训练实例数.

算法: 用 $kd$ 树的最近邻搜索

输入: 已构造的 $kd$ 树, 目标点 $x$;

输出: $x$ 的最近邻.

在 $kd$ 树中找出包含目标点 $x$ 的叶结点: 从根结点出发，递归地向下访问 $kd$ 树. 若目标点 $x$ 当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点. 直到子结点为叶结点为止.

以此叶结点为“当前最近点”.

递归地向上回退，在每个结点进行以下操作:

如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”.

当前最近点一定存在于该结点一个子结点对应的区域. 检查该子结点的父结点的另一子结点对应的区域是否有更近的点. 具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交.

如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点. 接着，递归地进行最近邻搜索; 如果不相交，向上回退.

当回退到根结点时，搜索结束。最后的“当前最近点”即为 $x$ 的最近邻点.