KNN

---

k近邻（k-nearest neighbor, K-NN）是一种基本分类与回归方法

KNN根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测，不具有显式的学习过程

KNN相当于将特征空间划分为一些子空间，确定子空间里的每个点所属的类

KNN三要素：距离度量 k值的选择 分类决策规则

• 距离度量
  • 详见一般的Lp距离
• k值的选择
  • 在应用中，k值一般取一个比较小的数值，通常采用交叉验证法来选取最优的k值
    • 关于交叉验证法，可以考虑用k-fold来找k
    • 如k的候选为[3,5,7,9]，可以把数据集分成四份，每次取其中三份作为训练集和一个不同的k值，最后看哪个k值对应模型的Error最小
    • 除了交叉验证，也可以通过Grid Search来找到合适的k值
  • k值的减小意味着整体模型变得复杂，容易发生过拟合
  • k值的增大意味着整体模型变得简单
  • 简单的方法：k选择一个不大不小的奇数（避免打平的情况）
• 分类决策规则
  • 多数表决规则等价于经验风险最小化

K近邻法的实现：kd树

为了提高k近邻搜索的效率，考虑使用特殊的结构存储训练数据，以减少计算距离的次数

kd树是二叉树，表示对k维空间的一个划分

构造kd树，相当于不断地用垂直于坐标轴的超平面将k维空间切分，构造一系列k维超矩形区域，kd树的每一个节点对应于一个k维超矩形区域

wiki : https://zh.wikipedia.org/wiki/K-d树

• reference
  • 统计学习方法（李航）第3章