KNN学习

idea

作为最简单的监督学习算法，可概括为"近朱者赤近墨者黑"。

作为典型的消极学习(lazy learning)，KNN在训练阶段仅仅是把样本保存起来，训练时间开销为零(没有显式的训练过程), 待收到测试样本后再进行处理；

KNN基于某种近邻索引方法找出训练样本集中与其最靠近的K个样本，然后进行结果预测；

  • 对于分类问题使用“投票法”获得预测结果；
  • 对于回归问题使用“平均法”获得预测结果。

1NN性能

当我们讨论1NN(最近邻分类器)在二分类问题的性能，结论是泛化错误率不超过贝叶斯最优分类器的错误率的两倍

时目标是找到最近邻的1个点，给定测试样本 ,最近邻训练样本为，标签集为,抽样的样本独立同分布

  • 对任意测试样本，总能在任意近的范围的范围内找到一个训练样本
  • 令表示Bayes最优分类器的结果,计算分类出错的概率

距离度量

根据距离函数计算待分类样本X和每个训练样本的距离（作为相似度），选择与待分类样本距离最小的K个样本作为X的K个最近邻，最后以X的K个最近邻中的大多数所属的类别作为X的类别。

流程

  1. 导入划分训练集和测试集

    • 每条属性应该有若干属性和一个标签
    • 由于KNN是懒惰学习，对于测试集的每一个样本，KNN通过样本的若干属性和训练集的样本的属性的距离

  2. 设置算法的K值，为超参数，需要人为设置，算法实现后可通过交叉验证的方式选取最好的

  3. 设置算法的距离指标

  4. 遍历所有的测试样本，对每一个样本进行预测

  • 当前的样本为 sample，计算 sample与训练集中的样本(标签为 lb)的距离 d,
  • 把所有距离-标签元组((d, lb))按照 d升序排序
  • 投票：对前 K个元组，找到出现次数最多的标签，这个标签就是预测的结果(平局的情况：我们选择数据点中第一个出现的数据点的标签作为结果，这在python也是很好实现的。)

  1. 记录所有预测的标签，计算准确率

  2. 对所有的可能的​值，交叉验证

问题

  1. K值设定：K值选择过小：得到的近邻数过少，会降低分类精度，同时会放大噪声的干扰，K值选择过大：k个近邻并不相似的数据亦被包含进来，造成噪声增加而导致分类效果的降低。
  2. 类别的判定方式：投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。
  3. 距离度量方式的选择：当变量越多（高维诅咒问题），欧式距离的区分能力越差。
  4. 性能问题 ：KNN是一种懒惰算法，构造模型很简单但在对测试样本分类地的系统开销大。

针对这些可能的问题，我们提出如下策略：采样训练样本量减少训练集的大小；或通过聚类，将聚类所产生的中心点作为新的训练样本。

特点

  • 对值敏感：增大值，一般来说准确率先上升后下降

  • 高维诅咒：在高维空间中近邻的点都变得差不多远，在高维情形下出现的数据样本稀疏

  • 非参数化parameter-free：不对数据分布做出任何假设

  • 简单，易于实现，内存消耗大，计算成本高，解释性差，预测慢