第四章 k近邻法

1.简介

1.1概念

k近邻法(k-nearest neighbor，k-NN)是一种基本的分类与回归方法。
主要思想：假定给定一个训练数据集，其中实例标签已定，当输入新的实例时，可以根据其最近的k个训练实例的标签，预测新实例对应的标注信息。

• 分类问题：对新的实例，根据与之相邻的k个训练实例的类别，通过多数表决的等方式进行预测。

• 回归问题：对新的实例，根据与之相邻的k个训练实例的标签，通过均值计算进行预测。

1.2 图例解释

1. k=3时，绿色圆点属于红色三角形类别

2. k=5时，绿色圆点属于蓝色正方形类别

1.3 算法

输入： 训练集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ 其中，xi∈X⊆Rn,y∈Y={c1,c2,...,cK}x_i \in \mathcal{X} \subseteq R^n,y\in \mathcal{Y}=\{c_1,c_2,...,c_K\}xi​∈X⊆Rn,y∈Y={c1​,c2​,...,cK​},实例$x$;

输出：实例x所属类别y

1. 根据给定的距离度量，计算x与T中点的距离；

2. 在T中找到与x最邻近的k个点，涵盖这k个点的x的邻域记作$N_k(x)$

3. 在$N_k(x)$中根据分类决策规则(如多数表决)决定x的类别y。
   $y={\mathrm{argmax}}_{c_j}{\sum }_{x_i\in N_k(x)}I(y_i=c_j)$， $ i=1,2,…,N;j=1,2,…,K$ ;I为指示函数当$y_i=c_i$为1，否则为0

1.4 误差率

• 训练集：$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

• 类别合集：Y={c1,c2,...,cK}\mathcal{Y}=\{c_1,c_2,...,c_K\}Y={c1​,c2​,...,cK​}

• 考虑最近邻法：对新实例x,$x_i$为距离它最近的训练实例，两者所属类别分别记作a和b

• 误差率：
  $\begin{array}{rl}Err(x,x_i)& =P(a\ne b|x,x_i)\\ & =\sum _{j=1}^{K}P(a=c_j,b\ne c_j|x,x_i)\\ & =\sum _{j=1}^{K}P(a=c_j|x)P(b\ne c_j|x_i)\\ & =\sum _{j=1}^{K}P(a=c_j|x)(1-P(b=c_j|x_i))\end{array}$

• 当$K\to \infty$时,

  • ${\lim }_{K\to \infty }P(b=c_j|x_i)=P(a=c_j|x)$
    当类别K趋于无穷大时，对于新实例$x$说，它和最近实例$x_i$是同一类别的概率相同

  • $\begin{array}{rl}Err(x,x_i)& =\sum _{j=1}^{K}P(a=c_j|x)(1-P(b=c_j|x_i))\\ & \to \sum _{j=1}^{K}P(a=c_j|x)-\sum _{j=1}^K{P}^2(a=c_j|x)\\ & =1-\sum _{j=1}^J{P}^2(a=c_j|x)\end{array}$

• 假设$x$的真实类别为$c^{\ast }$,
  $c^{\ast }={\mathrm{argmax}}_{c_j\in \mathcal{Y}}P(c_j|x)$
  对应贝叶斯误差率：$P^{\ast }(err|x)=1-P(c^{\ast }|x)$

• 误差率第二项：
  $\begin{array}{rl}\sum _{j=1}^K{P}^2(a=c_j|x)& =P^2(c^{\ast }|x)+\sum _{c_j\ne c^{\ast }}{P}^2(c_j|x)\\ & \le P^2(c^{\ast }|x)+\sum _{c_j\ne c^{\ast }}(\frac{1-P(c^{\ast }|x)}{K-1}{)}^2\\ & =P^2(c^{\ast }|x)+\frac{(1-P(c^{\ast }|x){)}^2}{K-1}\\ & =(1-P^{\ast }{)}^2+\frac{(P^{\ast }{)}^2}{K-1}\end{array}$

• 误差率：
  $Err(x,x_i)\le 1-(1-P^{\ast }{)}^2-\frac{(P^{\ast }{)}^2}{K-1}=2P^{\ast }-\frac{K}{K-1}(P^{\ast }{)}^2$

• 当$P^{\ast }$较小时,$Err(x,x_i)$的上界近似$2P^{\ast }$,则$P^{\ast }\le Err(x,x_i)\le 2P^{\ast }$

