模式识别二次线性分类错误率

模式识别二次线性分类错误率第1页，共91页，2023年，2月20日，星期五2这一节的目的（概念）有两个：在一定的分布和条件下（如正态、等协方差矩阵），贝叶斯决策可以导致二次或线性分类器。虽然贝叶斯决策（似然比检验）在错误率或风险上是最优的，但必须知道类条件密度。在大多数应用场合，类条件密度函数是从有限的样本中估计的。后面我们将讲一些密度函数估计的方法。但密度函数的估计本身是一件复杂工作（其难度不低于分类）并且需要大量样本。第2页，共91页，2023年，2月20日，星期五3即使我们得到了密度函数，有时用似然比检验的方法也很难计算，需要大量的时间和空间。因此我们有时考虑更简便易行的分类器设计方法。用二次、线性、分段线性分类器。即先规定分类器的数学形式，然后在适当的准则下，来确定这些参数。这一节先分析在什么条件下贝叶斯分类器变成二次和线性分类器，然后讨论当这些条件不满足时，如何设计“性能好”的参数分类器。第3页，共91页，2023年，2月20日，星期五4一.两类问题的二次和线性分类器对于似然比检验的决策规则：第4页，共91页，2023年，2月20日，星期五5当各类的类条件密度是高斯分布时，

mi和Ki为均值向量和协方差矩阵。第5页，共91页，2023年，2月20日，星期五6这时似然比为

定义，-2倍自然对数,则:第6页，共91页，2023年，2月20日，星期五7上式是二次分类器。计算x到各类均值mi的Mahalanobis距离，然后和阈值

相比较，决定x属于第一或第二类。第7页，共91页，2023年，2月20日，星期五8在一维时，马氏距离，即比较用方差标准化的一般距离。展开h(x)式，有（※※）式中第8页，共91页，2023年，2月20日，星期五9决策边界h(x)=T是二次曲面（超曲面）：超椭球面、超双曲面、超抛物面、超平面等，或它们组合的形式。（为了确定二次曲面的形状，首先要消掉x的各分量相乘的项，可采用旋转坐标系的方法，把坐标轴旋转到A（※※）的特征向量的方向。曲面的几何形状由A的特征值决定。如果A的特征值全部是正的，则是超椭球面；如果特征值有些正，有些负，则是超双曲面；如果有些特征值是0，则是超抛物面。）第9页，共91页，2023年，2月20日，星期五10当x落到决策边界的某一侧时，就把它分到相应的类。也可以把上述二次分类器用到非高斯分布的密度函数，但这时不能保证错误率最小。（但所确定的边界是和二阶统计矩（均值、方差）最相匹配的。）

任何具有（※※）式的分类器都叫作二次分类器。只有A、b、c是由高斯密度函数确定时，才叫高斯分类器。第10页，共91页，2023年，2月20日，星期五11例1：两维时的二次分类器的决策边界假定两类模式都是高斯分布的，参数为：求的分类边界，并画出其曲线。第11页，共91页，2023年，2月20日，星期五12解：

第12页，共91页，2023年，2月20日，星期五13假定T=0，h(x)=T=0化为：，是一双曲线。第13页，共91页，2023年，2月20日，星期五14第14页，共91页，2023年，2月20日，星期五15第15页，共91页，2023年，2月20日，星期五16当先验概率相等时，最小错误率决策规则选择密度函数大的。由于第二类在x2方向上的方差大于类1的，这样密度函数p(x|ω2)在x2方向上将有较广的延伸。使得在左边R2区域内有p(x|ω2)>

p(x|ω1)，尽管这些点比较靠近类1的均值点。在前面的h(x)=xTAx+bTx+c中，如果两类的协方差矩阵相等，K1=

K2=

K，则矩阵A=0，这时决策规则为：第16页，共91页，2023年，2月20日，星期五17这时的决策边界就退化为线性决策边界（超平面），相应的分类器为线性分类器。式中第17页，共91页，2023年，2月20日，星期五18二.判别函数和多类分类器判别函数当模式有类，这时的最小错误率的决策规则可以表示为：若（※）

式中

称为判别函数（discriminantfunction）。它表示决策规则。第18页，共91页，2023年，2月20日，星期五19由贝叶斯公式，和等价。即把用在（※）式中时，决策结果和是一样的。当先验概率相等时，p(x|ωk)也是一组等价的判别函数。一般地，若是任意一组判别函数，则下面定义的也是一组等价的判别函数：a>0,b是常数。（也可以是x的函数，但不能是k的函数。）第19页，共91页，2023年，2月20日，星期五20同样，若f是单调增函数，则

它和也是等价的判别函数。这些性质可以使我们从一组判别函数推导出另外的判别函数，以便计算上更加简单，或者意义更清楚，便于理解。

