一、KNN算法原理

KNN算法是选择与输入样本在特征空间内最近邻的k个训练样本并根据一定的决策规则，给出输出结果 。

决策规则：

    分类任务：输出结果为k个训练样本中占大多数的类 。

    回归任务：输出结果为k个训练样本值的平均值 。

如下图所示房价预测任务：

K代表我们的候选对象个数，也就是找和我房间数量最相近的其他房子的价格

假设我们的数据源中只有5条信息，现在我想针对我的房子（只有一个房间）来定一个价格。

二、KNN算法步骤

回归：

          1、计算待预测样本与训练集的每个样本的距离

          2、将训练集的样本按照距离从小到大排序

          3、取前K个距离最小的训练样本，计算平均值

分类：

           1、计算已知类别数据集中的点与当前点之间的距离；

            2、按照距离递增依次排序；

            3、选取与当前点距离最小的K个点；

            4、确定前k个点所在类别的出现频率；

            5、返回前k个点出现频率最高的类别作为当前点的预测分类

三、KNN算法三要素

K值的选择、距离度量和分类决策规则是K近邻算法的三个基本要素。当三个要素确定后，对于任何一个新的输入实例，它所属的Y值也确定了，本节介绍了三要素的含义。

 1、K值的选择：

K取值较小时，模型复杂度高，训练误差会减小，泛化能力减弱；K取值较大时，模型复杂度低，训练误差会增大，泛化能力有一定的提高。KNN模型的复杂度可以通过对噪声的容忍度来理解，若模型对噪声很敏感，则模型的复杂度高；反之，模型的复杂度低。为了更好理解模型复杂度的含义，我们取一个极端，分析K=1和K="样本数"的模型复杂度。

由上图可知，K=1时，模型输出的结果受噪声的影响很大。

由上图可知，样本数等于7，当K=7时，不管输入数据的噪声有多大，输出结果都是绿色类，模型对噪声极不敏感，但是模型太过简单，包含的信息太少，也是不可取的。

通过上面两种极端的K选取结果可知，K值选择应适中，K值一般小于20，建议采用交叉验证的方法选取合适的K值。

2、距离的度量：

KNN算法用距离来度量两个样本间的相似度。

常用的距离表示方法：

欧式距离公式

曼哈顿距离公式

闵可夫斯基距离公式

可以看出，欧式距离是闵可夫斯基距离在p=2时的特例，而曼哈顿距离是p=1时的特例 。

3. 分类决策规则：

KNN算法一般是用多数表决方法，即由输入实例的K个邻近的多数类决定输入实例的类。这种思想也是经验风险最小化的结果。

训练样本为(xi , yi)。当输入实例为 x，标记为c，是输入实例x的k近邻训练样本集。

我们定义训练误差率是K近邻训练样本标记与输入标记不一致的比例，误差率表示为：

(2.1)

因此，要使误差率最小化即经验风险最小，就要使(2.1)式右端的最大，即K近邻的标记值尽可能的与输入标记一致，所以多数表决规则等价于经验风险最小化。

四、KNN算法优缺点

优点：

1）算法简单，理论成熟，可用于分类和回归。

2）对异常值不敏感。

3）可用于非线性分类。

4）比较适用于容量较大的训练数据，容量较小的训练数据则很容易出现误分类情况。

5）KNN算法原理是根据邻域的K个样本来确定输出类别，因此对于不同类的样本集有交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为合适。

缺点：

1）时间复杂度和空间复杂度高。

2）训练样本不平衡，对稀有类别的预测准确率低。

3）相比决策树模型，KNN模型可解释性不强。

参考：https://mp.weixin.qq.com/s?__biz=MzU0MDQ1NjAzNg==&mid=2247485435&idx=1&sn=e7e78e931eda0fe10972db8f8fae46b1&chksm=fb39a2f0cc4e2be6d546aa746adccfc5034495e7703c76e576dca76414542398d488ba2bad6a

附带代码：K近邻(KNN)-代码 - 简书