第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
国科大-机器学习与模式识别-第三次作业.doc
一、在一个 10 类的模式识别问题中，有 3 类单独满足多类情况 1，其余的类别满足多类情
况 2。问该模式识别问题所需判别函数的最少数目是多少？
应该是
13
C
2
7
6*74
2
4
21
25
其中加一是分别 3 类 和 7 类
二、一个三类问题，其判别函数如下：
d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-x2-1
(1)设这些函数是在多类情况 1 条件下确定的，绘出其判别界面和每一个模式类别的区域。
(2)设为多类情况 2，并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。绘出其判别
界面和多类情况 2 的区域。
(3)设 d1(x), d2(x)和 d3(x)是在多类情况 3 的条件下确定的，绘出其判别界面和每类的区
域。
一、两类模式，每类包括 5 个 3 维不同的模式，且良好分布。如果它们是线性可分的，问权
向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分
量？（设模式的良好分布不因模式变化而改变。）
如果线性可分，则 4 个
建立二次的多项式判别函数，则
2
5 C
10
个
二、(1)用感知器算法求下列模式分类的解向量 w:
ω1: {(0 0 0)T, (1 0 0)T, (1 0 1)T, (1 1 0)T}
ω2: {(0 0 1)T, (0 1 1)T, (0 1 0)T, (1 1 1)T}
将属于ω2 的训练样本乘以（-1），并写成增广向量的形式。
x①=(0 0 0 1)T, x②=(1 0 0 1)T, x③=(1 0 1 1)T, x④=(1 1 0 1)T
x⑤=(0 0 -1 -1)T, x⑥=(0 -1 -1 -1)T, x⑦=(0 -1 0 -1)T, x⑧=(-1 -1 -1 -1)T
第一轮迭代：取 C=1，w(1)=(0 0 0 0) T
因 w T (1) x① =(0 0 0 0)(0 0 0 1) T =0 ≯0，故 w(2)=w(1)+ x① =(0 0 0 1)
因 w T(2) x② =(0 0 0 1)(1 0 0 1) T =1>0，故 w(3)=w(2)=(0 0 0 1)T
因 wT(3)x③=(0 0 0 1)(1 0 1 1)T=1>0，故 w(4)=w(3) =(0 0 0 1)T
因 wT(4)x④=(0 0 0 1)(1 1 0 1)T=1>0，故 w(5)=w(4)=(0 0 0 1)T
因 wT(5)x⑤=(0 0 0 1)(0 0 -1 -1)T=-1≯0，故 w(6)=w(5)+ x⑤=(0 0 -1 0)T
因 wT(6)x⑥=(0 0 -1 0)(0 -1 -1 -1)T=1>0，故 w(7)=w(6)=(0 0 -1 0)T
因 wT(7)x⑦=(0 0 -1 0)(0 -1 0 -1)T=0≯0，故 w(8)=w(7)+ x⑦=(0 -1 -1 -1)T
因 wT(8)x⑧=(0 -1 -1 -1)(-1 -1 -1 -1)T=3>0，故 w(9)=w(8) =(0 -1 -1 -1)T
因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第二轮迭代。
第二轮迭代：
因 wT(9)x①=(0 -1 -1 -1)(0 0 0 1)T=-1≯0，故 w(10)=w(9)+ x① =(0 -1 -1 0)T
因 wT(10)x②=(0 -1 -1 0)( 1 0 0 1)T=0≯0，故 w(11)=w(10)+ x② =(1 -1 -1 1)T
因 wT(11)x③=(1 -1 -1 1)( 1 0 1 1)T=1>0，故 w(12)=w(11) =(1 -1 -1 1)T
因 wT(12)x④=(1 -1 -1 1)( 1 1 0 1)T=1>0，故 w(13)=w(12) =(1 -1 -1 1)T
因 wT(13)x⑤=(1 -1 -1 1)(0 0 -1 -1)T=0≯0，故 w(14)=w(13)+ x⑤ =(1 -1 -2 0)T
因 wT(14)x⑥=(1 -1 -2 0)( 0 -1 -1 -1)T=3>0，故 w(15)=w(14) =(1 -1 -2 0)T
因 wT(15)x⑧=(1 -1 -2 0)( 0 -1 0 -1)T=1>0，故 w(16)=w(15) =(1 -1 -2 0)T
因 wT(16)x⑦=(1 -1 -2 0)( -1 -1 -1 -1)T=2>0，故 w(17)=w(16) =(1 -1 -2 0)T
因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第三轮迭代。
第三轮迭代：
w(24)=(2 -2 -2 0);
因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第四轮迭代。
第四轮迭代：
w(31)=(2 -2 -2 1)
因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第五轮迭代。
第五轮迭代：
w(40)=(2 -2 -2 1)
因为该轮迭代的权向量对全部模式都能正确判别。所以权向量即为(2 -2 -2 1),相应的判别
函数为 d(x)=2x1-2x2-2x3+1
(2)编写求解上述问题的感知器算法程序。
代码：
clc;
clear all;
fprintf('感知器算法\n');
x=[0,0,0,1;1,0,0,1;1,0,1,1;1,1,0,1;0,0,-1,-1;0,-1,-1,-1;0,-1,0,-1;-1,-1,-1,-1];
[N,n]=size(x);
C=1;
w0=[0,0,0,0]';
w=w0;
flag=1;
k=0;
while(flag)
flag=0;
k=k+1;
for i=1:N
if w'*x(i,:)'<=0%
w=w+x(i,:)';
flag=1;
end
end
end
fprintf('迭代次数为%d\n',k);
fprintf('解向量为 w=(');
for j=1:n
fprintf('%d ',w(j));
end
fprintf(')\n');
fprintf('相应的判别函数为 d(x)=');
for j=1:n-1
fprintf('(%d)x%d+',w(j),j);
end
fprintf('(%d)\n',w(j));
三、用多类感知器算法求下列模式的判别函数：
ω1: (-1 -1)T
ω2: (0 0)T
ω3: (1 1)T
将模式样本写成增广形式：
x①=(-1 -1 1)T, x②=(0 0 1)T, x③=(1 1 1)T
取初始值 w1(1)=w2(1)=w3(1)=(0 0 0)T，C=1。
第一轮迭代（k=1）：以 x①=(-1 -1 1)T 作为训练样本。
d1(1)=
Tw
)1(1
x①=(0 0 0)(-1 -1 1)T=0
d2(1)=
Tw
)1(2
x①=(0 0 0)(-1 -1 1)T=0
d3(1)=
Tw
)1(3
x①=(0 0 0)(-1 -1 1)T=0
因 d1(1)≯d2(1)，d1(1)≯d3(1)，故
w1(2)=w1(1)+x①=(-1 -1 1)T
w2(2)=w2(1)-x①=(1 1 -1)T
w3(2)=w3(1)-x①=(1 1 -1)T
第二轮迭代（k=2）：以 x②=(0 0 1)T 作为训练样本
d1(2)=
Tw
)2(1
x②=(-1 -1 1)(0 0 1)T=1
d2(2)=
Tw
)2(2
x②=(1 1 -1)(0 0 1)T=-1
d3(2)=
Tw
)2(3
x②=(1 1 -1)(0 0 1)T=-1
因 d2(2)≯d1(2)，d2(2)≯d3(2)，故
w1(3)=w1(2)-x②=(-1 -1 0)T
w2(3)=w2(2)+x②=(1 1 0)T
w3(3)=w3(2)-x②=(1 1 -2)T
第三轮迭代（k=3）：以 x③=(1 1 1)T 作为训练样本
d1(3)=
Tw
)3(1
x③=(-1 -1 0)(1 1 1)T=-2
d2(3)=
Tw
)3(2
x③=(1 1 0)(1 1 1)T=2
d3(3)=
Tw
)3(3
x③=(1 1 -2)(1 1 1)T=0
因 d3(3)≯d2(3)，故
w1(4)=w1(3) =(-1 -1 0)T
w2(4)=w2(3)-x③=(0 0 -1)T
w3(4)=w3(3)+x③=(2 2 -1)T
第四轮迭代（k=4）：以 x①=(-1 -1 1)T 作为训练样本
d1(4)=
Tw
)4(1
x①=(-1 -1 0)(-1 -1 1)T=2
d2(4)=
Tw
)4(2
x①=(0 0 -1)(-1 -1 1)T=-1
d3(4)=
Tw
)4(3
x①=(2 2 -1)(-1 -1 1)T=-5
因 d1(4)>d2(4)，d1(4)>d3(4)，故
w1(5)=w1(4) =(-1 -1 0)T
w2(5)=w2(4) =(0 0 -1)T
w3(5)=w3(4) =(2 2 -1)T
第五轮迭代（k=5）：以 x②=(0 0 1)T 作为训练样本
d1(5)=
Tw
)5(1
x②=(-1 -1 0)(0 0 1)T=0
d2(5)=
Tw
)5(2
x②=(0 0 -1)(0 0 1)T=-1
d3(5)=
Tw
)5(3
x②=(2 2 -1)(0 0 1)T=-1
因 d2(5) ≯d1(5)，d2(5) ≯d3(5)，故
w1(6)=w1(5)-x② =(-1 -1 -1)
w2(6)=w2(5)+x②=(0 0 0)
w3(6)=w3(5)-x②=(2 2 -2)
第六轮迭代（k=6）：以 x③=(1 1 1)T 作为训练样本
d1(6)=
Tw
)6(1
x③=(-1 -1 -1)(1 1 1)T=-3
d2(6)=
Tw
)6(2
x③=(0 0 0)(1 1 1)T=0
d3(6)=
Tw
)6(3
x③=(2 2 -2)(1 1 1)T=2
因 d3(6)>d1(6)，d3(6)>d2(6)，故
w1(7)=w1(6)
w2(7)=w2(6)
w3(7)=w3(6)
第七轮迭代（k=7）：以 x①=(-1 -1 1)T 作为训练样本
d1(7)=
Tw
)7(1
x①=(-1 -1 -1)(-1 -1 1)T=1
d2(7)=
Tw
)7(2
x①=(0 0 0)(-1 -1 1)T=0
d3(7)=
Tw
)7(3
x①=(2 2 -2)(-1 -1 1)T=-6
因 d1(7)>d2(7)，d1(7)>d3(7)，分类结果正确，故权向量不变。
由于第五、六、七次迭代中 x①、x②、x③均已正确分类，所以权向量的解为：
w1=(-1 -1 -1)T
w2=(0 0 0)T
w3=(2 2 -2)T
三个判别函数：
d1(x)=- x1 -x2-1
d2(x)=0
d3(x)=2x1+2x2-2
四、采用梯度法和准则函数
),
(
bxwJ
,
1
x
8
2
[(
T
bxw
)
T
bxw
2
]
式中实数 b>0，试导出两类模式的分类算法。
J
w
1
|4
x
｜
2
||
(
其中，
T
bxw
)
|
T
bxw
*x-x*|
sign(
T
bxw
)
sign
(
T
bxw
)
1
1
T
-
bxwif
bxwif
T
0
0
当
0 bxwT
时，则 w(k+1) = w(k)，此时不对权向量进行修正；
当
0bxwT
时，则
(
kw
)1
)(
kw
Cx
k
||
x
k
|
｜
2
(
T
xw
k
k
b
)
，需对权向量进行校
正，初始权向量 w(1)的值可任选。即
(
kw
)1
)(
Ckw
|
｜
x
k
x
k
2
||
0
T
xw
k
k
(
b
)
T
bxwif
bxwif
T
0
0
五、用二次埃尔米特多项式的势函数算法求解以下模式的分类问题
ω1: {(0 1)T, (0 -1)T}
ω2: {(1 0)T, (-1 0)T}
（1）
1
2
3
4
5
6
7
8
9
( )
x
( )
x
( )
x
( )
x
( )
x
( )
x
( )
x
( )
x
( )
x
,
(
x x
1
1
2
,
(
x x
2
1
2
(
,
x x
1
2
3
,
(
x x
4
1
2
,
(
x x
5
1
2
(
,
x x
1
2
6
,
(
x x
7
1
2
(
,
x x
1
2
8
,
(
x x
9
1
2
)
)
)
)
)
)
)
)
)
0
1
2
1
2
1
1
0
0
1
2
) 1
(
H x H x
0
2
(
2
)
x
H x H x
2
2
2
(
)
4
x
H x H x
2
2
(
2
)
H x H x
x
1
0
2
(
4
)
x x
H x H x
1 2
2
2
(
)
2 (4
H x H x
x
x
2
1
2
2
4
)
(
2
H x H x
x
1
2
0
2
2 (4
2)
(
)
H x H x
x
x
1
2
2
2
2
2)(4
(4
)
(
x
H x H x
x
2
1
2
)
)
1
)
)
)
)
)
1
)
)
(
(
(
(
(
(
(
(
(
2)
2
2
1
1
1
1
1
1
1
2
1
2
2)
按第一类势函数定义，得到势函数
( ,
K x x
)
k
9
i
1
(
i
( )
x
i
x
k
)
其中
x
1
Txx
)
(
,
2
，
x
k
(
x
k
1
,
x
k
2
T
)
（2）通过训练样本逐步计算累积位势 K(x)
给定训练样本：ω1 类为 x①=(0 1)T, x②=(0 -1)T
ω2 类为 x③=(1 0)T, x④=(-1 0)T
累积位势 K(x)的迭代算法如下
第一步：取 x①=(0 1)T∈ω1，故
K X
1
(
)
15 20
x
2
40
2
x
2
24
2
x
1
32
2
x x
1
2
64
2
2
x x
1
2
第二步：取 x②=(0 -1)T∈ω1，故 K1(x②)=5
因 K1(x②)>0 且 x②∈ω1，故 K2(x)=K1(x)
第三步：取 x③=(1 0)T∈ω2，故 K2(x③)=9
因 K2(x③)>0 且 x③∈ω2，故
K X
(
3
)
K X
(
2
)
K X X
(
,
)
3
20
x
2
16
2
x
2
20
x
1
16
2
x
1
第四步：取 x④=(-1 0)T∈ω2，故 K3(x④)=4
因 K3(x④)>0 且 x④∈ω2，
K X
(
4
)
K X
(
3
)
K X X
(
,
) 15 20
x
2
56
2
x
1
8
2
x
2
32
2
x x
1
2
64
2
2
x x
1
2
4
将全部训练样本重复迭代一次，得
第五步：取 x⑤=x①=(0 1)T∈ω1，K4(x⑤)=27>0
故 K5(x)=K4(x)
第六步：取 x⑥=x②=(0 -1)T∈ω1，K5(x⑥)=-13<0
故
K X
(
6
)
K X
(
5
)
K X X
(
,
)
32
2
x
1
32
2
x
2
6
第七步：取 x⑦=x③=(1 0)T∈ω2，K6(x⑦)=-32<0
故 K7(x)=K6(x)
第八步：取 x⑧=x④=(-1 0)T∈ω2，K7(x⑧)=-32<0
故 K8(x)=K7(x)
第九步：取 x⑨=x①=(0 1)T∈ω1 ，K8(x⑨)=32>0
故 K9(x)=K8(x)
第十步：取 x⑩=x② =(0 -1)T∈ω1，K9(x⑩)=32>0
故 K10(x)=K9(x)
其中第七步到第十步的迭代过程中对全部训练样本都能正确分类，因此算法收敛于判
别函数
六、用下列势函数
(
d X
)
K X
10
(
)
32
2
x
1
32
2
x
2
K X X
(
,
)
||
e
k
X X
2
||
k
求解以下模式的分类问题
ω1: {(0 1)T, (0 -1)T}
ω2: {(1 0)T, (-1 0)T}
取α=1，在二维情况下势函数为
[(
x
1
x
2
)
2
])
2
k
xx
k
)
e
,(
xxK
这里：ω1 类为 x①=(0 1)T, x②=(0 -1)T
ω2 类为 x③=(1 0)T, x④=(-1 0)T
e
k
1
2
2
k
(
x
x
可以看出，这两类模式是线性不可分的。算法步骤如下：
第一步：取 x①=(0 1)T∈ω1，则
K X
1
(
)
exp{
2
x
1
(
x
2
2
1) }
第二步：取 x②=(0 -1)T∈ω1
因 K1(x②)=e-(4+0)=e-4>0，故 K2(x)=K1(x)
第三步：取 x③=(1 0)T∈ω2
因 K2(x③)=e-(1+1)=e-2>0，故
K X
(
3
)
K X
(
2
)
K X X
(
,
)
exp{
2
x
1
(
x
2
3
2
1) } exp{ (
x
1
2
1)
2
}
x
2
第四步：取 x④=(-1 0)T∈ω2
因 K3(x④)=e-(1+1) - e-(4+0) =e-2 - e-4>0，故
K X
(
4
)
K X K X X
3
(
)
(
,
)
exp{
2
x
1
(
x
2
4
2
1) } exp{ (
x
1
2
1)
2
x
2
} exp{ (
x
1
2
1)
2
x
2
}
第五步：取 x⑤=(0 1)T∈ω1
因 K4(x⑤)=1-e-(1+1) - e-(1+1) =1-e-2 - e-2>0，故 K5(x)=K4(x)
第六步：取 x⑥=(0 -1)T∈ω1
因 K5(x⑥)= e-(0+4) - e-(1+1) - e-(1+1) =e-4 - e-2- e-2<0，故
6
(
)
(
K X
2
exp{
K X
x
1
exp{ (
x
1
K X X
)
(
)
,
5
6
(
x
2
2
1)
2
2
1) } exp{
x
1
2
} exp{ (
x
x
2
1
(
x
2
2
1)
2
1) }
2
}
x
2
第七步：取 x⑦=(1 0)T∈ω2
因 K6(x⑦)= e-(1+1) + e-(1+1)–1- e-(4+0) =e-2 +e-2-1-e-4<0
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
