模式识别：近邻分类.ppt

2017-2-21 1第4讲近邻分类 2017-2-21 2基于实例的学习概述?已知一系列的训练样例,许多学习方法为目标函数建立起明确的一般化描述。?基于实例的学习方法只是简单地把训练样例存储起来,从这些实例中泛化的工作被推迟到必须分类新实例的时候。?每当学习器遇到一个新的查询实例,它分析这个新实例与以前存储的实例的关系, 并据此把一个目标函数值赋给新实例。 2017-2-21 3基于实例的学习概述?基于实例的学习方法包括: –假定实例可以表示成欧氏空间中的点?最近邻法?局部加权回归法–对实例采用更复杂的符号表示?基于案例的推理 2017-2-21 4基于实例的学习概述?基于实例的学习方法有时被称为消极学习法,它把处理工作延迟到必须分类新的实例时。?这种延迟的学习方法有一个优点:不是在整个实例空间上一次性地估计目标函数, 而是针对每个待分类新实例作出局部的和相异的估计。 2017-2-21 5基于实例的学习概述?基于实例的学习方法的学习过程只是简单地存储已知的训练数据,当遇到新的查询实例时,一系列相似的实例从存储器中取出,用来分类新的查询实例。?与其他方法相比,基于实例的学习方法的一个关键差异是:可以为不同的待分类查询实例建立不同的目标函数逼近。 2017-2-21 6基于实例的学习概述?许多技术不建立目标函数在整个实例空间上的逼近,只建立局部逼近,并将其用于与新实例邻近的实例。?这样做的好处是:有时目标函数很复杂,但具有不太复杂的局部逼近描述。 2017-2-21 7基于实例的学习概述?基于实例的方法的不足: –分类新实例的开销可能很大。?几乎所有的计算都发生在分类时,而不是在第一次遇到训练样例时。如何有效地索引训练样例是一个重要的问题。–当从存储器中检索相似的训练样例时,一般考虑实例的所有属性,如果目标概念仅依赖于很多属性中的几个,那么真正最“相似”的实例之间可能相距甚远。 2017-2-21 8基于实例的学习概述?K-近邻算法和它的几个变体。?局部加权回归法,这是一种建立目标函数的局部逼近的学习方法,被看作 k-近邻算法的一般形式。?基于案例的推理,是一种使用符号表示和基于知识的推理的方法。?径向基函数网络,为基于实例的学习算法和神经网络学习算法提供了一个有趣的桥梁。?消极学习方法和积极学习方法之间的差异。 2017-2-21 9 K-近邻学习概述?不同于 eager 学习算法, K-近邻方法在训练阶段只是简单地把训练样例存储起来,把建模过程推迟到了要预测新实例的工作阶段。因此, K-近邻方法是一种典型的 lazy 学习算法。?k-近邻方法既可以用于目标函数值是离散的情况, 也可以用于是连续的情况。离散的情况就是分类, 连续的情况就是回归。?K-近邻方法的学习过程分两部: 1)找到要预测新实例的 K个邻居; 2)根据这 K个邻居来预测新实例的目标值。 2017-2-21 10k-近邻算法?k-近邻算法假定所有的实例对应于 n维空间 Rn 中的点,任意的实例表示为一个特征向量<a 1 (x), ..., a n (x)> ?根据欧氏距离定义实例间的距离。两个实例x i和x j的距离 d(x i ,x j)定义为?????? nr jrirjixaxaxxd 1 2)()(),(