[理学]模式识别导论二.ppt

模式识别 Pattern Recognition,张正道 江南大学通信与控制工程学院 信息安全系,第二章 贝叶斯决策理论,贝叶斯分类器 最小风险Bayes分类器 聂曼皮尔逊判别准则 最大最小判别准则 序贯分类 正态分布决策理论 关于分类的错误率分析,2-1 引言,应用要求： 各类别总体的的概率分布已知 要决策分类的类别数一定 假设样本有d个观测量(特征) x= (X1,X2,Xd)T 称：X为d维特征向量，其所有可能的取值构成d维特征空间。 假设要求：要研究的分类问题有C个类，分别由 表示。各类 出现的先验概率 以及类条件概率密度函数 已知。,对x再观察：有细胞光密度特征 ,有类条件概率密度: P(x/ ) =1,2,。如图所示 利用贝叶斯公式 ： 通过 对细胞的再观察，就可以把先验概率转化为后验概率，利用后验概率可对未知细胞x进行识别 。,2-2 几种常见的决策规则,一、基于最小错误率的Bayes决策 1、两类问题 例如：细胞识别问题 1正常细胞，2异常细胞 某地区，经大量统计获先验概率P(1),P(2)。若取该地区 某人细胞x属何种细胞 ，只能由 先验概率决定。,设N个样本分为两类1，2。每个样本抽出n个特征， x =（x1， x2， x3， xd）T,通过 对细胞的再观察，就可以把先验概率转化为后验概率，利用后验概率可对未知细胞x进行识别 。,1、判别函数： 若已知先验概率P(1),P(2)，类条件概率密度P(x/ 1)， P(x/ 2)。 则可得贝叶斯判别函数四种形式 ：,2、决策规则：,2、决策规则：,2、决策规则：,2、决策规则：,3、决策面方程： x为一维时，决策面为一点，x为二维时决策面为曲线，x为三维时，决策面为曲面，x大于三维时决策面为超曲面。 例：某地区细胞识别； P(1)=0.9， P(2)=0.1 未知细胞x，先从类条件概率密度分布曲线上查到： 解：该细胞属于正常细胞还是异常细胞，先计算后验概率：,P(x/ 1)=0.2， P(x/ 2)=0.4,4、分类器设计：,2、多类情况：=(1,2,c)，x=(x1,x2,xd) 1.判别函数：M类有M个判别函数g1(x), g2(x), gd(x).每个判别函数有上面的四种形式。 2.决策规则：,另一种形式：,3、决策面方程： 4、分类器设计：,一般错误率分析：,二、最小风险Bayes分类器 假定要判断某人是正常(1)还是肺病患者(2),于是在判断中可能出现以下情况： 第一类，判对(正常正常) 11 ；第二类，判错(正常肺病) 21 ； 第三类，判对(肺病肺病) 22；第四类，判错(肺病正常) 12 。 在判断时，除了能做出“是” i类或“不是” i类的动作以外，还可以做出“拒识”的动作。为了更好地研究最小风险分类器，我们先说明几个概念：,假定有c类问题，用 表示类型，用 表示可能作出的判决。实际应用中，判决数a和类型数c可能相等，ac；也可能不等，即允许除c类的c个决策之外，可以采用其它决策，如“拒绝”决策，此时ac+1。,行动i：表示把模式x判决为i类的一次动作。 损耗函数ii=(i/i)表示模式X本来属于i类而错判为i所受损失。因为这是正确判决，故损失最小。 损耗函数ij=(i/j)表示模式X本来属于j类错判为i所受损失。因为这是错误判决，故损失最大。 风险R（期望损失）：对未知x采取一个判决行动(x)所付出的代价（损耗）,由于判决数目有a个，这样对于不同的判决和不同类型就有一个a*c维风险矩阵。,在整个特征空间中定义期望风险, 期望风险：,条件风险（也叫条件期望损失）：,条件风险只反映对某x取值的决策行动i所带来的风险。期望风险则反映在整个特征空间不同的x取值的决策行动所带来的平均风险。,最小风险Bayes决策规则：,实施最小风险判决规则的步骤如下： 在给定样本x条件下，计算各类后验概率,2.按照(2.3-1)式求各种判决的条件平均风险,为此，需要知道风险矩阵。 按照(2.3-2）式，比较各种判决的条件平均风险， 把样本x归属于条件平均风险最小的那一种判决。,二类问题：把x归于1时风险： 把x归于2时风险：,三、在一类错误率固定使另一类错误率最小的判别准则（聂曼-皮尔逊判决neyman-pearson）,例：两类的模式分布为二维正态 协方差矩阵为单位矩阵1=2=I，设20.09求聂曼皮尔逊准则 T. 解：,所以此时聂曼皮尔逊分类器的分界线为：,由图可知为保证2足够小，边界应向1一侧靠， 则1,T与2的关系表如右：,四、最大最小判别准则 前边的讨论都是假定先验概率不变，现在讨论在P(i)变化时如何使最大可能风险最小，先验概率P(1)与风险R间的变化关系如下：,这样，就得出最小风险与先验概率的关系曲线，如图所示：,讨论：,上式证明，所选的判别边界，使两类的概率相等：,这时可使最大可能的风险为最小，这时先验概率变化，其风险不变,五、序贯分类 迄今为止所讨论的分类问题，关于待分类样本的所有信息都是一次性提供的。但是，在许多实际问题中，观察实际上是序贯的。随着时间的推移可以得到越来越多的信息。 假设对样品进行第 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 ，再重复上面的判决，直到所有的样品分类完毕为止。 这样做的好处是使那些在二类边界附近的样本不会因某种偶然的微小变化而误判，当然这是以多次观察为代价的。,由最小错误概率的Bayes 判决，对于两类问题，似然比为,现在来确定A、B的值。 因为,序贯分类决策规则：,上下门限A、B是由设计给定的错误概率P1(e), P2(e)来确定的，Wald 已证明，观察次数不会很大，它收敛的很快。,2-3 正态分布时的统计决策理论 为什么采用正态分布： a、物理上的合理性：正态分布在物理上是合理的、广泛的。 b、数学上的简单性：正态分布数学上简单, N(,) 只有均值和方差两个参数。 一、正态分布概率密度函数的定义及性质,1单变量正态分布 定义：,2、（多变量）多维正态分布 （1）函数形式：,其中,为边缘分布，,而：,协方差矩阵：,、不相关性等价于独立性。若xi与xj互不相关,则xi与xj一定独立。 、线性变换的正态性Y=AX，A为线性变换矩阵。若X为正态分布，则Y也是正态分布。 、线性组合的正态性。,(2)、性质： 、与对分布起决定作用P(x)=N(, ), 由n个分量组成，由n(n+1)/2元素组成。多维正态分布由n+n(n+1)/2个参数组成。 、等密度点的轨迹是一个超椭球面。区域中心由决定，区域形状由决定。,边缘分布与条件分布的正态性 不难证明正态随机向量的边缘分布与条件分布仍服从正态分布。,判别函数：类条件概率密度用正态来表示：,决策面方程：,二、多元正态概率型下最小错误率Bayes分类 从最小错误率这个角度来分析Bayes 分类器 1.第一种情况：各个特征统计独立，且同方差情况。(最简单情况),判别函数：,如果M类先验概率相等：,最小距离分类器：未知x与i相减，找最近的i把x归类,讨论：,讨论：,2、第二种情况： i 相等，即各类协方差相等。,未知x，把x与各类均值相减，把x归于最近一类。最小距离分类器。,讨论：针对1，2二类情况，如图：,3、第三种情况(一般情况)：为任意，各类协方差矩阵不等，二次项xT x与i有关。所以判别函数为二次型函数。,判别函数：,决策规则：,2-4 关于分类器的错误率分析 1、一般错误率分析：,2、正态分布最小错误率(在正态分布情况下求最小错误率),2-5 Bayes分类的算法（假定各类样本服从正态分布） 1.输入类数M；特征数n，待分样本数m. 2.输入训练样本数N和训练集资料矩阵X(Nn)。并计算有关参数。 3.计算矩阵y中各类的后验概率。 4.若按最小错误率原则分类，则可根据 3 的结果判定y中各类样本的类别。 5.若按最小风险原则分类，则输入各值，并计算y中各样本属于各类时的风险并判定各样本类别。,例1、有训练集资料矩阵如下表所示，现已知，N=9、N1=5、N2=4、n=2、M=2，试问，X=(0,0)T应属于哪一类？ 解1：假定二类协方差 矩阵不等（12） 则均值:,解2、假定两类协方差矩阵相等=1+2,解1、假定三类协方差不等；,例2：有训练集资料矩阵如下表所示，现已知， N=9、N1=N2=3、 n=2、M=3，试问，未知样本 X=(0,0)T应属于哪一类？,可得三类分界线如图所示：,解2、设三类协方差矩阵相等,可得三类分界线如图所示：,作业：在下列条件下，求待定样本x=(2,0)T的类别，画出分界线，编程上机。 1、二类协方差相等，2、二类协方差不等。,作业：有训练集资料矩阵如下表所示，现已知， N=9、N1=N2= N3=3、n=2、M=3，试问，X=(-2,2)T应属于哪一类？,要求：用两种解法a、三类协方差不等；b、三类协方差相等。 编程上机，画出三类的分界线。,4-8 决策树多峰情况 Bayes分类器只能适用于样本分布呈单峰情况，对多峰情况则不行。 若用决策树，可进行如下步骤分类,整个分类过程可用右图的树表示: 1、基本概念 （1）决策树：二叉树。每个节点都是两类分类器。例如；节点a上的决策规则为： （2）代价（损失）矩阵 定义节点L的代价为：,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的代价和 其中， 为一经验因子，用以防止无限分割下去,只要经