统计学习方法——KNN

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章
上一篇:LLC谐振变换器原理及变频控制


下一篇:天使玩偶:CDQ分治&KD-tree