Day7~8 第三章 k 近邻

作者: Bocchi | 来源:发表于2023-02-20 22:44 被阅读0次

1 k 近邻算法

$k$ 近邻算法的思想是：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的 $k$ 个实例，这 $k$ 个实例的多数属于某个类，就把该输入实例分为这个类。
算法 3.1 ( $k$ 近邻算法)
输入：训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$ 其中 $x_i\in\mathcal{X}=\mathbb{R}^n$ ， $y_i\in\mathcal{Y}=\{c_1,c_2,\dots,c_K\}$ ， $i=1,2,\dots,N$ ；实例向量 $x$ ；
输出：实例 $x$ 所属的类 $y$ ；
(1) 根据给定的度量距离，在训练集 $T$ 中找出与 $x$ 最邻近的 $k$ 个点，涵盖这 $k$ 个点的 $x$ 的邻域作 $N_k(x)$ ；
(2) 在 $N_k(x)$ 中根据分类决策规则决定 $x$ 的类别 $y$ ： $y=\text{arg}\max\limits_{c_j}\sum\limits_{x_i\in N_k(x)} I(y_i=c_j),\quad i=1,2,\dots,N;\ j=1,2,\dots,K$ 式中， $I$ 为指示函数，即当 $y_i=c_i$ 时 $I$ 为 1，否则 $I$ 为 0。

$k$ 近邻法的特殊情况是 $k=1$ 的情形，称为最近邻算法；

$k$ 近邻法没有显式的学习过程；

$k$ 值、度量距离以及分类决策规则是 $k$ 近邻法的三个基本要素。当训练集以及三个基本要素确定后，对于任何一个新的输入实例，它所属的类唯一地确定。

从算法的步骤不难发现，KNN 是一种 lazy-learning 算法，分类器不需要进行训练，即训练过程的时间复杂度为 0。KNN 分类的计算复杂度和训练集中的实例数目成正比，也就是说，如果训练集中实例总数为 $n$ ，那么 KNN 的分类时间复杂度为 $O(n)$ 。

2 k 近邻模型

2.1 度量距离

设特征空间 $\mathcal{X}=\mathbb{R}^n$ ， $x_i,x_j\in\mathcal{X}$ ， $x_i=(x_i^{(1)},x_i^{(2)},\dots,x_i^{(n)})^T$ ， $x_i,x_j$ 的 $L_p$ 距离定义为 $L_p(x_i,x_j)= \left(\sum\limits_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p\right)^{\frac{1}{p}}$ 其中 $p\geqslant 1$ 。

当 $p=2$ 时，称为欧式距离： $L_2(x_i,y_j) = \left(\sum\limits_{l=1}^{n} |x_i^{(l)}-x_j^{(l)}|^2\right)^{\frac{1}{2}}$

当 $p=1$ 时，称为曼哈顿距离： $L_1(x_i,y_j) = \sum\limits_{l=1}^{n} |x_i^{(l)}-x_j^{(l)}|$

当 $p=\infty$ 时，称为切比雪夫距离： $L_\infty(x_i,y_j) = \max\limits_{l} |x_i^{(l)}-x_j^{(l)}|$

2.2 k 值的选择

$k$ 值的选则会对 $k$ 近邻法的结果产生重大影响。
若选则的 $k$ 值较小，学习的近似误差会减小，只有与输入实例较近的点会对预测结果起作用；但学习的估计误差会增大，预测结果会对近邻的点的实例点十分敏感，容易发生过拟合。反之，若选则的 $k$ 值较大，可以减少学习的估计误差，但是学习的近似误差会增大。

2.3 分类决策规则

$k$ 近邻法中的决策规则往往采用多数表决规则。多数表决规则 (majority voting rule) 有如下解释：若分类的损失函数为 0-1 损失函数，分类函数为 $f:\mathbb{R}^n\rightarrow \{c_1,c_2,\dots,c_K\}$ 那么误分类的概率是 $P(Y\neq f(X))=1-P(Y=f(X))$ 对给定的实例 $x\in\mathcal{X}$ ，其最近邻的 $k$ 个训练实例点构成集合 $N_k(x)$ 。若涵盖 $N_k(x)$ 的区域类别是 $c_j$ ，那么误分类是 $\frac{1}{k}\sum\limits_{x_i\in N_k(x)}I(y_i\neq c_j)=1-\frac{1}{k}\sum\limits_{x_i\in N_k(x)}I(y_i=c_j)$ 要使误分类率最小即经验风险最小，就要使 $\sum\limits_{x_i\in N_k(x)}I(y_i=c_j)^{}$ 最大，所以多数表决规则等价于经验风险最小化。

3 k 近邻法的实现：kd 树

1. 背景 ^[1]
一般说来，索引结构中相似性查询有两种基本的方式：
(1) 范围查询：范围查询时给定查询点和查询距离阈值，从数据集中查找所有与查询点距离小于阈值的数据。
(2) k 近邻查询：就是给定查询点及正整数 k，从数据集中找到距离查询点最近的K个数据；当 k=1 时，它就是最近邻查询。
同样，针对特征点匹配也有两种方法：
(1) 线性扫描，也就是我们常说的穷举搜索，依次计算样本集中每个样本到输入实例点的距离，然后抽取出计算出来的最小距离的点即为最近邻点。此种办法简单直白，但当样本集或训练集很大时，计算将会非常耗时，明显是不足取的。
(2) 构建数据索引，因为实际数据一般都会呈现簇状的聚类形态，因此我们想到建立数据索引，然后再进行快速匹配。索引树是一种树结构索引方法，其基本思想是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为 Clipping 和 Overlapping 两种。前者划分空间没有重叠，其代表就是 k-d 树；后者划分空间相互有交叠，其代表为 R 树。

