k近邻法

• 分类与回归方法
• 模型：对应于基于训练数据集对特征空间的一个划分
• k近邻法三要素：距离度量、k值的选择、分类决策规则。
  • 距离度量：$L_p$ 距离
  • k值选择：k值小时，模型更复杂；k值大时，模型更简单。通常由交叉验证选择最优的k。
  • 分类决策规则：常用多数表决，对应于经验风险最小化。
• 快速搜索k个最近邻点：kd树
  • 构造平衡kd树
  • 搜索kd树