K近邻基础

k近邻法分类的直观理解：给定一个训练数据集，对于新的输入实例，在训练集中找到与该实例最邻近的k个实例。这k个实例的多数属于某个类别，则该输入实例就划分这个类别。

KNN三要素

k近邻法的三要素：k值选择、距离度量和分类决策规则。

k值选择

当k=1时k近邻算法称为最近邻算法。此时将训练集中与$\vec{x}$最近点的类别作为$\vec{x}$的分类。

k值的选择会对k近邻法的结果产生重大影响。

k较小

相当于在较小的邻域中的训练实例进行预测，学习的近似误差减少。

• 优点：只有与输入实例较近的训练实例才会对预测起作用。

• 缺点： 学习的估计误差会增大，预测结果对近邻的实例非常敏感，若近邻的训练实例点刚好是噪声，那么预测就会出错。

k较大

相当于在较大的邻域中的训练实例进行预测

• 优点：减少学习的估计误差
• 缺点：学习的近似误差会增大，使得模型整体变得简单，忽略了训练实例中大量有用的信息。

距离度量

KNN算法要求数据的所有特征都可以做可比较的量化。若在数据特征中存在非数值类型，必须采取手段将其量化为数值。样本有多个参数，每一个参数都有自己的定义域和取值范围。为了公平，样本参数必须做一些归一化处理，最简单的方式就是所有特征的数据都采取归一化处置。

K近邻模型的特征空间一般是n维实数向量空间${\mathbb{R}}^n$。一般为欧式距离，也可以是一般的$L_p$距离：
$$\begin{gathered} L_p(\overrightarrow{x_i},\overrightarrow{x_j})=(\sum _{i=1}^n|x_i^{(l)}-x_j^{(l)}{|}^p{)}^{\frac{1}{p}} \\ \overrightarrow{x_j},\overrightarrow{x_j}\in \mathcal{X}={\mathbb{R}}^n \\ \overrightarrow{x_i}=(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)}{)}^T \\ p\ge 1 \end{gathered}$$
当$p=2$时，为欧式距离

当$p=1$时，为曼哈顿距离

当$p=\infty$时，为每个维度距离中的最大值$L_{\infty }(\overrightarrow{x_i},\overrightarrow{x_j})={\max }_l|x_i^{(l)}-x_j^{(l)}|$

不同的距离度量所确定的最近邻点是不同的，一般情况下，选欧式距离囝距离度量，但只适用于连续度量。

分类决策规则

分类决策通常采用多数表决。也可以基于距离的远近进行加权投票，距离越近的样本权重越大。

多数表决规则等价于经验风险最小化。设分类的损失函数为0-1损失函数，分类函数为f:Rn→{c1c2,⋯ ,ck}f:\mathbb{R}^n \rightarrow \{c_1c_2,\cdots,c_k\}f:Rn→{c1​c2​,⋯,ck​}。误分类概率为$P(Y̸=f(X))=1-P(Y=f(X))$

给定实例$\vec{x}\in \mathcal{X}$，其最近邻的k个训练点构成集合$N_k(\vec{x})$。则误分类率为：
$$\frac{1}{k}\sum _{{\vec{x}}_i\in N_k(\vec{x})}I(y_i̸=c_j)=1-\frac{1}{k}\sum _{{\vec{x}}_i\in N_k(\vec{x})}I(y_i=c_j)$$
即多数表决：
$$c_j=\arg \underset{c_j}{\max }\sum _{\vec{x}\in N_k(\vec{x})}I(y_i=c_j)$$

K近邻算法

• 输入：训练数据集T={(x⃗1,y1),(x⃗2,y2),⋯ ,(x⃗N,yN)},x⃗i∈X⊆RnT=\{(\vec x_1,y_1),(\vec x_2,y_2),\cdots,(\vec x_N,y_N)\},\vec x_i\in \mathcal{X}\sube \mathbb{R}^nT={(x 1​,y1​),(x 2​,y2​),⋯,(x N​,yN​)},x i​∈X⊆Rn为实例的特征向量，yi∈Y={c1,c2,⋯ ,cK}y_i\in \mathcal{Y}=\{c_1,c_2,\cdots,c_K\}yi​∈Y={c1​,c2​,⋯,cK​}为实例的类别。
• 输出：实例$\vec{x}$所属的类别$y$
• 步骤
  • 根据给定的距离度量，在T中寻找与$\vec{x}$最近邻的k个点。定义涵盖这k个点的$\vec{x}$的邻域记作$N_k(\vec{x})$
  • 从$N_k(\vec{x})$中，根据分类决策规则决定$\vec{x}$的类别

kd树

k近邻法中如何对训练数据进行快速k近邻搜索个问题，最简单粗暴的方法是：线性扫描。通过计算输入样本与每个训练样本的距离，来找出最近邻的k个训练样本。当训练集很大时，计算非常耗时，常用的解决方法是使用kd树，可以大幅度提高k近邻搜索的效率。

• 输入：k维空间数据集为T
• 输出：kd树
• 算法步骤
  • 开始：构造根节点。选择$x^1$为轴，以T中所有样本的$x^1$坐标的中位数$x^{1\ast }$作为切分点，将根节点的超矩形切分为两个子区域。切分超平面$x^1=x^{1\ast }$。本次切分产生深度为1的左右子节点。左子节点对应于坐标$x^1<x^{1\ast }$的子区域；右子节点对应于坐标$x^1>x^{1\ast }$的子区域。落在切分超平面上的点$x^1=x^{1\ast }$，保存在根节点。
  • 重复：对深度为$j$的子节点，选择$x^l$为切分的坐标轴，$l=j\mathrm{m}\mathrm{o}\mathrm{d}k+1$ 。本次切分之后，树的深度为$j+1$。这里取模，而不是$l=j+1$，是因为树的深度可以超过维度$k$，此时切分轴又重复回到$x^1$，轮转坐标轴进行切分
  • 结束：直到所有节点的两个子域中没有样本存在时，切分停止。此时得到kd树。

使用kd树的算法相对复杂，用kd树的最近邻搜索算法如下：

• 输入： kd树和样本$\vec{x}$

• 输出：样本$\vec{x}$的最近邻点

• 步骤

  • 在kd树中找到包含测试点$\vec{x}$的叶节点。方法是：从根结点出发，递归向下访问kd树。

    • 若测试点$\vec{x}$当前维度的坐标小于切分点的坐标，则查找当前节点的左子节点。
    • 若测试点$\vec{x}$当前维度的坐标大于切分点的坐标，则查找当前节点的右子节点。

    在访问过程中记录下访问的各节点的顺序。

  • 以此叶节点为当前最近${\vec{x}}_{nst}$。真实最近点一点在$\vec{x}$与当前最近点构成的超球体内。$\vec{x}$为球心。

  • 设当前考察的节点为$\vec{x}$，递归向上回退，设回退弹出的节点为${\vec{x}}_{inew}$（每次回退都是退到kd树的父节点）。考察节点${\vec{x}}_{inew}$所在的超平面与以$\vec{x}$为球心、以$\vec{x}$到当前最近点${\vec{x}}_{nst}$的距离半径的超球体是否相交

    • 若相交

      若${\vec{x}}_i$是${\vec{x}}_{inew}$的左子节点，则进入${\vec{x}}_{inew}$的右子节点，然后先进行向下搜搜，然后向上回退。

      若${\vec{x}}_i$是${\vec{x}}_{inew}$的右子节点，则进入${\vec{x}}_{inew}$的左子节点，然后先进行向下搜搜，然后向上回退。

    • 若不相交，则直接回退

  • 当回到根结点时，搜索结束，最后的当前最近点即为$\vec{x}$的最近邻点。

kd搜索的平均计算复杂度为$O(\log N)$，N为训练集大小。