2. 构造 kd 树
kd 树中，kd 代表 k-dimension，每个节点即为一个k维的点。构造 kd 树的思想就是将每个非叶节点想象为一个分割超平面，用垂直于坐标轴的超平面将空间分为两个部分，这样递归的从根节点不停的划分，直到没有实例为止。具体算法如下：
算法 3.2 (构造平衡 kd 树)
输入： $k$ 维空间数据集 $T=\{ x_1,x_2,\dots, x_N\}$ ，其中 $x_i = ( x_i^{( 1 )} , x_i^{(2)} , ⋯ , x_i^{(k)})^T$ ， $i=1,2,\dots,N$ ；
输出：kd 树；
(1) 开始：构造根结点，根结点对应于包含 $T$ 的 $k$ 维空间的超矩形区域。
选择 $^{(1)}$ 为坐标轴，以 $T$ 中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(1)}$ 垂直的超平面实现。
由根结点生成深度为1的左、右子结点：左子结点对应坐标 $x^{(1)}$ 小于切分点的子区域，右子结点对应于坐标 $x^{(1)}$ 大于切分点的子区域。
将落在切分超平面上的实例点保存在根结点。
(2) 重复：对深度为 $j$ 的结点，选择 $x^{(l)}$ 为切分的坐标轴， $l＝j(\text{mod} \ k)+1$ ，以该结点的区域中所有实例的 $x^{(l)}$ 坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(l)}$ 垂直的超平面实现。
由该结点生成深度为 $j+1$ 的左、右子结点：左子结点对应坐标 $x^{(l)}$ 小于切分点的子区域，右子结点对应坐标 $x^{(l)}$ 大于切分点的子区域。
将落在切分超平面上的实例点保存在该结点。
(3) 直到两个子区域没有实例存在时停止。从而形成 kd 树的区域划分。

构造 kd 树的规则有三种：随机划分（玄学）、轮换划分（每个维度轮着划分）与方差划分（优先划分方差较大的维度）。

书中介绍的是轮换划分：

随着树的深度增加，循环的选取坐标轴，作为分割超平面的法向量。例如 3-d tree，根节点选取 x 轴，根节点的孩子选取 y 轴，根节点的孙子选取 z 轴，根节点的曾孙子选取 x 轴，这样循环下去。

每次均为所有对应实例的中位数的实例作为切分点，切分点作为父节点，左右两侧为划分的作为左右两子树。

对于轮换划分以中位数 (期望时间复杂度 $\Theta(n)$ ) 的实例点作为切分点故有递推式： $T(n)=2T(n/2)+\Theta(n)$ 根据主定理有 $a=2$ ， $b=2$ ， $\log_b a=1$ ， $f(n)=\Theta(n)$ ；
基准函数为 $\Theta(n^{\log_b a})=\Theta(n)$ ；
故有期望时间复杂度为 $T(n) = \Theta(n\log n)$

3. 搜索 kd 树
搜索 kd 树的思想就是根据所给定的目标点，搜索其最近邻。首先找到包含目标点的叶节点；然后从该叶节点出发，一次回退到父节点；不断查抄与目标点最邻近的节点，当确定不可能存在更近的节点是终止。这样搜索就被限制在空间的局部区域上。具体算法如下：
算法 3.3 (用 kd 树的最近邻搜索)
输入：已构造的 kd 树，目标点 x；
输出：x 的最近邻
(1) 在 kd 树种找出包含目标点x的叶结点：从根结点出发，递归地向下搜索 kd 树。若目标点 x 当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点，直到子结点为叶结点为止。
(2) 以此叶结点为“当前最近点”。
(3) 递归的向上回溯，在每个结点进行以下操作：
(a) 如果该结点保存的实例点比当前最近点距离目标点更近，则更新 “当前最近点”，也就是说以该实例点为 “当前最近点”。
(b) 当前最近点一定存在于该结点一个子结点对应的区域，检查子结点的父结点的另一子结点对应的区域是否有更近的点。具体做法是，检查另一子结点对应的区域是否以目标点位球心，以目标点与 “当前最近点” 间的距离为半径的圆或超球体相交：
如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点，接着，继续递归地进行最近邻搜索；如果不相交，则向上回溯。
(4) 当回退到根结点时，搜索结束，最后的 “当前最近点” 即为 x 的最近邻点。

如果实例点是随机分布的，那么kd树搜索的期望计算复杂度是 $\Theta(\log N)$ ，这里的 $N$ 是训练实例树。所以说，kd 树更适用于训练实例数远大于空间维数时的 k 近邻搜索，当空间维数接近训练实例数时，它的效率将会退化至线性扫描的速度。

Day7~8 第三章 k 近邻

1 k 近邻算法

2 k 近邻模型

2.1 度量距离

2.2 k 值的选择

2.3 分类决策规则

3 k 近邻法的实现：kd 树

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读