基于决策理论分类器

第二章基于决策理论的分类器ClassifiersBased

on

Bayes

Decision

Theory§1

引言§2

Bayes决策理论最小错误率的最小风险的决策决策§3

Bayes分类器和判别函数§4

正态分布的Bayes决策§1引言模式识别是根据对象特征值将其分类。d个特征组成特征向量x=[x1,···,xd]T，生成d维特征空间，在特征空间一个x

称为一个模式样本。Bayes决策理论是用概率统计方法研究决策问题。⒈为什么可用Bayes决策理论分类？⑴样本的不确定性：①样本从总体中抽取，特征值都是随 量，在相同条件下重复观测取值不同，故x为随机向量。②特征选择的不完善引起的不确定性；③测量中有随机噪声存在。⑵另一方面从样本的可分性来看：当各类模式特征之间有明显的可分性时，可用直线或曲线(面)设计分类器，有较好的效果。当各类别之间出现 现象时，则分类

。这时需要采用统计方法，对模式样本的统计特性进行观测，分析属于哪一类的概率最大。此时要按照某种判据分类，如，分类错误发生的概率最小，或在最小风险下进行分类决策等。⒉三个重要的概率和概率密度先验概率、类条件概率密度函数、后验概率。⑴先验概率Pi由样本的先验知识得到先验概率，可从训练集样本中估算出来。例如，两类10个训练样本，属于1为个，属于2为个，则先验概率P1=0.2，P2=0.8。⑵类条件概率密度函数p(x|i)模式样本x在i类条件下，出现的概率密度分布函数。也称p(x|i)为i

关于x

的似然函数。在本章中均假设已知上述概率和概率密度函数。⑶后验概率P(i|x)定义为某个样本x,属于i

类的概率,i=1,···,c

。如果用先验概率P(i)来确定待分样本x的类别,依据显然是非常不充分的，须用类条件概率密度p(x|i)来修正。根据样本x

的先验概率和类条件概率密度函数p(x|i)用Bayes公式重新修正模式样本所属类的概率，称后验概率P(i|x)。3.用Bayes决策理论分类时要求：①各类总体的概率分布是已知的。②要决策的类别数c是一定的。p(

x

|

i

)P(i

)p(

x)§2 Bayes决策理论1.Bayes公式，也称Bayes法则已知：先验概率

P(i

),

类条件概率密度函数p(

x

|

i

)c其中，全概率密度p(x)

p(x

|

i)P(i)i

1i

|

x)

则后验概率为P(如果

P(1

x)

P(2如果

P(1

x)

P(2

x)，则x属于1类x)，则x属于2类2.Bayes分类规则：用后验概率分类两类(c

2)情况下类条件概率密度后验概率上图i,

j

1,2,,

c③

l(

x)

p(

x

1

)

P(2

)p(

x

2

)

P(1

)②

p(

x

|

1

)P(1

)

p(

x

|

2

)P(2

)①

P(1

|

x)

P(2

|

x)⑴两类情况下的Bayes分类规则的几种等价形式下述四种等价规则的决策：x

1，否则x

2j

1,,cP(i

|

x)

max

P(

j

|

x),

则x

i⑵多类问题的Bayes决策：21

2

P(

)

P(1

)

)

ln

p(

x

|

)

lnP(1

)统计学中

l(

x)称为似然比,

P(2

)

称为似然比阈值取h(x)

ln

l(x)④

h(

x)

ln[

l(

x)]

ln