• 对于新实例x,推广到k近邻法，当$N\to \infty$且$K\to \infty$时，
  $Err(x)\to P^{\ast }$(即类别K足够大，但相对于样本数量N有足够小，在大样本数量上，用k近邻法近似于最优决策)

2.三要素

k近邻法不具有显性的学习过程，实际上是利用训练数据集对特征向量空间进行划分，以其作为分类的"模型"。

2.1 距离度量

$L_P$距离：

特征空间$\mathcal{X}$假设为$R^n，\forall x_i,x_j\in \mathcal{X},x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)}{)}^T,x_j=(x_j^{(1)},x_j^{(2)},...,x_j^{(n)}{)}^T$,则
$L_p(x_i,x_j)=({\sum }_{I=1}^n|x_i^{(I)}-x_j^{(I)}{|}^P{)}^{\frac{1}{p}},p\ge 1$

• 欧式距离（Euclidean distance）:
  $L_2(x_i,x_j)=({\sum }_{I=1}^n|x_i^{(I)}-x_j^{(I)}{|}^2{)}^{\frac{1}{2}}$

• 曼哈顿距离(Manhattan distance):
  $L_1(x_i,x_j)={\sum }_{I=1}^n|x_i^{(I)}-x_j^{(I)}|$

• 切比雪夫距离(Chebyshev distance):
  $L_{\infty }(x_i,x_j)={\max }_I|x_i^{(I)}-x_j^{(I)}|$

例： 已知二维空间中三个点：$x_1=(1,1{)}^T,x_2=(5,1{)}^T,x_3=(4,4{)}^T$,求p取不同值时，$x_1$的最邻近点。

• $p=1$:$L_1(x_1,x_2)=|1-5|+|1-1|=4,L_1(x_1,x_3)=|1-4|+|1-4|=6$
  此时最邻近点为$x_2$

• $p=2$:$L_2(x_1,x_2)=\sqrt{|1-5{|}^2+|1-1{|}^2}=4,L_2(x_1,x_3)=\sqrt{|1-4{|}^2+|1-4{|}^2}=3\sqrt{2}$
  此时最邻近点为$x_2$

• $p=\infty$:L∞(x1,x2)=max⁡{∣1−5∣,∣1−1∣}=4,L∞(x1,x3)=max⁡{∣1−4∣,∣1−4∣}=3L_{\infty}(x_1,x_2)=\max\{|1-5|,|1-1|\}=4,L_{\infty}(x_1,x_3)=\max\{|1-4|,|1-4|\}=3L∞​(x1​,x2​)=max{∣1−5∣,∣1−1∣}=4,L∞​(x1​,x3​)=max{∣1−4∣,∣1−4∣}=3

此时最邻近点为$x_3$

2.2 k值选择

• 较小的k值，学习的训练误差会减小，但预测误差增大，敏感性增强，而且模型复杂，容易过拟合

• 较大的k值，减少学习的预测误差，但训练误差会增大，模型简单，总是会倾向于选择类别中数量较多的类别

2.3 分类决策规则

多数表决规则：由输入实例的k个邻近的训练实例中多数类决定输入实例的类

• 分类函数： f:Rn→{c1,c2,...,ck}f:R^n \rightarrow \{c_1,c_2,...,c_k\}f:Rn→{c1​,c2​,...,ck​}

• 0-1损失函数： $L(Y,f(x))=\{\begin{array}{l}1,Y\ne f(x)\\ 0,Y=f(x)\end{array}$

• 误分类概率：$P(Y\ne f(x))=1-P(Y=f(x))$

给定实例$x\in \mathcal{X}$,相应的k邻域$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)$,即$N_k$邻域被错误划分为$c_j$类别数量与总数量k的比值

最小化误分类率，等价于$\mathrm{argmax}{\sum }_{x_i\in N_k(x)}I(y_i=c_j)$

kd树

kd树是一种特殊的树形存储结构，用来存储训练数据，以减少计算距离的次数。

3.1 什么是kd数

概念

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。

• 本质：二叉树，表示对k维空间的一个划分

• 构造过程：不断地用垂直于坐标轴的超平面将k维空间切分，形成k维超矩形区域

• kd树的每一个结点对应于一个k维超矩形区域

3.2 构造kd树

输入： k维空间数据集T={x1,x2,...,xN}T=\{x_1,x_2,...,x_N\}T={x1​,x2​,...,xN​} ,其中$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(k)}{)}^T$

