1. KNN基本思想
KNN是一个基本而简单的分类算法，作为监督学习，那么KNN模型需要的是有标签的训练数据，对于新样本的类别由与新样本距离最近的k个训练样本点按照分类决策规则决定。
因此KNN有三个要点：
第一，距离度量；
第二，k值的选择；
第三，分类决策规则。
1.1 距离度量
特征空间中两个样本点之间的距离反映了两个样本点之间的相似度，度量的距离可以是欧式距离或其他范式距离。
当时，欧式距离为：
当时，曼哈顿距离为：
1.2 k值的选择
定性来讲：
1.过小的k值模型中，输入样本点会对近邻的训练样本点十分敏感，如果引入了噪声，则会导致预测出错。对噪声的低容忍性会使得模型变得过拟合。
2.过大的k值模型中，就相当于选择了范围更大的领域内的点作为决策依据，可以降低估计误差。但邻域内其他类别的样本点也会对该输入样本点的预测产生影响。
3.如果k=N，N为所有样本点，那么KNN模型每次都将会选取训练数据中数量最多的类别作为预测类别，训练数据中的信息将不会被利用。
一般k值选取比较小的数值，并采用交叉验证法选择最优的k值。
1.3 分类决策规则
邻域
一般来讲，KNN的分类决策规则就是对输入新样本的邻域内所有样本进行统计数目。
邻域的定义就是，以新输入样本点为中心，离新样本点距离最近的k个点所构成的区域。下面给出了k值分别为5.6.7时的邻域情况。
image.png
image.png
image.png
根据
其中，
KNN模型的多数表决规则属于经验风险最小化的策略，因此KNN模型的误分类率为：
参考《李航统计学习方法》
