k近邻法

学习笔记

• k值的选择、距离度量及分类决策规则是k近邻法的三要素
• 三要素在算法之中完整体现出来：

算法

输入: \(T=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}， x_i\in X \sube{\bf{R}^n}, y_i\in Y=\{c_1,c_2,\dots, c_k\}\); 实例特征向量\(x\) 输出: 实例所属的\(y\) 步骤: 1. 根据指定的距离度量，在\(T\)中查找\(x\)的最近邻的\(k\)个点，覆盖这\(k\)个点的\(x\)的邻域定义为\(N_k(x)\) 1. 在\(N_k(x)\)中应用分类决策规则决定\(x\)的类别\(y\) \[ y=\arg\max_{c_j}\sum_{x_i\in N_k(x)}I(y_i=c_j), i=1,2,\dots,N, j=1,2,\dots,K \]

距离度量

• 特征空间中的两个实例点的距离是两个实例点相似程度的反映。

1. \(p=1\) 对应 曼哈顿距离
2. \(p=2\) 对应 欧氏距离
3. 任意\(p\) 对应 闵可夫斯基距离

\[L_p(x_i, x_j)=\left(\sum_{l=1}^{n}{\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^p}\right)^{\frac{1}{p}}\]

• 范数是对向量或者矩阵的度量，是一个标量，这个里面两个点之间的\(L_p\)距离可以认为是两个点坐标差值的\(p\)范数

k值选择

• k值选择会对算法结果产生重大影响。若选较小，只有与输入实例相似的训练实例才会对预测结果起作用，“学习”的近似误差会减小，但“学习”的估计误差会增大，会对近邻的实例点非常敏感，k值减少意味着整体模型变得复杂，容易发生过拟合；若选较大，与输入实例不相似的训练实例也对预测起作用，从而发生错误
• 通过交叉验证选取最优\(k\)，算是超参数，一般k值会取一个较小的数值
• 在二分类问题中，\(k\)选择奇数有助于避免平票

分类决策规则

• 决策规则往往是多数表决(Majority Voting Rule)
• 误分类率

\[\frac{1}{k}\sum_{x_i\in N_k(x)}{I(y_i\ne c_i)}=1-\frac{1}{k}\sum_{x_i\in N_k(x)}{I(y_i= c_i)}\]

• 如果分类损失函数是0-1损失，误分类率最低即经验风险最小。

kd树

• k近邻最简单的实现方法是线性扫描，这时候要计算输入实例与每一个训练实例的距离
• 为了提高k近邻的搜索效率，考虑使用树结构存储训练数据，以减少计算距离的次数
• kd树是二叉树，表示对k维空间的一个划分，注意这里的k和k近邻的k意义并不相同，只是习惯上的一致
• kdTree搜索时效率未必是最优的，这个和样本分布有关系。随机分布样本kdTree搜索(这里应该是最近邻搜索)的平均计算复杂度是\(O(\log N)\)，空间维数\(K\)接近训练样本数\(N\)时，搜索效率急速下降，几乎\(O(N)\)
• kd树的构造：构造根结点，使根结点对应于k维空间中包含所有实例点的超矩形区域；通过递归的方法，不断对k维空间进行切分，生成子节点；直到子区域内没有实例时终止。

  k = len(data[0])  # 数据维度
  
  def CreateNode(split, data_set): # 按第split维划分数据集exset创建KdNode
      if not data_set:    # 数据集为空
          return None
  
      data_set.sort(key=lambda x: x[split])
      split_pos = len(data_set) // 2      # //为Python中的整数除法
      median = data_set[split_pos]        # 中位数分割点             
      split_next = (split + 1) % k        # cycle coordinates
      
      # 递归的创建kd树
      return KdNode(median, split, 
                    CreateNode(split_next, data_set[:split_pos]),     # 创建左子树
                    CreateNode(split_next, data_set[split_pos + 1:])) # 创建右子树
  self.root = CreateNode(0, data)         # 从第0维分量开始构建kd树,返回根节点

kd树最近邻搜索

• 算法 >输入：已构造的\(kd\)树，目标点\(x\) >输出：\(x\)的最近邻 >1. 在\(kd\)树中找出包含目标点\(x\)的叶结点：从根结点出发，递归地向下访问\(kd\)树。若目标点\(x\)当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。 >1. 以此叶结点为“当前最近点”。 >1. 递归地向上回退，在每个结点进行以下操作： > * 如果该点保存地实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。 > * 当前最近点一定存在于该结点一个子结点对应地区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。 > 如果相交，可能在另一子结点对应的区域内存在距离目标点更近的点，移动到另一个子结点。接着递归地进行最近邻搜索； > 如果不相交，向上回退。 >4. 当回退到根结点时，搜索结束。最后的“当前最近点”即为\(x\)的最近邻点。

习题解答

• 3.1 参照图 3.1，在 二维空间中给出实例点，画出 k 为 1 和 2 时的 K 近邻法构成的空间划分，并对其进行比较，体会 K 值选择与模型复杂度及预测准确率的关系。

  • k为1时
  • k为2时

• 3.2 利用例题 3.2 构造的kd树求点 x=(3,4.5) 的最近邻点。

  • 首先找到包含(3,4.5)的叶节点(4,7)，将叶节点作为“当前最近点”；
  • 回退到(4,7)的父节点(5,4)，将(5,4)作为“当前最近点”。以(3,4.5)为圆心，到“当前最近点”(5,4)距离为半径的圆显然和(5,4)的另一个子节点(2,3)区域相交，因此移动到(2,3)；
  • 移动到(2,3)后发现，距离(3,4.5)更近，因此将(2,3)作为“当前最近点”，由于(2,3)是叶节点，因此直接回退；
  • 回到(5,4)的根节点(7,2)，到(7,2)距离大于到“当前最近点”距离，同时(3,4.5)和“当前最近点”距离构成的圆和根节点的另一个子节点的区域不相交，所以搜索结束，得到最近点(2，3)。

• 3.3 参照算法 3.3，写出输出为 x 的 K 近邻的算法。

在寻找最近邻节点的时候需要维护一个”当前最近点“，而寻找 K 近邻的时候，就需要维护一个”当前 K 近邻点集“。首先定义一个”当前 K 近邻点集“插入新点操作：如果”当前 K 近邻点集“元素数量小于K，那么直接将新点插入集合；如果”当前 K 近邻点集“元素数量等于K，那么将新节点替换原来集合中最远的节点。

（1）在 kd 树中找出包含目标点 x 的叶结点：从根结点出发，递归地向下访问树。若目标点 x 当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点，直到子结点为叶结点为止；

（2）如果”当前 K 近邻点集“元素数量小于K或者叶节点距离小于”当前 K 近邻点集“中最远点距离，那么将叶节点插入”当前 K 近邻点集“；

（3）递归地向上回退，在每个结点进行以下操作：

• 如果”当前 K 近邻点集“元素数量小于K或者当前节点距离小于”当前 K 近邻点集“中最远点距离，那么将该节点插入”当前 K 近邻点集“，

• 检查另一子结点对应的区域是否与以目标点为球心、以目标点与于”当前 K 近邻点集“中最远点间的距离为半径的超球体相交。如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点 . 接着，递归地进行最近邻搜索；如果不相交，向上回退；

（4）当回退到根结点时，搜索结束，最后的”当前 K 近邻点集“即为 x 的 K 近邻点集。