KNN模型

距离度量方法

设特征空间 $X$ 是 $n$ 维实数向量空间 $\bf{R}^n$,$x_i, x_j \in \bf{R}^n$,$x_i = (x_i^{(1)},x_i^{(2)},\dots,x_i^{(n)})^T$,$x_j = (x_j^{(1)},x_j^{(2)},\dots,x_j^{(n)})^T$,$x_i$ 和 $x_j$ 的 $L_p$ 距离定义为:
$$ L_p(x_i, x_j) = \left( \sum_{l=1}^{n}| x_i^{(l)} - x_j^{(l)} |^p \right)^{\frac{1}{p}} $$

当 $p=1$ 时,称为曼哈顿距离,即:
$$ L_1(x_i, x_j) = \sum_{l=1}^{n}| x_i^{(l)} - x_j^{(l)} | $$

当 $p=2$ 时,称为欧式距离,即:
$$ L_2(x_i, x_j) = \left( \sum_{l=1}^{n}| x_i^{(l)} - x_j^{(l)} |^2\right)^{\frac{1}{2}} $$

当 $p=\infty $ 时,它是各个坐标距离的最大值
$$L_\infty(x_i, x_j) = \max_l|x_i^{(l)} - x_j^{(l)}|$$

显然,不同的距离度量方法最确定的最近邻点是不同的。

最近邻算法

显然,最近邻算法隐含的决策边界是非线性的。

K 近邻算法

对 $k$ 近邻算法的一个简单改进是对 $k$ 个近邻的贡献加权,根据它们相对查询点 $x$ 的距离,将较大的权值赋给较近的近邻。

因为 $k$ 近邻最简单的实现方法是线性扫描,所以算法缺点十分明显:

  • 存储量大:所有样本需要存到内存
  • 计算量大:每次决策都要计算所有样本的相似性

快速算法

快速搜索近邻法

算法原理:将样本分成不相交的子集,基于子集的搜索

  1. 样本分级分层为多个子集
  2. 逐层搜出一个最优子集
  3. 在最后的子集中局部找最近样本点

典型的快速搜索近邻法就是 $kd$ 树方法:$kd$ 树是一种对 $k$ 维空间内的实例点进行存储以便对其进行快速检索的树形数据结构,$kd$ 树是二叉树,表示对 $k$ 维空间的一个划分。

构造 kd 树

算法过程


算法实例

搜索 kd 树

算法过程


算法实例

这里 是一个关于 $kd$ 树构建和搜索的详细示例,在搜索时不单单是寻找最近邻。

剪辑近邻法

压缩近邻法


拒绝决策近邻法

参考文献:
[1] 周晓飞,《统计机器学习》,中国科学院大学2017年秋季研究生课程
[2] KD树算法之详细篇-聚宽