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

1、模式识别之二次和线性分类器 即使我们得到了密度函数，有时用似然比检验的方法也很难计算，需要大量的时间和空间。 因此我们有时考虑更简便易行的分类器设计方法。用二次、线性、分段线性分类器。即先规定分类器的数学形式，然后在适当的准那么下，来确定这些参数。 这一节先分析在什么条件下贝叶斯分类器变成二次和线性分类器，然后讨论当这些条件不满足时，如何设计“性能好的参数分类器。 2一. 两类问题的二次和线性分类器对于似然比检验的决策规那么： ,xxx2121Tppl 112112212212PPPPTrrrrxdlp223 当各类的类条件密度是高斯分布时， iiTiinimKmKpxx2121x1212ex

2、p mi和Ki为均值向量和协方差矩阵。 4 这时似然比为 212122111112xx21xx21xmKmmKmKKlTTexp定义 ，-2倍自然对数,那么: ln 2xxlh lnln2xxxxx212121221111TKKmKmmKmhTT5 上式是二次分类器。计算x到各类均值mi的 Mahalanobis距离，然后和阈值 相比较，决定x属于第一或第二类。 21KKTln6 在一维时，马氏距离 ，即比较用方差标准化的一般距离。 22iimx 展开h(x)式，有 TcbhTT21xAxxx 式中 1211AKK1112122mKmKb2121221111KKmKmmKmcTTln7 决策边

3、界h(x)=T是二次曲面超曲面：超椭球面、超双曲面、超抛物面、超平面等，或它们组合的形式。 为了确定二次曲面的形状，首先要消掉x的各分量相乘的项，可采用旋转坐标系的方法，把坐标轴旋转到A的特征向量的方向。曲面的几何形状由A的特征值决定。如果A的特征值全部是正的，那么是超椭球面；如果特征值有些正，有些负，那么是超双曲面；如果有些特征值是0，那么是超抛物面。 8 当x落到决策边界的某一侧时，就把它分到相应的类。也可以把上述二次分类器用到非高斯分布的密度函数，但这时不能保证错误率最小。但所确定的边界是和二阶统计矩均值、方差最相匹配的。 任何具有式的分类器都叫作二次分类器。只有A、b、c是由高斯密度函

4、数确定时，才叫高斯分类器。 9 例例1 1：两维时的二次分类器的决策边界 假定两类模式都是高斯分布的，参数为： 410011K001m100412K202m 0 Th x求 的分类边界，并画出其曲线。 10 解：解： 4141ln2 1004 2 4001 21212121xxxxxxxxh x224422212221xxxxx4444222212221xxxxx443322221xxx113434321222xxx94343232122xx假定T=0，h(x)=T=0化为： 221223432xx，是一双曲线。 1213Pattern Classification, Chapter 2 (P

5、art 1)2214 领先验概率相等时，最小错误率决策规那么选择密度函数大的。 由于第二类在x2方向上的方差大于类1的，这样密度函数p(x|2)在x2方向上将有较广的延伸。使得在左边R2区域内有p(x|2) p(x|1)，尽管这些点比较靠近类1的均值点。 在前面的h(x)= xTAx+bTx+c中，如果两类的协方差矩阵相等，K1= K2= K，那么矩阵A=0，这时决策规那么为： 15 这时的决策边界就退化为线性决策边界超平面，相应的分类器为线性分类器。 TcbhT21xx1212mmKb212111mKmmKmcTT式中 16二. 判别函数和多类分类器 1. 判别函数 当模式有 类，这时的最小

6、错误率的决策规那么可以表示为： 2cN假设 ikkigg maxxx 式中 ckrkNkPg， 2 1 xx 称为判别函数discriminant function。它表示决策规那么。 xkg17 由贝叶斯公式， 和 等价。即把 用在式中时，决策结果和 是一样的。 领先验概率相等时，p(x|k)也是一组等价的判别函数。 一般地，假设 是任意一组判别函数，那么下面定义的 也是一组等价的判别函数： a0,b是常数。也可以是x的函数，但不能是k的函数。 krkkPpgxx xkg xkg xkg xkg ckkNkbagg， 2 1 xx xkg18 同样，假设f是单调增函数，那么 它和 也是等价的

