机器学习之KNN算法简介

一、KNN算法是什么

我们都听说过物以类聚人以群分，或者近朱者赤近墨者黑这些词语，KNN算法似乎也符合人类社会的这种发展规律。那么什么是KNN算法呢？KNN算法又叫K近邻算法，也是机器学习中最简单的算法之一，假如我们要判断一个人性格，我们可以通过他平时经常交往的朋友来判断，不是一个圈的人融不进一个圈。KNN算法就是通过找到离当前样本空间最近的K个样本的分类，然后通过多数表决法来判断该样本所属的分类。

举个栗子说明，如上图所示，图中绿色的圆圈是需要预测的样本，假如K=3，可以看到离绿色圆圈最近的3个样本有2个红色的三角形和1个蓝色的正方形，再通过多数表决法（少数服从多数）判断该预测样本应该是一个红色三角形；假如K=5，则判断该预测样本为蓝色正方形。

二、影响算法效果的主要因素

1.K值的选择：由上图所示，不一样的K值对分类的判断影响很大，选择较小或较大的K值都容易造成欠拟合或过拟合，可使用交叉验证法来找到合适K值。

2.距离的度量：我们学生时代都学过很多距离度量的方法，例如欧氏距离、哈曼顿距离、夹角余弦等，一般我们使用欧氏距离来度量，例如有两个点a(x1,x2,x3,...,xn)和b(y1,y2,y3,...,yn)，则欧氏距离的计算公式如下：

(1)

3.分类判断规则：一般在解决分类问题的时候采用多数表决法，解决回归问题的时候采用平均值法。

三、使用Python来实现KNN算法

对于小数据量问题，使用KNN算法可以直接暴力求解，如果数据量比较大，则需要使用KD树等其它快速求解最近邻的算法，KD树可以在大量样本数据中快速寻找到预测样本的最近邻，这里代码使用暴力求解来实现，具体如下：

1.导入所需的库

2.使用公式(1)定义欧氏距离计算方法

3.定义KNN算法

4.初始化训练集和测试集数据，这里的数据使用sklearn自带的鸢尾花数据集

5.使用KNN算法预测测试集数据，这里分别取K=2、3、4来进行预测

6.绘图展示预测结果

由上图结果可以看出不同的K值预测的效果不一样，这里K=3时候预测的效果较好。