KNN(K近邻算法)概述


简介

KNN 是入门级的机器学习分类算法,是最简单的算法之一,这里的 K 是指 近邻个数,也就是最近的 K 个点

原理

KNN 预测一个新的值的类别的时候,会计算它和数据集里每一个数据的 距离,这个距离是抽象意义,后面再讲,计算距离后,我们选取其中最近的 K 个值(即 K 个邻居),而数据集里的数据都是分好类的,就看 K 个邻居里哪个种类的邻居最多,这个新的值就被分为哪一类(所以 K 值一般选奇数,避免出现两个种类的邻居数量相同的情况),那么了解了原理,就需要关注两个问题,一是距离是怎么计算的,二是 K 值如何选取

          

如何计算距离

度量空间中的数据点的距离,有多种方式,如曼哈顿距离计算,余弦值,相关度,欧式距离计算等等,而 KNN 中通常使用欧式距离,就是二维坐标系里计算两点坐标之间距离的方式,这里不用细讲

K 值如何选取

如果当K的取值过小时,一旦有噪声得成分存在们将会对预测产生比较大影响,例如取K值为1时,一旦最近的一个点是噪声,那么就会出现偏差,K值的减小就意味着整体模型变得复杂,容易发生过拟合;

如果K的值取的过大时,就相当于用较大邻域中的训练实例进行预测,学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用,使预测发生错误。K值的增大就意味着整体的模型变得简单;

如果 K==N 的时候,那么就是取全部的实例,即为取实例中某分类下最多的点,就对预测没有什么实际的意义了;

K 值取法:可以从K = 1 开始取奇数,采用 N 折交叉验证,选取误差率最低的 K 值,一般K不大于20,数据集增大,K 也会增大

步骤

1)计算测试数据与各个训练数据之间的距离;
2)按照距离的递增关系进行排序;
3)选取距离最小的K个点;
4)确定前K个点所在类别的出现频率;
5)返回前K个点中出现频率最高的类别作为测试数据的预测分类

注意

一是要注意 标准化,避免结果受数据里的部分过大的特征值影响,可以用极差法,或标准差法进行标准化

二是KNN实际上是没有学习过程的,因此也没有模型参数(训练数据时就在学习这个参数)。KNN在验证过程中计算验证样本点和已知样本点的距离,这时在学习超参数K,超参数是模型外面的参数。

当需要使用分类算法,且数据比较大的时候就可以尝试使用KNN算法进行分类

优点
  • 简单易用,对于边界不规则数据的分类效果好于线性分类器
  • 模型训练时间快,上面说到KNN算法是惰性的
  • 预测效果好。
  • 对异常值不敏感
缺点
  • 对内存要求较高,因为该算法存储了所有训练数据
  • 预测阶段可能很慢
  • 对不相关的功能和数据规模敏感