第三章 分类器的设计
线性分类器的设计
分段线性分类器的设计
非线性分类器的设计
§ 3-1 线性分类器的设计上一章我们讨论了线性判别函数形式为,g(x)=WTX
其中 X= (X1,X2… Xn) n维特征向量
W= (W1,W2… Wn,Wn+1) n维权向量通常通过特征抽取可以获得 n维特征向量,因此 n维权向量是要求解的 。
求解权向量的过程就是分类器的训练过程,使用已知类别的有限的学习样本来获得分类器的权向量被称为有监督的分类 。
0)(,
0)(,
2
1
xgx
xgx
分类准则利用已知类别学习样本来获得权向量的训练过程如下已知 x1 ∈ ω1,通过检测调整权向量，最终使 x1 ∈ ω1
已知 x2 ∈ ω2,通过检测调整权向量，最终使 x2 ∈ ω2
这样就可以通过有限的样本去决定权向量
x1
x2
…….
xn
1
w1
w2
wn
wn+1
∑ >0 x∈ ω1
检测
(已知类别 )
W1 X1
W2 X2
Wn Xn
Wn+1
<0 x∈ ω2
g(x)=wTx
WW 1
利用方程组来求解权向量对二类判别函数 g(x) = W1X1+ W2X2 +W3
已知训练集,Xa,Xb,Xc,Xd且当 (Xa,Xb) ∈W 1时 g(x)＞ 0
当 (Xc,Xd) ∈W 2时 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
为各模式增 1矩阵为 N*(n+1） 矩阵
N为样本数,n为特征数
1
1
1
1
21
21
21
21
dd
cc
bb
aa
XX
XX
XX
XX
X
训练过程就是对已知类别的样本集求解权向量 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)代入 ① 式得：
J(Wk+1)≈J(Wk)-ρk||▽ J||2+ ρk2▽ JT D▽ J
其中 ▽ J=▽ J(Wk)
对 ρk求导数,并令导数为零有最佳步长为 ρk=||▽ J||2/▽ JTD▽ J
这就是最佳 ρk的计算公式,但因二阶偏导数矩阵 D的计算量太大,因此此公式很少用 。
2
1
若令 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为响应阈值定义感知准则函数：只考虑错分样本定义,其中 x0为错分样本当分类发生错误时就有 WTX <0，或－ WTX >0,所以 J(W)
总是正值，错误分类愈少,J(W)就愈小。
理想情况为 即求最小值的问题。
0
)( XX XWWJ T
0)(?WJ
求最小值对 W求梯度代入迭代公式中 Wk+1 = Wk-ρk▽ J
由 J(W)经第 K+1次迭代的时候,J(W)趋于 0，收敛于所求的 W值
0
)(
XX XW
WJJ
0
1 XX XWW kkk?即感知器迭代公式：
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分成一类 。
x1
x2
x3
2
H
3
H1
4
H2
5
W区间
+
感知器算法：
1.错误分类修正 wk
如 wkTx≤0并且 x∈ ω1 wk+1= wk-ρkx
如 wkTx≥0并且 x∈ ω2 wk+1= wk-ρkx
2.正确分类,wk不修正如 wkTx＞ 0并且 x∈ ω1
如 wkTx＜ 0并且 x∈ ω2
wk+1= wk
+
-
H
wk+1
ρkxwk
权值修正过程
ρk选择准则
① 固定增量原则 ρk固定非负数
② 绝对修正规则 ρk>
③ 部分修正规则 ρk=λ 0＜ λ≤2
xx
xw
T
T ||
xx
xw
T
T ||
例题：有两类样本
ω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) =0 所以修正 w2
w3=w2-x4=(0,-1,1,-1)
第一次迭代后,权向量 w3=(0,-1,1,-1),再进行第 2,3,… 次迭代如下表直到在一个迭代过程中权向量相同,训练结束 。
w6=w=(0,1,3,0) 判别函数 g(x)= -x2+3x3
感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点,
训练样本 wkTx 修正式 修正后的权值 wk＋ 1 迭代次数
x1 1 0 1 1
x2 0 1 1 1
x3 1 1 0 1
x4 0 1 0 1
+
+
+
0
w1
w1
w1-x3
w2-x4
1 1 1 1
1 1 1 1
0 0 1 0
0 –1 1 -1
1
x1 1 0 1 1
x2 0 1 1 1
x3 1 1 0 1
x4 0 1 0 1
0
+
0
-
w3+x1
w4
w4-x3
w5
1 –1 2 0
1 –1 2 0
0 –2 2 –1
0 –2 2 -1
2
x1 1 0 1 1
x2 0 1 1 1
x3 1 1 0 1
x4 0 1 0 1
+
-
-
-
w5
w5+x2
w6
w6
0 –2 2 –1
0 –1 3 0
0 –1 3 0
0 –1 3 0
3
x1 1 0 1 1
x2 0 1 1 1
x3 1 1 0 1
x4 0 1 0 1
+
+
-
-
w6
w6
w6
w6
0 –1 3 0
0 –1 3 0
0 –1 3 0
0 –1 3 0
4
线性不可分样本集的分类解 (取近似解 )
对于线性可分的样本集，可以用上述方法解到正确分类的权向量。当样本集线性不可分时，用上述方法求权值时算法不收敛。如果我们把循环的权向量取平均值作为待求的权向量，或就取其中之一为权向量，一般可以解到较满意的近似结果。
例：在样本
ω1,X1 =（ 0,2） X3 =（ 2,0）
X5 =（ -1,-1）
ω2,X2 =（ 1,1） X4 =（ 0,-2）
X6 =（ -2,0）
求权向量的近似解
x2
x1
x6
x1
x3
－ 2
x5
－ 2x4
x2
1
1
H
解：此为线性不可分问题，利用感知器法求权向量权向量产生循环 (-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类，但大部分分类还是正确的。
作业：已知四个训练样本
w1={(0,0),(0,1)}
w2={(1,0),(1,1)}
使用感知器固定增量法求判别函数设 w1=(1,1,1,1) ρk=1
要求编写程序上机运行,写出判别函数,并打出图表 。
三 最小平方误差准则 (MSE法 )---非迭代法前面我们研究了线性不等式方程组 g(x) =WTX>0的解法 。
它们共同点是企图找一个权向量 W,使错分样本最小 。
现在我们把不等式组变成如下形式,WTXi=bi>0
则有联立方程 XW=b 这是矛盾方程组,方程数大于未知数,所以没有精确解的存在 。
NnNN
n
N XXX
X
XXX
X
X
X
X
...
............
.........
....
.....
21
21
11211
2
1
N,,,.,2,1,XXX TX?令
给定的任意正常数N,,,,,2,1,bbb Tb?
每个样本有 n个特征定义误差向量,e=XW-b≠0 把平方误差作为目标函数
W的优化就是使 J(W)最小 。 求 J(W)的梯度并为 0。
解上方程得 XTXW=XTb
这样把求解 XW=b的问题,转化为对 XTXW=XTb求解,这一有名的方程最大好处是因 XTX是方阵且通常是非奇异的,
所以可以得到 W的唯一解 。
N
i
b iX iW TbXWeWJ
1
222 ||||||||)( MSE准则函数
0)(22J ( W )
1
bXWXXb iX iW T Ti
N
i
只要计算出 X+就可以得到 W
取：
最小平方误差法同 Fisher法是一致的。
bXbXXX TW T 1
的伪逆（规范矩阵）称为其中 XXXX TX T 1
2
2
1
..........
1
/
......
/
/
/
NN
NN
NN
NN
b
（ MSE 解）
其中 N/N1有 N1个,N/N2有 N2个四 韦 — 霍氏法（ 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
为任意常数其中令 11kk?
XXX TX T 1伪逆 计算量很大因此下降算法不论 XTX是否奇异,总能产生一个解 。
若训练样本无限的重复出现,则简化为
W1任意
Wk+1=Wk+ρk(bk-WkTXk)Xk
ρk随迭代次数 k而减少,以保证算法收敛于满意 的 W值k
1
K
取五 何 — 卡氏法 （判断迭代过程中是否线性可分）
若训练样本线性可分时,感知器法可求出界面,但对不可分问题不收敛只能取平均 。 最小平方误差法不论样本是否线性可分都能给出一加权矢量,但不能保证此矢量就是分界矢量,下面介绍一种方法可以检测迭代过程中是否线性可分 。
因最小平方误差法的 J(W)的解为
因为 XW=b b应 为正值
c为矫正系数当 （ XWk-bk） ≤0 时当 （ XWk-bk） ＞ 0 时
bXbXXX TW T 1
|]|[ kkkkk bXWbXWcbb＝的增量为?
kkk bbbb 1前后两次迭代后，对的增量为其中 bb k?
0＝kb?
][2 kkk bXWcb?＝?
引入误差矢量 ek
ek=XWk-bk判断是否线性可分
所以 J(W)的解为初始条件 W1=X+b1并且 b1>0
迭代时检测如果 ek≥0时,XW >b,系统线性可分,迭代收敛如果 ek<0时,XW <b,系统线性不可分,迭代不收敛
我们用下面的例子来说明 ek的作用
|]|[ kkk eeCb
]|[][ |11 kKkkKkKKk eeXcWbXbXbbXbXW
因此上式可以写成
例题：
ω1={(0,0)T,(0,1)T} ω2={(1,0)T,(1,1)T}
解：正规化对 ω2取负,有
111
101
110
100
X
2/12/12/12/3
1111
1111
2
11
XXX TX T
X的规范矩阵为
x2
x1
x1
x2
x3
x4
取 b1=(1,1,1,1)T c=1 W1=X+b1=(-2,0,1)T
所以 W1为所求解 e1=XW1-b1=0 系统线性可分
01111
1
0
2
111
101
110
100
,,,1
T
WX
因为若四个样本变成：
ω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,迭代就应立即停止 。
101
110
111
100
X
x2
x1
1
1
2/12/12/12/3
1111
1111
2
1
X
六 Fisher分类准则现在讨论通过映射投影来降低维数的方法。
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的问题。
w(y)
w
y1
y2
x2
x1
ω1
ω2
投影样本之间的分离性用投影样本之差表示投影样本类内离散度,
XXNXNyY YNYY i
iiii
i WW
11 TT?
空间的投影均值在
Nxi
i
i
XNxX 1空间的均值：在
11 WY XT 22 WY XT?
类间分离性越大越好|)(||| 2121 XXWYY T
WSWNX XTXTyY YY iT
i ii
ii WW 222?
WSW T 121 WSW T 222
i=1,2
i=1,2
i T
i
ii XXNX XXS其中
2
222 NX XXXXS
T
1
111 NX XXXXS T
2 21 2
21
2||
)(
YYWJFi s h e r 准则函数有所以
WSWXW TXW TYYWJ bT 21 221 2)( 的分子
2121 XXXXS Tb其中
WSWWSWWSWWJ wTTT 212 21 2)(的分母小越好。投影样本的总离散度越
）来表示，要求用（投影样本总的离散度可 2 21 2
类间散布矩阵
SSS w 21
上式就是 n维 x空间向一维 y空间 的最好投影方向，
它实际是多维空间向一维空间的一种映射。
XXSWWJ w 211)(求极值得对
WSW
WSW)(
wT
bT?WJ所以其中 Sw为类内散布矩阵,Sb为类间散布矩阵现在我们已把一个 n维的问题转化为一维的问题 。
现在一维空间设计 Fisher分类器,
W0的选择
20
10
XWXWY
XWXWY
T
T
2.1 210 YYW
21
21
21
21
0 2122.2 NN X
WNXWN
NN
YNYNW TT
Yki表示第 i类中第 k个样本的投影值
N1为 ω1样本数 N2为 ω2样本数当 W0选定后,对任一样本 X,只要判断 Y=WTX>0 则
X∈ ω1; Y=WTX<0 则 X∈ ω2。 分类问题就解决了
N
YY
N
YY
N
YY
YYYW
k
k
k
k
k
k
2
2
1
1
1
1
121
1
2
2
1
1
2
1
1
2
0 )(.3
§ 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
并且满足条件 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
③ 重复以上迭代,直到收敛,此法 类似于固定增量法,
3.未知子类数目时的设计方法当每类应分成的子类数也不知时,这是最一般情况,方法很多,举例如下 。
树状分段线性分类器,
设 两类情况 ω1,ω2。 如图所示
① 先用两类线性判别函数求出 W1,超平面 H1分成两个区间,每个区间包含两类 。
② 再利用二类分类求出 W2(H2),
W3(H3)。
③ 如果每个部分仍包含两类,
继续上面的过程 。
关键是初始权向量 W1的选择,一般先选两类中距离最近的两个子类的均值连线做垂直线作为 H1(w1)初始值再求最优解 。
w1Tx>0
w4Tx≥0
w3Tx≥0 w2Tx≥0
Y N
Y
Y
N
Nω
1
ω1 ω2
ω2
N Y
ω1
树状决策框图
§ 3-3 非线性分类器的设计
电位函数分类器,用非线性判别函数区分线性不可分的类别
电位函数分类器,每个特征作为一个点电荷,把特征空间作为能量场,电位分布函数有下面三种形式 。
α为系数 xk为某一特定点上图是这些函数在一维时的图形,第三条是振荡曲线,
只有第一周期才是可用范围 。
||||1
1 )K( 2.
2kk xxXX
|
||||
||||s in|)K( 3.
2
2
k
k
k
xx
xxXX
x
K(x)
x
3
2
1
}||||e x p{ - )K( 1,2kk xxXX
电位函数算法的训练过程是在逐个样本输入时,逐渐积累电位的过程,对于二类问题,经过若干循环后,如积累电位方程的运算结果能以正,负来区分二类样本,则训练就可结束 。
算法,设初始电位为 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)
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个样本
积累电荷 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
例题,
设有两类样本
ω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{-( 02+ 22)}>0 不修正
K2(x)= K1(x) =exp{-( x12+ x22)}
③ 输入 x3=(1,1)T x3∈ ω2代入
K2(x3)=exp{-( 12+ 12)}>0 所以需要修正
K3(x)= K2(x)- K(xx3) =exp{-( x12+ x22)}
-exp{-[(x1-1)2+ (x2-1)2]}
④ 输入 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{-( x12+ x22)}- exp{-[(x1-1)2+ (x2-1)2]}
-exp{-[(x1-1)2+ (x2+1)2]}+ -exp{-[(x1-2)2+ x22]}
⑦ 输入 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
同理得到,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]}
上边的非线性判别函数形成的边界如图所示 。 虽然它可以把线性不可分的样本分开,但当样本很多时,使方程的项数太多,增大计算量 。
线性分类器的设计
分段线性分类器的设计
非线性分类器的设计
§ 3-1 线性分类器的设计上一章我们讨论了线性判别函数形式为,g(x)=WTX
其中 X= (X1,X2… Xn) n维特征向量
W= (W1,W2… Wn,Wn+1) n维权向量通常通过特征抽取可以获得 n维特征向量,因此 n维权向量是要求解的 。
求解权向量的过程就是分类器的训练过程,使用已知类别的有限的学习样本来获得分类器的权向量被称为有监督的分类 。
0)(,
0)(,
2
1
xgx
xgx
分类准则利用已知类别学习样本来获得权向量的训练过程如下已知 x1 ∈ ω1,通过检测调整权向量，最终使 x1 ∈ ω1
已知 x2 ∈ ω2,通过检测调整权向量，最终使 x2 ∈ ω2
这样就可以通过有限的样本去决定权向量
x1
x2
…….
xn
1
w1
w2
wn
wn+1
∑ >0 x∈ ω1
检测
(已知类别 )
W1 X1
W2 X2
Wn Xn
Wn+1
<0 x∈ ω2
g(x)=wTx
WW 1
利用方程组来求解权向量对二类判别函数 g(x) = W1X1+ W2X2 +W3
已知训练集,Xa,Xb,Xc,Xd且当 (Xa,Xb) ∈W 1时 g(x)＞ 0
当 (Xc,Xd) ∈W 2时 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
为各模式增 1矩阵为 N*(n+1） 矩阵
N为样本数,n为特征数
1
1
1
1
21
21
21
21
dd
cc
bb
aa
XX
XX
XX
XX
X
训练过程就是对已知类别的样本集求解权向量 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)代入 ① 式得：
J(Wk+1)≈J(Wk)-ρk||▽ J||2+ ρk2▽ JT D▽ J
其中 ▽ J=▽ J(Wk)
对 ρk求导数,并令导数为零有最佳步长为 ρk=||▽ J||2/▽ JTD▽ J
这就是最佳 ρk的计算公式,但因二阶偏导数矩阵 D的计算量太大,因此此公式很少用 。
2
1
若令 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为响应阈值定义感知准则函数：只考虑错分样本定义,其中 x0为错分样本当分类发生错误时就有 WTX <0，或－ WTX >0,所以 J(W)
总是正值，错误分类愈少,J(W)就愈小。
理想情况为 即求最小值的问题。
0
)( XX XWWJ T
0)(?WJ
求最小值对 W求梯度代入迭代公式中 Wk+1 = Wk-ρk▽ J
由 J(W)经第 K+1次迭代的时候,J(W)趋于 0，收敛于所求的 W值
0
)(
XX XW
WJJ
0
1 XX XWW kkk?即感知器迭代公式：
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分成一类 。
x1
x2
x3
2
H
3
H1
4
H2
5
W区间
+
感知器算法：
1.错误分类修正 wk
如 wkTx≤0并且 x∈ ω1 wk+1= wk-ρkx
如 wkTx≥0并且 x∈ ω2 wk+1= wk-ρkx
2.正确分类,wk不修正如 wkTx＞ 0并且 x∈ ω1
如 wkTx＜ 0并且 x∈ ω2
wk+1= wk
+
-
H
wk+1
ρkxwk
权值修正过程
ρk选择准则
① 固定增量原则 ρk固定非负数
② 绝对修正规则 ρk>
③ 部分修正规则 ρk=λ 0＜ λ≤2
xx
xw
T
T ||
xx
xw
T
T ||
例题：有两类样本
ω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) =0 所以修正 w2
w3=w2-x4=(0,-1,1,-1)
第一次迭代后,权向量 w3=(0,-1,1,-1),再进行第 2,3,… 次迭代如下表直到在一个迭代过程中权向量相同,训练结束 。
w6=w=(0,1,3,0) 判别函数 g(x)= -x2+3x3
感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点,
训练样本 wkTx 修正式 修正后的权值 wk＋ 1 迭代次数
x1 1 0 1 1
x2 0 1 1 1
x3 1 1 0 1
x4 0 1 0 1
+
+
+
0
w1
w1
w1-x3
w2-x4
1 1 1 1
1 1 1 1
0 0 1 0
0 –1 1 -1
1
x1 1 0 1 1
x2 0 1 1 1
x3 1 1 0 1
x4 0 1 0 1
0
+
0
-
w3+x1
w4
w4-x3
w5
1 –1 2 0
1 –1 2 0
0 –2 2 –1
0 –2 2 -1
2
x1 1 0 1 1
x2 0 1 1 1
x3 1 1 0 1
x4 0 1 0 1
+
-
-
-
w5
w5+x2
w6
w6
0 –2 2 –1
0 –1 3 0
0 –1 3 0
0 –1 3 0
3
x1 1 0 1 1
x2 0 1 1 1
x3 1 1 0 1
x4 0 1 0 1
+
+
-
-
w6
w6
w6
w6
0 –1 3 0
0 –1 3 0
0 –1 3 0
0 –1 3 0
4
线性不可分样本集的分类解 (取近似解 )
对于线性可分的样本集，可以用上述方法解到正确分类的权向量。当样本集线性不可分时，用上述方法求权值时算法不收敛。如果我们把循环的权向量取平均值作为待求的权向量，或就取其中之一为权向量，一般可以解到较满意的近似结果。
例：在样本
ω1,X1 =（ 0,2） X3 =（ 2,0）
X5 =（ -1,-1）
ω2,X2 =（ 1,1） X4 =（ 0,-2）
X6 =（ -2,0）
求权向量的近似解
x2
x1
x6
x1
x3
－ 2
x5
－ 2x4
x2
1
1
H
解：此为线性不可分问题，利用感知器法求权向量权向量产生循环 (-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类，但大部分分类还是正确的。
作业：已知四个训练样本
w1={(0,0),(0,1)}
w2={(1,0),(1,1)}
使用感知器固定增量法求判别函数设 w1=(1,1,1,1) ρk=1
要求编写程序上机运行,写出判别函数,并打出图表 。
三 最小平方误差准则 (MSE法 )---非迭代法前面我们研究了线性不等式方程组 g(x) =WTX>0的解法 。
它们共同点是企图找一个权向量 W,使错分样本最小 。
现在我们把不等式组变成如下形式,WTXi=bi>0
则有联立方程 XW=b 这是矛盾方程组,方程数大于未知数,所以没有精确解的存在 。
NnNN
n
N XXX
X
XXX
X
X
X
X
...
............
.........
....
.....
21
21
11211
2
1
N,,,.,2,1,XXX TX?令
给定的任意正常数N,,,,,2,1,bbb Tb?
每个样本有 n个特征定义误差向量,e=XW-b≠0 把平方误差作为目标函数
W的优化就是使 J(W)最小 。 求 J(W)的梯度并为 0。
解上方程得 XTXW=XTb
这样把求解 XW=b的问题,转化为对 XTXW=XTb求解,这一有名的方程最大好处是因 XTX是方阵且通常是非奇异的,
所以可以得到 W的唯一解 。
N
i
b iX iW TbXWeWJ
1
222 ||||||||)( MSE准则函数
0)(22J ( W )
1
bXWXXb iX iW T Ti
N
i
只要计算出 X+就可以得到 W
取：
最小平方误差法同 Fisher法是一致的。
bXbXXX TW T 1
的伪逆（规范矩阵）称为其中 XXXX TX T 1
2
2
1
..........
1
/
......
/
/
/
NN
NN
NN
NN
b
（ MSE 解）
其中 N/N1有 N1个,N/N2有 N2个四 韦 — 霍氏法（ 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
为任意常数其中令 11kk?
XXX TX T 1伪逆 计算量很大因此下降算法不论 XTX是否奇异,总能产生一个解 。
若训练样本无限的重复出现,则简化为
W1任意
Wk+1=Wk+ρk(bk-WkTXk)Xk
ρk随迭代次数 k而减少,以保证算法收敛于满意 的 W值k
1
K
取五 何 — 卡氏法 （判断迭代过程中是否线性可分）
若训练样本线性可分时,感知器法可求出界面,但对不可分问题不收敛只能取平均 。 最小平方误差法不论样本是否线性可分都能给出一加权矢量,但不能保证此矢量就是分界矢量,下面介绍一种方法可以检测迭代过程中是否线性可分 。
因最小平方误差法的 J(W)的解为
因为 XW=b b应 为正值
c为矫正系数当 （ XWk-bk） ≤0 时当 （ XWk-bk） ＞ 0 时
bXbXXX TW T 1
|]|[ kkkkk bXWbXWcbb＝的增量为?
kkk bbbb 1前后两次迭代后，对的增量为其中 bb k?
0＝kb?
][2 kkk bXWcb?＝?
引入误差矢量 ek
ek=XWk-bk判断是否线性可分
所以 J(W)的解为初始条件 W1=X+b1并且 b1>0
迭代时检测如果 ek≥0时,XW >b,系统线性可分,迭代收敛如果 ek<0时,XW <b,系统线性不可分,迭代不收敛
我们用下面的例子来说明 ek的作用
|]|[ kkk eeCb
]|[][ |11 kKkkKkKKk eeXcWbXbXbbXbXW
因此上式可以写成
例题：
ω1={(0,0)T,(0,1)T} ω2={(1,0)T,(1,1)T}
解：正规化对 ω2取负,有
111
101
110
100
X
2/12/12/12/3
1111
1111
2
11
XXX TX T
X的规范矩阵为
x2
x1
x1
x2
x3
x4
取 b1=(1,1,1,1)T c=1 W1=X+b1=(-2,0,1)T
所以 W1为所求解 e1=XW1-b1=0 系统线性可分
01111
1
0
2
111
101
110
100
,,,1
T
WX
因为若四个样本变成：
ω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,迭代就应立即停止 。
101
110
111
100
X
x2
x1
1
1
2/12/12/12/3
1111
1111
2
1
X
六 Fisher分类准则现在讨论通过映射投影来降低维数的方法。
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的问题。
w(y)
w
y1
y2
x2
x1
ω1
ω2
投影样本之间的分离性用投影样本之差表示投影样本类内离散度,
XXNXNyY YNYY i
iiii
i WW
11 TT?
空间的投影均值在
Nxi
i
i
XNxX 1空间的均值：在
11 WY XT 22 WY XT?
类间分离性越大越好|)(||| 2121 XXWYY T
WSWNX XTXTyY YY iT
i ii
ii WW 222?
WSW T 121 WSW T 222
i=1,2
i=1,2
i T
i
ii XXNX XXS其中
2
222 NX XXXXS
T
1
111 NX XXXXS T
2 21 2
21
2||
)(
YYWJFi s h e r 准则函数有所以
WSWXW TXW TYYWJ bT 21 221 2)( 的分子
2121 XXXXS Tb其中
WSWWSWWSWWJ wTTT 212 21 2)(的分母小越好。投影样本的总离散度越
）来表示，要求用（投影样本总的离散度可 2 21 2
类间散布矩阵
SSS w 21
上式就是 n维 x空间向一维 y空间 的最好投影方向，
它实际是多维空间向一维空间的一种映射。
XXSWWJ w 211)(求极值得对
WSW
WSW)(
wT
bT?WJ所以其中 Sw为类内散布矩阵,Sb为类间散布矩阵现在我们已把一个 n维的问题转化为一维的问题 。
现在一维空间设计 Fisher分类器,
W0的选择
20
10
XWXWY
XWXWY
T
T
2.1 210 YYW
21
21
21
21
0 2122.2 NN X
WNXWN
NN
YNYNW TT
Yki表示第 i类中第 k个样本的投影值
N1为 ω1样本数 N2为 ω2样本数当 W0选定后,对任一样本 X,只要判断 Y=WTX>0 则
X∈ ω1; Y=WTX<0 则 X∈ ω2。 分类问题就解决了
N
YY
N
YY
N
YY
YYYW
k
k
k
k
k
k
2
2
1
1
1
1
121
1
2
2
1
1
2
1
1
2
0 )(.3
§ 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
并且满足条件 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
③ 重复以上迭代,直到收敛,此法 类似于固定增量法,
3.未知子类数目时的设计方法当每类应分成的子类数也不知时,这是最一般情况,方法很多,举例如下 。
树状分段线性分类器,
设 两类情况 ω1,ω2。 如图所示
① 先用两类线性判别函数求出 W1,超平面 H1分成两个区间,每个区间包含两类 。
② 再利用二类分类求出 W2(H2),
W3(H3)。
③ 如果每个部分仍包含两类,
继续上面的过程 。
关键是初始权向量 W1的选择,一般先选两类中距离最近的两个子类的均值连线做垂直线作为 H1(w1)初始值再求最优解 。
w1Tx>0
w4Tx≥0
w3Tx≥0 w2Tx≥0
Y N
Y
Y
N
Nω
1
ω1 ω2
ω2
N Y
ω1
树状决策框图
§ 3-3 非线性分类器的设计
电位函数分类器,用非线性判别函数区分线性不可分的类别
电位函数分类器,每个特征作为一个点电荷,把特征空间作为能量场,电位分布函数有下面三种形式 。
α为系数 xk为某一特定点上图是这些函数在一维时的图形,第三条是振荡曲线,
只有第一周期才是可用范围 。
||||1
1 )K( 2.
2kk xxXX
|
||||
||||s in|)K( 3.
2
2
k
k
k
xx
xxXX
x
K(x)
x
3
2
1
}||||e x p{ - )K( 1,2kk xxXX
电位函数算法的训练过程是在逐个样本输入时,逐渐积累电位的过程,对于二类问题,经过若干循环后,如积累电位方程的运算结果能以正,负来区分二类样本,则训练就可结束 。
算法,设初始电位为 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)
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个样本
积累电荷 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
例题,
设有两类样本
ω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{-( 02+ 22)}>0 不修正
K2(x)= K1(x) =exp{-( x12+ x22)}
③ 输入 x3=(1,1)T x3∈ ω2代入
K2(x3)=exp{-( 12+ 12)}>0 所以需要修正
K3(x)= K2(x)- K(xx3) =exp{-( x12+ x22)}
-exp{-[(x1-1)2+ (x2-1)2]}
④ 输入 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{-( x12+ x22)}- exp{-[(x1-1)2+ (x2-1)2]}
-exp{-[(x1-1)2+ (x2+1)2]}+ -exp{-[(x1-2)2+ x22]}
⑦ 输入 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
同理得到,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]}
上边的非线性判别函数形成的边界如图所示 。 虽然它可以把线性不可分的样本分开,但当样本很多时,使方程的项数太多,增大计算量 。
