第三章 分类器的设计 线性分类器的设计 分段线性分类器的设计 非线性分类器的设计.

Presentation on theme: "第三章 分类器的设计 线性分类器的设计 分段线性分类器的设计 非线性分类器的设计."— Presentation transcript:

1 第三章 分类器的设计 线性分类器的设计 分段线性分类器的设计 非线性分类器的设计

2 §3-1 线性分类器的设计 上一章我们讨论了线性判别函数形式为:g(x)=WTX 其中 X= (X1, X2…Xn) n维特征向量
W= (W1, W2 … Wn , Wn+1) n维权向量 通常通过特征抽取可以获得n维特征向量，因此n维 权向量是要求解的。 求解权向量的过程就是分类器的训练过程，使用已 知类别的有限的学习样本来获得分类器的权向量被称为 有监督的分类。

3 利用已知类别学习样本来获得权向量的训练过程如下
W1 X1 x1 w1 W2 X2 g(x)=wTx x2 w2 >0 x∈ω1 ∑ ……. <0 x∈ω2 xn wn Wn Xn 检测 (已知类别) 1 wn+1 Wn+1 已知x1 ∈ω1, 通过检测调整权向量，最终使x1 ∈ω1 已知x2 ∈ω2, 通过检测调整权向量，最终使x2 ∈ω2 这样就可以通过有限的样本去决定权向量

4 利用方程组来求解权向量 对二类判别函数g(x) = W1X1+ W2X2 +W3 已知训练集：Xa, Xb, Xc, Xd且 当 (Xa, Xb) ∈W1时 g(x)＞0 当 (Xc, Xd) ∈W2时 g(x)＜0 设 Xa = (X1a, X2a)T Xb = (X1b, X2b)T Xc = (X1c, X2c)T Xd = (X1d, X2d)T 判别函数可联立成： X1aW1+ X2aW2+ W3＞ ① X1bW1+ X2bW2+ W3＞ ② X1cW1+ X2cW2+ W3＜ ③ X1dW1+ X2dW2+ W3＜ ④ 求出W1 , W2, W3

