对于感知器，训练数据中可用的知识被提取并以压缩形式保存在权重wi中。从而丢失了有关数据的信息。然而，如果系统应该从训练数据推广到新数据，这正是所希望的。在这种情况下的泛化是一个时间密集的过程，其目标是以函数的形式找到数据的紧凑表示，该函数尽可能好地分类新数据。
通过简单地保存它们来记忆所有数据是完全不同的。这里的学习非常简单。但是，如前所述，保存的知识并不容易适用于新的未知示例。例如，这种方法非常不适合学习如何滑雪。通过观看优秀滑雪者的视频，初学者永远不会成为一名优秀的滑雪者。显然，当自动进行这种类型的学习运动时，就会发生类似于per-ceptron的情况。经过足够长时间的练习，训练样本中存储的知识被转化为大脑中的内部表征。
然而，有成功的记忆实例，其中也可以进行概括。在诊断疑难病例期间，医生可以尝试记住过去的类似病例。如果他的记忆是健全的，那么他可能会遇到这种情况，在他的文件中查找并最终得出类似的诊断。对于这种方法，医生必须具有良好的相似感，以便记住最相似的情况。如果他找到了这个，那么他必须问自己它是否足够相似以证明同样的诊断。
图8.13 在这个带有负和正训练样例的例子中，最近邻方法将标记为黑色的新点分组为负类
在我们正在构建的形式语境中，相似性意味着什么？我们像往常一样在多维特征空间中表示训练样本并定义：它们在特征空间中的距离越小，两个示例就越相似。
我们现在将此定义应用于图 8.13中的简单二维示例。这里黑点的下一个邻居是一个反面的例子。因此它被分配给负类。
∈∈
例如，两点 x R n 和 y R n 之间的距离d（ x ， y ）可以是
由欧几里德距离测量
ñ
d（ x ， y ）= | x – y | =
i = 1
（xi – yi）2。
因为除了这个之外还有许多其他距离指标，所以考虑具体应用的替代方案是有意义的。在许多应用程序中，某些功能比其他功能更重要。因此，通过权重wi来不同地缩放特征通常是明智的。然后公式读取
dw（ x ， y ）= | x – y | =
ñ
i = 1
wi（xi – yi）2。
i = 1
wi（xi – yi）2。
吨= argmin X ∈ 中号+ ∪ 中号–
{ d（小号， X ）}
以下简单的最近邻分类程序在训练数据中搜索新示例s的最近邻居t，然后将s完全分类为t。3
N
EAREST N EIGHBOR [ M +，M
–， s ]
如果吨 ∈ 中号 + 然后返回（“+”）
其他退货（“ – ”）
3 函数argmin和argmax与min和max类似，确定集合或函数的最小值或最大值。但是，它们不是返回最大值或最小值，而是给出位置，即极值出现的参数。
图8.14。一组点与它们的Voronoi-图（一起左）和分界线根儿ated为两个类中号+和中号–
图8.15最近邻方法将标记为黑色的新点分配给错误（正）类，因为最近邻居很可能被归类为错误
与感知器相比，最近邻方法不生成划分训练数据点的线。但是，确实存在将两个类分开的假想线。我们可以通过首先生成所谓的Voronoi图来生成它。在Voronoi图中，每个数据点都被凸多边形包围，因此在其周围定义了一个邻域。Voronoi图具有以下属性：对于任意新点，数据点中最近的邻居是数据点，其位于相同的邻域中。如果确定了一组训练数据的Voronoi图，则很容易找到要被分类的新点的最近邻居。然后将从最近的邻居获取班级成员资格。
在图 8.14中，我们清楚地看到最近邻方法比感知器明显更强大。它能够正确地实现任意复杂的分界线（通常：超平面）。但是，这里有一个危险。在某些情况下，单个错误点可能导致非常糟糕的分类结果。在黑点分类期间，这种情况发生在图 8.15 中。最近邻方法可能将此错误归类。如果黑点紧挨着作为正定类异常值的正点，那么它将被分类为正而非负的，如此处所预期的那样。对随机误差（噪声）的错误拟合称为过度拟合。
V = { ķ 在最近的邻居中号+∪中号– }
返回（“+”）
返回（“ – ”）返回（随机（“+”，“ – ”））
其他
ElseIf | 中号 +∩ V | < | 中号 – ∩ V | 然后
如果 | 中号 +∩ V | > | 中号 – ∩ V | 然后
K -N EAREST N EIGHBOR（M +
，M – ，s）
图8.16的ķ -N EAREST Ñ EIGHBOR算法
图8.17最近邻分类的相对正确性与反转位数的函数关系。最小值为13且最大值为19的曲线结构与训练数据的特殊结构有关。为了比较，第 174页上的例 8.3中的感知器的值以灰色显示
为了防止由于单个异常值导致的错误分类，建议稍微平滑分割面。这可以通过如下实现：前充足，与ķ -N EAREST Ñ EIGHBOR
图算法8.16，这使得之中的马jority决定ķ最近邻。
例8.4我们现在将N EAREST N EIGHBOR 应用于第174 页的例8.3 。因为我们正在处理二进制数据，所以我们使用汉明距离作为距离度量。4作为测试示例，我们再次使用修改后的训练示例，每个示例具有n 个连续的反转位。在图8.17中，正确分类的测试示例的百分比显示为反转位数b的函数。对于多达8个反转位，可以正确识别所有模式。过了这一点，错误的数量迅速增加。这并不令人惊讶，因为训练模式编号为2
来自M + 类的第 174 页的图 8.11 与两个训练样例的汉明距离为9，其他类别的数字为4和5。这意味着测试
模式很可能接近其他类的模式。很明显，我们看到最近邻分类在本申请中优于感知器，最多可达8个假位。
4 两个位向量之间的汉明距离是两个向量的不同位数。
图8.18学习剂，这是应该避免的光（左），表示为分类器（中间），和作为近似（右）
1.
两个类，许多类，近似
最近邻分类也可以应用于两个以上的类。就像两个类的情况一样，要分类的特征向量的类被简单地设置为最近邻居的类。对于k个最近邻方法，该类将被确定为k个最近邻居中具有最多成员的类。
如果类的数量很大，那么使用分类算法通常不再有意义，因为必要的训练数据的大小随着类的数量而快速增长。此外，在某些情况下，在许多课程的分类过程中会丢失重要的信息。这将在以下示例中变得清晰。
=
=
= –
例8.5 一个自动机器人具有类似于第2页图1.1所示的Braitenberg车辆的简单传感器，应该学会远离光线。这意味着它应尽可能地学习将其传感器值映射到控制行驶方向的转向信号上。机器人正面配有两个简单的光传感器。来自两个传感器的信号（与 SL 用于左眼和 SR 用于右传感器），则关系 X SR / SL 被计算。为了从该值 x 控制两个车轮的电动机，两个电压 Ur 和 U1 的差值 v Ur U1左右电动机分别为。学习代理的任务现在是避免光信号。因此，它必须学习映射 f ，其计算“正确”值 vf（x）。五
为此，我们进行了一项实验，其中，对于一些测量值x，我们发现尽可能优化值v 。这些值作为数据点绘制在图8.18中，并应作为学习代理的训练数据。在最近邻居分类期间，特征空间中的每个点（即，在x轴上）被分类为与训练数据中的最近邻居一样。然后，转向电机的功能是具有大跳跃的阶跃函数（图8.18中间）。如果我们想要更精细的步骤，那么我们必须提供相应的更多训练数据。上
5为了使示例简单易读，故意将特征向量x保持为一维。
另一方面，如果我们近似平滑函数以适合五个点，我们可以获得连续函数（右边第 179 页的图 8.18 ）。要求函数f 连续导致非常好的结果，即使没有额外的数据点。
所述ķ最近邻方法可以以简单的方式向合适近似值问题来施加。在该算法中ķ -N EAREST Ñ EIGHBOR，该组后V =
确定{ x 1， x 2，…， x k } ， k个最近邻居的平均函数值
ķ
ķ
一世
˚F （ X）= 1 F（X ） （8.2）
i = 1
i = 1
被计算并作为近似˚F 用于 查询向量X。更大的k
变，该函数的平滑˚F 是 。
2.
距离是相关的
在k近邻方法的离散以及连续变体的实际应用中，经常出现问题。随着k变大，通常存在比距离小的邻居更远的邻居。从而
计算˚F 被 邻居相距遥远为主。为了防止这种情况，k
对邻居进行加权，使得较远的邻居对结果的影响较小。在该算法中的多数决定ķ -N EAREST Ñ EIGHBOR中，“内容”进行加权的权重
1
一世
w i = 1 + αd（x，x）2 ， （8.3）
随着距离的平方而减小。常数α 确定权重减少的速度。公式（8.2）现在被替换为
˚F （ X）=
ki = 1
wif（x i）。
ķ
我= 1 瓦特我
对于特征空间中点的均匀分布集中，这确保了随着距离的增加，点的影响渐近地接近零。因此，可以使用许多甚至所有训练数据来对给定的输入矢量进行分类或近似。
图8.19的比较 ķ -nearest邻法（上排）与 ķ = 1（左）， ķ = 2（中间）和 ķ = 6（右），其距离加权变体（下排）与 α = 20在一维数据集上（左）， α = 4（中）和 α = 1（右）
为了了解这些方法，在图8.19中，将k-最近邻方法（在上面一行）与其距离加权优化进行比较。由于平均，如果适当地设置k最近邻居或参数α的邻居数，则两种方法都可以推广或换句话说抵消噪声。图表很好地表明，距离加权方法比k最近邻法提供了更平滑的近似。关于近似质量，这种非常简单的方法可以与复杂的近似算法很好地匹配，例如非线性神经网络，支持向量机和高斯过程。
第 180 页的（ 8.3 ）中给出了权重函数（也称为内核）的许多替代方法。例如，可以使用高斯或类似的钟形函数。对于大多数应用程序，结果在选择内核时不是很明智。但是，必须手动设置所有这些功能的宽度参数α 对结果有很大影响，如图 8.19 所示。为了避免这种不方便的手动调整，已经开发了用于自动设置该参数的优化方法[SA94，SE10]。
3.
计算时间
+
如前所述，通过简单地将所有训练向量与其标签（类值）或函数值f（x）一起保存，可以在最近邻方法的所有变体中完成训练。因此，没有其他学习算法可以快速学习。但是，回答分类或近似向量x的查询可能会变得非常昂贵。仅为n个训练数据找到k个最近邻居需要与n线性增长的成本。对于分类或近似，还存在k的线性成本。总计算时间因此增长为Θ（nk）。对于大量的训练数据，这可能会导致问题。
图8.20为了确定雪崩危险，从训练数据中近似得出一个函数。这里用于比较的局部模型（实线），和全球模式（虚线）
4.
摘要和展望
因为在所呈现的最近邻居方法的学习阶段没有发生任何事情，所以这种算法也被称为懒惰学习，与急切学习相反，其中学习阶段可能是昂贵的，但是应用于新示例是非常有效的。感知器和所有其他神经网络，决策树学习以及贝叶斯网络的学习都是渴望学习的方法。由于懒惰学习方法需要使用所有训练数据访问存储器以接近新输入，因此它们也称为基于记忆的学习。
为了比较这两类学习过程，我们将以瑞士某个地区新下雪量确定当前雪崩危险为例。6
在图8.20中输入由专家确定的值，我们希望将其用作训练数据。在应用进行数据线性近似的急切学习算法期间，计算图中所示的虚线。由于对直线的限制，误差相对较大，最大约为1.5危险等级。在延迟学习期间，在查询当前危险等级之前没有计算任何内容。然后从几个最近的邻居（即本地）计算答案。它可能会产生图中所示的曲线，该曲线从线段组合在一起并显示出更小的误差。懒惰方法的优点是它的位置。近似值是从当前的新雪水平本地获取的，而不是全球的。
6 三天的降雪总量实际上是确定危险程度的一个重要特征。但实际上，使用了其他属性[Bra01]。这里使用的示例是简化的。
|
特征 |
询问 |
来自案例库的案例 |
|
有缺陷的部分： |
尾灯 |
前灯 |
|
自行车型号： |
马林松山 |
VSF T400 |
|
1993年 |
2001年 |
|
|
能量源： |
电池 |
发电机 |
|
灯泡状况： |
好 |
好 |
|
光缆条件： |
？ |
好 |
|
解 |
||
|
诊断： |
？ |
前电气接触缺失 |
|
修理： |
？ |
建立正面电气接触 |
图8.21 查询的简单诊断示例和案例库中的相应案例
近年来，这些基于记忆的学习方法正在变得越来越流行，并且已经应用了各种改进的变体（例如局部加权线性回归）[Cle79]。
为了能够使用所描述的方法，训练数据必须以整数或实数的向量的形式可用。因此，它们不适用于其中数据以符号表示的应用，例如作为一阶逻辑公式。我们现在简要讨论一下。
5.
基于案例的推理
在基于案例的推理（CBR）中，最近邻法被扩展为符号问题描述及其解决方案。CBR用于诊断客户服务或电话热线中的技术问题。图 8.21 所示的关于自行车灯外出诊断的例子说明了这种情况。
搜索具有有缺陷的后自行车灯的顾客的查询的解决方案。在右列中，给出了类似于中间列中的查询的情况。这源于案例库，它对应于最近邻法中的训练数据。如果我们只是采用最相似的情况，就像我们在最近邻法中所做的那样，那么当尾灯被打破时，我们最终会尝试修复前灯。因此，我们需要将解决方案反向转换为已发现的类似问题返回查询。解决CBR案例的最重要步骤在第 184 页的图 8.22中进行。此示例中的转换很简单：后灯映射到前灯。
理论上这种方法看起来既美观又简单，实际上CBR诊断系统的构建是一项非常困难的任务。三个主要困难是：
建模应用程序的域必须在正式上下文中建模。这里逻辑单调，我们从Chap知道。4，提出困难。开发人员可以预测并映射所有可能的特殊情况和问题变体吗？
图8.22 如果对于一个案例xa找到类似的情况y，那么为了获得x的解，必须确定变换并将其逆应用于发现的情况y
相似性为符号，非数字特征找到合适的相似性度量。
转换即使发现了类似的情况，目前还不清楚转换映射及其反转应该如何。
实际上，目前使用的诊断应用存在实用的CBR系统。但是，由于上述原因，这些在性能和灵活性方面远远落后于人类专家。CBR的一个有趣的替代方案是Chap中提出的贝叶斯网络。7.通常，符号问题表示也可以很好地映射到离散或连续的数字特征。然后可以成功地使用所提及的归纳学习方法，例如决策树或神经网络。
