KNN算法原理

K最近邻（K-Nearest Neighbor,KNN）算法核心思想是如果一个样本在特征空间中的k个最临近的样本中的大多数属于某一个类别，则该样本也属于这个类别。K通常是不大于20的整数。

KNN算法三要素

三要素为：k值的选取，距离度量的方式和分类决策规则。

K值的选择

对于k值的选择，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的k值，K通常是不大于20的整数。
选择较小的k值，就相当于用较小的区域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大。换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合。
选择较大的k值，就相当于用较大区域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
一个极端的情况是k等于样本数m，此时完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。
K值的选择方法：

一种常见的方法是从k等于训练集中样本数量的平方根开始。比如训练集中有100个案例，则k可以从10开始进行进行进一步筛选。
另一种方法是基于各种测试数据测试多个k值，并选择一个可以提供最好分类性能的k值。除非数据的噪声非常大，否则大的训练集可以使k值的选择不那么重要。
还有一种方法是选择一个较大的k值，同时用一个权重投票，在这个过程中,认为较近邻的投票比远的投票权重更大。

距离度量的方式

距离度量的方式有三种：欧式距离、曼哈顿距离、闵可夫斯基距离。
欧式距离:
$$
d(x, y)=\sqrt{\sum_{k=1}^{n}\left(x_{k}-y_{k}\right)^{2}}
$$
最常用的就是欧式距离。
曼哈顿距离：
$$
d(x, y)=\sum_{k=1}^{n}\left|x_{k}-y_{k}\right|
$$
闵可夫斯基距离:
$$
\begin{array}{l}{D(x, y)=\sqrt[p]{\left(\left|x_{1}-y_{1}\right|\right)^{p}+\left(\left|x_{2}-y_{2}\right|\right)^{p}+\ldots+\left(\left|x_{n}-y_{n}\right|\right)^{p}}=} {\sqrt[p]{\sum_{i=1}^{n}\left(\left|x_{i}-y_{i}\right|\right)^{p}}}\end{array}
$$
我们可以发现，欧式距离是闵可夫斯基距离距离在p=2时的特例，而曼哈顿距离是p=1时的特例。