KNN(K Nearest Neighbors)

Posted by Jerry on November 22, 2016

概述

给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近K个实例,这K个实例的多数属于某个类,就把该输入实例分为这个类

可见,KNN算法思想非常的简单,KNN不具有显示的学习过程,整个算法模型由三部分组成:

  • 距离度量的选择
  • K值的选择
  • 分类决策规则的选择

距离度量的选择

常用的计算距离方法有: 闵可夫斯基距离度量: 闵可夫斯基距离度量 曼哈顿距离度量: 曼哈顿距离度量 欧式距离度量(最常用): 欧式距离度量

不同的距离所确定的最邻近点是不同的,在实际实现过程中,别忘了归一化数据。

K值选择

不同的K值对KNN算法的结果会产生重大影响

如果K值过小,相当于只用与输入实例较近(相似)的样本会对预测结果产生影响,这样带来的不足之处是预测结果会对近邻的样本点非常敏感,如果邻近的样本点恰好是噪声点,那么预测结果就会出错。换句话说,K值的减小意味着模型变得复杂,容易发生过拟合 相反,如果K值过大,那么预测结果取决于输入实例较大邻域内的样本点,这样带来的不足之处是预测结果可能受到较远(不太相似)的样本点的干扰,从而使得预测结果不准确。换句话说,K值增大意味着模型变得简单,极端情况下,K=N,那么无论输入实例是什么,都将简单地预测它属于训练实例中出现最多的类,这时,模型过于简单,完全忽略了训练集中有用的信息,所以该方案是不可取的。 通常,K值一般取一个较小的数值,然后使用交叉验证法来选取最优的K值

分类决策规则的选择

KNN决策规则也有多种,同样,不同的决策规则会产生不同的预测结果。 常用的决策规则是:多数表决法,即由输入实例的K个邻近样本点中的多数类决定输入实例的类。此外,还有例如加权统计的方法进行决策等。

优缺点

优点:

  • 简单有效,容易理解,计算时间和空间线性于训练集的规模
  • 重新训练的代价较低(类别体系的变化和训练集的变化,在WEB环境和电子商务应用中是常见的)

缺点:

  • 输出的可理解性不够强(无法给出像决策树那样的规则),类别评分不规格(不像概率评分)
  • 计算量大,因为对每一个待分类点都要计算它到全体已知样本点的距离才能得到K个最邻近点。此问题可用KD Tree 或者Ball Tree进行优化
  • 样本不平衡时,如某一类一家独大时,新样本点的K个邻近中该类占据多数,可以采用加权方法,样本距离小的邻居权值大来加以改进

实现

Python实现

代码与数据集都来自《机器学习实战》,本文使用的是识别手写数字的案例,如有需要,可以从我的Github中找到相应代码

Scikit-Learn 库调用

Scikit-Learn的KNN库 API已经介绍的十分详细,这里稍作说明:

class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=1, **kwargs)

参数说明:

  • n_neighbors:K值设定,默认为5
  • weights:决策规则中权重设置,默认所有权重相同,相当于多数表决法
  • algorithm:找近邻的算法,可以有KD Tree、Ball Tree等算法,使用这些算法可以让你的KNN跑得更快
  • metric:距离度量算法,默认使用的是闵可夫斯基度量公式
  • p:针对上面的闵可夫斯基公式,设定p值,p为1,则为曼哈顿公式,p为2,则为欧式公式。默认为2

其他参数可查看相应API

模型使用:

fit(X,y) # 使用训练集构建模型,X为训练集,数据格式要求为array-like,y为训练集类别
predict(X) # 对新样本进行预测所属类别,X为测试集,数据格式要求为array-like,返回结果为预测所属类

运行对比

当使用KD Tree算法,其他条件保持一致时,发现其速度远远快于普通算法:

  • 第一种算法耗时:27s
  • 第二种算法耗时:6s

Reference

  • 统计学习方法——李航
  • 机器学习实战