第20页，共91页，2023年，2月20日，星期五21当每类都是正态分布，其均值和协方差矩阵分别为mk和Kk时，这时的最小错误率决策规则的判别函数为：多类的二次和线性分类器

由于自然对数是单调增的，所以可以定义下面等价的判别函数：第21页，共91页，2023年，2月20日，星期五22（※）这是二次判别函数。当所有类的先验概率相等时，可以省略。前面已经证明，当两类的协方差矩阵相等时，二次分类器退化为线性分类器。多类时也是如此。第22页，共91页，2023年，2月20日，星期五23当时，（※）式化为：上式中，由于第一项和第四项对所有的类都是相同的，所以等价的一组判别函数为：（※※）上式是x的线性函数。下面考虑一些特定情况，说明二次和线性分类器的应用。以下假定各类的先验概率都相等。第23页，共91页，2023年，2月20日，星期五24例2：最小距离分类器。假定各类的先验概率相等，而且各类，即x的各个分量不相关，且各类等方差。解：这时的判别函数化为（P22（※）式）：后两项对所有类是共同的，可以省略。分母中的也可以去掉，因而有等价的判别函数：这时的决策规则的含义是：x离哪类的均值最近，就把它分到哪类。第24页，共91页，2023年，2月20日，星期五25例3：内积分类器（相关分类器）有假定。利用线性判别函数若进一步假定每类的均值的模相等，即|mk|相等，它们分布在半径为|mk|的一个超球面上，且由于假定先验概率也相等，因此，等价的判别函数为：第25页，共91页，2023年，2月20日，星期五26即将测量向量x和每类的均值mk作内积（或称相关），然后选择值最大的，作为它的类。上述例子是通信理论中信号检测的一个经典例子。假定有Nc种已知信号要检测。令x(t)表示接收到的信号，mk(t)是已知的信号，k=1，2，…，Nc

。当mk(t)发送时，加入了白噪声w(t)，第26页，共91页，2023年，2月20日，星期五27白噪声w(t)是零均值、等方差、不相关的信号（随机过程）。即在任意时刻ti，w(ti)的均值为0，方差为，且当时，。即：如果随机向量x和mk是由相应的时间函数取样而成，即第27页，共91页，2023年，2月20日，星期五28第28页，共91页，2023年，2月20日，星期五29这是一个相关分类器（内积分类器）的模式识别问题。假定|mk|2相等，即所有的信号具有相等的能量。第29页，共91页，2023年，2月20日，星期五30把接收到的信号和已知信号作相关mkTx，然后选择相关最大的。作相关时通常通过一个“匹配滤波器”来实现。选择最大的输出

匹配滤波器1

┇

匹配滤波器2

匹配滤波器Nc

第30页，共91页，2023年，2月20日，星期五31在连续时，判别函数：另外，mk和x间的相关也可以通过一个线性滤波器的输出来实现。构造一个函数gk(t)，使满足gk(T－t)=mk(t)，则（线性系统的杜哈美尔积分）

第31页，共91页，2023年，2月20日，星期五32即滤波器的输出是相关值，而滤波器的脉冲响应是gk(t)，匹配滤波器可由专门的仪器来作。*可以把上面的线性分类器的讨论再进一步。在线性分类器中，如果把向量在K的特征向量的坐标系下表示（作变换），并作比例变换使所有分量的方差变为1，这时，线性分类器将作mkTx相关运算。在通信问题中，如果噪声信号是相关的，而且方差是变化的，那么最优的信号检测是使噪声变为不相关的，然后作相关或匹配滤波器运算。

第32页，共91页，2023年，2月20日，星期五33三.Fisher线性分类器—另一种决策准则（另外一种解决思路）

在前面一节中，我们讨论了两种形式的分类器，在n维空间内分析了它的判别边界。其中分类的参数如A、b、c和T都是确定的，如果模式满足高斯分布，那么分类器可以使错误率、最小风险或者Neyman—Pearson准则最小。第33页，共91页，2023年，2月20日，星期五34但在某些情况下，不知道类条件密度函数，因此不可能找出最优分类器。在另外一些情况下，虽然可以对类条件密度进行估计，但推导最优分类器的计算量太大。因此，实际工作中，一般是先假定一种分类器的数学形式，如线性或二次分类器，然后确定它的参数，使它对某种适当的准则函数最优，如类间的分离性等。在一般情况下，这种准则函数不一定是错误率，而是更加简单和易于分析的。第34页，共91页，2023年，2月20日，星期五35人们在线性分类器上作了许多工作。这不仅因为它形式简单，而且用分段线性的组合可以任意逼近复杂的决策边界。我们先介绍其中的一种：Fisher线性分类器（两类问题）。线性分类器的形式：寻找分类器的参数，能够使以下的Fisher准则函数最大：（3.21）

