轻松理解机器学习算法- K近邻算法（KNN）

大家好，欢迎来到IT知识分享网。

1、KNN算法简介

K近邻算法（K-Nearest Neighbor, KNN）是1968年由Cover T和Hart P提出的一种基本分类与回归方法。它的基本原理为：建立一个训练样本集，且样本集中每个数据都存在标签，即已知样本集中每一个数据与所属分类之间的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前K个最相似的数据，这就是K-近邻算法中K的来源，通常K是不大于20的整数。最后，选择K个最相似数据中出现次数最多的分类，作为新数据的分类。如图1所示，绿色方形是要预测的目标点，当K=3时，KNN算法会找到与它距离最近的3个点（如虚线圆所示），判断属于哪种类别的点多一些，这个例子中蓝色三角较多，则绿色方形就归属到蓝色三角一类。然而，当K=5时，判定结果就不一样了（如图2所示）。此种情况下，红色圆变多，所以绿色方形就被归到红色圆一类。从这个例子中可以看出，K取值非常重要。

图1 K=3时，判定绿色方形属于蓝色三角一类

图2 K=5时，判定绿色方形属于红色圆一类

2、K值的选择

从上面的例子中可以看出，K的取值非常重要，那么该如何确定K的值呢？通常采用交叉验证方法，即从选取一个较小的K值开始，然后不断增加K的值并计算验证集合的方差，最终找到一个适合的K值。图3所示为一个交叉验证例子，当K值增大时，错误率先降低，因为目标点周围有许多样本可以借鉴，分类效果较好；当K值再增大时，错误率升高，原因是当K取值接近样本最大数时，KNN基本就没有意义了。

图3 交叉验证试验

3、KNN算法的流程

• 计算已知类别数据集中的点与当前点之间的距离（通常使用欧式距离）；
• 按照距离递增次序排序；
• 选取与当前点距离最小的K个点；
• 确定前K个点所在类别的出现频率；
• 返回前K个点所出现频率最高的类别作为当前点的预测分类。

4、KNN算法的优缺点

了解KNN算法的优点和缺点，可以帮助我们在选择学习算法的时候做出更加明智的决定。

优点：

• KNN算法简洁明了，即使没有高深的数学背景也能弄清楚它的原理；
• 模型训练速度快；
• 预测效果好；
• 对异常值不敏感。

缺点：

• 由于KNN存储了所有训练数据，所以其对计算机内存要求高；
• 预测阶段可能很慢；
• 对不相关的功能和数据规模敏感。

总之，当需要使用分类算法且数据量比较大时，我们首先应该尝试使用KNN算法进行分类。

（本文部分内容来自
https://www.cnblogs.com/listenfwind/p/10311496.html）