7、判别函数。 这些性质可以使我们从一组判别函数推导出另外的判别函数，以便计算上更加简单，或者意义更清楚，便于理解。 xkg ckkNkgfg， 2 1 xx19 当每类都是正态分布，其均值和协方差矩阵分别为mk和Kk时，这时的最小错误率决策规那么的判别函数为： 2. 多类的二次和线性分类器 kkTkknkrkmKmKPgxx212x1212exp 由于自然对数是单调增的，所以可以定义下面等价的判别函数： 20 ln2xln2xnggkkkrkkkTkPKmKmln2lnxx1 这是二次判别函数。当所有类的先验概率相等时，可以省略 。 krPln 前面已经证明，当两类的协方差矩阵相等时，二次分类器

8、退化为线性分类器。多类时也是如此。 21 当 时，式化为： 上式中，由于第一项和第四项对所有的类都是相同的，所以等价的一组判别函数为： KKKKcN21 krkTkTkTkPkmkmkmkgln2ln2111xxxx ckrkTkTkkNkPmkmkmg， 2 1ln2211xx 上式是x的线性函数。 下面考虑一些特定情况，说明二次和线性分类器的应用。 以下假定各类的先验概率都相等。 22 例例2 2：最小距离分类器。假定各类的先验概率相等，而且各类 ，即x的各个分量不相关，且各类等方差。 解：这时的判别函数化为P22式 ： 后两项对所有类是共同的，可以省略。分母中的 也可以去掉，因而有等价的

9、判别函数： ckNkIK， 212 krkkPnmgln2ln2xx222 2kkmgxx 这时的决策规那么的含义是：x离哪类的均值最近，就把它分到哪类。 23 例例3 3 ：内积分类器相关分类器：内积分类器相关分类器 有 假定 。利用线性判别函数 假设进一步假定每类的均值的模相等，即|mk|相等，它们分布在半径为|mk|的一个超球面上，且由于假定先验概率也相等，因此，等价的判别函数为： ckNkIK， 212 krkTkTkkPmKmKmgln2x2x11 krkTkkPmmgln22222xx24 jdjjkTkkxmmg1 xx 即将测量向量x和每类的均值mk作内积或称相关，然后选择值最

10、大的，作为它的类。 上述例子是通信理论中信号检测的一个经典例子。 假定有Nc种信号要检测。令x(t)表示接收到的信号，mk(t)是的信号，k=1，2，Nc 。当mk(t)发送时，参加了白噪声w(t)， 25 白噪声w(t)是零均值、等方差、不相关的信号随机过程。即在任意时刻ti，w(ti)的均值为0，方差为 ，且当 时， 。 即： twtmtkx2ijtt 0jitwtwE 如果随机向量x和mk是由相应的时间函数取样而成，即2627 已知信号 21mkkkktmtmtmm 白噪声 0022twtwEtwEtwE 噪声信号mtxtxtx21x 这是一个相关分类器内积分类器的模式识别问题。 假定|

11、mk|2相等，即所有的信号具有相等的能量。 28 把接收到的信号和信号作相关mkTx，然后选择相关最大的。作相关时通常通过一个“匹配滤波器来实现。 选择最大的输出 匹配滤波器1 匹配滤波器2 匹配滤波器Nc 29 在连续时，判别函数： dtttmxmmgTkjdjjkTkkxxx01 另外，mk和x间的相关也可以通过一个线性滤波器的输出来实现。 构造一个函数gk(t)，使满足 gk(Tt)=mk(t)，那么 线性系统的杜哈美尔积分 dtttTgdtttmTkTkxx0030 即滤波器的输出是相关值，而滤波器的脉冲响应是gk(t)，匹配滤波器可由专门的仪器来作。 * 可以把上面的线性分类器的讨论

