基于实例的学习机器学习.ppt

2003.12.18 机器学习-基于实例的学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏 机器学习 第8章 基于实例的学习 基于实例的学习 K-近邻算法 局部加权回归 径向基函数 基于案例的推理 基于实例的学习方法有时被称为消极学习法，因为它把处理工作延迟到必须分类新实例的时候。 理解：已知一系列的训练样例，很多学习方法（如决策树，神经网络，贝叶斯学习）为目标函数建立起明确的一般化描述。与此不同，基于实例的学习方法只是简单地把训练样例储存起来，当遇到待分类实例时，建立不同的逼近函数来进行分类。 这种延迟的学习方法有一个优点：不是在整个实例空间上一次性地估计目标函数，而是针对每个待分类新实例作出局部的和相异的估计。 简介 基于实例的学习方法的学习过程只是简单地存储已知的训练数据，当遇到新的查询实例时，一系列相似的实例从存储器中取出，用来分类新的查询实例 与其他方法相比，基于实例的学习方法的一个关键差异是：可以为不同的待分类查询实例建立不同的目标函数逼近 这样做的好处是：有时目标函数很复杂，但却可以用不太复杂的局部逼近描述时，这样做有明显的优势 简介（2） 基于实例的方法的不足： 分类新实例的开销可能很大。 几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。 如何有效地索引训练样例是一个重要的问题 当从存储器中检索相似的训练样例时，一般考虑实例的所有属性，如果目标概念仅依赖于很多属性中的几个，那么真正最“相似”的实例之间可能相距甚远。 理解：待分类实例a1,a2,a3……an,但是它的分类只依赖与a1，a2，那么如果有一个训练样例b1,b2……bn，其中a1=b1,a2=b2，其他的属性值完全不等。因为分类实例的属性只依赖于a1，a2，所以待分类实例的分类应该和这个训练样例一致，但是根据距离d的公式，它的值会很大，则它们两个在欧式空间中相距很远。 k-近邻算法 k-近邻算法是最基本的基于实例的学习方法 k-近邻算法：假定所有的实例对应于n维空间Rn中的点，任意的实例表示为一个特征向量a1(x), ..., an(x) 根据欧氏空间定义实例的距离。两个实例xi和xj的距离d(xi,xj)定义为 在最近邻学习中，目标函数值可以是离散的也可以是实值的，本节先考虑离散的情况。 k-近邻算法（2） 考虑离散目标函数f: Rn?V，V={v1,...,vs} 表8-1逼近离散值函数f: Rn?V的k-近邻算法 训练算法 将每个训练样例x,f(x)加入到训练列表training_examples 分类算法 给定一个要分类的查询实例xq 在training_examples中选出最靠近xq的k个实例，并用x1...xk表示 返回 其中 k-近邻算法（3） 表8-1的算法返回值是对f(xq)的估计，它是距离xq最近的k个训练样例中最普遍的f值，结果与k的取值相关。 图8-1图解了一种简单情况下的k-近邻算法，实例是二维空间中的点，目标函数具有布尔值，1-近邻算法把xq分类为正例，5-近邻算法把xq分类为反例,所以说，结果与K的取值有关。 图8-1中右图画出了1-近邻算法在整个实例空间上导致的决策面形状。这种图称为训练样例集合的Voronoi图 MATLAB：voronoi(x,y) 分别标出x、y的坐标 k-近邻算法（4） 离散的k-近邻算法作简单修改后可用于逼近连续值的目标函数。即计算k个最接近样例的平均值，而不是计算其中的最普遍的值，逼近的实值目标函数f: Rn?R，计算式如下： 在K-近邻算法中，与待分类实例相邻的K个样例（不管远近），对该实例的作用程度（贡献率）都是一样的。 那么，对k-近邻算法做一个改进：对k个近邻的贡献加权，离待分类实例越近的训练样例赋予大的权值，离待分类实例远的样例赋予小的权值。 距离加权最近邻算法 我们根据K个训练样例与xq的距离平方的倒数加权这个训练样例 为了处理查询点xq恰好匹配某个训练样例xi，即导致d(xq,xi)为0的情况，令这种情况下的 等于f(xi)，如果有多个这样的训练样例，我们使用它们占多数的分类 也可以用类似的方式对实值目标函数进行距离加权（距离加权的平均），用下式替代表8-1中的计算式，wi的定义与前相同 距离加权最近邻算法（2） k-近邻算法的所有变体都只考虑k个近邻用以分类查询点，如果使用按距离加权，那么可以允许所有的训练样例影响xq的分类，因为非常远的实例的影响很小 考虑所有样例的唯一不足是会使分类运行得更慢 简单介绍：如果分类一个新实例时，考虑所有的训练样例，我们称为全局法；如果仅考虑靠近的训练样例，称为局部法 对k-近邻算法的说明 距离加权的k-近邻算法对训练数据中的噪声有很好的健壮性，通过取k个近邻的加权平均，可以消除孤立