KNN(K-NearestNerborhood)学习

特点

• 懒惰学习(LazyLearning):

  1. 在训练阶段仅仅是把样本保存起来，训练时间开销为零(没有显式的训练过程)
  2. 待收到测试样本后再进行处理
  3. 预测阶段较慢

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

  讨论1NN在二分类问题的性能：泛化错误率不超过贝叶斯最优分类器的错误率的两倍

  • 时目标是找到最近邻的1个点，给定测试样本 ,最近邻训练样本为，标签集为,抽样的样本独立同分布
  • 对任意测试样本，总能在任意近的范围的范围内找到一个训练样本
  • 令表示Bayes最优分类器的结果,计算分类出错的概率

• 高维诅咒：在高维空间中近邻的点都变得差不多远，而且KDtree优化难以进行

• 其他：

  • 非参数化parameter-free：不对数据分布做出任何假设
  • 简单，易于实现，内存消耗大，计算成本高，解释性差，预测慢

基本思想

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

分类原理

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

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

2. 设置算法的K值

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

3. 设置算法的距离指标

   Minkowski距离

   • 对数据对象 ,各维权重为
   • Minkowski距离：
   • 注意，各维等价时，称为Manhattan距离 ，称为Euclidean距离

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

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

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

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

注意

1. K值设定

• K值选择过小：得到的近邻数过少，会降低分类精度，同时会放大噪声的干扰
• K值选择过大：k个近邻并不相似的数据亦被包含进来，造成噪声增加而导致分类效果的降低。

2. 类别的判定方式

• 投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。

3. 距离度量方式的选择

当变量越多（高维诅咒问题），欧式距离的区分能力越差。

4. 性能问题

KNN是一种懒惰算法，构造模型很简单但在对测试样本分类地的系统开销大。

策略：采样训练样本量减少训练集的大小；或通过聚类，将聚类所产生的中心点作为新的训练样本。