第8章基于实例的学习-Read.doc

基于实例的学习 已知一系列的训练样例，很多学习方法为目标函数建立起明确的一般化描述；但与此不同，基于实例的学习方法只是简单地把训练样例存储起来。从这些实例中泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。基于实例的学习方法包括最近邻（nearest neighbor）法和局部加权回归（locally weighted regression）法，它们都假定实例可以被表示为欧氏空间中的点。基于实例的学习方法还包括基于案例的推理（case-based reasoning），它对实例采用更复杂的符号表示。基于实例的学习方法有时被称为消极（lazy）学习法，因为它们把处理工作延迟到必须分类新的实例时。这种延迟的或消极的学习方法有一个关键的优点，即它们不是在整个实例空间上一次性地估计目标函数，而是针对每个待分类新实例作出局部的和相异的估计。 简介 基于实例的学习方法中，最近邻法和局部加权回归法用于逼近实值或离散目标函数，它们在概念上都很简明。对于这些算法，学习过程只是简单地存储已知的训练数据。当遇到新的查询实例时，一系列相似的实例被从存储器中取出，并用来分类新的查询实例。这些方法与其他章讨论的方法相比，一个关键差异是：基于实例的方法可以为不同的待分类查询实例建立不同的目标函数逼近。事实上，很多技术只建立目标函数的局部逼近，将其应用于与新查询实例邻近的实例，而从不建立在整个实例空间上都表现良好的逼近。当目标函数很复杂，但它可用不太复杂的局部逼近描述时，这样做有显著的优势。 基于实例的方法也可以使用更复杂的符号表示法来描述实例。在基于案例的学习中，实例即以这种方式表示，而且也按照这种方式来确定邻近实例。基于案例的推理已经被应用到很多任务中，比如，在咨询台上存储和复用过去的经验；根据以前的法律案件进行推理；通过复用以前求解的问题的相关部分来解决复杂的调度问题。 基于实例方法的一个不足是，分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。所以，如何有效地索引训练样例，以减少查询时所需计算是一个重要的实践问题。此类方法的第二个不足是（尤其对于最近邻法），当从存储器中检索相似的训练样例时，它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时，那么真正最“相似”的实例之间很可能相距甚远。 在下一节我们将介绍k-近邻（k-Nearest Neighbor）法，以及这个广泛应用的方法的几个变体。在此之后我们将讨论局部加权回归法，一种建立目标函数的局部逼近的学习方法，这种方法可以被看作k-近邻法的一般形式。然后我们描述径向基函数（radial basis function）网络，这种网络为基于实例的学习算法和神经网络学习算法提供了一个有趣的桥梁。再下一节讨论基于案例的推理，一种使用符号表示和基于知识的推理（knowledge-based inference）的方法。这一节包括了一个基于案例的推理应用实例，用于解决工程设计问题。最后，我们讨论了本章讲述的消极学习方法和本书其他各章的积极（eager）学习方法间的差异。 k-近邻法 基于实例的学习方法中最基本的是k-近邻算法。这个算法假定所有的实例对应于n维欧氏空间(n中的点。一个实例的最近邻是根据标准欧氏距离定义的。更精确地讲，把任意的实例x表示为下面的特征向量： a1(x)，a2(x)，(an(x) 其中ar(x)表示实例x的第r个属性值。那么两个实例xi和xj间的距离定义为d(xi, xj)，其中： d(xi, xj)( 在最近邻学习中，目标函数值可以为离散值也可以为实值。我们先考虑学习以下形式的离散目标函数f : (n(V。其中V是有限集合{v1, (vs}。表8-1给出了逼近离散目标函数的k-近邻算法。正如表中所指出的，这个算法的返回值(xq)为对f(xq)的估计，它就是距离xq最近的k个训练样例中最普遍的f值。如果我们选择k=1，那么“1-近邻算法”就把f(xi)赋给(xq)，其中xi是最靠近xq的训练实例。对于较大的k值，这个算法返回前k个最靠近的训练实例中最普遍的f值。 表8-1 逼近离散值函数f : (n(V的k-近邻算法 训练算法： 对于每个训练样例x, f(x)，把这个样例加入列表training_examples 分类算法： 给定一个要分类的查询实例xq 在training_examples中选出最靠近xq的k个实例，并用x1(xk表示 返回 其中如果a=b那么((a, b)=1，否则((a, b)=0。 图8-1图解了一种简单情况下的k-近邻算法，在这里实例是二维空间中的点，目标函数具有布尔值。正反训练样例用“+”和“-”分别表示