KNN算法

一、概念

KNN（K Near Neighbor）：k个最近的邻居，即每个样本都可以用它最接近的k个邻居来代表。

用我们的一句古语来说就是：物以类聚，人以群分。假如一个人的通讯录里有马云、王健林、李嘉诚等，那么这个人肯定也是这个圈子里的人；再假如，一个爱好游戏的人的朋友圈，应该大部分都是玩游戏的；爱喝酒的人的朋友圈，应该都是爱喝酒的；有句话说得好，臭味相投。

最近邻算法是一种分类算法，1968年由Cover和Hart提出，应用场景有字符识别、文本分类、图像识别等领域。
该算法的思想是：一个样本与数据集中的k个样本最相似，如果这k个样本中的大多数属于某一个类别，则该样本也属于这个类别。

如上图所示：当$k=1$k=1时，绿色这个点属于class1；当$k=5$k=5时，绿色这个点属于class2。

二、距离度量

KNN的主要思想是计算样本与样本之间的距离，接下来我们介绍距离度量的方法。
在我们选择两个实例相似性时，一般使用欧氏距离进行度量。
$LP距离：$LP距离： $L_p(x_i,x_j)=(\sum\limits_{i}^n|x_i^{(l)}-x_j^{(l)}|^p)^\frac{1}{p}$Lp​(xi​,xj​)=(i∑n​∣xi(l)​−xj(l)​∣p)p1​，其中$x_i\in R^n$xi​∈Rn，$x_j\in R^n$xj​∈Rn,$L_\infty$L∞​定义为：
$L_\infty(x_i,x_j)=\mathop{max}\limits_{l}|x_i^{(l)}-x_j^{(l)}|$L∞​(xi​,xj​)=lmax​∣xi(l)​−xj(l)​∣，其中$p$p是一个参数。
1）当$p=1$p=1时，就是曼哈顿距离。
曼哈顿距离：$L_1=\sum\limits_{k=1}^n|x_{1k}-x_{2k}|$L1​=k=1∑n​∣x1k​−x2k​∣，$L1$L1范数表示为：$|x|=\sum\limits_{i=1}^n|x_i|$∣x∣=i=1∑n​∣xi​∣，
其中$x=\begin{bmatrix}x_1\\x_2\\\vdots \\ x_n\end{bmatrix}\in R^n$x=⎣⎢⎢⎢⎡​x1​x2​⋮xn​​⎦⎥⎥⎥⎤​∈Rn
曼哈顿距离对应$L1$L1范数，也就是欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离的总和。例如，在平面上，坐标$(x_1,y_1)$(x1​,y1​)的点$p_1$p1​与坐标$(x_2,y_2)$(x2​,y2​)的点$p_2$p2​的曼哈顿距离为：$|x_1-x_2|+|y_1-y_2|$∣x1​−x2​∣+∣y1​−y2​∣，要注意的是，曼哈顿距离依赖坐标系的转度，而非系统在坐标轴上的平移或映射。
2）当$p=2$p=2时，就是欧氏距离（对应$L2$L2范数），最常见的两点之间或多点之间的距离表示法，又称为欧几里得度量，它定义于欧几里得空间中。$n$n维空间中两个点$x_1(x_{11},x_{12},...,x_{1n})$x1​(x11​,x12​,...,x1n​)与$x_2(x_{21},x_{22},...,x_{2n})$x2​(x21​,x22​,...,x2n​)间的欧氏距离为：
$d_{12}=\sum\limits_{k=1}^n\sqrt{(x_{1k}-x_{2k})^2}$d12​=k=1∑n​(x1k​−x2k​)2​，$L2$L2范数为：$|x|=\sqrt{\sum\limits_{i=1}^nx_i^2}$∣x∣=i=1∑n​xi2​​
其中$x=\begin{bmatrix}x_1\\x_2\\\vdots \\ x_n\end{bmatrix}\in R^n$x=⎣⎢⎢⎢⎡​x1​x2​⋮xn​​⎦⎥⎥⎥⎤​∈Rn。
3）当$p=\infty$p=∞，就是切比雪夫距离，二维平面两点$a(x_1,y_1)$a(x1​,y1​)与$b(x_2,y_2)$b(x2​,y2​)间的切比雪夫距离：
$d_{12}=max(|x_1-x_2|,|y_1-y_2|)$d12​=max(∣x1​−x2​∣,∣y1​−y2​∣)
$n$n维空间点$a(x_{11},x_{12},...,x_{1n})$a(x11​,x12​,...,x1n​)与$b(x_{21},x_{22},...,x_{2n})$b(x21​,x22​,...,x2n​)的切比雪夫距离：
$d_{12}=max(|x_{1i}-x_{2i}|),i=1,2,...,n$d12​=max(∣x1i​−x2i​∣),i=1,2,...,n

三、K值的选择

在说K值选择之前，我们先说两个概念：近似误差和估计误差。
${\color{red}近似误差}：$近似误差：可以理解为对现有训练集的训练误差。
近似误差关注训练集，如果k值小了会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较大偏差的预测。模型本身并不接近最佳模型。
${\color{red}估计误差}：$估计误差：可以理解为对测试集的测试误差。
估计误差关注测试集，估计误差小了说明对未知数据的预测能力好。模型本身最接近最佳模型。
1）k值过小：如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，学习的近似误差会减小，只有与输入实例较近的训练实例才会对预测结果起作用，但缺点是学习的估计误差会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值减小就意味着整体模型变复杂，分的不清楚，就容易发生过拟合。
2）k值较大：如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测，其优点是可以减少学习的估计误差，但近似误差会增大，也就是对输入实例预测不准确，k值增大就意味着整体模型变得简单。
在实际应用中，k值一般选择一个比较小的数值，通常采用交叉验证法来选取最优的k值。
KNN算法流程：
1）计算已知类别数据集中的点与当前点之间的距离；
2）按距离递增次序排序；
3）选取与当前点距离最小的k个点；
4）统计前k个点所在的类别出现的频率；
5）返回前k个点出现频率最高的类别作为当前点的预测分类。
优点：
1）简单有效；2）重新训练代价低；3）算法复杂度低；4）适合类域交叉样本；5）适用大样本自动分类。
缺点：
1）惰性学习；2）类别分类不标准化；3）输出可解释性不强；4）不均衡性；5）计算量较大。
小例子：

上述给出了每个电影的电影名称，和电影中出现的搞笑镜头以及拥抱、打斗等镜头的次数，通过这些已经标好的电影类型，来预测新出的电影的类型。

比如给定电影名称《唐人街探案》，并给出其搞笑、拥抱、打斗镜头出现的次数，现在我们来预测其电影的类型。
这里我们采用欧几里得距离：$d=\sqrt{\sum\limits_{i=1}^n(x_i-y_i)^2}$d=i=1∑n​(xi​−yi​)2​
比如计算《唐人街探案》和《伦敦陷落》的相似距离：
$d=\sqrt{(23-2)^2+(3-3)^2+(17-55)^2}=43.42$d=(23−2)2+(3−3)2+(17−55)2​=43.42
依次计算出《唐人街探案》与所有电影之间的相似距离，如下所示：

当$k=5$k=5时，如上图所示，我们判断《唐人街探案》的电影类型为喜剧片。