K Nearest Neighbors

0.什么是KNN

KNN采用测量不同特征变量间的距离或相似度的方法进行分类，这里的距离一般指的是欧式距离。通俗点来说，KNN是典型的一种“近朱者赤近墨者黑”分类模型，样本与样本间的距离越近或者说越相似，则就被判为同一类。

算法的决策过程：

1. 计算数据集中样本与样本间的距离
2. 选择距离最近的前$K$K个样本作为近邻数据集

注意的是KNN里的$K$K指的是近邻个数。

通过一个简单的示意图解释KNN的工作原理，如下图所示：

图中可以看到KNN就是使用近邻的距离来判断当前样本是否属于该样本的类别，圆范围内的样本即是当前样本的近邻区域。但是随着近邻个数$K$K的增加，当前样本的近邻集也在不断的扩展，当近邻个数不断扩张直到包含了另一类别的样本时，KNN的分类性能将大打折扣。因为此时的样本近邻集内已经不再是同一个类别的数据了。

所以$K$K的选择不同，得到的结果也会不同，也就是说$K$K的个数制约着KNN的性能。

1.KNN理论

假设数据矩阵$X$X如下所示：
$(x_1,x_2,\dots,x_N)^T_{N \times p} = \left[ \begin{matrix} x_1^T \\ x_2^T \\ \vdots \\ x_N^T \end{matrix} \right] = \left[ \begin{matrix} x_{11} & x_{12} & \dots & x_{1p} \\ x_{21} & x_{22} & \dots & x_{2p} \\ \vdots & \vdots & \vdots& \vdots \\ x_{N1} & x_{N2} & \dots & x_{Np} \\ \end{matrix} \right]_{N \times p}$(x1​,x2​,…,xN​)N×pT​=⎣⎢⎢⎢⎡​x1T​x2T​⋮xNT​​⎦⎥⎥⎥⎤​=⎣⎢⎢⎢⎡​x11​x21​⋮xN1​​x12​x22​⋮xN2​​……⋮…​x1p​x2p​⋮xNp​​⎦⎥⎥⎥⎤​N×p​

1. 标准化处理： 假设我们有两个样本点$x_1,x_2$x1​,x2​，且每个样本都有两个特征变量$x_1 = (1,200)^T,x_2=(2,300)^T$x1​=(1,200)T,x2​=(2,300)T，如果不经过标准化处理，它们的欧式距离就是$\sqrt {(1-2)^2 + (200-300)^2} = \sqrt {1+10000}$(1−2)2+(200−300)2​=1+10000​。这样计算出的距离会受到第二个特征变量与第一个特征变量间量级的影响。因此与PCA相同，第一步应使用z-score方法去除变量间的量纲影响。

2. 计算距离： 一般度量空间中点的距离的话，有多种方式，如常见的曼哈顿距离计算，欧式距离计算等。通常KNN使用的是欧式距离，欧式距离计算公式如下：
   $\begin{aligned} Dist(x_i,x_j) &= \sqrt {(x_{i1} - x_{j1})^2 +(x_{i2} - x_{j2})^2+,\dots +(x_{ip} - x_{jp})^2}\\ &=\sqrt{\sum_{k=1}^p (x_{ik} - x_{jk})^2 }\end{aligned}$Dist(xi​,xj​)​=(xi1​−xj1​)2+(xi2​−xj2​)2+,⋯+(xip​−xjp​)2​=k=1∑p​(xik​−xjk​)2​​
   这里就可以看出KNN通过最简单粗暴的将预测样本与所有样本进行点距离的计算，然后排序保存，选出前$K$K个距离较近的样本来判别类别。