模式识别导论(四)_第1页
模式识别导论(四)_第2页
模式识别导论(四)_第3页
模式识别导论(四)_第4页
模式识别导论(四)_第5页
已阅读5页,还剩52页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第四章 贝叶斯决策理论 贝叶斯分类器 正态分布决策理论 关于分类的错误率分析 最小风险Bayes分类器 Bayes分类器算法和例题 聂曼皮尔逊判别准则 最大最小判别准则 决策树 序贯分类v 对x再观察:有细胞光密度特征 ,有类条件概率密度: P(x/ ) =1,2,。如图所示v 利用贝叶斯公式利用贝叶斯公式 : 通过 对细胞的再观察,就可以把先验概率转化为后验概率,利用后验概率可对未知细胞x进行识别 。 第四章第四章 贝叶斯决策理论贝叶斯决策理论v 4-1 Bayes分类器分类器最优分类器、最佳分类器一、两类问题例如:细胞识别问题 1正常细胞,2异常细胞某地区,经大量统计获先验概率P(1),P

2、(2)。若取该地区某人细胞x属何种细胞 ,只能由 先验概率决定。这种分类器决策无意义221121),()(),()(xPPxPP,(也称为后验概率)21)()()()()(jjjiiiPxPPxPxP)(1xP)(2xPx条件概率密度分布)(ixP221121),()(),()(xxPxPxxPxP则若则若 设N个样本分为两类1,2。每个样本抽出n个特征, x =(x1, x2, x3, xn)Tv 通过 对细胞的再观察,就可以把先验概率转化为后验概率,利用后验概率可对未知细胞x进行识别 。 1、判别函数:若已知先验概率P(1),P(2),类条件概率密度P(x/ 1), P(x/ 2)。 则可

3、得贝叶斯判别函数四种形式 :)()()(21xgxgxg)(1xP)(2xPx2 . 04 . 06 . 08 . 00 . 1后验概率分布)(xPi2、决策规则:)( ,)()(ln)()(ln)() 4()( ,)()()()()() 3 ()(),()()()()() 2()(),()()() 1 (12211221221121取对数方法似然比形式类条件概率密度后验概率PPxPxPxgPPxPxPxgPxPPxPxgxPxPxg2112212112212122112121)()(ln)()(ln)()4()()()()()3()()()()()2()()()1 (xPPxPxPxgxPP

4、xPxPxPxPPxPxxPxP 3、决策面方程: x为一维时,决策面为一点,x为二维时决策面为曲线,x为三维时,决策面为曲面,x大于三维时决策面为超曲面。v 例例:某地区细胞识别; P(1)=0.9, P(2)=0.1 未知细胞x,先从类条件概率密度分布曲线上查到:v 解解:该细胞属于正常细胞还是异常细胞,先计算后验概率:0)(xgP(x/ 1)=0.2, P(x/ 2)=0.4.),()(),()(,182. 0)(1)(818. 01 . 04 . 09 . 02 . 09 . 02 . 0)()()()()(211211221111用所以先验概率起很大作因为属正常细胞。因为PPxxPx

5、PxPxPPxPPxPxPjjjg(x)nxxxX.21特征向量判别计算决策21x阈值单元 4、分类器设计: 二、多类情况:=(1,2,m),x=(x1,x2,xn) 1.判别函数:M类有M个判别函数g1(x), g2(x), gm(x).每个判别函数有上面的四种形式。 2.决策规则:),.,2, 1( ,)()(max)()()(1MixPxPPxPxgijjMjiiiiijMjiiixPxPPxPxg)(ln)(lnmax)(ln)(ln)(1另一种形式:3、决策面方程:4、分类器设计:0)()(),()(xgxgxgxgjiji即g1(x)max(g(x)nxxxX.21特征向量判别计算

6、决策ixg2(x)gn(x)最大值选择器.v4-2 正态分布决策理论正态分布决策理论 一、正态分布判别函数 1、为什么采用正态分布: a、正态分布在物理上是合理的、广泛的。 b、正态分布数学上简单,N(, ) 只有均值和方差两个参数。 2、单变量正态分布: )()()(,)()(:),(21exp21)(22222方差,均值或数学期望其中dxxPxxEdxxxPxENxxP1)()( , 0)(dxxPxxP列关系:概率密度函数应满足下)(xPX2295.013、(多变量)多维正态分布 (1)函数形式:的行列式为的逆阵,为维协方差矩阵,为维均值向量,维特征向量其中121211212),.,(,

7、.,:21exp21)(nnnnxxxxxxxPTnTnTniiiiidxxPxxE)()(nnnnnnnnnnnnTxxxxxxxxExxxxExxE.,.,.111111111111是协方差,非对角线是方差对角线jijixxExxExxExxEijijnnnnnnnnnnnnn22222212121221111111111,.(2)、性质: 与对分布起决定作用P()=N(, ), 由n个分量组成,由n2元素组成。多维正态分布由n+n2个参数组成。 等密度点的轨迹是一个超椭球面。区域中心由决定,区域形状由决定。 不相关性等价于独立性。若xi与xj互不相关,则xi与xj一定独立。 线性变换的正

8、态性Y=AX,A为线性变换矩阵。若X为正态分布,则Y也是正态分布。 线性组合的正态性。211X2X 判别函数:类条件概率密度用正态来表示:112211221()ln()()11ln(exp()2211lnexpln()2211ln 2lnln()222iiiTiiiiniTiiiiniTiiiiigxPxPxxPxxPnxxP 二、最小错误率(Bayes)分类器:从最小错误率这个角度来分析Bayes 分类器 1.第一种情况:第一种情况:各个特征统计独立,且同方差情况。(最简单情况) 决策面方程:()()0ijgxgx111()()2() lnln0()ijiijjijijjgxgxxxxxiP

9、P iTiiiiiiiTiiiiiiiiiTiixxxPxPxxxginIIIPnxxxg222121221),(ln2)(ln21)(2ln2,1,)(lnln212ln221)(其中对分类无影响。无关。都与因为1222()().()(), ()2miiPPPxgx欧 氏 距 离零。,只有方差,协方差为即22112.0.0.:nniI判别函数: 最小距离分类器:未知x与i相减,找最近的i把x归类v如果m类先验概率相等 00220012,( ),()11,ln()22( )maxTTTTiiiiiTiiiTiiiiiiTTiiijjij mxxx xxx xigxw xwwwPgxw xww

10、xwx 因为二次项与 无关简化可得:线性判别函数其中:判别规则:)()(ln)(210)(0)()(200jijijijijijiPPxWxxWxgxg其中决策面方程:21112111222222( )( )( )()11()()ln02()TTTg xgxgxPxxP对于二类情况讨论:201212( ),( )()0()iijaIbWxxHWWWH因为协方差为零。所以等概率面是一个圆形。因与点积为 ,因此分界面 与垂直又因为,所以与同相同方向决策面 垂直于 的联线。12(,) 二类情况下12( )()(),( )cPPHHd如果先验概率相等通过 联线的中点。否则离开先验概率大的一类。多类情况

11、,用各类的均值联线的垂直线作为界面。12WH时决策面)()(21PP124334H23H14H12H1121x2xHW20 x)()()(21)()(.)()()()(ln)()(21)(.21321121马氏距离,若先验概率相等无关与因为rxxxgPPPPPxxxgiiTiiiiiTiiM 未知x,把x与各类均值相减,把x归于最近一类。最小距离分类器。)(ln21,)()()(101011iiTiiiiiTiiTiTiPwWwxWxgixxxx其中(线性函数)无关。与展开;把 2、第二种情况:、第二种情况:i 相等,即各类协方差相等。)()()()()(ln)(21)(, 0)(1010ji

12、TjijijijijiTPPxWxxW。其中00112121111112222( )max( )( )( )()()1()ln02()( )( )0TTiiijjij mTTijijg xW xwW xwxg xgxg xxPxPg xgx 决策规则:对于二类情况决策界面:若与相邻 讨论:针对1,2二类情况,如图:200010( ),( )()0,()( )(),();1( )(),;2iiijijijaIbWxxWxxHxcWWHdxHH因为所以等概率面是椭圆,长轴由本征值决定因为与点积为所以与正交,通过 点。因为所以与不同相不垂直于 值联线。若各类先验概率相等,则则通过均值联线中点否则离开

13、先验概率大的一类。1121x2xHW20 x 3、第三种情况、第三种情况(一般情况):为任意,各类协方差矩阵不等,二次项xT -1x与i有关。所以判别函数为二次型函数。001( )maxTTiiiiTTjjjij mg xx W x W xwx W x W xwx 决策规则:对于二类情况)(lnln2121)()( ,21,)(:10110iiiiTiiiiiiiiTiiTiPwnWnnWwxWxWxxg,维列向量矩阵其中判别函数112111122211122211( )( )( )()()()()22()1ln ln02()TTg xgxg xxxxxPxP圆)(a1x2x12双曲线)(d1

14、22椭圆)(b21抛物线)(c1212先验概率相等。为条件独立;二类情况对于二类问题,条件:各种图形:下面看一下决策界面的决策面方程::0)()(2121cxxbaxgxgji直线)(e2211v4-3 关于分类器的错误率分析关于分类器的错误率分析 1、一般错误率分析、一般错误率分析:21121221121122112211()(),().(),()(),( )()( )()( )()( )()( )()( )() ()RRRPxPxxPxPxxP e xPxxP eP e x dxeP xdxeP xdxP ePePePP x 二类问题:若则这时错误率为当这时错误率最小。当平均错误率:第一类

15、判错概率:第二类判错概率:总错误率:21221122min2211() ()() ()() ()( )() ()() ()TTRYYdxPP xdxPP xPP xP ePP xdxPP xdx使错误率最小条件:(证明略))()(11PxP)()(22PxPTY1R2R1Y计算量很大)总错误率对于多类问题:)()()()(.)()(.)()(.)()()()(.)()()(11121222321111312iMiMjjjMMMMMMMPRxPPRxPRxPRxPPRxPRxPRxPPRxPRxPRxPePijMiiRiMiiiidxPxPPRxPMPi11)()()()()(用平均正确分类概率

16、:,计算相对简单。错误率:)(1)(MPeP2、正态分布最小错误率、正态分布最小错误率(在正态分布情况下求最小错误率)21)()(21PP设:)(21exp21)()(21exp21)(2211BxxPAxxP率。因此可计算出最小错误可以计算若已知错误率最小对多维问题:可计算可以计算若已知,其中:。可得代入把值值就是,可解出条件:把上式代入最小错误率.,)(21,21exp21)(,)(,)()(,2121exp21)()()()()()()(.)()()()(21211212min222111min212221122211minmin2211kkduuePNxPNxPePkkxuduudxx

17、PPdxxPPePePePYYxxPPxPPTkkYYTTTTv4-4 最小风险最小风险Bayes分类器分类器 假定要判断某人是正常(1)还是肺病患者(2),于是在判断中可能出现以下情况:第一类,判对(正常正常) 11 ;第二类,判错(正常肺病) 21 ; 第三类,判对(肺病肺病) 22;第四类,判错(肺病正常) 12 。 在判断时,除了能做出“是” i类或“不是” i类的动作以外,还可以做出“拒识”的动作。为了更好地研究最小风险分类器,我们先说明几个概念: 在整个特征空间中定义期望风险, 期望风险: ).(,.,2 , 1,1MaaixPExRjMjjijii )( , 平均风险dxxPxx

18、RR行动i:表示把模式x判决为i类的一次动作。 损耗函数ii=(i/i)表示模式X本来属于i类而错判为i所受损失。因为这是正确判决,故损失最小。 损耗函数ij=(i/j)表示模式X本来属于j类错判为i所受损失。因为这是错误判决,故损失最大。 风险R(期望损失):对未知x采取一个判决行动(x)所付出的代价(损耗) 条件风险(也叫条件期望损失):条件风险只反映对某x取值的决策行动i所带来的风险。期望风险则反映在整个特征空间不同的x取值的决策行动所带来的平均风险。 最小风险Bayes决策规则:kiMikxxRxR则若,min,.,2 , 1 二类问题:把x归于1时风险: 把x归于2时风险:12121

19、11221221221112212211()0.9,()0.1,()0.2,()0.40,6,1,0()0.818,()0.182()()()1.092()()0.818jjjPPP xP xPxPxRxPxPxRxPx例:已知正常细胞先验概率为异常为从类条件概率密度分布曲线上查的,由上例中计算出的后验概率:条件风险:因为12112()(),6RxRxx 异常细胞 因决策类风险大。因 较大,决策损失起决定作用。)()()()()()(22212122121111xPxPxRxPxPxR分类器。这时便得到最小错误率最大,最小,就相当于后验概率时时函数用最小风险分类规则:)()()(1)()()(

20、)()(, 1, 0)(:10)()()()()(1121221211121121xPxRxPxPxPxPxRjijixxPxxRxRiiijjjijijijjMiiijjjv4-5 Bayes分类的算法分类的算法(假定各类样本服从正态分布)v1.输入类数M;特征数n,待分样本数m.v2.输入训练样本数N和训练集资料矩阵X(Nn)。并计算有关参数。v3.计算矩阵y中各类的后验概率。v4.若按最小错误率原则分类,则可根据 3 的结果判定y中各类样本的类别。v5.若按最小风险原则分类,则输入各值,并计算y中各样本属于各类时的风险并判定各样本类别。v 例例1、有训练集资料矩阵如下表所示,现已知,N=

21、9、N1=5、N2=4、n=2、M=2,试问,X=(0,0)T应属于哪一类?v解解1、假定二类协方差 矩阵不等(12) 则均值:53, 0) 11011 (511211XX训练样本号k 1 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方法)的计算请看协方差协方差矩阵为1122211211212221212111(,410032,103001:.)47, 0(,)53, 0(,CCCCXXXXXXTTTT计算方法同上)协方差矩阵为(410032,103001103)( )(410)( )(411)

22、01()01()00()01 ()01 (41)()(15121122511222221121225111112222221115111111TkkkTkkkkkTkxxxxCCCxxxxCxxxxC223. 0)()(ln,94)(,95)(:59. 0ln,61,103,40023,310001212121211211PPPP先验概率188.12)5 .13(81.14091.101832210)()0 , 0(091.10)()0 , 0(),(x,),(x0)()(lnln21)xx()xx(21)xx()xx(21)()()(22222122221121212121211222111

23、112xxxxxxgXxgxxxxxPPxgxgxgTTTTTT程:这是一个非线性椭圆方得分界线方程为:令类。属于所以判代入得:将利用公式:1X2X12待定样本11211两种解得分界线62. 0.61. 0068. 21147)()0 , 0(x068. 2)()(ln)xxxx(21x)xx()(221211212111112所示为一直线,如图中虚线从而得分界线方程为类,判为故应把xxxgPPxgTTTT1X2X12待定样本11211两种解得分界线得:所以代入Tx0 , 0,11200053,20110035121 v 解解2、假定两类协方差矩阵相等=1+2训练样本号k1 2 31 2 31

24、 2 3特征 x10 1 2-2 -1 -2 0 1 -1特征 x21 0 -1 1 0 -1 -1 -2 -2类别123v 解解1、假定三类协方差不等;v例例2:有训练集资料矩阵如下表所示,现已知, N=9、N1=N2=3、n=2、M=3,试问,未知样本 X=(0,0)T应属于哪一类?3213213100110031,1001:)35, 0(x)0 ,35(x,)0 , 1 (x,协方差矩阵为,均值TTT300110031001131211,所以6 . 3)()(, 5 . 0)(:0 , 02 . 710321)(2 . 710321)(1221)(.lnln2121,21,)(31313

25、11321222213122212122211111321321xgxgxgXxxxxgxxxxgxxxxgPwwWwxwxWxxgPPPTiiiiTiioiiiiiioTiiTi代入得将所以其中代入多类判别函数先验概率,12X321X待定样品353511x3x2x06.252)()(055)()(01.36)()()()(),()(),()(0,021221321222132121211332211xxxxgxgxxxxxgxgxxxgxgxgxgxgxgxgxgXT分别令类为故应判样品12X321X待定样品353511x3x2xv 可得三类分界线如图所示:可得三类分界线如图所示:4225)

26、()(,143)(:0 , 0422575)(422575)(,14373)()(:730073,37003732123121101321 xgxgxgXxxgxxgxxgwxwxgTiTii代入得将所以代入多类时判别函数 解解2、设三类协方差矩阵相等12X321X待定样品353511x3x2x2187573)()(7575)()(21878)()()()(),()(),()(0,0211321321211332211xxxgxgxxxgxgxxgxgxgxgxgxgxgxgXT分别令类为故应判样品v 可得三类分界线如图所示:可得三类分界线如图所示:v作业:作业:在下列条件下,求待定样本x=(

27、2,0)T的类别,画出分界线,编程上机。v 1、二类协方差相等,2、二类协方差不等。训练样本号k1 2 31 2 3特征x11 1 2-1 -1 -2特征x21 0 -11 0 -1类别 1 2v 作业作业:有训练集资料矩阵如下表所示,现已知, N=9、N1=N2= N3=3、n=2、M=3,试问,X=(-2,2)T应属于哪一类? 要求:要求:用两种解法a、三类协方差不等;b、三类协方差相等。 编程上机,画出三类的分界线。训练样本号k 1 2 31 2 3 1 2 3特征x10 2 1-1 -2 -2 0 0 1特征x20 1 0 1 0 -1 -2 -1 -2类别12321211122211

28、12222011212,P xdxP xdxrTP xdxTP xdxT为判为的错误率为判为的错误率 如图所示:,聂曼皮尔逊准则是在取为常数时使最小,要满足以上条件 先定义一个辅助常数:其中: 为待定常数v4-6 在一类错误率固定使另一类错误率最小的判在一类错误率固定使另一类错误率最小的判别准则别准则(聂曼-皮尔逊判决neyman-pearson))(1xP)(2xP12X1X12dxxPdxxPxxTxPxPxPxTPrdxxPxTPrdxxPdxxP211122211121121112111),(.,11同理:类属于区域在即区域内应使在应使积分为负最小为变量,要使式中,因为.)()(.()

29、()(,)()(121212221211TxTxPxPxTxPxPdxxTPxPr值皮尔逊规则归结为找阈得到判决准则根据两个不等式,我们区域)在v例例:两类的模式分布为二维正态 协方差矩阵为单位矩阵1=2=I,设20.09求聂曼皮尔逊准则 T.v 解:解:最小一定这时可确定,为常数时,的函数在取为的分界线作时当1222222121,)(.,)()(TTdxxPTTxPxPTTT0 , 1,0 , 121 22exp212exp21)(21exp212exp21)(22212222221111xxxxxPxxxxxPTT同理:所以因为是两类正态如图所示:时为最小错误率小但大小大但小大如图所示:的

30、不同直线。判别边界是平行于对于不同式有了判别边界和判别形即判别式为:判别边界为:如右图所示.1,;,ln212exp2exp2exp)()(:121222112111121TTTxTxTxxTxxTTxxPxP42 12141111x2x12345. 07 . 0345. 07 . 0v所以此时聂曼皮尔逊分类器的分界线为:2111345. 0,69. 02lnln,ln21xxTTx所以因为v由图可知为保证2足够小,边界应向1一侧靠,则1v T与2的关系表如右:最小的判别规则。时使这就是在给定最小上式使此时判别式为:由表查得给定12122121209. 0,2)()(209. 0 xTxPxP

31、T的关系表与2TT 4 2 1 20.04 0.09 0.16 0.25 0.38v4-7最大最小判别准则最大最小判别准则:前边的讨论都是假定先验概率不变,现在讨论在P(i)变化时如何使最大可能风险最小,先验概率P(1)与风险R间的变化关系如下: .)(,11)(12122212111212211122212221121222211212212111121122122121的线性函数就是被确定,风险一旦,对二类情况有:关系:与风险PRdxxPdxxPPdxxPRdxxPdxxPPPdxxPPxPPdxxPPxPPdxxPxxRdxxPxxRdxxPxxRRPRi 122222121112122

32、1122212221dxxPdxxPbdxxPabPaR其中:)(1xP)(2xP12X1X12 这样,就得出最小风险与先验概率的关系曲线,如图所示: 讨论: 。使最大风险为不变,变化,则平行,与横坐标这时直线如图所示,这时候最大风险为最小即无关与使如果选择关系为一条曲线与选择不同时,当关系为直线关系与区间固定时,当a:0., 0,3;,2;,1112221222222121112122111211211121212RPPRdxxPaRdxxPdxxPPRbPRRPPR1PR固定21,*RA选择不同21,)(1*P1PR*RB)(1*P不变变化RP1 .,0. 0,21212112221121

33、12两类错误概率相等若选取损失为满足应该使边界所以在最大最小判别中ePePdxxPdxxPb上式证明,所选的判别边界,使两类的概率相等: ePeP21这时可使最大可能的风险为最小,这时先验概率变化,其风险不变。其判别规则为*121221*21211112()()1()If then()()() P xPP xPxv4-8 决策树决策树多峰情况多峰情况v Bayes分类器只能适用于样本分布呈单峰情况,对多峰情况则不行。v 若用决策树,可进行如下步骤分类 ExxFxxxxDxxxxBxxCxxxxAxxxxxx121212111211211111202,5),5(4,3;,32);4(),2(1否

34、则则若否则则转若否则则若否则则转若否则转则转若2XEFDCAB1X21112212x20 x11xv 整个分类过程可用右图的树表示:v 1、基本概念v (1)决策树:二叉树。每个节点都是两类分类器。例如;节点a上的决策规则为:v (2)代价(损失)矩阵定义节点L的代价为:cbxx202202xx202xx111xx111xx121xx121xx111xx121xx121xxABCDEFabc1j11222v 2、决策树的构造在构造决策树时,需要考虑以下问题:1)、如何判断一节点是否为叶子。如右图表示,假定A、B、C、D、E、F各包含50个样本,并有以下的代价矩阵v 对于节点a,可以作出以下两个

35、决策之一:v 决策1,a不再分割v 决策2,a分为两类v 决策1的代价为 A1(a)=Ca 节点a的代价v 决策2的代价为 A2(a)=(Cb+Cc) 节点b,c的代价和v 其中, 为一经验因子,用以防止无限分割下去上各类样本混淆程度表示在节点类的损失,误判为类原属于类样本数表示属于类样本数表示属于其中:LCrrrrCLijijjjLiiLijijjLiLL,202xx202xx111xx 111xx 121xx 121xx 111xx 121xx 121xx ABCDEFabc1j1122201010022211211v 只要经验因子2.25,便有A2(a) A1(a),因此取决策2的代价较

36、小,故应把分为两类。v 一般地决策代价为:2)、选择节点的分割方式: a、根据经验确定。例如,全部样本分为三类,其代价矩阵为200000450000101501501015015021212121211212212121ijijjcicijijjbibcbaaaaijijjaiaarrrrCCrrrrrrC分为两类不再分割树叶决策分类公式:,分为两类,不再分割LLALAPCCPCLARRLP122121,L1R2R050605001060100333231232221131211v b、根据对样本分布的了解试探确定。如右图所示,将a划分为b,c的方式有两种v c、根据聚类结果来划分。3)、如何确定各节点分类器。v原则:v 、分类器应尽量简单,因此,多采用线性分类器,v 、尽量减小分类时所使用的特征,选用最有效的特征进行分类2XEFDCAB1X21112212x20 x11x。原则划分作为另一类。根据这一类,而合为一,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论