【早读算法】K近邻算法原理小结

一、KNN算法原理

KNN算法是选择与输入样本在特征空间内最近邻的$k$个训练样本并根据一定的决策规则，给出输出结果。

决策规则：

分类任务：输出结果为$k$个训练样本中占大多数的类

如下图的分类任务，输出结果为${\omega }_1$类。

二、KNN算法三要素

K值的选择

$k$取值较小时，模型复杂度较高，训练误差会减小，泛化能力减弱；

$k$取值较大时，模型复杂度低，训练误差会增大，泛化能力有一定的提高。

KNN模型的复杂度可以通过对噪声的容忍度来理解，若模型对噪声很敏感，则模型的复杂度较高；反之，模型的复杂度低。

下面举一个例子，我们取一个极端，分析$K=1$和$K{=}^{\prime }样本{数}^{\prime }$的模型复杂度：


由上图可知，$K=1$时，模型输出的结果受噪声的影响很大；

样本数为7，当$K=7$时，不管输入的数据的噪声有多大，输出结果都是绿色类，模型对噪声极不敏感，但是模型太过简单，包含的信息太少，也是不可取的。

总结：

$K$值的选择应该适中，$K$值一般小于20，建议采用交叉验证的方法选择合适的$K$值。

距离度量

KNN算法用距离来度量两个样本间的相似度，常用的距离表示方法为：

（1）欧式距离
$$\begin{gathered} D(x,y)=\sqrt{(x_1-y_1{)}^2+(x_2-y_2{)}^2+\cdots +(x_n-y_n{)}^2} \\ =\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2} \end{gathered}$$

（2）曼哈顿距离
$$\begin{gathered} D(x,y)=|x_1-y_1|+|x_2-y_2|+\cdots +|x_n-y_n| \\ =\sum _{i=1}^n|x_i-y_i| \end{gathered}$$

其他距离可以自行查阅，这里不再赘述。

距离的表达通式：

设特征空间$\chi$是$n$维实数向量空间${\mathbb{R}}^n$，$x_i,x_j\in \chi ,x_i=(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)}{)}^T,x_j=(x_j^{(1)},x_j^{(2)},\cdots ,x_j^{(n)}{)}^T$，$x_i,x_j$的$L_p$距离定义为：
$$L_p(x_i,x_j)=(\sum _{l=1}^n|x_i^{(l)}-x_j^{(l)}{|}^p{)}^{\frac{1}{p}}$$

分类决策规则

KNN算法一般是用多数表决方法，即由输入实例的$K$个邻近的多数类决定输入实例的类，这种思想也是经验风险最小化的结果。

为什么呢？

多数表决规则有如下解释：如果分类的损失函数为0-1损失函数，分类函数为：
f : R n → { c 1 , c 2 , ⋯   , c K } f:\R^n\rightarrow \{c_1,c_2,\cdots,c_K\} f:Rn→{c1​,c2​,⋯,cK​}
那么误分类的概率是：
$$p(Y\ne f(X))=1-p(Y=f(X))$$
对给定的实例$x\in \chi$，其最近邻的$k$个训练实例点构成集合$N_k(x)$。如果涵盖$N_k(x)$的区域的类别是$c_j$，那么误分类率是：
$$\frac{1}{k}\sum _{x_i\in N_k(x)}I(y_i\ne c_j)=1-\frac{1}{k}\sum _{x_i\in N_k(x)}I(y_i=c_j)$$
要使误分类率最小即经验风险最小，就要使${\sum }_{x_i\in N_k(x)}I(y_i=c_j)$最大，所以多数表决规则等价于经验风险最小化。

KNN算法之暴力实现方法

暴力搜索是线性扫描输入实例与每一个训练实例的距离并选择前$k$个最近邻的样本来多数表决，算法简单，但是当训练集或特征维度很大时，计算非常耗时，故这种暴力实现原理是不可行的。

KNN算法之kd数实现方法

kd树是一种对$k$维空间中的实例点进行存储以便对其进行快速检索的树形数据结构，构造kd树相当于不断用垂直于坐标轴的超平面将$k$维空间进行划分，构成一系列的$k$维超矩形区域，kd树省去了对大部分数据的搜索，大大的减少了计算量。

kd树的KNN算法实现包括三部分：kd树的构建、kd树的搜索和kd树的分类。

1. 构建kd树

kd树实质上是二叉树，其划分思想与cart树一致，即划分使样本复杂度降低最多的特征，kd树认为特征方差越大，则该特征的复杂度越大，优先对该特征进行切分，切分点是所有实例在该特征的中位数，重复该切分步骤，知道切分后无样本则终止切分，终止时的样本为叶节点。

下面举一个例子：

给定一个二位空间的数据集：
$$T=\{(2,3{)}^T,(5,4{)}^T,(9,6{)}^T,(4,7{)}^T,(8,1{)}^T,(7,2{)}^T\}$$
构造kd树的步骤：

（1）数据集在维度$x^{(1)}$和$x^{(2)}$的方差分别为6.9和5.3，因此先从$x^{(1)}$维度进行切分；

（2）数据集在$x^{(1)}$维度的中位数是6，因为没有6，所以选择7，以平面$x^{(1)}=7$将空间分为左右两个矩形；

（3）分别对左右两个矩形的样本在$x^{(2)}$维度的中位数进行切分；

（4）重复步骤（2）、（3），直到无样本，该节点为叶子节点。

如下图，绿色为叶子节点，红色为节点和根节点：

2. kd树搜索

（1）搜索路径从根节点到叶节点，在KD树里面找到包含目标点的叶子节点。

（2）搜索路径从叶节点到根结点，找到距离目标点最近的样本实验点，过程不再复述，具体方法请参考李航老师的《统计学习方法》。

KNN算法的优缺点

优点：

1）算法简单，理论成熟，可用于分类和回归；

2）对异常值不敏感；

3）可用于非线性分类；

4）比较适用于容量较大的训练数据，容量较小的训练数据则很容易出现误分类的情况。

5）KNN算法原理是根据邻域的K个样本来确定输出类别，因此对于不同类的样本集有交叉或重叠较多的待分样本集来说，KNN方法较其他方法更适合。

缺点：

1）时间复杂度和空间复杂度高

2）训练样本不平衡，对稀有类别的预测准确率低

3）相比决策树模型，KNN算法模型可解释性不强