K近邻法

机器学习 K近邻法

---

定义
输入： 训练数据集

$$T = \{(x_1, y_1), (x_2, y_2), ... (x_N, y_N)\}$$
其中，$x_i \in X \subseteq R^n$为实例的特征向量，$y_i \subseteq Y = \{c_1, c_2, ... c_k\}$为实例的类别，$i = 1, 2, ...N$;
输出：实例$x$所属的类$y$
1. 根据给定的距离度量，在训练集$T$中找出与$x$最邻近的$k$个点，涵盖这$k$个点的$x$的临域记作$N_k(x)$
2. 在$N_k(x)$中根据分类决策规则决定$x$的类别$y$:
$$y = arg \max_{c_j}\sum_{x_i \in N_k(x)} I(y_i=c_j), i = 1,2,...,N; j = 1,2,...,K$$
当$k=1$时，称为最近邻算法。

距离度量

$$L_p(x_i, x_j) = (\sum_{l=1}^{n}{|{x_i}^l - {x_j}^l|}^p)^{(1/p)}$$
$p=1$, 曼哈顿距离
$p=2$, 欧氏距离
$p=\infty$, 它是各个坐标距离的最大值
$$L_{\infty}(x_i, x_j) = \max_l|{x_i}^l - {x_j}^l|$$

使用kd树求取最近邻，kd树的构建
输入：k维空间数据集$T={x_1, x_2,...,x_N}$,其中$x_i={({x_i}^{(1)}, {x_i}^{(2)},...,{x_i}^{(k)})}^T, i=1,2,...N$
输出： kd树
1. 开始：构造根节点，根节点对应于包含T的k维空间的超矩形区域；
2. 对于第j层，选择第$l = j (mod \space k) + 1$维数据进行切分，按中位数将数据切分为两个子集；
3. 重复2，直到所有的数据被切分。

使用kd树进行搜索
输入： 已构造的kd树，目标点x；
输出：x的最近邻

1. 按照切分规则，找到x点归属的叶子节点；
2. 以该叶子节点为当前最近点；
3. 递归的向上回退，在每个节点进行以下操作：
   
   • 如果该节点保存的实例点比当前最近点距离目标点更近，则以该实例点为当前最近点；
   • 当前最近点一定存在于该节点一个子节点对应的区域。检查该子节点的父节点的另一个节点对应的区域是否有更近的点。

代码实现
python