k 近邻算法 k-NN

k 近邻法：基本分类与回归方法

基本思想

给定一个训练数据集，其中实例类别已定。对于新的实例，根据其 $k$ 个最近邻的训练实例的类别，通过多数表决等方式进行预测

输入：训练数据集

$$
T={(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)}
$$

  • $x_i\in\chi\subseteq R^n$：实例的特征向量
  • $y\in\psi={c_1,c_2,\dots,c_k}$

三要素

  • $k$ 值选择
  • 距离度量
  • 分类决策规则

kd 树

k 近邻法最简单的实现方式是线性扫描（Linear Scan），但不适用于大训练集

构造 kd 树

  • kd 树是二叉树
  • 表示对 $k$ 维空间的一个划分（paritition）
  • 不断用垂直于坐标轴的超平面对 $k$ 维空间进行划分，构成一系列 $k$ 维超矩形区域
  • kd 树的每个结点对应一个 $k$ 维超矩形区域

步骤

例：给定一个二维空间的数据集：$T={(2,3)^T,(5,4)^T,(9,6)^T,(4,7)^T,(8,1)^T,(7,2)^T}$，构造一个平衡 kd 树

  • 选择 $x^{(1)}$ 轴，6 个数据点的 $x^{(1)}$ 坐标中位数为 $6$（但是对应没有数据点，所以取 $5$ 或 $7$），取 $7$，以平面 $x^{(1)}=7$ 将空间分为左右两个子矩形（即为子节点）
  • 接着对于左矩形，取 $x^{(2)}$ 的中位数，以 $x^{(2)}=4$ 分为两个子矩形；右矩形同理以 $x^{(2)}=6$ 分为两个子矩形
  • 递归

![[images/截屏2026-03-23 13.21.03.png]]