KNN

什么是KNN

KNN(K近邻)算法：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最近邻的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

KNN使用的模型实际上对应于特征空间的划分，没有显式的训练过程。

KNN三要素

• 距离度量

  特征空间中两个实例点的距离是两个实例点相似程度的反映。设输入实例\(x\in \mathbb{R}^n\)，\(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})} \]

  当p为1时成为曼哈顿距离，当p为2是为欧氏距离，当p为正无穷大时为各个坐标轴距离的最大值。不同的p值可能导致最近邻点的选取不同。

• k值

  较小的k值代表整体模型变得复杂，分类结果容易被噪声点影响，容易发生过拟合。

  较大的k值代表整体模型变得简单，容易欠拟合。

  在应用中，k值一般取一个比较小的数值，通常采用交叉验证法来选取最优的k值。

• 分类决策规则

  一般采用多数表决规则。

kd树

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

• 构造平衡kd树的算法：

  输入：k维空间数据集\(T=\{x_1,x_2,..,x_N\}\)，其中\(x_i=(x_i^{(0)},x_i^{(1)},...,x_i^{(l-1)})\)为\(l\)维向量。

  输出：kd树。

  1. 开始：构造根结点，根结点对应于包含T的l维空间的超矩形区域。

     选择\(x^{(0)}\)为坐标轴，以T中所有实例在该坐标轴上的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并于坐标轴\(x^{(0)}\)垂直的超平面实现。

     由根结点生成深度为1的左、右子结点，分别对应坐标轴\(x^{(0)}\)小于和大于切分点的子区域，将落在切分超平面上的实例点保存在根结点

  2. 对深度为j的结点，选择\(x^{j\bmod l}\)为切分坐标轴（也可选择方差最大的坐标轴），重复1所述的切分过程。

  3. 直到两个子区域没有实例存在时停止，从而形成kd树的区域划分。

• kd树的最近邻搜索

  输入：kd树，目标点x；

  输出：x的最近邻；

  1. 在kd树中从根结点出发，递归向下查找包含目标点x的叶结点；
  2. 以此叶结点为当前最近点；
  3. 递归向上回退，在每个结点进行以下操作：
     • 如果该结点保存到实例点比当前最近点距离目标点更近，则以该实例点位当前最近点。
     • 检查该结点的另一子结点是否与以目标点为球心，以目标点与当前最近点间的距离为半径的超球体相交。如果相交，则移动到另一子结点进行递归搜索，，否则向上回退。
     • 当回退到根结点时，搜索结束，当前最近点即为x的最近邻点。