模式识别习题参考3-教材第6and7章
第5章 句法模式识别习题解答
6.1 用链码法描述5～9五个数字。
解：用弗利曼链码表示，基元如解图6.1所示：
数字5~9的折线化和量化结果如解图6.2所示：
各数字的链码表示分别为：
“5”的链码表示为434446600765=x ； “6”的链码表示为3444456667012=x ； “7”的链码表示为00066666=x ； “8”的链码表示为21013457076543=x ； “9”的链码表示为5445432107666=x 。
1
7
解图6.1 弗利曼链码基元 解图6.2 数字5~9的折线化和量化结果
6.2 定义所需基本基元，用PDL 法描述印刷体英文大写斜体字母“H ”、“K ”和
“Z ”。 解：设基元为：
用PDL 法得到“H ”的链描述为)))))(~((((d d c d d x H ?+?+=；
“K ”的链描述为))((b a d d x K ??+=； “Z ”的链描述为))((c c g x Z ?-=。
6.3 设有文法),,,(S P V V G T N =，N V ，T V 和P 分别为
},,{B A S V N =，},{b a V T =
：P ①aB S →，②bA S →，③a A →，④aS A →
⑤bAA A →，⑥b B →，⑦bS B →，⑧aBB B → 写出三个属于)(G L 的句子。 解：
以上句子ab ，abba ，abab ，ba ，baab ，baba 均属于)(G L 。
6.4 设有文法),,,(S P V V G T N =，其中},,,{C B A S V N =，}1,0{=T V ，P 的各
生成式为
①A S 0→，②B S 1→，③C S 1→
b
c
a
d
e
abba abbA abS aB S ???? ① ⑦ ② ③
ab aB S ?? ① ⑥
ba bA S ??
② ③ abab abaB abS aB S ???? ① ⑦ ① ⑥
baab baaB baS bA S ???? ② ④ ① ⑥
baba babA baS bA S ????
② ④ ② ③
④A A 0→，⑤B A 1→，⑥1→A ⑦0→B ，⑧B B 0→，⑨C C 0→，⑩1→C
问00100=x 是否属于语言)(G L ？ 解：由
可知00100=x 属于语言)(G L 。
6.5 写出能产生图示树的扩展树文法，设基元a ，b 分别为“→”和“↓”，它
所描述的模式是什么？
解：1. 写出生成树的扩展树文法生成式集：
2. 检查非终止符的等价性。
a
$
b
a
b
b
a
b
001000010001000?????B B A A S
① ④ ⑤ ⑧ ⑦
?$A →1
4
A 2
A 3
?a A →2
?a A →3
?b A →5
9
A 6
A 5
?b A →4
⑿a A →12
(6)a A →6
A 7
A 8
⑺a A →7
⑻a A →8
⑼b A →9
A 10
⑽b A →10
A 11
⑾a A →11
A 12
查得1172A A A ≡≡。删除7A 和11A 及其后代生成式，其余生成式中的7A 和
11A 用2A 代替，合并后得到
3. 建立起始产生式。将?中的1A 用S 代替得到：
设推断的扩展树文法为),,,(S P r V G t ='，由以上推断得：
T N V V V =，},,,,,,,{10965432A A A A A A A S V N =，},,{b a $V T =
2)(=$r ，}0,1{)(=a r ，}1,2{)(=b r
P 的各生成式为
当基元a ，b 分别为“→”和“↓”时， 它所描述的模式如解图6.3所示：
a a
b b b b
a a
a a
a
$ $S →
4
A 2
?b A →5
9
A 6
A 5
?b A →4
(6)a A →6
A 2
⑼b A →9
A 10
⑽b A →10
A 2
?$A →1
4
A 2
A 3
?a A →2
?a A →3
?b A →5
9
A 6
A 5
?b A →4
(6)a A →6
A 2
⑼b A →9
A 10
⑽b A →10
A 2
?$S →
4
A 2
A 3
?a A →2
?a A →3
解图6.3 描述的模式
6.6 已知)(G L 的正样本集}0010,111,100,01{=+R ，试推断出余码文法c G 。 解：设余码文法为),,,(S P V V G T N c =。 (1) 由+R 得c G 的终止符集}1,0{=T V 。
(2) 求+R 的全部余码，组成非终止符集N V 。+R 的全部余码为
}0010,111,100,01{=+R D λ，}010,1{0=+R D ，}11,00{1=+R D
}{01λ=+R D ，}0{10=+R D ，}1{11=+R D ，}10{00=+R D }{100λ=+R D ，}{111λ=+R D ， }0{001=+R D ，}{0010λ=+R D
等号右边相同的合并，非空余码标以符号组成非终止符集N V ：
}0010,111,100,01{==+R D S λ，}010,1{01==+R D U ，}11,00{12==+R D U
}0{103==+R D U ，}1{114==+R D U ，}10{005==+R D U
所以},,,,,{54321U U U U U S V N =。 (3) 建立生成式集P 。
由10}010,1{U S D ==，有生成式10U S →； 由510}10{U U D ==，有生成式510U U →； 由320}0{U U D ==，有生成式320U U →； 由λ=30U D ，有生成式03→U ；
由21}11,00{U S D ==，有生成式21U S →； 由λ=11U D ，有生成式11→U ；
由421}1{U U D ==，有生成式421U U →； 由λ=41U D ，有生成式14→U ； 由351}0{U U D ==，有生成式351U U →； 所以余码文法),,,(S P V V G T N c =为
},,,,,{54321U U U U U S V N =，}1,0{=T V P ：10U S →，510U U →，320U U →，03→U 21U S →，11→U ，421U U →，14→U ，351U U →
6.7 设文法),,,(S P V V G T N =，其中},,{B A S V N =，}1,0{=T V ，P 的各生成式为
①1→S ，②1B S →，③B S →
④A B 1→，⑤A B B 1→，⑥0→A ，⑦0A A →
设待识别链1000=x ，试用填充树图法的顶下法分析x 是否属于)(G L ? 解：(1) 从S 开始考察P 中的①、②、③式：
若选①，则结果为x =1，排除；
若选②，导出的x 末位必为1，与题不符，排除； 选③式，如解图6.4(a)所示。
(2) 填充目标为B ，考察④、⑤均可填充，先试④，如解图6.4(b)所示。若不行，再返回用⑤式。
(3) 此时填充目标为A ，考察⑥、⑦。若选⑥，导出的x 为 2位，与题不符，排除。选⑦式，如解图6.4(c)所示。
(4) 类似地，得到图6.4所示各步结果，树叶为1000。 故x 属于)(G L 。
6.8 设上下文无关文法),,,(S P V V G T N =，},{C S V N =，}1,0{=T V ，P 中生成式的乔姆斯基范式为
CC S →，CS S →，1→S ，SC C →，CS C →，0→C
用CYK 分析法分析链01001=x 是否为该文法的合法句子。
解图6.4 填充树图过程 S
1
B
A
A
S
1
B
A
A
S
1
B
A
A
S
1
B
A
S B (a) (b) (c) (d) (e)
解：待识别链为5位，构造5行5列的三角形分析表，如解图6.5所示。
求表中元素ij t 的值：
(1) 令1=j ，求1i t ，51≤≤i 。 各子链为0，1，0，0，1。
对于01=a ，C t =11； 对于12=a ，S t =21； 对于03=a ，C t =31； 对于04=a ，C t =41。 对于15=a ，S t =41。
(2) 令2=j ，求2i t ，41≤≤i 。各子链为01，10，00，01。
对于0121=a a ，因有CS S →和CS C →，0→C ，1→S ，故S C t ,12=； 对于1032=a a ，有SC C →，1→S ，0→C ，故C t =22。 对于0043=a a ，有CC S →，0→C ，0→C ，故S t =32。
对于0154=a a ，有CS S →和CS C →，0→C ，1→S ，故S C t ,42=； (3) 令3=j ，求3i t ，31≤≤i 。各子链为010，100，001。
对于010321=a a a ，因有CC S →，
0→C ，10*
?C ；和SC C →，01*
?S ， 0→C 。故S C t ,13=。
类似地有S t =23，S C t ,33=，S C t ,14=，S C t ,24=，S C t ,15=。填表结果如解图6.6所示。
解图6.5 分析表
t 14 t 13 t 12 t 11
t 23 t 22 t 21
t 32 t 31
t 41
t 15 t 51
t 42 t 33 t 24
因为S 在15t 中，所以)(G L x ∈。
6.9 已知正则文法),,,(S P V V G T N =，其中},{B S V N =，},{b a V T =，P 的各生成式为
aB S →，aB B →，bS B →，a B →
构成对应的有限态自动机，画出自动机的状态转换图。
解：设有限态自动机),,,,(0∑=F q Q A δ，由A 与G 的对应关系得
∑==},{b a V
T
},,{F B S F V Q N ==
S q =0
δ：由aB S →，有B a S =),(δ；
由aB B →，a B →有},{),(F B a B =δ；
由bS B →，有S b B =),(δ。
故有限态自动机),,,,(0∑=F q Q A δ为
∑=},{b a ，},,{F B S Q =，S q
=0
δ：B a S =),(δ，},{),(F B a B =δ，S b B =),(δ
解图6.6 CYK 分析表填表结果 C,S C,S C
S C S
S C
C
C,S S
C,S C,S C,S C,S 解图 6.7 自动机的状态转换图
6.10 已知有限态自动机),,,,(0∑=F q Q A δ，其中
∑=}1,0{，},,,{32
1
q q
q q Q =，}{3q F =
A 的状态转换图如图6.15所示，求A 对应的正则文法G 。
解：设正则文法为),,,(S P V V G T N =，由G 与A 的对应关系得：
},,,{3210q q q q Q V N ==； ∑==}1,0{T V ；
0q S =；
根据状态转换图有：
P ：因}{)0,(20q q =δ，有200q q →； 因}{)1,(10q q =δ，有101q q →；
因}{)0,(31q q =δ，有310q q →；而F q ∈3，故01→q ； 因}{)1,(01q q =δ，有011q q →； 因}{)0,(02q q =δ，有020q q →；
因}{)1,(32q q =δ，有321q q →；而F q ∈3，故12→q ； 因}{)0,(13q q =δ，有130q q →； 因}{)1,(23q q =δ，有231q q →。
由此得正则文法),,,(S P V V G T N =为
},,,{3210q q q q Q V N ==，∑==}1,0{T V ，0q S =
图6.15 状态转换图
P ：200q q →，101q q →，01→q ，011q q → 020q q →，12→q ，130q q →，231q q →
6.11 已知上下文无关文法),,,(S P V V G T N =，其中
},{A S V N =，},,,{d c b a V T =
P 的各生成式为
cA S →，aAb A →，d A →
写出文法G 的格雷巴赫范式，构成相应的下推自动机。 解：文法),,,(S P V V G T N =的格雷巴赫范式为：
},,{B A S V N =，},,,{d c b a V T =
P ：cA S →，aAB A →，d A →，b B → 设相应的下推自动机为),,,,,,(00∑=F Z q ΓQ A p δ，其中
∑==},,,{d c b a V
T
，}{0q Q =
},,{B A S V ΓN ==，S Z =0，φ=F
转换规则δ：
因P 中有cA S →，故),(),,(00A q S c q =δ
因P 中有aAB A →，故),(),,(00AB q A a q =δ 因P 中有d A →，故),(),,(00λδq A d q = 因P 中有b B →，故),(),,(00λδq B b q = 即下推自动机),,,,,,(00∑=F Z q ΓQ A p δ为：
∑=},,,{d c b a ，}{0
q
Q =，},,{B A S Γ=，S Z =0，φ=F
P ：),(),,(00A q S c q =δ，),(),,(00AB q A a q =δ
),(),,(00λδq A d q =，),(),,(00λδq B b q =
第6章 模糊模式识别法习题解答
7.1 试分别说明近似性、随机性和含混性与模糊性在概念上的相同处与不同处。 解：(1) 近似性与模糊性的异同
① 共同点：描述上的不精确性。
② 区别：不精确性的根源和表现形式不同。
a) 近似性：问题本身有精确解，描述时的不精确性源于认识条件的局限性和认识过程发展的不充分性。
b) 模糊性：问题本身无精确解，描述的不精确性来源于对象自身固有的性态上的不确定性。
(2) 随机性与模糊性的异同 ① 共同点：不确定性。
② 区别：模糊性和随机性所表现出的不确定性的性质不同。
a) 模糊性：表现在质的不确定性。是由于概念外延的模糊性而呈现出的不确定性。
b) 随机性：是外在的不确定性。是由于条件不充分，导致条件与事件之间不能出现确定的因果关系，事物本身的性态(性质、状态、特征等)和类属是确定的。
c) 排中律：即事件的发生和不发生必居且仅居其一，不存在第三种现象。随机性遵守排中律，模糊性不遵守，它存在着多种，甚至无数种中间现象。
(3) 含混性与模糊性的异同 ① 共同点：不确定性。 ② 区别：
a) 含混性：由信息不充分（二义性）引起，一个含混的命题即是模糊的，又是二义的。一个命题是否带有含混性与其应用对象或上下文有关。
b) 模糊性：是质的不确定性。
7.2 已知论域}3,2,1,0{=X ，~A 和~
B 为X 中的模糊集合，分别为
()()()(){}3,5.0,2,4.0,1,3.0,
0,2.0~
=A
()()()(){}3,0,2,3.0,1,4.0,0,5.0~
=B
（1）求~~B A ，~~B A ，~A 和~B ；
（2）求()
~
~~A B A 。
解：（1）由()()()???
??=x x x B A B A ~~~
,max μμμ 有
~
~B A =()()()(){}3,5.0,2,4.0,1,4.0,
0,5.0
由()()()???
??=x x x B A B A ~~~
,min μμμ 有
~
~B A ()()()(){}3,0,2,3.0,1,3.0,
0,2.0=
由()()x x A A ~
~
1μμ-=有
~
A ()()()(){}3,5.0,2,6.0,1,7.0,0,8.0= ~
B ()()()(){}3,1,2,7.0,1,6.0,0,5.0=
（2）(
)
~
~~A B A
=()()()(){}3,5.0,2,4.0,1,4.0,
0,5.0 ()()()(){}3,5.0,2,6.0,1,7.0,0,8.0 ()()()(){}3,5.0,2,4.0,1,4.0,
0,5.0=
7.3 已知两个模糊集合
()(){}b a A ,8.0,,5.0~
=，
()(){}b a B ,2.0,,9.0~
=
试验证截集的两个性质：1）λλλB A B A =)~~(；2）λλλB A B A =)~~(。
解：（1）验证λλλB A B A =)~~(
左边：()(){}b a B A ,2.08.0,
,9.05.0~
~∨∨= ()(){}b a ,8.0,,9.0=
{}b a B A ,)~
~(5.0=
右边：{}b a A ,5.0=，{}a B =5.0，有{}b a B A ,5.05.0= 所以：左边 = 右边。 （2）验证λλλB A B A =)~
~(
左边：()(){}b a B A ,2.08.0,
,9.05.0~
~∧∧= ()(){}b a ,2.0,,5.0=
{}a B A =3.0)~
~(
右边：{}b a A ,3.0=，{}a B =3.0，有{}a B A =3.03.0 所以：左边 = 右边。
7.4 判断模糊矩阵????
??? ??=13.03.01.02.012.03.01.03.012.02.01.03.01R 是否是传递模糊矩阵。
解：????
??
?
????????? ??=13.03.01.02.012.03.01.03.012.02.01.03.0113.03.01.02.012.03.01.03.012.02.01.03.01 R R
???????
??∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨= 1.03.02.02.02.01.01.02.02.01.03.01.03.01.03.03.01.01.02.01??????
? ??=13.03.03.02.013.03.02.03.013.02.03.03.01 由计算结果可见R R R ? 不成立，故R 不是传递模糊矩阵。
7.5 证明7.5节定理1：对n n ?阶模糊等价矩阵R ，当且仅当[]1,0∈?λ时，λ
R 都是等价的布尔矩阵。 证明：设()ij r =R ，()λλij r =R
（1）证明自反性，即证明由1=ii r 可导出1=λii r 。
∴≤≤,
10λ 结论显然成立。
（2）证明对称性，即证明由ji ij r r =可导出λλji ij r r =。
采用反证法：设由ji ij r r =可导出λ
λji ij r r ≠，则
对[]1,0∈?λ，由λ
λji ij r r ≠必有ji ij r r ≠，与题设矛盾，得证。
（3）证明传递性（R R R ?），即证明由()jk ij n j ik r r r ∧∨≥=1
可导出()
λ
λλ
jk ij n
j ik r r r ∧∨≥=1
。
布尔矩阵中元素只有0和1，故考虑两种情况。
a) 当1=λik r 时，因为“1”是布尔矩阵中的最大值，故不等式()
λλλ
jk ij n
j ik r r r ∧∨≥=1
必然
成立。
b) 当0=λ
ik
r 时，有λ j ik r r r ∧∨≥=1 ，有 (){}n j r r r r r jk ij jk ij n j ik ,,1,max 1 =∧>?∧∨>?>=λλλ ()n j r r jk ij ,,1, =∧>∴λ 不失一般性，设ij r 为较小者，则 () 0001 =∧∨?=∧?=?>=λ λλ λλλjk ij n j jk ij ij ij r r r r r r () λλλ jk ij n j ik r r r ∧∨≥=1仍成立，即传递性成立。 λR 满足自反性、对称性、传递性， λR ∴是等价的布尔矩阵。 7.6 证明7.5节定理2：若10≤≤≤μλ，则μR 所分出的每一类必是λR 所分出的 某一类的子类。 证明：11=?≥==?≥?=≥λλ μμ λμij ij ij ij r r r r 亦即：由1=μij r 可导出1=λij r ，所以μR 所分出的每一类必是λR 所分出的某一类的子类。 7.7 设论域{}321,,x x x X =，在X 中有模糊集合 ()()(){}321,0.1,,8.0, ,6.0~ x x x A = ()()(){}321,8.0,,6.0,,4.0~ x x x B = 求格贴近度。 解：()()?? ????∧∨=∈?i B i A X x x x B A ~~~~μμ 8.08.06.04.0)8.00.1()6.08.0()4.06.0(=∨∨=∧∨∧∨∧= ()()?? ????∨∧=∈i B i A X x x x B A ~~~~μμ⊙ 6.00.18.06.0)8.00.1()6.08.0()4.06.0(=∧∧=∨∧∨∧∨= ()()[] ~~1~~21~,~B A B A B A ⊙-+=∴?σ()[]6.06.018.02 1 =-+= 7.8 设论域为{}4321,,,x x x x X =，~A 和~ B 是论域X 上的两个模糊集，X 上 每个元素隶属于~A 和~ B 的隶属度分别表示为 {}43213.0,4.0,7.0,5.0~ x x x x A = {}43215.0,7.0,8.0,7.0~ x x x x B = 下式为采用内积、外积函数表示的一种贴近度 () )~ ~ ~~()(1~,~B A B A A A B A ⊙-+--=?σ 其中A ，A 分别为模糊集~A 中隶属度的最大值和最小值，求贴近度() ~ ,~B A σ。 解：()()?? ????∧∨=∈?i B i A X x x x B A ~~~~μμ 7 .03.04.07.05.0)5.03.0()7.04.0()8.07.0()7.05.0(=∨∨∨=∧∨∧∨∧∨∧= ()()?? ????∨∧=∈i B i A X x x x B A ~~~~μμ⊙ 5 .05.07.08.07.0)5.03.0()7.04.0()8.07.0()7.05.0(=∧∧∧=∨∧∨∧∨∧∨= () )~ ~ ~~()(1~,~B A B A A A B A ⊙-+--=?σ 8.0)5.07.0()3.07.0(1=-+--= 7.9已知三个模糊集合分别为 ()()()(){}4321,1.0,,5.0,,4.0, ,2.0~ x x x x A = ()()(){}4321,1.0,,3.0,,6.0~ x x x B = ()()(){}3212,5.0,,3.0,,2.0~ x x x B = (1) 用海明距离和海明贴近度判别~1B ，~2B 哪个与~A 最相近； (2) 用格贴近度判别~1B ，~2B 哪个与~A 最相近。 解：(1) ① 用海明距离判断 ∑=-=4 1 1)()()~,~(~~1i i B i A H x x B A d μμ 6 .01.01.03.05.06.04.002.0=-+-+-+-= ∑=-=4 1 2)()()~,~(~~2i i B i A H x x B A d μμ 2 .001.05.05.03.04.02.02.0=-+-+-+-= )~ ,~()~,~(12B A d B A d H H < ∴~2B 与~A 最相近。 ② 利用海明贴近度判断 ??? ??~,~1B A H σ()()∑=--=41~ ~1411i i B i A x x μμ 85.0)02.02.02.0(4 1 1=+++-= ?? ? ??~,~2B A H σ()()∑=--=41~~2411i i B i A x x μμ 95.0)1.001.00(4 1 1=+++-= ? ? ? ??>??? ??~,~~,~12B A B A H H σσ ∴ ~2B 与~A 最相近。 (2) 用格贴近度()()[] ~ ~1~~21 ~,~B A B A B A ⊙-+=?σ判断 ()()?? ? ???∧∨=∈?i B i A X x x x B A ~~1~~1μμ 4 .01.03.04.00)1.01.0()3.05.0()6.04.0()02.0(=∨∨∨=∧∨∧∨∧∨∧= ()()?? ????∨∧=∈i B i A X x x x B A ~~1~~1μμ⊙ 1 .01.05.06.02.0)1.01.0()3.05.0()6.04.0()02.0(=∧∧∧=∨∧∨∧∨∧∨=????????? ??-+=??? ??∴?~~1~~21~,~111B A B A B A ⊙σ()[]65.01.014.021=-+= ()()?? ????∧∨=∈?i B i A X x x x B A ~~2~~2μμ 5 .005.03.02.0)01.0()5.05.0()3.04.0()2.02.0(=∨∨∨=∧∨∧∨∧∨∧=()()?? ? ???∨∧=∈i B i A X x x x B A ~~2~~2μμ⊙ 1 .01.05.04.02.0)01.0()5.05.0()3.04.0()2.02.0(=∧∧∧=∨∧∨∧∨∧∨= ????????? ??-+=??? ? ?∴?~~1~~21~,~222B A B A B A ⊙σ()[]7.01.015.021=-+= ? ? ? ??>??? ??~,~~,~12B A B A σσ ∴ ~2B 与~A 最相近。 7.10 已知模糊关系矩阵 ??? ??? ? ? ? ?=16.01.04.03.06.013.02.05.01.03.011.08 .04.02.01.011.03.05.08.01.01 R 判断R 是模糊相似矩阵还是模糊等价矩阵，并用截矩阵法按不同λ水平聚类，给出动态聚类图。 解：设论域为{}54 321,,,x x x x x X =。 ① 判断R 是模糊相似矩阵还是模糊等价矩阵。 模糊矩阵R 显然具有自反性和对称性，下面验证是否具有传递性： ??? ??? ? ? ? ????????? ? ?=16.01.04.03.06.013.02.05 .01.03.011.08 .04.02.01.011.03.05.08.01.01 16.01.04.03.06.013.02.05.01.03.011.08 .04.02.01.011 .03.05.08.01.01 R R 其中，()()()()()3.03.05.05.08.08.01.01.01111∧∨∧∨∧∨∧∨∧=r 13.05.08.01.01=∨∨∨∨= ()()()()()4.03.02.05.01.08.011.01.0112∧∨∧∨∧∨∧∨∧=r 3.03.02.01.01.01.0=∨∨∨∨= 类似地得：8.01.03.08.01.08.013=∨∨∨∨=r 5.01.05.03.01.05.014=∨∨∨∨=r 5.03.05.01.01.03.015=∨∨∨∨=r 3.03.02.01.01.01.021=∨∨∨∨=r 1 4.02.01.011.022=∨∨∨∨=r 2.01.02.01.01.01.023=∨∨∨∨=r 4.04.02.01.02.01.024=∨∨∨∨=r 4.04.02.01.04.01.025=∨∨∨∨=r …… 有 ??? ??? ? ? ? ?= 4.05.04.05.02.08 .04.04.02.013 .05.05.08.03.01 R R 可以看出，R 不满足R R R ?的传递性要求，故是模糊相似矩阵。 ② 用截矩阵法进行聚类。 根据逐步平方的方法，可得到模糊等价矩阵，设为R '： ??? ??? ?? ??='16.05.04.05.06.015.04.05.05.05.014.08 .04.04.04.014.05.05.08.04.01R 依次取R '的λ截矩阵聚类： ??? ??? ? ? ? ?='10000010000010000010000011 R 此等价布尔矩阵将模式分为5类：{}1x ，{}2x ，{}3x ，{}4x ，{}5x 。 ??? ?? ? ?? ??='1000001000001010001000101 0.8 R ，此时分为4类：{}31,x x ，{}2x ，{}4x ，{}5x 。 ??? ?? ? ?? ??='11000110000010100010001010.6 R ，此时分为3类：{}31,x x ，{}2x ，{}54,x x 。 ??? ?? ? ?? ??='11101111011110100010111010.5 R ，此时分为2类：{}5431,,,x x x x ，{}2x 。 ??? ?? ? ? ? ? ?='11111111111111111111111110.4 R ，此时归为1类。 动态聚类图如解图7.1所示： 7.11 设论域为{}7654321,,,,,,x x x x x x x X =，已知模糊相似矩阵为 ? ????? ???? ? ??=18.07.06.05.03 .03 .01 2.08.06.06.05.015.017.08.017.0 3.02 .01 4.0118.01R 按最大树法进行聚类，求1<λ，8.0<λ时的聚类结果。 解：① 构造最大树。 依次逐列画出R 中元素2.0,3.0,4.0,5.0,6.0,7.0,8.0,1=ij r 的元素集，至全部元素都已出现，标出权重，得最大树如解图7.2所示： ② 聚类。 54321 x x x x x 4 .05.06.08.01=====λλλλλ 0.7 0.8 0.8 1 1 0.8 4 6 2 5 7 3 1 解图7.1 动态聚类图 解图7.2 最大树 7.朴素贝叶斯方法的条件独立假设是( P(x| 3 i) =P(x1, x2,…,xn | co i) 第一章绪论 1 ?什么是模式？具体事物所具有的信息。 模式所指的不是事物本身，而是我们从事物中获得的 2?模式识别的定义？ 让计算机来判断事物。 3?模式识别系统主要由哪些部分组成？ 数据获取一预处理一特征提取与选择一分类器设计 / 分类决策。 第二章贝叶斯决策理论 P ( W 2 ) / P ( W 1 ) _,贝V X 1. 最小错误率贝叶斯决策过程？ 答：已知先验概率，类条件概率。利用贝叶斯公式 得到后 验概率。根据后验概率大小进行决策分析。 2. 最小错误率贝叶斯分类器设计过程？ 答：根据训练数据求出先验概率 P ( W i ), > 类条件概率分布P ( X | W i ), i 1 , 2 利用贝叶斯公式得到后验概率 P (W i 1 x) 1 如果输入待测样本 X ，计算X 的后验概率根据后验概率大小进行分类决策分析。 3. 最小错误率贝叶斯决策规则有哪几种常用的表示形式? 决策规则的4- I-J 形工战< d x +) — max 爪'(vr I A *), MJ A * 匚 w. 如SI 卫(A *叫)厂)= 如果lg=上心lw) py %) 心li M/ JC ) = —1IL | /( A *)J = — hi JC | 讥.j + 111 | i r 2 ) > 尸(“空) I MJ 4 .贝叶斯决策为什么称为最小错误率贝叶斯决策？ 答：最小错误率Bayes 决策使得每个观测值下的条件错误率最小因而保证了 (平均)错误率 最小。Bayes 决策是最优决策：即，能使决策错误率最小。 5. 贝叶斯决策是 由先验概率和(类条件概率)概率，推导(后验概率)概率，然后利用这 个概率进行决策。 6. 利用乘法法则和全概率公式证明贝叶斯公式 p(AB) p(A|B)p(B) p(B|A)p(A) P (A 」B ) 答： m 所以推出贝叶斯公式 p(B) p(B|Aj)p(Aj) j 1 P(W i |x) P (x | W i ) P(W i ) 2 P(x | W j ) P (w j ) j 1 1 , 2 .信息__。 如果 I (x) P (X | W i ) P (W i ) P(X | W j )P(W j ) max />(A' | t ),则 时 P(B |A i )P(AJ P ( B ) P ( B | A i ) P ( A i ) 7M P ( B | A j ) P ( A j ) 2 模 式 识 别 非 学 位 课 考 试 试 题 考试科目： 模式识别 考试时间 考生姓名： 考生学号 任课教师 考试成绩 一、简答题（每题6分，12题共72分）： 1、 监督学习和非监督学习有什么区别？ 参考答案：当训练样本的类别信息已知时进行的分类器训练称为监督学习，或者由教师示范的学习；否则称为非监督学习或者无教师监督的学习。 2、 你如何理解特征空间？表示样本有哪些常见方法？ 参考答案：由利用某些特征描述的所有样本组成的集合称为特征空间或者样本空间，特征空间的维数是描述样本的特征数量。描述样本的常见方法：矢量、矩阵、列表等。 3、 什么是分类器？有哪些常见的分类器？ 参考答案：将特征空中的样本以某种方式区分开来的算法、结构等。例如：贝叶斯分类器、神经网络等。 4、 进行模式识别在选择特征时应该注意哪些问题？ 参考答案：特征要能反映样本的本质；特征不能太少，也不能太多；要注意量纲。 5、 聚类分析中，有哪些常见的表示样本相似性的方法？ 参考答案：距离测度、相似测度和匹配测度。距离测度例如欧氏距离、绝对值距离、明氏距离、马氏距离等。相似测度有角度相似系数、相关系数、指数相似系数等。 6、 你怎么理解聚类准则？ 参考答案：包括类内聚类准则、类间距离准则、类内类间距离准则、模式与类核的距离的准则函数等。准则函数就是衡量聚类效果的一种准则，当这种准则满足一定要求时，就可以说聚类达到了预期目的。不同的准则函数会有不同的聚类结果。 7、 一种类的定义是：集合S 中的元素x i 和x j 间的距离d ij 满足下面公式： ∑∑∈∈≤-S x S x ij i j h d k k )1(1 ，d ij ≤ r ，其中k 是S 中元素的个数，称S 对于阈值h ，r 组成一类。请说明， 该定义适合于解决哪一种样本分布的聚类？ 参考答案：即类内所有个体之间的平均距离小于h ，单个距离最大不超过r ，显然该定义适合团簇集中分布的样本类别。 8、 贝叶斯决策理论中，参数估计和非参数估计有什么区别？ 参考答案：参数估计就是已知样本分布的概型，通过训练样本确定概型中的一些参数；非参数估计就是未知样本分布概型，利用Parzen 窗等方法确定样本的概率密度分布规律。 9、 基于风险的统计贝叶斯决策理论中，计算代价[λij ]矩阵的理论依据是什么？假设这个矩阵是 M ?N ，M 和N 取决于哪些因素？ 2013模式识别练习题 一. 填空题 1、模式识别系统的基本构成单元包括：模式采集、特征的选择和提取和模式分类。 2、统计模式识别中描述模式的方法一般使用特征矢量；句法模式识别中模式描述方法一般有串、树、 网。 3、影响层次聚类算法结果的主要因素有计算模式距离的测度、聚类准则、类间距离阈值、预定的类别数目。 4、线性判别函数的正负和数值大小的几何意义是正负表示样本点位于判别界面法向量指向的正负半空间中， 绝对值正比于样本点与判别界面的距离。 5、感知器算法1 ，H-K算法 2 。 （1）只适用于线性可分的情况；（2）线性可分、不可分都适用。 6、在统计模式分类问题中，聂曼- 况；最小最大判别准则主要用于先验概率未知的情况。 7、“特征个数越多越有利于分类”这种说法正确吗？错误。 特征选择的主要目的是。一般在可 和（C n m>>n ）的条件下，可以使用分支定界法以减少计算量。 8、散度J ij越大，说明ωi类模式与ωj类模式的分布差别越大； 当ωi类模式与ωj类模式的分布相同时，J ij= 0。 二、选择题 1、影响聚类算法结果的主要因素有（B、C、D ）。 A.已知类别的样本质量； B.分类准则； C.特征选取； D.模式相似性测度 2、模式识别中，马式距离较之于欧式距离的优点是（C、D）。 A.平移不变性； B.旋转不变性；C尺度不变性；D.考虑了模式的分布 3、影响基本K-均值算法的主要因素有(ABD）。 A.样本输入顺序； B.模式相似性测度； C.聚类准则； D.初始类中心的选取 4、位势函数法的积累势函数K(x)的作用相当于Bayes判决中的（B D）。 模式识别导论习题集 1、设一幅256×256大小的图像，如表示成向量，其维数是多少？如按行串接成一维，则第3行第4个象素在向量表示中的序号。 解：其维数为2；序号为256×2＋4＝516 2、如标准数字1在5×7的方格中表示成如图所示的黑白图像，黑为1，白为0，现若有一数字1在5×7网格中向左错了一列。试用分别计算要与标准模板之间的欧氏距离、绝对值偏差、偏差的夹角表示，异己用“异或”计算两者差异。 解：把该图像的特征向量为5×7＝35维，其中标准模版的特征向量为： x =[0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0]T 待测样本的特征向量为： y =[0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0]T ，绝对值偏差为351 |()|14i i i x y =-=∑， 夹角余弦为cos 0|||||||| T x y x y θ= =?，因此夹角为 90度。 3、哈明距离常用来计算二进制之间的相似度，如011与010的哈明距离为1，010与100距离为3。现用来计算7位LED 编码表示的个数字之间的相似度，试计算3与其它数字中的哪个数字的哈明距离最小。 解：是“9”，距离为1 4、对一个染色体分别用一下两种方法描述： (1)计算其面积、周长、面积/周长、面积与其外接矩形面积之比可以得到一些特征描述，如何利用这四个值？属于特征向量法，还是结构表示法？ (2)按其轮廓线的形状分成几种类型，表示成a 、b 、c 等如图表示，如何利用这些量？属哪种描述方法？ (3)设想其他结构描述方法。 解： （1）这是一种特征描述方法，其中面积周长可以体现染色体大小，面积周长比值越小，说明染色体越粗，面积占外接矩形的比例也体现了染色体的粗细。把这四个值组成一个维数为4的特征向量，该特征向量可以描述染色体的一些重要特征，可以按照特征向量匹配方法计算样本间的相似度。可以区分染色体和其它圆形、椭圆细胞结构。 （2）a 形曲线表示水平方向的凹陷，b 形表示竖直方向的凹陷，c 形指两个凹陷之间的突起，把这些值从左上角开始，按顺时针方向绕一圈，可以得到一个序列描述染色体的边界。它可以很好的体现染色体的形状，用于区分X 和Y 染色体很合适。这是结构表示法。 （3）可以先提取待识别形状的骨架，在图中用蓝色表示，然后，用树形表示骨架图像。 5. 设在一维特征空间中两类样本服从正态分布，1σ=2σ=1，μ1=0，μ2=3，两类先验概率之比e P P =)(/)(21ωω，试求按基于最小错误率贝叶斯决策原则的决策分界面的x 值。 解：按照公式（2－84），分界面上的点应满足： 模式识别习题Part 1 CH1 1. Describe the structure of a pattern classification system and give detailed information about each module. CH2 2. Bayesian Classifier (a) What is the decision rule of the Bayesian classifier? (b) Which independency assumption is used for naive Bayes and how does this affect the decision rule? (c) Show the optimality of the Bayesian classifier. 3. Vessel diseases are a growing problem in the western world. Now, there is a software that can classify a diseased person as actually diseased with 99% reliability. However, it may happen in 2% of the cases that a healthy person is mistakenly classified as diseased. A statistical analysis shows that the disease is apparent in one out of 100 patients. What is the probability that a patient is actually diseased if the system classifies a disease? 4. 分别写出在以下两种情况 1) P (x|w 1)=P (x|w 2) 2) P (w 1)=P (w 2) 下的最小错误率贝叶斯决策规则。 (《模式识别》第二版，边肇祺，pp.43 2.4) 5. 若λ11=λ22=0，λ12=λ21 ，证明此时最小最大决策面是来自两类的错误率相等。 (《模式识别》第二版，边肇祺，pp.43 2.7) 6. 二维正态分布，μ1=（?1,0）T ，μ2=（1,0）T ，Σ1=Σ2=Ι，P (ω1)=P (ω2)。试写 出对数似然比决策规则。 (《模式识别》第二版，边肇祺，pp.45 2.23) 7. 在习题6中若Σ1≠Σ2，Σ1=[1 12 1 21 ]，Σ2=[ 1? 12 ?1 2 1 ]，写出负对数似然比决策规则。 (《模式识别》第二版，边肇祺，pp.45 2.24) 模式识别 复习题 1. 简单描述模式识别系统的基本构成（典型过程）？ 2. 什么是监督模式识别（学习）？什么是非监督模式识别（学习）？ 对一副道路图像，希望把道路部分划分出来，可以采用以下两种方法： (1). 在该图像中分别在道路部分与非道路部分画出一个窗口，把在这两个窗口中的象素数据作为训练集，用某种判别准则求得分类器参数，再用该分类器对整幅图进行分类。 (2)．将整幅图的每个象素的属性记录在一张数据表中，然后用某种方法将这些数据按它们的自然分布状况划分成两类。因此每个象素就分别得到相应的类别号，从而实现了道路图像的分割。 试问以上两种方法哪一种是监督学习，哪个是非监督学习？ 3. 给出一个模式识别的例子。 4. 应用贝叶斯决策的条件是什么？列出几种常用的贝叶斯决策规 则，并简单说明其规则. 5. 分别写出在以下两种情况：（1）12(|)(|)P x P x ωω=；（2）12()() P P ωω=下的最小错误率贝叶斯决策规则。 6. （教材P17 例2.1） 7. （教材P20 例2.2），并说明一下最小风险贝叶斯决策和最小错误 率贝叶斯决策的关系。 8. 设在一维特征空间中有两类服从正态分布的样本， 12122,1,3,σσμμ====两类先验概率之比12(),() P e P ωω= 试确定按照最小错误率贝叶斯决策规则的决策分界面的x 值。 9. 设12{,,...,}N x x x =X 为来自点二项分布的样本集，即 1(,),0,1,01,1x x f x P P Q x P Q P -==≤≤=-，试求参数P 的最大似然估 计量?P 。 10. 假设损失函数为二次函数2??(,)()P P P P λ=-，P 的先验密度为均匀分布，即()1,01f P P =≤≤。在这样的假设条件下，求上题中的贝叶 斯估计量?P 。 11. 设12{,,...,}N x x x =X 为来自(|)p x θ的随机样本，其中0x θ≤≤时， 1 (|)p x θθ=，否则为0。证明θ的最大似然估计是max k k x 。 12. 考虑一维正态分布的参数估计。设样本（一维）12,,...,N x x x 都是由 独立的抽样试验采集的，且概率密度函数服从正态分布，其均值μ和方差2σ未知。求均值和方差的最大似然估计。 13. 设一维样本12{,,...,}N x x x =X 是取自正态分布2(,)N μσ的样本集，其中 均值μ为未知的参数，方差2σ已知。未知参数μ是随机变量，它的先验分布也是正态分布200(,)N μσ，200,μσ为已知。求μ的贝叶斯估计 ?μ 。 14. 什么是概率密度函数的参数估计和非参数估计？分别列去两种 参数估计方法和非参数估计方法。 15. 最大似然估计和Parzen 窗法的基本原理？ 第一章 绪论 1.什么是模式？具体事物所具有的信息。 模式所指的不是事物本身，而是我们从事物中获得的___信息__。 2.模式识别的定义？让计算机来判断事物。 3.模式识别系统主要由哪些部分组成？数据获取—预处理—特征提取与选择—分类器设计/ 分类决策。 第二章 贝叶斯决策理论 1.最小错误率贝叶斯决策过程？ 答：已知先验概率，类条件概率。利用贝叶斯公式 得到后验概率。根据后验概率大小进行决策分析。 2.最小错误率贝叶斯分类器设计过程？ 答：根据训练数据求出先验概率 类条件概率分布 利用贝叶斯公式得到后验概率 如果输入待测样本X ，计算X 的后验概率根据后验概率大小进行分类决策分析。 3.最小错误率贝叶斯决策规则有哪几种常用的表示形式？ 答 ： ???∈>=<2 1 1221_,)(/)(_)|() |()(w w x w p w p w x p w x p x l 则如果∑==2 1 ) ()|() ()|()|(j j j i i i w P w x P w P w x P x w P 2 ,1),(=i w P i 2 ,1),|(=i w x p i ∑== 21 ) ()|() ()|()|(j j j i i i w P w x P w P w x P x w P 4.贝叶斯决策为什么称为最小错误率贝叶斯决策？ 答：最小错误率Bayes 决策使得每个观测值下的条件错误率最小因而保证了（平均）错误率 最小。Bayes 决策是最优决策：即，能使决策错误率最小。 5.贝叶斯决策是由先验概率和（类条件概率）概率，推导（后验概率）概率，然后利用这个概率进行决策。 6.利用乘法法则和全概率公式证明贝叶斯公式 答： ∑====m j Aj p Aj B p B p A p A B p B p B A p AB p 1 ) ()|()() ()|()()|()(所以推出贝叶斯公式 7.朴素贝叶斯方法的条件独立假设是（P(x| ωi) =P(x1, x2, …, xn | ωi) = P(x1| ωi) P(x2| ωi)… P(xn| ωi)） 8.怎样利用朴素贝叶斯方法获得各个属性的类条件概率分布？ 答：假设各属性独立，P(x| ωi) =P(x1, x2, …, xn | ωi) = P(x1| ωi) P(x2| ωi)… P(xn| ωi) 后验概率：P(ωi|x) = P(ωi) P(x1| ωi) P(x2| ωi)… P(xn| ωi) 类别清晰的直接分类算，如果是数据连续的，假设属性服从正态分布，算出每个类的均值方差，最后得到类条件概率分布。 ∑== = M j j j i i i i i A P A B P A P A B P B P A P A B P B A P 1 ) ()| () ()|() () ()|()|( 一、填空与选择填空（本题答案写在此试卷上，30分） 1、模式识别系统的基本构成单元包括：模式采集、特征提取与选择 和模式分类。 2、统计模式识别中描述模式的方法一般使用特真矢量；句法模式识别中模式描述方法一般有串、树、网。 3、聚类分析算法属于（1）；判别域代数界面方程法属于（3）。 （1）无监督分类 (2)有监督分类（3）统计模式识别方法（4）句法模式识别方法 4、若描述模式的特征量为0-1二值特征量，则一般采用（4）进行相似性度量。 （1）距离测度（2）模糊测度（3）相似测度（4）匹配测度 5、下列函数可以作为聚类分析中的准则函数的有（1）（3）（4）。 （1）（2） (3) (4) 6、Fisher线性判别函数的求解过程是将N维特征矢量投影在（2）中进行。 （1）二维空间（2）一维空间（3）N-1维空间 7、下列判别域界面方程法中只适用于线性可分情况的算法有（1）；线性可分、不可分都适用的有（3）。 （1）感知器算法（2）H-K算法（3）积累位势函数法 8、下列四元组中满足文法定义的有（1）（2）（4）。 （1）({A, B}, {0, 1}, {A→01, A→ 0A1 , A→ 1A0 , B→BA , B→ 0}, A) （2）({A}, {0, 1}, {A→0, A→ 0A}, A) （3）({S}, {a, b}, {S → 00S, S → 11S, S → 00, S → 11}, S) （4）({A}, {0, 1}, {A→01, A→ 0A1, A→ 1A0}, A) 9、影响层次聚类算法结果的主要因素有（计算模式距离的测度、（聚类准则、类间距离门限、预定的 类别数目））。 10、欧式距离具有（ 1、2 ）；马式距离具有（1、2、3、4 ）。 （1）平移不变性（2）旋转不变性（3）尺度缩放不变性（4）不受量纲影响的特性 11、线性判别函数的正负和数值大小的几何意义是（正（负）表示样本点位于判别界面法向量指向的 正（负）半空间中；绝对值正比于样本点到判别界面的距离。）。 12、感知器算法1。 （1）只适用于线性可分的情况；（2）线性可分、不可分都适用。 1 ．设有下列语句，请用相应的谓词公式把它们表示出来： （1）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。答：定义谓词： MAN（X）：X是人， LIKE（X，Y）：X喜欢Y ((?X)(MAN(X)∧LIKE(X, 梅花)) ∧ ((?Y)(MAN(Y)∧LIKE(Y,菊花))∧ ((?Z)(MAN(Z)∧(LIKE(Z,梅花) ∧LIKE(Z,菊花)) （2）他每天下午都去打篮球。 答：定义谓词：TIME(X):X是下午 PLAY(X,Y):X去打Y （?X）TIME(X) PLAY(他,篮球) （3）并不是每一个人都喜欢吃臭豆腐。 定义谓词：MAN（X）：X是人 LIKE（X，Y）：X喜欢吃Y ┐（（?X）MAN（X） LIKE（X，CHOUDOUFU）） 2 ．请对下列命题分别写出它的语义网络： （1）钱老师从 6 月至 8 月给会计班讲《市场经济学》课程。 （2）张三是大发电脑公司的经理，他 35 岁，住在飞天胡同 68 号。 （3）甲队与乙队进行蓝球比赛，最后以 89 ： 102 的比分结束。 3. 框架表示法 一般来讲，教师的工作态度是认真的，但行为举止有些随便，自动化系教师一般来讲性格内向，喜欢操作计算机。方园是自动化系教师，他性格内向，但工作不刻苦。试用框架写出上述知识，并求出方圆的兴趣和举止？ 答： 框架名：<教师> 继承：<职业> 态度：认真 举止：随便 框架名：<自动化系教师> 继承：<教师> 性格：内向 兴趣：操作计算机框架名：<方园> 继承：<自动化系教师> 性格：内向 态度：不刻苦 兴趣：操作计算机 举止：随便 4. 剧本表示法 作为一个电影观众，请你编写一个去电影院看电影的剧本。 1、PCA和LDA的区别？ PCA是一种无监督的映射方法，LDA是一种有监督的映射方法。PCA只是将整组数据映射到最方便表示这组数据的坐标轴上，映射时没有利用任何数据部的分类信息。因此，虽然做了PCA后，整组数据在表示上更加方便（降低了维数并将信息损失降到了最低），但在分类上也许会变得更加困难；LDA在增加了分类信息之后，将输入映射到了另外一个坐标轴上，有了这样一个映射，数据之间就变得更易区分了（在低纬上就可以区分，减少了很大的运算量），它的目标是使得类别的点距离越近越好，类别间的点越远越好。 2、最大似然估计和贝叶斯方法的区别？p(x|X)是概率密度函数，X是给定的训练样本的集合，在哪种情况下，贝叶斯估计接近最大似然估计？ 最大似然估计把待估的参数看做是确定性的量，只是其取值未知。利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值(模型已知，参数未知）。贝叶斯估计则是把待估计的参数看成是符合某种先验概率分布的随机变量。对样本进行观测的过程，把先验概率密度转化为后验概率密度，利用样本的信息修正了对参数的初始估计值。 当训练样本数量趋于无穷的时候，贝叶斯方法将接近最大似然估计。如果有非常多的训练样本，使得p(x|X)形成一个非常显著的尖峰，而先验概率p(x)又是均匀分布，此时两者的本质是相同的。 3、为什么模拟退火能够逃脱局部极小值？ 在解空间随机搜索，遇到较优解就接受，遇到较差解就按一定的概率决定是否接受，这个概率随时间的变化而降低。实际上模拟退火算法也是贪心算法，只不过它在这个基础上增加了随机因素。这个随机因素就是：以一定的概率来接受一个比单前解要差的解。通过这个随机因素使得算法有可能跳出这个局部最优解。 4、最小错误率和最小贝叶斯风险之间的关系？ 基于最小风险的贝叶斯决策就是基于最小错误率的贝叶斯决策，换言之，可以把基于最小错误率决策看做是基于最小风险决策的一个特例，基于最小风险决策本质上就是对基于最小错误率公式的加权处理。 5、SOM的主要功能是什么？怎么实现的？是winner-all-take-all 策略吗？ SOM是一种可以用于聚类的神经网络模型。 自组织映射（SOM）或自组织特征映射（SOFM）是一种使用非监督式学习来产生训练样本的输入空间的一个低维（通常是二维）离散化的表示的人工神经网络（ANN）。自组织映射与其他人工神经网络的不同之处在于它使用一个邻近函数来保持输入控件的拓扑性质。SOM网络中, 某个输出结点能对某一类模式作出特别的反应以代表该模式类, 输出层上相邻的结点能对实际模式分布中相近的模式类作出特别的反映,当某类数据模式输入时, 对某一输出结点产生最大刺激( 获胜结点) , 同时对获胜结点周围的一些结点产生较大刺激。在训练的过程中, 不断对获胜结点的连接权值作调整, 同时对获胜结点的邻域结点的连接权值作调整; 随着训练的进行, 这个邻域围不断缩小, 直到最后, 只对获胜结点进行细微的连接权值调整。 不是winner-all-take-all 策略。获胜结点产生刺激，其周围的结点也会产生一定程度的兴奋。 6、期望算法需要哪两步？请列出可能的公式并做必要的解释。 E-Step和M-Step。E-Step叫做期望化步骤，M-Step为最大化步骤。 整体算法的步骤如下所示： 1、初始化分布参数。 2、(E-Step)计算期望E，利用对隐藏变量的现有估计值，计算其最大似然估计值，以此实现期望化的过程。 3、(M-Step)最大化在E-步骤上的最大似然估计值来计算参数的值 第一章 绪论 1.什么是模式具体事物所具有的信息。 模式所指的不是事物本身，而是我们从事物中获得的___信息__。 2.模式识别的定义让计算机来判断事物。 3.模式识别系统主要由哪些部分组成数据获取—预处理—特征提取与选择—分类器设计/ 分类决策。 第二章 贝叶斯决策理论 ~ 1.最小错误率贝叶斯决策过程 答：已知先验概率，类条件概率。利用贝叶斯公式 得到后验概率。根据后验概率大小进行决策分析。 2.最小错误率贝叶斯分类器设计过程 答：根据训练数据求出先验概率 类条件概率分布 利用贝叶斯公式得到后验概率 、 如果输入待测样本X ，计算X 的后验概率根据后验概率大小进行分类决策分析。 3.最小错误率贝叶斯决策规则有哪几种常用的表示形式 答： 4.贝叶斯决策为什么称为最小错误率贝叶斯决策 答：最小错误率Bayes 决策使得每个观测值下的条件错误率最小因而保证了（平均）错误率 最小。Bayes 决策是最优决策：即，能使决策错误率最小。 5.贝叶斯决策是由先验概率和（类条件概率）概率，推导（后验概率）概率，然后利用这个概率进行决策。 6.利用乘法法则和全概率公式证明贝叶斯公式 答： ∑====m j Aj p Aj B p B p A p A B p B p B A p AB p 1 ) ()|()() ()|()()|()(所以推出贝叶斯公式 ???∈>=<211 221_,)(/)(_)|()|()(w w x w p w p w x p w x p x l 则如果∑== 2 1 )()|() ()|()|(j j j i i i w P w x P w P w x P x w P 2,1),(=i w P i 2,1),|(=i w x p i ∑==2 1 )()|() ()|()|(j j j i i i w P w x P w P w x P x w P ∑=== M j j j i i i i i A P A B P A P A B P B P A P A B P B A P 1 ) ()| () ()|()() ()|()|( 《模式识别》试题库 一、基本概念题 1.1 模式识别的三大核心问题是： 、 。 1.2、模式分布为团状时，选用 聚类算法较好。 1.3 欧式距离具有 。 马式距离具有 。 （1）平移不变性 （2）旋转不变性 （3）尺度缩放不变性 （4）不受量纲影响的特性 1.4 描述模式相似的测度有： 。 （1）距离测度 （2）模糊测度 （3）相似测度 （4）匹配测度 1.5 利用两类方法处理多类问题的技术途径有：（1） ；（2） ； （3） 。其中最常用的是第 个技术途径。 1.6 判别函数的正负和数值大小在分类中的意义是： ， 。 1.7 感知器算法 。 （1）只适用于线性可分的情况；（2）线性可分、不可分都适用。 1.8 积累位势函数法的判别界面一般为 。 （1）线性界面；（2）非线性界面。 1.9 基于距离的类别可分性判据有： 。 （1）1[]w B Tr S S - （2） B W S S （3）B W B S S S + 1.10 作为统计判别问题的模式分类，在（ ）情况下，可使用聂曼-皮尔逊判决准则。 1.11 确定性模式非线形分类的势函数法中，位势函数K(x,x k )与积累位势函数K(x)的关系为（ ）。 1.12 用作确定性模式非线形分类的势函数法，通常，两个n 维向量x 和x k 的函数K(x,x k )若同时满足下列三个条件，都可作为势函数。 ①（ ）； ②（ ）； ③ K(x,x k )是光滑函数，且是x 和x k 之间距离的单调下降函数。 1.13 散度J ij 越大，说明ωi 类模式与ωj 类模式的分布（ ）。当ωi 类模式与ωj 类模式的分布相同时，J ij =（ ）。 1.14 若用Parzen 窗法估计模式的类概率密度函数，窗口尺寸h1过小可能产生的问题是（ ），h1过大可能产生的问题是（ ）。 1.15 信息熵可以作为一种可分性判据的原因 是： 。 1.16作为统计判别问题的模式分类，在（ ）条件下，最小损失判决规则与最小错误判决规则是等价的。 1.17 随机变量l(x )=p(x |ω1)/p(x |ω2)，l(x )又称似然比，则 E {l(x )|ω2}=（ ）。在最小误判概率准则下，对数似然比Bayes 判决规则为（ ）。 1.18 影响类概率密度估计质量的最重要因素是 （ ）。 第一章 绪论 1.什么是模式？具体事物所具有的信息。 模式所指的不是事物本身，而是我们从事物中获得的___信息__。 2.模式识别的定义？让计算机来判断事物。 3.模式识别系统主要由哪些部分组成？数据获取—预处理—特征提取与选择—分类器设计/ 分类决策。 第二章 贝叶斯决策理论 1.最小错误率贝叶斯决策过程？ 答：已知先验概率，类条件概率。利用贝叶斯公式 得到后验概率。根据后验概率大小进行决策分析。 2.最小错误率贝叶斯分类器设计过程？ 答：根据训练数据求出先验概率 类条件概率分布 利用贝叶斯公式得到后验概率 如果输入待测样本X ，计算X 的后验概率根据后验概率大小进行分类决策分析。 3.最小错误率贝叶斯决策规则有哪几种常用的表示形式？ 答： 4.贝叶斯决策为什么称为最小错误率贝叶斯决策？ 答：最小错误率Bayes 决策使得每个观测值下的条件错误率最小因而保证了（平均）错误率 最小。Bayes 决策是最优决策：即，能使决策错误率最小。 5.贝叶斯决策是由先验概率和（类条件概率）概率，推导（后验概率）概率，然后利用这个概率进行决策。 6.利用乘法法则和全概率公式证明贝叶斯公式 答：∑====m j Aj p Aj B p B p A p A B p B p B A p AB p 1) ()|()() ()|()()|()(所以推出贝叶斯公式 7.朴素贝叶斯方法的条件独立假设是（P(x| ωi) =P(x1, x2, …, xn | ωi) = P(x1| ωi) P(x2| ωi)… P(xn| ωi)） 8.怎样利用朴素贝叶斯方法获得各个属性的类条件概率分布？ 答：假设各属性独立，P(x| ωi) =P(x1, x2, …, xn | ωi) = P(x1| ωi) P(x2| ωi)… P(xn| ωi) 后验概率：P(ωi|x) = P(ωi) P(x1| ωi) P(x2| ωi)… P(xn| ωi) 类别清晰的直接分类算，如果是数据连续的，假设属性服从正态分布，算出每个类的均值方差，最后得到类条件概率分布。 均值：∑==m i xi m x mean 11)( 方差：2)^(11)var(1∑=--=m i x xi m x 9.计算属性Marital Status 的类条件概率分布 给表格计算，婚姻状况几个类别和分类几个就求出多少个类条件概率。 ???∈>=<2 11221_,)(/)(_)|()|()(w w x w p w p w x p w x p x l 则如果∑==21 )()|()()|()|(j j j i i i w P w x P w P w x P x w P 2,1),(=i w P i 2,1),|(=i w x p i ∑==2 1)()|()()|()|(j j j i i i w P w x P w P w x P x w P ∑=== M j j j i i i i i A P A B P A P A B P B P A P A B P B A P 1) ()| ()()|()()()|()|( 一、判断题（共10个题） 请写清楚题号，在答卷纸上填写√或×，不要直接在本页回答。 特别说明：本部分题目的得分规则为：答对一个题，得2分；不答（即放弃回答）的题，本题得0分；答错一个题，得-2分（即反扣2分）。本道大题得负分的，从其他大题扣除。所以，判断题的回答，建议慎重对待。 1. 基于最小错误率的贝叶斯概率是 损失函数0-1的 基于最小风险贝叶斯概率的特例 2. 监督参数估计是（太多记不住）。。。 3. 单隐层神经网络在经过足够训练后，不管节点多少，总能找到全局最优解。 4. 决策树可以生成规则集，且生成的规则集是可以解释的。 5. SVM 向量机在样本数据少、非线性的情况下有优势。 6. Bagging 是一种串行学习框架。 7. 泛化能力指的是在训练集中体现的特点。 8. Self_Trainning 是一种半监督的方法。 9. 决策树属性选择是依照信息增益比。 10. 2006年以前，多隐层神经网络因为缺乏良好的算法，限制了深度学习的发展。 二、计算题 设在某个局部地区细胞识别中正常和异常两类的先验概率分别为： 正常状态： 异常状态： 现有一待识别的细胞，其观察值为x ，从类条件概率密度分布曲线上查得 2ω 1ω9.0)(1=ωP 1 .0)(2=ωP 试使用贝叶斯决策对该细胞x 进行分类（要求给出具体计算过程及计算结果） 解： 利用贝叶斯公式，分别计算出 及 的后验概率 根据贝叶斯决策规则，有 所以合理的决策规则是把x 归类于正常状态。 三、简答题 1、应用贝叶斯决策需要满足的三个前提条件是什么？ （1）分类的类别数；（2）先验概率；（3）各类的类条件概率密度。 2、试简述您对先验概率和后验概率理解 先验概率：预先已知的或者可以估计的模式识别系统位于某种类型的概率。根据大数定 律，当训练集包含充足的独立同分布样本时，先验概率就可以通过各类样本出现的频率4 .0)|(,2.0)|(21==ωωx p x p 182 .0)|(1)|(818.01.04.09.02.09.02.0)()|()()|()|(1221111=-==?+??==∑=x P x P p x p p x p x P j j j ωωωωωωω182 .0)|(818.0)|(21=>=x P x P ωω1ω2 ω 《模式识别》试题库 一、基本概念题 1.1 模式识别的三大核心问题是：、、。 1.2、模式分布为团状时，选用聚类算法较好。 1.3 欧式距离具有。马式距离具有。 （1）平移不变性（2）旋转不变性（3）尺度缩放不变性（4）不受量纲影响的特性 1.4 描述模式相似的测度有：。 （1）距离测度（2）模糊测度（3）相似测度（4）匹配测度 1.5 利用两类方法处理多类问题的技术途径有：（1）；（2）； （3）。其中最常用的是第个技术途径。 1.6 判别函数的正负和数值大小在分类中的意义 是：， 。 1.7 感知器算法。 （1）只适用于线性可分的情况；（2）线性可分、不可分都适用。 1.8 积累位势函数法的判别界面一般为。 （1）线性界面；（2）非线性界面。 1.9 基于距离的类别可分性判据有：。 （1） 1 [] w B Tr S S - （2） B W S S（3） B W B S S S + 1.10 作为统计判别问题的模式分类，在（）情况下，可使用聂曼-皮尔逊判决准则。 1.11 确定性模式非线形分类的势函数法中，位势函数K(x,x k)与积累位势函数K(x)的关系为 （）。 1.12 用作确定性模式非线形分类的势函数法，通常，两个n维向量x和x k的函数K(x,x k)若同时满足下列三个条件，都可作为势函数。 ①（）； ②（ ）； ③ K(x,x k )是光滑函数，且是x 和x k 之间距离的单调下降函数。 1.13 散度J ij 越大，说明ωi 类模式与ωj 类模式的分布（ ）。当ωi 类模式与ωj 类模式的分布相同时，J ij =（ ）。 1.14 若用Parzen 窗法估计模式的类概率密度函数，窗口尺寸h1过小可能产生的问题是（ ），h1过大可能产生的问题是（ ）。 1.15 信息熵可以作为一种可分性判据的原因 是： 。 1.16作为统计判别问题的模式分类，在（ ）条件下，最小损失判决规则与最小错误判决规则是等价的。 1.17 随机变量l(x )=p( x |ω1)/p( x |ω2)，l( x )又称似然比，则E {l( x )|ω2}= （ ）。在最小误判概率准则下，对数似然比Bayes 判决规则为（ ）。 1.18 影响类概率密度估计质量的最重要因素是 （ ）。 1.19 基于熵的可分性判据定义为 )] |(log )|([1 x P x P E J i c i i x H ωω∑=-=，J H 越（ ），说明模式的 可分性越强。当P(ωi | x ) =（ ）(i=1,2,…,c)时，J H 取极大值。 1.20 Kn 近邻元法较之于Parzen 窗法的优势在于 （ ）。 上述两种算法的共同弱点主要是（ ）。 1.21 已知有限状态自动机Af=(∑，Q ，δ，q0，F)，∑={0，1}；Q={q0，q1}； δ：δ(q0，0)= q1，δ(q0，1)= q1，δ(q1，0)=q0，δ(q1，1)=q0；q0=q0；F={q0}。现有输入字符串：(a) 00011101011，(b) 1100110011，(c) 101100111000，(d)0010011，试问，用Af 对上述字符串进行分类的结果为（ ）。 1.22 句法模式识别中模式描述方法有： 。 （1）符号串 （2）树 （3）图 （4）特征向量 复习要点 绪论 1、举出日常生活或技术、学术领域中应用模式识别理论解决问题的实例。 答：我的本科毕设内容和以后的研究方向为重症监护病人的状态监测与预诊断，其中的第一步就是进 行ICU病人的死亡率预测，与模式识别理论密切相关。主要的任务是分析数据库的8000名ICU病人，统计 分析死亡与非死亡的生理特征，用于分析预测新进ICU病人的病情状态。 按照模式识别的方法步骤，首先从数据库中采集数据，包括病人的固有信息，生理信息，事件信息等并分为死亡组和非死亡组，然后分别进行数据的预处理，剔除不正常数据，对数据进行插值并取中值进行第一次特征提取，然后利用非监督学习的方法即聚类分析进行第二次特征提取，得到训练样本集和测试样本集。分别利用判别分析，人工神经网络，支持向量机的方法进行训练，测试，得到分类器，实验效果比传统ICU 中采用的评价预测系统好一些。由于两组数据具有较大重叠，特征提取，即提取模式特征就变得尤为重要。语音识别，图像识别，车牌识别，文字识别，人脸识别，通信中的信号识别； ① 文字识别 汉字已有数千年的历史，也是世界上使用人数最多的文字，对于中华民族灿烂文化的形成和发展有着不可 磨灭的功勋。所以在信息技术及计算机技术日益普及的今天，如何将文字方便、快速地输入到计算机中已 成为影响人机接口效率的一个重要瓶颈，也关系到计算机能否真正在我过得到普及的应用。目前，汉字输 入主要分为人工键盘输入和机器自动识别输入两种。其中人工键入速度慢而且劳动强度大；自动输入又分 为汉字识别输入及语音识别输入。从识别技术的难度来说，手写体识别的难度高于印刷体识别，而在手写 体识别中，脱机手写体的难度又远远超过了联机手写体识别。到目前为止，除了脱机手写体数字的识别已 有实际应用外，汉字等文字的脱机手写体识别还处在实验室阶段。 ②语音识别 语音识别技术技术所涉及的领域包括：信号处理、模式识别、概率论和信息论、发声机理和听觉机理、人 工智能等等。近年来，在生物识别技术领域中，声纹识别技术以其独特的方便性、经济性和准确性等优势 受到世人瞩目，并日益成为人们日常生活和工作中重要且普及的安验证方式。而且利用基因算法训练连续 隐马尔柯夫模型的语音识别方法现已成为语音识别的主流技术，该方法在语音识别时识别速度较快，也有 较高的识别率。 ③ 指纹识别 我们手掌及其手指、脚、脚趾内侧表面的皮肤凹凸不平产生的纹路会形成各种各样的图案。而这些皮肤的 纹路在图案、断点和交叉点上各不相同，是唯一的。依靠这种唯一性，就可以将一个人同他的指纹对应起 来，通过比较他的指纹和预先保存的指纹进行比较，便可以验证他的真实身份。一般的指纹分成有以下几 个大的类别:环型(loop),螺旋型(whorl),弓型(arch),这样就可以将每个人的指纹分别归类，进行检索。指 纹识别基本上可分成：预处理、特征选择和模式分类几个大的步骤。 ③ 遥感 遥感图像识别已广泛用于农作物估产、资源勘察、气象预报和军事侦察等。 ④医学诊断 在癌细胞检测、X射线照片分析、血液化验、染色体分析、心电图诊断和脑电图诊断等方面，模式识别已取 得了成效。 第5章 句法模式识别习题解答 6.1 用链码法描述5～9五个数字。 解：用弗利曼链码表示，基元如解图6.1所示： 数字5~9的折线化和量化结果如解图6.2所示： 各数字的链码表示分别为： “5”的链码表示为434446600765=x ； “6”的链码表示为3444456667012=x ； “7”的链码表示为00066666=x ； “8”的链码表示为21013457076543=x ； “9”的链码表示为5445432107666=x 。 1 7 解图6.1 弗利曼链码基元 解图6.2 数字5~9的折线化和量化结果 6.2 定义所需基本基元，用PDL 法描述印刷体英文大写斜体字母“H ”、“K ”和 “Z ”。 解：设基元为： 用PDL 法得到“H ”的链描述为)))))(~((((d d c d d x H ?+?+=； “K ”的链描述为))((b a d d x K ??+=； “Z ”的链描述为))((c c g x Z ?-=。 6.3 设有文法),,,(S P V V G T N =，N V ，T V 和P 分别为 },,{B A S V N =，},{b a V T = ：P ①aB S →，②bA S →，③a A →，④aS A → ⑤bAA A →，⑥b B →，⑦bS B →，⑧aBB B → 写出三个属于)(G L 的句子。 解： 以上句子ab ，abba ，abab ，ba ，baab ，baba 均属于)(G L 。 6.4 设有文法),,,(S P V V G T N =，其中},,,{C B A S V N =，}1,0{=T V ，P 的各 生成式为 ①A S 0→，②B S 1→，③C S 1→ b c a d e abba abbA abS aB S ???? ① ⑦ ② ③ ab aB S ?? ① ⑥ ba bA S ?? ② ③ abab abaB abS aB S ???? ① ⑦ ① ⑥ baab baaB baS bA S ???? ② ④ ① ⑥ baba babA baS bA S ???? ② ④ ② ③模式识别习题
模式识别试题答案
最新模式识别练习题
模式识别导论习题集
模式识别 习题集
模式识别复习题1
模式识别习题及答案
模式识别试题及总结
模式识别习题答案
模式识别习题集答案解析
模式识别习题及答案
《模式识别》试题库
模式识别习题及答案
山东大学2016模式识别考试题回忆版
模式识别复习题分解
模式识别复习要点和参考习题
模式识别习题参考1-齐敏教材第6章