3-模式识别导论-分类器的设计

模式识别课件

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

模式识别课件

§3-1 线性分类器的设计上一章我们讨论了线性判别函数形式为:g(x)=WTX 其中 X= (X1, X2…Xn) n维特征向量 W= (W1, W2 … Wn , Wn+1) n维权向量

x ∈ ω 1 , g ( x) > 0 分类准则 x ∈ ω 2 , g ( x) < 0通常通过特征抽取可以获得n维特征向量，因此n维 权向量是要求解的。 求解权向量的过程就是分类器的训练过程，使用已 知类别的有限的学习样本来获得分类器的权向量被称为 有监督的分类。

模式识别课件

利用已知类别学习样本来获得权向量的训练过程如下 x1 x2 ……. xn 1 wn wn+1W n Xn Wn+1

w1 w2

W 1 X1 W 2 X2

g(x)=wTx

∑检测

>0 x∈ω1 <0 x∈ω2

(已知类别)

W1 = W ±

已知x1 ∈ω1, 通过检测调整权向量，最终使x1 ∈ω1 已知x2 ∈ω2, 通过检测调整权向量，最终使x2 ∈ω2 这样就可以通过有限的样本去决定权向量

模式识别课件

利用方程组来求解权向量 对二类判别函数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>0 ① X1bW1+ X2bW2+ W3>0 ② X1cW1+ X2cW2+ W3<0 ③ X1dW1+ X2dW2+ W3<0 ④ 求出W1 , W2, W3

模式识别课件

将③ ④式正规化，得 -X1cW1- X2cW2- W3 >0 -X1dW1- X2dW2- W3 >0 所以 g(x) =WTX >0 其中W = (W1 , W2, W3)T X 1a X 1b X = X 1c X 1d X 2a X 2b X 2c X 2d 1 1 1 1

为各模式增1矩阵

为N*(n+1)矩阵 N为样本数，n为特征数

模式识别课件

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

模式识别课件

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

W2 = W1-ρ1▽J(W1)W1为起始权向量 ρ1为迭代步长 J(W1) 为目标函数 ▽J(W1)为W1处的目标函数的梯度矢量

模式识别课件

在第K步的时候 Wk+1 = Wk-ρk▽J(Wk) ρk为正比例因子 这就是梯度下降法的迭代公式。这样一步步迭代 就可以收敛于解矢量，ρk取值很重要 ρk太大，迭代

太快，引起振荡，甚至发散。 ρk太小，迭代太慢。 应该选最佳ρk。

模式识别课件

选最佳ρ 选最佳 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)代入①式得： 1 2+ J(Wk+1) ≈J(Wk)- ρk||▽J|| ρk2▽JT D▽J 2 其中▽J=▽J(Wk) 对ρk求导数 ，并令导数为零有 最佳步长为ρk=||▽J||2/▽JTD▽J 这就是最佳ρk的计算公式，但因二阶偏导数矩阵D的计算 量太大，因此此公式很少用。

模式识别课件

若令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为奇异时，无法用牛顿法。

模式识别课件

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

模式识别课件

通过对W的调整，可实现判别函数g(x) =WTX > RT 其中RT为响应阈值 定义感知准则函数：只考虑错分样本 定义： J (W ) =

X ∈X 0

∑ ( W

T

X)

其中x0为错分样本

当分类发生错误时就有WTX <0,或-WTX >0, 所以J(W) 总是正值，错误分类愈少， J(W)就愈小。 理想情况为 J (W ) = 0即求最小值的问题。

模式识别课件

求最小值对W求梯度

J =

J (W ) = ∑ ( X ) W X ∈X 0

代入迭代公式中Wk+1 = Wk-ρk▽J即感知器迭代公式： W k + 1 = W k + ρ k X ∈X 0

∑X

由J(W)经第K+1次迭代的时候，J(W)趋于0,收敛于所求的W值

模式识别课件

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

x3

3

4 2 x2

W区间

H1 x1

H

H2

模式识别课件

+感知器算法： 1.错误分类修正wk 如wkTx≤0并且x∈ω1 如wkTx≥0并且x∈ω2 2.正确分类 ，wk不修正 如wkTx>0并且x∈ω1 如wkTx<0并且x∈ω2 wk+1= wk + wk wk+1= wk-ρkx wk+1= wk-ρkx

H wk+1 ρk x

权值修正过程

模式识别课件

ρk选择准则 ① 固定增量原则 ρk固定非负数 ② 绝对修正规则 ρk>

| wT x | x x | wT x | x xT T

③

部分修正规则 ρk=λ

0<λ≤2