模式识别近邻分类.ppt

模式识别近邻分类基于实例的学习概述已知一系列的训练样例，许多学习方法为目标函数建立起明确的一般化描述。基于实例的学习方法只是简单地把训练样例存储起来，从这些实例中泛化的工作被推迟到必须分类新实例的时候。每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。第2页,共22页，星期六，2024年，5月基于实例的学习概述基于实例的学习方法包括：假定实例可以表示成欧氏空间中的点最近邻法局部加权回归法对实例采用更复杂的符号表示基于案例的推理第3页,共22页，星期六，2024年，5月基于实例的学习概述基于实例的学习方法有时被称为消极学习法，它把处理工作延迟到必须分类新的实例时。这种延迟的学习方法有一个优点：不是在整个实例空间上一次性地估计目标函数，而是针对每个待分类新实例作出局部的和相异的估计。第4页,共22页，星期六，2024年，5月基于实例的学习概述基于实例的学习方法的学习过程只是简单地存储已知的训练数据，当遇到新的查询实例时，一系列相似的实例从存储器中取出，用来分类新的查询实例。与其他方法相比，基于实例的学习方法的一个关键差异是：可以为不同的待分类查询实例建立不同的目标函数逼近。第5页,共22页，星期六，2024年，5月基于实例的学习概述许多技术不建立目标函数在整个实例空间上的逼近，只建立局部逼近，并将其用于与新实例邻近的实例。这样做的好处是：有时目标函数很复杂，但具有不太复杂的局部逼近描述。第6页,共22页，星期六，2024年，5月基于实例的学习概述基于实例的方法的不足：分类新实例的开销可能很大。几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。如何有效地索引训练样例是一个重要的问题。当从存储器中检索相似的训练样例时，一般考虑实例的所有属性，如果目标概念仅依赖于很多属性中的几个，那么真正最“相似”的实例之间可能相距甚远。第7页,共22页，星期六，2024年，5月基于实例的学习概述K-近邻算法和它的几个变体。局部加权回归法，这是一种建立目标函数的局部逼近的学习方法，被看作k-近邻算法的一般形式。基于案例的推理，是一种使用符号表示和基于知识的推理的方法。径向基函数网络，为基于实例的学习算法和神经网络学习算法提供了一个有趣的桥梁。消极学习方法和积极学习方法之间的差异。第8页,共22页，星期六，2024年，5月K-近邻学习概述不同于eager学习算法，K-近邻方法在训练阶段只是简单地把训练样例存储起来，把建模过程推迟到了要预测新实例的工作阶段。因此，K-近邻方法是一种典型的lazy学习算法。k-近邻方法既可以用于目标函数值是离散的情况，也可以用于是连续的情况。离散的情况就是分类，连续的情况就是回归。K-近邻方法的学习过程分两部：1）找到要预测新实例的K个邻居；2）根据这K个邻居来预测新实例的目标值。第9页,共22页，星期六，2024年，5月k-近邻算法k-近邻算法假定所有的实例对应于n维空间Rn中的点，任意的实例表示为一个特征向量a1(x),...,an(x)根据欧氏距离定义实例间的距离。两个实例xi和xj的距离d(xi,xj)定义为第10页,共22页，星期六，2024年，5月伪代码（离散）考虑离散目标函数f:Rn?V，V={v1,...,vs}逼近离散值函数f:Rn?V的k-近邻算法训练算法将每个训练样例x,f(x)加入到列表training_examples分类算法给定一个要分类的查询实例xq在training_examples中选出最靠近xq的k个实例，并用x1...xk表示返回其中第11页,共22页，星期六，2024年，5月伪代码（连续）逼近连续值目标函数f:Rn?R的k-近邻算法训练算法将每个训练样例x,f(x)加入到列表training_examples分类算法给定一个要分类的查询实例xq在training_examples中选出最靠近xq的k个实例，并用x1...xk表示返回第12页,共22页，星期六，2024年，5月距离加权的k-近邻算法（离散）对k-近邻算法的一个改进是对k个近邻的贡献加权，越近的距离赋予越大的权值，比如：其中为了处理查询点xq恰好匹配某个训练样例xi，从而导致d(xq,xi)2为0的情况，令这种情况下的等于f(xi)，如果有多个这样的训练样例，我们使用它们占多数的分类。第13页,共22页，星期六，2024