12、再进一步。在线性分类器 ckrkTkTkkNkPmKmKmg， ln212x2x11中，如果把向量在K的特征向量的坐标系下表示作变换，并作比例变换使所有分量的方差变为1，这时，线性分类器将作mkTx相关运算。在通信问题中，如果噪声信号是相关的，而且方差是变化的，那么最优的信号检测是使噪声变为不相关的，然后作相关或匹配滤波器运算。 31三. Fisher线性分类器另一种决策准那么另外一种解决思路 在前面一节中，我们讨论了两种形式的分类器，在n维空间内分析了它的判别边界。其中分类的参数如A、b、c和T都是确定的，如果模式满足高斯分布，那么分类器可以使错误率、最小风险或者NeymanPearson准

13、那么最小。 32 但在某些情况下，不知道类条件密度函数，因此不可能找出最优分类器。 在另外一些情况下，虽然可以对类条件密度进行估计，但推导最优分类器的计算量太大。 因此，实际工作中，一般是先假定一种分类器的数学形式，如线性或二次分类器，然后确定它的参数，使它对某种适当的准那么函数最优，如类间的别离性等。在一般情况下，这种准那么函数不一定是错误率，而是更加简单和易于分析的。 33 人们在线性分类器上作了许多工作。这不仅因为它形式简单，而且用分段线性的组合可以任意逼近复杂的决策边界。我们先介绍其中的一种：Fisher线性分类器两类问题。 线性分类器的形式： cbhTxx寻找分类器的参数，能够使以下

14、的Fisher准那么函数最大：2221221F3.21 343.22a 式中 iihEx 2 , 1x22ihEiii 3.22b 希望使两类的均值离得越开越好，而方差尽可能的小。回想一下，假设有 Axy 即 xyAAx ETAAKAEKxyx 353.23a 这时h(x)分类器的输出的均值和方差为 3.23b 方程3.21和参数c无关相减，因此c可以包括到阈值T里去。因此只要找出b就可以了。对准那么函数求导并令其等于0，有 变换后的均值和方差 cmbiTi212，ibKbiTi 36222221212211FbFbFbFbbF022212222122121222121bKbKmm3.24 2

15、1121212221mmKKb3.25 37 利用3.23式可以求出 、 、 、 ，然后代入上式，但为了简单，有时就把b定为 1221222112121mmKKb3.26 而把项 放到阈值里去。 21222138 这样分类器的形式就成为： TKKmmT2112121x21当K1=K2=K时，3.26式的b和3.9 a的成比例。这样，当模式满足高斯分布，且协方差矩阵相等时，使Fisher准那么最优等价于最小错误率最优。1212mmkb39小结小结 这一章首先讨论了一些简单的决策理论 最小错误率、风险、NeymanPearson 似然比检验，只是阈值不同。 最小最大决策，领先验概率变化时，使最大的

16、错误率最小。 序贯决策：测量的维数可变时，分析了阈值和错误率间的关系。在独立同分布的假定下分析了维数的期望值。 40 这一章还介绍了线性和二次分类器 对于多类模式识别问题的判别函数。 讨论了最近距离分类和相关分类。 讨论了两类问题的一种线性分类器Fisher分类器。在高斯分布、等协方差矩阵的情况下，Fisher分类器等价于最小错误率分类器。 41 * 这类线性分类器的更一般解法 线性分类器是最容易实现的。然而，只在正态分布和等协方差的情况下，线性判别函数才是贝叶斯意义上最优的。 在通信系统的信号检测中，等协方差矩阵是合理的。但在不少应用场合，并不满足协方差矩阵相等。 在设计正态分布、不等协方差

