北京大学：《模式识别》课程教学资源（课件讲稿）线性判别函数（第一部分）

1.0引言 分类器 9 第四章线性判别函数 功能结构 92 MAX a(x) 基于样本的Bayes分类 2009-10-27 设计相应 的判别函数。 ■最一般情况下适用的“最 优”分类器：错误幸/风 样本分布的 决策规则： 险最小，对分类器设计 在理论上有指导意义， 训练样本年 统计特征： 判别函数 概率密度函数 决策面方程 获取统计分布及其参数 很困难，实际问题中并 1.0引言 1.1线性判别函数的基本概念 口基于样本的直接确定判别函数方法： 口特点 ■针对各种不同的情况，使用不同的准则函数，设 计出满足这些不同准则要求的分类器。 ■形式最简单 ■这些准则的“最优”并不一定与错误率最小相一致： 次优分类器。 ■容易实现 ■实例：正态分布最小错误率贝叶斯分类器在特殊 ■所需计算量和存储量小 情况下，是线性判别函数gx)尸w(决策面是超 平面)，能否基于样本直接确定w? ■线性判别函数是统计模式识别的基本方法。 选择最佳准则 决策规则 训练样本集 判别酒数 决策面方程 1.1线性判别函数的基本概念 1.1线性判别函数的基本概念 口d维空间中的线性判别函数的一般形式： 口两类问题的分类决策规则 g(x)=g(x)-82() g(x)=w'x+@o; g(x)>0,则决策x∈a, 如果 g(x)<0, 则决策x∈2 其中，x是样本向量，即样本在d维特征空间中 g()=0,可将其任意分类或拒绝 的描述；W是权向量，@是一个常数（闲值权）。 ■gx)=0是分类面（决策面）方程，将特征空间 分成决策区域。 X=[x,x2,x',w=[w,w2,w; ■w是分类面的法向量； ■00是分类面相对于原点的偏移； ■设计线性分类器的关键是给出估计w和w0的准则

第四章 线性判别函数 2009-10-27 2 1.0 引言 基于样本的Bayes分类 器：通过估计类条件概 率密度函数，设计相应 的判别函数。 MAX g1 . . . g2 gc . . . x1 x2 xn a(x)  最一般情况下适用的“最 优”分类器：错误率/风 险最小，对分类器设计 在理论上有指导意义。  获取统计分布及其参数 很困难，实际问题中并 不一定具备获取准确统 计分布的条件。 训练样本集 样本分布的 统计特征： 概率密度函数 决策规则： 判别函数 决策面方程 分类器 功能结构 3 1.0 引言 基于样本的直接确定判别函数方法：  针对各种不同的情况，使用不同的准则函数，设 计出满足这些不同准则要求的分类器。  这些准则的“最优”并不一定与错误率最小相一致： 次优分类器。  实例：正态分布最小错误率贝叶斯分类器在特殊 情况下，是线性判别函数 g(x)=wTx（决策面是超 平面），能否基于样本直接确定w? 训练样本集 决策规则： 判别函数 决策面方程 选择最佳准则 4 1.1 线性判别函数的基本概念  特点  形式最简单；  容易实现；  所需计算量和存储量小；  线性判别函数是统计模式识别的基本方法。 5 1.1 线性判别函数的基本概念  d 维空间中的线性判别函数的一般形式： 其中，x是样本向量，即样本在 d 维特征空间中 的描述；w 是权向量，ω0是一个常数（阈值权）。 0 () ; T g x x   w   12 1 2 , ,... , , ,... ;    T T d d x w   xx x ww w 6 1.1 线性判别函数的基本概念  两类问题的分类决策规则  g(x) = 0 是分类面（决策面）方程，将特征空间 分成决策区域。  w 是分类面的法向量；  ω0 是分类面相对于原点的偏移；  设计线性分类器的关键是给出估计w和ω0的准则。 1 2 ( ) 0, ( ) 0, ( ) 0, g g g             x x x x x 则决策 如果 则决策 可将其任意分类或拒绝 1 2 gg g () () () xxx  

11线性判别函数的基本概念 1.2广义线性判别函数 口线性判别函数的几何意义 口线性判别函数是形式最为简单的判别函数；但是 ■gx)是点x到决策面H的距离的一种代数度量。 它局限性较大，不能用于复杂情况。 方向 ■例：设计一个一维分类器，使其功能为： x=x,+r W g(x)=rlwl: 如果r<b或x>a 则决策x∈E b≤x≤a 则决策x∈ R1:g>0 ·r是x到H的垂直距离： 一判决函数： ·I,是x在H上的投影向量： g(x)=(x-a(x-b): ·一片是原点到快策面的距离。 一判决规则： R,:g<0 如果)>0 则决策xe H:g-0 g(x)≤0，则决策xe, 1.2广义线性判别函数 1.2广义线性判别函数 口对非线性判别函数gx),可通过适当的变换转化 口例：如x=xx了，二次判别函数为 为线性判别函数g(y)。 8(x)=c+Bx+xAx; ■二次判别函数的一般形式 ■定义y=[x,x,x,x,x,则可找到a,ao,使 8(x)=co+cx+cx; 映射X一Y g'(y)=a'y+ao=g(x). 片1「17 「a =x a= = →g)=ay-2ay=8 1.2广义线性判别函数 1.2广义线性判别函数 口任何非线性函数gx)都可通过级数展开转化成高 口一种特殊映射方法：增广样本向量y与增广权 次多项式（逼近），故任何非线性判别函数都可 向量a 转化成广义线性判别函数来处理。 y[-a[], 口问题： L ■实现这种转化的非线性变换可能非常复杂； 口线性判别函数的齐次简化： ■变换空间的维数可能非常高。（维数灾难） g(x)=wx+@o=a'y; ■增广样本向量使特征空间增加了一维，但保持了 样本间的欧氏距离不变，对于分类效果也与原决 策面相同，只是在Y空间中决策面是通过坐标原 点的。 类似于直战方程y一上红☐

7 1.1 线性判别函数的基本概念  线性判别函数的几何意义  g(x) 是点 x 到决策面 H 的距离的一种代数度量。 0 0 , () ; p p r gr r H H r        w xx x w w x x x w 是 到 的垂直距离; 是 在 上的投影向量; 是原点到决策面的距离。 方向 8 1.2 广义线性判别函数  线性判别函数是形式最为简单的判别函数；但是 它局限性较大，不能用于复杂情况。  例：设计一个一维分类器，使其功能为： — 判决函数： — 判决规则： 1 2 b a xb xa x x x          或 则决策 如果 则决策 g( ) ( )( ) x x axb   ； 1 2 ( ) 0, ( ) 0, gx x gx x          则决策 如果 则决策 9 1.2 广义线性判别函数  对非线性判别函数 g(x)，可通过适当的变换转化 为线性判别函数 g’(y)。  二次判别函数的一般形式 3 1 '( ) ( ). T i i i g a y g x   y ay    2 01 2 g( ) x c cx cx   ； 1 10 2 21 2 3 32 y 1 a c y x ac y x ac                     y a ， ； 10 1.2 广义线性判别函数  例：如 x=[x1, x2]T，二次判别函数为  定义 则可找到a，a0，使 ( ) T g x xx x   cB A ； 2 2 1 2 1 2 12 [ , , , , ], T y  x x x x xx 0 '( ) ( ). T g ag y   a y x 11 1.2 广义线性判别函数  任何非线性函数 g(x) 都可通过级数展开转化成高 次多项式（逼近），故任何非线性判别函数都可 转化成广义线性判别函数来处理。  问题：  实现这种转化的非线性变换可能非常复杂；  变换空间的维数可能非常高。（维数灾难） 12 1.2 广义线性判别函数  一种特殊映射方法：增广样本向量 y 与增广权 向量 a  线性判别函数的齐次简化：  增广样本向量使特征空间增加了一维，但保持了 样本间的欧氏距离不变，对于分类效果也与原决 策面相同，只是在Y空间中决策面是通过坐标原 点的。   1,..., ,1 ; 1 T d x x         x y   1 0 0 ,..., , ; T w wd           w a 0 () ; T T g x wx ay    类似于直线方程 y = kx

1.2广义线性判别函数 1.3线性分类器设计步骤 口举例：设在三维空间中一个类别分类问题拟采用 口线性分类器设计任务：给定样本集K,确定线性 二次曲面。如采用广义线性方程求解，试求其广 判别函数gx)=wx的各项系数w. 义样本向量与广义权向量的表达式，及其维数。 口步骤： ■收集一组样本K={,,Xw axi +bxi+cx+drp;+xx;+++h++m= ■按需要确定一个准则函数K,W,其值反映分类 器的性能，其极值解对应于“最好”决策， a=(a.b.c,d.e.f.g,h.l,m)' ■用最优化技术求准则函数J的极值解w*,从而 智 y=(2,2,x,x2,X3x2,,2,1) 确定判别函数，完成分类器设计。 了广义线性 w*=argmaxJ(K,w)方 维数为10 :=g(x)=g'y)=y 判别函数 →对于未知样本x,计算gx),判断其类别。 2.Fisher线性判别(FDA) 2.Fisher线性判别（FDA) 口线性判别函数y=gx)=w: 口图例 ■样本向量x各分量的线性加权； ■样本向量x与权向量w的向量点积； ■如果Iw作1，则视作向量x在向量w上的投影. 口Fisher准则的基本原理：找到一个最合适的投 影轴，使得 ■两类样本在该轴上投影之间的距离尽可能远； ■每一类样本的投影尽可能紧凑； Fisher准则的描述：用投影后数据的统计性质 ◆从而使分类效果为最佳。 均值和离散度的函数作为判别优劣的标准。 2.Fisher?线性判别(FDA) 2.Fisher线性判别(FDA) 口符号含义 口d雏空间样本分布的描述量 ■m,m分别表示两类（原始）数据的均值向量； ■各类样本均值向量m ■S,S2分别表示两类（原始）数据的离散度矩阵； ■样本类内离散度矩阵S与总类内离散度矩阵S S=S+S2 ■m,m,分别表示两类（投影后，一维）数据的均 5=(x-mXx-m),i=1.2 5,=P(o)S,+P(@:)S: 值； ■样本类问离散度矩阵了，，=(m-m,m-m ■5，S,分别表示两类（投影后，一维）数据的离 S=P@)P(am-mm-m广 散度 高散度矩阵在形式上与协方差矩阵很相似，但 协方差矩阵是一种期望值，而高散矩阵只是表 示有限个样本在空间分布的高散程度

13 1.2 广义线性判别函数  举例：设在三维空间中一个类别分类问题拟采用 二次曲面。如采用广义线性方程求解，试求其广 义样本向量与广义权向量的表达式，及其维数。 14 1.3 线性分类器设计步骤  线性分类器设计任务：给定样本集 K，确定线性 判别函数 g(x) = wTx 的各项系数 w。  步骤：  收集一组样本 K={x1, x2,…, xN}；  按需要确定一个准则函数 J(K, w)，其值反映分类 器的性能，其极值解对应于“最好”决策。  用最优化技术求准则函数 J 的极值解 w*，从而 确定判别函数，完成分类器设计。 对于未知样本 x，计算 g(x)，判断其类别。 * arg max ( , );  J w w w K 15 2. Fisher线性判别（FDA）  线性判别函数 y = g(x) = wTx ：  样本向量 x 各分量的线性加权；  样本向量 x 与权向量 w 的向量点积；  如果 || w ||=1，则视作向量 x 在向量 w 上的投影。  Fisher准则的基本原理：找到一个最合适的投 影轴，使得  两类样本在该轴上投影之间的距离尽可能远；  每一类样本的投影尽可能紧凑； 从而使分类效果为最佳。 16 2. Fisher线性判别（FDA）  图例 Fisher准则的描述：用投影后数据的统计性质— 均值和离散度的函数作为判别优劣的标准。 17 2. Fisher线性判别（FDA）  符号含义  m1, m2 分别表示两类（原始）数据的均值向量；  S1, S2 分别表示两类（原始）数据的离散度矩阵;  分别表示两类（投影后，一维）数据的均 值；  分别表示两类（投影后，一维）数据的离 散度. 1 2 ~, ~ m m 1 2 S S,   18 2. Fisher线性判别（FDA）  d 维空间样本分布的描述量  各类样本均值向量 mi :  样本类内离散度矩阵 Si 与总类内离散度矩阵Sw:  样本类间离散度矩阵 Sb: 1 1, 2; i i i x i N     x K m ( )( ) , 1, 2; i T i ii i    x x x K S mm 1 2 11 2 2 ; () (); w w P P       S SS S SS 1 21 21 2 1 21 2 ( ) ( )( )( ) ( )( ) ; . T b T b   P P     S m mm m S mmmm 离散度矩阵在形式上与协方差矩阵很相似，但 协方差矩阵是一种期望值，而离散矩阵只是表 示有限个样本在空间分布的离散程度

2.Fisher?线性判别(FDA) 2.Fisher线性判别(FDA) 口一维投彩空间(Y空间)样本分布的描述量 口样本x与其投影y的统计量之间的关系： ■各类样本均值： A发三12 ■样本类内离散渡和总类内离散度： =∑wx=wm,i=l2 5=∑0-m,1=1,2 5=+: ■样本类间离散度：S。=(m-m) 5,=(m-m2)2=(wm-w'm) =w (m-m)(m-m2)w=w'S,w; 以上定义描迷d维空间样本点到一个向量投形的分 散情况，因此也就是对时某向量w的投形在w上的 分布。样本离数度的定义与随机变量方差相类似， 2.Fisher?线性判别(FDA) 2.Fisher线性判别（FDA) 口样本x与其投影y的统计量之间的关系： 口评价投影方向w的原则：使原样本向量在该方 S,=∑0y-m 向上的投影能兼顾类间分布尽可能分开，类内样 e到 本投影尽可能密集的要求。 =∑(wx-w'm, 口Fisher准则函数的定义： XEK, 类间离散度☐ 5 =w∑-m,x-m,y Jr(w)=5+5: wS.w wS.w [总类内离散度 -wSw. 口Fisher最佳投影方向的求解： w*=argmaxJ(w). S.=S+S=w(S+S2)w=wS.w. 2.Fisher?线性判别(FDA) 2.Fisher线性判别(FDA) 口Fisher准则的合理性 口Fisher最佳投影方向的求解 ■(w)只与投影方向有关，与w大小无关一如 ■求出最佳投影方向上任何一个w即可。 果w是一个最优解，则w也是最优解(k是任 意不为零的常数。) ■(w)有上界，最佳投影方向一定存在！ 口Fisher最佳投影方向的求解要求 J(w)s4(S.) (S)min S=S+S2正定； ■否则，存在投影方向w,使得w'Sw=0: (S)mx,(S)mm分别是矩阵S。,S的最大、最 小特征根。 即，所有数据被投影到一点上！J(w)没有极大 值

19 2. Fisher线性判别（FDA）  一维投影空间(Y空间)样本分布的描述量  各类样本均值：  样本类内离散渡和总类内离散度：  样本类间离散度： 1 , 1, 2; i i i y m yi N      2 ( ) , 1, 2; i i i y S ym i       1 2 ; w S SS     2 1 2 ( ). b S mm      以上定义描述 d 维空间样本点到一个向量投影的分 散情况，因此也就是对某向量 w 的投影在 w 上的 分布。样本离散度的定义与随机变量方差相类似。 20 2. Fisher线性判别（FDA）  样本 x 与其投影 y 的统计量之间的关系： 1 1 , 1, 2; i i T i i T i i y m y i N N        x w x w K  m 2 2 12 1 2 1 21 2 ( )( ) ( )( ) ; b T T T b T T S m m S      w w w w w w m m mmmm    21 2. Fisher线性判别（FDA）  样本 x 与其投影 y 的统计量之间的关系： 2 2 ( ) ( ) ( )( ) ; i i i i y T T i T T i i T i i S S y m                    x x wx wm w x x w w w K K m m   12 12 () . T T w w S S      SS SS   w w w w 22 2. Fisher线性判别（FDA）  评价投影方向 w 的原则：使原样本向量在该方 向上的投影能兼顾类间分布尽可能分开，类内样 本投影尽可能密集的要求。  Fisher 准则函数的定义：  Fisher 最佳投影方向的求解： * arg max ( ). F  J w w w 1 2 () ; T b b F T w S S J S S S    w w w w w    类间离散度 总类内离散度 23 2. Fisher线性判别（FDA）  Fisher 准则的合理性  JF(w) 只与投影方向有关，与 w 大小无关 — 如 果 w 是一个最优解，则 kw 也是最优解（ k 是任 意不为零的常数。）  Fisher 最佳投影方向的求解要求  否则，存在投影方向 w ，使得 即，所有数据被投影到一点上！JF(w) 没有极大 值。 1 2 S SS w   正定； 0 T w w w S  ； 24 2. Fisher线性判别（FDA）  Fisher 最佳投影方向的求解  求出最佳投影方向上任何一个 w 即可。  JF(w) 有上界，最佳投影方向一定存在！ 分别是矩阵 的最大、最 小特征根。 max min ) () ; ) b F w S J S   w  （ （ max min ), ) b w （ （ S S  b w S S

