K近邻法

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

模型
- 每个训练实例点，距离该点比其他点更近的所有点构成的区域称为一个单元
- 所有实例点的单元构成对特征空间的一个划分
- 将所有实例的类作为各实例点对应单元的类标记
距离度量
- 是两个实例点相似程度的反映
- $L_p距离$
  - 对$n$维实数空间$\boldsymbol{R}^N$，$x_i, x_j \in \mathcal{X}, x_i = (x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T, x_j = (x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^T$
  - $L_p距离$定义为：
    $$L_p(x_i, x_j)=\left( \sum\limits_{I=1}^N |x_i^{(I)} - x_j^{(I)}|^p \right)^{\frac{1}{p}} , \quad p \ge 1$$
  - $p=2$时是欧氏距离；$p=1$时是曼哈顿距离；
  - $p = \infty$时是各坐标距离最大值，即$L_{\infty}(x_i, x_j)= \max\limits_{l} |x_i^{(l)} - x_j^{(l)}|$
K值的选择
- K太小，近似误差小，估计误差大，模型容易过拟合（分的太细）
- K太大，可以减小估计误差，但近似误差会增大，模型欠拟合（分的太粗）
- K=N，即模型只会把要预测的点分入点最多的类中，不可取。
- 采用交叉验证的方法选取K值
分类决策规则
- “多数表决”：即K个临近点中点最多的类别就是待分类点的类别
- 若分类函数的损失函数为0-1损失函数
  - 分类函数为：
    - $f: \boldsymbol{R}^n = {c_1, c_2, …, c_K}$
  - 误分类的概率为：
    - $P(Y \neq f(X))=1-P(Y = f(X))$
  - 对给定实例$x \in \boldsymbol{x}$，最邻近的K个点构成集合$N_K(x)$，类别共$c_j$个，则误分类率是：
    $$\cfrac{1}{k}\sum\limits_{x_i \in N_K(x)} I(y_i \neq c_j) = 1-\cfrac{1}{k}\sum\limits_{x_i \in N_K(x)} I(y_i = c_j)$$

K近邻法的实现：KD树

算法是为了减少计算距离的次数，这对大规模数据的K近邻操作十分必要

构造KD树（是一个二叉树）
- 相当于不断地用垂直于坐标轴的超平面将K维空间划分，每个节点都对应一个K维超矩形区域
- 根节点对应包含所有实例点的超矩形区域
- 子节点划分方式：选择实例点在选定坐标轴上的中位数进行切分
  - 这样得到的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$
- 构造根节点
- 选择$x^{(1)}$为坐标轴，以$T$中所有实例的$x^{(1)}$坐标的中位数为切分点划分为两个子区域，生成为根节点的两个子节点：左子节点对应小于切分点的区域，右子节点对应大于切分点的区域
- 落在切分超平面上的点保存在根节点
- 重复：选择$x^{(l)}$为坐标轴，$l = j(\mod k) + 1$
- 直到子区域没有实例存在时停止
搜索算法
- 输入：已构造的KD树，目标点x
- 从根结点出发，依照x当前维坐标访问KD树，直到叶节点
- 以此节点为当前最近点，向上回退：
  - 若该节点保存的实例点比当前最近点距离目标点更近，则更新“当前最近点”为回退点中那个更近的实例点
  - 检查另一个子节点对应区域是否有更近的点，检查相交：
    - 如果相交，就更新到那个子节点
    - 不相交，向上回退
  - 回退到根节点时，搜索结束，最后的“当前最近点”即为x的最近邻点
  - 算法时间复杂度为O(logN)，N是训练实例数