5 所以 g(x) =WTX >0 其中W = (W1 , W2, W3)T
将③ ④式正规化，得 -X1cW1- X2cW2- W3 >0 -X1dW1- X2dW2- W3 >0 所以 g(x) =WTX >0 其中W = (W1 , W2, W3)T 为各模式增1矩阵 为N*(n+1）矩阵 N为样本数，n为特征数

6 训练过程就是对已知类别的样本集求解权向量w，
这是一个线性联立不等式方程组求解的过程。 求解时： ① 只有对线性可分的问题，g(x) =WTX才有解 ② 联立方程的解是非单值，在不同条件下，有不同的解，所以就产生了求最优解的问题 ③ 求解W的过程就是训练的过程。训练方法的共同点是，先给出准则函数，再寻找使准则函数趋于极值的优化算法，不同的算法有不同的准则函数。算法可以分为迭代法和非迭代法。

7 一 梯度下降法—迭代法 W2 = W1-ρ1▽J(W1) 欲对不等式方程组WTX>0求解，首先定义准则函数(目
标函数)J(W)，再求J(W)的极值使W优化。因此求解权 向量的问题就转化为对一标量函数求极值的问题。解决 此类问题的方法是梯度下降法。 方法就是从起始值W1开始，算出W1处目标函数的梯度 矢量▽J(W1)，则下一步的w值为： W2 = W1-ρ1▽J(W1) W1为起始权向量 ρ1为迭代步长 J(W1) 为目标函数 ▽J(W1)为W1处的目标函数的梯度矢量

8 在第K步的时候 Wk+1 = Wk-ρk▽J(Wk) ρk为正比例因子 这就是梯度下降法的迭代公式。这样一步步迭代 就可以收敛于解矢量，ρk取值很重要 ρk太大，迭代太快，引起振荡，甚至发散。 ρk太小，迭代太慢。 应该选最佳ρk。

9 选最佳ρk 目标函数J(W)二阶台劳级数展开式为 J(W)≈J(Wk)+ ▽JT(W- Wk)+(W- Wk)TD(W- Wk)T/2 ①
其中D为当W = Wk时 J(W)的二阶偏导数矩阵 将W=Wk+1 = Wk-ρk▽J(Wk)代入①式得： J(Wk+1) ≈J(Wk)- ρk||▽J||2+ ρk2▽JT D▽J 其中▽J=▽J(Wk) 对ρk求导数 ，并令导数为零有 最佳步长为ρk=||▽J||2/▽JTD▽J 这就是最佳ρk的计算公式，但因二阶偏导数矩阵D的计算 量太大，因此此公式很少用。

10 若令W=Wk+1上式为 J(Wk+1)=J(Wk)+▽JT(Wk+1-Wk)+(Wk+1-Wk)TD(Wk+1-Wk)T/2 对Wk+1求导，并令导数为零可得： 最佳迭代公式：Wk+1= Wk- D-1▽J —牛顿法的迭代公式 D-1是D的逆阵 讨论：牛顿法比梯度法收敛的更快，但是D的计算量大并且要计算D-1。当D为奇异时，无法用牛顿法。

11 二 感知器法 感知器的原理结构为：

12 通过对W的调整，可实现判别函数g(x) =WTX > RT
定义感知准则函数：只考虑错分样本 定义： 其中x0为错分样本 当分类发生错误时就有WTX <0，或－WTX >0, 所以J(W) 总是正值，错误分类愈少， J(W)就愈小。 理想情况为 即求最小值的问题。

13 求最小值对W求梯度 代入迭代公式中Wk+1 = Wk-ρk▽J 由J(W)经第K+1次迭代的时候，J(W)趋于0，收敛于所求的W值

14 5 3 x3 4 2 x2 H1 x1 H W的训练过程： 例如:x1, x2, x3∈ω1 作 x1, x3的垂直线可得解区(如图)
假设起始权向量w1=0 ρk = 1 1. x1, x2, x3三个矢量相加得矢量2,垂直于矢量2的超平面H将x3错分. 2. x3与矢量2相加得矢量3,垂直于矢量3的超平面H1,将x1错分. 3.依上法得矢量4,垂直于矢量4做超平面, H2将x3错分 4. x3与矢量4相加得矢量5,矢量5在解区内,垂直于矢量5的超平面可以把 x1, x2, x3分成一类 。 5 3 x3 4 2 x2 H1 W区间 x1 H H2

15 + 感知器算法： 1.错误分类修正wk 如wkTx≤0并且x∈ω1 wk+1= wk-ρkx
H + - wk+1 wk ρkx 权值修正过程

16 ρk选择准则 ①     固定增量原则 ρk固定非负数 ②     绝对修正规则 ρk> ③ 部分修正规则 ρk=λ ＜λ≤2

17 例题：有两类样本 ω1=（x1,x2）={(1,0,1),(0,1,1)} ω2=（x3,x4）={(1,1,0),(0,1,0)} 解：先求四个样本的增值模式 x1=(1,0,1,1) x2=(0,1,1,1) x3=(1,1,0,1) x4=(0,1,0,1) 假设初始权向量 w1=(1,1,1,1) ρk=1 第一次迭代： w1Tx1=(1,1,1,1) (1,0,1,1)T=3>0 所以不修正 w1Tx2=(1,1,1,1) (0,1,1,1)T=3>0 所以不修正 w1Tx3=(1,1,1,1) (1,1,0,1)T=3>0 所以修正w1 w2=w1-x3=(0,0,1,0) w2Tx4=(0,0,1,0)T (0,1,0,1) = 所以修正w2 w3=w2-x4=(0,-1,1,-1) 第一次迭代后,权向量w3=(0,-1,1,-1),再进行第2,3,…次迭代 如下表

18 直到在一个迭代过程中权向量相同，训练结束。 w6=w=(0,1,3,0) 判别函数g(x)= -x2+3x3
训练样本 wkTx 修正式 修正后的权值wk＋1 迭代次数 x x x x + w1 w1-x3 w2-x4 0 – 1 - w3+x1 w4 w4-x3 w5 1 – 0 –2 2 –1 0 – 2 w5+x2 w6 0 – 3 4 直到在一个迭代过程中权向量相同，训练结束。 w6=w=(0,1,3,0) 判别函数g(x)= -x2+3x3 感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点.

19 对于线性可分的样本集，可以用上述方法解到正确分
线性不可分样本集的分类解(取近似解) 对于线性可分的样本集，可以用上述方法解到正确分 类的权向量。当样本集线性不可分时，用上述方法求权 值时算法不收敛。如果我们把循环的权向量取平均值作 为待求的权向量，或就取其中之一为权向量，一般可以 解到较满意的近似结果。 例：在样本 ω1: X1 =（0,2） X3 =（2,0） X5 =（-1,-1） ω2: X2 =（1,1） X4 =（0,-2） X6 =（-2,0） 求权向量的近似解 x2 x1 x2 1 x6 x3 x1 －2 1 x5 H x4 －2

20 解：此为线性不可分问题，利用感知器法求权向量
权向量产生循环(-1, 2, 0), (0, 2, 2), (-1, 1, 1), (-1, 1, 1) (-1, 1, 1), (0, 0, 0), (-1, 2, 0) 因此算法不收敛，我们可以取循环中任一权值，例如取 W=(0,2,2)T 则判别函数为： g(x)= 2x1+2x2 判别面方程为： g(x)= 2x1+2x2＝0 所以x1+x2＝0 由图看出判别面H把二类分开，但其中x2错分到ω1类， 而x1错分到ω2类，但大部分分类还是正确的。

21 作业：已知四个训练样本 w1={(0,0),(0,1)} w2={(1,0),(1,1)} 使用感知器固定增量法求判别函数 设w1=(1,1,1,1) ρk=1 要求编写程序上机运行，写出判别函数，并打出图表。

22 三 最小平方误差准则(MSE法)---非迭代法
前面我们研究了线性不等式方程组g(x) =WTX>0的解法。它们共同点是企图找一个权向量W，使错分样本最小。 现在我们把不等式组变成如下形式：WTXi=bi>0 则有联立方程XW=b 这是矛盾方程组，方程数大于未知 数，所以没有精确解的存在。 每个样本有n个特征

23 定义误差向量：e=XW-b≠0 把平方误差作为目标函数
W的优化就是使J(W)最小。求J(W)的梯度并为0。 解上方程得 XTXW=XTb 这样把求解XW=b的问题，转化为对XTXW=XTb求解，这 一有名的方程最大好处是因XTX是方阵且通常是非奇异的， 所以可以得到W的唯一解。 MSE准则函数

24 最小平方误差法同Fisher法是一致的。
只要计算出X+就可以得到W 取： 最小平方误差法同Fisher法是一致的。 （MSE 解） 其中N/N1有N1个，N/N2有N2个

25 四 韦—霍氏法（LMS法）迭代法 上节得到MSE法的W解为：W=X+b 在计算X+时， 计算量很大 1． 要求XTX矩阵为非奇异
2．  由于计算量太大而引入比较大误差 所以要用迭代法来求 求J(W)的梯度 ▽J(W) =2XT(XW-b) 代入迭代公式 W1任意设定 Wk+1 = Wk-ρkXT(XWk-b) 此法可收敛于W值。W满足: XT(XW-b)=0 计算量很大

26 因此下降算法不论XTX是否奇异，总能产生一个解。
若训练样本无限的重复出现，则简化为 W1任意 Wk+1=Wk+ρk(bk-WkTXk) Xk ρk随迭代次数k而减少，以保证算法收敛于满意的W值

27 五 何—卡氏法 （判断迭代过程中是否线性可分）
若训练样本线性可分时，感知器法可求出界面，但对不可分问题不 收敛只能取平均。最小平方误差法不论样本是否线性可分都能给出 一加权矢量，但不能保证此矢量就是分界矢量，下面介绍一种方法 可以检测迭代过程中是否线性可分。 因最小平方误差法的J(W)的解为 因为XW=b b应为正值 c为矫正系数 当（XWk-bk）≤0 时 当（XWk-bk）＞ 0 时

28 引入误差矢量ek ek=XWk-bk判断是否线性可分 所以J(W)的解为 初始条件 W1=X+b1并且b1>0 迭代时检测 如果ek≥0时，XW >b，系统线性可分，迭代收敛 如果ek<0时，XW <b，系统线性不可分，迭代不收敛 我们用下面的例子来说明ek的作用 因此上式可以写成

29 例题： ω1={(0,0)T,(0,1)T} ω2={(1,0)T,(1,1)T} 解：正规化 对ω2取负，有 x2 x4 x2 x3 x1 x1 X的规范矩阵为

30 取b1=(1,1,1,1)T c= W1=X+b1=(-2,0,1)T 所以W1为所求解 e1=XW1-b1=0 系统线性可分 因为

31 在算法进行过程中，应在每一次迭代时，检测ek 的值。 只要出现ek<0 ，迭代就应立即停止。 x2
若四个样本变成： ω1={(0,0)T,(1,1)T} ω2={(0,1)T,(1,0)T} 解： 取b1=(1,1,1,1)T c=1 W1=X+b1=(0,0,0)T e1=XW1-b1=(-1,-1,-1,-1)T<0 系统线性不可分 C为校正系数,取0＜ C ≤1 在算法进行过程中，应在每一次迭代时，检测ek 的值。 只要出现ek<0 ，迭代就应立即停止。  x2 1 1 x1

32 六 Fisher分类准则 x2 w 现在讨论通过 ω1 映射投影来降低 维数的方法。 y1 w(y) ω2
X空间 X=-WTX-W0 >0 X∈ω1 X=-WTX-W0 <0 X∈ω2 映射Y空间 Y=WTX-W0 >0 X∈ ω1 Y=WTX-W0 <0 X∈ω2 把X空间各点投影到Y空间得一直线上，维数由2维降为一 维。若适当选择W的方向，可以使二类分开。下面我们从 数学上寻找最好的投影方向，即寻找最好的变换向量W的 问题。 x2 w ω1 y1 w(y) ω2 y2 x1

33 投影样本之间的分离性用投影样本之差表示 投影样本类内离散度: i=1,2 i=1,2

34 类间散布矩阵

35 上式就是n维x空间向一维y空间的最好投影方向， 它实际是多维空间向一维空间的一种映射。
其中Sw为类内散布矩阵, Sb为类间散布矩阵

36 现在我们已把一个n维的问题转化为一维的问题。
现在一维空间设计 Fisher分类器: W0的选择           

37 Yki表示第i类中第k个样本的投影值 N1为ω1样本数 N2为ω2样本数  当W0选定后，对任一样本X，只要判断Y=WTX>0 则 X∈ω1; Y=WTX<0 则X∈ω2。分类问题就解决了

38 §3-2 分段线形分类器的设计 先求子类的权向量Wi l，再求总的权向量Wi 1. 已知子类划分时的设计方法
把每一个子类作为独立类，利用每个子类的训练样本， 求每个子类的线性判别函数，总的判别函数就可获得。 子类的划分可用以下方法： ①   用先验知识直接划分 ②   用聚类分析，聚成多个子类 2. 已知子类的数目的设计方法 ① 设各个子类的初始权向量：Wi 1 , Wi 2 …Wi li i = 1,2,…M Wi中有Li个子类 ② 若第K步迭代时ωj 类样本Xj 同ωj类某个子类的权向量Wj n (k)的内积值最大， 即Wj n (k)l xj = max{ Wj n (k)l xj } n = 1,2,…lj

39 并且满足条件Wj n (k) xj >Wi n (k)l xj
i =1,2,…M类 j =1,2,…li子类 i≠j 则权向量Wi 1 (k)，Wi 2(k)，… ,Wi li (k)不影响分类， 所以权向量不需要修正。 若有某个或某几个子类不满足条件即： 存在Wi n(k)使Wj n (k) xj ≤Wi n (k)l xj i≠j 所以xj 错分类，要修改权向量。 设Wi n (k)l xj = max{ Wi n (k)l xj } n = 1,2,…li i≠j 则修改权向量Wjn(k+1)= Wj n(k) ± ρkxj ③ 重复以上迭代,直到收敛,此法类似于固定增量法.

40 3.未知子类数目时的设计方法 当每类应分成的子类数也不知 时，这是最一般情况，方法很 多，举例如下。 树状分段线性分类器: 设两类情况ω1， ω2。如图所示 ① 先用两类线性判别函数求 出W1,超平面H1分成两个区 间,每个区间包含两类。 ②再利用二类分类求出W2(H2), W3(H3)。 ③ 如果每个部分仍包含两类, 继续上面的过程。

41 关键是初始权向量W1的选择:一般先选两类中距离最近的两个子类的均值连线做垂直线作为H1(w1)初始值再求最优解。
树状决策框图 Y N w1Tx>0 N Y N Y w2Tx≥0 w3Tx≥0 ω1 Y N ω2 ω1 w4Tx≥0 ω1 ω2 关键是初始权向量W1的选择:一般先选两类中距离最近的两个子类的均值连线做垂直线作为H1(w1)初始值再求最优解。

42 §3-3 非线性分类器的设计 电位函数分类器,用非线性判别函数区分线性不可分的类别
电位函数分类器:每个特征作为一个点电荷,把特征空间作为能量场. 电位分布函数有下面三种形式。 α为系数 xk为某一特定点 上图是这些函数在一维时的图形，第三条是振荡曲线， 只有第一周期才是可用范围。 K(x) 3 2 x x 1

43 电位函数算法的训练过程是在逐个样本输入时，逐渐积
累电位的过程，对于二类问题，经过若干循环后，如积 累电位方程的运算结果能以正、负来区分二类样本，则 训练就可结束。 算法: 设初始电位为K0(x)=0 1.输入样本x1计算积累电位K1(x) 若x∈ω1 K1(x)= K0(x)+K(xx1) 若x∈ω2 K1(x)= K0(x)-K(xx1) 设ω1为正电荷,ω2为负电荷 在K0(x)=0时 若x1∈ω1 K1(x)= K(xx1) 若x1∈ω2 K1(x)= -K(xx1)

44 2. 输入样本x2计算积累电荷有以下几种情况 a. 若x2∈ω1 并且K1(x2)>0 若x2∈ω2 并且K1(x2)<0 K1(x)= K2(x) 不修正 b. 若x2∈ω1 并且K1(x2)≤0 若x2∈ω2 并且K1(x2)≥0 K2(x)= K1(x)±K(xx2)= ±K1(xx1)±K(xx2) 修正 直到第k+1步,已输入x1, x2, ….xk个样本

45 积累电荷Kk+1(x)有三种情况: 1.若xk+1∈ω1并且Kk(xk+1)>0或xk+1∈ω2 并且Kk(xk+1)<0 则Kk+1(x)= Kk(x) 不修正 2. 若xk+1∈ω1并且Kk(xk+1) ≤0 则Kk+1(x)= Kk(x)+K(xxk) 3. 若xk+1∈ω2并且Kk(xk+1) ≥ 0 则Kk+1(x)= Kk(x)-K(xxk) 综合式： Kk+1(x)= Kk(x)+rk+1K(x,xk) 其中： xk+1∈ω1并且Kk(xk+1)>0时 rk+1= 0 xk+1∈ω1并且Kk(xk+1) ≤ 0时 rk+1= 1 xk+1∈ω2并且Kk(xk+1)<0时 rk+1= 0 xk+1∈ω2并且Kk(xk+1) ≥ 0时 rk+1= -1

46 例题. 设有两类样本 ω1={(0,0)T,(2,0)T} ω2={(1,1)T,(1,-1) T}如下图线性不可分 特征为二维的，所以电位函数为： K(xx2)=exp{-[(x1-xk1)2+( x2-xk2)2]} ① 输入x1=( xk1, xk2)T=(0,0)T x1∈ω1 K1(x)= K1(xx1)=exp{-( x12+ x22)} ② 输入x2=(2,0)T x2∈ω1代入 K1(x2)=exp{-( )}>0 不修正 K2(x)= K1(x) =exp{-( x12+ x22)} ③ 输入x3=(1,1)T x3∈ω2代入 K2(x3)=exp{-( )}>0 所以需要修正 K3(x)= K2(x)- K(xx3) =exp{-( x12+ x22)} -exp{-[(x1-1)2+ (x2-1)2]}

47 ④输入x4=(1,-1)T x3∈ω2代入 K3(x4)=e-2- e-4>0 所以需要修正 K4(x)= K3(x)- K(xx4) =exp{-( x12+ x22)}- exp{-[(x1-1)2+ (x2-1)2]} -exp{-[(x1-1)2+ (x2+1)2]} 第二次迭代 ⑤输入x5=x1=(0,-0)T x5∈ω1代入 K4(x5)=1-e-2- e-4>0 K5(x)= K4(x) ⑥输入x6=x2=(2,0)T x6∈ω1代入 K5(x6)= e-4-e-2- e-2=0 所以需要修正 K6(x)= K5(x)+ K(xx6) -exp{-[(x1-1)2+ (x2+1)2]}+ -exp{-[(x1-2)2+ x22]}

48 ⑦输入x7=x3=(1,1)T x7∈ω2代入 K6(x7)= e-2- e0 -e-4+e-2<0 所以不需要修正
K7(x)= K6(x) ⑧输入x8=x4=(1,-1)T x8∈ω2代入 K7(x8)= e-2- e-2 - e0 +e-2<0 所以不需要修正 K8(x)= K7(x) ⑨输入x9=x1=(0,0)T x9∈ω1代入 K8(x9)= 1-e-2-e-2+e-4>0 所以不需要修正 K9(x)= K8(x) g(x)<0 g(x)>0 g(x)>0 g(x)<0

49 同理得到: K10(x)= K9(x)= K8(x)= K7(x)= K6(x) ,经一个完
整的循环可得判别函数为： g(x)= exp{-( x12+ x22)} -exp{-[(x1-1)2+ (x2-1)2]}} -exp{-[(x1-1)2+ (x2+1)2]}+exp{-[(x1-2)2+ x22]} 上边的非线性判别函数形成的边界如图所示。虽然它 可以把线性不可分的样本分开，但当样本很多时，使方 程的项数太多，增大计算量。