17、的线性分类器，在设计非正态分布的线性分类器上有不少研究成果。当然，它们不是最优的。但简单易行，可以补偿性能上的损失。下面我们更一般地讨论这一问题。 42令 0210vhTxvx任务是要确定 和 。 Tnvvv，21v 0vxvyT表示x在V方向上的投影。投影后的均值 和方差 是衡量类可分性的一个准那么。 i2i43投影 比 要好。投影后的均值 和方差 是衡量类可分性的一个准那么。 vvi2i44 0vmhEiTiivx vvx2iTiiKhVar令 是任一准那么函数要最大或最小的，要确定使f最大小的v和v0。 222121，fvvvvv221122222121fffff022011022220

18、21210vfvfvfvfvf45由于 v2v2iiKiimv002vi10vi代入，有： 0v2212211222121ffmfmfKfKf46由以上两式可以计算出v，但由于错误率只依赖v的方向，而不是它的大小。因而可以消去v的常数系数不是mi和ki的函数。 解出： 121211vmmKssK式中， 222121fffs47 注意，上面得出的v和f无关，f只是出现在s中。 回想在正态、等协方差的情况下，有 这里是用s和(1s)对K1和K2作加权平均。当f的具体形式给出后，v0是 的解。1212vmmK021ff48例例1：Fisher线性分类器。 2221221f 222212212221f

19、f因此s0.5 Fisher准那么不依赖于v0。因为v0从 和 相减中消失了。 121212121mmkkv最正确的1249例例2 2：另种准那么是：另种准那么是 解出后有 Fisher准那么不能确定v0。 类内散度类间散度 222211222211ppppf1ps 1212211vmmKpKp22110mpmpvTv502.5 分类器的错误率问题 对样本进行分类是PR的任务之一。在分类过程中总会有错误率，领先验概率和类条件密度函数，采用的决策规那么也确定后，错误率也就固定了。 错误率反映了模式分类问题本身的固有复杂程度。也是衡量分类器性能的重要指标。分类器是否和要解决的问题相匹配。一. 错误

20、率的计算和估计 51 xxxxdpPdpPePRrRr 122211 ePPePPrr2211 从上式可以看出，在x是多维时，P(e)的计算要进行多重积分。当类条件密度函数的解析形式比较复杂时，P(e)的计算相当困难。错误率的计算公式前面已经分析，对两类问题：52 由于错误率对模式识别系统的重要性和复杂性，人们对错误率的计算和估算方法进行了大量的研究。方法主要有以下几类： 按公式计算错误率； 估算错误率的上限； 从实验中估计错误率。 这一小节先讨论前两种方法。 53 正态分布且等协方差矩阵时； 当x的各分量间相互独立时； 参考清华的书，略。 下面讨论估计错误率上限的方法 二. 在一些特殊情况下

21、错误率的计算 54 模式可分性度量反映了模式分类的困难程度，和错误率有密切关系。既有理论上的意义，也用在特征抽取和选择等问题上。这一节介绍模式可分性的两种重要度量：偏离度divergence和Bhattacharyya距离。 泾渭清楚，西瓜瓤和籽 先对一般的概率密度函数定义这两个量。然后在多元高斯情况下，看看会有什么结果。 三. 模式可分性的度量 55 对于对数的似然比检验： 也是一个随机变量。它可以用两个密度函数 和 来描述。如以下图所示，当两个密度函数偏离较大时，错误率一定低，反之会大。 1.偏离度和Bhattacharyya距离 Tppxxlnx211p 2p 56两类模式可分性的一种度

22、量是它们均值的差 ，称为偏离度D 。2157偏离度的定义为： 21xxEED xxxxxxxxdpppdppp221121lnln定义量： ijiijippEdpppjiHxxxxxxlnln，称为有单向偏离度，或第i类相对第j类的相对信息。有些作者称它为Kullbackliebler数。 58由上两式可知 1221，HHD 这样，当相对信息H(1，2)和H(2，1)大时，D也大，可分性好。 可分性的另一种度量是Bhattacharyya距离： B21lnlnxxxdppB而量 ，有时称为Bhattacharyya系数。 xxxdppeB21B59 这两个量比起偏离度来，直观上更难解释。但假设

