随机模式的分类方法2.pptVIP

Made in CV&PRLab of Shandong University,基本思想：类先验概率未知，考查先验概率变化对错误率的影响，找出使最小贝叶斯风险最大的先验概率，以这种最坏情况设计分类器。 在实际应用中，有时分类器处理的各种类型样本的“先验概率是变化的”，此时再按照某个固定的条件下的决策规则来进行决策，就得不到最小错误率或最小风险所需要得出的结果。这时就要用“最小最大判决规则”了。 先回顾一下2.3节里，介绍的最小风险判决规则，以及条件平均风险的概念和计算公式：,2.6 最小最大判决规则（minimax）,Made in CV&PRLab of Shandong University,把摸式样本归属于条件平均风险 最小的那一种类型。由上式可以看出， 与类概率密度 、损失函数 、先验概率 有关。如果上述因素是不变的，由足够的样本对分类器进行训练，就可以把特征空间划分成不同的类型区域 。如果先验概率 不是确切知道，在训练过程中，采用多组先验概率，就会得到多组类型区域 的划分结果。 另外，条件平均风险仅反映在样本x条件下，判决为的平均风险，而不能反映把整个特征空间划分成某种类型空间的总的平均风险。,（2.3-1）,2.6 最小最大判决规则（minimax）,Made in CV&PRLab of Shandong University,又由于x的观测值是随机向量 ，决策结果又依赖于x，所以决策作为x的函数可以记为 ，它也是一个随机变量。因此，可以定义“平均风险”为：,(2.6-1),其中 为x的取值空间，实际上就是整个特征空间。当特征 空间被划分成c个类型区域 之后(2.6-1)变为：,(2.6-2),2.6 最小最大判决规则（minimax）,Made in CV&PRLab of Shandong University,由上式看出： 如果类型区域的划分不同，则平均风险也不同。 由于先验概率不同，对分类器训练结果，有不同的类型区域划分。 所以，平均风险可作为先验概率的函数。（因为对于各类先验概率组合，有一系列的类型区域划分结果，从而可以计算出一系列的平均风险，可以得到与先验概率的函数关系。） 下面研究一下两类问题，用 和 表示不同的类型，它们的先验概率满足：,2.6 最小最大判决规则（minimax）,Made in CV&PRLab of Shandong University,所以，上述平均风险与先验概率的关系就是 与 的关系，一般是非线性关系。假定已经得到这个关系，如右图曲线所示。 如果预先不确切知道先验概率，能否按照使平均风险最小来选择决策方案呢? 这是不可以的！ 这涉及所谓最小最大判决规则。为了说明这个问题，下面针对两类问题进一步研究平均风险,2.6 最小最大判决规则（minimax）,Made in CV&PRLab of Shandong University,由(2.6-2)：,将 ， ， 代入上式，得到：,(2.6-3),2.6 最小最大判决规则（minimax）,Made in CV&PRLab of Shandong University,又因为 ，代入上式：,又因为： ， 代入上式，得到：,(2.6-4),(2.6-5),(2.6-6),2.6 最小最大判决规则（minimax）,式中：,Made in CV&PRLab of Shandong University,损失函数 是给定的，由(2.6-5)式和(2.6-6)式看出，如果已经确定类型区域 和 ，则a、b为常数。根据(2.6-4)式，平均风险 是先验概率 的线性函数。由于先验概率 的取值范围为01，所以 值变化范围为a(a+b)。 例如，在上图中，在划分类型区域时， ， 。在分类判决过程中，类型区域不再变化，而 可能变化，最大可能的平均风险 ，这是所不希望的。 如何使最大可能的平均风险为最小呢?,2.6 最小最大判决规则（minimax）,Made in CV&PRLab of Shandong University,由(2.6-4)式， ，如果b0， ，且 与 无关，即最大可能的平均风险达到最小值。但是b0又意味着由于类型区域的划分使平均风险达到曲线极值，如下图所示。此时 , 为曲线的最大值。,即在训练过程中使平均风险达到最大值（对于不同的变化的先验概率），恰好在分类判决中使最大可能的平均风险达到最小值（即E-D-F水平线，其他任何一点的切线的最大可能的平均风险都比该直线的最大点要大，例如上面的图中的直线的最高点），这就是最小最大判决规则的基本思想。,2.6 最小最大判决规则（minimax）,Made in CV&PRLab of Shandong University,由上述分析，为了实施最小最大判决规则，必须令b=0。由(2.6-6)式，有：,(2.6-7),此时，在分类判决中，平均风险 为：,(2.6-8),这种情况下，平均风险与先验概率的变化无关。,2.6 最小最大判决规则（minimax）,Made in CV&PRLab of Shandong University,对于特殊情况：,也就是取01损失函数，代入(2.6-46)，有：,最小错误率判决规则的错误率,2.6 最小最大判决规则（minimax）,Made in CV&PRLab of Shandong University,序贯分类方法 基本思想：除考虑分类造成的损失外，还考虑特征获取所造成的代价。先用一部分特征分类，然后逐步加入新特征以减少分类损失，同时衡量总的损失，以求得最优的效益。,2-7 序贯分类,Made in CV&PRLab of Shandong University,2-7 序贯分类,迄今为止所讨论的分类问题，关于待分类样本的所有信息都是一次性提供的。但是，在许多实际问题中，观察实际上是序贯的。随着时间的推移可以得到越来越多的信息。 假设对样品进行第 i 次观察获取一序列特征为：X=(x1,x2,xi)T 则对于1，2两类问题, 若X 1，则判决完毕 若X 2 ，则判决完毕 若X不属1也不属2 ，则不能判决，进行第i+1次观察，得X=(x1,x2,xi,x i+1)T ，再重复上面的判决，直到所有的样品分类完毕为止。 这样做的好处是使那些在二类边界附近的样本不会因某种偶然的微小变化而误判，当然这是以多次观察为代价的。,Made in CV&PRLab of Shandong University,由最小错误概率的Bayes 判决，对于两类问题，似然比为,Made in CV&PRLab of Shandong University,现在来确定A、B的值。 因为,Made in CV&PRLab of Shandong University,Made in CV&PRLab of Shandong University,序贯分类决策规则：,上下门限A、B是由设计给定的错误概率P1(e), P2(e)来确定的，Wald 已证明，观察次数不会很大，它收敛的很快。,Made in CV&PRLab of Shandong University,2-8 决策树多峰情况 Bayes分类器只能适用于样本分布呈单峰情况，对多峰情况则不行。 若用决策树，可进行如下步骤分类,整个分类过程可用右图的树表示: 1、基本概念 （1）决策树：二叉树。每个节点都是两类分类器。例如；节点a上的决策规则为： （2）代价（损失）矩阵 定义节点L的代价为：,Made in CV&PRLab of Shandong University,2、决策树的构造 在构造决策树时，需要考虑以下问题： 1）、如何判断一节点是否为叶子。如右图表示，假定A、B、C、D、E、F各包含50个样本，并有以下的代价矩阵,对于节点a，可以作出以下两个决策之一： 决策1，a不再分割 决策2，a分为两类 决策1的代价为 A1（a）=Ca 节点a的代价 决策2的代价为 A2（a）=（Cb+Cc） 节点b,c的代价和 其中， 为一经验因子，用以防止无限分割下去,Made in CV&PRLab of Shandong University,只要经验因子2.25，便有A2(a) A1(a)，因此取决策2的代价较小，故应把分为两类。 一般地决策代价为：,2）、选择节点的分割方式： a、根据经验确定。例如，全部样本分为三类，其代价矩阵为,Made in CV&PRLab of Shandong University,b、根据对样本分布的了解试探确定。如右图所示，将a划分为b，c的方式有两种 c、根据聚类结果来划分。,3)、如何确定各节点分类器。 原则： 、分类器应尽量简单，因此，多采用线性分类器， 、尽量减小分类时所使用的特征，选用最有效的特征进行分类,Made in CV&PRLab of Shandong University,分类器设计的主要问题 -运用统计决策规则对样本x进行分类,2.9 分类器设计,Made in CV&PRLab of Shandong University,1. 判别函数和决策面 定义：用于表达决策规则的函数称为判别函数。 决策面：将划分决策域的边界面称为决策面。可用数学表达式表达为决策面方程。 对两类最小错误率Bayes决策规则，有4种表达方式：,（4）,对应,2.9 分类器设计,（1）,（2）,（3）,对应,对应,对应,Made in CV&PRLab of Shandong University,对多类别情况：,，c类,同样存在4个决策规则：,（1） （2） （3） （4）,对应,2.9 分类器设计,Made in CV&PRLab of Shandong University,上面讨论了最小错误率Bayes决策，对于最小风险Bayes决策，同样有：,，对应样本,推广到多维情况：,2.9 分类器设计,Made in CV&PRLab of Shandong University,2. 多类判别函数和分类器 （1）判别函数 一般定义，一组函数 ， 表示多类决策规则：,对于多类情况， 可以定义为：,（1） （2） （3）,2.9 分类器设计,Made in CV&PRLab of Shandong University,（2） 决策面方程 各决策域 被决策面所分割，这些决策面是特征空间种的超曲面，对于相邻的两个决策域 和 分割它们的决策面方程应满足：,（显然它们在决策面上相邻决策函数相等）,此时 与 的决策面：,注意： 在一维空间，对应的是点； 在二维空间，对应的是曲线 在三维空间，对应的是曲面 在四维空间，对应的是超曲面 （此处维数是指x的维数）,2.9 分类器设计,Made in CV&PRLab of Shandong University,（3）分类器设计 功能：先设计出c个判别函数 ，再从中选出对应于判决函数为最大值的类作为决策结果。 分类器可由硬件或者软件构成（已经模块化了）。 对于c类问题 ， 等效于,多类分类器结构：,2.9 分类器设计,Made in CV&PRLab of Shandong University,3两类情况 （1）判决函数：,决策规则：,具体来说，可定义 ：,（1） （2） （3）,2.9 分类器设计,Made in CV&PRLab of Shandong University,