最近邻方法

最近邻方法#

1. 基本思想#

最近邻方法（Nearest Neighbor）背后的原理是找到距离新点最近的预定义数量的训练样本，并从这些预测标签中预测标签。样本的数量可是用户定义的常数（k-最近邻学习），或基于点的局部密度（基于半径的近邻学习）而变化。通常，距离可是任何度量标准。基于近邻的方法被称为非泛化机器学习方法，也叫消极学习（lazy learning）。因为它们只是”记住”其所有训练数据（可能变换为快速索引结构，例如Ball Tree或KD Tree）。

最近邻学习不在整个样本空间上一次性地估计目标函数，而是针对每个待测样本作出局部的目标函数逼近。当目标函数很复杂，它可用不太复杂的局部函数来逼近，这样做有非常明显的优势。作为一种非参数方法，它通常在决策边界非常不规则的分类情况下是成功的。

最近邻学习的思想非常简单：给定待测样本，首先基于某种近邻索引方法找出训练集中与其最靠近 的\(k\)个样本，然后基于这\(k\)个样本的后验概率来预测 待测样本的类标记。具体算法分为两个阶段

  • 训练阶段：将每个训练样本保存起来

  • 工作阶段：

    • 给定一个待测样本

    • 基于某种近邻索引方法找出训练样本集中与其最靠近\(k\) 个样本

    • 基于这\(k\)个训练样本的后验概率来预测待测样本的类标记

关于最近邻算法，若两个邻居具有相同的距离但不同的标签，结果将取决于训练数据的排序。

1.1. 最近邻分类#

KNeighborsClassifier 中的 \(k\)-近邻分类是最常用的技术。\(k\)的最佳选择高度依赖于数据：通常，较大的\(k\)会抑制噪声的影响，但会使分类边界变得不则明显。

在数据未被均匀采样的情况下，RadiusNeighborsClassifier 中基于半径的最近邻分类可能是更好的选择。用户指定固定半径\(r\)，使得较稀疏的邻域中的点使用较少的最近邻进行分类。对于高维参数空间，由于所谓的”维度诅咒”，该方法变得不则有效。

基本近邻分类使用均匀权重：即，分配给查询点的值是从最近邻的简单多数投票计算的。在某些情况下，最好对最近邻进行加权，以使较近的最近邻对拟合做出更多贡献。

1.2. 最近邻回归#

基于近邻的回归可用于数据标签是连续的而不是离散的变量的情况。分配给查询点的标签是根据其最近邻居的标签的均值计算的。

1.3. 距离索引#

最近邻学习的所有计算几乎都花费在索引近邻问题上。故，如何有效地索引近邻样本，以减少分类时所需计算是一个重要的实践问题。

目前，使用最多的近邻索引方法就是通过计算待测样本与每个训练样本之间的距离，然后基于距离排序，选择距离最短的\(K\)个训练样本作为待测样本的最近邻样本。因此如何度量样本点之间的距离就变得非常重要了。

为度量样本点之间的距离，学者们提出了许多经典的距离度量函数。根据样本点的数据类型划分，主要有

  • 连续属性：Euclidean 距离，Manhattan 距离等

  • 离散属性：Overlap Metric 距离，Value Difference Metric 距离等

  • 混合属性：HEOM 距离（Heterogeneous Euclidean -Overlap Metric），HVDM（Heterogeneous Value Difference Metric）等

1.4. 树型索引#

  • KD Tree

KD-Tree 数据结构（K 维树的简称）把训练样本存储在树的叶子节点上，邻近的样本存储在相同或相近的叶子节点上，然后通过测试待测样本在内部节点上的划分属性把待测样本划分到相关的叶子节点上。

这种方法因为树的构建是在训练阶段进行的，故比基于距离排序的索引方法所需的计算量要小得多。但如何构建有效的树成了另外一个需要解决的问题。

  • Ball Tree

为了解决更高维度的 KD 树的低效问题，开发了球树数据结构。在 KD 树沿 Cartesian 轴分割数据的地方，球树在一系列嵌套超球体中划分数据。这使得树构造比 KD 树的构建成本更高。但，导致数据结构在高度结构化的数据上非常有效，即使在非常高的维度上亦为如此。

2. 最近邻改进#

2.1. 维度 & 邻域#

前面讲到的许多学习方法，如决策树学习，只测试部分属性就可作出判断，而最近邻学习中样本间的距离是根据样本的所有属性来计算的。若目标函数仅依赖于很多属性中的几个时，样本间的距离会被大量不相关的属性所支配，从而导致相关属性 的值很接近的样本相距很远。

解决维度诅咒的常用方法主要包括

  • 属性加权

  • 属性选择

另一个很重要的参数，那就是邻域的大小，即最近邻样本的数目\(k\)，最近邻学习的预测结果与\(k\)的大小密切相关。同样的数据，\(k\)值不同可能导致不同的预测结果。

目前对于\(k\)值的选取主要有两种办法

  • 基于经验直接给定

    • 选择较小的\(k\)值，相当于用较小的领域中的训练实例进行预测，\(k\)值的减小就意味着整体模型变得复杂，容易过拟合；

    • 选择较大的\(k\)值，相当于用较大领域中的训练实例进行预测，\(k\)值的增大就意味着整体的模型变得简单，容易欠拟合；

  • 基于数据自动学习

2.2. 最近质心法#

NearestCentroid 分类器通过其成员的质心来表示每个类。实际上，这使得它类似于 sklearn.KMeans 算法的标签更新阶段。它也没有选择的参数，使其成为一个很好的基线分类器。但，它确实受到非凸类以及类具有完全不同的方差的影响，因为设所有维度都存在相等的方差。

NearestCentroid 分类器具有 shrink_threshold 参数，该参数实现最近的缩小的质心分类器。实际上，每个质心的每个要素的值除以该要素的类内方差。然后通过 shrink_threshold 减小特征值。最值得注意的是，若特定特征值过零，则将其设置为零。实际上，这会消除该功能影响分类。这很有用。例如，用于删除噪音特征。

2.3. 后验 & 偏置#

给定待测样本的\(k\)个最近邻样本，估计其后验概率的常用方法包括

  • 投票法

  • 加权投票法

  • 局部概率模型法

当计算得到的后验概率出现相同的情况下，可使用随机分类或拒判的方法进行处理。

在计算后验概率的过程经常会使用一些常用的概率估计方法

  • 基于频率的最大似然估计

  • Laplace 估计

  • 基于相似度（距离）加权的 Laplace 估计

  • 朴素贝叶斯估计

最近邻学习的归纳偏置是：在输入空间上相近的样本点具有相似的目标函数输出。即，一个待测样本的类标记与它在输入空间中相邻的训练样本的类标记相似。

有效的距离度量方法可在一定程度上缓解归纳偏置问题，如属性加权的距离度量方法。

Contents