23、将 写为： B 221221BppEdpppxxxxxx 我们可以给出Bhattacharyya距离的一种解释，如以下图： 6061 假设原来的两个密度函数分的较开，那么f相对于2的期望将较小1。 这时的ln值将会大，Bhattacharyya距离将会大。 62 反之，假设p1 (x)和p2 (x)近似重叠，那么期望值将较大，ln将较小。即Bhattacharyya距离小。如以下图： 63 偏离度和B距离是真的距离度量吗？ 偏离度和Bhattacharyya距离都满足： 1.在一对一的线性变换下不变；2. 当x的分量独立时，这两个量都满足相加性对每个成分。 64 令 表示偏离度或Bhattac

24、haryya距离，有： 21Jd，21210Jd ，02211JJdd，1221JJdd， 但它们都不满足距离的三角不等式，所以都不是真实的距离。但它们满足下面的性质： 21121JJdd，65 对于高斯分布的数据，可以推导出它的偏离度的封闭形式解。 2.高斯分布下的偏离度和Bhattacharyya距离 12111121222121xx21xx21xxKKmKmmKmppTTlnln而 12122xx2121mKmEHT，121111121xx21KKmKmETln66由于 iiTiiiTimxKmxtrmxKmx11而且由 ABtrBAtr有 11111xxmKmETItrKtrKmmtr

25、KET11111111xx67和 12122xxmKmET12212xxmmtrKETTmmmmKtrK2121112211221112mmKmmKtrKTI1122121KKtrH ，122112212121KKmmKmmTln68同样，有： I2112112KKtrH，211211122121KKmmKmmTln 1221，HHD2112112121mmKKmmTI221112211KKKKtr 这就是高斯分布的偏离度。 69 对于高斯分布的Bhattacharyya距离，有相似的推导。 xxxdppB21ln412411221lnKKn xxxxx21221111dmKmmKmTT41-

26、exp70其中的指数项可以化为： 21221111xxxxmKmmKmTT41111111111x2xxmKmKmKTTT41212212212x2xxmKmKmKTTTcmKmKmKppTppTppT111x2xx21可以化为71其中12111KKKp21212111mKmKKmpp21ppTpTTmKmmKmmKmc12122111124172 2124124112121pncPKeKKKBlnxxx1dmKmppTp21-exppKKKc21221121ln73可以证明 ppTpTTmKmmKmmKmc12122111124121121212mmKKmmT81 以及 2122112121

27、221121KKKKKKKp 74证明的思路和技巧：定义量 先证明 21KKKA21111121211pAAKKKKKKK由此再证： 111212111KKKKKKKppA以及 2121111， iKKKKKipiiA75由上面各种关系证明和。 这是对于高斯分布的Bhattacharyya距离。 21221121211212121212KKKKmmKKmmBTln8176由上式的B和前面的 可以看出，当两类的协方差矩阵相等时，K1= K2= K， 此时的D 和B 是等价的度量，而且和两类均值间的马氏距离等价。说明D 和B 确是两类间偏离和距离的一种度量。 2112112111221121221

28、mmKKmmKKKKtrDTIBmmKmmDT82112177 上一小节定义了偏离度和Bhattacharyya距离。下面分析它们和错误率的关系。 这一节讨论似然比检验的错误率的上界。它们是基于Bhattacharyya距离及其推广。 四. 错误率的Bhattacharyya和Chernoff界 1.最小错误率的上界 最小错误率有时也叫贝叶斯错误率eB 为：78 xxxx122211dpPdpPeRrRrB xxxdpPpPrr min-2211，利用不等式 0 minbaabba，上式可以化为： xxx212121dppPPerrB 即 BBrrBeePPe21212211 这个结果称为Bhattacharyya界