一、KNN算法原理
KNN算法是选择与输入样本在特征空间内最近邻的k个训练样本并根据一定的决策规则，给出输出结果 。
决策规则：
分类任务：输出结果为k个训练样本中占大多数的类 。
回归任务：输出结果为k个训练样本值的平均值 。
如下图所示房价预测任务：
二、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选取结果可知，K值选择应适中，K值一般小于20，建议采用交叉验证的方法选取合适的K值。
2、距离的度量：
KNN算法用距离来度量两个样本间的相似度。
常用的距离表示方法：
可以看出，欧式距离是闵可夫斯基距离在p=2时的特例，而曼哈顿距离是p=1时的特例 。
3. 分类决策规则：
KNN算法一般是用多数表决方法，即由输入实例的K个邻近的多数类决定输入实例的类。这种思想也是经验风险最小化的结果。
训练样本为(xi , yi)。当输入实例为 x，标记为c，是输入实例x的k近邻训练样本集。
我们定义训练误差率是K近邻训练样本标记与输入标记不一致的比例，误差率表示为：
因此，要使误差率最小化即经验风险最小，就要使(2.1)式右端的最大，即K近邻的标记值尽可能的与输入标记一致，所以多数表决规则等价于经验风险最小化。
四、KNN算法优缺点
优点：
1）算法简单，理论成熟，可用于分类和回归。
2）对异常值不敏感。
3）可用于非线性分类。
4）比较适用于容量较大的训练数据，容量较小的训练数据则很容易出现误分类情况。
5）KNN算法原理是根据邻域的K个样本来确定输出类别，因此对于不同类的样本集有交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为合适。
缺点：
1）时间复杂度和空间复杂度高。
2）训练样本不平衡，对稀有类别的预测准确率低。
3）相比决策树模型，KNN模型可解释性不强。
附带代码：K近邻(KNN)-代码 - 简书
