knn算法近朱者赤近墨者黑海量资源.pdfVIP

本文由简悦SimpRead转码，原文地址

你好，从这一开始，进入“模块三：分类问题”的学算法部分，我会介绍一个跟算法思

想相关的小例子，然后介绍算法的优缺点和适用场景，对于部分算法我将给出算法模块的调用方法，此

外一些扩展的内容我会放在最后讲解。在每一个类型的算法最后，我都尽量安排一节小小的实践课，一

起来看看数据挖掘是如何做的。

今天我要讲的这个算法是最近邻算法（K-NearestNeighbor），简称KNN算法。

一个例子

有一句老话叫作“物以类聚、人以群分”。想象我们在一个特别的社区里，一条清澈的小河从社区流

过，小河左侧环境优美，住着一群，家家户户都是别墅；而小河的另一侧，住着大片贫民，用茅

草和纸板的临时住所密密麻麻的。这时有一个新的住户从外面搬进了这个社区，他住在了小河的左

侧，此时社区里就传开了消息：“我们这又搬来了一户家。”可是谁都不认识他，也看不到他的银

行账户，为什么就认定他是呢？那是因为他跟住在一起了。故事到了这里，也就说明了最

近邻算法的思路：“你跟谁住得近，你就跟谁是同一类”。

算法原理

有了思路，我们再来看看原理，KNN算法是如何处理的。用一句话来解释KNN算法原理，那就是找到

K个与新数据最近的样本，取样本中最多的一个类别作为新数据的类别。面的例子中，找到和新搬

进来的一户人家住的距离最近的K户人家，看看K户人家中是多还是穷人多，取多的那个类别

作为新搬来这户的类别。所以，显然他住在富人区，那附近就会有的富人。

这里面我们提到了一个距离最近，关于距离该怎么计算呢？最常见的一个计算方法就是欧式距离，即两

点之间的连线，如果放在地图上就是两个房子的直线距离。当然除了欧式距离，还有很多距离计算的方

式，比如曼哈顿距离、切比雪夫距离等。

算法的优缺点

如此简单的算法都有哪些优缺点呢？下面我结合使用场景进行分析。

优点

简单易实现：刚把KNN算法介绍完了，是不是很简单？从上面的内容可以看出来，KNN算法最后实际

上并没有抽象出任何模型，而是把全部的数据集直接当作模型本身，当一条新数据来了跟数据集里

面的每一条数据进行对比。

所以可以看到KNN算法的一些优点，首当其冲的就是这个算法简单，简单到都不需要进行什么训练

了，只要把样本数据整理好了，就结束了，来一条新数据就可以进行预测了。

对于边界不规则的数据效果较好：可以想到，我们最终的预测是把未知数据作为点，然后画一个

圈，使得圈里有K个数据，所以对于边界不规则的数据，要比线性的分类器效果更好。因为线性分类器

可以理解成画一条线来分类，不规则的数据则很难找到一条线将其分成左右两边。

缺点

只适合小数据集：正是因为这个算法太简单，每次预测新数据都需要使用全部的数据集，所以如果数据

集太大，就会消耗非常长的时间，占用非常大的空间。

数据不平衡效果不好：如果数据集中的数据不平衡，有的类别数据特别多，有的类别数据特别少，那么

这种方法就会失效了，因为特别多的数据最后在投票的时候会更有竞争优势。

必须要做数据：由于使用距离来进行计算，如果数据量纲不同，数值较大的字段影响就会变大，

所以需要对数据进行，比如都转换到0-1的区间。

不适合特征维度太多的数据：由于我们只能处理小数据集，如果数据的维度太多，那么样本在每个维度

上的分布就很少。比如我们只有三个样本，每个样本只有一个维度，这比每个样本有三个维度特征要明

显很多。

关于K的选取

K值的选取会影响到模型的效果。在情况下，如果K取1，由于富人区人均面积都很大，家里可能

是别墅加后花园，富人与富人房子的距离相对较远，那个恰好住在河边的人可能跟河对面的一户贫民家

最近，那么这个新人就会被判定为贫民。

如果K取值与数据集的大小一样，那么也可想而知，由于贫民的人数户数都远远多于富人，那么所有新

进来的人，不管他住哪里都会被判定为贫民。这种情况下，最果就是整个样本中占多数的分类的结

果，这个模型也就没有什么作用了。

用我们前面学过的内容来看，当