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

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

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

距离度量的方式有三种：欧式距离、曼哈顿距离、闵可夫斯基距离。 欧式距离: d ( x , y ) = ∑ k = 1 n ( x k − y k ) 2 d(x, y)=\sqrt{\sum_{k=1}^{n}\left(x_{k}-y_{k}\right)^{2}} d(x,y)=k=1∑n​(xk​−yk​)2 ​ 最常用的就是欧式距离。 曼哈顿距离： d ( x , y ) = ∑ k = 1 n ∣ x k − y k ∣ d(x, y)=\sum_{k=1}^{n}\left|x_{k}-y_{k}\right| d(x,y)=k=1∑n​∣xk​−yk​∣ 闵可夫斯基距离: D ( x , y ) = ( ∣ x 1 − y 1 ∣ ) p + ( ∣ x 2 − y 2 ∣ ) p + … + ( ∣ x n − y n ∣ ) p p = ∑ i = 1 n ( ∣ x i − y i ∣ ) p p \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} D(x,y)=p(∣x1​−y1​∣)p+(∣x2​−y2​∣)p+…+(∣xn​−yn​∣)p ​=p∑i=1n​(∣xi​−yi​∣)p ​​ 我们可以发现，欧式距离是闵可夫斯基距离距离在p=2时的特例，而曼哈顿距离是p=1时的特例。

分类决策规则一般使用多数表决法。即如果一个样本在特征空间中的k个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。

输入训练集数据和标签，输入测试数据； 计算测试数据与各个训练数据之间的距离； 按照距离的递增关系进行排序，选取距离最小的K个点； 确定前K个点所在类别的出现频率，返回前K个点中出现频率最高的类别作为测试数据的预测分类。

KNN算法的优点:

KNN算法的缺点: