统计机器学习-k近邻法

作者: 又双叒叕苟了一天 | 来源:发表于2020-07-08 17:20 被阅读0次

k近邻法既可以用于分类，也可以用于回归，这里只讨论分类的k近邻法。k近邻法的思路是：给定一个输入，在训练集中找出 $k$ 个最相近的实例，然后分到这 $k$ 个实例大多数归属的一个类。

k近邻法包含三个要素：

（1）k值的选择

（2）距离度量（如欧氏距离、曼哈顿距离等等）

（3）分类决策规则（如多数表决）

k近邻算法

输入：训练数据集
$T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$
其中， $x_i\in\mathcal X=\textbf R^n$ 为实例的特征向量 $y_i\in\mathcal Y= \{c_1,c_2,\cdots,c_K\}$ ，为实例的类别， $i=1,2,\cdots,N$ ；实例特征向量 $x$ 。

输出：实例 $x$ 所属的类 $y$ 。

（1）根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最邻近的 $k$ 个点，涵盖这 $k$ 个点的 $x$ 的领域记做 $N_k(x)$ ；

（2）在 $N_k(x)$ 中根据分类决策规则（如多数表决）决定 $x$ 的类别 $y$ ：
$y=\arg\max_{c_j}\sum_{x_i\in N_k(x)}I(y_i=c_k), \ \ i=1,2,\cdots,N;\ \ j=1,2,\cdots,K$
其中 $I$ 是指示函数，当 $y_i=c_j$ 时为1，否则为0。

下面针对三个要素提出解决方案。

k值的选择

k值的选择会对k近邻法的结果产生重大影响。一般k越小代表模型变复杂，容易出现过拟合（低偏差，高方差），尤其是当近邻点是噪声点时，预测就会出错。k越大，模型越简单。当k等于样本数 $N$ 时，模型最简单，但是忽略了样本中大量的有用信息。

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

距离度量

距离可以选择如下度量方式：

（1） $L_p$ 距离：
$L_p(x_i,x_j)=\bigg(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p\bigg)^{\frac1p}$
（2）欧氏距离（ $L_2$ 距离）：
$L_2(x_i,x_j)=\bigg(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^2\bigg)^{\frac12}$
（3）曼哈顿距离（ $L_1$ 距离）：
$L_1(x_i,x_j)=\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|$
等等。

分类决策规则

通常使用多数表决规则，即有输入实例的 $k$ 个邻近的训练实例中的多数类决定输入实例的类。多数表决相当于经验风险最小化。

kd树

k近邻法需要计算输入实例和训练集中所有实例的距离。当训练集很大时，如果采用线性扫描的方式，是十分费时的。为了提高效率，对训练样本可以采用树结构存储，减少计算距离的次数。

kd树是平衡二叉树，即左子树小于右子树，且任意子树高度差小于等于1。下面给出kd树的构造方法。

构造平衡kd树

输入： $k$ 维空间数据集 $T= \{x_1,x_2,\cdots,x_N\}$ ，其中 $x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(k)})$ ， $i=1,2,\cdots,N$ ；

输出： $kd$ 树。

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

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

由根结点生成深度为1的左右子结点：左子结点对应坐标 $x^{(1)}$ 小于切分点的子区域，右子结点对应于坐标 $x^{(1)}$ 大于切分点的子区域。

将落在切分超平面上的实例点保存在根结点。

（2）重复：对深度（根结点深度为0）为 $j$ 的结点，选择 $x^{(l)}$ 为切分坐标轴， $l=(j\mod k)+1$ ，以该结点的区域中所有实例 $x^{(l)}$ 坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(l)}$ 垂直的超平面实现。

由该结点生成深度为 $j+1$ 的左、右子结点：左子结点对应坐标 $x^{(l)}$ 小于切分点的子区域，右子结点对应于坐标 $x^{(l)}$ 大于切分点的子区域。

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

上述算法在深度0时，选择 $x_i$ 的第一个维度 $x_i^{(1)}$ 划分成两棵子树，在深度1时，选择 $x_i$ 的第二个维度 $x_i^{(2)}$ 划分，依次直到对最后一个维度 $x_i^{(k)}$ 划分完，然后再次从第一个维度划分，不断循环直到实例全部划分完。当然在每个深度上的维度选择上，也可以参考决策树的特征选取方式。构造完kd树，下面介绍如何搜索。

用kd树的最近邻搜索

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

输出： $x$ 的最近邻。

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

（2）以此叶结点为“当前最近点”。

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

（a）如果该结点保存的实例点比当前最近点距离目标点更近，则该实例点为“当前最近点”。

（b）当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体的，检查另一子结点对应的区域是否与以目标点为球心，以目标点与“当前最近点”间的距离为半径的超球体相交。

如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归的进行最近邻搜索；

如果不相交，向上回退。

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

如果要找 $k$ 个最近邻点，只需对该算法稍作修改。该搜索的平均计算复杂度是 $O(\log N)$ ，当样本数远大于特征数时，效果更好，当特征数和样本数相近时，效率下降，接近线性搜索。

另外超矩形区域和球体判断相交：只需要在超矩形区域的每个维度上找与球心对应维度上最近的点，然后计算到球心的距离，如果大于半径，则不相交。

统计机器学习-k近邻法

k近邻算法

k值的选择

距离度量

分类决策规则

kd树

构造平衡kd树

用kd树的最近邻搜索

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读