跳转至

K-近邻算法

概述

K近邻算法 (K-Nearest Neighbors, KNN) 是一种基础的监督学习算法，既可以用于分类问题，也可以用于回归问题（本书不详细讨论）

k近邻法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。

k近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决 等方式进行预测。k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素

k近邻法有常见一个实现方法——kd树，后文将介绍构造kd树和搜索kd树的算法。

算法概述

对于一个新的未知样本：

  1. 确定K值: 选择一个正整数K。
  2. 计算距离: 计算未知样本与训练集中所有样本之间的距离。常用的距离度量有欧氏距离、曼哈顿距离等。
  3. 找到K个最近邻: 根据计算出的距离，找出距离未知样本最近的K个训练样本。
  4. 决策:
    • 分类问题: 根据这K个最近邻样本的类别，通过多数表决（Majority Voting）的方式，决定未知样本的类别。即K个邻居中出现次数最多的类别，就是新样本的类别。
    • 回归问题: 取这K个最近邻样本的目标值的平均值（或加权平均值，例如根据距离远近进行加权）作为未知样本的预测值。

关键要素

k近邻法使用的模型，实际上对应于对特征空间的划分。

模型有三个基本要素：距离度量、k值的选择和分类决策规则。

距离度量

常用的距离度量包括：欧氏距离、曼哈顿距离、闵可夫斯基距离（更一般化）

注意: 由于距离计算对特征的尺度敏感，因此在使用KNN之前，通常需要对特征进行 标准化 (Standardization) 处理

K值的选择

  • 较小的K值:
    • 模型复杂度较高，容易受到临近噪声数据的影响，估计误差较高，容易过拟合。
  • 较大的K值:
    • 模型复杂度较低，可能会导致欠拟合，因为会包含一些不太相关的邻居，近似误差高
    • 如果K值等于样本总数，则所有新样本都会被预测为训练集中样本数最多的那个类别。

选择方法: 通常通过交叉验证 (Cross-Validation) 来选择一个最优的K值。

分类决策

一般采用多数表决规则，等价于经验风险最小化

Kd树

KNN算法要求搜索最近的K个实例，然而直接线性搜索的开销太大，我们需要一个合适的数据结构来搜索

通常，我们可以使用Kd树。这是一种用于组织K维空间中点集的数据结构，它是一种特殊的二叉树（Binary Tree）。

构建Kd树

构建Kd树是一个递归的过程：

  1. 选择切分维度
    • 从根节点开始，选择一个维度作为当前节点的切分维度。
    • 切分维度的选择通常是循环进行的，例如：第一层按第1维切分，...，然后第K+1层再按第1维切分，以此类推。
  2. 选择切分点
    • 在选定的切分维度上，从当前节点所包含的所有点中选择一个点作为切分点。
    • 通常选择这些点在该维度上的中位数 (median) 对应的点（该点实际存在）。
  3. 划分数据点:
    • 所有在该维度上值小于等于中位数点的点，被分配到当前节点的左子树。
    • 所有在该维度上值大于中位数点的点，被分配到当前节点的右子树。

重复以上算法，直到划分区域两侧都没有数据为止

最近邻搜索

目标：给定一个查询点 (query point)，找到树中距离它最近的点。

  1. 向下搜索路径 (Path Finding):
    • 从根节点开始，将查询点与当前节点在节点的切分维度上的值进行比较并向下搜索
    • 重复此过程，直到到达一个叶子节点。这个叶子节点作为当前的“最近邻候选点”。
  2. 回溯与剪枝 (Backtracking and Pruning):
    • 从该叶子节点开始向上回溯。
    • 对于路径上的每个节点：
      • 更新候选点: 计算查询点与当前节点之间的距离。如果该距离小于当前最佳距离，则更新最近邻候选点和最小距离。
      • 检查另一侧子空间: 判断查询点到当前节点切分超平面的距离。如果这个距离小于当前已知的最小距离（即以查询点为球心，最小距离为半径的超球体与该切分超平面相交），那么另一侧的子空间中可能存在更近的点。此时，需要递归地搜索另一侧子树。
      • 如果超球体不与切分超平面相交，则另一侧子空间不可能有更近的点，可以剪枝 (prune)，即不必搜索该子树。
    • 继续回溯直到根节点。

对于k近邻搜索，方法类似，区别在于我们会维护一个容量为k的列表及最远距离D（类比上述的最近距离）

当列表满容量时，我们比较当前点的距离和最远距离D，如果当前点距离更小，则踢出最远距离的点。

kd树的特点

  • 维度灾难 (Curse of Dimensionality): 当数据的维度K很高时（例如 K > 20），Kd树的性能会急剧下降，搜索效率可能退化到接近暴力搜索的 \(O(N)\)。在高维空间中，几乎所有点都可能成为“近邻”的候选，剪枝效果变差。
  • 对数据分布敏感: 如果数据分布不均匀，Kd树可能会变得不平衡，导致最坏情况下的搜索时间复杂度达到 \(O(N)\)。