p(

x

|

后验概率p(

x)Bayes

公式iip(

x

|

)P(

)iP(

|

x)3.

最小错误率的

Bayes

决策⑴为什么这样分类的结果平均错误率最小？在一维特征空间中，t

为两类的分界面分成两个区域R1和R2

，R1为(－∞,t)；R2为(t,∞)。R1区域所有x值：分类器判定属于1类；R2区域所有x值：分类器判定属于2类。判断错误的区域为阴影包围的面积。i,

j

1,2,,

cj

1,2,,c误差概率

P(e

ror

)

min[

P(i

|

x)]决策规则

P(i

|

x)

max

P(

j

|

x),

则x

ix0判定错误区域及错误率真实状态2，而把模式x判定属于1类真实状态1，而把模式x判定属于2类平均错误率P(e)决策规则实际上对每个x都使

p(e|x)取小者，移动决策面t都会使错误区域增大，因此平均错误率最小。

2

1

2P(

|

x)，当P(

|

x)

P(

|

x)P(e

|

x)

P(1

|

x)，当P(2

|

x)

P(1

|

x)2

2

1

11p(x

)dx2

1221RRP(e)

P(

)P

(e)

P(

)P

(e)p(x

)dx

P(

)P(e)

P(

)⑵错误率计算：多类时，特征空间分割成R1,···

Rc

，P(e)由c×(c-1)项组成，计算量大。用平均正确分类率P(c)计算只有c

项：c

cj

1

j

1

RiP(e)

1

P(c)P(c)

P(

x

Rj

|

j

)P(

j

)

p(

x

|

j

)P(

j

)dx例1：细胞识别已知：正常类P(1)＝0.9;

异常类P(2)＝0.1待识别细胞

x,

从类条件概率密度曲线上查得这种规则先验概率起决定作用。这里没有考虑错误分类带来的损失。x

1j

1P(2

|

x)

1－P(1

|

x)

0.182因此P(1

|

x)

0.818

P(2

|

x)

0.1822p(

x

|

1

)P(1

)p(x|1)＝0.2;

p(x|2)＝0.4解：利用Bayes公式分别计算1和2的后验概率1

0.818

p(

x

|

j

)P(

j

)P(

|

x)

4.最小风险的Bayes决策⑴把分类错误引起的“损失”加入到决策中去。决策论中：采取的决策称为动作，用ai表示；每个动作带来的损失，用表示。归纳数学符号：①

x是d维随机向量

x

[x

,

x

,，x

]T1

2

d②状态空间由c个自然状态(c类)组成

{1,2

,,c

}③决策空间A由a个决策ai组成,

i

1,2,,

c,

aA

{a1,

a2

,ac

,

aa

},

下标a

c

1(

决策)表示当真实状态为

j时，采取的决策为ai

的损失。④损失函数(ai

,

j

),

i

1,2,,

aj

1,2,,

c一般用决策表或损失矩阵表示上述三者关系。决策表表示各种状态下的决策损失，如下表：由于引入了“损失”的概念(即在错判时造成的损失)，不能只根据后验概率来决策，必须考虑所采取的决策是否使损失最小。对于给定的x，决策ai，可在c个(ai,j)中选一个，其相应的后验概率为P(j|x)。和在决策论中条件期望损失称为条件风险，即x被判为i类时损失的均值。由于x是随机向量的观察值，不同的x采取不同决策ai

，其条件风险的大小是不同的。i

1,2,,

ac此时的条件期望损失，即后验概率R(ai

x)

E[(ai

,

j

)]

(ai

,

j)P(

j

x)j

1决策a可看成随机向量x的函数，记为a(x)，它本身也是一个随

量。定义期望风险RR

R(a(x)

x)p(x)dxdx是d维特征空间的体积元，积分在整个特征空间。期望风险R反映对整个特征空间上所有x的取值都采取相应的决策a(x)所带来的平均风险；而条件风险

R(ai|x)只反映观察到某一x的条件下采取决策ai

所带来的风险。如果采取每个决策行动ai使条件风险R(ai|x)最小，则对所有的x作出决策时，其期望风险R也必然最小。这就是最小风险Bayes决策。即

R(ak

|

x)

min

R(ai

|

x),i1,2,,a则ak

就是最小风险Bayes决策。ci1,2,,a⑵最小风险的Bayes决策规则：如果

R(ak

|

x)

min

R(ai

|

x),

则对应的决策

a

ak最小风险Bayes决策可按下列步骤进行：①已知P(

j),

p(x

|

j),

根据待识别的x,

由Bayes公式，计算后验概率P(

j

|

x)；②利用决策表，计算出采取ai决策的条件风险R(ai

|

x)R(ai

|

x)

(ai

|

j

)P(

j

|

x),

i

1,2,,

ai1③上式得到的a个条件风险值R(ai

|

x),

i

1,2,,

a进行比较，找出使条件风险最小的决策ak如果只有两类的情况下R(a1

|

x)

11P(1

|

x)

12P(2

|

x)R(a2

|

x)

21P(1

|

x)

22P(2

|

x)这时最小风险的Bayes决策法则为：如果R(a1|x)<R(a2|x),则x的真实状态1,否则2。两类时最小风险Bayes决策规则的另两种形式：如果(21

11

)P(1

|

x)(12

22

)P(2

|

x)，则决策1；否则2则决策1；否则2P(2

)，P(1

)

22p(

x

2

)21

11如果

l(

x)

p(

x

1

)

12例2：条件同例1，利用决策表，按最小风险Bayes决策分类这里决策与例1结论相反为异常细胞。因损失起了主导作用。不易确定，要与有关 商定。

00.).)4|2|((,21

1

22

0P

2

x

182例1

得到后验概率：

P

1

x

)91((,

00.).11

0

12

6

p

x

2p

x

1已知：P

1

P

2x

12

P

2(||(x|)(1).)09221

j

P

j(|()|R

a2

x

21P

1(|x|(0).)

8181j

12

RR)x,xaa

所以x

2条件风险

R

a1

x

由于例3：现有两类问题，比较两种Bayes决策。已知：单个特征变量x为正态分布两类方差都为

2=1/2,

均值分别为

=

0,1即求：①若先验概率P(1)=P(2)=1/2，计算最小错误率情况下的阈值x0。②如果损失矩阵为12P(x

)

1p(x

)

1exp(x2

)

类条件概率密度函数exp((x

1)2

)0

0

0.5

1计算最小风险情况下的阈值x0。)

]

