模式识别之二次和线性分类器

2.3二次和线性分类器

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

mi和Ki为均值向量和协方差矩阵。5这时似然比为

定义，-2倍自然对数,则:6上式是二次分类器。计算x到各类均值mi的Mahalanobis距离，然后和阈值

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

任何具有（※※）式的分类器都叫作二次分类器。只有A、b、c是由高斯密度函数确定时，才叫高斯分类器。10例1：两维维时时的的二二次次分分类类器器的的决决策策边边界界假定定两两类类模模式式都都是是高高斯斯分分布布的的，，参参数数为为：：求的的分分类类边边界界，，并并画画出出其其曲曲线线。。11解：：12假定定T=0，h(x)=T=0化为为：：，是是一一双双曲曲线线。。131415当先先验验概概率率相相等等时时，，最最小小错错误误率率决决策策规规则则选选择择密密度度函函数数大大的的。。由于第二二类在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这时的决决策边界界就退化化为线性性决策边边界（超超平面）），相应应的分类类器为线线性分类类器。式中17二.判别函数数和多类类分类器器判别函数数当模式有有类类，这这时的最最小错误误率的决决策规则则可以表表示为：：若（※）式中称为判别别函数（discriminantfunction）。它表示示决策规规则。18由贝叶斯斯公式，，和和等等价。即即把用用在在（※）式中时时，决策策结果和和是是一样样的。当先验概概率相等等时，p(x|ωk)也是一组组等价的的判别函函数。一般地，，若是是任意意一组判判别函数数，则下下面定义义的也也是一一组等价价的判别别函数：：a>0,b是常数。。（也可可以是x的函数，，但不能能是k的函数。。）19同样，若f是单调增增函数，，则它和也也是等等价的判判别函数数。这些性质质可以使使我们从从一组判判别函数数推导出出另外的的判别函函数，以以便计算算上更加加简单，，或者意意义更清清楚，便便于理解解。20当每类都都是正态态分布，，其均值值和协方方差矩阵阵分别为为mk和Kk时，这时时的最小小错误率率决策规规则的判判别函数数为：多类的二二次和线线性分类类器由于自然然对数是是单调增增的，所所以可以以定义下下面等价价的判别别函数：：21（※）这是二次次判别函函数。当当所有类类的先验验概率相相等时，，可以省省略。。前面已经经证明，，当两类类的协方方差矩阵阵相等时时，二次次分类器器退化为为线性分分类器。。多类时时也是如如此。22当时时，（※）式化为：上式中，，由于第第一项和和第四项项对所有有的类都都是相同同的，所所以等价价的一组组判别函函数为：：（※※）上式是x的线性函函数。下面考虑虑一些特特定情况况，说明明二次和和线性分分类器的的应用。以下假定定各类的的先验概概率都相相等。23例2：最小距离离分类器器。假定定各类的的先验概概率相等等，而且且各类，，即x的各个分分量不相相关，且且各类等等方差。。解：这时的判判别函数数化为（P22（※）式）：后两项对对所有类类是共同同的，可可以省略略。分母母中的也也可可以去掉掉，因而而有等价价的判别别函数：：这时的决决策规则则的含义义是：x离哪类的的均值最最近，就就把它分分到哪类类。24例3：内积分类类器（相相关分类类器）有假定。。利利用线性性判别函函数若进一步步假定每每类的均均值的模模相等，，即|mk|相等，它它们分布布在半径径为|mk|的一个超超球面上上，且由由于假定定先验概概率也相相等，因因此，等等价的判判别函数数为：25即将测量量向量x和每类的的均值mk作内积（（或称相相关），，然后选选择值最最大的，，作为它它的类。。上述例子子是通信信理论中中信号检检测的一一个经典典例子。。假定有Nc种已知信信号要检检测。令令x(t)表示接收收到的信信号，mk(t)是已知的的信号，，k=1，2，…，Nc。当mk(t)发送时，，加入了了白噪声声w(t)，26白噪声w(t)是零均值值、等方方差、不不相关的的信号（（随机过过程）。。即在任任意时刻刻ti，w(ti)的均值为为0，方差为为，，且当当时时，，。。即：如果随机机向量x和mk是由相应应的时间间函数取取样而成成，即2728这是一个个相关分分类器（（内积分分类器））的模式式识别问问题。假定|mk|2相等，即即所有的的信号具具有相等等的能量量。29把接收到到的信号号和已知知信号作作相关mkTx，然后选选择相关关最大的的。作相相关时通通常通过过一个“匹配滤波波器”来实现。。选择最大的输出

匹配滤波器1

┇

匹配滤波器2

匹配滤波器Nc

