KNN算法直接作用于带标记的样本,属于有监督的算法,既可以用于分类也可以用于预测。它是一种懒惰的算法(lazy learning),因为它实际上并没有“训练”的过程,也不产生一个真实意义的“模型”。而只是一字不差地将所有的训练样本保存下来,等到需要对新样本进行分类的时候,将新样本与所有的训练样本进行比较,找出预期距离最接近的K个样本,然后基于这K个邻居所属的类别进行投票,决定分类效果。



算法过程:

  1. 计算距离:给定待分类的样本,计算该样本与其他每个样本的距离。
  2. 距离排序:将计算出的距离降序排序。
  3. 选择K个近邻:根据排序结果,选择距离最近的K个样本作为待分类样本的K个近邻。
  4. 决定分类:找出K个近邻的主要类别,即按投票方式决定待分类样本的类别。

KNN三要素

  1. 距离度量
    1. 对欧式距离,点$P_1(x_{11},x_{12},\ldots,x_{1n})$与点$P_2(x_{21},x_{22},\ldots,x_{2n})$之间的距离为:$$d_{12} = \sqrt{\sum_{k=1}^n(x_{1k}-x_{2k})^2}$$
    2. 对曼哈顿距离,点$P_1(x_{11},x_{12},\ldots,x_{1n})$与点$P_2(x_{21},x_{22},\ldots,x_{2n})$之间的距离为:$$d_{12} = \sum_{k=1}^n|x_{1k}-x_{2k}|$$
    3. 对切比雪夫距离,点$P_1(x_{11},x_{12},\ldots,x_{1n})$与点$P_2(x_{21},x_{22},\ldots,x_{2n})$之间的距离为:$$d_{12} = \max_{i \in [1,n]}(|x_{1i}-x_{2i}|)$$
    4. 对夹角余弦距离,点$P_1(x_{11},x_{12},\ldots,x_{1n})$与点$P_2(x_{21},x_{22},\ldots,x_{2n})$之间的距离为:$$cos(\theta) = \frac{\sum_{k=1}^nx_{1k}x_{2k}}{\sqrt{\sum_{k=1}^nx_{1k}^2}\sqrt{\sum_{k=1}^nx_{2k}^2}}$$
  2. K值选择:选取恰当的K值大小
    1. 小:过拟合
    2. 大:平滑简单
  3. 分类决策
    1. 对距离加权
    2. 对样本加权

优点

  • 原理简单,易于理解,实现方便,不需要训练的过程。
  • 特别适用于多分类问题,如根据基因的特征判断基因的功能
  • 对异常值不敏感

缺点

  • 每次进行预测都要对所有样本进行重新扫描和计算距离,因此当样本集很大时,计算量会很大。
  • 需要存储所有的样本。
  • 结果的可解释性差,无法给出规则。
  • 数据集中如果含有缺失值,需要特殊处理。