1

2

21

x

p(x)

exp[

(2①最小错误概率情况下阈值x0

(取对数运算)如果这两类不是等概率，

P(1)<P(2),阈值左移

也就是说扩大最大可能类的区域。可能性大的类可产生更小的误差。2exp(x2

)

exp((x

1)2

)0x

12

2

1

ln

2

1②最小风险情况下阈值x0exp(x2

)

2

exp((x

1)2

)0x阈值左移⑶

决策对x作出若此时各类判别。判别风险相同，即都为z，则则判别的条件为z

Raix

i=1,2,···,c。c在某些情况下 决策比错误判别风险要小。样本x在各种判别条件下的平均风险R(ai

|x)

(ai

|

j

)P(

j

|x),

i

1,2,,

ai1当i=c+1时，如果Racx

Raix

i=1,2,···,c则|(j|(|)x(P))xPxzc

c

z

j

1j

1c1

z

jx)表示对x采取决策i的条件错误概率。条件风险R(ai表示正确决策没有损失；错误决策损失均为1。c

P(

jcx)

P(

j

x)j

1j

icx)

(ai

,

j

)P(

jj

1i

j1,

i

j5.两种Bayes决策关系①多类问题中，若损失函数为0—1时i

j(a

,

)

0,i,

j

1,2ccc

P(

j

x)

min

P(

jj

1j

ij

1j

i使

R(ak

x)

min

R(ai

x)

的最小风险Bayes

决策等价于x)

最小错误概率Bayes

决策。i

1,,c

j

1j

ii

1,,c②两类问题中，若有12－22＝21－11即所谓对称损失函数的情况下，这时最小风险的Bayes决策和最小错误概率的Bayes决策方法相同。此外还有下列三种主要的决策方法：

－决策：两类模式中，一类错误率为常数，另一类错误率达到极小值时的决策。最大最小决策：考虑到先验概率有可能改变的分类方法。选择风险为最大时的P()来设计。序贯分类决策：考虑特征的获取要付出一定的代价。先用一部分特征来分类，逐步加入特征以减少分类损失。§3

Bayes分类器和判别函数c类的分类问题，就是按决策规则将d维特征空间划分为c个决策区域，其边界称为决策面，用决策面方程表示。用于表示决策规则的函数称为判别函数g(x)。c个类就有c个由d个特征组成的单值函数，即判别函数g(x)。1.Bayes决策中的判别函数gi(x)=P(i|x)最小错误概率的决策规则最小风险的决策规则gi(x)=

-R(ai|x)决策规则：

gi(x)

>

gj(x)

所有i≠j

则x∈i两类情况下，设最小错误率的Bayes决策规则的四种等价形式后验概率类条件概率密度函数与先验概率似然比似然比取对数多类情况下，设最小错误率的Bayes决策规则的四种等价形式2.决策面方程各决策域R被决策面所分割，这些决策面是特征空间中的点、直线、超曲面，相邻的两个决策域在决策面上其判别函数相等。决策面方程应满足gi

(x)

=

gj

(x)gij(x)

=

gi(x)－gj(x)=0i≠j且i与j为相邻的两类。一维、三类二维、二类只有两类的分界面：x为一维，决策面为一分界点；如图(a)x为二维，决策面为一曲线；如图(b)x为三维，决策面为一曲面；x为d维，决策面为一超曲面(b)3.分类器设计在d维特征空间内，划分为c个决策区域。⑴多类：根据各类训练集样本x计算得到c个判别函数gi，将待分样本计算gi，从中选择最大值作为类决策。分类器可看成由硬件或 组成的一个“机器”。x属ij

于，ii((j

))xg，xg对一切()i|

ln

Pxpxi

)g(①

i(|()x)Pxg②

i

Pxp((xii)g)()|③

i

()

ln如果

i每个类有一个判别函数。

三种形式的判别函数i

()xg：⑵两类：两类分类器可看作只是对x计算判别函数的一个

“机器”，根据计算结果的符号将x分类。设－1）③

g(

x)

ln

p(

x

|

1

)

ln

P(1

)p(

x

|

2

)

P(2

)决策规则如果

g(

x)

0，则x属于1

(设＋1)；否则（2判别函数g(x)g(

x)

g1

(

x)

g2

(

x)同样有三种形式：①

g(

x)

P(1

|

x)

P(2

|

x)②

g(

x)

p(

x

|

1

)P(1

)

p(

x

|

2

)P(2

)例4

对例1和例2分别列出判别函数和决策面方程例1.

判别函数决策面方程例2.判别函数g(

x)

R(a2

|

x)

R(a1

|

x)

21

P(1

|

x)

12

P(2

|

x)

21

p(

x

|

1

)P(1

)

22

p(

x

|

2

)P(2

)g(

x)

0.9

p(

x

|

1

)

0.6

p(

x

|

2

)决策面方程：g(x)

9

p(x

|

1)

6

p(x

|

2

)

0g(

x)

p(

x

|

1

)P(1

)

p(

x

|

2

)P(2

)g(

x)

0.9

p(

x

|

1

)

0.1p(

x

|

2

)g(x)

9

p(x

|

1)

p(x

|

2

)

0g(x)

0,§4

正态分布的Bayes决策大量随 量服从正态分布,

而且数学上容易处理,

因此以正态分布为例来说明。1.正态分布函数和性质⑴单变量的正态分布概率密度函数性质：p(x)由,

2确定。随量x

集中在均值附近,

其分散度正比于标准差, 95%样本落入|x

-|<2范围内。2

xp(

x)dx均值

E{x}exp[

1

(

x

)2

]p(

x)

2

12(

x

)

p(

x)dx2方差

记为p(x)~

N(,

2

)⑵多元(维)正态分布的概率密度函数方差，对角线上的元素2ii2ij22122122222112

2j j

E[(

xi

i

)(x

)]协方差,非对角线上的元素

22d

对称矩阵，并且正定1d

1

是的逆矩阵，

是的行列式

2

d1

2d

dd

d维随

量d维均值向量

d维d

的协方差矩阵x

xp)(TT

1d

/2)()(x

exp

)2(

],,[][1

d)([x(xET

])

xE1

d式中

xx]xT,,[1211/2⑶多元正态分布的性质：①参数

和

决定分布形状概率密度函数由d+d(d+1)/2个数目的参数唯一确定，其中d为均值数，d(d+1)/2为协方差数。通常记为p(x)~

N

(,)。②等概率密度点的轨迹为一超椭球面x大部分落在以均值向量为中心，大小由协方差矩阵确定的区域。指数项为常数的x点即为等概率密度。因此超椭球的方程应是(x

)T

1(x

)

k超椭球主轴方向由的本征向量确定，其长度与协方差矩阵的本征值平方根成正比。证明：中心移到坐标原点=0，xT

1

x

k，可用这约束条件构造Lagrange函数，求极值得到。L(

x,

)

xT

x

(

xT

1

x

k)xT

x

xT

1

x

k长度与

矩阵的本征值成比例。两边

xT②

x

1

x

0,(

)

x

0，主轴方向是矩阵的本征向量方向。x即①

x

1

x

0,

两边

超球体主轴的必要条件L

2

x

2

1

x

0在数理统计中，定义r

2

(x

)T

1(x

)称x到

的Mahalanobis(马氏)距离平方。所以等概率密度点的轨迹是x到μ的马氏距离为常数的超椭球面。③在正态分布中不相关性等价于独立性。若两个随

量xi和xj间对多元正态的任意两个分量xi和xj来说两者等价。ii如果xi和xj是统计独立，∑中xi

的方差

2,xi和xj

的ijj协方差

2,

则

2＝0,

∑为对角矩阵。则

x=(x1,···,xd)T各分量是相互独立的正态分布随 量。不相关性定义：独立性定义：

ExE

Exixj[ijx]][[]

(p(p),ipj)ix)j

(xxx

独立性条件更强④多元正态分布的边缘分布和条件分布具有正态性⑤线性变换的正态性：x为多元正态分布的随机向量，其均值向量为，协方差矩阵为。对x作线性变换，即y=

AxA为线性变换矩阵，且非奇异，变换后服从均值向量为A，协方差矩阵为A∑AT的多元正态分布。p(y)

~

N(A,

A∑AT)⑥线性组合的正态性x为多元分布的正态随机向量，则线性组合y=Tx是一维的正态随量,是与x同维向量p(y)~N(T,

T∑A)2.正态分布的最小错误率的Bayes分类条件概密函数2

221212

212121i

i

d

ln

2

1

ln

|

|

ln

P(

)Ti

iTi

i

ii

i

iig

(

x)

i|

ln

P(

)id

12T)

)

