7.近邻法(2学时).ppt

* 4. 压缩近邻法 * 【问题的提出】 剪辑近邻法所得到的剪辑样本集在样本数量的压缩方面并不十分明显，它的作用在于将原样本集中处于边界处样本删除掉，但靠近两类中心大部分样本仍被保留下来。 按近邻规则来看，这些样本中的大多数对分类决策没什么用处，如能在剪辑的基础上再去掉一部分这样的样本，将有助于进一步缩短计算时间与压缩存储量，这种方法称为压缩近邻法。 * 【基本思想】 压缩近邻法压缩样本的思想很简单，它利用现有样本集，逐渐生成一个新的样本集。使该样本集在保留最少量样本的条件下, 仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类, 并保持正常识别率。 该算法的作法也十分简单，它定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。 * 【步骤】 1.［初始化］ Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store中作为新样本集第一个样本。 2.［样本集生成］ 在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若分类正确，则将该样本放回Grabbag中，对Grabbag中所有样本重复上述过程。 3.［结束过程］ 若Grabbag中所有样本在执行第二步时没有发生转入Store的现象，或Grabbag已成空集，则算法终止，否则转入第二步。 * 【举例】 剪辑样本经压缩近邻法生成的压缩样本集。从中可看出样本的数量极大地减少了。 图中还画出了贝叶斯分界面与压缩后的近邻法决策面，它虽然比剪辑样本的近邻产生的决策面偏离贝叶斯决策面要大些，但所需样本数量却大大减少了，因此可以大大节省存储量。 * 【本章小结】 几个要点： 弄清楚近邻法的定义以及基本做法。 弄清“近邻法性能好”是在什么意义上讲的？ 快速有哪些信誉好的足球投注网站方法是使用怎样的原理？ 剪辑近邻法的原理是什么? 而压缩近邻法与剪辑近邻法有什么不同之处？ 有7个二维向量: x1=[1; 0], x2=[0;1], x3=[0;-1], x4=[0;0], x5=[0;2], x6=[0;-2], x7=[-2;0] 其中前三个属于w1类，后四个属于w2类。 请画出最近邻法决策面。 * 【课后习题】 * 本章结束 国家杰出青年科学基金答辩申请 * 国家杰出青年科学基金答辩申请 * 国家杰出青年科学基金答辩申请 * 国家杰出青年科学基金答辩申请 * 国家杰出青年科学基金答辩申请 * 国家杰出青年科学基金答辩申请 * 国家杰出青年科学基金答辩申请 * 国家杰出青年科学基金答辩申请 * 国家杰出青年科学基金答辩申请 * 国家杰出青年科学基金答辩申请 * 国家杰出青年科学基金答辩申请 * 国家杰出青年科学基金答辩申请 * * 哈尔滨工业大学 第6章 近邻法 李君宝 * 0.引言 1.近邻法原理及其决策规则 2.快速有哪些信誉好的足球投注网站近邻法 3.剪辑近邻法 4.压缩近邻法 * 0.引言 * 【引言】 模式识别或者分类的基本方法有两大类: 一类是将特征空间划分成决策域,需要确定判别函数或确定分界面方程。 另一类是模板匹配:将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。 近邻法在原理上属于模板匹配。 它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)，就以最近似的模板的类别作为自己的类别。 * 【引言】 近邻法优缺点： 1）原理简单、易于实现，在模板数量很大时其错误率低。 2）计算量大，存储量大，要存储的模板很多，每个测试样本要对每个模板计算一次相似度。 * 1.近邻法原理及其决策规则 * 【基本原理】 背景： 最小距离分类器是将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本为代表点。测试样本的类别则以其与这些代表点距离最近作决策。该法的缺点是所选择的代表点并不一定能很好地代表各类, 后果将使错误率增加。 近邻法的基本思想： 一种极端的情况是以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。 * 【最近邻法决策规则 】 若 则 其中 表示是 类的第 个样本。决策规则为: 定义：将与测试样本最近邻样本类别作为决策的方法。 对一个 类别问题，每类有 个样本，