C03. k 近邻法

• k 近邻法 (k-nearest neighbor, k-NN) 是一个基本且简单的方法，用于分类与回归。
  • 输入为实例的特征向量，对应于特征空间的点；
  • 输出为实例的类别，可以取多个类。
• 基本思想
  • 假设给定一个训练数据集，其中的实例类别已经确定；
  • 对新输入的实例分类时，根据其 k 个最近邻的训练实例的类别，通过多数表决等方式进行预测。
  • 不具有显式的学习过程。
  • 实际上利用训练数据集对特征向量空间进行切分，并作为其分类的 “模型”。
• k 近邻的模型
  • 对应于基于训练数据集对特征空间的一个划分。
  • 当训练集、距离度量、k 值及分类决策规则确定后，输入实例所属类别也唯一确定。
• k 近邻法的三个要素
  • 学习准则 : 距离度量，常用欧氏距离； ( 距离定义 ) [^Duda,2003]
  • k 值的选择 : 反映了近似误差与估计误差之间的权衡。
    • k 值越大时，近似误差会增大，估计误差会减小，模型也越简单；
    • k 值越小时，近似误差会减少，估计误差会增大，模型也越复杂。
    • 可以用交叉验证的方式选择最优 k 值。
  • 分类决策规则 : 多数表决规则 (majority voting rule), 等价于 经验风险最小化。
• k _近邻法的实现基于 kd 树_。 ( 了解即可，实际应用中大多使用的是已经成熟的软件包 )
  • kd 树是一种便于对 k 维空间中的数据进行快速检索的数据结构；
  • kd 树是二叉树，表示对 k 维空间的一个划分；
  • kd 树的每个圣战对应于 k 维空间划分中的一个超矩形区域；
  • 利用 kd 树可以省去对大部分数据点的搜索，从而减少搜索的计算量。
• 学习总结
  • 了解即可，因为面对高维问题效果很差，需要考虑降维操作。[^周志华，2018] P225