输出：kd树

1. 开始：构造根节点

   1. 选取$x^{(1)}$为坐标轴，以训练集中的所有数据$x^{(1)}$坐标的中位树作为切分点，将超矩形区域切割为两个子区域，将该切点作为根结点。

   2. 由根结点生成深度为1的左右子结点，左结点对应坐标小于切分点，右结点对应坐标大于切分点。

2. 重复

   1. 对于深度为j的结点，选择$x^{(I)}$为切分坐标轴，$I=(jmodk)+1$,以该结点区域中所有实例$x^{(I)}$坐标的中位数作为切分点，将区域分为两个子区域

   2. 生成深度为j+1的左右子结点。左结点对应坐标小于切分点，右结点对应坐标大于切分点。

3. 直到两个子区域没有实例时停止。

例题

输入：训练集$T=\{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)\}$

输出：kd树

$x^{(1)}:2,4,5,7,8,9$

开始：选择$x^{(1)}$为坐标轴，中位数为7，即(7,2）为切分点，切分整个区域

再次划分区域：以$x^{(2)}$为坐标轴，选择中位数，左边标区域为4，右边区域为6。故左边区域的切分点为(5,4),
右边区域切分点坐标为(9,6)

划分左边区域：

以$x^{(1)}$为坐标轴，选择中位数，上边区域为4，下边区域为2。故上边区域切分点为(4,7),下边区域切分点为(2,3）

划分右边区域：

以$x^{(1)}$为坐标轴，选择中位数，上边无实例点，下边区域为8，故切分点为(8,1)

训练集划分完毕，输出kd树

3.3 搜索kd树

最近邻搜索：

• 寻找"当前最近点"
  寻找最近邻的子结点作为目标点的"当前最近点"。

• 回溯
  以目标点和"当前最近点"的距离沿树根部进行回溯和迭代。

输入：已构造的kd树，目标点x

输出：x的最近邻

• 寻找"当前最近点"

  • 从根结点出发，递归访问kd树，找出包含x的叶节点；

  • 以此叶结点为"当前最近点";

• 回溯

  • 若该结点比"当前最近点"距离目标点更近，更新"当前最近点";

  • 当前最近点一定存在于该结点的一个子结点对应的区域，检查子结点的父节点的另一个子结点对应区域是否有更近的点

• 当回退到根结点时，搜索结束，最后的"当前最近点"即为x的最近邻点。

例题

输入：kd树，目标点$x=(2.1,3.1)$;

输出：最近邻点

查找过程如下：

1. 初始搜索（向下查找）：

   • 从根节点 $(7,2)$ 出发。第一层切分维度为$x^{(1)}$，切分值为 7。

   • 目标点$x=(2.1,3.1)$的第一维坐标$2.1<7$，因此进入左子树。

   • 到达下一层节点 $(5,4)$。这一层切分维度为$x^{(2)}$，切分值为 4。

   • 目标点$x=(2.1,3.1)$ 的第二维坐标$3.1<4$，因此进入左子树。

   • 到达叶子节点 $(2,3)$。

2. 计算初始距离：

   • 将 $(2,3)$作为当前“最近邻点”。

   • 计算它与目标点的欧氏距离平方：
     $d^2=(2-2.1{)}^2+(3-3.1{)}^2=0.02$

   • 当前最短距离$d=\sqrt{(}0.02)\approx 0.141$

3. 回溯查找（检查是否有更近点）：

   • 回溯到父节点 $(5,4)$：
     该节点的切分维度为 $x^{(2)}$,切分超平面为 $y=4$。目标点$(2.1,3.1)$距离该平面的垂直距离为 $|3.1-4|=0.9$。
     因为$0.9>0.141$，说明切分面另一侧（包含节点 $(4,7)$的右子树）的所有点到目标点的距离都大于 0.9，不可能存在更近的点，因此不搜索右子树。

   • 回溯到根节点 (7,2)：
     根节点的切分超平面为 $x=7$。目标点距离该平面的垂直距离为$|2.1-7|=4.9$。
     因为 4.9>0.141，说明右侧区域（包含节点 (9,6)及其子节点 (8,1)）的所有点距离更远，不搜索右子树。

4. 得出结论：
   经过全部回溯检查，没有发现比 (2,3) 距离目标点 (2.1,3.1) 更近的点。

最终输出： 最近邻点为 (2,3)。