第35页，共91页，2023年，2月20日，星期五36（3.22a）

式中

（3.22b）

希望使两类的均值离得越开越好，而方差尽可能的小。回想一下，若有即第36页，共91页，2023年，2月20日，星期五37（3.23a）

这时h(x)（分类器的输出）的均值和方差为（3.23b）

方程（3.21）和参数c无关（相减），因此c可以包括到阈值T里去。因此只要找出b就可以了。对准则函数求导并令其等于0，有变换后的均值和方差第37页，共91页，2023年，2月20日，星期五38（3.24）

∴

（3.25）

第38页，共91页，2023年，2月20日，星期五39利用（3.23）式可以求出、、、，然后代入上式，但为了简单，有时就把b定为（3.26）

而把项放到阈值里去。第39页，共91页，2023年，2月20日，星期五40这样分类器的形式就成为：当K1=K2=K时，（3.26）式的b和（3.9a）的成比例。这样，当模式满足高斯分布，且协方差矩阵相等时，使Fisher准则最优等价于最小错误率最优。第40页，共91页，2023年，2月20日，星期五41小结这一章首先讨论了一些简单的决策理论最小错误率、风险、Neyman—Pearson

似然比检验，只是阈值不同。最小最大决策，当先验概率变化时，使最大的错误率最小。序贯决策：测量的维数可变时，分析了阈值和错误率间的关系。在独立同分布的假定下分析了维数的期望值。第41页，共91页，2023年，2月20日，星期五42这一章还介绍了线性和二次分类器

对于多类模式识别问题的判别函数。讨论了最近距离分类和相关分类。讨论了两类问题的一种线性分类器——Fisher分类器。在高斯分布、等协方差矩阵的情况下，Fisher分类器等价于最小错误率分类器。第42页，共91页，2023年，2月20日，星期五43*这类线性分类器的更一般解法

线性分类器是最容易实现的。然而，只在正态分布和等协方差的情况下，线性判别函数才是贝叶斯意义上最优的。在通信系统的信号检测中，等协方差矩阵是合理的。但在不少应用场合，并不满足协方差矩阵相等。在设计正态分布、不等协方差的线性分类器，在设计非正态分布的线性分类器上有不少研究成果。当然，它们不是最优的。但简单易行，可以补偿性能上的损失。下面我们更一般地讨论这一问题。第43页，共91页，2023年，2月20日，星期五44令

任务是要确定和。

表示x在V方向上的投影。投影后的均值和方差是衡量类可分性的一个准则。

第44页，共91页，2023年，2月20日，星期五45投影比要好。投影后的均值和方差是衡量类可分性的一个准则。

第45页，共91页，2023年，2月20日，星期五46令是任一准则函数（要最大或最小的），要确定使f最大（小）的v和v0。第46页，共91页，2023年，2月20日，星期五47由于

代入，有：

第47页，共91页，2023年，2月20日，星期五48由以上两式可以计算出v，但由于错误率只依赖v的方向，而不是它的大小。因而可以消去v的常数系数（不是mi和ki的函数）。

解出：

式中，第48页，共91页，2023年，2月20日，星期五49注意，上面得出的v和f无关，f只是出现在s中。回想在正态、等协方差的情况下，有

这里是用s和(1－s)对K1和K2作加权平均。当f的具体形式给出后，v0是的解。第49页，共91页，2023年，2月20日，星期五50例1：Fisher线性分类器。

∵

因此s＝0.5Fisher准则不依赖于v0。因为v0从和相减中消失了。

∴最佳的第50页，共91页，2023年，2月20日，星期五51例2：另种准则是

解出后有∴Fisher准则不能确定v0。

第51页，共91页，2023年，2月20日，星期五522.5分类器的错误率问题

对样本进行分类是PR的任务之一。在分类过程中总会有错误率，当先验概率和类条件密度函数已知，采用的决策规则也确定后，错误率也就固定了。错误率反映了模式分类问题本身的固有复杂程度。也是衡量分类器性能的重要指标。分类器是否和要解决的问题相匹配。一.错误率的计算和估计第52页，共91页，2023年，2月20日，星期五53从上式可以看出，在x是多维时，P(e)的计算要进行多重积分。当类条件密度函数的解析形式比较复杂时，P(e)的计算相当困难。错误率的计算公式前面已经分析，对两类问题：第53页，共91页，2023年，2月20日，星期五54由于错误率对模式识别系统的重要性和复杂性，人们对错误率的计算和估算方法进行了大量的研究。方法主要有以下几类：按公式计算错误率；估算错误率的上限；从实验中估计错误率。这一小节先讨论前两种方法。第54页，共91页，2023年，2月20日，星期五55正态分布且等协方差矩阵时；当x的各分量间相互独立时；（参考清华的书，略）。下面讨论估计错误率上限的方法二.在一些特殊情况下错误率的计算第55页，共91页，2023年，2月20日，星期五56模式可分性度量反映了模式分类的困难程度，和错误率有密切关系。既有理论上的意义，也用在特征抽取和选择等问题上。这一节介绍模式可分性的两种重要度量：偏离度（divergence）和Bhattacharyya距离。

