1. KNN基本思想

KNN是一个基本而简单的分类算法，作为监督学习，那么KNN模型需要的是有标签的训练数据，对于新样本的类别由与新样本距离最近的k个训练样本点按照分类决策规则决定。
因此KNN有三个要点：
第一，距离度量；
第二，k值的选择；
第三，分类决策规则。

1.1 距离度量

特征空间中两个样本点之间的距离反映了两个样本点之间的相似度，度量的距离可以是欧式距离或其他 $L_p$ 范式距离。
$L_p(x_i,x_j)=\Big(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p\Big)^{\frac{1}{p}}$
当 $p=2$ 时，欧式距离为：
$L_2(x_i,x_j)=\Big(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^2\Big)^{\frac{1}{2}}$
当 $p=1$ 时，曼哈顿距离为：
$L_1(x_i,x_j)=\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|$

1.2 k值的选择

定性来讲：
1.过小的k值模型中，输入样本点会对近邻的训练样本点十分敏感，如果引入了噪声，则会导致预测出错。对噪声的低容忍性会使得模型变得过拟合。
2.过大的k值模型中，就相当于选择了范围更大的领域内的点作为决策依据，可以降低估计误差。但邻域内其他类别的样本点也会对该输入样本点的预测产生影响。
3.如果k=N，N为所有样本点，那么KNN模型每次都将会选取训练数据中数量最多的类别作为预测类别，训练数据中的信息将不会被利用。
一般k值选取比较小的数值，并采用交叉验证法选择最优的k值。