2.Fisher?线性判别(FDA) 2.Fisher线性判别（FDA) 口Fisher最佳投影方向的求解 口Fisher最佳投影方向的求解 ■因为S正定，一定存在一个最优化的W,满足 ■采用拉格朗日乘子算法解决带约束的最优化： wSw-l: 定义Lagrange函数 L(w,i)=w"S,w-A(w"S.w-I); wS.w ■无约束最优化：max wS.w 令 等价于带约束的最优化 aL(w,》=S,w-2Sw=0, Ow maxwSw,s.l.wS.w=1. 最优解满足：Sw*-Sw*=0, 2.Fisher线性判别(FDA) 2.Fisher线性判别(FDA) 口Fisher最佳投影方向的求解 口Fisher最佳投影方向的求解 根据类间离散度S。的定义： w*=S(m,-m2)=(S+S2)'(m-m2)片 2w*=S-S,w*=Sn-(m,-m2m,-m2)w*, 注意： (m,-m2)了w*是一个数，记作R m1-m,是一个向量，对与(m,m)平行的向量投影 可使两均值，点的距离最远。但是如从使类间分得较 开，同时又使类内密集程度较高这样一个综合指标 W*= m-m,)=S(m,-m, 来看，则需根据两类样本的分布离散程度对投影方 向作相应的调整，这就体现在对mm2向量按S 作一线性变换，从而使Fisher准则函数达到极值，点 被忽略，因为只关心投影方向 2.Fisher?线性判别(FDA) 2.Fisher线性判别(FDA) 口一维分类问题 例：设两类样本的类内离散矩阵分别 ■当d和N很大时，y近似正态分布，可在Y空 为S1,S,各类样本均值分别为 s 间内用Bayes分类器。 m,-(2,0,m,-(2,2y,试用Fisher?准 则求其决策面方程。 s4周 ■利用先验知识确定一维分类阈值0 Fisher:谁则 为二所+应 人=应士N应=应 =+52=P07 02 一景佳授影 2 N+N, w*=S(m,-m2)= 9][9 [0.5 由于两类样本分布形状是相同的（只是 ■决策规则：对任意x 方向不同)，因此%应为（投影后）两 y=w*x=J y=w*x三y>→IeO 类均值的中点： y<%→X∈02 人-+应=(m+m.- 即0-3）】 2 2 Fisher准刚最佳分界面

25 2. Fisher线性判别（FDA）  Fisher 最佳投影方向的求解  因为 正定，一定存在一个最优化的 w，满足  无约束最优化： 等价于带约束的最优化 1 T w w w S  ； w S max T b T w S S w w w w max , . . 1. T T b w ww ww S st S  26 2. Fisher线性判别（FDA）  Fisher 最佳投影方向的求解  采用拉格朗日乘子算法解决带约束的最优化： Lagrange : ( , ) ( 1); T T L SS w ww ww     b w 定义 函数 (,) : 0; b w L S S       w w w w 令 * * 0; b w 最优解满足：S S w w    27 2. Fisher线性判别（FDA）  Fisher 最佳投影方向的求解 1 1 1 21 2 * * (m m )(m m ) *; b T wb w S  SS S   ww w    根据类间离散度 的定义： 1 2 (m m ) * T 注意： 是一个数，记作 ；  w R 1 1 12 12 ( ) ( ). w w R S S    w mm mm     被忽略，因为只关心投影方向 28 2. Fisher线性判别（FDA）  Fisher 最佳投影方向的求解 1 1 1 2 12 1 2 ( ) ( ) ( ). w S SS   w mm mm      m1-m2 是一个向量，对与 (m1-m2) 平行的向量投影 可使两均值点的距离最远。但是如从使类间分得较 开，同时又使类内密集程度较高这样一个综合指标 来看，则需根据两类样本的分布离散程度对投影方 向作相应的调整，这就体现在对 m1-m2 向量按 Sw -1 作一线性变换，从而使Fisher准则函数达到极值点。 29 2. Fisher线性判别（FDA）  一维分类问题  当 d 和 N 很大时，y 近似正态分布，可在 Y 空 间内用Bayes 分类器。  利用先验知识确定一维分类阈值 y0：  决策规则: 对任意 x 1 2 0 2 m m y     ； 11 2 2 0 1 2 Nm Nm y m N N       ； 0 1 0 2 . T y y y y y          x w x x 30 由于两类样本分布形状是相同的（只是 方向不同），因此 y0 应为（投影后）两 类均值的中点： 12 1 2 0 ( ) 1; 2 2 T m m y        w mm 1 1 2 0.5 0 0 0 () ; 0 0.5 2 1 w S                       w mm 2. Fisher线性判别（FDA） 1 2 2 0 ; 0 2 w S SS         Fisher准则 最佳投影 0 2 1 2 ; (0, 1) 1. T x y y x x               w x 即 Fisher准则最佳分界面