KNN

约 478 个字预计阅读时间 2 分钟

定义

K 临近算法(K-Nearest Neighbors)核心思想是通过计算待分类样本与训练集中各个样本的距离，找到最临近的K个样本，然后根据这K个样本的类别来预测待分类样本的类别。

从几何理解，对于训练集中的任意一个点，在它周围都存在一定空间，在这个空间中的点到它的距离比到其他任何点都小，这个空间称作这个点的单元(cell)，所有训练集的点的单元形成了对特征空间的一个划分。KNN 的实质就是把某个训练集中的点的单元打上了一个和这个点相同的标签。

这个求解就是纯粹的计算，不具备显式学习过程。当训练集、距离度量（比如欧式距离），k值以及决策规则确定后，对于任何一个新的输入，输出是确定的。

k值的选择会对计算产生重大影响，k太小容易过拟合，过于受到噪声点干扰，太大会受到不相干（相距远）的点的影响，并且模型太简单，通常采用交叉验证来选择最优的k。

最简单的想法是线性扫描，复杂度是$O(N) $，但是N往往很大，所以是不可取的。这里采用了一种特殊的数据结构——kd树

kd树是一种对k维空间中的实例点进行存储以便快速对齐进行检索的数据结构。kd树是二叉树，表示对k维空间的一个划分 构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个节点对应一个超矩形区域。