30在连续时时，判别别函数：：另外，mk和x间的相关关也可以以通过一一个线性性滤波器器的输出出来实现现。构造一个个函数gk(t)，使满足足gk(T－t)=mk(t)，则（线性系统统的杜哈哈美尔积积分）31即滤波器器的输出出是相关关值，而而滤波器器的脉冲冲响应是是gk(t)，匹配滤滤波器可可由专门门的仪器器来作。。*可以把上上面的线线性分类类器的讨讨论再进进一步。。在线性性分类器器中，如果果把向量量在K的特征向向量的坐坐标系下下表示（（作变换换），并并作比例例变换使使所有分分量的方方差变为为1，这时，，线性分分类器将将作mkTx相关运算算。在通通信问题题中，如如果噪声声信号是是相关的的，而且且方差是是变化的的，那么么最优的的信号检检测是使使噪声变变为不相相关的，，然后作作相关或或匹配滤滤波器运运算。32三.Fisher线性分类类器—另一种决决策准则则（另外一一种解决决思路））在前面一一节中，，我们讨讨论了两两种形式式的分类类器，在在n维空间内内分析了了它的判判别边界界。其中中分类的的参数如如A、b、c和T都是确定定的，如如果模式式满足高高斯分布布，那么么分类器器可以使使错误率率、最小小风险或或者Neyman——Pearson准则最小小。33但在某些些情况下下，不知知道类条条件密度度函数，，因此不不可能找找出最优优分类器器。在另外一一些情况况下，虽虽然可以以对类条条件密度度进行估估计，但但推导最最优分类类器的计计算量太太大。因此，实实际工作作中，一般是先先假定一一种分类类器的数数学形式式，如线性或或二次分分类器，，然后确定定它的参参数，使使它对某某种适当当的准则则函数最优，如类间间的分离离性等。。在一般情情况下，，这种准准则函数数不一定定是错误误率，而而是更加加简单和和易于分分析的。。34人们在线线性分类类器上作作了许多多工作。。这不仅仅因为它它形式简简单，而而且用分分段线性性的组合合可以任任意逼近近复杂的的决策边边界。我我们先介介绍其中中的一种种：Fisher线性分类类器（两两类问题题）。线性分类类器的形形式：寻找分类类器的参参数，能能够使以以下的Fisher准则函函数最最大：（3.21）35（3.22a）式中（3.22b）希望使使两类类的均均值离离得越越开越越好，，而方方差尽尽可能能的小小。回想一一下，，若有有即36（3.23a）这时h(x)（分类类器的的输出出）的的均值值和方方差为为（3.23b）方程（（3.21）和参参数c无关（（相减减），，因此此c可以包包括到到阈值值T里去。。因此此只要要找出出b就可以以了。。对准准则函函数求求导并并令其其等于于0，有变换后后的均均值和和方差差37（3.24）∴（3.25）38利用（（3.23）式可可以求求出、、、、、、，，然然后代代入上上式，，但为为了简简单，，有时时就把把b定为（3.26）而把项项放放到到阈值值里去去。39这样分分类器器的形形式就就成为为：当K1=K2=K时，（（3.26）式的的b和（3.9a）的成比例例。这这样，，当模模式满满足高高斯分分布，，且协协方差差矩阵阵相等等时，，使Fisher准则最最优等等价于于最小小错误误率最最优。。40小结这一章章首先先讨论论了一一些简简单的的决策策理论论最小错错误率率、风风险、、Neyman——Pearson似然比比检验验，只只是阈阈值不不同。。最小最最大决决策，，当先先验概概率变变化时时，使使最大大的错错误率率最小小。序贯决决策：：测量量的维维数可可变时时，分分析了了阈值值和错错误率率间的的关系系。在在独立立同分分布的的假定定下分分析了了维数数的期期望值值。41这一章章还介介绍了了线性性和二二次分分类器器对于多多类模模式识识别问问题的的判别别函数数。讨论了了最近近距离离分类类和相相关分分类。。讨论了了两类类问题题的一一种线线性分分类器器——Fisher分类器器。在在高斯斯分布布、等等协方方差矩矩阵的的情况况下，，Fisher分类器器等价价于最最小错错误率率分类类器。。42*这类线性分分类器器的更更一般般解法法线性分分类器器是最最容易易实现现的。。然而而，只只在正正态分分布和和等协协方差差的情情况下下，线线性判判别函函数才才是贝贝叶斯斯意义义上最最优的的。在通信信系统统的信信号检检测中中，等等协方方差矩矩阵是是合理理的。。但在在不少少应用用场合合，并并不满足足协方方差矩矩阵相相等。在设计计正态态分布布、不不等协协方差差的线线性分分类器器，在在设计计非正正态分分布的的线性性分类类器上上有不不少研研究成成果。。当然然，它它们不不是最最优的的。但但简单单易行行，可可以补补偿性性能上上的损损失。。下面面我们们更一般般地讨讨论这这一问问题。43令任务是是要确确定和和。。表示x在V方向上上的投投影。。投影影后的的均值值和和方差差是是衡量量类可可分性性的一一个准准则。。44投影比比要要好好。投投影后后的均均值和和方方差是是衡衡量类类可分分性的的一个个准则则。45令是是任一准准则函函数（要最最大或或最小小的）），要要确定定使f最大（（小））的v和v0。46由于代入，，有：：47由以上上两式式可以以计算算出v，但由由于错错误率率只依依赖v的方向向，而而不是是它的的大小小。因因而可可以消消去v的常数系数数（不是mi和ki的函数）。。解出：式中，48注意，上面面得出的v和f无关，f只是出现在在s中。回想在正态态、等协方方差的情况况下，有这里是用s和(1－s)对K1和K2作加权平均均。当f的具体形式式给出后，，v0是的解。49例1：Fisher线性分类器器。∵因此s＝0.5Fisher准则不依赖赖于v0。因为v0从和相相减中中消失了。。∴最佳的50例2：另种准则是是解出后有∴Fisher准则不能确确定v0。512.5分类器的错错误率问题题对样本进行行分类是PR的任务之一一。在分类类过程中总总会有错误误率，当先先验概率和和类条件密密度函数已已知，采用用的决策规规则也确定定后，错误误率也就固固定了。错误率反映映了模式分分类问题本本身的固有复杂程程度。也是衡量分类器器性能的重要指标标。分类器器是否和要要解决的问问题相匹配配。一.错误率的计计算和估计计52从上式可以以看出，在在x是多维时，，P(e)的计算要进进行多重积积分。当类类条件密度度函数的解解析形式比比较复杂时时，P(e)的计算相当当困难。错误率的计计算公式前前面已经分分析，对两两类问题：：53由于错误率率对模式识识别系统的的重要性和和复杂性，，人们对错错误率的计算和估算方法进行了了大量的研研究。方法法主要有以以下几类：：按公式计算算错误率；；估算错误率率的上限；；从实验中估估计错误率率。这一小节先先讨论前两两种方法。。54正态分布且且等协方差差矩阵时；；当x的各分量间间相互独立立时；（参考清华华的书，略略）。下面讨论估估计错误率率上限的方方法二.在一些特殊殊情况下错错误率的计计算55模式可分性性度量反映映了模式分分类的困难难程度，和和错误率有有密切关系系。既有理理论上的意意义，也用用在特征抽取和和选择等问问题上。这一节节介绍模式式可分性的的两种重要要度量：偏偏离度（divergence）和Bhattacharyya距离。（泾渭分明明，西瓜瓤和籽））先对一般的的概率密度度函数定义义这两个量量。然后在在多元高斯斯情况下，，看看会有有什么结果果。三.模式可分性性的度量56对于对数的的似然比检检验：也是一个随随机变量。。它可以用用两个密度度函数和和来来描述述。如下图图所示，当当两个密度度函数偏离离较大时，，错误率一一定低，反反之会大。。偏离度和Bhattacharyya距离57两类模式可可分性的一一种度量是是它们均值值的差，，称为偏离度D。58偏离度的定定义为：定义量：称为有（单单）向偏离离度，或第第i类相对第j类的相对信信息。有些些作者称它它为Kullback——liebler数。59由上两式可可知这样，当相相对信息H(1，2)和H(2，1)大时，D也大，可分分性好。可分性的另另一种度量量是Bhattacharyya距离：而量，，有时时称为Bhattacharyya系数。60这两个量比比起偏离度度来，直观观上更难解解释。但若若将写写为：我们可以给给出Bhattacharyya距离的一种种解释，如如下图：6162若原来的两两个密度函函数分的较较开，则f相对于ω2的期望将较较小（<<1）。这时的－ln值将会大，，Bhattacharyya距离将会大大。63反之，若p1(x)和p2(x)近似重叠，，则期望值值将较大，，－ln将较小。即即Bhattacharyya距离小。如如下图：64偏离度和B距离是真的的距离度量量吗？偏离度和Bhattacharyya距离都满足足：在一对一的的线性变换换下不变；；当x的分量独立立时，这两两个量都满满足相加性性（对每个个成分）。。65令表表示示偏离度或或Bhattacharyya距离，有：：但它们都不满足距离离的三角不不等式，所以都不不是真实的的距离。但但它们满足足下面的性性质：66对于高斯分分布的数据据，可以推推导出它的的偏离度的的封闭形式式解。高斯分布下下的偏离度度和Bhattacharyya距离而67由于而且由有68和∴69同样，有：：∴这就是高斯斯分布的偏偏离度。70对于高斯分分布的Bhattacharyya距离，有相相似的推导导。71其中的指数数项可以化化为：可以化为72其中73∴74可以证明（※）以及（※※）75证明的思路路和技巧：：定义量先证明由此再证：：以及76由上面各种种关系证明明（※）和（※※）。∴这是对于高高斯分布的的Bhattacharyya距离。77由上式的B和前面的可以看出，，当两类的的协方差矩矩阵相等时时，K1=K2=K，∴此时的D和B是等价的度度量，而且且和两类均均值间的马马氏距离等等价。说明明D和B确是两类间间偏离和距距离的一种种度量。78上一小节定定义了偏离离度和Bhattacharyya距离。下面面分析它们们和错误率率的关系。。