（泾渭分明，西瓜瓤和籽）

先对一般的概率密度函数定义这两个量。然后在多元高斯情况下，看看会有什么结果。三.

模式可分性的度量第56页，共91页，2023年，2月20日，星期五57对于对数的似然比检验：

也是一个随机变量。它可以用两个密度函数和来描述。如下图所示，当两个密度函数偏离较大时，错误率一定低，反之会大。偏离度和Bhattacharyya距离第57页，共91页，2023年，2月20日，星期五58两类模式可分性的一种度量是它们均值的差，称为偏离度D

。第58页，共91页，2023年，2月20日，星期五59偏离度的定义为：

定义量：称为有（单）向偏离度，或第i类相对第j类的相对信息。有些作者称它为Kullback—liebler数。第59页，共91页，2023年，2月20日，星期五60由上两式可知

这样，当相对信息H(1，2)和H(2，1)大时，D也大，可分性好。可分性的另一种度量是Bhattacharyya距离：而量，有时称为Bhattacharyya系数。第60页，共91页，2023年，2月20日，星期五61这两个量比起偏离度来，直观上更难解释。但若将写为：我们可以给出Bhattacharyya距离的一种解释，如下图：第61页，共91页，2023年，2月20日，星期五62第62页，共91页，2023年，2月20日，星期五63若原来的两个密度函数分的较开，则f相对于ω2的期望将较小（<<1）。这时的－ln值将会大，Bhattacharyya距离将会大。第63页，共91页，2023年，2月20日，星期五64反之，若p1(x)和p2(x)近似重叠，则期望值将较大，－ln将较小。即Bhattacharyya距离小。如下图：第64页，共91页，2023年，2月20日，星期五65偏离度和B距离是真的距离度量吗？偏离度和Bhattacharyya距离都满足：在一对一的线性变换下不变；当x的分量独立时，这两个量都满足相加性（对每个成分）。第65页，共91页，2023年，2月20日，星期五66令表示偏离度或Bhattacharyya距离，有：但它们都不满足距离的三角不等式，所以都不是真实的距离。但它们满足下面的性质：第66页，共91页，2023年，2月20日，星期五67对于高斯分布的数据，可以推导出它的偏离度的封闭形式解。高斯分布下的偏离度和Bhattacharyya距离

而第67页，共91页，2023年，2月20日，星期五68由于而且由有第68页，共91页，2023年，2月20日，星期五69和∴第69页，共91页，2023年，2月20日，星期五70同样，有：∴这就是高斯分布的偏离度。第70页，共91页，2023年，2月20日，星期五71对于高斯分布的Bhattacharyya距离，有相似的推导。第71页，共91页，2023年，2月20日，星期五72其中的指数项可以化为：

可以化为第72页，共91页，2023年，2月20日，星期五73其中第73页，共91页，2023年，2月20日，星期五74∴第74页，共91页，2023年，2月20日，星期五75可以证明（※）

以及（※※）

第75页，共91页，2023年，2月20日，星期五76证明的思路和技巧：定义量先证明由此再证：以及第76页，共91页，2023年，2月20日，星期五77由上面各种关系证明（※）和（※※）。∴这是对于高斯分布的Bhattacharyya距离。第77页，共91页，2023年，2月20日，星期五78由上式的B和前面的可以看出，当两类的协方差矩阵相等时，K1=

K2=

K，∴此时的D和B是等价的度量，而且和两类均值间的马氏距离等价。说明D

和B

确是两类间偏离和距离的一种度量。第78页，共91页，2023年，2月20日，星期五79上一小节定义了偏离度和Bhattacharyya距离。下面分析它们和错误率的关系。这一节讨论似然比检验的错误率的上界。它们是基于Bhattacharyya距离及其推广。四.错误率的Bhattacharyya和Chernoff界最小错误率的上界最小错误率（有时也叫贝叶斯错误率）eB

为：第79页，共91页，2023年，2月20日，星期五80利用不等式上式可以化为：即这个结果称为Bhattacharyya界。第80页，共91页，2023年，2月20日，星期五81若利用不等式和前面的推导一样，可得更一般的Chernoff界：式