模式识别第二章优秀PPT.ppt

模式识别第二章你现在浏览的是第一页，共109页贝叶斯决策理论贝叶斯决策理论 统计模式识别的统计模式识别的主要方法主要方法之一之一 随机模式随机模式分类方法的基础分类方法的基础 采用贝叶斯决策理论分类的采用贝叶斯决策理论分类的前提前提：目标（事物）的目标（事物）的观察值是随机的，服从一定的概观察值是随机的，服从一定的概 率分布。率分布。率分布。率分布。即：即：模式不是一个确定向量，模式不是一个确定向量，而是一个随机向量。而是一个随机向量。你现在浏览的是第二页，共109页用贝叶斯决策理论分类的用贝叶斯决策理论分类的要求要求：各类别总体各类别总体概率分布是已知概率分布是已知概率分布是已知概率分布是已知的的 P(wi)及及p(x/wi)已知，或已知，或P(wi/x)已知已知决策分类的决策分类的类别确定类别确定类别确定类别确定你现在浏览的是第三页，共109页特征向量、特征空间：特征向量、特征空间：设某个样本（模式），可用设某个样本（模式），可用d d个特征量个特征量x x1 1,x x2 2,x,xd d来刻化，即来刻化，即x=xx=x1 1,x,x2 2,x,xd d T T 表示样本的特征向量表示样本的特征向量特征空间：特征空间：这些特征的取值范围构成的这些特征的取值范围构成的d d维空间，维空间，为特征空间。为特征空间。每一个样本可看作每一个样本可看作d d维空间的维空间的向量或点向量或点特征向量特征向量:你现在浏览的是第四页，共109页相关统计量：相关统计量：nP(wP(wi i)类别类别w wi i出现的出现的先验概率先验概率n p p(x/w(x/wi i)类条件概率密度类条件概率密度，即类别状态为，即类别状态为w wi i类时，类时，出现模式出现模式x x的条件概率密度，也称的条件概率密度，也称似然函数似然函数。np p(x)(x)全概率密度全概率密度nP(wP(wi i/x)/x)后验概率后验概率，即给定输入模式，即给定输入模式x x时，该模式属于时，该模式属于w wi i类的条件概率。类的条件概率。nP(wP(wi i,x),x)联合概率联合概率 你现在浏览的是第五页，共109页n相互关系：相互关系：n n贝叶斯公式：贝叶斯公式：你现在浏览的是第六页，共109页需解决的问题：需解决的问题：设：样本集设：样本集X，有，有C类别，各类别状态为类别，各类别状态为wi，i=1,C。已知。已知P(wi)及及p(x/wi)要解决的问题是：要解决的问题是：要解决的问题是：要解决的问题是：当观察样本当观察样本x=xx=x1 1,x,x2 2,x,xd d T T 出现时，出现时，如何将如何将x x划归划归为某一类为某一类。你现在浏览的是第七页，共109页方法：方法：已知类别的已知类别的P(P(w wi i)及及x x的的p(x/p(x/w wi i)，利用贝叶斯公式，利用贝叶斯公式，可得类别的后验概率可得类别的后验概率P(P(w wi i/x)/x)再基于再基于最小错误概率准则、最小风险准则等最小错误概率准则、最小风险准则等最小错误概率准则、最小风险准则等最小错误概率准则、最小风险准则等，就可统计判决分类。就可统计判决分类。你现在浏览的是第八页，共109页2.2 2.2 几种常用的决策规则几种常用的决策规则1 1基于最小错误率的贝叶斯决策基于最小错误率的贝叶斯决策分类准则：分类准则：错误率最小错误率最小讨论讨论两类问题两类问题的决策：的决策：w w1 1,w,w2 2例如：癌细胞检查、产品质量等例如：癌细胞检查、产品质量等你现在浏览的是第九页，共109页合理决策依据：合理决策依据：根据后验概率决策根据后验概率决策 已知已知后验概率后验概率P(wP(w1 1|x),P(w|x),P(w2 2|x)|x)，决策规则决策规则：当当P(wP(w1 1|x)P(w|x)P(w2 2|x)x|x)x w w1 1，当当P(wP(w1 1|x)P(w|x)11,12 22下面给出下面给出 R与与P(w)的函数关系的函数关系:你现在浏览的是第五十一页，共109页平均风险（即总风险、也称期望风险）：平均风险（即总风险、也称期望风险）：根据根据R(R(i i/x)/x)定义定义及贝叶斯公式及贝叶斯公式 1 1的决策区域的决策区域 2 2的决策区域的决策区域（将（将 R R表示成表示成P(w)P(w)的函数）的函数）你现在浏览的是第五十二页，共109页利用利用 代入上式代入上式,整理得：整理得：其中：其中：目的：需要目的：需要分析平均风险分析平均风险R R与与P(wP(w1 1)的关系的关系用用P(wP(w1 1)表示表示平均风险平均风险R:R:你现在浏览的是第五十三页，共109页可见：可见：1）一旦决策区域一旦决策区域R1，R2确定确定，即即a,b为常数为常数，平均风，平均风险险R就是就是P(w1)的的线性函数线性函数线性函数线性函数；即；即P(w1)变化时，变化时，R1，R2不不作调整，则平均风险作调整，则平均风险R与与P(w1)呈呈线性关系。线性关系。2）P(w1)变化时，变化时，决策区域决策区域R1，R2划分也变化，即划分也变化，即a,b变化，变化，则平均风险则平均风险R与与P(w1)是非线性关系。是非线性关系。求求R与与P(w1)的关系曲线：的关系曲线：即即R=fP(w1)你现在浏览的是第五十四页，共109页先先取定取定P(wP(w1 1)求求R R P(wP(w1 1)曲线：曲线：按按最最小小风风险险贝贝叶叶斯斯决决策策确确定定分分类类面面，即即确确定定决决策策区区域域R1R1，R2R2利用上式求相应的利用上式求相应的最小风险最小风险R R*P(wP(w1 1)从从0 01 1取若干个值取若干个值，重复上述过程，得到，重复上述过程，得到R R*P P(w(w1 1)关系曲线关系曲线见图见图2.42.4你现在浏览的是第五十五页，共109页 R与与P(w1)是非线性关系是非线性关系，且曲线上，且曲线上R值都对应每个值都对应每个P(w1)值的值的最小风险损失最小风险损失。图中图中R*是当是当P(w1)P*(w1)时的最小风险值时的最小风险值。R=fP(w1)你现在浏览的是第五十六页，共109页 如果区域如果区域R1、R2确定（确定（a,b为常数），为常数），意味意味判别门限判别门限判别门限判别门限固定。当固定。当固定。当固定。当P(wP(w1 1)变化时，变化时，变化时，变化时，R R与与与与P(wP(w1)为线性关系。为线性关系。为线性关系。为线性关系。显然，显然，得不到最佳结果得不到最佳结果，因，因CD直线在曲线上方直线在曲线上方，且，且a R a+b这时这时R最大可能的风险值为最大可能的风险值为：R=a+b （图中（图中D点）点）不希望！不希望！见图中见图中CD直线直线你现在浏览的是第五十七页，共109页 取不同的固定门限，有不同直线，对应的取不同的固定门限，有不同直线，对应的R最最大值不同大值不同。直线。直线EF的最大值的最大值R=a+b P(w1)是不知或变化的，是不知或变化的，考虑如何使最大可能考虑如何使最大可能考虑如何使最大可能考虑如何使最大可能风险为最小风险为最小风险为最小风险为最小你现在浏览的是第五十八页，共109页 如果有某个如果有某个P(w1)，使最小风险决策得到的区域，使最小风险决策得到的区域R1、R2能能使使b=0，则，则 这时这时R与与P(w1 1)无关，即最大可能的风险达到最小无关，即最大可能的风险达到最小无关，即最大可能的风险达到最小无关，即最大可能的风险达到最小值为值为值为值为a a你现在浏览的是第五十九页，共109页1）以总风险）以总风险R对对P(w1)求极值求极值，即，即方法：方法：2）找出极值点找出极值点后，该点的切线就为水平线，后，该点的切线就为水平线，这时总风这时总风险险R与与P(w1)无关；无关；b=0b=0，意味，意味决策区域的划分使平均风险决策区域的划分使平均风险R达到曲线的极达到曲线的极大值大值（最小风险的极大值）。（最小风险的极大值）。由由2-34求导，得求导，得令其为令其为0，得极大值，得极大值，你现在浏览的是第六十页，共109页见图见图2-4b，当，当P(w1)=P*M(w1)时，时，R=R*M为最大值。为最大值。对应决策区域不变时，对应决策区域不变时，R与与P(w1)的关系为的关系为一条平行线一条平行线C D，即不管即不管P(w1)如何变化，风险不再变化如何变化，风险不再变化。使最大风险达到了最小化！使最大风险达到了最小化！使最大风险达到了最小化！使最大风险达到了最小化！你现在浏览的是第六十一页，共109页总结：当当P(w1)变化时，变化时，应选使风险应选使风险R达最大值（达最大值（b0）时的）时的P*(w1)来设计分类器来设计分类器。在这种分类决策区域，。在这种分类决策区域，能保证不管能保证不管P(w1)如何变化，最大风险为最小值如何变化，最大风险为最小值a。最小最大决策任务就是寻找最小最大决策任务就是寻找使使R最大时的决策域最大时的决策域R1，R2，即即求求b=0的决策域的决策域，由，由2-35求解。求解。你现在浏览的是第六十二页，共109页2.2.5 序贯分类方法序贯分类方法 实际中，为得到实际中，为得到x的的d个观测值，要个观测值，要花费代价花费代价。考虑每个特征值提取所花的代价，最优分类结果不一考虑每个特征值提取所花的代价，最优分类结果不一定将定将d个特征值全部使用；个特征值全部使用；另外，虽然特征数目增多，一般判决风险另外，虽然特征数目增多，一般判决风险R(i/x)降降低，但每个低，但每个特征值贡献不同。特征值贡献不同。排队从大排队从大小小，每投入一新特征，计算一次，每投入一新特征，计算一次R，同时，同时计算获取新特征应付出的代价与该特征对计算获取新特征应付出的代价与该特征对R的贡献之的贡献之和，和，比较后决定是否加入新特征。比较后决定是否加入新特征。序贯分类方法序贯分类方法你现在浏览的是第六十三页，共109页2.2.6 分类器设计分类器设计 c类分类决策问题：按决策规则把类分类决策问题：按决策规则把d维特征空间分维特征空间分为为c个决策区域。个决策区域。决策面：决策面：划分决策域的划分决策域的边界面边界面称为决策面。称为决策面。数学上用决策面方程表示。数学上用决策面方程表示。几个概念几个概念判别函数判别函数：表达决策规则的函数表达决策规则的函数，称为判别函数。，称为判别函数。你现在浏览的是第六十四页，共109页1）定义一组）定义一组判别函数判别函数根据根据决策规则决策规则若若 ，将将x归于归于wi 类类即即讨论具体的讨论具体的判别函数、决策面方程、分类器设计判别函数、决策面方程、分类器设计你现在浏览的是第六十五页，共109页例：基于最小错误率贝叶斯判决规则，显然其例：基于最小错误率贝叶斯判决规则，显然其 可可定义为：定义为：判别函数判别函数 有多种形式有多种形式你现在浏览的是第六十六页，共109页例：基于最小风险贝叶斯判决规则，判别函数例：基于最小风险贝叶斯判决规则，判别函数 可定义为：可定义为：显然，依据显然，依据最大值判别法最大值判别法，且，且 选择选择不是唯一不是唯一若将若将 都都乘以相同乘以相同的正常数或的正常数或加相同加相同的常量，的常量，不影响判决结果不影响判决结果你现在浏览的是第六十七页，共109页一般地一般地 是是单调递增函数单调递增函数，则分类结果不变，则分类结果不变 2）决策面方程决策面方程（即（即判决边界判决边界）若类型若类型wi与与wj的的 区域相邻，它们之间的决策面方程为区域相邻，它们之间的决策面方程为你现在浏览的是第六十八页，共109页图图2.5(a)2.5(a)为一维特征空间的三个决策区域（为一维特征空间的三个决策区域（d=1d=1），决），决策面为策面为分界点分界点；根据判决规则，建立分类器结构根据判决规则，建立分类器结构图图2.5(b)2.5(b)为二维特征空间的两个决策区域（为二维特征空间的两个决策区域（d=2d=2），决策），决策面为面为曲线曲线；三维特征空间，分界处是三维特征空间，分界处是曲面曲面；d d维特征空间，分界处是维特征空间，分界处是超曲面超曲面。你现在浏览的是第六十九页，共109页3）分类器设计分类器设计 （硬件软件）（硬件软件）功能：功能：先确定先确定选出选出判决判决你现在浏览的是第七十页，共109页g1(x)Maxg(x)g2(x)gn(x)例：图例：图2-6 分类器的组成分类器的组成d维空间维空间你现在浏览的是第七十一页，共109页再由结果的再由结果的正负作决策正负作决策，可简化设计。见图，可简化设计。见图2-7两类：求两类：求 最大值可转为将两个判别函数最大值可转为将两个判别函数相减相减，即定义一个即定义一个简单判别函数简单判别函数例例2.3g(x)阈值单元阈值单元你现在浏览的是第七十二页，共109页2.3 正态分布时的统计决策（研究正态分布时的统计决策（研究贝叶斯分类方法在正态分布中的应用）贝叶斯分类方法在正态分布中的应用）很多时候，正态分布模型是一个合理假设。很多时候，正态分布模型是一个合理假设。在特征空间中，某类样本较多分布在这类均值附近，在特征空间中，某类样本较多分布在这类均值附近，远离均值的样本较少，一般用远离均值的样本较少，一般用正态分布正态分布模型是合理的。模型是合理的。a、正态分布在、正态分布在物理上是合理的、广泛的物理上是合理的、广泛的。b、正态分布、正态分布数学上简单数学上简单，N(,)只有均值和方差两个只有均值和方差两个参数参数研究的理由：研究的理由：你现在浏览的是第七十三页，共109页1.一维正态分布一维正态分布，见式见式243 （常见）（常见）你现在浏览的是第七十四页，共109页2.多维（多维（d维）随机向量维）随机向量x的正态分布的正态分布 由由多元联合概率密度多元联合概率密度描述描述其中：其中：d维特征向量维特征向量d维均值向量维均值向量且且：协方差矩阵，对称且有：协方差矩阵，对称且有 个独立元素个独立元素 你现在浏览的是第七十五页，共109页你现在浏览的是第七十六页，共109页1）参数参数、对分布起决定性作用对分布起决定性作用，即，即p(x)由由、确定，确定，记为记为N(,)，个独立元素确定。个独立元素确定。2）等密度点轨迹为超椭球面等密度点轨迹为超椭球面，区域中心，区域中心由由决定，区域形状由决定，区域形状由决定。决定。正态分布特点：正态分布特点：称为超椭球面称为超椭球面即等密度点满足即等密度点满足当指数项为常数时，当指数项为常数时，p(x)值不变值不变你现在浏览的是第七十七页，共109页在数理统计中在数理统计中被称为被称为马氏距离的平方马氏距离的平方（Mahalanobis）等密度点轨迹是等密度点轨迹是x到到u的马氏距离的马氏距离r为常数的超椭球面为常数的超椭球面，其大，其大小是样本对均值向量的小是样本对均值向量的离散度度量离散度度量。最小错误率贝最小错误率贝叶斯叶斯决策规则变为决策规则变为决策规则变为决策规则变为：若若 如果如果如果如果x x到期望向量到期望向量到期望向量到期望向量u ui i的马氏距离最小，则的马氏距离最小，则x w wi i你现在浏览的是第七十八页，共109页3）不相关性等价于独立性不相关性等价于独立性 对于正态分布的随机向量对于正态分布的随机向量x，若，若xi和和xj之间不相关，则它之间不相关，则它们一定互相独立们一定互相独立不相关：不相关：独独 立：立：推论：推论：是对角阵，是对角阵，xi i=1,d，互相独立，互相独立你现在浏览的是第七十九页，共109页5）线性变换的正态性线性变换的正态性Y=AX，A为线性变换矩阵。若为线性变换矩阵。若X为正态分布，则为正态分布，则Y也也是正态分布。是正态分布。即即则则4）边缘分布和条件分布仍是正态分布边缘分布和条件分布仍是正态分布例例是正态分布，则是正态分布，则是正态分布是正态分布也是正态分布也是正态分布你现在浏览的是第八十页，共109页 即：即：总可以找到一组坐标系，使变换到新坐标系的总可以找到一组坐标系，使变换到新坐标系的随机变量是独立的随机变量是独立的（重要！重要！）因此，总可以找到一个因此，总可以找到一个线性变换矩阵线性变换矩阵A，使使y的协方差的协方差阵阵A AT为对角尺寸为对角尺寸，这时，这时y的各分量之间独立的各分量之间独立。6）线性组合的正态性线性组合的正态性你现在浏览的是第八十一页，共109页2.3.2 正态分布下的最小错误率正态分布下的最小错误率贝叶斯判别函数和决策面贝叶斯判别函数和决策面 i=1,c其中其中1判别函数判别函数最小错误率判别函数是：最小错误率判别函数是：服从服从 你现在浏览的是第八十二页，共109页进行进行单调单调的的对数变换对数变换，则，则判别函数判别函数为：为：决策面是超二次曲面决策面是超二次曲面，如：超平面，超球面，超椭球面，如：超平面，超球面，超椭球面马氏距离的度量值马氏距离的度量值你现在浏览的是第八十三页，共109页2决策面方程决策面方程即：即：你现在浏览的是第八十四页，共109页3特殊情况特殊情况1）对所有类）对所有类即：各类协方差阵相等，且即：各类协方差阵相等，且都是对角矩阵都是对角矩阵。对角线对角线为为 2，非对角线为零，非对角线为零不影响分类，可忽略不影响分类，可忽略判别函数判别函数为：为：你现在浏览的是第八十五页，共109页则则判别函数变为判别函数变为：欧几里得距离平方，欧几里得距离平方，即欧氏距离平方即欧氏距离平方 得到得到欧氏距离的度量值欧氏距离的度量值，它是马氏距离度量的，它是马氏距离度量的一个特例。一个特例。即：等密度点是圆形即：等密度点是圆形你现在浏览的是第八十六页，共109页欧氏距离欧氏距离则则贝叶斯决策规则变为贝叶斯决策规则变为最小距离分类规则最小距离分类规则最小距离分类规则最小距离分类规则。最小距离分类法最小距离分类法：服从正态分布，各类协方差矩阵服从正态分布，各类协方差矩阵 且先验概率相等，则可执行最小距离分类法。且先验概率相等，则可执行最小距离分类法。其判别规则为其判别规则为：若若 ，则，则你现在浏览的是第八十七页，共109页即：即：计算样本计算样本x与与i的欧氏距离，找最近的的欧氏距离，找最近的i把把x归类归类 例：设一维特征空间（例：设一维特征空间（d=1）的样本分布）的样本分布 u1=55.28，u2=79.74若若 则则 否则否则你现在浏览的是第八十八页，共109页将将 展开得：展开得：则则判别函数：判别函数：其中其中 ，与分类无关，与分类无关，忽略忽略即：即：是是线性判别函数线性判别函数线性判别函数线性判别函数，称为线性分类器，称为线性分类器你现在浏览的是第八十九页，共109页对于两类情况：对于两类情况：你现在浏览的是第九十页，共109页决策面方程决策面方程：其中其中推出：推出：决策面是一个通过决策面是一个通过决策面是一个通过决策面是一个通过x x0 0，且与向量且与向量且与向量且与向量w w正交的超平面正交的超平面正交的超平面正交的超平面超平面方程超平面方程分类平面的法向量分类平面的法向量你现在浏览的是第九十一页，共109页讨论：讨论：（两类情况）（两类情况）你现在浏览的是第九十二页，共109页你现在浏览的是第九十三页，共109页2）i：仍是超平面，但不与 垂直 求样本求样本x x与各类均值的马氏距离，把与各类均值的马氏距离，把x x归于最近归于最近一类一类最小距离分类器。最小距离分类器。你现在浏览的是第九十四页，共109页决策规则：决策规则：将将进一步简化进一步简化你现在浏览的是第九十五页，共109页对于两类情况：你现在浏览的是第九十六页，共109页讨论：（针对1，2二类情况）你现在浏览的是第九十七页，共109页3、第三种情况、第三种情况(一般情况一般情况)：二次项二次项xTx与与i有关。有关。判别函数为二次型函数。判别函数为二次型函数。为任意，各类协方差矩阵不等。为任意，各类协方差矩阵不等。你现在浏览的是第九十八页，共109页总结：总结：最小错误率贝叶斯决策；最小错误率贝叶斯决策；1.分类法最小风险贝叶斯决策；最小风险贝叶斯决策；聂曼皮尔逊决策规则聂曼皮尔逊决策规则(N(NP P）（仅知道类概密时，可使用，针对两类）（仅知道类概密时，可使用，针对两类）最小最大决策最小最大决策（当（当不确切知道不确切知道P(wi)P(wi)，且在类别判决过程中，且在类别判决过程中，P(wi)P(wi)又是变化的又是变化的，易采用易采用，它使决策平均风险达极值，而换取的是分类过程，它使决策平均风险达极值，而换取的是分类过程中中最大平均风险达最小值，且不随最大平均风险达最小值，且不随p(wi)p(wi)变化）变化）。序贯分类方法序贯分类方法（观测的代价和风险都要考虑）你现在浏览的是第九十九页，共109页2.分类器设计：分类器设计：判决函数、决策面方程判决函数、决策面方程（判决的边界）（判决的边界）3.贝叶斯方法在正态分布中的应用贝叶斯方法在正态分布中的应用(2)导出了有关的判别函数、决策面方程，且当导出了有关的判别函数、决策面方程，且当 时，可用时，可用最小距离分类法。最小距离分类法。总之，正态分布具有总之，正态分布具有普遍性普遍性，数学上，数学上易计算易计算，广泛应用。广泛应用。(1)特性特性你现在浏览的是第一百页，共109页贝叶斯（贝叶斯（Bayes）分类的）分类的算法流程算法流程（假定各类样本服从（假定各类样本服从正态分布正态分布）1）输入类数）输入类数c；特征数；特征数d，待分样本数，待分样本数m2）输入训练样本数）输入训练样本数N和训练集资料矩阵和训练集资料矩阵X(Nd)。并计。并计算有关参数。算有关参数。3）计算待测样本集矩阵）计算待测样本集矩阵y中各类的中各类的后验概率后验概率。4）若按最小错误率原则分类，则可根据步骤）若按最小错误率原则分类，则可根据步骤3 的结果的结果判定样本集判定样本集y中各类样本的类别中各类样本的类别5）若按最小风险原则分类，则输入各值，并计算）若按最小风险原则分类，则输入各值，并计算y中各中各样本属于各类时的风险并判定各样本类别。样本属于各类时的风险并判定各样本类别。你现在浏览的是第一百零一页，共109页例：有训练集资料矩阵如下表所示，已知训练样本数例：有训练集资料矩阵如下表所示，已知训练样本数N=9、其中、其中N1=5、N2=4；d=2、c=2，试问，试问，x=(0,0)T应属于哪一类？应属于哪一类？训练样本号k1 2 3 4 5 1 2 3 4 特征 x1特征 x21 1 0 -1 -1 0 1 0 -1 0 1 1 1 0-1 -2 -2 -2类别1 2你现在浏览的是第一百零二页，共109页解：均值为解：均值为:你现在浏览的是第一百零三页，共109页你现在浏览的是第一百零四页，共109页你现在浏览的是第一百零五页，共109页你现在浏览的是第一百零六页，共109页你现在浏览的是第一百零七页，共109页1.在下列条件下，求待定样本在下列条件下，求待定样本x=(2,0)T的类别，画出的类别，画出分界线，编程上机。分界线，编程上机。（1）二类协方差相等，（）二类协方差相等，（2）二类协方差不等。）二类协方差不等。训练样本号k1 2 31 2 3特征x11 1 2-1 -1 -2特征x21 0 -11 0 -1类别 1 2补充补充作业作业习题：习题：2.23你现在浏览的是第一百零八页，共109页2 设以下模式类别具有正态概率密度函数：（设以下模式类别具有正态概率密度函数：（选作）选作）你现在浏览的是第一百零九页，共109页