机器学习基于实例的学习

2020/6/211第8章基于实例的学习8.1简介8.2k一近邻算法8.3局部加权回归8.4径向基函数8.5基于案例的推理8.6对消极学习和积极学习的评论8.7小结和补充读物2020/6/2128.1简介（1/3）思想：基于实例的学习方法先把训练样例存储起来。泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。基于实例的学习方法有时被称为消极(lazy)学习法，因为它们把处理工作延迟到必须分类新的实例时。与其相对的方法称为积极的（eager)。延迟的或消极的学习方法有一个关键的优点，即它们不是在整个实例空间上一次性地估计目标函数，而是针对每个待分类新实例作出局部的和相异的估计。2020/6/2138.1简介（2/3）基于实例的学习方法包括最近邻法(nearestneighborNN)和局部加权回归(locallyweightedregressionLWR)法，它们都假定实例可以被表示为欧氏空间中的点。基于实例的学习方法还包括基于案例的推理(case-basedreasoningCBR）它对实例采用更复杂的符号表示。2020/6/2148.1简介（3/3）基于实例方法的一个不足是，分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。所以如何有效地索引训练样例，以减少查询时所需的计算是一个重要的实践问题。第二个不足是(尤其对于最近邻法)，当从存储器中检索相似的训练样例时，它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时，那么真正最“相似”的实例之间很可能相距甚远。2020/6/2158.2k一近邻算法（1/5）k一近邻算法假定所有的实例对应于n维空间Rn中的点。一个实例的最近邻是根据标准欧氏距离定义的。即把任意实例x表示为下面的特征向量:a1(x),a2(x),…,an(x)其中,ar(x)表示实例x的第r个属性值。那么，两个实例xi和xj间的距离定义为d(xi,xj)，其中:21(,)(()())nijrirjrdxxaxax2020/6/216逼近离散值函数的k-近邻算法KNN训练算法:对于每个训练样例x,f(x)，把这个样例加人列表training_examples。分类算法:给定一个要分类的查询实例xq。在training_examples中选出最靠近xq的k个实例，并用x1，…xk表示。返回其中，如果a=b,那么(a，b)=l，否则(a，b)=0。就是距离xq最近的k个训练样例中最普遍的分f值。1ˆ()argmax(,())kqivVifxvfxVfn:ˆ()qfx2020/6/2178.2k一近邻算法（2/5）下图图解了一种简单情况下的k一近邻算法，在这里实例是二维空间中的点，目标函数具有布尔值。正反训练样例用“+”和“-”分别表示。图中也画出了一个查询点xq。1一近邻算法把xq分类为正例，然而5一近邻算法把xq分类为反例。2020/6/2188.2k一近邻算法（3/5）k-近邻算法隐含考虑的假设空间H的特性:k-近邻算法并不形成关于目标函数f的明确的一般假设。它仅在需要时计算每个新查询实例的分类。隐含的一般函数是什么?或者说，如果保持训练样例不变，并用X中的每个可能实例查询算法，会得到什么样的分类?2020/6/2198.2k一近邻算法（4/5）下图画出了1一近邻算法在整个实例空间上导致的决策面形状。决策面是围绕每个训练样例的凸多边形的合并。对于每个训练样例，多边形指出了一个查询点集合，它的分类完全由相应训练样例决定。在这个多边形外的查询点更接近其他的训练样例。这种类型的图经常被称为这个训练样例集合的Voronoi图（梯森多边形）。2020/6/21108.2k一近邻算法（5/5）对k一近邻算法作简单的修改，它可被用于逼近连续值的目标函数。让算法计算k个最接近样例的平均值，而不是计算其中的最普遍的值。更精确地讲，为了逼近一个实值目标函数，我们使用公式:nf:kxfxfkiiq1)()(ˆ2020/6/21118.2.1距离加权最近邻算法（1/3）对k一近邻算法的一个改进是对k个近邻的贡献加权，根据它们相对查询点xq的距离，将较大的权值赋给较近的近邻。在逼近离散目标函数的算法中，可以根据每个近邻与xq的距离平方的倒数加权这个近邻的“选举权”:当xq=xi，将导致分母d(xqxi)2为0，此时令。如果有多个这样的训练样例，我们使用它们中占多数的分类。ˆ()()qifxfx))(,(maxarg)(ˆ1kiiiViqxfvwxf2),(1iqixxdw2020/6/21128.2.1距离加权最近邻算法（2/3）对实值目标函数进行距离加权，用下式：其中，wi的定义与前式中相同。注意该式中的分母是一个常量，它将不同权值的贡献归一化(例如，它保证如果对所有的训练样例xi，f(xi)＝c，那么，。ˆ()qfxckiikiiiqwxfwxf11)()(ˆ2020/6/21138.2.1距离加权最近邻算法（3/3）注意，以上k一近邻算法的所有变体都只考虑k个近邻用以分类查询点。可以考虑所有的训练样例影响的分类，因为非常远的实例对其影响很小。考虑所有样例的惟一不足是会使分类运行得更慢。如果分类一个新的查询实例时考虑所有的训练样例，我们称它为全局(global)法。如果仅考虑最靠近的训练样例，我们称它为局部(local)法。当式(8.4)（前式）的法则被应用为全局法时，它被称为Shepard法。ˆ()qfx2020/6/21148.2.2对k-近邻算法的说明（1/6）按距离加权的k一近邻算法是一种非常有效的归纳推理方法。它对训练数据中的噪声有很好的健壮性，而且当给定足够大的训练集合时也非常有效。注意，通过取k个近邻的加权平均，可以消除孤立的噪声样例的影响。k一近邻算法的归纳偏置对应于假定:一个实例的分类xq与在欧氏空间中它附近的实例的分类相似。2020/6/21158.2.2对k-近邻算法的说明（2/6）应用k一近邻算法的一个实践问题是，实例间的距离是根据实例的所有属性(也就是包含实例的欧氏空间的所有坐标轴)计算的。考虑把k一近邻算法应用到这样一个问题:每个实例由20个属性描述，但在这些属性中仅有2个与它的分类有关。在这种情况下，这两个相关属性的值一致的实例可能在这个20维的实例空间中相距很远。结果，依赖这20个属性的相似性度量会误导k一近邻算法的分类。2020/6/21168.2.2对k-近邻算法的说明（3/6）近邻间的距离会被大量的不相关属性所支配。这种由于存在很多不相关属性所导致的难题，有时被称为维度灾难(curseofdimensionality)最近邻方法对这个问题特别敏感。解决维度问题的一个有趣的方法是，当计算两个实例间的距离时，对每个属性加权。这相当于按比例缩放欧氏空间中的坐标轴，缩短对应于不太相关的属性的坐标轴，拉长对应于更相关的属性的坐标轴。每个坐标轴应伸展的量可以通过交叉验证的方法自动决定。2020/6/21178.2.2对k-近邻算法的说明（4/6）具体做法如下：首先，假定使用加权因子zj，伸展(乘)第j个根坐标轴，选择zj的各个值z1…zn，以使学习算法的真实分类错误率最小化。其次，这个真实错误率可以使用交叉验证来估计。交叉验证:随机选取现有数据的一个子集作为训练样例，然后决定z1…zn的值使剩余样例的分类错误率最小化。通过多次重复这个处理过程，可以使加权因子的估计更加准确。这种伸展坐标轴以优化k一近邻算法的过程，提供了一种抑制无关属性影响的机制。2020/6/21188.2.2对k-近邻算法的说明（5/6）另外一种更强有力的方法从实例空间中完全消除最不相关的属性。这等效于设置某个缩放因子zj为0。注意，上面的两种方法都可以被看作以某个常量因子伸展坐标轴。另外一种可选的做法是使用一个在实例空间上变化的值伸展坐标轴。这样增加了算法重新定义距离度量的自由度，然而也增加了过度拟合的风险。所以，局部伸展坐标轴的方法是不太常见的。2020/6/21198.2.2对k-近邻算法的说明（6/6）应用k一近邻算法的另外一个实践问题是如何建立高效的索引。因为k一近邻算法推迟所有的处理，直到接收到一个新的查询，所以处理每个新查询可能需要大量的计算。一种索引方法是kd-tree，它把实例存储在树的叶结点内，邻近的实例存储在同一个或附近的结点内。通过测试新查询xq的选定属性，就可以把查询xq排列到相关的叶结点。2020/6/21208.2.3术语注解回归(Regression)的含义是逼近一个实数值的目标函数。残差(Residual)是逼近目标函数时的误差核函数(Kernelfunction)是一个距离函数，它用来决定每个训练样例的权值。换句话说，核函数就是使wi=K(d(xi,xq))的函数K。ˆ()()fxfx2020/6/21218.3局部加权回归（1/2）最近邻方法可以被看作在单一的查询点x=xq上逼近目标函数f(x)。（没有明确的目标函数，只有目标值）局部加权回归是最近邻方法的推广。它在环绕xq的局部区域内为目标函数f建立明确的逼近。使用附近的或距离加权的训练样例来形成这种对f的局部逼近。可以使用线性函数、二次函数、多层神经网络或者其他函数形成在环绕xq的邻域内逼近目标函数。“局部加权回归”名称中，“局部”是指目标函数的逼近仅仅根据查询点附近的数据;“加权”是指每一个训练样例的贡献是由它与查询点间的距离加权的;“回归”表示逼近实数值函数。2020/6/21228.3局部加权回归（2/2）给定一个新的查询实例，局部加权回归的一般方法是：建立一个逼近，使拟合环绕xq的邻域内的训练样例。(可以使用归纳学习等方法）然后用这个逼近来计算的值，也就是为查询实例估计的目标值输出。然后，的描述被删除，因为对于每一个独立的查询实例都会计算不同的局部逼近。fˆfˆ)x(ˆqffˆ2020/6/21238.3.1局部加权线性回归(1/3)使用如下形式的线性函数来逼近xq邻域的目标函数f:ai(x)表示实例x的第i个属性值。梯度下降方法中，感兴趣的是目标函数的全局逼近。权值选择方法是使训练集合D上的误差平方和最小化，即:根据这个误差定义，我们得出了以下梯度下降训练法则:2020/6/21248.3.1局部加权线性回归(2/3)修改这个过程来推导出局部逼近方法是:重新定义误差准则E以着重于拟合局部训练样例。下面给出了三种可能的误差准则。1)只对在k个近邻上的误差平方最小化:2)使整个训练样例集合D上的误差平方最小化，但对每个训练样例加权，权值为关于相距xq距离的某个递减函数K:3)综合1和2:21k1ˆ()(()())2qqxxExfxfx的个近邻221ˆ()(()())((,))2qqxDExfxfxKdxx23k1ˆ()(()())((,))2qqqxxExfxfxKdxx的个近邻2020/6/21258.3.1局部加权线性回归(3/3)使用上面的准则3，并使用与第4章相同的推理方式重新推导梯度下降法则，可以得到以下训练法则:注意，这个新的法则和全局逼近给出的法则的差异是:实例x对权值更新的贡献现在乘上了一个距离惩罚项K(d(xq，x))仅对k个最邻近的训练实例的误差求和。kˆ((,))(()())()qiqjxxwKdxxfxfxax的个近邻2020/6/21268.3.2局部加权回归的说明上面考虑了使用一个线性函数在查询实例xq的邻域内逼近f。在局部加权回归的文献中，在对训练样例距离加权方面，还有很多其他可选方法，还有很多目标函数局部逼近方法。通常使用一个常量、线性函数或二次函数来局部逼近目标函数，一般不使用更复杂的函数，原因是:(1)对每个查询实例用更复杂的函数来拟合，其代价