ii)

(

x

1iig

(

x)

((x

x

xx

x

ln

2

ln

|

判别函数gi

(

x)

ln[

p(

x

|

i

)P(i

)]

ln

p(

x

|

i

)

ln

P(i

)11T

1T

1i

1ci

E[(x

i

)(x

i)

]Ti

i

iiip(

x

|

)

21

11/

2T

1i

E(

x)exp[

(

x

)

(

x

)]2

d

/

2

决策面方程根据相邻的决策域在决策面上的判别函数相等，得到

gi

(

x)

g

j

(

x)

或

gi

(

x)

g

j

(

x)

0

i,

j相邻几种不同的情况：⑴

i=

⑵

i＝i

=1,

2,···,c⑶

i≠j

i,

j

=1,

2,···,c2 |

j

|下面P(

j

)

1

ln

|

i

|

ln

P(i

)

0)]21T

1jjT

1)

(

x

ji

i

i)

(

x

)

(

x

即

[(x

⑴

i=

各类模式分布的协方差矩阵相等，各xi统计独立且方差相同，协方差均为0。几何上相当于各类样本落在以i为中心同样大小的一些超球体中。判别函数中第二和第三项与类别i无关若c类先验概率相等，则gi(x)可忽略最后一项。

2

2

0

0

2

2||

x

||2gi

(

x)

i

ln

P(i

)2dTi

i

i)

(

x

||

x

||

(

x

)

(

x

)2j

ijj

1

12ln

221iiln

|

|

ln

P(

)Ti(

x

)

)

)

1iiig

(

x)

((x

d22,

I

/

2d

1i

i欧氏距离平方：Bayes

决策：①

P(i)=

P(j)先验概率相等测量从待分类向量x到每一类均值向量的欧氏距i

是从训练样本集中得到的。也称最小距离分类器。若把每个均值向量i看作一个典型的样本(模板)，则这种分类方法也称为模板匹配技术。②

P(i)≠P(j)欧氏距离的平方必须用方差2

规范化后减去

lnP(i)再用于分类。因此，如果待分类的向量x同两类均值向量的欧氏距离相等，则最小错误概率Bayes决策把这模式归入先验概率大的那类。2离，把x分到距离最近的类，minix

i

1,,c实际使用中不必计算欧氏距离，把gi(x)展开可得这是x的二次函数，其中xT

x与分类无关这是与均值有关的线性判别函数，组成线性分类器。对待分类的样本x,分别计算gi(x),i=1,2,···,cgk(x)＝max

gi(x)

则决策ix∈k12

2(

xT

x

2

T

x

T

)

ln

P(

)i

i

i

iig

(

x)

i

0(2T

x

T

)

ln

P(

)

W

T

x

wi

i

i

i

i12

2ig

(

x)

2

21gi

(

x)

Wi

x

wTi

0i

i

0Ti

i

i

ln

P(

)i

2其中W

1

,

w

决策面方程相邻决策面方程是由上述线性方程所确定的一个超平面，且 的是方差相等，协方差为0这样一种特殊情况，即。这个方程确定了决策面是通过x0并正交于向量W的一个超平面。由于W=i－j所以超平面正交于均值向量i与j之间的联线。ln

i

P

)(i

j

)i

j

||||

P

j

)(i

j

)(12

2x0

0x

x

0)(其中

W

i

jW

Tgi

x

g

j

x

(()0)i2

I若先验概率相等P(i

)

P(

j

)超平面通过i与j联线的中点，且与联线正交。若先验概率不相等，则x0

不在中点，超平面向先验概率小的方向移动。若2<<||i-j||2,则先验概率对决策面的影响就比较小。d维特征空间，交界面呈球状分布，其判别边界为d-1维的平面，垂直于中心线。2j0

ix

1

(

)一维二维三维⑵i＝

与i无关。各类的协方差矩阵相等1＝2＝···

＝c=。几何上相当于各类样本集中于以该类均值i点为中心的同样大小和形状的超椭球体中。判别函数：12若c类先验概率相等，则gi

(

x)

r

(

x

i

)

(

x

i

)2

T

1Bayes决策：计算x到每类均值点i的马氏距离平方r2,将x分到距离最近的类中去，或归于r2最小的类。i

i

i)

ln

P(

)(

x

)

(

x

T

1ig

(

x)

W不在(i-j)方向上，超平面通过x0点但不与均值向量连线正交。i线性判别函数，因此决策面仍是一个超平面。相邻决策面方程gi

(

x)

g

j

(

x)

0W

T

(

x

x

)

001其中

W

(

)12展开后,

忽略与i无关项xT-1x，则判别函数gi

(

x)

Wi

x

wi

0Ti

i i

0i

i

i

ln

P(

)w

1其中W

,

T

1)20

i

jx

1

(

)

i

j

i

jjln[

p(i

)

/

p(

j

)](

)

(

T

1若先验概率相等，则交点在均值向量联线的中点；若先验概率不相等则向小先验概率方向移动(左图)。若先验概率相差较大，判别边界不会落入球状

分布的中心点之间

(右图)。P(ω1)＝0.7P(ω2)＝0.3P(ω1)＝0.9P(ω2)＝0.1例5

两类二维正态分布的分类问题已知：协方差∑相同，均值向量不同。应属于距离近的类，x＝[1.0,2.2]T属于第一类。

0

0T

3

3T1

20.3

1.9

1.1

0.3

0.95