K-近邻算法(KNN)

kNN算法概述

  • 简介:KNN,英文全称为K-nearst neighbor,中文名称为K近邻算法,它是由Cover和Hart在1968年提出来的。 KNN是Machine Learning领域一个简单又实用的算法,它是一种非参方法。即不必像线性回归、逻辑回归等算法一样有固定格式的模型,也不需要去拟合参数。同时它既可用于分类,又可应用于回归

  • 基本指导思想:类似“物以类聚,人以群分”,就比如“如果你要了解一个人,可以从他最亲近的几个朋友去推测他是什么样的人”。

  • 适用场景:由于kNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,kNN方法较其他方法更为适合。

  • 例子:在分类领域,对于一个未知点,选取K个距离(可以是欧氏距离,也可以是其他相似度度量指标)最近的点,然后统计这K个点,在这K个点中频数最多的那一类就作为分类结果。比如下图,若令K=4,则?处应分成红色三角形;若令K=6,则?处应分类蓝色正方形。

    knn_example

算法描述

  • 核心思想:如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。

  • 计算步骤

    • 1)算距离:给定测试对象,计算它与训练集中的每个对象的距离
    • 2)找邻居:圈定距离最近的k个训练对象,作为测试对象的近邻
    • 3)做分类:根据这k个近邻归属的主要类别,来对测试对象分类
  • KNN的特点

    • 优点

      • 简单,易于理解,易于实现,无需拟合参数,无需训练,在样本本身区分度较高的时候效果会很不错;
      • 适合对稀有事件进行分类(例如当流失率很低时,比如低于0.5%,构造流失预测模型);
      • 特别适合于多分类问题(multi-modal,对象具有多个类别标签),例如根据基因特征来判断其功能分类,kNN比SVM的表现要好。
    • 缺点

      • 懒惰算法,当样本量大的时候,找出K个最邻近点的计算代价会很大,会导致算法很慢,内存开销大,评分慢
      • 可解释性较差,无法给出决策树那样的规则。
      • 不适合样本不平衡
      • 计算量大
  • 改进算法

    • 分类效率:事先对样本属性进行约简,删除对分类结果影响较小的属性,快速的得出待分类样本的类别。该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。
    • 分类效果:采用权值的方法(和该样本距离小的邻居权值大)来改进,Han等人于2002年尝试利用贪心法,针对文件分类时做可调整权重的k最近邻居法WAkNN (weighted adjusted k nearest neighbor),以促进分类效果;而Li等人于2004年提出由于不同分类的文件本身有数量上有差异,因此也应该依照训练集合中各种分类的文件数量,选取不同数目的最近邻居,来参与分类。

KNN性能讨论

  • KNN的性能与下列几个因素有关:
    • K预设值取多少:当K取不同的值时,相应的分类结果也会不同。
    • 如何定义距离:不同的距离计算方式得到的“近邻”可能有显著差别,从而导致分类结果的显著的不同。

K的选取问题

K选取不恰当的情况如下表。

K的取值 K太小 K太大
特点 分类边界曲线越光滑,偏差越小,方差越大 分类边界曲线越平坦,偏差越大,方差越
不良影响 分类结果易受噪声点影响 近邻中又可能包含太多的其它类别的点。(对距离加权,可以降低k值设定的影响)

K的选取,具体体现在考虑偏差和方差的权衡问题。

建议:k值通常是采用交叉检验来确定(以k=1为基准),经验规则:k一般低于训练样本数的平方根

距离衡量问题

  • 常用的距离衡量:曼哈顿距离、欧式距离、闵可夫斯基距离和夹角余弦等。具体可参考:KNN算法中常用的距离计算公式

    对于文本分类来说,使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适。

  • 距离衡量影响因素

    • 高维度对距离衡量的影响:众所周知当变量数越多,欧式距离的区分能力就越差。
    • 变量值域对距离的影响:值域越大的变量常常会在距离计算中占据主导作用,因此应先对变量进行标准化。

参考:

  1. KNN算法实现及其交叉验证
  2. 机器学习(一)——K-近邻(KNN)算法