简介(3) k近邻算法和它的几个变体 局部加权回归法,这是一种建立目标函数的局 部逼近的学习方法,被看作k-近邻算法的一般 形式 径向基函数网络,它为基于实例的学习算法和 神经网络学习算法提供了一个有趣的桥梁 基于案例的推理,这是一种使用符号表示和基 于知识的推理的方法 消极学习方法和积极学习方法之间的差异 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 6 简介（3） • k-近邻算法和它的几个变体 • 局部加权回归法，这是一种建立目标函数的局 部逼近的学习方法，被看作k-近邻算法的一般 形式 • 径向基函数网络，它为基于实例的学习算法和 神经网络学习算法提供了一个有趣的桥梁 • 基于案例的推理，这是一种使用符号表示和基 于知识的推理的方法 • 消极学习方法和积极学习方法之间的差异
k-近邻算法 k近邻算法是最基本的基于实例的学习方法 k近邻算法假定所有的实例对应于n维空间Rn 中的点,任意的实例表示为一个特征向量 <a1(x)2…,an1(X)> 根据欧氏距离定义实例的距离。两个实例x和x 的距离d(x2x)定义为 dxy)=∑(x)-a( 在最近邻学习中,目标函数值可以是离散的也 可以是连续的,本节先考虑离散的情况。 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 7 k-近邻算法 • k-近邻算法是最基本的基于实例的学习方法 • k-近邻算法假定所有的实例对应于n维空间Rn 中的点，任意的实例表示为一个特征向量 <a1 (x), ..., an (x)> • 根据欧氏距离定义实例的距离。两个实例xi和xj 的距离d(xi ,xj )定义为 • 在最近邻学习中，目标函数值可以是离散的也 可以是连续的，本节先考虑离散的情况。 ( ) = = − n r i j r i r j d x x a x a x 1 2 ( , ) ( ) ( )
k-近邻算法(2) 考虑离散目标函数fRV,V={V1n,s} 表8-1逼近离散值函数fR→V的k近邻算法 训练算法 将每个训练样例<x,x)>加入到列表 training examples 分类算法 给定一个要分类的查询实例x 在 training examples中选出最靠近x的k个实例,并用x1x表 小 返回f(x)← arg max∑6(,f(x) 其中 (a,b) 0a≠b 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 8 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 i i v V q f x v f x 1 ( ) arg max ( , ( )) ˆ = = a b a b a b 0 1 ( , )
k-近邻算法(3) 表8-1的算法返回值是对fx)的估计,它是距离x最近 的k个训练样例中最普遍的f值,结果与k的取值相关 ·图8-1图解了一种简单情况下的k-近邻算法,实例是二 维空间中的点,目标函数具有布尔值,1-近邻算法把x 分类为正例,5-近邻算法把x分类为反例 k-近邻算法不形成关于目标函数f明确的一般假设, 仅在需要时计算每个新查询实例的分类,但依然可以 问:k近邻算法隐含的一般函数是什么? 图8-1中右图画出了1近邻算法在整个实例空间上导致 的决策面形状。这种图称为训练样例集合的 Voronoi图 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 9 k-近邻算法（3） • 表8-1的算法返回值是对f(xq )的估计，它是距离xq最近 的k个训练样例中最普遍的f值，结果与k的取值相关。 • 图8-1图解了一种简单情况下的k-近邻算法，实例是二 维空间中的点，目标函数具有布尔值，1-近邻算法把xq 分类为正例，5-近邻算法把xq分类为反例 • k-近邻算法不形成关于目标函数f的明确的一般假设， 仅在需要时计算每个新查询实例的分类，但依然可以 问：k-近邻算法隐含的一般函数是什么？ • 图8-1中右图画出了1-近邻算法在整个实例空间上导致 的决策面形状。这种图称为训练样例集合的Voronoi图
k-近邻算法(4) 离散的k-近邻算法作简单修改后可用于 逼近连续值的目标函数。即计算k个最接 近样例的平均值,而不是计算其中的最 普遍的值,为逼近fRR,计算式如下: (x)+令f(x) 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 10 k-近邻算法（4） • 离散的k-近邻算法作简单修改后可用于 逼近连续值的目标函数。即计算k个最接 近样例的平均值，而不是计算其中的最 普遍的值，为逼近f: Rn→R，计算式如下： k f x f x k i i q =1 ( ) ( ) ˆ